Large-scale Incremental Processing Using Distributed Transactions and Notifications
Transactions and triggers bolted onto a store built without either, so an index can be updated one page at a time instead of rebuilt whole.
Read the original ↗The paper behind Caffeine, and the reason a page you publish now can be in Google within minutes instead of within weeks. Its mechanism is distributed transactions on a store that was designed without them - and it prints the price it paid, which almost nobody who cites it repeats.
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.
- BoardFreshness & Tiered Servingthe batch-to-incremental switch this paper is, with Caffeine and weeks-to-minutes on the board
- BoardThe Inverted Indexthe index built as a MapReduce - the pipeline this replaced for the indexing job
- BoardStorage & Compute InfraBigtable, the store whose missing cross-row transactions this paper puts back
- BoardBatch Processingimmutable input and a materialised stage per job - the model that cannot touch one document
- BoardStream Processingincremental derived data as a field, which is where the answer here belongs
- BoardTransactionsthe isolation ladder: this lands on snapshot isolation, write skew and all
- BoardThe Two Ledgers Must Agreetwo-phase commit, run by the client with no coordinator alive to block on
- LabIsolation levelsthe rung this protocol sits on, and the races it still allows
- LabThe two ledgers must agreeprepare then commit, and what a participant left holding a lock costs
- VideoDistributed transactions: the two ledgers must agreethe crash between two writes, which here is a client dying between prewrite and commit
- VideoExactly-once: the outbox, the retry chain, and reconciliationthe outbox: protocol state written into the same store as the data, which is this design at small scale
- VideoThe data platform: measuring everything, testing anythinga batch pipeline with a faster path beside it - the hybrid shape a freshness conversion ends at
- LessonGoogle Search - the case studyUses the board Freshness & Tiered Serving
- LessonBatch ProcessingUses the board Batch Processing
- LessonStream ProcessingUses the board Stream Processing
- LessonTransactionsUses the board Transactions
- LessonThe Two Ledgers Must Agree (Distributed Transactions)Uses the board The Two Ledgers Must Agree
Further reading
Read the original for the full argument and its evidence.
- The paper (PDF) ↗OSDI 2010. Section 2.2 is the transaction protocol with the pseudocode worth tracing by hand; section 4 is the indexing deployment and the resource comparison against MapReduce.
- Google's Caffeine announcement ↗2010, and deliberately says nothing about how. Useful as the outside view of the same change: the user-visible claim the paper is the mechanism for.
- Bigtable: A Distributed Storage System for Structured Data ↗The store underneath, and the decision this paper is working around - read section 2 for the data model the lock and write columns are bolted onto.