JavaScript: From Closures to Autonomous Systems

Chapter 17. The Limits of Consistency

Part IV. Distributed Reactivity9 min

17

The Limits of Consistency

As long as data has one main copy, all disputes are settled simply. In the fifteenth chapter the client guessed what the server would do, and if it guessed wrong, the server corrected it. In the sixteenth the server decided what the client was allowed to see. In both cases the server had the last word. But the server is sometimes unreachable: a phone lost its network, a warehouse in another city was cut off from headquarters for an hour, two data centres stopped seeing each other. The copies keep working meanwhile, and when the connection returns they hold different data. Which of them is right has to be decided anew.

In 2000 Eric Brewer gave a talk formulating a claim that later came to be called the CAP theorem. Two years later Seth Gilbert and Nancy Lynch proved it rigorously. If the network splits into parts that cannot reach each other, the system must choose one of two things: either keep answering requests at the risk of returning stale data, or refuse to answer until the connection is restored. You cannot have both. For a long time the theorem was retold as the formula «pick two of three», and in 2012 Brewer himself wrote an article saying that this formula is misleading. The network splits rarely, and the rest of the time there is no need to choose.

In the same issue of the journal, Daniel Abadi clarified that you do have to choose all the time. Even when the network is intact, to answer with a guarantee that the data is fresh, the copies must agree among themselves, and that takes time. If they do not agree, the answer will be fast but possibly stale. Abadi called this PACELC: under a partition you choose between availability and consistency, else between latency and consistency. The latency compensation of the fifteenth chapter is such a choice in its purest form. Meteor showed the user a result before the server confirmed it, that is, it chose speed, and restored consistency later, during reconciliation.


If a system chooses availability, it must be able to merge copies that have diverged. In 2007 Amazon described its internal store, Dynamo, and the main example in the paper was the shopping cart. Adding an item to the cart must always work, even if some servers are unavailable, because every refusal is a lost sale. When copies of a cart diverge, Dynamo hands both versions to the application, and the application merges them by union: everything that was in at least one copy goes into the result. An added item is never lost. But a deleted item can come back: if the customer removed it while one of the copies was cut off, the union will pull it back from the copy that did not know about the deletion. Amazon chose this behaviour deliberately, because the customer will notice an extra item in the cart and remove it, while a missing one could cost a sale.

Free, one step away

The rest of the book is free

Leave your email and I will send a link to confirm it. Once you click it, every chapter opens here, on this device, for a year. When a new book comes out I will write to this address; reply “stop” to any email and I will not write again.

Have an INITE account? Sign in and the book opens without an email.

I do not charge for the book. If you would like to support it, you can donate from any chapter.

How your email is stored