Consistency and Repair at Depth

Versioning under a partition

A store keeps several replicas of each value so it stays up when one machine fails. A network partition can cut the replicas into groups that cannot talk.

During the partition, both groups keep accepting writes. The same value now has two different versions, and neither group knows about the other.

Wall clocks cannot settle which version is newer. Machine clocks drift apart, and two writes can carry the same timestamp.

Last-write-wins settles it by timestamp alone. It silently throws one write away, even when that write was never seen by the winner.

How a vector clock works

A version is one stored state of a value, produced by one write. The vector clock is the version's memory of where it came from.

Every replica owns one counter in the clock. When a replica writes a value, it raises its own counter by one and stamps the new version with the full clock.

Replica A writes a value for the first time. A's counter becomes 1, and the version carries a clock showing A at 1 and every other replica at 0.

When a replica receives a version from elsewhere, it merges the clocks. For each counter, it keeps the higher number, because the higher number has seen more writes.

The clock travels with the value on every read and write. No central machine assigns it, so partitioned groups can keep stamping versions on their own.

Comparing two clocks

One clock is older than another when every counter is equal or lower, and at least one counter is lower. The newer version has seen everything the older one saw, and more.

Two clocks are concurrent when each is higher in at least one counter. Each version saw a write the other never saw.

Concurrent versions are called siblings. The store keeps both, because picking one would delete a write nobody has seen.

A later read returns the siblings together. The application merges them, or a person chooses, and the merged result is written back with a clock that covers both.

That is the heart of the idea. A vector clock does not order every write. It proves when one write came after another, and it admits honestly when it cannot prove that.

Every counter is equal or lower, and one is lower. The first version is older.

Every counter is equal or higher, and one is higher. The first version is newer.

Each clock is higher somewhere. The versions are concurrent.

Every counter is equal. The versions are the same.

Causal consistency

Causal consistency is a consistency promise built on this idea of one write depending on another. If a write depends on an earlier write, every replica shows them in that order.

A reply depends on the message it answers. Causal consistency guarantees no replica shows the reply before the message.

Writes that do not depend on each other may appear in different orders on different replicas. The promise only covers cause and effect.

Vector clocks are the machinery that makes the promise checkable. A replica can compare clocks and know whether a version it is about to show is missing a cause.

The cost of the clock

The clock grows with the number of replicas, not with the size of the value. A value stored on many replicas carries a long clock on every version.

Take a store with 100 replicas and 8 bytes per counter, as a stated demo choice.

100 replicas × 8 bytes = 800 bytes of clock on every version.

At 1,000,000 writes a day, that is 1,000,000 × 800 bytes = 800,000,000 bytes of clock data a day, about 800 MB.

Old counters can be pruned when a replica leaves for good. Pruning is risky, because a pruned replica that returns can produce versions the others can no longer compare.

Vector clock trade-offs

Against last-write-wins, the trade is clear. Last-write-wins is tiny and fast, and it loses concurrent writes without a sound.

Against a single leader, the trade is availability. A leader gives every write one order, but a partition can leave a group with no leader to write to.

Vector clocks fit stores that must accept writes in several places at once. Shopping carts and sync tools are the classic shape, because merging siblings there is natural.

The price is real. Versions multiply, applications must merge siblings, and every version carries the clock as overhead.

Drift between replicas

Anti-entropy is a background repair process in which replicas compare what they hold and copy whatever the other is missing. It works through a Merkle tree, a tree of checksums over ranges of keys, so two replicas can find a difference without sending all their data.

Replicas drift apart in ordinary operation. A write misses a replica that was restarting, and a copy promised for later delivery never arrives.

Repairs that happen during reads only fix values that somebody reads. A cold value, one nobody asks for, can stay wrong on one replica for months.

The store needs a repair that runs whether or not anyone reads. It also needs that repair to be cheap, because comparing two full datasets is far too much data to move.

Checksums and the Merkle tree

A checksum is a short number computed from a block of data. Change any part of the data, and the number changes with it.

A Merkle tree organises checksums over a replica's keys. The keys are split into ranges, and each leaf of the tree holds the checksum of one range's data.

Each parent in the tree holds a checksum computed from its children's checksums. The root, at the top, is one number that summarises the entire dataset.

Two replicas with the same data build the same tree. Two replicas that differ anywhere build different roots.

Comparing two trees

The comparison starts at the root. Equal roots end the conversation, because everything below them already agrees.

Different roots send the comparison one level down. The replicas compare the children, keep the branches that match, and descend only into the branches that differ.

At the leaves, the replicas know exactly which key ranges disagree. They copy the missing or newer versions for those ranges only, in both directions.

Take a demo tree with 16 children per node and 5 levels. It has 16 × 16 × 16 × 16 × 16 = 1,048,576 leaves, about a million key ranges.

Finding one differing range costs 16 comparisons per level × 5 levels = 80 checksum comparisons.

Sending the data itself instead would move 1,000,000 records × 1 KB = 1,000,000,000 bytes, about 1 GB, to learn the same thing.

Root checksums match. The replicas agree.

Root checksums differ. The replicas compare the children.

One child differs. The comparison descends into that child only.

Leaf ranges differ. The missing versions are copied.

The repair run

Anti-entropy runs on a schedule in the background. Pairs of replicas are chosen in turn, often using the gossip protocol to spread the pairing fairly.

Each pair exchanges trees, finds its differing ranges, and streams the missing versions across. Both replicas end the run holding the union of what either one had.

The run is throttled on purpose. It takes spare bandwidth and spare disk time, and it yields whenever real reads and writes need the machine.

Deleted values take part like any other data. A delete leaves a marker behind, and the marker is compared and copied too, or a deleted value would quietly return from a replica that missed the delete.

Where anti-entropy breaks

The tree is a snapshot. Data that changes while two replicas compare can make a range look different when it is only newer, so runs compare versions, not just presence.

Rebuilding a tree over fast-changing data is itself work. Stores update the tree as writes land, and rebuild it rarely, to keep the cost steady.

Repair is eventual, never instant. Between runs, replicas can disagree, and a read in that window can still meet a stale copy.

A checksum collision, two different blocks with the same number, is possible in theory. Wide checksums make it so unlikely that stores treat equal checksums as equal data.

Anti-entropy trade-offs

Anti-entropy is the repair of last resort. It covers the cold data and the lost hints that no read will ever trigger a fix for.

Its cost is a steady background tax. Trees must be built, comparisons must run, and differing ranges must stream, forever, even when nothing is wrong.

The tuning knob is frequency. Frequent runs close the disagreement window quickly and tax the cluster more. Rare runs are cheap and let drift live longer.

Replicas will drift, so the store schedules the comparison that finds the drift, and the Merkle tree makes that comparison cheap enough to run forever.

Gaps at write and read time

Hinted handoff is a repair technique where a replica that takes a write meant for a down replica stores it for a while, with a note naming the intended owner, and hands it over when that replica returns. Read repair is its partner. A read that finds disagreeing copies updates the stale copies on the spot.

Consistent hashing assigns each value to a small set of replicas. In the quorum design, a value has N = 3 copies, a write counts at W = 2 copies, and a read asks R = 2 copies.

Machines go down at awkward moments. A write can arrive while one of its three replicas is restarting, and a read can meet a copy that missed the last few writes.

Refusing every write that cannot reach its full set would tank availability. Accepting writes and reads anyway leaves gaps, and the gaps need cheap repairs.

Hinted handoff

The replica that takes a request and organises the others is called the coordinator here. It sends the write to the value's replicas as usual.

When one target replica is down, the coordinator asks a healthy replica outside the set to hold the write instead. That stand-in stores the write with a hint, a note naming the replica the write truly belongs to.

The held write still counts toward the write quorum. The write succeeds now, and its durability rests on a promise to deliver later.

When the down replica returns, the stand-in hands the write over and deletes its hinted copy. The set is whole again, and nobody outside the repair ever noticed the gap.

The cost of holding hints

Hints pile up while a replica is down. The pile is easy to estimate with stated demo figures.

A replica is down for 1 hour, and writes aimed at it arrive at 1,000 per second.

1,000 writes per second × 3,600 seconds = 3,600,000 writes waiting as hints.

At 1 KB per write, the stand-ins hold 3,600,000 × 1 KB = 3,600,000,000 bytes, about 3.6 GB of hints.

Hints are held for a limited time, and the stand-in can fail too. A hint is a favour, not a guarantee, so a long outage can still lose the writes nobody else copied.

Read repair

A read asks R = 2 copies of the value. The coordinator compares the versions that come back, using their vector clocks or timestamps.

When the copies disagree, the reader returns the newest version to the client. It then writes that version back to the stale copies, quietly fixing them for the next reader.

The repair load follows the disagreement rate. At 1,000,000 reads a day with 1 read in 100 finding a stale copy, that is 1,000,000 ÷ 100 = 10,000 repairs a day.

Read repair only touches values that get read. Hot values heal almost at once, and cold values never heal this way at all.

Where the pair breaks

Both repairs are best-effort by design. A hint can expire before its owner returns, and a stale copy can sit unread for months.

Read repair adds write work to the read path. On a very hot value with constant disagreement, the repairs themselves become load worth watching.

Neither repair proves anything about the whole dataset. They close the gaps they happen to meet, and stay silent about the rest.

That silence is why anti-entropy exists behind them. The two cheap repairs cover the common gaps, and the background comparison covers everything else, slowly.

Layered repair and trade-offs

The strict alternative is to refuse a write until its real replicas are back. That keeps every promise and fails requests that hinted handoff would have accepted.

This is the PACELC trade in daily clothes. When a replica is down, the store chooses availability now and repairs the certainty later.

The pattern to remember is layered repair. Fix at write time what can be held, fix at read time what can be compared, and sweep the rest in the background.

Hinted handoff covers a replica that is down at write time.

Read repair covers a copy that is stale at read time.

Anti-entropy covers copies that drift and are never read.

A job across services

A saga is a way to finish a job that spans several services. It runs the job as a chain of small local steps, each one committed on its own service, with an undo step ready if a later step fails. A distributed transaction is the stricter alternative. All the services change together, or none of them change.

One database can make several changes together or not at all. That promise ends at the database boundary.

A booking job spans services. One service reserves the seat, one takes the payment, one books the room, and one sends the confirmation.

Each service owns its own data. If the room booking fails after the payment lands, the customer has paid for a trip that does not exist.

The job needs an all-or-nothing feel across services that share no database. Two designs answer that need, and they trade very differently.

The distributed transaction

A distributed transaction stretches the database promise across services. One coordinator runs the agreement.

First the coordinator asks every service to prepare. Each service does its part of the work, holds it uncommitted, locks the data it touched, and answers ready or not ready.

If every service answers ready, the coordinator tells them all to commit. If any service cannot prepare, the coordinator tells them all to abandon the work.

The weakness is the waiting. Prepared services hold locks and cannot finish until the coordinator decides, so a coordinator that fails mid-agreement leaves services frozen with it.

Long agreements across distant services stretch that wait further. The design buys certainty with other people's availability.

The saga

A saga gives up the single agreement. It splits the job into a chain of small steps, and each step is an ordinary local transaction on its own service.

Each step commits as soon as it finishes. The seat is really reserved, the payment is really taken, and the world can see each result at once.

One service can lead the chain, sending each step in turn and recording progress as it goes. Or each finished step can announce itself, and the next service reacts to the announcement.

The saga's record of which steps have finished must be durable. It is kept in a write-ahead log or a database, so a crashed leader can resume the chain instead of guessing.

When a step fails, the saga stops moving forward. It starts moving backward instead, undoing the steps that already committed.

Compensating actions

A compensating action is an action that undoes the effect of a finished step, in the terms of the job itself. It releases the seat, refunds the payment, or cancels the room.

It is not a rollback of stored bytes. The payment really happened, and the refund is a new, real event that balances it.

Compensations run in reverse order, last finished step first. Each one is retried until it lands, using idempotency so a retry never refunds twice.

Some steps cannot be undone. A sent confirmation message cannot be unsent, so well-built sagas put the un-undoable step last, after every step that might fail.

The arithmetic explains why this machinery matters. Take a stated demo where 1 step in 1,000 fails, and a saga has 10 steps.

1,000,000 sagas × 10 steps = 10,000,000 steps, and at 1 failure per 1,000 steps that is 10,000,000 ÷ 1,000 = 10,000 failed steps.

So roughly 10,000 sagas in every million need their compensating actions. Compensation is not an edge case. It is a normal path, and it is designed like one.

Where sagas break

A saga has no hiding place mid-flight. Other readers see the half-finished job, a paid booking with no room, until the chain completes or compensates.

Applications must tolerate those states. A screen that shows the booking should show it as pending, not as broken or as final.

Compensating actions can fail too. A refund service that is down leaves the saga paused mid-undo, and operators need a way to see and prod stuck sagas.

Two sagas can also trip over each other. With no locks held between steps, two chains touching the same seat must settle the clash by their own rules.

Saga trade-offs

The distributed transaction gives a clean promise and takes availability as payment. It suits short agreements among services that are close and controlled together.

The saga gives availability and scale, and takes on visible half-finished states and hand-written undo steps as payment. It suits long jobs across services owned by different teams.

The main idea is the exchange itself. Across services, all-or-nothing stops being free. A design either blocks everyone until all agree, or commits step by step and learns to undo.

Keeping other stores current

Change data capture is a technique that reads a database's own record of its changes and streams each change onward to other systems as it happens. Search indexes, caches and analytics stores stay current with the database, without the application writing to each of them separately.

One database is rarely the only store that must know a fact. A product change must reach the search index, the cache and the analytics store.

The direct answer is the dual write. The application writes the database, then writes each other store in turn.

A crash between those writes splits the truth. The database has the change, the index never hears of it, and no error is recorded anywhere.

Polling is the other direct answer. Each store keeps asking the database what changed, which wastes queries and still learns late.

Dual write. The app writes twice, and a crash splits the writes.

Polling. A store asks the database again and again, with lag and wasted queries.

Change data capture. The change log is read, and the method needs access to the log.

Reading the log

A database already keeps a write-ahead log. Every change is written there first, in the order it happened, so the database can recover after a crash.

Change data capture reads that log as a stream. Each entry becomes one change event for the systems downstream.

A change event names the table, the key of the row, and the value before and after the change. Deletes travel as events too, marked as deletes.

Order is the prize. Changes to the same row arrive downstream in the order they were made, because the log itself is ordered.

The application writes once, to its database, and stays out of the distribution business entirely.

Estimate the stream

A busy table sees 10,000,000 updates a day, as a stated demo figure.

10,000,000 updates ÷ 86,400 seconds = 116 change events per second on average.

At 500 bytes per event, the stream carries 10,000,000 × 500 bytes = 5,000,000,000 bytes a day, about 5 GB.

Keeping 7 days of the stream for replay takes 5 GB × 7 = 35 GB of log storage.

The stream is modest next to the database itself. The cost of capture is mostly the consumers keeping up, not the reading of the log.

Consumers and replay

Each consumer reads the stream at its own pace. A search indexer applies product changes, a cache consumer deletes stale entries, and an analytics loader appends rows.

Every consumer remembers its position in the log. After a crash, it restarts from that position and replays what it missed.

Replay means some events arrive twice. Consumers are built idempotent, or they dedupe events they have already applied, so a second delivery changes nothing.

A new consumer can start from the very beginning of the retained log. That is how a fresh search index is built without stopping the application.

Where change data capture breaks

The shape of the stored data changes over time. When a table gains a field, old events lack it and new events carry it, and every consumer must cope with both shapes.

Retention is a hard window. A consumer that stays down longer than the log is kept loses its place, and it must rebuild from a fresh snapshot instead of replaying.

Downstream systems are eventually current, not instantly current. Under load the stream lags, and a search can miss a change made a moment ago.

The log is the database's own machinery. Tying consumers to its format couples them to the database, and swapping databases means rebuilding the capture layer.

Change data capture trade-offs

Against the dual write, capture wins on truth. There is exactly one write, so there is nothing to split.

Against polling, capture wins on freshness and load. Changes flow as they happen, and no store burns queries asking whether anything changed.

The main idea is reuse. The database already writes the perfect record of its changes for its own recovery. Change data capture simply lets everyone else read it.

The shape of time-series data

Time-series data is data made of measurements stamped with the time they were taken, like a server's memory use sampled every few seconds. It arrives in time order, it is read by time range, and it grows too fast to keep at full detail forever.

Monitoring produces a particular shape of data. Machines report measurements, the measurements are never edited afterwards, and nobody ever asks for one measurement by its own key.

Reads ask about ranges. What did memory do in the last hour, and how does this week compare with last week.

A general database spends much of its machinery on updates, transactions and single-row lookups. Time-series data uses almost none of it, and arrives at a rate that punishes waste.

Estimate the volume

A fleet has 10,000 servers, and each server reports 100 metrics, as stated demo figures.

One metric from one server is one series. The fleet therefore has 10,000 × 100 = 1,000,000 series.

Each series is sampled every 10 seconds. The fleet produces 1,000,000 series ÷ 10 seconds = 100,000 samples per second.

Over a day that is 100,000 samples per second × 86,400 seconds = 8,640,000,000 samples.

At 16 bytes per stored sample, one day of raw data is 8,640,000,000 × 16 bytes = 138,240,000,000 bytes, about 138 GB.

Keeping a year at that rate is out of the question. The design must spend detail to buy time, which is where downsampling comes in.

Storing by time

Writes are appends. Samples land in time order and are never changed, so storage is organised as time ranges, one after another.

Partitioning by time range is the natural shard key here. A query for the last hour touches only the newest ranges, and old ranges sit untouched on cheaper storage.

Whole ranges expire together. Dropping a month of old data is deleting its ranges, not hunting through live data for old rows.

Recent ranges stay on fast disks for dashboards. Older ranges move to slower, cheaper storage, because they are read rarely and in bulk.

Downsampling

Downsampling is the practice of keeping older data at lower resolution. Many samples are combined into one summary value, such as the average, the highest and the lowest for each minute.

Combining 10-second samples into one value per minute shrinks the data sixfold. The day's 8,640,000,000 samples become 8,640,000,000 ÷ 6 = 1,440,000,000 summary values.

Stored at 16 bytes each, the summarised day takes 1,440,000,000 × 16 bytes = 23,040,000,000 bytes, about 23 GB instead of about 138 GB.

The tiers run on a schedule. Raw samples are kept for days, minute summaries for months, and hour summaries for years.

Each tier answers the questions its age actually gets. Nobody debugging a live incident needs last year's data at 10-second detail.

Up to 2 days old. Every 10 seconds is kept, for live dashboards.

Up to 1 month old. One value per minute is kept, for recent investigations.

Beyond 1 month old. One value per hour is kept, for capacity planning.

Where time-series data breaks

Summaries hide spikes. A five-second burst vanishes inside a one-minute average, so the summaries keep the highest value as well as the average.

Machine clocks disagree. A sample stamped by a slow clock lands in the wrong minute, and late samples arrive after their range was already summarised.

Labels can explode the series count. A label is a tag on a series, and a label with millions of values, like a user id, creates millions of series and sinks the store.

The guard is discipline about labels. Series stay countable when labels come from small sets, like server names and regions.

Time-series trade-offs

Every retention choice trades three things. Resolution, retention and storage cost pull against each other, and the tiers are how a design buys all three partly.

Against a general database, the specialised store gives up flexible queries. In return it swallows a write rate and a data volume the general store cannot hold.

The main idea is that time is the index. Time-series data is written by time, read by time and deleted by time, and downsampling lets it age gracefully instead of growing forever.

Distributed transaction vs saga