I've actually posted on this topic in the past, but I spend so much of my own time thinking about it that I'm going to revisit the question from my "revised and improved" perspective, a year or so down the road.
Context: with the move towards a disaggregated data center model in which we use RDMA or other forms of next-generation direct access to talk to remote memory (perhaps persistent, perhaps not), we find ourselves in a world where the underlying costs and barriers have shifted dramatically relative to the programming style familiar in the past.
Specific example: Consider 2-phase commit, or your favorite consensus protocol, or Paxos. In the recent past, we would program these protocols by having some leader who initiates the protocol and sends out a request to the other participants: "can you commit transaction 71?" or "I vote 1", or "I propose that we place value v into Paxos log slot 22, and this is my 3rd ballot for that slot." Responses eventually come back, and after a round or two of these back-and-forth interactions, the protocol terminates.
In that classic way of thinking, there was a kind of implicit balance in mind between the cost of moving the data (value v in the example above) and the cost of the back-and-forth round-trips. I'm not quite sure how to best express this sense of balance, but what one finds is that the cost of the round-trip actions (the RTT, as we say in the business...) is sort of "reasonable" relative to the bandwidth available for moving the value field, often over TCP connections or UDP.
Today, with new forms of direct remote memory access, talking to remote memory over a technology like RDMA is actually faster than talking to local memory, but only in the sense that RDMA can sustain a far higher bandwidth than local actions like using memcpy (the fastest available copying primitive on a Linux/C computing platform) to move data from one place in memory to another, assuming that the data in question isn't in the L2 cache. As RDMA speeds up, this gap will only get larger. So it is very cheap to move data from machine A to machine B.
In contrast, the RTT for a modern optical Ethernet is surprisingly high, when you consider quite how fast copying can be. We see RTTs in the 1.5us to 2.5us range: quite fast compared to the 1-10ms numbers that were common for protocols running over TCP/UDP/IP, but relatively sluggish if you consider the number of bytes that could have been sent in that time, particularly if you add in the delays for scheduling a thread to notice the request coming in (when A's message arrives on B), or to send the reply (when B's response reaches A).
If A blocks sending while waiting for this RTT to complete, quite a few bytes won't be sent. And as RDMA gets faster (today, 100Gbps, but tomorrow 200, then 400, and 1Tbps is within range now), the amount of missed transmission opportunity gets pretty substantial.
Concurrency feels like the obvious answer, but this instinctive reaction proves to be naive. The theory would be that if A has lots of side by side transactions with B, then while one waits, another can transmit. But that overlooks overheads: concurrency also brings many kinds of costs, and this model is anything but a clear win! Those costs could quickly add up: locking to ensure that the transfers won't interfere with one-another, memory contention on the DRAM chunks where the data lives, various forms of state that might be sitting around while the round-trip interactions are running (threads consume stack space, for example). So concurrency doesn't come for free.
Batching is a second possibility: A could collect a bunch of requests, then send them as a batch (while collecting the next batch), B could respond on the whole series of requests (one by one, but as a batch of responses), and so forth. This amortizes costs in a nice way.
Batching makes sense on a receiver, too. Rather than sending batches and forcing the receiver to use those batch sizes, a sender could send continuously, and the receiver could bite off a chunk of incoming records based on when it happens to be ready to run. So if we have A sending continuously, rather than having A batch 10 items at a time, it could stream steadily to B. B might be ready for its next chunk of input at a moment when there are 11 items available; it treats these as a batch of 11. Then at the next loop, B is perhaps ready for input when 4 new items have turned up: a batch of 4. We still see a benefit of amortized costs, but the batch sizes are variable and determined by when B happens to be ready, rather than fixed and decided by A (the sender).
Derecho works this way.
Now why are we discussing these obvious points? Well, the optimality of Derecho is directly tied to its use of this style of receiver-side batching. The key "thing" about Derecho is that it runs a version of Paxos modified to make decisions as soon as possible, based on the Paxos notion of safety, using receiver-side batches. This allows us to stream an exceptionally high rate of Paxos requests, process them with no unnecessary delays, and amortize all costs over batches of events.
In fact, the value of this method centers on the steady stream of updates. With one update, by itself, classic Paxos is a reasonable choice of protocol. But with a stream of updates, we need to amortize costs for efficiency. The classic protocols run in a greedy way, and cease to be efficient because they miss this opportunity!
So now the question arises: is this a story purely about Derecho, or does the same opportunity transition to other kinds of systems that aren't doing atomic multicast (vertical Paxos) and atomic log updates (classic durable Paxos)? For example, could a distributed file system somehow gain performance by being implemented to use the same sort of pattern? Could a database system be optimized by leveraging this sort of transformation?
And we can pose the problem even more broadly. As a programming question (almost a compilation question), is there a systematic programming methodology here, one that would lead the developer to an optimized solution matched to the underlying cost model mentioned earlier (the cost model in which steady flow works extremely well at high rates and with large data volumes, but RTT looks somewhat costly)? How could one start with a specification of a file system, or a specification of Paxos, and systematically arrive at a solution like Derecho?
I find it fascinating that despite all the work that has been done on stream processing in database systems, there seems to be very little prior work on the kind of protocol optimization I've outlined. The underlying "memory model" is really just an exaggerated NUMA one, with a cache-line memory coherence model, remote memory access, but with unusually high latencies relative to the extremely high bandwidth. By and large, my colleagues in the PL community view the resulting questions as being variations on what they are already used to: they have extensive experience with NUMA programming. Yet here we can see that we actually are after solutions that can be quite different from the classic ones: Derecho doesn't look a lot like Paxos at first glance, and the optimality we achieved emerges from the Paxos protocol transformations that let us optimize for the RDMA environment. So there was something non-trivial happening here, even though it happens over the standard NUMA model.
I don't know if we have PL readers of this blog, but I would love to hear their thoughts, if so!
Showing posts with label 2-phase commit. Show all posts
Showing posts with label 2-phase commit. Show all posts
Wednesday, 7 March 2018
Wednesday, 8 March 2017
The ultimate Paxos (and Atomic Multicast) protocol
Many years ago, probably around 1986, Barbara Simons organized a workshop on replication at Asilomar, a California resort that had an iconic role in early systems research (it took a while, but eventually our community was too large to fit there).
Her idea was to bring people together across areas: theory and practice, and within the practitioners, databases as well as other forms of distributed systems. It was a good idea, and a great workshop.
In Jim Gray's talk, he pointed out that the interaction pattern we associate with the 2-phase commit protocol was seemingly universal, and that perhaps we were wrong to think of 2-phase commit as primarily a database construct. Instead, he then asked, if 2-phase commit is really concerned with something deeper than database transactions, what is this deeper core concept? The essential point of his talk was that the 2-phase pattern seen in 2PC clearly allowed a distributed system to "learn" something. And from this, he suggested, that if we could start to appreciate the minimal "knowledge" required for a distributed system to be correct, we could build a minimal implementation of that protocol and solve the problem once and for all.
A long time has passed. Jim is no longer with us, and we know all about knowledge in distributed systems, and how processes learn. Even so, Jim's question still sometimes comes up. I mentioned this to Idit Keidar today over lunch, and her response was definitive: she convinced me that today, we really do (finally) understand the answer to Jim's question. Her thinking centers on work she published in 2006 with Alex Shraer.
Here's what she explained.
First, she observed, distributed computing is ultimately about just one question: fault-tolerant consensus. For her, Jim had noticed this, but was understanding it as something about the 2PC communication pattern rather than appreciating that the thing that matters more is consensus: moving from a state in which some decision is uncertain to one in which a decision has been reached. As Idit views the question, one can transform consensus into other forms, we can route the messages in all sorts of patterns, but the bottom line is that either we achieve agreement via consensus or we simply aren't building systems that can make logically sound claims about their behavior.
Next, she pointed out, agreement is trivial while failures aren't happening. While a system remains stable, the author of a new piece of information simply needs to multicast it, and this accomplishes consensus. If there might be many authors, you can circulate a token around them either before they send (as in the old Totem and Transis protocols) or after the messages arrive, to assign them a delivery ordering.
And so in Idit's view, the only hard issue is to handle failures. Obviously, in the case of 2PC, particularly back in 1986, the field started out with a somewhat muddled understanding of this aspect: 2PC starts by stating that there is a set of processes that need to achieve agreement, but where does that set come from? In a modern system like Derecho, the set itself is the output of a consensus layer. 2PC uses a crash failure model, but this is one of many models. Back in 1986 people were very focused on models: crash failures, failstop failures, omission to send, omission to receive, timing errors, Byzantine models.
But these days all that really matters is to handle crash failures correctly. Some organizations toy with Byzantine fault-tolerance, but honestly, I've never met anyone who had a service that actually came under a Byzantine attack. Maybe the blockchain people will finally have that experience.
So let's focus on crash failures for a moment. In light of the FLP theorem, we know now that without a perfect failure detector, protocols can't be proved correct: you can show safety, but not liveness. In practice, we solve this by forcing a seemingly faulty process to leave the system and then, if you want, it can rejoin.
So failure becomes a purely behavioral abstraction: if the majority of the system deems some process to be worthy of excluding, for whatever arbitrary reason it desires, than out goes the offending process, end of story.
Where did the majority constraint come from? The role of the majority restriction is to prevent logical partitioning.
So, we end up with a rather dynamic form of membership: the system defines its own membership, excluding processes that seem faulty, and makes progress as long as it can maintain a dynamic form of majority. To whit: at any point in time, some epoch defines the composition of the system. In order to move to a new epoch, the systems needs agreement by the majority of whoever is in the active epoch.
So here's where all of this leads: Derecho is a concrete implementation of this new-age perspective on Jim's question. Indeed, it is the ultimate story in the sense that the system is optimal in many different ways.
To appreciate this, you'll need to read the Derecho papers, but in a nutshell, the system maps consensus onto RDMA hardware in an exceptionally efficient way. But the protocol itself runs consensus on the configuration of each epoch, and then uses a cheaper consensus protocol within an epoch (one that can assume membership is stable and that failures won't occur), leaving a very clean realization of distributed computing.
Indeed, Derecho is a constructive lower bound in every interesting dimension. It is an optimal solution to the problem of distributed computing, using consensus-based methods.
Why do I make this claim? Well, first, during a given epoch, the system is as quick to deliver messages as is possible: one can prove that any system that delivers messages with fewer "exchanges of information" between its processes is either incorrect, or at last at risk of needing to stop because of some single fault.
Next, one can show that Derecho's agreement on the state of each membership epoch is optimal. Here, Derecho makes use of an all-to-all pattern of information exchange, and I asked Idit if she thought the protocol could be improved. Idit pointed again to her 2006 papers with Alex. Without prior knowledge of which processes failed, and how many failed, she explained, this pattern of information exchange is the quickest way to reach agreement on the membership of the next epoch.
Finally, we can show that Derecho makes progress with a failure model called <>P: eventually perfect failure detection. Idit explained to me that in the past, people actually thought it might make sense to focus on progress with weaker detection models, like <>W, but that if you do so, you either end up with a fault model equivalent to <>P, or you end up with slower agreement protocols that look much more like Byzantine agreement. So, for the style of quick progress Derecho is after, she explains, <>P is the right goal. And Derecho is live with <>P, provided that no more than a minority of processes fail in any epoch. Which again, is the best one can do.
Now, Idit is a theory person, but it is interesting for me as a practitioner to also think about practicalities. As the old adage goes: "In theory, theory and practice are the same, but in practice, they differ."
As it happens, Derecho is optimal in a communications-engineering (networking) sense.
Given that reliable networks always have a one-to-one acknowledgement based layer, reliable multicast over a tree is an optimal data dissemination pattern: if you try and disseminate multicasts over an unreliable 1-N protocol, the cost of detecting lost packets and resending them will be very high compared to a tree of unicast transfers. (Perhaps optical networks with optically aggregated acknowledgements could offer a slight hardware speedup, but even this isn't clear, since the optical aggregator would itself be a tree).
Now if you happen to be a cloud computing engineer, and read the above, what will jump to mind is heavy-tailed behaviors and multi-tenancy: Derecho protocols sometimes relay data, so if a relayer is very slow, everyone waits. Paxos classically would avoid this using quorums: the system doesn't wait for the slowest process. So how can I claim that Derecho is optimal in a practical sense if it doesn't use quorums?
There are a few answers. A long-winded one would talk about work Fernando Pedone and his student, Parissa Jallali, did while visiting my group a few years ago. Basically, they studied quorum behaviors in Paxos and discovered that while Paxos can briefly "outrun" a slow process, eventually work piles up and either flow-control causes the protocol to pause, or a shifting pattern of just who is the slow process switches the slow guy into the quorum and some previous quorum member becomes slow. Either way, Paxos basically halts until everyone catches up and is back in sync. So quorum patterns do not evade the disruption caused by heavy tailed behaviors.
Conversely, offloading the protocol into hardware actually can eliminate that issue, because the hardware is dedicated: the network spends 100% of its time communicating, so if you can describe a pattern of communication, then let it rip, the network is the ideal engine for moving data. As it happens, Derecho generates deterministic data transfer schedules, hence given adequately programmable NICs we can hand the entire sequence of block transfers to the NIC. So we can even make "optimal" use of the network, and since a NIC never sleeps or pauses, quorum behaviors aren't needed even if end-applications sometimes are a bit slow.
So a road that for me started around when Jim asked his question about 2PC seems to have reached its end: Derecho implements the ultimate Paxos protocols for atomic multicast (often called vertical Paxos) and for persisted memory (classic Paxos). We could add an optimistic early delivery protocol with a flush, too, as in Isis and Vsync, but we decided to keep the system simple and omitted it: most people who would use that feature probably just want raw RDMC from the Derecho API, and this we do offer.
And so the Paxos problem is solved. And you know what? Its about time! Idit feels that it was solved back in 2006, actually. As for me, well, until I can write an application using the ultimate protocol, the problem is open. But today, I finally can. (I don't mind at all that Derecho employs a protocol that is actually extremely similar to our first Isis protocols from 1985.)
So should we all pack our bags and go home?
Not quite yet. First, there are other forms of distributed consistency, like convergent (gossip) protocols, self-stabilization, and of course, Byzantine Agreement. It would be nice to see how those fit into this picture and whether there can be a single integrated story that combines all the elements.
A second issue is the engineering complexity of modern platforms. I'll write a whole blog posting on this sometime soon, but suffice it to say that in a data center with physical topology (racks, switches, TOR switches, failure-independence domains...), GPU clusters, NetFPGA accelerators, Intel SGX protection enclaves... it just isn't obvious how to write code for such environments. Derecho is just part of the answer, and not the whole story.
Then beyond all of this are dimensions we have yet to tackle in Derecho itself. For example, even if Derecho is the ultimate data center protocol, is it also the ultimate WAN version? As it happens, I suspect that this may be true too, but more attention to the question will be needed. Anyhow, until we have it running, I won't believe the story even if I figure it out "in theory". After all, in theory, theory and practice are the same... but in practice, they are enormously different.
So I wouldn't despair: very likely we are finally at the end of the road for Paxos, but it certainly isn't the end of the road for distributed systems. Watch this space: I can promise plenty of interesting new questions, and new answers, in years to come.
Her idea was to bring people together across areas: theory and practice, and within the practitioners, databases as well as other forms of distributed systems. It was a good idea, and a great workshop.
In Jim Gray's talk, he pointed out that the interaction pattern we associate with the 2-phase commit protocol was seemingly universal, and that perhaps we were wrong to think of 2-phase commit as primarily a database construct. Instead, he then asked, if 2-phase commit is really concerned with something deeper than database transactions, what is this deeper core concept? The essential point of his talk was that the 2-phase pattern seen in 2PC clearly allowed a distributed system to "learn" something. And from this, he suggested, that if we could start to appreciate the minimal "knowledge" required for a distributed system to be correct, we could build a minimal implementation of that protocol and solve the problem once and for all.
A long time has passed. Jim is no longer with us, and we know all about knowledge in distributed systems, and how processes learn. Even so, Jim's question still sometimes comes up. I mentioned this to Idit Keidar today over lunch, and her response was definitive: she convinced me that today, we really do (finally) understand the answer to Jim's question. Her thinking centers on work she published in 2006 with Alex Shraer.
Here's what she explained.
First, she observed, distributed computing is ultimately about just one question: fault-tolerant consensus. For her, Jim had noticed this, but was understanding it as something about the 2PC communication pattern rather than appreciating that the thing that matters more is consensus: moving from a state in which some decision is uncertain to one in which a decision has been reached. As Idit views the question, one can transform consensus into other forms, we can route the messages in all sorts of patterns, but the bottom line is that either we achieve agreement via consensus or we simply aren't building systems that can make logically sound claims about their behavior.
Next, she pointed out, agreement is trivial while failures aren't happening. While a system remains stable, the author of a new piece of information simply needs to multicast it, and this accomplishes consensus. If there might be many authors, you can circulate a token around them either before they send (as in the old Totem and Transis protocols) or after the messages arrive, to assign them a delivery ordering.
And so in Idit's view, the only hard issue is to handle failures. Obviously, in the case of 2PC, particularly back in 1986, the field started out with a somewhat muddled understanding of this aspect: 2PC starts by stating that there is a set of processes that need to achieve agreement, but where does that set come from? In a modern system like Derecho, the set itself is the output of a consensus layer. 2PC uses a crash failure model, but this is one of many models. Back in 1986 people were very focused on models: crash failures, failstop failures, omission to send, omission to receive, timing errors, Byzantine models.
But these days all that really matters is to handle crash failures correctly. Some organizations toy with Byzantine fault-tolerance, but honestly, I've never met anyone who had a service that actually came under a Byzantine attack. Maybe the blockchain people will finally have that experience.
So let's focus on crash failures for a moment. In light of the FLP theorem, we know now that without a perfect failure detector, protocols can't be proved correct: you can show safety, but not liveness. In practice, we solve this by forcing a seemingly faulty process to leave the system and then, if you want, it can rejoin.
So failure becomes a purely behavioral abstraction: if the majority of the system deems some process to be worthy of excluding, for whatever arbitrary reason it desires, than out goes the offending process, end of story.
Where did the majority constraint come from? The role of the majority restriction is to prevent logical partitioning.
So, we end up with a rather dynamic form of membership: the system defines its own membership, excluding processes that seem faulty, and makes progress as long as it can maintain a dynamic form of majority. To whit: at any point in time, some epoch defines the composition of the system. In order to move to a new epoch, the systems needs agreement by the majority of whoever is in the active epoch.
So here's where all of this leads: Derecho is a concrete implementation of this new-age perspective on Jim's question. Indeed, it is the ultimate story in the sense that the system is optimal in many different ways.
To appreciate this, you'll need to read the Derecho papers, but in a nutshell, the system maps consensus onto RDMA hardware in an exceptionally efficient way. But the protocol itself runs consensus on the configuration of each epoch, and then uses a cheaper consensus protocol within an epoch (one that can assume membership is stable and that failures won't occur), leaving a very clean realization of distributed computing.
Indeed, Derecho is a constructive lower bound in every interesting dimension. It is an optimal solution to the problem of distributed computing, using consensus-based methods.
Why do I make this claim? Well, first, during a given epoch, the system is as quick to deliver messages as is possible: one can prove that any system that delivers messages with fewer "exchanges of information" between its processes is either incorrect, or at last at risk of needing to stop because of some single fault.
Next, one can show that Derecho's agreement on the state of each membership epoch is optimal. Here, Derecho makes use of an all-to-all pattern of information exchange, and I asked Idit if she thought the protocol could be improved. Idit pointed again to her 2006 papers with Alex. Without prior knowledge of which processes failed, and how many failed, she explained, this pattern of information exchange is the quickest way to reach agreement on the membership of the next epoch.
Finally, we can show that Derecho makes progress with a failure model called <>P: eventually perfect failure detection. Idit explained to me that in the past, people actually thought it might make sense to focus on progress with weaker detection models, like <>W, but that if you do so, you either end up with a fault model equivalent to <>P, or you end up with slower agreement protocols that look much more like Byzantine agreement. So, for the style of quick progress Derecho is after, she explains, <>P is the right goal. And Derecho is live with <>P, provided that no more than a minority of processes fail in any epoch. Which again, is the best one can do.
Now, Idit is a theory person, but it is interesting for me as a practitioner to also think about practicalities. As the old adage goes: "In theory, theory and practice are the same, but in practice, they differ."
As it happens, Derecho is optimal in a communications-engineering (networking) sense.
Given that reliable networks always have a one-to-one acknowledgement based layer, reliable multicast over a tree is an optimal data dissemination pattern: if you try and disseminate multicasts over an unreliable 1-N protocol, the cost of detecting lost packets and resending them will be very high compared to a tree of unicast transfers. (Perhaps optical networks with optically aggregated acknowledgements could offer a slight hardware speedup, but even this isn't clear, since the optical aggregator would itself be a tree).
Now if you happen to be a cloud computing engineer, and read the above, what will jump to mind is heavy-tailed behaviors and multi-tenancy: Derecho protocols sometimes relay data, so if a relayer is very slow, everyone waits. Paxos classically would avoid this using quorums: the system doesn't wait for the slowest process. So how can I claim that Derecho is optimal in a practical sense if it doesn't use quorums?
There are a few answers. A long-winded one would talk about work Fernando Pedone and his student, Parissa Jallali, did while visiting my group a few years ago. Basically, they studied quorum behaviors in Paxos and discovered that while Paxos can briefly "outrun" a slow process, eventually work piles up and either flow-control causes the protocol to pause, or a shifting pattern of just who is the slow process switches the slow guy into the quorum and some previous quorum member becomes slow. Either way, Paxos basically halts until everyone catches up and is back in sync. So quorum patterns do not evade the disruption caused by heavy tailed behaviors.
Conversely, offloading the protocol into hardware actually can eliminate that issue, because the hardware is dedicated: the network spends 100% of its time communicating, so if you can describe a pattern of communication, then let it rip, the network is the ideal engine for moving data. As it happens, Derecho generates deterministic data transfer schedules, hence given adequately programmable NICs we can hand the entire sequence of block transfers to the NIC. So we can even make "optimal" use of the network, and since a NIC never sleeps or pauses, quorum behaviors aren't needed even if end-applications sometimes are a bit slow.
So a road that for me started around when Jim asked his question about 2PC seems to have reached its end: Derecho implements the ultimate Paxos protocols for atomic multicast (often called vertical Paxos) and for persisted memory (classic Paxos). We could add an optimistic early delivery protocol with a flush, too, as in Isis and Vsync, but we decided to keep the system simple and omitted it: most people who would use that feature probably just want raw RDMC from the Derecho API, and this we do offer.
And so the Paxos problem is solved. And you know what? Its about time! Idit feels that it was solved back in 2006, actually. As for me, well, until I can write an application using the ultimate protocol, the problem is open. But today, I finally can. (I don't mind at all that Derecho employs a protocol that is actually extremely similar to our first Isis protocols from 1985.)
So should we all pack our bags and go home?
Not quite yet. First, there are other forms of distributed consistency, like convergent (gossip) protocols, self-stabilization, and of course, Byzantine Agreement. It would be nice to see how those fit into this picture and whether there can be a single integrated story that combines all the elements.
A second issue is the engineering complexity of modern platforms. I'll write a whole blog posting on this sometime soon, but suffice it to say that in a data center with physical topology (racks, switches, TOR switches, failure-independence domains...), GPU clusters, NetFPGA accelerators, Intel SGX protection enclaves... it just isn't obvious how to write code for such environments. Derecho is just part of the answer, and not the whole story.
Then beyond all of this are dimensions we have yet to tackle in Derecho itself. For example, even if Derecho is the ultimate data center protocol, is it also the ultimate WAN version? As it happens, I suspect that this may be true too, but more attention to the question will be needed. Anyhow, until we have it running, I won't believe the story even if I figure it out "in theory". After all, in theory, theory and practice are the same... but in practice, they are enormously different.
So I wouldn't despair: very likely we are finally at the end of the road for Paxos, but it certainly isn't the end of the road for distributed systems. Watch this space: I can promise plenty of interesting new questions, and new answers, in years to come.
Subscribe to:
Posts (Atom)