Indexing an Immutable Ledger: Intents, Backfills and Checksums at Trillion-Row Scale
Strong, eventual and time-range indexes for financial records, a two-phase write that cannot orphan an entry, and how to prove a trillion-row migration.
On this page
Immutability is a gift for integrity and a tax on queries. You cannot reshape a ledger row to suit a new screen, so every new question becomes a new index. The craft is choosing, for each question, how fresh the index must be and what that freshness costs.
The ledger contract
Two properties define the system: records never change once written, and they can be found fast by many keys. With billions of trips and deliveries driving tens of billions of financial transactions, the second property means a vast number of index entries sitting beside the data.
Three indexes, three consistency promises
| Index | Promise | Example consumer | How it is built |
|---|---|---|---|
| Strongly consistent | Read your own write, immediately | Card authorization hold at trip start | Two-phase style intent, record, commit |
| Eventually consistent | Updated shortly after the write | Payment history screen | Materialised view refreshed in the background |
| Time-range | Efficient bounded scans of a window | Archive to cold storage, seal for compliance | Single table partitioned by timestamp |
Choose the weakest promise the use case can tolerate. A card hold must be visible instantly, or the rider can be charged twice. A history list can lag a few seconds and nobody notices.
The strong index: intent, record, commit
- Write the index intent
Record that an entry is about to exist, in every index it needs. If this write fails, the whole insert fails, and nothing is left behind.
- Write the record
Insert the actual ledger entry into the main store.
- Commit the index, asynchronously
Flip the intent to committed in the background so the caller does not wait for it.
The failure case is the interesting one: the intent was written, the record write failed. Now an index entry points at a record that does not exist. Rather than a janitor job, the read path repairs it.
read index entry
committed? -> return the record
pending? -> look in the main store
record exists -> commit the entry (async), return record
record missing -> roll back the intent, return nothing
Writers never hold locks across systems, and orphaned intents are cleaned up exactly when someone would trip over them. The write path stays fast because the slow step, committing, is off the critical path.
If you wrote the record first and the index second, a crash between them leaves a record that cannot be found, which for money means an invisible charge. An orphaned intent only produces an entry that resolves to “no such record”, which is harmless and self-healing.
The eventual index: materialised views
A materialised view stores a precomputed query result. A background process scans for changes and refreshes it, with a configurable consistency window setting how often. Reads are cheap and writes are not slowed. The cost is staleness, which is fine for display surfaces.
The time-range index
Batch jobs ask questions like “everything between 10:00 and 10:30”. A design that works well:
- One table, partitioned by the full timestamp so writes spread evenly and no partition runs hot.
- Sorted storage by partition and sort key.
- Reads as prefix scans over fixed granules: 30 minutes becomes three 10-minute scans, run on every shard in parallel, then scatter-gathered and merged in sorted order.
Changing an index without breaking the system
Indexes are added and redefined over the life of the ledger. A state machine makes each change safe:
- Create the new index table
Empty and unused, so nothing can break.
- Backfill history
Build entries from historical data in cold storage, rate-limited and batched.
- Validate completeness
Prove the index matches the source before anyone reads it.
- Swap reads and writes
Cut over to the new index.
- Decommission the old one
Only after the new one has proven itself.
Validation with order-independent checksums
To check an index is complete, compute a checksum per time window (say, per hour) over the source of truth and over the index, using a function that ignores row order. If a single entry from 2:30 PM is missing, the 2:00 to 3:00 PM checksum mismatches, and you know exactly which hour to investigate. It scales because it is embarrassingly parallel and needs no sorting.
Migrating a trillion entries
Uber’s payment platform started on DynamoDB in 2017 and, by 2021, was running three stores: DynamoDB for the latest twelve weeks, an internal blob store for older data, and the new ledger store receiving writes. The stated reasons to consolidate were recurring cost, simpler code with one system instead of three, lower indexing lag by running in their own data centres, and a store designed for payment-style data with verifiable immutability and tiered storage.
The scale reported publicly: around 1.2 PB compressed, over a trillion entries, and about 0.5 PB of uncompressed secondary index data. Two validation methods did the work.
What the backfill taught
| Lesson | Practice |
|---|---|
| Scale gradually | Start small and climb. Pushing past the limit becomes a self-inflicted denial of service |
| Backfill in small batches | A single big pass can multiply normal traffic tenfold. Make each batch finish in minutes |
| Control the rate dynamically | Raise the rate additively, cut it multiplicatively under load, the shape of TCP congestion control |
| Size files sensibly | Around 1 GB, between 100 MB and 10 GB, to avoid multipart limits and tiny-file overhead |
| Plan for bad data | Watch failure rates. Stop and fix on a spike, keep going and fix in parallel for rare cases |
| Rate-limit logging | Log routine progress every 30 seconds, log rare errors always |
The reported outcome: more than two trillion unique indexes moved with no inconsistency detected in over six months of production, and estimated savings above six million dollars a year from reduced DynamoDB spend.
Take it with you
Do
Match each index to the weakest consistency its consumer can tolerate. Write intents before records. Make reads repair pending state. Validate every backfill with windowed checksums before cutover.
Don't
Write the record first and “add the index after”. A crash in between creates money that exists and cannot be found.
Takeaway
An immutable ledger turns every new question into an index, and the discipline is in choosing how fresh each one must be. Strong indexes use intents that readers repair, eventual ones use materialised views, time-range ones serve batch work. When it comes time to move trillions of rows, you do not trust, you measure: shadow reads for live traffic, offline comparison for history, windowed checksums for completeness, and a rate that backs off the moment the system complains.
Frequently asked questions
Why does a financial ledger need so many indexes?
Ledger rows are immutable, so you cannot restructure them for each query. Different consumers ask different questions: by account, by trip, by time window, by status. Each pattern needs its own index over the same records, and at large scale that adds up to a very large number of index entries.
How can an index be strongly consistent without locking the table?
Write an index intent first, then the record, then commit the index asynchronously. A reader that finds a pending intent checks the main store: if the record exists it commits the entry, otherwise it rolls it back. The reader repairs state instead of the writer holding locks.
What is an order-independent checksum used for?
Validating that two copies of data match without sorting them. Compute a checksum over each time window, such as one hour, in a way that does not depend on row order, and compare source and index. A single missing or extra row changes that window's checksum.
How do you rate-limit a backfill safely?
Start small, raise the rate additively while the system is healthy, and cut it multiplicatively at the first sign of stress, the same shape as TCP congestion control. Also cap batch size so each step finishes in minutes, and rate-limit logging so errors do not overwhelm the logging system.

/* Comments */
Comments are offline right now — we reconnect automatically, nothing is lost.