Data and Storage

Every database is a file, plus rules. The rules keep the file correct when two programs use it at the same time, and when the power fails. These chapters build those rules from zero: append-only records, a lock, an index, and a log. The program writes the log before the change that the log describes.

1. An append-only file cannot delete. To remove a value, you add a record. Thus every log-structured store has tombstones.
2. Read, modify, write is three steps. The other writer can change the data in the gap between the first step and the third step.
3. A race can give a different answer on each run. That property makes a race expensive to find, but it does not make a race rare.
4. An index does not make the data smaller. An index adds a second structure, and you must keep the two structures consistent.

5 chapters.

• An Append-Only Record StoreNever modify written data. A delete is a record that you add.
• Two Writers, One FileWhat a lost update looks like, and the lock that prevents it.
• An Index Over the LogA second structure, made from the first, that you must now keep in agreement with the first.
• A Write-Ahead LogWrite down what you will do, then do it. Recovery is a replay of the note.
• A Query EngineThe parser asks what. The planner asks how, and the planner does the real work of a database.