Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Index Table

A table the application maintains, keyed by the field you need to query and pointing back to the data, for stores that only look up by primary key or data sharded by another key: keeping it in step in one transaction or from a change feed with retries and reconciliation, what a reader sees while it lags, pointers versus copied columns, and a unique field.

Eight milliseconds by chip, forty seconds by phone

"My dog is missing. My number is 07700 900123. Is she registered?" The pet microchip registry taking that call holds 30 million records, one per implanted chip, in a key-value store keyed by the 15-digit chip number. A shelter that scans a stray and reads 985112003456789 gets the owner's name and phone in about 8 milliseconds: one lookup by key. The caller has only her phone, and nothing in the store is keyed by phone, so the only answer is a full scan: read all 30 million records and keep those whose phone matches, about 40 seconds per call on the registry's cluster, slowing other lookups while it runs.

A relational database would add an index on the phone column and let its planner use it, as Indexing & query optimisation explains. This store has no secondary indexes, so the application builds one: an Index Table, a second table keyed by the field you need to query, whose rows point back to the records. Here it is keyed by phone number, and each row holds a chip number.

Two lookups instead of a scan

The registry service reads the phone index for the chip numbers, then reads each chip's record by key. Both reads are lookups by key; neither scans.

The call takes milliseconds again, for at least one more round trip per lookup, a second write per change and a second table's storage.

One phone, three dogs

Phone numbers are not unique here: a family with three dogs gives one number for all three chips. A list of chip numbers in one index row looks natural, and loses data when two chips are registered to the same phone at once: both writers read the list, each appends and writes back, and unless the write is conditional the second overwrites the first. Give each pairing its own row instead. Stores such as Cassandra and DynamoDB group rows by a partition key and sort them within it by a second key, so the phone is the partition key and the chip number the sort key: all chips for a phone sit together under one partition key, and a new chip adds one row without touching the others.

The desk's screen also shows the pet's and the owner's names. Copying them into each index row saves a read per dog, and makes each copied column one more thing to keep in step: a renamed dog now changes its index row too.

The change that has to land twice

An owner changes her number from 07700 900123 to 07700 900456. Her record changes, the index row under the old number must go, and a row under the new one must appear. The first version did these as three separate writes in the request handler, and one afternoon a deploy restarted the process after the record had the new number and the old index row was gone, but before the new row was written. The record was right and the index was not: the dog could no longer be found by the only number its owner now gives, and nothing was logged. Two independent writes in one request can end with one done and the other not; retrying in the handler narrows that window, and a crash can still land in it.

There are two sound ways to keep the index in step. If the store has transactions that cover both tables, update the record and both index rows in one, so they commit or fail together; DynamoDB's TransactWriteItems is one such operation. If it does not, or a transaction cannot reach the index, update the index asynchronously from a change feed: the service writes only the record, and an indexer reads each committed change and applies it. Each change must carry the old number as well as the new, or the indexer cannot know which row to delete. The indexer retries until a change is applied, so applying one twice must be harmless: deleting a row already gone, writing a row that already exists. Changes to one record must also be applied in the order they were made, retries included, or an old change can undo a newer one. Reading committed changes from the database's own log, where each record's changes appear in the order they were made, is what Change data capture does; where no such log is available, the service can write the change to an outbox table in the same local transaction as the record, for a relay to deliver (Transactional Outbox).

Retries cover the failures the indexer sees, not a change that never reached the feed, an indexer bug, or a record fixed by hand. So the registry also runs reconciliation, a nightly job that checks each record against its index rows and each index row against its record, and repairs any difference. When it has drifted badly, after a week-long indexer bug say, it is simpler to rebuild it: fill a new index table from a full read of the records, apply every change made since that read began, each record's in order, and switch lookups to it once it has caught up.

What the desk sees while the indexer catches up

Updated asynchronously, the index is eventually consistent: it catches up with the records, not at the moment a record changes, and the gap grows to minutes or more while the indexer is behind or down. In that window a search by the new number finds nothing yet, and a search by the old number still finds the dog, pointing at a record that no longer has that number.

The stale hit is cheap to handle on the read path: after following a pointer, check that the record still has the searched number, and drop it if not, provided that read of the record is itself up to date. The missing hit the reader cannot detect, since there is nothing to follow. The registry accepts it: an owner who changes her number is told searches may take a few minutes to find it, and a search by chip number reads the record itself, not the index. When that trade is acceptable is the ground of Consistency models: strong vs eventual (CAP).

Sharded by chip, searched by phone

Once the records are split across 16 shards by chip number, a phone index kept on each shard (a local index) means every search asks all 16 and merges the answers, as in Scatter-Gather. A global index, partitioned by phone number itself, sends the search to the one partition that holds that number, and each chip it returns is then read from that chip's shard; every lookup is routed like any other key (Shard routing and the shard map). The cost moves to writes: a record and its index row now usually sit on different shards, beyond one shard's transaction, so the change feed becomes the normal path and the index is eventually consistent, which is also how DynamoDB's global secondary indexes behave. Making both writes atomic would take a cross-shard protocol such as Two-phase commit, with its extra round trips and blocking.

Which kind of index this is

The same table can enforce a unique field: an index keyed by login email, claimed at signup with a conditional insert-if-absent, so the store refuses a second account with that address, although a crash between the claim and the account creation leaves a claim to retry or clean up. Whatever the index is for, the decision it forces is the same: which writes may run ahead of the index, and what a reader does in the gap. An Index Table leads back to the records, copied columns or not; a read model built in a different shape, such as counts per county, is a Materialized View. Its Challenge is the closest practice, since no Challenge yet asks outright for a lookup by a second field: its palette has the Index Table node, and its brief asks to "Model the projector that updates the view from source changes" and to "Note the view is disposable and rebuildable from the source". Feed a phone-keyed Index Table from that same Projector, and decide what each change must carry for the index to delete the old row.

Practice this