AWS Abandons Custom Gossip Protocols for Paxos-Backed Metadata Stores

AWS放弃自定义Gossip协议，转向基于Paxos的元数据存储 随着云弹性迫使每位开发者构建分布式应用，团队必须依赖标准化的共识原语，而非在罕见规模异常下必然失效的自定义协议。 AWS工程师Allan Vermeulen与Swami Sivasubramanian深入探讨了云弹性、通用硬件以及不断扩大的规模如何将每位应用构建者转变为分布式系统开发者。他们剖析了关键的分布式原语，包括组成员管理、服务发现、元数据存储、故障检测以及幂等工作流，将静态文件和Gossip协议等朴素方案与稳健的共识系统进行了对比。演讲者指出，分布式一致性最终要么依赖单点故障，要么依赖如Paxos等经过验证的共识算法，否则在极端情况下必然会崩溃。最后，他们追溯了亚马逊在共识领域的运维演进历程：从共享代码库和锁管理器，发展到支撑Amazon Kinesis和DynamoDB Streams等服务的符合ACID特性的事务日志。 部署在云上的每个现代应用本质上都是分布式系统，这迫使开发者必须在通用硬件上构建高可用软件，而非依赖定制的容错机。 (3:45) 诸如组成员管理、服务发现、故障检测和工作流等核心分布式系统原语，最终都可归结为分布式共识这一基本问题。 (37:25) Allan Vermeulen提出，每个具备一致性的分布式系统，要么依赖单点故障，要么在其底层实现Paxos，否则其根本就是存在缺陷的。 (40:00) 亚马逊的共识架构经历了演进，从原生Paxos库到中心化锁与租约服务，最终落脚于为Amazon Kinesis和DynamoDB Streams等服务提供支撑的事务日志。 (43:00)

[30:00] Allan Vermeulen: Silence in a distributed system is very, very hard to deal with. Because you can't tell the difference between somebody who's just resting and somebody who's failed. [37:25] Allan Vermeulen: Agreement in your distributed system really is the fundamental problem. [3:45] Swami Sivasubramanian: And every app is becoming a distributed app. And every developer is becoming a distributed developer, whether they like it or not.

[0:00] All right, good morning, everybody. I hope you all enjoyed Werner's keynote. My name's Al Vee. I've been an engineer with Amazon Web Services for better than 10 years, which is an awful long time. In fact, it was almost 10 years ago to this day, within a few weeks of this day, I was in an offsite meeting just off of Amazon's main sort of campus and sitting around a table with Swami and a few other people brainstorming about the idea of building a cloud storage solution. And the results of that were a few weeks later, I guess, We built the S3 team and started building the product that became S3. Um... So along that road, so during the 10-year period, we've learned a lot about how to build distributed systems. And that's really what we're going to be talking about Yeah, my name is Suomi. I'm part of the database services team. I manage DynamoDB and other non-relational database services. In addition to the core AWS database platform, which is... based on which the rest of AWS and Amazon is built on. So in this talk, the crux of what we are going to talk about is like how did services like S3, DynamoDB, and other things actually were built? And what are some of the key distributed system primitives that we learnt. and actually built along the way to build these services that our customers are using. All right, but before we do that, I want to talk a little bit about cleaning your house. OK? So it turns out that through the first half of the 20th century, there was kind of a Moore's Law for vacuum cleaners. So in the beginning of the first half of the 20th century, there was nothing. This is the Skinner vacuum invented in 1905. It's the first portable electric vacuum cleaner. And things happened very quickly after the Skinner vacuum came out. Vacuum cleaners got lighter and smaller and more prolific. And here's what people thought would happen. People thought, because we have these electric vacuum cleaners now, we're not going to have to spend any more time doing housework. Right? This is going to be awesome. But it didn't happen that way. And Swami, who it turns out is an expert in housekeeping, can tell us why. I mean, the reason primarily is, like, our expectations of cleanliness grew up. Two things conspired against it. Our expectations of Clenolus went up. And then as we were able to clean houses better, Scale went up. People started buying bigger houses. So these two things started considering against it. And this is true. But like vacuum cleaners get-- becoming lighter and lighter. It does not mean like people had more free time, so they started reading more. or they started enjoying odds or other things. These things kept conspiring against them. To some extent, the same thing is going on with the computing industry as well. Moosh Law, I mean, all of you know, computing systems are getting more and more capable. However, it's not like the code we wrote like two years ago is now running like twice faster. I mean, if that was the case, it would be awesome, right? I could actually get goals of... so many things where, like, my customers are getting double the latency and with nothing to do, no optimizations to do or anything. But in reality, the expectations, what we uh... get out of these systems. It can be Amazon.com, it can be actually, let's say, DynamoDB or S3. We want actually continue to drive for like lower latency, better throughput, and many other things. So one of the frustrants that actually, what we are seeing driving the growth in distributed systems in Amazon and many of our AWS customers as well, is that there is this ever-running race between computing power and expectations. OK, so that's one trend we have is that expectations are going up all the time. And things like big data and the web itself are driving the expectations of what we can do with our computers. I want to illustrate another trend with this picture. Anybody here go to the University of Waterloo besides myself? We've only got one Waterloo-- a couple of Waterloo grads. Well, so it turns out that they built the math and computer building in Waterloo in 1967. And the architects had the foresight to include a room downstairs that would house the computer. And this was super cool. When I toured Waterloo, when I was in high school, I walked around the gallery that's way up there and looked down and saw, I think it was an IBM 370 at the time, and thought, "Man, this is awesome. Like, this school has this big honking computer. I want to go to school here." And so the original data center here at the University of Waterloo was basically built to house one computer. And Swami, you've been to Amazon data centers in the past. Is that still sort of the way it is? I'm not allowed to share the number of servers even in a single availability zone. But I mean, nowadays, the real issue is that each data center hosts like hundreds of thousands of servers at any given time. And that leads to the number two trend which we are facing within Amazon. And this is true across this is that the number of computers that we are [5:00] using-- I mean computers, but in reality, most of you are server programmers. The number of servers that we are using in our application is going up fast. Gone are the days where you can deploy it in a single server and then database and then you're done. Instead, we are actually-- every application is distributed. And distributed systems is not a niche field anymore, which is reserved for, like, academics. I mean, you are starting to actually think about failure modes across multiple tiers. And every app is becoming a distributed app. And every developer is becoming a distributed developer, whether they like it or not. And I'm going to illustrate a third trend that we want to use to underlie the sort of foundation of the primitives we've built. by talking a little bit about fault tolerance. So in the old days of having one computer in the data center, engineers put a lot of effort into making that computer rock solid. I'm going to illustrate that concept with a picture of this airplane. This happens to be my airplane. And airplanes have this same issue. Airplanes have this issue that failure is really bad. Like, when you're flying a plane and it fails... That's not where you want to be. So as a result, airplane designers put a huge amount of effort into making sure that an individual airplane does not fail. Like my airplane, like most other airplanes of this sort, every cylinder in the engine has two spark plugs. So there's redundancy in the spark plug systems. Those two spark plugs are driven by completely independent ignition systems. So if something goes wrong with your ignition system, you have a backup ignition system. There are two batteries. There are two alternators. Two completely independent electrical systems. I have five GPS's. I still get lost, but I have five GPS's on board my airplane. plus my iPad. um... so The point is that what airplane designers have done is put a lot of money into making these systems highly resilient. Each individual airplane is highly resilient, the same way that we used to build computer servers back when I started at Amazon in the late '90s. You know, we had these awesome servers that had dual power supplies, and they were multi-homed. And they were basically built to be-- each individual server was very solid. On the other hand, there was a downside to that. And that's really the key thing about hardware and software trends, which Amazon itself has, like the earlier, it used to be even during the early days of Amazon, we bought these giant boxes that are specialized hardware with built-in redundancy at multiple levels of, processors and network cards and various things. What it enabled us was to actually build simpler software. I mean, we had to-- we can ignore safely all the complexity, but That's not really true, because it shows up when we really have some bad issue with it. But now the new edge is something a lot simpler. It is all about commodity hardware. that you can actually get on the cloud, but what developers are forced to think about now. is that they've got to build smarter software. You've got to be aware of, like, are your servers actually distributed across multiple availability zones? What is your failover strategy, and how does it work? So this is one of the third trends, actually, you wanted to call, Basically, the commodity hardware and smarter software. And that's actually great for us, right? Because what happens is the way that we compensate for the fact that we're running on commodity hardware is by investing in software. And that's what a lot of us do. So we like that. This is a picture of Amazon.com's website back in the early '90s. And I want to talk a little bit about how we architected the Amazon.com website when I got to Amazon in the late '90s. It looks something like this. It was a basic client server system. There were a bunch of hosts that we called onlines. So these were a number of, at the time, Unix servers. Um, And we had a fleet of those. They took web requests. And then they connected directly to a couple of databases. And then they would use the data in the databases to answer the web requests. and move on. Now, the thing I want to talk about with respect to this architecture is how do we decide how many onlines to buy, and how do we decide what size database to buy? And you're all at the AWS conference, so you understand where I'm going with this. What we'd have to do is buy a sufficient number of online hosts so that we could scale through our Q4 peak. because people buy stuff around Christmas time. And we'd have to buy a big enough database that we would manage to survive Q4. And what would happen is Q4 would come along, and at Amazon, we would all be kind of hanging on and survive barely by the skin of our teeth, and everything would just hold together. And then we'd get to Q1, and we'd have all these hosts, and they would be mostly sitting idle. What we'd actually like to do is reduce the number of online hosts. And we'd have a big database, and we didn't need that big database. We'd prefer to have a smaller database. And of course, as you all know, that's not how we do things today. Yeah. So the new world of Amazon has drastically changed. boxes with auto scaling groups where we are not locked into capacity anymore at a quarterly level. [10:00] Instead, they are getting auto-scaled at an hourly level. And same thing is true for even the database. Nowadays, now, our database is a lot more elastic, and things can actually go up and down. as much as we want. While this is talking about how we are using services, the underlying trend which becomes true is that With cloud, elasticity is the new normal. and The result for a distributed systems developer is that it's more complexity. I mean, this effectively means you as a distributed systems developer has to deal with actually varying set of processes or servers in your system and... And how do you deal with that? So... In summary, this is the world where we live in. It really comes with like high expectations and enormous scale. Every app is a distributed systems. whether you actually believe it or not or like it or not. And we live in a world of commodity hardware where everything is elastic. So with these constraints in a world, These are the challenges a developer has to deal with. Right, so these four trends are actually terrific for most of the computing industry, but they do come with challenges, and that's mostly what this talk is about. So for example, with high expectations comes the reality of scale. Um, uh, many apps nowadays have to be able to scale broadly. So gone are the days when you can build an app, run it on a single server, and be content with that. With the fact that every app is a distributed system, comes latency and concurrency. One of the things that that I think is important for people to realize is we-- at least some of us who are old enough-- kind of grew up in a world where the way we-- when we studied computer science, we learned to decompose a problem into maybe objects or subroutines or something like that. And then you'd have a single app where you would make calls to those subroutines and they would return right away. And in the new world, even though sometimes we model things with RPC calls that look like that's what's happening, that's not what's happening. In the new world, the difference in latency between calling a local method and a local method and a local method and a local method. and calling something remote via distributed call is enormous, right? You go from nanoseconds to, at best, microseconds, maybe milliseconds. And because of that, we're also running everything concurrently. So we have to deal with these challenges of latency and concurrency. Um, One of the questions I sometimes ask when I'm interviewing is, why are distributed systems hard? And this is my favorite answer. The reason distributed systems are harder-- one of my favorite reasons that some people know-- is because you have to deal with partial failures. In the old days, when we wrote a program that would run on a single computer, you didn't really have to deal with partial failures all that much, right? I mean, you wouldn't sort of have an object in your Java JVM or whatever sort of-- fail, because if the object had failed, your process has failed, like everything's failed. There's a shared fate between all the components that are working together. In a distributed systems world, that is no longer true. And that's, in a way, the toughest problem. And finally, no more static configuration. So one of the nice things about the original Amazon architecture was that I knew what all the onlines were. I knew exactly where the database was, and that's gone now. So-- As Amazon itself has a developer platform within Amazon engineers, when we started facing these distributed computing challenges, I mean, we looked at, like, so how do we actually... enable our developers to build these distributed systems. I mean, granted, just like any other company, we said, why not start with education? So, something called Principles of Amazon talk series, where we actually have principal engineers and architects give talk every week about great patterns and whatnot. But education goes only so far. So one of the next things we did is, like, we started building high-level services. I mean, some of them are now widely used by AWS customers like you, like things like S3, DynamoDB, RDS, Aurora, and whatnot. And then we actually built a bunch of tools to help with actually building these systems, things like code deploy, fault injection. And eventually... when you're still building on top of AWS platform, and just like actually us, let's say I'm building the next new AWS service that I'm going to launch in next re:Invent, we still need a bunch of fundamental distributed system primitives. that absolutely must have must have for us to build. So the whole talk is all about, like, what are these core distributed systems' primitives that are necessary for us to build the next big AWS servers. And we're going to pick five of them. We could have an argument sometime, and we did have a bit of an argument about what the right five should be. So we're just sort of picking five representative ones, because we only have a half an hour to discuss this. And the ones we've chosen to talk about are group membership, discovery. A metadata store, failure detection, and workflows. We're going to go through those one by one. Yeah, so let's get to... The first one right away. So group membership. So we [15:00] What is the fundamental challenge in group membership? So let's take an example. So let's say we are building S3. you get a put request for an object. So one of the first stations you need to know is actually what are the list of servers I need to store a given object. and you get a GET request for an object, you need to know what are the servers that actually already contain. This object. Same thing is true for, like, RDS Multi-AZ. So if you have used RDS, we actually have a synchronous replication system called MultiAC. where underneath the cards we have like replicated databases with primary and standby, and we elect one of them to be masters. So effectively this is again a group where you have like two members, and one of them has a special role called a primary. Same thing is true for ElastiCache as well. So the fundamental challenge with group membership is effectively deciding who is in the group and who is not. And what are the roles behind it? This might actually sound like a very simple problem. Why not just store the server endpoints in a configuration file and move on. I mean, that's not too hard. So let me just walk through a very simple example of what happens in a replicated database system I mean, this is something very similar. This example is similar to the Dynamo paper, which 10 years ago, but it's not exactly the same. So let me start with this. Now you have a three-way replicated data store. Um... and you get rights from clients. And now let's take a failure scenario where the replica C is partitioned away. So now, I mean, all is well. You actually can do a majority-style quorum voting, and you can continue to operate. So there is no issue, per se, with this model. And you can continue to operate. At some point, you want to say, hey, three replicas is important for my durability. So these two replicas can spin off a third one and get it caught out. So far, so good. There is really no issue. But then now comes the next part. What will replica C do, which is partitioned away? It is faced with the question saying, like, should I continue to serve reads? And should I start my own new quorum of sorts? Now, in this scenario, let's say it goes and does something very simple. It spins up two creating actually... parallel read and write. This is what in commonly distributed systems and databases is called as split brain syndrome. This is usually not a problem if you have like a reconciliation mechanism under the cars and you don't guarantee strong consistency. This was one of the techniques we used in the original Dynamo. But let's say you want to build a strongly consistent system, like the DynamoDB system or something else, then this basic group membership algorithm does not really work. So. That really comes down to what are the fundamentals around group membership. Right. I want to point out with the split brain scenario Swami showed, is somewhat contrived. And actually, the Dynamo system was built to withstand that kind of split brain. But the split-brain problem can happen due to very complicated network interactions with group membership protocols that don't quite measure up to exactly what we need. And we have actually seen it with various systems. So let's say that these are the fundamentals of group membership. We need to be able to add members to the group. You need to be able to excommunicate a member from the group when you decide it's failed or you don't need it anymore. And then fundamentally, discovery is really important. Somebody needs to be able to discover what the group membership is, how it's changed, and what the roles are within the group. So we're going to move from group membership over to the next primitive, which is discovery. So discovery, the problem with discovery is really simple. So you have a list of members in a distributed system, and you want to know who are all your members in your group. So let's take a simple example, saying, like, let's say I'm a new server in S3, and I boot up, and then say... Which set of servers do I belong to? for example. or like what are the replica endpoints for a given RDS multi-AZ cluster? And This problem doesn't sound too hard. I mean, we all know and we still use, actually, the most popular option, which is configuration file. I mean, this is by far the most widely used technique for building discovery. I mean, I'm pretty sure every one of you is still running, because some of my teams still do. So this problem usually works well for mostly static group membership. I mean, this is if your servers don't change that often. And You can actually continue to do it, but then in reality, If your system is elastic, like in the world of EC2, like what Amazon is right now, then any change to your membership now requires... a manual operator to come in and actually start intervening and then updating the config and deploying it and then reloading the configuration. So this does not lend well with the Elastic world we live in. So the second most [20:00] popular option that we used to use, and we still use in some parts, is DNS. I mean, DNS was built with a very simple discovery challenge in mind. How do you take a domain name that is well understood by humans and written in single server endpoint. to customers so that the browsers and all other clients could actually route to it. As programmers started realizing, hey, this is actually doing something really what I want, so why not overload it to-- discover who are all the servers behind my given application, and give it a DNS endpoint. And this seems to work reasonably well, and it's universally adopted protocol for discovery. But the problem with this approach is that Two things. One, DNS, until Route 53 and other services like that came along, it was not So you can't actually call an API and say, hey, this endpoint, now it does not have these five cells anymore. Instead, these are like now three servers or ten servers. So that does not work well. And second thing is, it does not deal with rapid changes in membership. So you can't build like a replicated failover mechanism using this and discover. And Third thing is actually the most crucial one. Historically, DNS has always scaled well because of the multiple tiers of caching. DNS responses are cached in your local box. It can be in your JVM. It can be in your operating system. It can be in your resolver caches. operated by your platform, and then your ISPs, and it just goes on and on like it's a six-layered or seven-layered caches. So this makes it super hard to learn of new challenges. So that's when we actually looked at this problem. I mean, Al actually thought, you know what? Why can't we do something better? So I'm going to talk about discovery via gossip protocol. And I'll tell you that this was actually the first sort of network primitive or distributed computing primitive that we built at Amazon. We built this for S3. how S3 does discovery for various membership things. And the idea of gossip is to use the network to discover things. So I'll tell you basically how it works. So I'm a server... And I have a list of people I think are in my group. Every second or so, I wake up. And I pick one of those people at random, and I send them a message that says, hey, I'm Al V. I'm still alive. They're all doing the same thing. So every now and then, I process a message from somebody else, and I use that to change my view of the group. So if I get a message that says, hey, I'm Swami, I'm in your group, I'll say, oh great, I'll add you to my table now. Very simple protocol. In fact, this is in the realm of my favorite sorts of protocols. And there's a lot of these in the distributed systems world. And the reason it's one of my favorites is because it's very, very simple. You know, literally the first version of this was coded over the weekend by one of the guys on the S3 team. Um. But despite the fact that it's very simple, it's deep and complex. So this protocol that I described is also called an epidemic protocol. And the modeling for how the protocol behaves, how quickly it converges, and so on, is all based on epidemic on the mathematics of epidemics. And indeed, the protocol is a virus, so there's all kinds of interesting problems that you can have because of that. But the primary problem is that different members can have different views of who are currently in the group. And this is actually the same problem that you have with DNS and the same problem that you have with configuration files. Different people have different versions of those configuration files. And that is a hard problem to deal with. It's up to the builder of the distributed system to deal with that. And I'll tell you that in the early days of AWS and the S3 project in particular, We way underestimated how that could lead to subtle problems and hard things to work out. It's just very hard to deal with the fact that you don't have a consistent view of the group membership. I'm from one side to another. And because of that, Thank you. That's right. Oh, I'm sorry. I forgot my slide. So actually, that's not just descriptive gossip protocol cons. That is the con. That is the problem. with using gossip to do to do discovery. So while we love the simplicity of gossip protocols, what it enables us to do one of the, as Al talked about, being able to rationalize this as a developer, not just building it, but also actually in an operational setting when there is, let's say, a network partition and all those things. turned out to be a huge problem for us. So one of the techniques now we have started using is actually use a metadata store or a consensus store to bootstrap. So for a list of endpoints for a given server in a cluster, we use a metadata store like DynamoDB. So as servers boot up, they actually query this metadata store, and this is a surprisingly simple mechanism to bootstrap. But then what you have essentially done We have offloaded all the complexity with respect to availability and scale [25:00] to some other entity. In this example, things like DynamoDB. So we will get to the properties of what makes an excellent metadata store. Mm-hmm. And it's an interesting question to say, so why didn't we do this in S3? Can anybody guess why we didn't just use DynamoDB to store group membership and we built S3? Nobody knows? Yeah, because it didn't exist. That was the problem. VIKAS KHAN: That calls me a slacking offer not building it earlier. So that's really-- so-- One of the key reasons, so what do you look for in metadata? There are various AWS services that are built on systems like DynamoDB to store metadata. So what is an example of a metadata that needs to be stored? So when I built RDS... I mean, one of the fundamental questions you really start off is like, When you're building the control plane where you call create DB instance as a customer, You need to store information. and some database saying, like, this is-- customer A, and this is the instance they actually ask with this kind of EC2 instance. This is the level of storage and You need to store those configurations somewhere so that next time when they do a describe instances call, you actually know that these are the things they actually query for. Same thing is true even for DynamoDB. Even within DynamoDB, we had to run like a mini DynamoDB so that we know for a given table, what are all the partitions that exist, and what are all the server endpoints for the partition? And same thing is true for ElastiCache. So let's take a brief look at what are the good characteristics that makes it. So the key things we really stress on with respect to metadata store is like three things: simplicity. We really always stress on, like, keep the access patterns really simple. So don't do... things like a big table join across two or three tables, when you are actually trying to do like a describe tables. That just means at some point your flip on you. So that's why we rather favor simplistic approaches to metadata with things like DynamoDB, which are built for query access Second thing is, it needs to have a higher availability. So you pick and choose what kind of consistency models you want. Switch to eventually consistent reads if you can. And scalability. The scale at which AWS is growing, I mean, the amount of data, even if it is not the actual data, but the metadata, that needs to constantly grow, and we don't want to be fighting always like a capacity planning exercise. It needs to scale along with you. While we have actually used DynamoDB extensively, some of the key things we have done Even on top of DynamoDB, here are some of the lessons we learned, many of the teams abstract the data store underneath, with their own APIs for a couple of reasons. One is things like they will be able to change the schema on the fly if they ever need to. Or even in case, let's say they want to move some parts of it to, let's say, a cache or Redis or whatever else, they will be--it offers them the flexibility in the future without having to go through a migration. exercise that badly. And then the third thing is actually keep the data access patterns really simple. This is one of the... major lesson we have been learning. quite a bit. So this goes back to the group membership problem. The group membership problem, the second thing we needed to do was decide when to kick members out of the group. And a lot of that comes down to being able to do failure detection, and I'm going to illustrate the essential problem with failure detection in our world with the world's funniest joke. And this is actually true. There was some kind of study about how humans respond to humor and all this kind of stuff. This was decided to be the funniest joke in the world. Not that joke. I think that's the funniest joke in the world. But they didn't ask me. So here's the actual funniest joke in the world. Two hunters are out in the woods, OK? And one of them collapses. So his eyes are rolled back. He's looking really bad. His buddy goes over. He doesn't really know what to do. His buddy whips out his cell phone, calls 911, and says, you know, my friend's lying down there. I think he's dead. What do I do? And the operator says, hold on, hold on, just calm down first, make sure he's dead. So you hear the phone go quiet, and then you hear a gunshot. And the guy says, OK, now what? . And this is the essential problem with doing failure detection in our world. So, that there is no real way to tell that a server or a component has actually failed. And in the old days, there was. We talked about commodity hardware, and this is really a commodity hardware problem. If I go way back in time to when I was still young, we had techniques like I/O fencing, where we could use hardware to say, OK, that server-- I want that server no longer to be able to communicate with the rest of my cluster. So I want him fenced off. And now I've shot him. I know he's dead. We can't do that anymore. So the essential problem with failure detection is being able to tell that a server has died. So one common way to do that is you listen to a server, and when the server stops responding, you say, well, I think that server might have failed. [30:00] One of the many problems with that is that it could be that the server's fine, and it's actually the network that's failed. Right? So is it him that's failed, or is it me that's failed? really can't tell. And it's just a theoretical thing that you can't avoid, that you will have false positives. You will decide that some server has failed when it really has not. So what can we do about that? Well, we've got a few techniques. And the most common technique that we use for failure detection in general is not to try to detect failure, but to detect liveness. So have a heartbeat protocol. And while I may not be able to reason that a particular server has failed, I can reason that he's alive, that I have a communication path to that server and I'm receiving heartbeats. So heartbeat protocols are super useful. We use them all over the place. The gossip-based protocol that I talked about that we built for S3 is essentially this sort of mechanism. When I stop seeing in my little table about who's in my group, if I haven't received a heartbeat through the epidemic algorithm from some server in a while, I conclude that that server's probably failed. The other technique that we recommend using that should be used is using leasing. rather than locking. So it's a basic computer science idea, programming idea, that if you have some resource that you don't want concurred access to, you can use you establish a lock. on that resource, right? And this works great if you're writing like a Java program, because of what I said earlier. If some object has something locked, then unless you write-- it does happen from time to time. But typically with code, if that object fails, your whole JVM has failed. So you don't have to worry about the lock being kept. Whereas in a distributed system, if I assign a lock to some server, and that server fails, now my resources are unavailable, maybe forever. So a better protocol is to have that server obtain a lease on some resource. And then that server has to reason about this as well. If the server has a lease for 700 milliseconds, And it can't get its work done in 700 milliseconds. It has to know to stop touching that resource. But this is another technique we use to deal with failure detection. So here are the lessons around failure detection. Don't let components go silent. Silence in a distributed system is very, very hard to deal with. Because you can't tell the difference between somebody who's just resting and somebody who's failed. Thank you. The second one is try to get protocols that don't rely on accurate failure detection. The most easy way to deal with this is to not rely on your failure detection being correct. Then you can have more hair trigger failure detection and still get correct results. And finally, like I said, use leases instead of locks. Yeah. The final, actually, primitive that we'll be talking about is workflows. So, workflows, I mean, when I came to Amazon, I mean, I've been building distributed systems like data stores and then built Dynamo and other things. one of these systems, I think it was CloudFront or RDS, when I was building it, we had to start writing, like, workflows to actually provision instances or provision distribution. At that time, the thought of workflows itself reminded me of, like, the old school days of, like, writing people description and all the other things. So--but workflows in general, it's like a very fascinating distributed systems problem. I mean, when you think about it, the core problem is very simple. You need to execute a series of actions asynchronously one after the other. examples of it, these kind of workflows, are constantly running in AWS. When you call create EC2 instances in a VPC, we -- underneath the covers, it triggers a workflow. Same thing is true for RDS instance when you call them, or DynamoDB when you call a create table. So-- What is a workflow? So now let's take an example. What happens when you call, like, create DB instance in an RDS environment? We basically, for a multi-AC, we create EC2 instances in each AC and the volumes in it. And then we actually wait for them to be available. And then we set up the storage system. We set up the file system. We set up replication engines that run between them. We set up monitoring. And there are like 20 other steps that go into it before we actually mark it available, and then you can call describe instance. and then say, hey, now it is available and this is my endpoint. This is the series of workflows actually that happens. How do we build these kind of workflows? Before I get to that, it's imperative because Al explicitly warned me saying that when you start talking about workflows, then people are going to start taking things which are supremely simple to build and then not modeling it as a workflow. So it's always important to... explain what is not a workflow. So things that are easily synchronous and latency sensitive, try not to make them a workflow and make it asynchronous. So there are examples of Synchronous API calls, which should not be modeled using asynchronous workflow. And you should... And the converse is true. You cannot model, for example, something like a create EC2 instance. as an synchronous API call, Whereas underneath it [35:00] really becomes an async workflow. That's why EC2 instance, when you call it, it returns with the response saying creating, and then later you pull when it is available. So-- A popular technique to do workflow is what early days of Amazon used to do. Write a simple Perl script or nowadays it's Python or um... other things, and then you actually execute a series of commands, and continue to run forward. It really works pretty reasonable for, like, simple workflows, where you have, like, one or two steps. But then the problem is, if you have a long running workflow, like the RDS example that I gave, I mean, it really does not work well. essentially, things fail in between. And intermediate steps, actually, once they fail, you don't know where to restart. and you don't know what is the safe state for you to restart. So the way actually we look at this problem is very simple. We actually decompose every workflow into series of computation or activities. and each activity is meant to be, like, completely stateless and independent. And we actually start off with let's say activity one, once it becomes complete, it stores the metadata in a metadata store, something like Dynamo, and then it actually-- the next entity comes up and says, OK, what is my state? Oh, that means I need to execute activity two. and then again writes back and then moves to the next activity and goes, go forth. It's a very simple pattern that we actually repeat over and over again. So, this is the pattern which we commonly use across various AWS services. And some of the key lessons we learned here is, The most critical one I would stress is like idempotency. the activity that you actually build here Let's take activity one. It is considered a safe and reliable workflow if you can execute the activity in a workflow. Once and you get the same response, and a thousand times, you get the same response. If you're not able to build your workflow that way, That means, your workflows can't be rerun. That means you can't deal with failures. That means you really are actually compromising availability. The biggest takeaway I would call out is that build item button activities in your workflow so that you can actually Cartier to build. scalable workflows. And store your intermediate state. Easy way to build item Effectively, store your intermediate state in a metadata store. It can be like Dynamo. so that you know where you left off, so that it is safe for you to actually execute that over and over again. So this kind of complexity, to some extent, is abstracted by, like, design patterns and services like simple workflow. Some of our Amazon services already use them so that they don't have to deal with building all these frameworks. and whatnot. But then we talked about five AWS distributed systems parameters. And it really comes down to what is the underlying problem that is under the cars behind all of it? in In a group membership setting, you need to decide Who is the primary or who is the master in a database? In a metadata store, you need to decide what is the strongly consistent view of a given data. In a workflow, you had to store the data somewhere so that you can drive it item pattern. In a failure detection environment, You need to know if somebody is really actually not alive anymore. So it all comes down to one common problem in a distributed system called consensus. So consensus problem in distributed systems is really simple. It really comes down to a distributed set of processes agreeing on something. And the problem doesn't sound too hard. at the crux of it, it says, hey, this one, computers are programmed to actually just make us I mean, we can tell it what to do. So why is this problem that hard? And that's where actually, this is a favorite interview question for Al. Thank God you did not interview me when I was interviewing Amazon. But this is really coming down to one of the most challenging aspects in distributed system. How do you get a distributed set of servers and processes? that actually run in a global environment to agree on a single value. Right. So agreement in your distributed system really is the fundamental problem. You have multiple servers. And at the end of the day, if you want to build a consistent distributed system, those servers have to agree. You have to have an authoritative value for something. And it turns out that there is a protocol that implements agreement. It's been rediscovered several times, but it's most commonly known as a Paxos protocol invented by Leslie Lamport. The story of it, I think, is fascinating. I only have a couple minutes, so I'm going to gloss over it. The essence of the story is that it was not known back in the '80s, '70s, '80s, [40:00] whether this problem could be solved. That's why it's such a great interview problem, because it sounds so easy. But it's not easy. It's very hard and deep. And Lamport was actually trying to prove that it was impossible. to solve this problem, and while trying to prove it's impossible, he stumbled upon the solution. to the problem. So one of the things that I look at-- I've looked at a lot of systems at Amazon over the years, in various reviews, and so on. And anybody who claims that they have a distributed system that offers consistent results, I'll drill into their system, and I'm always able to classify it into one of three categories. And The first category is a system that has a single point of failure. And often the single point of failure is something like a database. So people can say, well, I've got the system and it's reliable, you know, it's consistent and so on. And the reason it's consistent is everybody looks at the database for the authoritative answer, and that's fine. But it means there's a single point of failure. The second kind of system is one that eventually, at the very bottom, uses Paxos to do the key piece of agreement. to decide on what the distributed system is. So those are two kinds. The third kind of system is systems that are broken. And those are the only three kind I've ever find. And the Paxos at the bottom one is subtle, right? We talked about using DynamoDB as a metadata store. And you could say, well, look, you've got a single point of failure, but DynamoDB is not a single thing. And so if you drill into how DynamoDB works and why there's no single server or network link that can cause a single point of failure-- and drill into how DynamoDB decides who's the master in a storage group and so on, and keep going down, what you'll find at the bottom is Paxos. And that's why I like that solution, because I believe it is resilient to not having a single point of failure. So the lessons learned around consensus is really beware of fuzzy protocols. So beware of people who go into a design review and say, yeah, I've got the system, and I know it's consistent, because I've worked out all the edge cases. because they haven't. And at Amazon, when we run at massive scale, even things that seem extremely unlikely do happen. It's amazing the unlikely things that actually happen in our environment. So make sure that either there's a single point of failure, and you understand that, and you're happy with it. or that Paxos is at the bottom. The second lesson is that Paxos is hard. It's harder than you'd think it is. So Swami and I wrote a system that implements Paxos a few years ago. um And the protocol itself is not that challenging. It's all the stuff that has to go around it to make it really work, to make it perform well, to make sure that you can upgrade, to make sure that when hosts fail, they can be replaced, all this kind of stuff. Getting it right is challenging. So avoid doing it over and over again. That's why in Amazon, as we started seeing so many people wanting like a uniform way to do consensus, then that's when we actually decided, you know what, let's actually, Al and I decided to go write a library. for PAXs, where we modeled the distributed state machine where We use Pax for these processes to agree on what is the state transition that they need to move from, let's say, state A to state B. I mean, this was good. We started using it for things like S3 and various other services, but then at some point, We actually started making every developer to consume this library and then recent through Paxos. That really did not scale well because it fell into the same trap of education. So that's why we actually said, you know what? We can do better. Let's go build PyAccess as a service. So we expose it as a lock primitive. I mean, I'm sure many of you would have heard Google Chubby. So they actually went down the same route, too. So we built a lock service. And people could use it, actually, as a locking mechanism. In reality, it is a leasing mechanism. And then you can actually use it for also group membership and other things. And the final one, actually, it turned out to be is that We evolved from a log service because one of the key things we realized is that consensus as a locking mechanism is not actually the best way. Instead, It is all coming down to you want a transactionally consistent journal, which actually preserves the history of state transition. not just the current state. So this is actually really cool. This is where we're going to end this talk to talk about-- this is sort of the latest distributed systems primitive that we have internally at Amazon.com. And it's the idea of having a transaction journal as a primitive. So not just coming to one agreement, but coming to agreement after agreement and putting those together into a log, or we call it a journal because it has strong ACID properties that I can't talk about in 20 seconds, but is interesting. And we've actually used that. to implement the other primitives that we've talked about in the talk today. This transactional journal also sits at the bottom of Amazon Kinesis. It's how Kinesis stores individual data streams. It sits at the bottom of Amazon DynamoDB Streams, which was announced just a few days ago in a blog post that gives you a consistent journal coming out of DynamoDB. So it's important that it be strongly consistent so you can see every update that you've made [45:00] DynamoDB table, for example. and then feed that into Lambda, as we saw in Werner's keynote today. Hmm. So with that, we will wrap up the talk. So we want you to take three things out of this talk. So one is trying to distribute systems is not a niche problem anymore. Even if you don't know it, each one of you building on top of AWS, you are already becoming a distributed systems developer, whether you like it or not. or whether you took that course in your undergrad or not. The second thing is think about code distributed system primitives that you need to actually use when you're building your application. So-- Preferably, if you would like to actually abstract all these complexity away, start using higher-order services. which actually, Mask all this complexity, things like S3, Dynamo, EC2s, Aurora's and simple workflows and RDS. So with that, feel free to email us if you have any questions. We'll be here to Thank you for staying. We apologize for going one minute and 15 seconds over. We were warned explicitly not to do that, and we did it anyway, so sorry about that. All right, thank you.