Skip to main content

Data Integration and the Limits of Total Order

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 12 — rewritten and condensed for teaching.

Every earlier lesson in this series described things largely as they are. This one opens the book's final chapter, where Kleppmann shifts to opinion and speculation about how applications should be designed — starting from a problem every real organization eventually hits: no single piece of software does everything.

Combining Specialized Tools by Deriving Data​

For a problem as simple-sounding as "store some data and look it up again later," earlier lessons already showed several genuinely different, all-valid approaches — log-structured storage, B-trees, column-oriented storage; single-leader, multi-leader, or leaderless replication. There is no single right answer, only approaches that fit different circumstances — and a real piece of software has to pick one. Trying to be good at every access pattern at once, in one codebase, is a near-guarantee of being good at none of them.

That specialization creates a second-order problem: real applications rarely need just one access pattern. A typical example — an OLTP database needs to be paired with a dedicated full-text search index to handle arbitrary keyword queries well, because search indexes make poor systems of record and general-purpose databases rarely index text as well as a dedicated tool. Scale that up across a real organization and you're routinely combining a system of record with a search index, a cache, a data warehouse, a recommendation engine, and more — one dataset, many representations, no single tool spanning all of them.

Reasoning About Dataflows​

Once several storage systems hold copies of the same underlying data, the question that matters most is: where does data get written first, and which representations are purely derived from that source?

The dangerous version of this setup lets an application write directly to both the database and the search index. Two clients can then send conflicting writes that arrive at the two systems in a different order — neither system is "in charge" of ordering, so they can each make a different, individually reasonable decision and end up permanently, silently inconsistent with each other.

The fix is the same idea driving Change Data Capture and event sourcing: funnel all writes through one system that decides the order once, and derive everything else from that single, ordered stream. This is really an application of state machine replication — whether the mechanism is CDC or an event log matters far less than the underlying principle of a single agreed-upon order. Done this way, updating derived data becomes deterministic and idempotent, which is exactly what makes it straightforward to recover from faults.

Derived Data versus Distributed Transactions​

Distributed transactions are the classic alternative for keeping multiple data systems consistent. Both approaches solve the same problem — deciding on one order for writes — through genuinely different mechanisms:

Distributed transactionsLog-based derived data
Achieves ordering viaLocks (mutual exclusion)An append-only log
Guarantees "exactly once" viaAtomic commitDeterministic retry + idempotence
Timing guaranteeLinearizability (e.g., read-your-writes)Usually asynchronous — no such default guarantee

Kleppmann's own opinion here is blunt: XA-style distributed transactions have poor fault-tolerance and performance characteristics that limit their real-world usefulness, and no better, widely-adopted protocol seems imminent. In the absence of one, he considers log-based derived data the more promising path for integrating heterogeneous systems — while still taking seriously that guarantees like read-your-own-writes are genuinely useful, not a comfort to be waved away with "eventual consistency — deal with it."

Check: combining tools and reasoning about dataflow​

Quiz

Deriving data, funneling writes, and derived data vs. distributed transactions

1 / 3

Why do complex applications typically end up combining several different data storage/processing tools rather than using just one?

Pick an answer to see if you are right.

The Limits of Total Ordering​

A single, totally ordered event log works cleanly for small-enough systems — it's exactly what single-leader replication already builds. But it stops scaling cleanly for several concrete reasons:

  • Throughput. A total order generally requires funneling every event through one leader node. Once event throughput exceeds what one machine can handle, the log has to be partitioned — and the relative order of events in different partitions becomes ambiguous.
  • Geographic distribution. Multiple datacenters, kept for fault tolerance, typically mean a separate leader per datacenter (see Multi-Leader Replication), since synchronous cross-datacenter coordination is too slow to be practical — so events originating in different datacenters have no defined relative order either.
  • Microservices. A common design keeps each service's durable state fully independent, with nothing shared — so events originating in two different services have no defined order between them.
  • Offline-capable clients. Client-side state that updates immediately on user input (without waiting on the server) means clients and servers are likely to observe events in different orders altogether.

Formally, deciding a total order over events is total order broadcast, which is equivalent to consensus (see Fault-Tolerant Consensus). Most consensus algorithms assume a single node's throughput is sufficient for the whole event stream — designing a consensus algorithm that scales past a single node's throughput, and that works well geographically distributed, remains, in Kleppmann's words, an open research problem.

Ordering Events to Capture Causality​

When events have no causal link, the lack of a total order genuinely doesn't matter — concurrent events can be ordered arbitrarily. Some causal cases are also easy: updates to the same object can be totally ordered just by routing them all to the same log partition. The harder case is when a causal dependency crosses that boundary.

The classic example: two users end a relationship. One removes the other as a friend, then posts a message complaining about their ex to their remaining friends — intending the ex not to see it, since the friend removal happened first. But if friendship status and messages live in different systems, that ordering dependency can be lost entirely. A notification service that processes the message-send event before the unfriend event will incorrectly notify the ex — because notifications are effectively a join between messages and the current friend list, and joins are exactly where time-dependence causes trouble.

There's no fully general fix, but there are starting points:

  • Logical timestamps (see Ordering Guarantees) give total ordering without coordination — but recipients still have to handle events arriving out of order, and extra metadata has to travel with every event.
  • Referencing the causally-prior event. If you log an event capturing "the state the user saw right before deciding," with a unique ID, later events can explicitly reference that ID to record the causal dependency directly — turning an implicit ordering assumption into an explicit, checkable link.
  • Conflict resolution algorithms (see Leaderless Replication) help when events arrive out of order and only state needs reconciling — but they don't help once an action has already had an external side effect, like a notification that already went out.

Practice: capturing a causal dependency explicitly​

Implement the "reference the causally-prior event" fix directly: a message references the highest-numbered friend-removal event its sender had already seen, so a downstream consumer can correctly exclude a removed friend even if it processes events out of their true order.

Check: the limits of total order and capturing causality​

Quiz

Why total ordering breaks down, and how to recover causality

1 / 3

Why does partitioning an event log for higher throughput undermine having a single total order over all events?

Pick an answer to see if you are right.

Key takeaways
  • No single storage or processing tool fits every access pattern, so real applications inevitably combine several specialized systems — making it essential to be explicit about where data is written first and which representations are purely derived.
  • Funneling all writes through one system that decides a single order (via CDC or event sourcing) avoids the silent, permanent inconsistency that direct, uncoordinated writes to multiple systems can produce.
  • Distributed transactions and log-based derived data solve the same ordering problem through different mechanisms — locks and atomic commit vs. an append-only log and idempotent retries — with log-based approaches trading away default linearizability guarantees like read-your-writes.
  • A single total order stops scaling cleanly once throughput demands partitioning, multiple datacenters need independent leaders, services keep fully independent state, or clients operate offline — and total order broadcast's equivalence to consensus means this is a fundamentally hard, still-open scaling problem.
  • Causal dependencies that cross storage-system boundaries can silently vanish; explicitly referencing the causally-prior event's ID is one concrete way to preserve that dependency even when downstream processing sees events out of order.

Further Reading​