{"id":305112,"date":"2020-03-26T14:31:13","date_gmt":"2020-03-26T21:31:13","guid":{"rendered":"https:\/\/css-tricks.com\/?p=305112"},"modified":"2022-05-27T07:17:47","modified_gmt":"2022-05-27T14:17:47","slug":"consistent-backends-and-ux-how-do-new-algorithms-help","status":"publish","type":"post","link":"https:\/\/css-tricks.com\/consistent-backends-and-ux-how-do-new-algorithms-help\/","title":{"rendered":"Consistent Backends and UX: How Do New Algorithms Help?"},"content":{"rendered":"\n

Article Series<\/h4>\n\n\n
  1. Why should you care?<\/a><\/li>
  2. What can go wrong?<\/a><\/li>
  3. What are the barriers to adoption?<\/a><\/li>
  4. How do new algorithms help?<\/a><\/li><\/ol>\n<\/div><\/div>\n\n\n\n

    In previous articles, we explained what consistency is, the difference between “strong” and “eventual” consistency, and why this distinction is more important than ever to modern application developers. We also introduced the notion of \u2018consistency tax\u2019: the extra time and effort that a development team needs to invest if they choose a system with only eventual consistency or limited consistency guarantees. <\/p>\n\n\n\n

    Several modern databases use state-of-the-art algorithms to eliminate the tradeoff between consistency and performance. Of course, we would not want you to take our word for it without a proper explanation. Therefore, in this final article, we dive into the technical details behind some of these databases. Typically, the only source of information for these technical details are research papers, so the point of this article is to explain these systems in simpler terms.  Because these systems are far more complex in reality, we\u2019ll provide the links in the text in case you want to know more and love to read research papers.<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    <\/p>\n\n\n

    Introduction<\/h3>\n\n\n

    In parts 1 and 2 of this article series, we explained how distributed databases use different replicas to spread the load and\/or serve users in different regions. To summarize here, for new readers, a replica is just a duplication of your data. And this duplication can live either in the same location for redundancy, or in another location to offer lower latencies to users in those locations. Having multiple replicas that can handle both reads and writes has a strong advantage, because the database becomes scalable and can offer lower latency to all your users, no matter where they are. However, you do not want each of the replicas to have their own interpretation of the data. Instead of small data differences between each replica, you want one unique interpretation of the data, which is often referred to as a single source of truth. In order to achieve that, you need to have some sort of agreement on data changes. We need a consensus. <\/p>\n\n\n

    Waiting for consensus<\/h4>\n\n\n

    Every distributed database that aims to be consistent has multiple replicas that have to agree on the outcome of transactions. If conflicting data updates happen these replicas have to agree which update goes through and which doesn\u2019t. This is called \u201cconsensus.\u201d<\/p>\n\n\n\n

    Let\u2019s go back to our game to exemplify why we need consensus. Imagine that the player of our game only has 3 gold pieces left, but tries to simultaneously buy two different items from two different shops for a total budget larger than the remaining 3 gold pieces. This involves two transactions, one for each item\/shop, which we denote as t1 and t2. And let’s pretend that the owners of the shops are across the globe from each other, so the transactions take place on two different replicas. If both of the transactions are accepted the user would be able to buy more than he can afford. How do we prevent the user from overspending?<\/p>\n\n\n\n

    \"\"
     An example of two replicas that each receive a transaction (t1)<\/strong> and (t2)<\/strong>. If we let both go through it would violate our business rule that users can\u2019t spend more than they own. Clearly these replicas need decide which transaction is allowed and which should be blocked.<\/figcaption><\/figure>\n\n\n\n

    We know that these replicas need to communicate in order to agree on the final outcome of the two transactions. What we don\u2019t know is how much communication they need. How many messages have to go back and forth between replica 1 and replica 2 in order to agree which transaction gets priority and which one gets cancelled?<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    As replicas in a distributed database are meant to serve users from different regions in the world with low latency, they are far apart by nature. By placing duplicates of the data closer to the end users, these users can read with lower latencies. However, when writes happen, the replicas need to send messages to each other to update all duplicated data uniformly–and these messages can take several 10s of milliseconds because they’re bridled by the speed of light as they travel across the globe. It\u2019s clear that we need to keep the number of cross-data center messages as small as possible so that the end user isn’t left waiting around for these replicas across the globe to come to consensus. <\/p>\n\n\n\n

    For a long time, it had been thought to be impossible or impractical to do this. But today, several technologies exist to keep the number of round-trips low and bring latency within normal bounds.<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    The distance between New York and Paris is 5,839 km. For light to travel from New York to Paris and then back again would take 40 milliseconds. <\/p>\u2014 Theoretical vs real-world speed<\/a><\/cite><\/blockquote>\n\n\n\n

    The most important question that remains is: \u201cHow many round-trips do we need to execute transactions?\u201d The answer to this question depends largely on the algorithms that are used.<\/p>\n\n\n

    How to reach agreement? <\/h5>\n\n\n

    It appears that in order to achieve consensus about something, you need at least four hops (or two rounds of communication): one round to let each replica know that you are about to do something, then a second round to actually execute the action once everyone agrees that this action can be executed. This is something called distributed two-phase commit<\/strong><\/a> <\/strong>which is used by almost any distributed database. Let\u2019s look at an analogy. Imagine you have to agree with a group of people on a good date for a party. It might go like this:<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    First, Polly asks everyone if they can make it to a party on Monday; she now knows that everyone can<\/strong> actually come to the party. Next, she needs to let everyone know that the party will <\/strong>indeed be on Monday, and people acknowledge that they will be there.<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    These are very similar to the two phases in two-phase commit. Of course, databases don\u2019t party so the phases have different functions. In the case of a distributed system, the phases are called: <\/p>\n\n\n\n