Papers
Life beyond Distributed Transactions: an Apostate's Opinion
Pat Helland · CIDR 2007, 2007
The problem: applications at enormous scale do not use distributed transactions
Helland opens the position paper with a confession: he spent much of his career advocating platforms that offer global serializability, that is, protocols such as two-phase commit (2PC), Paxos and quorum approaches that give the programmer the illusion of atomically updating data spread across several machines. From his experience in the previous decade, however, developers simply do not build highly scalable applications assuming distributed transactions; when they try, the projects founder because the performance cost and the fragility make the approach impractical. He compares these platforms to the Maginot Line. The paper does not try to solve high availability: the stated focus is only scalability and the consequences of not being able to count on distributed transactions at large scale. To think about this, the author proposes a thought experiment called 'almost infinite scaling', in which the number of customers, orders, accounts and other business things grows without bound, while each individual item does not get much bigger; the load ends up spread across an enormous number of machines, so many that they cannot be treated as a single machine. The paper's goal is to name and formalize abstractions that were already being used implicitly, and to discuss messaging patterns between pieces of data that can be repartitioned over time.
Entities: the transaction boundary is a single key
The central idea is an abstraction called an entity. An entity is a collection of data with a unique key, which lives within a single serializability scope (one machine or a small cluster). Because of this, atomic transactions are always possible within an entity, but not across entities. Each piece of data belongs to exactly one entity, and the data of one entity never overlaps with that of another; the paper's example is an order system in which each order, identified by an Order-ID, must be disjoint from the others. The internal representation is free (SQL records, XML, files, blobs). The paper assumes two layers: the business code on top is 'scale-agnostic' and only knows the entity key, while the layer below knows where each entity is and can move it when it repartitions. Since the lower layer may place two entities on different machines, the upper code can never count on atomicity across distinct keys. With key-range partitioning, adjacent keys usually end up on the same machine, so a test that depends on atomicity with a neighbor probably finds it in the test environment; only when a redeploy moves the entities to different scopes does the latent bug appear. Another consequence: alternate indexes cannot be kept transactionally consistent with the entity, since the index copy lives in another scope; the application must accept that the index may be stale and use a two-step lookup (alternate key, then entity key).
Messages between entities: at-least-once delivery and idempotency
If two entities cannot be updated in the same transaction, the link between them is a message. The paper asks that sending be asynchronous with respect to the transaction that originated it: the message only becomes visible at the destination after the sending transaction commits, and enqueuing is transactional, so that no message exists that was sent by a transaction that aborted. The message is addressed to the entity's key; finding the location is the job of the layer below, which delivers the message at least once. According to the author, most applications use at-least-once delivery, because message delivery is not coupled to the durable data update: the data is updated, the machine fails before the acknowledgement, and the message is processed again. The alternative would be losing messages (at-most-once), which he considers even harder. When entities move during repartitioning, messages may be repeated and arrive out of order. The consequence is that the application must process everything idempotently, that is, a repeat cannot cause a substantive change to the entity (what counts as "substantive" is defined by the application). Messages that only read, or that change the entity without a substantive change, are naturally idempotent; those that cause a substantive change require the entity to remember, as state, that it has already processed the message and, if there is a response, return the same one.
Activities: the state an entity keeps about each partner
To organize this state, the paper introduces the concept of an activity: the local information that an entity keeps about its relationship with each partner entity, including knowledge of the messages already received. Each activity lives in exactly one entity, and an entity will have one activity for each partner from which it receives messages. The author argues that focusing on per-partner state makes it easier to build scalable applications; one use is to implement idempotent processing, durably remembering the transition from 'the message can still be processed' to 'the message will no longer have any substantive effect', using some unique characteristic of the message. The paper's example is an order with several items: there is one entity for the order and one entity for each item managed by the warehouse, there are no transactions between them, and the per-item data inside the order entity are activities. At almost-infinite scale one cannot simply run a query to discover what is related; everything must be connected by a web of two-party relationships, stitched together with entity keys. The author also notes that it is hard, though possible, to deduplicate messages between fine-grained entities in the infrastructure, because the deduplication knowledge would have to migrate along with the entity; for this reason the common pattern is for application logic to guarantee idempotence.
Tentative operations, uncertainty and the author's prediction
Without atomic transactions across entities, reaching an agreement means accepting uncertainty for a while. In distributed transactions it shows up as locks managed by the transaction manager; here it moves into the business semantics, and the author sums this up as 'just workflow', only fine-grained, with entities as participants. The mechanism is the tentative operation: one entity asks another, by message, to take on a commitment that leaves open the possibility of cancellation. Whoever accepts agrees to let the other decide the outcome. Essential is the right to cancel: if the requester gives up, a cancel occurs; if it releases that right, a confirm occurs, and every tentative operation eventually confirms or cancels. The paper's example is the warehouse that allocates inventory to an order without knowing whether it will be used and later finds out whether it is needed, with one activity per order inside each item to track this uncertainty. Another analogy is escrow in a home purchase, a star-shaped structure of agreements between two parties. The author also points out that the uncertainty becomes business concepts such as reserved stock or allocation against a line of credit. In the conclusions, he predicts that, in a few years, these patterns would lead to new middleware or platforms that automate the management of such applications, in parallel with the emergence of TP monitors in the 1970s.
See the ideas at work
Practice the designs that use this paper in the System Design school.