Google Bigtable

Google's managed wide-column service, and the paper that started this whole family: a sorted map keyed by row, where performance is decided almost entirely by row-key design. Interviewers use it to test lexicographic key design — specifically how you avoid hotspotting on sequential keys.