Bigtable: A Distributed Storage System for Structured Data
A sparse, distributed, persistent multidimensional sorted map - and the sort order of the row key is the entire schema design.
Read the original ↗The most useful thing in this paper is a single sentence describing what a Bigtable is, and most retellings skip past it to the architecture. The data model is the design. Everything else in the paper is a consequence of it.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardStorage EnginesSSTables, the memtable and compaction, taken apart slowly
- BoardB-Tree on Diskthe structure Bigtable does not use, and the reason why
- BoardPartitioningtablets are row ranges, so partitioning by range is the design and not a setting
- BoardSplitting the Ledgera row key that puts every write at the end of the range - the hotspot this model is famous for
- BoardThe Right Book for the Jobwhere a wide-column store wins, and the queries it hands back to you
- LabLSM vs B-treeBigtable's engine against the alternative, with the dial that shows where the bill flips
- LabThe write-ahead logthe commit log in front of the memtable, and what checkpointing costs on the way back
- LabSplitting the ledgerwhat a badly chosen key does to a range-partitioned table
- LabThe right book for the jobfourteen queries against six stores - the row key decides which of them you can answer
- VideoChoosing a datastore: the workload picks the bookthe workload picks the store, which is the choice this paper is one answer to
- VideoThe shard key that lied: when a correct decision goes wrong on its owna key that was correct for years and then was not - the risk you take on when the key is the schema
- LessonStorage EnginesUses the board Storage Engines
- LessonBuild Your Own LSM TreeUses the board Storage Engines
- LessonLSM 01-02: The Memtable and the LogUses the board Storage Engines
- LessonB-Tree on DiskUses the board B-Tree on Disk
- LessonWhich shortcut to buildUses the board B-Tree on Disk
- LessonBuild three ways to joinUses the board B-Tree on Disk
- LessonPartitioningUses the board Partitioning
- LessonBuild Your Own DynamoUses the board Partitioning
- LessonKV: the ringUses the board Splitting the Ledger
- LessonSplitting the ledger (sharding)Uses the board Splitting the Ledger
- LessonLSM Capstone: EverythingUses the board The Right Book for the Job
- LessonThe Right Book for the Job (databases, deeply)Uses the board The Right Book for the Job
- LessonThe last vada (inventory contention and locking)Uses the board The Right Book for the Job
Further reading
Read the original for the full argument and its evidence.
- The paper (PDF) ↗OSDI 2006. Section 2 is the data model and is the part worth rereading; sections 5 and 6 are the storage engine and the refinements that make it fast.
- Spanner (PDF) ↗Later work, and the answer to this paper's biggest omission - its own introduction explains that Bigtable's lack of cross-row transactions is why it was built.