Understanding Cassandra's consistency and conflicts

After a long time, here comes another technical entry into my blog. I have been playing around with Cassandra trying to understand it as a system and one of the things that had often come up in many forums is the difficulty in understanding Cassandra's consistency. In this post, I hope to consolidate what I inferred from various forums, solutions and problems extended by many others who have been working with Cassandra. I intend this post to be useful to someone who has already had a flavor of what Cassandra is about and is familiar with the fundamental concepts of Distributed Systems and data stores. If not, I strongly recommend skimming through some of the basics here before proceeding further with this post.

A different ACID

Consistency in Cassandra doesn't directly relate to the 'C' in ACID. Consistency in traditional database systems refers to transactional consistency which ensures the correctness of the state for a given DB transaction. Whereas, in Cassandra, consistency of data across its replicas. In fact, it would be simpler to view this as the consistency of data that can be observed by an external client or client side consistency.  The consistency that is observed within Cassandra cluster (which might be different from that observed by an external client) can be defined as server side consistency. Cassandra does not provide transactional consistency (across multiple reads/writes) which is traded off for the higher speed and scalability. If essential, transactions and transactional consistency has to be implemented by the client. 

No rollbacks! 

An important implication of the above fact is that a Cassandra cluster (or simply cluster) could have partial writes (or writes in progress) but would not provide a roll-back mechanism for any (potentially) failed operations. For example, consider a Cassandra cluster with 3 nodes (N1, N2, N3), a replication factor (RF) of 3 and Read-Write Consistency Level (CL) of 2. Consider a write to X  is initiated on nodes N1,N2 and node N1 fails while the write is in progress. The write to N2 would succeed, a timeout is reported to client, but the write on N2 is not rolled-back as would have been the case with traditional databases. Fixing this inconsistency by retrying the failed operation or any corrective mechanism is the responsibility of the client. I believe, the only case of a true failure reported by Cassandra is when not enough nodes in the cluster are live for a given operation.  

Eventually consistent

"So what you are saying is, Cassandra cannot provide any consistency guarantees what-so-ever." No - this is a common misconception of many people that I have observed in many a user forum. Cassandra is eventually consistent. Huh!? Okay. Let me put it this way. Cassandra can be as consistent as you want it to be. The condition for strong consistency is 

R + W > N, where 

N - Number of replicas

W - Number of nodes that need to agree for a successful write

R - Number of nodes that need to agree for a successful read

And if R + W <= N, we say that the cluster is configured to have weak consistency or is eventually consistent. For example, consider the Figure 1. The system has a Read consistency (R CL) of quorum and a Write consistency (W CL) of ANY ( at least 1) and is therefore said to be eventually consistent. Since writes can succeed with just one node,  (W3) write 3 to N1 at time T0 and  (W5) write 5 to N2 at time T1 can happen independently to the same variable X. However, we can see from right hand side of the figure that a read  (R CL = quorum) at time T2 can result in different values depending on the set of nodes (N1, N2) or (N1,N3) which are chosen to serve the read request. 

Okay, I see that there can be inconsistency. But will it always remain so? And the answer is No - thanks to the read repairs that happens on the background. In both the cases illustrated here the read repairs (shown in purple) will ensure that subsequent reads will have converged on the same value for X. And this is why we say that Cassandra is eventually consistent.

Strong Consistency

Alright, now what would happen if I were to have R + W > N. Let us consider the extreme case where W CL = ANY and R CL = ALL shown in Figure 2. In this case, for the read to succeed, all replicas need to be in agreement and therefore have to be consistent before we respond back to the client.

Conflict resolution

Hold on, how did you decide that 5 and not 3 is the correct value? I didn't, Cassandra did. To resolve conflicts, all columns in Cassandra has a time stamp associated with it. Since T1 > T0 in our example, 5 becomes a later write and is therefore assumed to be correct. It is therefore evident that the nodes in the Cassandra cluster need to be synchronized in their measure of time to be semantically correct.


I thought Cassandra used vector clocks, no? After going through a number of threads and forums, I realized that this is not true. Vector clocks and version vectors are popular methods used for conflict identification. However, Cassandra already employs a per column time stamp for resolving conflicts thereby obviating the need for a causal ordering that is provided by the vector clocks.


Okay, I have synchronized my clocks. But what if I have a truly concurrent write with the same time stamp? In the unlikely case that you precisely end up with two time stamps that match in its microsecond, you might end up with a bad version but Cassandra ensures that ties are consistently broken by comparing the byte values.

Partial writes

Done. I did my math and made my cluster strongly consistent. Am I safe? The answer is both yes and no. This subtle but interesting scenario comes up when we have failures, which brings in the notion of partial writes. Consider Figure 3 which is the same example as shown before, but at time T1, the node N2 is disconnected from the cluster momentarily due to which the W5 gets timed out. This would mean that the a value of 5 is written to N2 but the write operation is not successful yet as it could not meet the required consistency level. Thereby N2 has the updated value while N1 and N3 have the older values. At a later time T2 (when N2 is back in cluster), the read can give different results based on the nodes which serve the reads.

Wait! Are you saying that we do not have strong consistency? No. We are still running strongly consistent, but there is a little non-determinism in the system. Consider Case 1 where the read goes to (N1,N3) and the value of 3 is returned after nodes N1 and N3 arrive at a consensus. It should be noted that the W5 is still in flight or in a timeout which is being handled by the client. In other words, the write is still in progress. Therefore it is semantically correct that the previous value 3 be returned.  In case 2, the read goes to (N1, N2). Here N2 has a more recent value (time stamp, remember?) and a consensus is reached with N1 before the value 5 is  returned. Now the subtlety - in this process, the W5 which was still in progress gets completed. Since W5 is now complete, the value returned (5),  is semantically the correct one. The read repairs shown by the purple lines happen asynchronously in both cases. So, despite the non-determinism we see in such cases, the semantics of consistency is still maintained and the conditions for strong consistency described earlier hold! 

To summarize, consistency in Cassandra is (a) different from that of transactional consistency (b) can be eventually or strongly consistent. A cliched conclusion to the post, I know, but I hope to have discussed some of the finer aspects that help understand what consistency means in Cassandra. Though some of these design decisions made in Cassandra incur additional effort for the developer, it keeps Cassandra simple and focused on its primary purpose - store and deliver data at blinding speeds. And trust me, it does that! 

The art of bus-riding

Today morning, a fellow student accidentally held on to my backpack to steady himself when the bus turned a corner. He looked up at me with a worried expression on his face and said apologetically "I'm so sorry, I didn't mean to.. I, I, I... was out of balance.." I looked up at him and smiled.

In the state where I hail from, school kids have a free-ride in government run buses - provided they are able to produce their
bus-pass within a micro-second to the bus-overseer (colloquially: 'kandectaar annan' - big brother conductor). As I was to learn in my undergraduate courses later, this was the speed at which early microprocessors used to operate. Therefore, keeping it folded in the wallet or inside the backpack is both infeasible and unacceptable. I'll avoid getting into the intricacies here, since carrying backpacks while riding a bus requires metier and is a topic requiring an intense treatment on its own. Losing the bus-pass is an expensive incident (as you don't get a replacement for that year) that earns severe rebuke from all affected parties. An exceptionally unfortunate situation is when teh kid realizes that he had lost his bus-pass when asked to produce on-board the bus. Elder co-passengers suddenly realize their social responsibility in educating the already shattered kid on the "art of carefulness".

Often, what clothing to wear when you ride the bus is a great dilemma, especially for the youth. In fact, it puts your morality, up-bringing and social-status at stake and determines where you end up in the social chart of your co-passengers. For instance, a young looking fellow by default is a good-for-nothing vagabond who apparently can have no respectable social status what-so-ever. A fellow with a neatly pressed shirt is tolerable and anyone with a ripped jean has no salvation, ever.

To top it up, bus-riding has a bunch of innate protocols associated with it. Any person who is occupying a double-seater is always required to offer the seat when he sees a couple standing. The decision to offer a seat when you see a couple is intricately complex and a direct confrontation of your morality. The worst part is, the correctness of your decision is never influenced by the ensuing behaviour of the couple. If they are married and abide by the socially accepted protocol of having non-mushy conversations, then your decision to offer the seat makes you earn a scornful look from your co-passengers. In case, the couple seem happy enough, you earn disdain. And if they turn out to be unmarried or just friends -  congratulations, you just got promoted to being an uncouth fellow and an object of sheer contempt for having allowed them to sit together.

With a billion people, buses are the life-line of public transportation in India and it is natural to expect them to be crowded. Bus-riding without jostling or stepping on someone is therefore a rare event and if you manage to get out of the bus after accidentally step on someone without having to put your all your known ancestors to shame, you should definitely buy yourself a lottery ticket that day. As a kid carrying a heavy backpack, my life was always in an unstable equilibrium when riding a bus. Enriching experiences have trained me not to worry too much about what goes on around you when in a bus.

But today, I looked up at him and smiled.

PS. Just in case you were wondering where I managed click this photograph, it was taken at our own Chennai a few years ago when I had been there visiting my friends.

2brnt2b is the question!

It is when you need to concentrate the most does your mind play all the tricks up it's sleeve and more often than not, the mind emerges the winner. Most of my writing is an artifact of such moments, but I'll let that be since that is definitely not the theme of my write-up today. I have always advocated that 'annoyance' is a perfect example of an intangible creation of our own mind, something that you can completely avoid. And yet, I infallibly fall for it every single time. But enough said about the mind, which I know is a product of my own contradictions. The anguished linguaphile in me had to seek solace by writing his agony targeted towards everyone and none in particular. It would be nothing short of being perfectly idiotic to fight for a lost cause, especially when the entire world is against you. But I'll stand up now and dish out a piece of my mind  to the world  in which mutilation of languages is considered fashionable.

Today, I was woken up by the muddled hooting of my phone on receiving a text message which said "tst" which was followed by another which said "txt d msg". And there it was - annoyance on two counts. The first being the most obvious - someone apparently chose me as the lucky person for his random testing of the new features of his/her phone. To explain this in terms of the butterfly effect, a few days ago the 'half-bitten fruit' folks released a new version of their iOS (to be pronounced ayyos), the impact which I had to bear now with some random person's experimental text messages. Following the two minute silence spent ruminating over my ill-luck was a half-an-hour nostalgia session recounting the undergrad days when free text messaging had been in vogue. Back then, it was the bread-and-butter communication strategy for students for a variety of recreational* purposes. The second reason for my annoyance was the content of the message - not the semantics but its syntax. The blatant non-availability of vowels in the message was just the icing that the cake needed.

That brings me to my chosen theme of the day - spelling. I can possibly understand the intent of robbing the words off its heart, if you were sending a Morse coded message hundred years ago when every alphabet communicated (or perhaps spoken too) was costing you money. Or if you were effecting a will endowing your million rupee property to an orphanage right before your very last breath^. Or if you were preparing** for an examination. But even the gentleman in me just cannot accept an email missing the vowels in a professional setting like requesting an appointment or writing to someone whom you do not know personally.

Very recently, an update appeared on my Facebook notifications; a comment that read thus "gr8,u 2 cum... pls du sumthn awsum dis wknd 4 dat." How in the sweet heaven do you guys even manage to do that! Every single word in there was perfectly misspelt! It has become fashionable to spell 'date' as 'd8' and 'time' as 'tym'. "To be or not to be" becomes "2 b r nt 2 b", "awesome" becomes "ossum" and "right" becomes "rite". And then there is "Choooo chweet" that pops up in all diabetic conversations between couples. And this list is endless. To misspell a word has sadly become a measure of cuteness in writing. If you end up spelling "do" as "du", I really think you should rather spend more time in middle school than on social networking. 

While there is one faction who splendidly mutilate the spelling by truncation, there is the other group who believe in perpetual repetition of an alphabet as a perfect equivalent for punctuation. So apparently, the length of grunting encoded using 'r'  in a "grrrrrrrrr" or the depth of disappointment in a "booooooooo" is a perfectly acceptable measure of your emotion. To say 'cooooool' is super cool and 'beautifullllllll' becomes extra-beautiful. On a similar note, the level of excitement in a "Superrrrrrr" or the measure of awe in a "Woooooooooow" is totally justified too. Sometimes, the length of repetition is so appalling that I often suspect their keyboard could possibly be the miscreant.

To all those who take pride in writing such sentences - Yes, I do appreciate your exceptional ability to comprehend sentences encrypted using phonetics and without vowels. But words are spelled in a language in a certain way for a reason - please let them be.

End of rant.

* includes SOS calls and soul-searching
** if you know what that means
^ if you don't understand this, you really need to watch more Hindi/Tamizh/Telugu movies. Don't look for Kannada, apparently even Google is not able to find any such thing called kannada movie.

dmr - a true titan

Last week-end, one of the great minds of our time, a true Titan of Computer Science, someone whom I respect from the bottom of my heart for his contributions to the world, departed this physical world. He revolutionized the world of computers - a true pioneer, a superlative mind and a great person. He invented the language that formed the fundamentals of the computers that we so freely use today. He laid the foundation for an operating system that fuels the world we live in. It is on his giant shoulders that millions ride on today and will do so for ever. He won the Turing award and the Hamming medal, something that can only be dreamt by most people. Being the intellectual giant he was, he kept contributing to this world, until his very last days.

I hate making comparisons, but it pains to see such a great person like dmr departing the world unnoticed while that of an corporate innovator gets flashed in the headlines and is being mourned by millions. By what standards is a Turing award winner lesser than the corporate wizard? But then, this is how the machinery of the world works. I guess, it doesn't matter anymore. That said, I do hope there would be a few who will recognize the magnitude of his contribution to the world. I do. 

You are one of the few people whom I shall repent not having known personally despite being almost in the same building.  Your emails signed with the famous dmr will no more reach us. You will be missed, Sir. The world will most definitely miss Dennis MacAlistair Ritchie.

http://cm.bell-labs.com/who/dmr/

Beyond the golden urn

So that's that. And we have the golden urn once again. And it doesn't end there.

The last few weeks have been an excellent avenue for columnists to mass-hypnotize a humongous audience and it is not surprising that they had milked it dry. I had run across many an article that elaborates why cricket is a religion in India. Numerous theories were churned out to proffer explanations about how a sport could bind a billion strong nation. Look at it from a hundred feet and it's just another game involving a few people. Generation after generation have warned us about the banality that surrounds the sport and how fragile the sentiments behind it are. It is also imperative that a sport cannot feed a country that has been fighting hard to establish itself on the world map. It was a dream come true for an entire nation all the same. A billion hearts beat as one today. And therefore we needed to win.

A friend of mine said she felt a sense of belonging every time India plays cricket and the things people do when they are passionate about something. There cannot be anything more honest than that statement. The thinkers have put it simply - the nation needed something to cheer about, to be passionate about, something that would help sail through disappointments that each individual is facing every moment in his life. And thus Cricket became a religion and Sachin Ramesh Tendulkar its God. A religion to a country in which you have to constantly compete - compete to progress, compete to prosper, compete to survive. We have to constantly fight against dominance from the rest of the world, fight against our own systems, fight against bureaucracy, fight against corruption, fight against mediocrity, fight for pride. A mere outlet for our passion in the form of a sport would never suffice. And therefore we needed to win.

While it is plain that cricket has been the glue that binds Indians together, a billion people coming from all obscure parts of life, it has remained just a symbol of hope and not of confidence. It is true that the flame had burned bright at times, but never consistent enough. And no, I'm not speaking of just cricket, but of a spectrum beyond it. We needed much more than a faint 'hope' to cling on to, something that can inspire us, motivate us, give us something to cheer for and aspire. And therefore we needed to win.

Today is definitely going down as one of the most historic days in Indian sports. Today is the day when we declared that the heroes of 1983 are not legends. We can do a better job of what they did earlier. They too are mortals and today, we ground them. Today, we declared that it wasn't just a lucky chance that we won. Today, we declared our will and grit to compete, fight till the finish. Neither was it an associate nation that we beat on our way, nor was it a result of a contrived complex interplay of politics. We blasted our way through the champions of the game and resoundingly declared that we are no less. And therefore we needed to win.

We needed to show, we learn from mistakes. We needed to show, we have the consistency and courage to stand up, aspiration to succeed. We needed to show that we do not merely stand and stare. This transformation in Team India wasn't an overnight process. It started ten years ago with a man who ripped off his shirt at Lord's and declared his grit and will to win.  And we never looked back. The last decade stands an immutable testimony. And today, we needed to show that irrespective of the future, we shall keep our will to compete burning bright as ever. And therefore we needed to win.


It is totally justified if you think of this to be a thought of mine that comes from the heat of the moment, a flash of inspiration that comes from passion rather than an instilled confidence. Trust me, I have been waiting for this right moment for a long time. I have had times of quiet satisfaction and pride when I have seen India stand up and command its authority and will to fight. How many of us remember our shooters and pugilists quietly wrapping up accolades in the Olympic events over the past decade? We had a time when India was huffing and puffing about a single medal that we won "long long ago, nobody knows how long ago" and now are at a stage where we take as many as 10 for granted every time. How many times have we been able to afford a contented chuckle when a coach from a pugilist powerhouse like Cuba comes over to the changing room and says, "I'm certain your boy would win the bout hands down".  We needed to show it wasn't just in a bunch of sporting events that we are competing. We needed to show that it is our indomitable spirit to compete and progress as a professional and as a peer to the rest of the world. And therefore we needed to win.

We all connect to cricket in a way that we do not connect with any other. Shedding their differences in social or economic status, Indians unite when it comes to cricket. We identify ourselves with cricket to the extent that we feel actually feel good about ourself when Team India wins. We let our thoughts and spirits fly high with intensity when we watch our team play. The Men In Blue resounded the nation's spirit today at the Wankhede Stadium. And then they lifted it. At that moment we realized what we gained was much beyond just the golden urn.