Eventual Consistency can be a Good Thing

• Atomic semantics literally imply an all-or-nothing, one-shot operation. When a statement is executed, every update within the transaction must succeed in order to be called successful. There is no partial failure 🐙
• Consistent suggests that data transitions from one proper state to another proper state, i.e. no chance that readers could view different values that do not make sense together 🐌
• Isolated semantics imply that transactions which execute concurrently won’t become enmeshed with one other. Each transaction executes in its own quarantined space 🐚
• Durable guarantees suggest that when a transaction has succeeded, the state changes will persist, and won’t be lost 🐢

Enter eventual consistency, so despair not 🐔

They built a system that implemented “checkpointing,” a way for the index to hold its place if a calamity befell a server or hard disk. But the new system went further—it used a different way to handle a cluster of disks, more akin to the parallel-processing style of computing (where a computational task would be split among multiple computers or processers) than the “sharding” technique Google had used, which was to split up the web and assign regions of it to individual computers. (Those familiar with computer terms may know this technique as “partitioning,” but, as Dean says, “everyone at Google calls it sharding because it sounds cooler.” Among Google’s infrastructure wizards, it’s key jargon.) 🚰

Now, to understand the raison d’etre for eventual consistency, let’s take a step back and have ourselves a slightly deeper look at the state of affairs—a consideration of the heavy burden that transactions place in the Big Data terrain especially—which directly led to a serious revisitation of and widespread adoption of the eventual consistency wherewithal. As Martin Fowler aptly noted in his classic book entitled Patterns of Enterprise Application Architecture (Pearson Education)

Most enterprise applications run into transactions in terms of databases. But there are plenty of other things that can be controlled using transactions, such as message queues, printers, and ATMs. As a result, technical discussions of transactions use the term “transactional resource” to mean anything that’s transactional—that is, that uses transactions to control concurrency. “Transactional resource” is a bit of a mouthful, so we just use “database,” since that’s the most common case. But when we say “database,” the same applies for any other transactional resource. 

To handle the greatest throughput, modern transaction systems are designed to keep transactions as short as possible. As a result the general advice is to never make a transaction span multiple requests. A transaction that spans multiple requests is generally known as a long transaction. For this reason a common approach is to start a transaction at the beginning of a request. 

For this reason a common approach is to start a transaction at the beginning of a request and complete it at the end. This request transaction is a nice simple model, and a number of environments make it easy to do declaratively, by just tagging methods as transactional.

And speaking of POEEA, Fowler goes on to provide a marvelously readable survey of (some related, hard core topics such as) reducing transaction isolation for liveness, patterns for offline concurrency control, and even—this one admittedly not for the faint of heart—application server concurrency. In fact, for application server concurrency in particular, I cannot think of a better, single resource than the fine book entitled Pattern-Oriented Software Architecture, Volume 2: Patterns for concurrent and distributed systems (John Wiley, 2000) by Schmidt, Stal, Rohnert, and Buschmann. Referring to that book, Fowler aptly points out that it is 😅

…more for people who design application servers than for those who use application servers, but it’s good to have some knowledge of these ideas when you use the results (italics mine). 

So there 😎

With that, let’s bring replication into the picture. Stripped to its essence, replication means keeping a copy of the same data on multiple machines which are connected to one another in a network with a given topology. 🐴  And lest anyone accuse me of putting cart before the horse, I hasten to add that the whole reason we even have replication is that we wish to 

• scale out the servers which can serve queries (think increased throughput on the read side of things) 📶
• keep data in geographical proximity to users (think reduced latency) 🏠
• allow systems to continue functioning in the face of partial failure (think increased availability) 🔥

I concede that the replication of databases is an antiquated topic; it is hoary by the scale of internet years because the foundations haven’t changed since their introduction (circa 1970), plus networking principles have stayed unchanged, mercifully enough, if I may add 😂  Most developers, though, go about their work with the deeply engrained idea that any given database is made up of a single node; clearly, though, the trend has squarely and unerringly converged on databases that are distributed; so thoroughly mainstream have distributed databases become that it’s almost unthinkable nowadays to even contemplate that it was ever otherwise 💭

My best guess is that therein lie the genesis of the phenomenon that I had sketched at the very outset of this essay. Look, I’ll be the first one to confess that eventual consistency—an eminently sensible strategy that I have come to view it as—takes a little getting used to before it begins feeling normal, until it eventually becomes second nature (pun sort of intended) 👻

In fact, I would surmise that the next generation of technologists, who will scarcely have seen anything but NoSQL—with nary a palpable trace of transaction processing mechanism in there—will take to the notion of eventual consistency like ducks take to water 🐢  The rest of us, raised as we were on a steady diet of transaction processing, have had to go through, and perhaps continue to go through a period of sorting out the all-too-natural confusion that has surely lurked in our minds, even if diffusely so, until the proverbial light bulb went off and we saw the light (at the end of the tunnel). I just had to wedge in the tunnel metaphor in there, didn’t I? My story is that poetic license beckoned, and I’m sticking by my story 🔦

Some related topics that I’ll only mention in passing—topics that are well worth your while to dig into deeper—include monotonic read consistency and read-your-writes consistency. Meanwhile, let’s round out our exploration of eventual consistency with a foray through the vital concerns of leaders and followers. Essentially, we start with the premise that a replica is simply a node which stores a complete copy of a given database, and we want to formulate any and all questions that would be worth addressing to move forward. 

First question, anyone? Okay, I’ll throw this one out there: How to make sure that the selfsame data consistently ends up on all replicas? If we think about it, each database write had better be processed by all replicas. If that does not happen, the replicas would diverge from a common dataset. Again, tons of gory details that we’ll gloss over here, but suffice it to say that the predominantly accepted solution for precisely this problem is known as leader-based replication. But I hear you asking, How does one achieve high availability with leader-based replication? Great question, and one that will take us down the path of coming up with strategies for handling node outages, which is a deep subject right there—straddling the broad areas of software design, operations, and maintenance—so I’ll be doing some vigorous hand waving here 🙌 😱

Returning now to the core topic of this essay—eventual consistency—we have at this point built up enough of a critical mass of understanding the relevant ideas, concepts, and background that are essential to grokking eventual consistency itself. The crux of the matter is that if an application reads from an asynchronous follower, and meanwhile the follower has fallen behind (the leader), it (i.e. the follower) will possibly see outdated data. Yep, you guessed it: This all will inevitably lead to perplexing inconsistencies in the database (The same query, when simultaneously run on the leader and a follower might well return divergent results). Yes, you guessed it again, this happens simply because not all writes have propagated on through to the follower. Given the transient nature of this inconsistency, all followers will eventually catch up with their leader, becoming matched up (consistency-wise) with it. And just to drive home the point—at the risk of sounding like a broken record—this phenomenon is the genesis of the phrase eventual consistency 🛁

There is only one boss. The customer. And he can fire everybody in the company from the chairman on down, simply by spending his money somewhere else 💳 💲 💴

Once again, to drive home the point—at the risk of sounding like a broken record—I should divulge that I was endearingly impressed by the onion metaphor as well as the undertones of constantly revisiting the basics for ever-increasingly faithful conceptualizations. I trace this to my undergrad years when I spent countless hours poring over the mesmerizing pages of the classic MIT textbook on Circuits, Signals, and Systems by William M. Siebert 🚂

Consistency essentially means that a read always returns the most recently written value. Consider two customers are attempting to put the same item into their shopping carts on an e-commerce site. If I place the last item in stock into my cart an instant after you do, you should get the item added to your cart, and I should be informed that the item is no longer available for purchase. This is guaranteed to happen when the state of a write is consistent among all nodes that have that data. But as we’ll see later, scaling data stores means making certain trade-offs between data consistency, node availability, and partition tolerance. Cassandra is frequently called eventually consistent, which is a bit misleading. Out of the box, Cassandra trades some consistency in order to achieve total availability. But Cassandra is more accurately termed tuneably consistent, which means it allows you to easily decide the level of consistency you require, in balance with the level of availability. Let’s take a moment to unpack this, as the term “eventual consistency” has caused some uproar in the industry. Some practitioners hesitate to use a system that is described as eventually consistent (italics mine).

In a truly distributed environment, and when writes involve quorums, you can tune how many nodes need to have successfully accepted a write so that the operation as a whole is a success. If you choose a W value less than the number of replicas, the remaining replicas that were not involved in the write will receive the data eventually. Again, we’re talking milliseconds in common cases, but it can be a noticeable lag, and your application should be ready to deal with cases like that. In every scenario, the common thing is that a write will reach all the relevant nodes eventually, so that all nodes have the same data. It will take some time, but eventually the data in the whole cluster will be consistent for this particular piece of data, even after network partitions. Hence the name eventual consistency. Once again it’s not really a specific feature of NoSQL databases, every time you have a setup involving masters and slaves, eventual consistency will strike with furious anger. The term was originally coined by Werner Vogels, Amazon’s CTO, in 2007. The paper he wrote about it is well worth reading. Being the biggest e-commerce site out there, Amazon had a big influence on a whole slew of databases 🏧

CAP is an abbreviation for consistency, availability, and partition tolerance. The basic idea is that in a distributed system, you can have only two of these properties, but not all three at once.

Wait a second, how in the universe did we manage to gloss over Brewer’s CAP Theorem until now? Well, there’s no time to waste ⛄ So a remarkably readable discussion of exactly what the CAP Theorem is all about can be found in the pages of Cassandra: The Definitive Guide (O’Reilly), authors Jeff Carpenter and Eben Hewitt. In their words

The theorem states that within a large-scale distributed data system, there are three requirements that have a relationship of sliding dependency: 

1. Consistency: All database clients will read the same value for the same query, even given concurrent updates ☀
2. Availability: All database clients will always be able to read and write data ☁
3. Partition tolerance: The database can be split into multiple machines; it can continue functioning in the face of network segmentation breaks ☂

Martin Gardner, the mathematics and science writer, once said in an interview: 

Beyond calculus, I am lost. That was the secret of my column’s success. It took me so long to understand what I was writing about that I knew how to write in a way most readers would understand. 

In many ways, this is how I feel about Hadoop. Its inner workings are complex, resting as they do on a mixture of distributed systems theory, practical engineering, and common sense. And to the uninitiated, Hadoop can appear alien.  

But it doesn’t need to be like this. Stripped to its core, the tools that Hadoop provides for working with big data are simple. If there’s a common theme, it is about raising the level of abstraction—to create building blocks for programmers who have lots of data to store and analyze, and who don’t have the time, the skill, or the inclination to become distributed systems experts to build the infrastructure to handle it 🐝

It seems fitting to talk about consistency a bit more since it is mentioned often throughout this book. On the outset, consistency is about guaranteeing that a database always appears truthful to its clients.

Every operation on the database must carry its state from one consistent state to the next. How this is achieved or implemented is not specified explicitly so that a system has multiple choices. In the end, it has to get to the next consistent state, or return to the previous consistent state, to fulfill its obligation. 

Consistency can be classified in, for example, decreasing order of its properties, or guarantees offered to clients. Here is an informal list: 

Strict: The changes to the data are atomic and appear to take effect instantaneously. This is the highest form of consistency 🚧

Sequential: Every client sees all changes in the same order they were applied 🚃

Causal: All changes that are causally related are observed in the same order by all clients 🚠

Eventual: When no updates occur for a period of time, eventually all updates will propagate through the system and all replicas will be consistent 🚏

Weak: No guarantee is made that all updates will propagate and changes may appear out of order to various clients 🚁

The class of system adhering to eventual consistency can be even further divided into subtler sets, where those sets can also coexist. Werner Vogels, CTO of Amazon, lists them in his post titled “Eventually Consistent”. The article also picks up on the topic of the CAP Theorem, which states that a distributed system can only achieve two out of the following three properties: consistency, availability, and partition tolerance. 

Now here is an oldie, but goldie 🎁 It shows, in my opinion, our industry’s rich heritage in that it reverberates with echoes of (recent) history, which radiantly glows with the aura of just how far we’ve come since its publication (circa the turn of a new millennium, the year 2001 to be precise). This is from the public domain, should you wish to head over and browse online the periodical entitled IEEE Internet Computing—Volume: 5 Issue: 4 Lessons from giant-scale services. So without further adieu, here is the promised oldie, but goldie 🎁 In particular, it’s offered here by way of the Abstract which accompanies the aforesaid periodical, and where we are boldly told how

Web portals and ISPs such as AOL, Microsoft Network, and Yahoo have grown more than tenfold in the past five years (1996-2001). Despite their scale, growth rates, and rapid evolution of content and features, these sites and other “giant-scale” services like instant messaging and Napster must be always available. Many other major Web sites such as eBay, CNN, and Wal-Mart, have similar availability requirements. The article looks at the basic model for such services, focusing on the key real-world challenges they face (high availability, evolution, and growth), and developing some principles for attacking these problems. Few of the points made in the article are addressed in the literature, and most of the conclusions take the form of principles and approaches rather than absolute quantitative evaluations. This is due partly to the author’s focus on high-level design, partly to the newness of the area, and partly to the proprietary nature of some of the information (which represents 15-20 very large sites). Nonetheless, the lessons are easy to understand and apply, and they simplify the design of large systems. 

~ Published in: IEEE Internet Computing ( Volume: 5, Issue: 4, Jul/Aug 2001 )

Work. Keep digging your well. 

Don’t think about getting off from work. 

Water is there somewhere. 

Submit to a daily practice. 

Your loyalty to that 

is a ring on the door.  

Keep knocking, and the joy inside 

will eventually open a window 

and look out to see who’s there (italics are mine)