[MUSIC] So in this lecture we're going to look at eventual consistency and why it's such a good thing inside a big cloud system. We sort of dealt with some of the higher level views in the previous lecture. In this lecture, let's talk about actually sort of how the rubber meets the road in a cloud system. We'll also look at what some of the pioneers in cloud computing have to say about eventual consistency. So what we are looking for [INAUDIBLE] system that has these attributes, that we have consistency, we have availability, and we have partition-tolerance. We have a theorem that says only two of those is actually viable. Looking at some of the definitions there, what you're saying is that in order to get the computation done, it's gotta sort of match in a state machine, Turing machine or whatever. There exists some total order for all operations so they look as if they were completed in a single instant. That every request that's coming in by a non-failing node, has to return some sort of response. And that no set of failures less than sort of complete destruction of the network is going to prevent you from actually responding incorrectly. That's what we would like to have in our data center. We're going to sort of go through and see the Brewer's Conjecture here, that you can only have two of these. You can have consistency or availability, or consistency and partition- tolerance, or partition-tolerance and availability. You can't have all three at once. What we're going to do is to follow a sort of intuitive argument about this and then see that there are sort of orders where you can have eventual consistency providing a lot of these features. And that that is actually the way that cloud providers think about offering services these days. If you go back to basics and to sort of 101 in computer systems, what you will find is that there are actually a number of theorems, useful theorems, about knowing what the state of an asynchronous system is. And one of the more, sort of, well known resources, perhaps, that it's impossible in an asynchronous model to implement a read/write data object that guarantees both availability and atomic consistency. And by asynchronous, what we're referring to is that it doesn't have a clock. That it's sending messages from one place to another, say in the network, and the actual packets that traverse the network or the communications that pack, they're not acknowledged, they are assumed to actually have crossed the network and work. And of course, you could actually lose some of those, or they could be delayed, causing you problems about how do you know whether results have been produced for something. Or how do you know that all the values in all the systems have been updated? So in all fair executions, including ones in which messages are lost, you have a difficulty with asynchronous systems. The decisions may be local computations or messages can' t sort of incorporate what happened to all of the rest of the systems involved in that asynchronism. An observation you can make, which sort of underlies all this, is that really if you have a message and it's asynchronous, you have no idea whether it's just lost or arbitrarily delayed. Now remember, we were talking about partitions as part of Brewer's. So if the network is broken, if it's separated into two pieces or whatever, actually messages may be lost as they try and traverse between the two disconnected parts of the system. So, yeah, you can't tell that from just sort of arbitrary delays and you get arbitrary delays because the messages aren't clocked, they're asynchronous. So that's really sort of the underlying cause here and you can picture that in a way of, here's computer that's attached, well, here's a display at least and it's attached to 3 machines, 3 PCs looking at 3 different values v1, v0, v0. If your network is broken, there's no way to know that these values in the system are consistent across the systems. In this case v1 and v0 are different. If we partition it, choosing how we sort of partition the network, we can have, well, the first two processes having v1, the other processes having v0. And there's actually no way that you can observe the value in that broken part of the partition is the wrong value. So this is really sort of the problem. In partially synchronous models, each node in the network is given a clock and all clocks increase at the same rate. So we can use clocks as timers to know whether they received the message. And this gives us some advantage and is sort of the basis for a number of different algorithms. Again, it's impossible to know in the partially synchronous network model to implement a read/write object that guarantees the following properties, availability and atomic consistency, in every execution that you get. Again, it's because some of the messaging has this arbitrariness about it. So partially synchronous is okay. There are stronger sort of concerns you can say about it, but it's still not ideal. If you look at what's happening in those partially synchronous algorithms, then, if you say, well, I'm prepared to wait and see what happens inside those systems. You can get a better feeling for getting all of those three properties, Brewer's properties, to actually sort of operate together. So there are partially synchronous algorithms that will return atomic data when all the messages in an execution are delivered, for example. So if all the messages actually get across, then you can say something. And they'll only return inconsistent data if messages are lost. And if messages are lost, you could be informed about the fact that they are lost. So an example would be a centralized server to receive all the messages and have that server respond to all the messages from all the nodes. And then using time outs, you could prompt, if you don't get all of the messages through if there's a, in order to predict completion of its successful message transfer, you can set your time out and see what happens. If you don't get that, then there might be a problem with atomic consistency, but if you know that, then you can accommodate that information perhaps. So we get to a notion of t-Connected consistency. If there are no partitions, then the system's consistent, and if you get a partition, then the system can return some data. And it can be stale data, it can be data that you know isn't up to date necessarily, but nevertheless, you know something about the data that's there. And once the partition heals, you have the Opportunity that messages can update the system and there will be eventually reaching consistency. The only property you need to know is that the message eventually can get through because the partition heals. So this notion of eventual consistency takes that and runs with that idea, that if you're exchanging the messages, then, okay, if it's asynchronous, you couldn't do anything about it. But if it's partially consistent, then what you can do is to take account of all these states, and reason about whether you've received all the messages that you needed to. And so you know when it actually has all worked that your state is actually consistent. And in between times that there's some problems that need healing. Given the time window an observation that things can heal. It can vary from people running along or automatic sort of system doing the healing. You can ask, well how much consistency is really needed if you're building a cloud implementation to provide service. And depending upon what the service is, you can come up with different solutions. So if you're doing YouTube videos, what's the consistency issue, all right? People are uploading those videos, but they don't know how long that's going to take, and they're probably prepared to wait until it's uploaded. If you're downloading videos, you're prepared to wait for a little while to get the videos. And so there's time for healing to occur in terms of what happens in the system. If you're buying from Amazon, and there's a number of units available, and it's sort of counted, well, you buy something. As long as you don't buy something that doesn't exist, you're probably happy if those counters don't actually, aren't actually exactly accurate. As long as you don't go below zero and sold something, have to pay money for non-existent entity, that doesn't really matter. So, in terms of Amazon then, if you can have eventual consistency and avoid the case that you don't have any items to sell, you're not too badly off. So can you come up with the general policy for knowing how much consistency you need for a given type of service that you are providing? And can you use that effectively? So client will always see a snapshot of the database that's, if that's internally consistent and might be valid, then can you proceed doing your sales or service or whatever it is? Internally the database might be generally consistent. That the states the client sought and tracked might become invalidated by an update, but does that matter? Inconsistency can be tolerated because it yields such sort of big speed-ups, or those clients might see the wrong results. So if I'm buying from Amazon and I have to see 250 units for sale and I'd buy 3 and then it's not updated immediately or even if the 250 was wrong, as long as it's got 3 units, I don't care terribly much about adding consistency. So if we look at an example, you've got caching say replicated data and then you've got some core memory that holds these replicates, the original data. You could read cached data quite happily as long as nothing happens that would invalidate it. If you actually want to sort of update cached data, you can do that provided it doesn't interfere with the person reading it. So if I sort of ranked the location 23 and the other person looking at reads from location 75, does that really matter? As long as those two locations aren't connected by some sort of dependency, some sort of invariance things can go on in parallel and everybody's going to be happy. And so I can be buying things from Amazon, people can be looking to see what's to say on Amazon. As long as those are consistent from a sort of client point of view, well we're fine. Here you see this transaction, it's updating the call, write it's values and then it would update the cached replica and that will be fine. There isn't really any sort of objection to having this sort of out of, this event notion of eventual consistency being in operation as long as it doesn't interfere with what the client wants. So how much can you actually support with this? What does it allow you to do? And the answer is well, it depends. If you have a lot of contention of a sharing of data, then a little bit of inconsistency, if you can survive it. If you build systems that are eventual consistency and the clients are happy with the way that works, that can buy you a lot of sales love services, it all depends. So the root challenge is to understand just how many updates occur, how often those updates conflict between concurrent reads, concurrent updates. In most cloud applications the contention is rare, because there's huge amount of data and a huge number people, a huge amount of clients, huge amount of services. And which case lacks consistency or work just fine you really have a sort of a case where you can things to run much faster with that notion of relaxed consistency. So is consistency is cloud instead? Well, it depends because there are thing in which the clouds would have to be consistent. There are other things which are, so you really need to look at very sort of the analysis of what is going on in that system. eBay for example lives, if you like, by trying to make sure that things don't interfere with each other, and they try and separate everything out. They try and live with eventual consistency, they partition everything, they use asynchrony everywhere. By partitioning, they get different sorts of sets of data, and so there's less interference from one customer to another. They use asynchronous everywhere, synchronous everywhere to make things really fast. They automate everything, so the updates are really quick if they can be done. They try to remember if anything, everything fails, they try to remember what happened and they embrace inconsistency. Even to the extent that if they make a mistake, then what they would do is to go and tell the customer that, okay, we made a mistake. You can have something for free or you can have so much off the next product. They make allowances for their inconsistency and therefore have a great sort of sales model and service system. Amazon, Werner Vogels is CTO at Amazon and he built their shopping cart service. The old one, the original one, built for Amazon had strong consistency for replicated data. Dynamo was built, it uses a distributed hash table, has a very weak consistency It eventually converges so that if you leave it long enough, the data in the database will actually reflect what it is Amazon's inventory. But if you go to it any particular time, it might be a little bit out of date. Weakens consistency, but has allowed Amazon to make a huge amount of money. Speed matters more than correctness. That's the Verner sort of philosophy of the way that Amazon works, and to a large extent, commercial systems can accommodate a little bit of incorrectness. Inconsistency does bring risks, as we said. Some of those are negligible, some of those can be accommodated by giving the clients a benefit of a free service, or whatever. Others cause real difficulties. So inconsistencies can cause bugs. And if you do it too often and if the inconsistencies are too bad, your clients are going to lose faith in what the servers are telling them. So there is going to be a trade-off. So, you have a notion of what is the weak or best effort consistency, and that depends really on well what are the things that could go wrong. What are the risks involved with getting an inconsistent model? What you see often enough is that if you have a strong security in your system, while your moving gold bars or something. And you wanted your gold bars not to get lost, then you're going to guarantee consistency. And an example of that would be, if you have a medical electronic health record system, or a bank that you uses weak consistency, that is scalability, it might have clients that start getting upset with those accounts. If, for example, you get charged for an overdraft when there wasn't. It wasn't an overdraft. That would be a real sort of failure of the bank to provide its service. The properties we might want that updates securing the agreed orders. So, if somebody wants to sell something, somebody wants to buy something, that all that follows in a logical order. The durability that once you've bid for something, it won't be forgotten. That once PayPal has told you you've bought this thing, it's not going to then turn around and sell it to somebody who's got more money. It's real-time responsive, that it's very fast, that you don't have to wait too long. That the security permits authorized actions by authenticated parties and doesn't allow arbitrary people to go in and make a mess of the system. That it doesn't disclose personal data. That you have some fault-tolerance, so if systems fail, they can recover. And that you have coordination actions, the actual actions don't interfere with one another. So those are the sort of properties we might want in building it. And then we can perhaps survive with some sort of eventual consistency. So here what you see is, we're challenging the notion, if you have a state machine, or a Turing machine, or whatever you want to think of as a computer. What we're arguing is, it doesn't have to be exactly consistent, our computation, as. It can have some sort of delays. As long as it eventually gets to what everybody would believe is a consistent state, that they all will be happy with, we have a decent system upon which we can build services. But you have to know what it is being used for and why it's being used, in order to imply the idea of eventual consistency. [MUSIC]
