Robert Blumen talks with Eric Brewer, who discovered the CAP (consistency, availability, partition tolerance) theorem. The first part of the show focuses on Brewer’s original thesis presented at the 2000 ACM Symposium on Principles of Distributed Computing (PODC): What set of problems motivated the formulation of CAP? How was it understood at the time? What are the three types of systems that can exist (or are there only two types)? Is latency the same as a partition? The second half of the show covers Brewer’s more recent retrospective article on how things have changed since then: What major insights about CAP have emerged? How has CAP impacted the architecture of real applications? How can architects use the full space of the CAP theorem to arrive at the best designs? Are some types of systems more CAP-friendly? How do CAP systems recover when partitions are healed? The show wraps up with some speculation about the next 16 years.
- Eric Brewer on Twitter: @eric_brewer
- Eric Brewer’s home page at the University of California, Berkeley http://www.cs.berkeley.edu/~brewer/
- Eric Brewer: selected publications http://www.eecs.berkeley.edu/Faculty/Homepages/brewer.html
- Wired magazine profile of Eric Brewer http://www.wired.com/2012/09/meet-the-man-whos-rewiring-google-from-the-inside-out/all/
- “Towards Robust Distributed Systems” http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf PODC keynote presentation slides, by Eric Brewer
- Wikipedia article on the CAP theorem http://en.wikipedia.org/wiki/CAP_theorem
- “CAP Twelve Years Later: How the ‘Rules’ Have Changed,” http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed by Eric Brewer
- “Perspectives on the CAP Theorem,” http://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf by Seth Gilbert and Nancy Lynch
- “Dynamo: Amazon’s Highly Available Key-value Store,” http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf by Giueseppe DeCandia et al.
Transcript brought to you by IEEE Software
Robert Blumen 00:00:36 For software engineering radio. This is Robert Blumen. Today I am joined by dr. Eric Brewer. Dr. Brewer is a professor of computer science at the University of California at Berkeley and the VP of infrastructure at Google. He earned his doctoral degree in computer science from the Massachusetts Institute of technology. His research interests include scalable servers, search engines, network infrastructure, distributed systems, and security. Dr. Brewer is the former founder and chief scientist of Inktomi corporation. He has been elected to the national Academy of engineering and is a past recipient of the ACM Infosys foundation award germane to today’s show. He is widely known as the discoverer of the CAP theorem, which has had a profound influence on subsequent work in the field of distributed systems and databases. Dr. Brewer, welcome to software engineering radio. I get so much glad to join you. Would you like to say anything about your background that I didn’t cover?
Eric Brewer 00:01:42 Well, that was pretty fun. I would say the only thing I would add is I spent a lot of time historically in developing countries, trying to figure out how to use technology to improve the quality of life. And that’s been a lot of fun also, but totally different than working on the shooter databases of computing. Great. Well today, you and I will be talking about the CAP serum. The original motivation for this show was a paper you wrote a few years ago called CAP at 12. I’m going to start out talking about the early days of the theorem. And then in the second part of the interview, we’ll talk about how things have changed and evolved to start out. What sort of problems were you working on when you had this insight, which became the CAP theorem and why did that set of issues emerge at that time? I think it stems from a shift to a focus on availability and I appreciated the focus at the time, but I didn’t fully understand the consequences. And what I mean by this is pre-internet a big database system. Typically got to go on maintenance mode at night. And if you had a banking database, you would basically do all your batch processing at night to do auditing records, generate reports, and none of that was alive service. And so I wanted to distinguish things you can do kind of anytime you want, which I generally think of as batch computing and things that have to be done right now and are visible externally, which I think of is live services. So with the internet, we started to see a lot more live services and that actually starts that shift.
Robert Blumen 00:03:21 Did you see the CAP theorem as an original insight, or was it more of a, a clear conceptual formulation of something that most people sort of knew intuitively who worked with those types of systems, but hadn’t clearly delineated it?
Eric Brewer 00:03:39 That is a very tricky question and it’s very, I thought about it a lot. I would say it was an original insight to me, but I wasn’t the first to have it. I think I was the first to have it in the way that it’s expressed now, perhaps what I mean by that is that insight about availability is in the literature in a few different places, although not in the database communities, typically in the networking literature. And I know several networking researchers that have sent me comments that, you know, I kind of said this in 1987 or whatever. And I, I agree with them. They did say it, but not in the language of Shu to databases and not to that audience. And, uh, that’s pretty typical. I think as fields mature and merge that you get some cross-fertilization,
Robert Blumen 00:04:26 I, this is reminding me of a book I read recently in which a researcher pulled together insights from many different fields and his comment was it’s all out there, but no one reads each other’s journals. Right?
Eric Brewer 00:04:39 I think that’s fair. And if you look at the network literature from the eighties to contain this stuff, it’s not talking about the same set of issues, even though the core idea is very similar.
Robert Blumen 00:04:49 Would you tell us at the time you proposed this as a conjecture, how did you understand it? The CAP theorem.
Eric Brewer 00:04:58 I first understood it kind of loosely, which was, we were definitely making tradeoffs that favored availability over consistency, and those were the right trade offs. And I have actually spoken about this particular topic a lot and come back to it. But roughly availability tends to correspond with revenue and therefore it’s a better choice than people might expect. And so we were making such choices at Inktomi in particular, and I was also teaching at the same time. So I started to teach some of these ideas in my graduate operating systems class. And I had one particular day in 1998 where it kind of jelled. And the next day I gave the lecture using CAP as the acronym in the lecture. And that was actually the first time I talked about it. I mean, it might’ve been 97 actually. Sorry.
Robert Blumen 00:05:46 And what was the reception when you proposed this at the conference? The P doc conference, uh, pod C.
Eric Brewer 00:05:53 He was nice enough to invite me to give their, and they weren’t expecting me to talk about CAP. They were actually looking for kind of a practitioner that was building interesting large scale systems. Uh, but I had been thinking about this at that point a couple years, and I knew that the Potsy community, which I have deep respect for it, it has many skills that I don’t have. Wasn’t seeing it the same way I was. So I knew immediately when I got the invite, what I was going to talk about. Uh, although I actually talked about three or four topics in that keynote and some of them I think are actually also interesting, but that’s obviously the CAP is the one that got the attention and it had a pretty immediate reaction and the audience that this is something they were intrigued by and really cared about.
Robert Blumen 00:06:39 If you look up the CAP theorem in Wikipedia or a basic presentation, it’s presented as the two out of three properties from C a N T. Could you talk to describe that, what that means?
Eric Brewer 00:06:56 That was the original way I chose to present it for variety of reasons. Um, I think it’s still a useful way to get into the topic. Uh, and so what it means is basically there’s three things you’d like to have you really liked to have the data’s consistent across replicas. You’d like to have that the system is available and you’d like to have that. If you happen to have a partition in your network, uh, things don’t go too badly. And that formulation says you can’t have all three, you have to pick at most two. And I understood actually in the, even in the pod talk where I give that formulation, I say, it’s actually more complicated than that. And there’s a spectrum of choices you can make, but that wasn’t the news. The news was two out of three. And that’s why I think that was the right focus for the time. And so I think given people weren’t ready to hear it, honestly, that was the reason to present it in that kind of star choice manner.
Robert Blumen 00:07:51 Yeah. I understand that two out of three people have found a lot more nuance in that in the intervening years. And I’d like to come back to that, but for the moment.
Eric Brewer 00:08:01 I disagree with that slightly. I’d like to say the nuance was always there and it’s even in the pod seat talk it’s that you have to get over the, the two out of three first before you can understand and dig into the nuance.
Robert Blumen 00:08:13 I see. So you see it more, it’s a progression in persons understanding that they first have to grasp, uh, the most simplistic or binary version of the theorem, and then they can start understanding more of the analog versus
Eric Brewer 00:08:29 I would agree with that. And I would say it’s true, not just individually, but more importantly as a community.
Robert Blumen 00:08:35 Sure. And that’s often the case with new ideas. So let’s focus for a little bit on this. What I’m calling the binary version of the theorem, which tells us there are three types of systems CP, a P N a C, although in some reading about this, there are people who say they’re really only two it’s the consistent or the available system. Let’s start with the idea of three systems. Could you tell us what are those three types of systems and give an example of each one? Sure.
Eric Brewer 00:09:07 The classic example of AP, meaning it’s highly available in porpoise consistency is essentially the internet. And you see this all the time with stale webpages or stale DNS entries. And so it’s, it’s inherent in the internet. And in general, I would say in networking, uh, because of partitions and things like caching and, uh, distant replication, uh, that’s not consistent. It’s always very AP in flavor databases with acid, we’re classically focused on C and would typically forfeit availability and, um, may or may not actually tolerate partitions. That’s they, you don’t actually, you’re not guaranteed. You get all free, by the way, there’s lots of systems that only have one and back. Lots of them don’t have any, but the best you can do is per database databases, especially the classic acid transactions, uh, acid itself, uh, at least with the reason rights requires consistency. And so if you have partitions, that means databases can’t be highly available. And that was really the most controversial part of it at the time, which is to say that, uh, database vendors that are claiming perfect availability, probably aren’t particularly accurate. And I remember having public discussions in conferences about this very point, and I can dig into some of those, but in general, databases do have windows where they can lose data. If the network is partitioned,
Robert Blumen 00:10:32 Let’s follow on that point, that how did the database world respond when you propose it there’s a limit on what they can ever accomplish with a distributed database?
Eric Brewer 00:10:44 I think the first action was generally that I was simply wrong. And then the second reaction was I was, had a very narrow amount of consistency they had to give up was very little so let’s dig into that part a little bit. So the classic way that this comes up for databases is you have a primary and a backup and you partitioned between the two, the backup it’s either going to be inconsistent, or if you want it to be consistent, then you have to take down the whole system and different databases will make different choices. But the ones that claimed availability would essentially allow the primary to fall behind. Right? Give me the network rotation is going to be temporary. When it closes, we will bring the backup back into UpToDate status. But the fact is if the backup has a snapshot, then it is inconsistent. And so you have to kind of pick your poison there. And in fact, you will lose data if your primary goes down and your backup is stale
Robert Blumen 00:11:43 In looking at subsequent work in database, in
which the CAP theorem has had a huge impact. I see things in now that the database field embraced CAP and database try to be explicit about where they position themselves on the triangle and to be as good as they can at their particular trade off that they make. Is, is that a fair statement
Eric Brewer 00:12:08 Is a fair statement. In fact, I would say that the most beneficial thing of the CAP Ferrum coming out was really that it opened up a thousand different database projects, right? So they’re not all good, but I love the fact that people are exploring the whole space. I think that’s super healthy and lots of good systems that come from that
Robert Blumen 00:12:27 We had Michael Stonebraker on a previous show talking about a paper he’d written called the end of a one size fits all in the database world. And he was talking about many different aspects, but a lot of it focused on the type of data you’re storing. I believe the CAP is, or this development we’re talking about. It is, uh, another dimension of the end of one size fits all in terms of the availability or consistency trade off that a system makes. And there is some extent those pieces are, uh, independent variables. I do think
Eric Brewer 00:13:05 You get to the more nuance aspects. You will find that depending on exactly what you want to do with data and the kind of generic data management system, you will definitely find that there are lots of interesting trade offs to make. And lots of optimizations. You can do
Robert Blumen 00:13:20 The title of your pod C talk. I’m going to pronounce that correctly. This time was toward robust distributed systems. How was Kappa contribution toward that goal?
Eric Brewer 00:13:32 I think that I was trying to get a little bit more clarity on a few topics that I thought weren’t handled well in general by distributed systems communities. And certainly CAP was part of that. But I do think that the purpose of CAP is to make you think about these trade offs explicitly early in your design, and that’s what makes your system more robust.
Robert Blumen 00:13:54 So could you give an example of a system where that thought process would result in a more robust end product?
Eric Brewer 00:14:04 Oh, I think lots of people are doing it now, but I would say, for example, uh, I talk about, you really want to think about what happens on a timeout. You know, you’re trying to do something operation didn’t happen. You haven’t heard back whether it was successful or are or not. And that is kind of the moment of truth for CAP. You have to actually decide, am I going to continue to try again to complete that operation, which is typically what you need to do for consistency? Or am I going to give up and forfeit availability, or am I going to escalate to the user and say, I can’t make progress right now? What do you want to do? And most people don’t think that carefully about their timeouts, either how to set them or what it really means when they can’t complete an action. Yes. And one, the themes and reading
Robert Blumen 00:14:52 I’ve done is around the area of timeout. How does a client distinguish between a timeout and a network partition, or is that a meaningful distinction?
Eric Brewer 00:15:01 As a very tricky question? A lot of people believe you can’t actually reliably detect a network partition. I would say it often doesn’t matter what matters is, is the expiration of the timeout for whatever reason, right? It’s really, you are unable to complete the operations you wanted for consistency. And now you need to decide whether to delay right, or whether to give up, which means you’re forfeiting consistency typically. And if you delay, you may be delaying forever in which case you’re unavailable. And it doesn’t really matter if it’s for a partition or not vacationing will cause that to happen for sure, but it’s not the only cause.
Robert Blumen 00:15:39 So it was a partition, really a property of the system as a whole, or does each client have its own view of whether it’s in contact with the rest of the system or isolated?
Eric Brewer 00:15:52 I tend to view it more the latter and I’ll give you some examples. They’re interesting. Sometimes you can actually pass data for consistency via the client. So if a client contacts, one server, you can put stuff in, say a cookie and later that client will give that cookie to another server. And that actually you can ask, are those two servers partitioned or not? If they can’t communicate well, they are communicating via the client. And then, so there were actually some cases where that via client networking is actually a good solution. And I don’t see it that much, but I do see it, something that is, it has from a design perspective is that the client sees kind of the right thing, meaning that if a client can’t tell if you have a partition, then maybe it doesn’t matter. Right? So in this case, we know whatever the client sees, the other server will be aware of that. And so your least be consistent for that client.
Robert Blumen 00:16:46 We are mostly familiar with the term asset from database systems. I think our listeners are very familiar with that. You coined the term base in contrast to asset systems. What does that stand for? And what type of a system is a base system?
Eric Brewer 00:17:04 This was done a little bit before CAP, but in the same era of trying to understand highly available systems and how they differ from strongly consistent systems. And again, with the push on the internet, again, we were building some of the very first giant scale, 24 seven systems. And so that really put a lot of emphasis on availability now base isn’t very much a kind of tongue in cheek acronym to compliment acid. And I picked it for a couple of reasons. So first of all, it stands for kind of silly. So base is basically available soft state, eventually consistent. And it’s kind of the properties you get when you choose availability over consistency. Although I didn’t say it exactly that way at the time, but that was kind the rough reasoning and is intentionally picked to be the opposite of acid. And also is intentionally picked to imply a spectrum, just like there’s a pH spectrum from acids or base.
Eric Brewer 00:17:58 There is a consistency availability spectrum from acid to base. Now I picked, took a lot of flack for that as an acronym because it’s definitely strained, but I would point out that acid is somewhat strange as well. And in fact, it’s now sacred, but even in the early days, Jim gray and I talked about this, it’s, it’s, it’s a bit of a stretch in places too. There’s some overlapping with the letters mean they’ve never, you know, sometimes people disagree on exactly what they mean. Uh, and he even claimed, I believe in his turning award talk that, you know, that acronym came from a, you know, a hot tub session. So there are, I would actually say they’re equally serious, uh, which is to say neither one was taken that seriously at the time.
Robert Blumen 00:18:38 I think people are willing to give up a lot for a catchy acronym.
Eric Brewer 00:18:42 Yes. I’m guilty of that
Robert Blumen 00:18:44 In your talk. You said most real systems are a mix of acid and base. Can you explain that?
Eric Brewer 00:18:51 Just like Stonebraker analysis, there’s no one size doesn’t fit all. When you’re building a real system, you actually have many different components. And then you actually want to decide on your consistency, availability, tradeoffs separately for each component. So you might want it to be the things that track personal information are extra consistent, or, you know, records for billing or consistent, but you might say things that are user facing, but maybe they choose availability. And so you can, you can actually mix these eBay, which was an early adopter of CAP and base thinking, did a very nice job with this in terms of having their relatively complex site divided into many different components, some of which were classic databases, some of which were much more internet style services and they mixed them right on the same page. And they, you could have situations where most of the page was up, but certain parts of the page weren’t working, because those were strongly consistent parts that were temporarily unavailable.
Robert Blumen 00:19:50 The architect that needs to go through every service or piece of data that goes into the end result and think about what’s the right level of consistency in each case,
Eric Brewer 00:20:02 I think that’s right. And you do it for performance too. Typically the systems that choose availability are often also choosing performance and latency by things like extensive caching. Whenever you’re doing extensive caching, you by definition are saying, it’s not going to be consistent. We’ll have some timeout or some window of inconsistency. And that is usually just fine, right? Google does the same thing. You made us the same things are fine choices, but it’s, it’s also performance issue, not just consistency versus availability.
Robert Blumen 00:20:31 So we’ve been talking about this. I think I want to make it a bit more explicit. The term eventual consistency is any, anything else? The term eventuall consistency. Could you give a definition of that? And the intended meaning is that
Eric Brewer 00:20:48 You can be calm and consistent temporarily typically during a network partition, but it can happen for other reasons. Uh, and that the hope is that when you reconnect, you will have enough data to reconstruct what the right end state is.
Robert Blumen 00:21:03 This is a property of the EI system because of the C system it’s consistent at the time you do a right. So you’re saying a system it’s not completely out of date forever. It takes a little while, but eventually it will catch up
Eric Brewer 00:21:21 As a design goal. If you’re choosing availability, since we think partitions should be rare and relatively short, the best you can do, which is quite good is to say it will be eventually consistent. Meaning when I get conductivity restored, I’m going to ensure it’s consistent at that point. And then one stay consistent as long as I’m not partitioned, which could well be most of the time.
Robert Blumen 00:21:42 It sounds very interesting discussion. I think this was in your later paper, which we’ll get to in a moment about the idea of offline or disconnected as a form of available system, where let’s say the ATM is disconnected from the ATM network and it could be disconnected for a while or the get version control system. Or you might be on an airplane that doesn’t have internet. It’s not a very interesting part of the design space. You talk about that, the idea of disconnected function as an example of the theorem.
Eric Brewer 00:22:22 Yeah. And actually it’s an important example because it is when I was teaching one of the examples that led me to the CAP theorem. In fact, some of the papers I was teaching at that time, things like the code of file system, which is a disconnected file system made for tilling. You have your laptop on a plane, you could work on your files locally and then sync them up when you get back. And there are other systems, another famous one called by you that had a kind of propagation model to restore consistency. And so these were examples where they were choosing a and then trying to provide eventual consistency by fixing it up. And one hallmark of all these systems is they cannot guaranteed always be able to fix it up for example, and get you mentioned and version control in general, it’s not guaranteed that all your mergers will work. Occasionally you’ll get conflicts that you have to fix by hand. And that’s exactly the place where availability prevented consistency.
Robert Blumen 00:23:16 And that would be true of any highly available system. Is that not the case?
Eric Brewer 00:23:21 It is not the case for very interesting reasons that are, I think really the, where we are in the most modern part of the research, which is when can you have consistency and availability, right? What are the limits? And I’ll give you the general answer, which is you can do pretty well with consistency and disconnect operation. If you have only local invariants, I mean, you don’t have any global names or global properties. Those are the ones that break when you lose connectivity. So in general, yes, and available system, uh, that wants to have, you know, strongly consistent global data is going to have to do repairs upon reconnection. But you could say maybe I don’t need strongly consistent data, uh, for my particular application. And I would certainly, I think that space needs more exploration.
Robert Blumen 00:24:11 Would this be an example of this? Be if something like get, if I was willing to check in files with version conflict and leave the unresolved version conflict in the file. And that was an acceptable file to me,
Eric Brewer 00:24:25 That would be a good example because there are no global invariants in that example. And in fact, if you squint actually a lot of systems do that. The first one I saw that did that was actually the, uh, the Palm pilot contact manager, where if you merge contacts for multiple Palm pilots, it would just keep all the duplicates and you had to go through by hand and merge them.
Robert Blumen 00:24:47 It sends up, pardon me, this opens up another area of the design space, which is how does a system cope with reconciliation on recovery from an partition?
Eric Brewer 00:24:59 That’s one of the things I wanted to push on in the, the 12 year paper, because I really felt that wasn’t being discussed enough. And I really feel like that is what an architect ought to do if they want to really get the nuance behavior out of cat, because you actually have to think about your timeouts, think about your partitions. And in particular, the hardest part is partitioned recovery. Meaning now that we’ve closed the partition, I can communicate, well, how do I restore consistency? And I gave some general guidance for that, but I actually think that there’s a, that’s an area of active work. And it’s very interesting.
Robert Blumen 00:25:36 I want to switch into covering this paper since we’re talking about partition reconciliation and recovery, let’s keep going in that direction. What are some of the interesting developments in that area that you just referred to?
Eric Brewer 00:25:51 Well, let’s see. So there was, there’s been a couple, there’s been work at Berkeley by Joe Hellerstein and his group on monotonic systems. What that means essentially is if the value of a variable only goes in one direction, then it’s easy to reconcile it because when you merged them, you can take the, the higher of the two values. And so that’s a constraint system, but it actually works for lots of things. And in fact, um, it’s a generalization of something Amazon famously did with their shopping cart, which was if you have to versus the shopping cart due to partition, when you merged them, you can basically just take the union, meaning that if an item was deleted on one side and not in the other, when you merge them, you just put them all back. And it does mean that you’ve forgotten that the nodding was deleted, but you know, it’s not, that’s not that big an error and the user can delete it again if they want to. And by the way, being Machiavellian, it’s actually better to have too many items in the shopping cart than too few. I think
Robert Blumen 00:26:47 Sir would probably want that if they had
Eric Brewer 00:26:49 To make a choice, I think they would. I don’t, I’m not
criticizing Amazon’s choice. I think it’s a very reasonable choice, but that union operations, the kind of general thing that you can do when you merge sets post reconciliation or post partition,
Robert Blumen 00:27:02 Thinking about the monotonic case, if you had a bank in which you could only make deposits, you could take the sum of all the deposits that occurred in both sides,
Eric Brewer 00:27:12 Partition, and generalizing that you, if your operations are competitive and associative, you can always take your set of operations from both sides and merge them and have it work out. The problem with banking is that, uh, they’re not competitive because even though it’s only plus, and minus the minus has a bounced check and that makes it not competitive. But then that is exactly the interesting case for the ATM,
Robert Blumen 00:27:35 The ATM, if it’s disconnected and you want to withdraw a hundred dollars, it has to decide whether to do that or not. And it might create a negative balance if it had the full state.
Eric Brewer 00:27:49 Yes. And so the way the bank handles that, which I think is a beautiful example of the nuanced version of CAP is in general, all, let you go deposits some amount while disconnected. Let’s put a maximum on it and say it’s 200 to $500. That means that at most, at least per ATM, you could overdraft by $500. And the bank has to site, is that good or bad? And I would say the answer is it’s good because in general, you’ve had all those ATM is be available rather than unavailable. So they’ve made more money. And in practice you have long lived relationships with these customers. And even if they’re overdrafted now that will probably get resolved and you’ll probably charge them the penalty. And actually come out ahead
Robert Blumen 00:28:32 Just now, when you said deposit, did you mean
Eric Brewer 00:28:34 The draw? Yes. Sorry. Yes. If you, if you over withdraw, chances are in the longterm, you will make deposits and this will actually be fine. And we’ll charge you an overdraft fee on top of it, just for their trouble.
Robert Blumen 00:28:47 This example you’re giving now you’re talking about the design of compensating transactions to deal with conflicts that occur Gregor hope he has, has written about this in a different context, that as long as you have compensating transactions that you can do, then consistency’s not necessarily so much of a problem. Would you agree with that?
Eric Brewer 00:29:11 I would agree with that. I would say that’s actually how the real world works, that in general, you know, the check is in the mail. We do not have consistent information, but we have is audit records and we have compensation.
Robert Blumen 00:29:23 Yes. So, uh, I’m gonna wrap up this thread. We’ve been talking about ideas that came out of this paper, the CAPita 12, by my calculation, we’re now at 17 CAP is going into its teenage years. I’d like to get your opinion, what primarily changed in either your understanding or the community at large in the time since you first proposed this?
Eric Brewer 00:29:48 Well, I think the most important thing, as I said is, is the exploration of the full space. And that is wonderful because you weren’t really exploring much of the space before. And again, there’s, there’s more database projects than there have ever been by a large amount. And that’s healthy. I think that’s a lot of good stuff’s going to come out of that. And a lot of learning is going on both individually and as communities. So all of that has been great. I would say these more nuanced things we’re talking about now, like how do you really get an eventual consistency? And what do you do to reconcile thing? How do you do compensation? Those are, I think still pretty open and very interesting. And then the last one is what kinds of invariants can you have on your data? This is work by Peter Bayliss, among others at Berkeley, such that, you know, you can do transactions and still get, um, good performance and reasonable tolerance to problems. And that has to do with, you know, weakening what you expect out of consistency a little bit, but it’s how much you have to weaken is very interesting.
Robert Blumen 00:30:47 Could you give an example of, of how consistency could be weakened and what type of invariant could still hold?
Eric Brewer 00:30:57 And in that case, general, you want invariants to be local or meaning that the day that you happen to have on your side, if you can keep it variant, just relative to that, then you can make progress. I think things that hurts you are global and variants. Like for example, I want to have a unique number. Well, you can kind of work on that. For example, you might say that every server’s given a range to allocate from, and therefore guarantees that service would never allocate the same number and there, then you have an invariant that’s local, meaning that I can always allocate a number because I know no matter what I’m connected or not, and no one else can allocate that number. So there’s lots of small techniques we have, but I would say the subtle thing here is that when you have a consistent system, you don’t really need to know what your invariants are and that’s a great crutch.
Eric Brewer 00:31:47 And this is, I think under a, well, a misunderstood thing is really what I want to say. I mean, that people think consistency is great, but actually see, they don’t realize the real reason it’s straight. And the real reason is great. Is that for the invariance you don’t know in a consistent system, they tend to work. If you choose availability, you have to be much more explicit about your invariants and think about them carefully. And that’s hard work. I think it’s worth it. And it’s what great architects should do, but it is more work than kind of inheriting consistency from your underlying system and not having to think about it. Conversely for end users, consistency is the preferred model. Exactly, because it kind of does what they expect. There are no surprises
Robert Blumen 00:32:30 In your original paper. You said people love acid. And don’t like to give it up. Is that what you meant by this statement?
Eric Brewer 00:32:38 I would say it was even a stronger feeling at the time, meaning that the acid was deservedly. So a triumphant, a victory over data, in some sense, you know, the transactional model and, and Jim gray and his turning the ward very well deserved, uh, that is something special and it was the way to approach data management. And so to say, well, you might want to think about availability and even for the consistency that was at least the beginning, not well received, although Jim gray himself had no problem with it for the record, you and I talked about it many times
Robert Blumen 00:33:12 Back up a minute, the idea of giving out a range of values. For example, you give a server or the range one to 10, so you can create account numbers in that range. One to 10, the next server can create account numbers two to 20. So the service could individually continue to create new accounts and assign them numbers. And you’re guaranteed to be able to merge,
Eric Brewer 00:33:37 Is that what we do for Mac addresses, every vendor that makes Nita that card is pretty given a range of Mac addresses that are allowed to use net for, we never have any conflicts on Mac addresses.
Robert Blumen 00:33:46 I could imagine an attack on an ATM where let’s take this ATM offline, uh, and then withdraw $200 from a thousand different accounts. So another example of this invariant via a limit on the total withdrawals that a single ATM node could make while it was discussed
Eric Brewer 00:34:07 Connected, well, it has two natural limits already, but yes, that would be a reasonable one. Variant also the natural limit is the back doesn’t have that much cash and he left all the cash in the ATM you’d be bummed, but it wouldn’t bankrupt. The bank, this second natural limit is it can only dispense cash for users. Who’s credentialed. It happens to know meaning that that card has been in that machine before probably. And there aren’t that many users and a adversarial user, even less likely to be in that list. I guess they could. They could. I think that I can have a single user that’s clever, could make sure that they have their credentials in many different HTMS from the same bank, pick them all offline, get $200 for each of them and kind of like check hiding, uh, avoid consistency for awhile. And in both tech hiding case and this ATM example, the bank will figure it out when they reconcile that partition and the cook has to be gone by then, but a very risky endeavor. Indeed.
Robert Blumen 00:35:02 Yeah. So we’ve been talking about compensating transactions, how systems deal with conflict and conflict resolution and exploring the full space, the CAPtain. Are there any other major influences in the 17 years that we haven’t discussed?
Eric Brewer 00:35:20 Sure. I would say several people have talked about the performance issues, uh, Daniel among them. And I agree with his assessment it’s in the 12 year paper also, meaning that many times architects are choosing the properties that go with availability with are choosing them more for latency reasons. And for availability reasons, if you use a lot of cash and you’re often doing it for performance, not for availability, but the net effect is the same that you are risking consistency. So the latency aspect is a legitimate part of the thing. And again, I think that’s a, that’s a good and more modern interpretation. And I, I always supportive of that view
Robert Blumen 00:35:57 Throwaway, you could restate the CAP theorem to make latency appear as part of the formulation,
Eric Brewer 00:36:05 Uh, well that nobody actually made a six letter acronym, which I can’t quite remember that included latency. Um, but the idea is that the system behaves somewhat differently, whether it’s partitions or not, this kind of gets back to one of your original questions, which is, uh, I claimed that there are three valid systems, including the ones that don’t have partitions and many practitioners say, that’s not true. You have to choose between CNA. And the distinction is people that view it. You’re choosing between CNA say that because they believe partitions are, are unavoidable. And I think for a distributed system that is true, but the CAP actually applies to non distributed systems as well. And in fact, the classic example of something that would be a sea of which they’re not many things is really kind of an enterprise database that you know, is inside a land has a very low chance of partition is the chance zero.
Eric Brewer 00:37:04 No, that doesn’t mean that, um, it’s, uh, can’t tolerate partitions even though that’s literally true when you get to things that are super unlikely, like a partition in the land, especially land with multipath. The reason I don’t view that is that big a case is because in those cases, your probability to now lower than the probability of the system, not working for other reasons, such as software problems. So it has to do with, if you bet on AMC bowl, is the problem, your system failing, do more to a partition in which case you’ve made a mistake, or is it due more to a software problems, which case I think the partitions irrelevant, but for David systems, partitions are something you can’t avoid.
Robert Blumen 00:37:43 I had understood the AC distributed system to be something like a sharded database where with no replication. So each shard could continue to take rights, even if it can’t communicate with the other shards is, is my understanding of that,
Eric Brewer 00:38:02 Correct? That’s actually an example of something that depends on whether you have only local and variants. So if you have charts with no replication and only local and variants, for example, there’s no constraints. If you don’t have duplicates, then you can make a system like that. It’ll still lose availability because if you lose one of those nodes, you lose availability for those keys, other keys. But if you have any global and variants on that data, then you lose consistency. Okay.
Robert Blumen 00:38:29 Um, so like to wrap up my last real serious question, where do you see the future of did systems and database is going in the next coming years?
Eric Brewer 00:38:41 I think we have another five, maybe 10 years of kind of new systems and exploration. Um, and then it’ll probably dwindle a bit, at least for awhile. I don’t know, maybe today it’s probably at least 10 years. We have 10 years more shoot days basis being a hot topic to go when it would settle down. Depends really, um, you know, uh, a few good implementations covering most of the space is kind of what happened even in the database space prior to CAP headed, settled on acid, there was consolidation in the space actually in terms of the number of players. Um, I wouldn’t say the feel that had stalled, but researchers had moved on to kind of other things. And I think the same thing will happen once we get through this wave of understanding global and local and variants and building artifacts in parallel, some of those artifacts will be great. It’s hard to know which ones. Um, also I think the cloud is going to be a big practical effect here that down the road, there isn’t that much reason to have a million databases. I think there will be a small number of winners, some open source, some not, and then services you can use on cloud providers that actually give you those properties. And then you don’t need to write them yourselves.
Robert Blumen 00:40:00 It will become more formalized in a way I can go on Amazon cloud. Now click a button and have a, my sequel or an Oracle server, or, uh, I can have it backed up or hot standby. And it’s gotten to a matter of anyone who can point and click can have whatever range of properties they want.
Eric Brewer 00:40:20 Yeah. So that, that is a different kind of the consolidation, but roughly most programmers will end up not working on state management because if something they get from their framework,
Robert Blumen 00:40:31 Most of the databases that have come out in recent years have emerged from industry in contrast to the acid world, which was more dominated by commercial products. Do you, uh, have any thoughts on that either why it is or whether that will continue? Well, I think we’re still
Eric Brewer 00:40:53 On the stage, although a little bit decreasing where a small group can ride an interesting system and make interesting choices about how they want to manage data. And, you know, the nature of open source, the nature of a cloud, giving people lots of resources to play with means you can actually build and test pretty big scale systems on your own in a way that wasn’t possible 10 years ago. So I think we’re in a fertile time for exploration in general, but certainly for data management systems. But I think again, at some point, those do end up needing to be commercialized because they need support contracts. They need maintenance, they need documentation and they’re that easy to build. And so as with the database industry in general, there will continue to be commercialization of a variety of systems because that’s actually what those systems need to do to have impact.
Robert Blumen 00:41:45 I have a Google question and you can either take this or not, uh, depending on if you feel appropriate. A lot of the open source databases have come out of some of the big tech companies like Facebook and LinkedIn. Then you have examples of companies like Amazon, which has had a huge influence on databases through their dynamo research paper, but mainly by people taking the ideas and building their own version of it and Google and the same way that Hadoop and some other databases, I think H base were an attempt to, to build a product according to a Google research paper. Do you see that split continuing between the open source world and certain companies keeping stuff proprietary and maybe disclosing how they did it, but not releasing the technology?
Eric Brewer 00:42:38 I think we’ll continue to see a mix. You know, Google, ironically doesn’t really use map produce much anymore. Internally we have newer systems that have replaced it. And, uh, I’ll actually be talking about some of those in an upcoming keynote, but in general, it’s important to do some publication, but it’s not, you know, as it’s always been the publications, don’t always contain all of the secrets. They also don’t always contain the latest stuff, but they’re still useful for lots of reasons. And it also is very useful to get many groups looking at these things and, and building systems. That’s all great.
Robert Blumen 00:43:14 We’d love to have you come back on and talk about some of the cool new stuff at Google after you give your keynote.
Eric Brewer 00:43:23 So it’s certainly a possibility,
Robert Blumen 00:43:24 Okay, let’s wrap up. If listeners would like to follow you or your research, where is the best place to go?
Eric Brewer 00:43:33 That’s a good question. There is no great place to go. I’m not hard to find online obviously. And, uh, I occasionally use Twitter to tweet things I think are interesting, Eric underscore Brewer, but, um, you know, at the moment, because the work I’m doing is largely Google and the work I do in developing countries, I’m actually not publishing that much directly on these topics. Like the CAP of 12 with the last paper I wrote that was directly on this area. Although I do meet with students and certainly advise a lot of different people, Google included, but I publish the stuff I’m working on at Google. And then not to just,
Robert Blumen 00:44:09 We’ll definitely link to cabin 12 in the show notes. And there is a page on the university of California’s website, which lists many of your publications. I don’t know if it’s all of them, but it’s a, certainly a pretty big number of publications that are listed there. And we’ll put that in the show notes as well. That sounds great. Thank you. So Eric Brewer, it’s been great having you. Thank you very much for speaking to software engineering radio. I pleasure for our listeners. We would love to hear back from you about what you like or don’t like about an episode or the show in general, you can go to iTunes and write a review. You can leave a comment on our blog, hit us on Twitter at se radio, or find us on Facebook, LinkedIn, or Google plus search for software engineering radio for software engineering radio. This has been Robert Blumen. Thank you for listening.
[End of Audio]
This transcript was automatically generated. To suggest improvements in the text, please contact [email protected].