---
topic: system-design
author: Crashtech Editorial
published: Nov 14, 2026 · read: 6 min
---

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.

– –

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

IndexPromiseExample consumerHow it is built
Strongly consistentRead your own write, immediatelyCard authorization hold at trip startTwo-phase style intent, record, commit
Eventually consistentUpdated shortly after the writePayment history screenMaterialised view refreshed in the background
Time-rangeEfficient bounded scans of a windowArchive to cold storage, seal for complianceSingle 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

  1. 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.

  2. Write the record

    Insert the actual ledger entry into the main store.

  3. 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.

Why intents beat doing it in the other order

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.
Advertisement

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:

  1. Create the new index table

    Empty and unused, so nothing can break.

  2. Backfill history

    Build entries from historical data in cold storage, rate-limited and batched.

  3. Validate completeness

    Prove the index matches the source before anyone reads it.

  4. Swap reads and writes

    Cut over to the new index.

  5. 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.

Shadow validation live traffic
Duplicate production reads to the new system and compare answers with the old one in real time. It proves the new system handles today’s traffic. To argue for six nines of confidence you need on the order of 100 million comparisons, which at 1,000 per second takes more than a day.
Offline validation the long tail
Rarely read historical data never shows up in shadow traffic. Compare full dumps instead, with Spark. The largest job compared about 760 billion records, roughly 70 TB compressed.

What the backfill taught

LessonPractice
Scale graduallyStart small and climb. Pushing past the limit becomes a self-inflicted denial of service
Backfill in small batchesA single big pass can multiply normal traffic tenfold. Make each batch finish in minutes
Control the rate dynamicallyRaise the rate additively, cut it multiplicatively under load, the shape of TCP congestion control
Size files sensiblyAround 1 GB, between 100 MB and 10 GB, to avoid multipart limits and tiny-file overhead
Plan for bad dataWatch failure rates. Stop and fix on a spike, keep going and fix in parallel for rare cases
Rate-limit loggingLog 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.

Advertisement

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.

Sources & further reading

/* Comments */