LinkedIn is Dropping ACID

OK that’s a little data science humor. ACID is a way to make sure that data stays in sync while it’s being manipulated. ACID compliance critical for providing integrity in financial transactions, but it’s no secret that creating web-scale databases is a non-trivial task, and often web scale companies break ACID compliance to improve performance.  I believe that this strategy is behind a recent set of LinkedIn anomalies. And I want to talk to aspiring data scientists about how to alleviate problems like this from their design.

I say that LinkedIn is not ACID compliant because my LinkedIn Posts have a variety of counts depending on which view I have.  They are almost never in sync but the other day it reached new levels and caused me to contact other authors to see if they were having the same problems.  Yep, so the problem is distributed around the globe.  But first let me show what went wrong.

I posted on the subject of swales, a water trapping technique meant to restore water tables and keep runoff from interfering with wetlands. Here is a picture of what you would have seen when you read the article.

OK great 861 views, 114 Likes, 18 comments (thanks to everyone for those). But when I went to look at how my postings were doing I saw 345 Views, 144 Likes, and 18 comments.  What happened to the almost 500 views?  Radical Anti-Environmentalists? The Papacy?  No just LinkedIn dropping ACID.

It’s quite difficult to scale traditional, ACID-compliant relational database systems on the cheap.  Your choices are usually to store the data in Key-Value pair databases, often referred to as NoSQL databases and the names of theses databases include HBase, Hive, BigTable, Cassandra etc.  In all such cases the programmer is responsible for making sure the databases are kept in sync.   This is great when everything works as its supposed to, but when a server goes down, or a patch is rolled into the system, who is counting where the record is kept and how it’s being updated?

Let me explain, if the database isn’t keeping the record up to date, you the programmer, have to create a structure.  Like a Java Structure that can be flattened (turned into text from its binary form).  Every time the web server points to my LinkedIn posting page the server has to send that view information back to the object keeping track of my views.  In Java this might be a Java Bean, or not.  Don’t worry we won’t go any deeper.  Now if someone comes along and kills the process holding the bean, the record is wiped out.  If there are two beans that have to be serialized and one is wiped out before the other is updated then you get an anomaly like the one we are showing on my post.

What can be done? One idea, mostly abandoned now, synchronizes replicas during transaction execution.  The processing is done in parallel, but the processes agree to some synchronization protocol.  This works fine but under some circumstances synchronization events can have greater bandwidth and latency requirements than a simple locking row of a single database.  And as an aside, since there are a million writers on LinkedIn there are not so many rows that a traditional DBMS wouldn’t do pretty well.  Unless of course you are doing like analysis, then your database is in graph form and you have a whole new set of problems.  But we digress, for the moment we just want to get the view count right.

Most of today's solutions involve a post-write replication where each transaction is executed first at some primary replica, say the European LinkedIn Server, and then updates are propagated, in batch files, around the other 24 time zones.  I don’t know how LinkedIn is doing it, so I am speculating and trying to help young data scientists understand what skills they will have to master. Basic master to slave log shipping is the simplest form example of post-write replication but it suffers from a durability vs latency vs consistency tradeoff.  How long should the slave wait before deciding the master is dead, or is finished?  Does it send a ping to see if more records are coming?  Does it include the records it is holding in queue?  All of these things the programmer is going to have to decide.

One promising method is lazy replication.  In this method, the records are EVENTUALLY harmonized with each actor carefully recording the details of its transactions.  Then over time the records become harmonized.  For the fearless you can even make population growth corrections to predict what the eventual number of reads will be and provide that figure until you have all the transactions in hand.

In the end, since I don’t work for LinkedIn, I’m just going to have to trust them to tell me how many views I have and hope they are somewhere in the ball park.

As a plug for HP, Vertica is a distributed ACID compliant database and it does have latency issues when the disks are far apart, but when we use it in the data center it is really fast.  And there is some support for distributed R!

Tell me about your, at scale data nightmare.  I’d love to hear the story.