the morning paper

A comprehensive study of Convergent and Commutative Replicated Data Types – Shapiro et al. 2011

This is the third of five Desert Island Paper choices from Jonas Bonér, and it continues the theme of avoiding coordination overhead in a principled manner whenever you can. As we saw yesterday, there are trade-offs between consistency, failure tolerance, latency tolerance, and performance. Let us not confuse the family of eventual consistency approaches with an ill-defined ‘approximate’ consistency though:

[Eventual consistency] performs well (as the consensus bottleneck has been moved off the critical path), and the weaker consistency is considered acceptable for some classes of applications. However, reconciliation is generally complex. There is little theoretical guidance on how to design a correct optimistic system, and ad-hoc approaches have proven brittle and error-prone.

This paper introduces the concept of a CRDT, a “simple, theoretically sound approach to eventual consistency.” Let’s adddress one of the pressing distributed systems questions of our time right here: “what does CRDT stand for?” We’ve seen over the last couple of weeks that there are two fundamental approaches to replication: you can execute operations at a primary and replicate the resulting state, or you can replicate the operations themselves. If you’re replicating state, then given some convergence rules for state, you can create Convergent Replicated Data Types. If you’re replicating operations, then given operations carefully designed to commute , you can create Commutative Replicated Data Types. Conveniently both ‘convergent’ and ‘commutative’ begin with C, so we can call both of these CRDTs. In both cases, the higher order goal is to avoid the need for coordination by ensuring that actions taken independently can’t conflict with each other (and thus can be composed at a later point in time). Thus we might also call them Conflict-free Replicated Data Types.

Think of it a bit like this: early on languages gave us standard data type implementations for set, list, map, and so on. Then we saw the introduction of concurrent versions of collections and related data types. With CRDTs, we are seeing the birth of distributed collections and related data types. Eventually any self-respecting language/framework will come with a distributed collections library – Riak already supports CRDTs and Jonas has an Akka CRDT library in github at least. As you read through the paper, it’s tempting to think “oh, these are pretty straightforward to implement,” but pay attention to the section on garbage collection – a bit like we saw with Edelweiss, making production implementations with state that doesn’t grow unbounded makes things more difficult.

Since, by design, a CRDT does not use consensus, the approach has strong limitations; nonetheless, some interesting and non-trivial CRDTs are known to exist.

Assume that some number of replicas of an object (e.g .a Set) are distributed. We’d like these to eventually converge to the same state, or more precisely, we’d like all query operations on the object to return the same result at each replica. For any two replicas i and j, this requires both a safety and a liveness condition:

• Safety: if the causal history of i and j is the same, then the abstract state of i and j is equivalent.
• Liveness: if some event e is in the causal history of i then it will eventually be in the causal history of j.

If we have this pairwise eventual convergence for any i and j, then this implies that any non-empty subset of replica objects will converge so long as all replicas eventually receive all updates.

State-based CRDTs

The terminology can seem intimidating, but the core idea is actually very simple. If you understand max(x,y) you can understand how state-based CRDTs work. Let’s suppose our state is a simple integer value. Given two values 4 and 6, then the max is 6. We could also describe 6 as the least upper bound of the two values: the smallest value such that 4 and 6 are both ≤ to it. Of course, the state values we want to compose won’t always be integers, but so long as we can define a meaningful least upper bound (LUB) function over the state, we can create a CRDT. You might hear the term join semilattice being thrown around. This simply means a set of values with an LUB-based partial order function defined over them. (Such as the set of integers, and max).

Take an object whose values come from such a semilattice, and define the merge operation for state values to be its least upper bound function. If the values of such an object only get larger (as defined by the least upper bound function) – a monotonic semilattice, then the type is a CRDT. Replicas of such a type will eventually converge.

Operation-based CRDTs

For an operation-based object, we assume a delivery channel (such as TCP) that can deliver updates in the deliver order specified by the data type (e.g. causal delivery). Operations not covered by this order are said to be concurrent. If all such concurrent operations commute, then all execution orders consistent with the delivery order are equivalent, and all replicas will converge to the same state. As an example, addition and subtraction commute (+7, -5 gives the same result as -5, +7).

Interestingly, it is always possible to emulate a state-based object using the operation-based approach, and vice-versa.

Example CRDTs

On the surface, it maybe seems a little underwhelming. The clever part is that if these rules are all we’ve got to work with, how can we design data types that stick to the constraints and yet still do meaningful things? Because if we can do that, we get all the nice convergent properties. To a man with a hammer, everything looks like a nail. We have a hammer, it’s time to find some nails…

Starting with the humble counter, an operation based counter is straightforward since addition and subtraction commute. The state-based counter highlights some of the interesting issues that arise in designing CRDTs though. Let’s start with a counter that only increments: if two independent replicas both increment the counter (from 0 to 1), and then we merge with max, we’ll end up with 1, not the desired 2. So let’s keep a more complex state structure modeled after a vector clock with one entry in the vector for each replica, increment at a given replica increments its counter in the vector. Now merge can take the maximum of each entry, and the counter value is the sum of all entries…

It is not straightforward to support decrement with the previous representation, because this operation would violate monotonicity of the semilattice. Furthermore, since merge is a max operation, decrement would have no effect.

But… we can solve that by keeping two counters, one for the number of increments, and one for the number of decrements. (The authors call this a PN-counter). Having a non-negative counter (e.g. to count the remaining quantity of some asset) turns out to be hard because ‘non-negative’ is a global invariant you can’t calculate locally. You can enforce the rule locally at each replica (you can’t decrement more than you increment) which will of course ensure the global property, but may be too restrictive.

Sadly, the remaining alternative is to synchronise. This might be only occasionally, e.g., by reserving in advance the right to originate a given number of decrements, as in escrow transactions.

Now that you’ve got an idea of what’s involved in designing a CRDT, let’s take a whistlestop tour through some of the other CRDTs defined in the paper:

• Last-Writer-Wins register (a register is a cell that can store an object or value) – merge is based on the timestamp
• Multi-value register – with merge based on a version vector
• A Grow-only Set (supports add and lookup). This turns out to be a useful building block for higher types.
• A 2P-Set (two-phase set), in which an item can be added and optionally removed, but never added again thereafter.
• • A U-Set, (unique set). Simplified variant of a 2P-Set under the assumption that ‘each element to be added is unique’. Which confused me on the first several readings – because by definition every element in a set is unique! What the authors seem to be capturing here is that the element to be added is not drawn from some a priori know fixed set of values, but instead is ‘created’ at the point of addition, in such a way that the same element can never be created again, nor can it be independently created at another replica. For example, suppose values are drawn from the set of all UUIDs, and replicas generate and then add UUIDs to the U-Set…
• A Last-Writer-Wins element Set, which keeps an add-set and a remove-set, with timestamped entries
• A PN-Set which keeps a counter for each element (has the interesting property that the counter can go negative, in which circumstance adding an element does not make it a set member…).
• An Observed-Remove Set:

The preceding Set constructs have practical applications, but are somewhat counter-intuitive. In 2P-Set, a removed element can never be added again; in LWW-Set the outcome of concurrent updates depends on opaque details of how timestamps are allocated. We present here the Observed-Removed Set (OR-Set), which supports adding and removing elements and is easily understandable. The outcome of a sequence of adds and removes depends only on its causal history and conforms to the sequential specification of a set. In the case of concurrent add and remove of the same element, add has precedence (in contrast to 2P-Set).

• A 2P2P-Graph (which is the combination of two 2P-Sets for vertices and edges).
• An add-only monotonic DAG (an edge may be added only if it is oriented in the same direction as an existing path).
• An add-and-remove partial order data type
• A couple of data types supporting collaborative text editing.

Shopping Carts Again

In Monday’s paper Alvaro et al. showed us how to reduce the amount of coordination required in a shopping cart using a CALM analysis in Bloom. Shapiro et al. pull off the same trick by modeling the shopping cart using CRDTs.

We define a shopping cart data type as a map from an ISBN number (a unique number representing the book edition) to an integer representing the number of units of the book the user wants to buy. Any of the Set abstractions presented earlier extends readily to a Map; we choose to extend OR-set as it minimises anomalies. An element is a (key, value) pair; concretely the key is a book ISBN (a unique product identifier), and the value is a number of copies.

Going one stage further, we can model a bookstore’s worth of shopping carts:

Our e-commerce bookstore maintains the following information. Each user account has a separate OR-Cart. Assuming accounts are uniquely identified, the mapping from user to OR-Cart can be maintained by a U-Map, derived from U-Set in the obvious way. The shopping cart is created when the account is first created, and removed when it is deleted from the system.

In Amazon’s multi-version approach used with Dynamo under failures with concurrent updates, version branching can occur. Added items are never lost, but a deleted item may resurface.

This (CRDT based-)design remains simple and does not incur the remove anomaly reported for Dynamo, and does not bear the cost of the version vector needed by Dynamo’s MV-Register approach.

A note on CRDTs and CALM

Alvaro et al.’s so-called CALM approach ensures eventual consistency by enforcing a monotonic logic. This is somewhat similar to our rule for CvRDTs, that every update or merge operation move forward in the monotonic semilattice. Their Bloom domain-specific language comes with a static analysis tool that analyses program flow and identifies non-monotonicity points, which require synchronization. This approach encourages programmers to write monotonic programs and makes them aware of synchronization requirements. Monotonic logic is more restrictive than our monotonic semilattice. Thus, Bloom does not support remove without synchronisation.

Consistency analysis in Bloom: a CALM and collected approach – Alvaro et al. 2011

This week I’m delighted to bring you another edition of Desert Island Papers, featuring Jonas Bonér. And it seems fitting that Jonas’ first choice is a paper by our previous Desert Island Paper guest, Peter Alvaro.

There are several big ideas in this paper: first, the introduction of the CALM principle for reasoning about distributed system behaviour; second, a declarative language called Bloom that encourages CALM programming and is well-suited to the inherent characteristics of distribution; and third, practical guidance and tools for developing software in this manner.

We show that we can bring that theory to bear on the practice of software development via “disorderly” programming patterns, complemented with automatic analysis techniques for identifying and managing a program’s points of order in a principled way.

If you’re interested in digging deeper into the theoretical underpinnings of Bloom, you might want to check out Joe Hellerstein’s ‘The Declarative Imperative’ paper. Also, don’t forget to read about Peter Alvaro’s follow-on work with Edelweiss.

Staying CALM in the face of uncertainty

The challenges of distribution—concurrency and asynchrony, performance variability, and partial failure—often translate into tricky data management challenges regarding task coordination and data consistency…. There are two main bodies of work to guide programmers through these issues. The first is the “ACID” foundation of distributed transactions, grounded in the theory of serializable read/write schedules and consensus protocols like Paxos and Two-Phase Commit. […] The second point of reference is a long tradition of research and system development that uses application-specific reasoning to tolerate “loose” consistency arising from flexible ordering of reads, writes and messages.

The latter approach can give better availability and/or lower latency but “it is typically unclear what guarantees are provided by systems built in this style. ” Temporal nondeterminism (i.e., not knowing when things are going to happen) is at the root of a lot of the difficulties. We can be eventually consistent however if we have order independence (tolerance of temporal nondetermism). Declarative languages based on sets tend to have this property, and the theory of relational databases and logic programming helps us to reason about them.

Monotonic programs—e.g., programs expressible via selection, projection and join (even with recursion)—can be implemented by streaming algorithms that incrementally produce output elements as they receive input elements. The final order or contents of the input will never cause any earlier output to be “revoked” once it has been generated. Non-monotonic programs—e.g., those that contain aggregation or negation operations—can only be implemented correctly via blocking algorithms that do not produce any output until they have received all tuples in logical partitions of an input set.

Monotonic programs are therefore easy to distribute and can tolerate message reordering and delays. “By contrast, even simple non-monotonic tasks like counting are difficult in distributed systems.”

As a mnemonic, we say that counting requires waiting in a distributed system: in general, a complete count of distributed data must wait for all its inputs, including stragglers, before producing the correct output. “Waiting” is specified in a program via coordination logic (Paxos, 2PC, …).

As we’ve seen over the last two weeks, distributed consensus also involves counting (to ensure a quorum). Thus we can also say ‘waiting requires counting.’

And here comes the big idea:

Our observations about waiting and counting illustrate the crux of what we call the CALM principle: the tight relationship between Consistency And Logical Monotonicity. Monotonic programs guarantee eventual consistency under any interleaving of delivery and computation. By contrast, non-monotonicity—the property that adding an element to an input set may revoke a previously valid element of an output set—requires coordination schemes that “wait” until inputs can be guaranteed to be complete.

We’d like to minimize the amount of coordination (for latency and availability reasons). By building the program on top of a logic language we can develop checks for distributed consistency since conservative tests for monotonicity are well understood in that domain.

In cases where an analysis cannot guarantee monotonicity of a whole program, it can instead provide a conservative assessment of the points in the program where coordination may be required to ensure consistency.

If all this sounds a bit daunting, don’t worry. The ideas can be embodied in a 2,400 line Ruby DSL with surprising power.

Keep CALM and code on

von Neumann architectures bring with them a legacy of implicit ordering assumptions…

Traditional imperative programming grew out of these pervasive assumptions about order. Therefore, it is no surprise that popular imperative languages are a bad match to parallel and distributed platforms, which make few guarantees about order of execution and communication. By contrast, set-oriented approaches like SQL and batch dataflow approaches like MapReduce translate better to architectures with loose control over ordering. Bloom is designed in the tradition of programming styles that are “disorderly” by nature. State is captured in unordered sets. Computation is expressed in logic: an unordered set of declarative rules, each consisting of an unordered conjunction of predicates.

Bloom programs comprise of a set of local collections (state), and a set of declarative statements concerning those collections.

Bloom statements are defined with respect to atomic “timesteps,” which can be implemented via successive rounds of evaluation. In each timestep, certain “ground facts” exist in collections due to persistence or the arrival of messages from outside agents (e.g., the network or system clock). The statements in a Bloom program specify the derivation of additional facts, which can be declared to exist either in the current timestep, at the very next timestep, or at some non-deterministic time in the future at a remote node.

Bloom is side-effect free and has no mutable state. Collections can be one of five basic types, and statements follow a simple ‘lhs rhs’ format. The collection types are:

• table – a collection that persists across timesteps
• scratch – a collection whose contents last for only a single timestep
• channel – a scratch collection with a special location specifier attribute. Tuples ‘appear’ at the network address specified by this location specifier
• periodic – a scratch collection in which tuples ‘appear’ approximately every period seconds with a unique id and the current wallclock time
• interface – a scratch collection especiallly designated as an interface point between modules

And the operations are:

• scratch = rhs (the contents of scratch are determined by the rhs for this timestep)
• table or scratch <= rhs (lhs includes the contents of rhs in the current timestep)
• table or scratch <+ rhs (lhs will include the contents of rhs in the next timestep)
• table <- rhs (lhs will not include tuples in rhs in the next timestep)
• channel <~ rhs (tuples in rhs will appear in the remote lhs at some point in the future)

This should be enough information for you to get a good impression of how the reliable unicast messaging program below works. Please refer to the full paper for a worked key-value store example including an abstract specification of a store and both single node and distributed implementations.

    module DeliveryProtocol
        def state 
            interface input, :pipe_in, 
                ['dst','src','ident'],['payload']
            interface output, :pipe_sent,
                ['dst','src','ident'],['payload']
        end
    end 
      
    module ReliableDelivery include DeliveryProtocol
      
      def state
          channel :data_chan, ['@dst','src','ident'],['payload']
          channel :ack_chan, ['@src','dst','ident']
          table :send_buf, ['dst','src','ident'],['payload']
          periodic :timer, 10
      end
      
      declare
      def send_packet
          send_buf <= pipe_in
          data_chan <~ pipe_in
      end
      
      declare
      def timer_retry
          data_chan <~ join([send_buf,timer]).map{|p,t| p}
      end 
      
      declare
      def send_ack
          ack_chan <~ data_chan.map{|p| [p.src, p.dst, p.ident] }
      end
      
      declare
      def recv_ack
          got_ack = join [ack_chan, send_buf], 
                         [ack_chan.ident, send_buf.ident]
          pipe_sent <= got_ack.map{|a, sb| sb}
          send_buf <- got_ack.map{|a, sb| sb}
      end
    
    end

(See the aforementioned Edelweiss paper for a way to make this program even simpler).

Thinking CALM thoughts

A Bloom program may be viewed as a dataflow graph with external input interfaces as sources, external output interfaces as sinks, collections as internal nodes, and rules as edges. This graph represents the dependencies between the collections in a program and is generated automatically by the Bud interpreter.

Generating such a graph makes it easy to visualise a program, and especially to see the points where coordination is required due to non-monotonicity. (Of course, it’s the fundamental properties of the logic-based language that enables this kind of analysis). This is turn helps you to reason about your design, and perhaps to choose alternatives that reduce the amount of coordination needed. A worked shopping cart example shows these ideas in action. The first alternative deletes items from the shopping cart in response to a delete request (which seems like a good idea on the surface!). But the second alternative simply accumulates update requests (adding and removing items) in a monotonically increasing set. This set is ‘summed up’ only at checkout. Instead of requiring coordination on every cart action, now we only require it on checkout.

Strictly monotonic programs are rare in practice, so adding some amount of coordination is often required to ensure consistency. In this running example we studied two candidate implementations of a simple distributed application with the aid of our program analysis. Both programs have points of order, but the analysis tool helped us reason about their relative coordination costs. Deciding that the disorderly approach is “better” required us to apply domain knowledge: checkout is a coarser-grained coordination point than cart actions and their replication.

If adding additional coordination is undesirable, Bloom’s ‘point-of-order’ analysis can help programmers figure out where they need to take appropriate action to tolerate inconsistency. Helland and Campbell’s “Building on Quicksand” paper is cited as a model from which we may draw inspiration (definitely one I’ll cover on The Morning Paper sometime soon). This introduces the notions of memories, guesses, and apologies.

Most of these patterns can be implemented as automatic program rewrites. We envision building a system that facilitates running low-latency, “guess”-driven decision making in the foreground, and expensive but consistent logic as a background process. When the background process detects an inconsistency in the results produced by the foreground system (e.g., because a “guess” turns out to be mistaken), it can then take corrective action by generating an “apology.” Importantly, both of these subsystems are implementations of the same high-level design, except with different consistency and coordination requirements; hence, it should be possible to synthesize both variants of the program from the same source code. Throughout this process—making calculated “guesses,” storing appropriate “memories,” and generating the necessary “apologies”—we see significant opportunities to build scaffolding and tool support to lighten the burden on the programmer.

Raft Refloated: Do we have consenus? – Howard et al. 2015

This is part ten of a ten-part series on consensus and replication.

We’re nearing the end of this journey after looking at Viewstamped Replication (and VRR), Paxos, ZooKeeper’s atomic broadcast, and Raft. Not that we’ve exhausted all the literature on these topics – far from it! We did manage to exhaust my brain though :). These are hard papers to read critically, and difficult to provide concise summaries of – every little detail is often crucial to correct operation. Of course one of the main points of Raft is to reduce this cognitive overload, and one of goals of Howard et al. is to reproduce the Raft work and find out if this is really true.

Hopefully you’ve got a feel for how these algorithms work and the basic ideas they share in common. You can also learn the basic ideas of how an internal combustion engine works. But would you therefore decide it’s a good idea to build your own car engine? There’s a big gap between the theory of how an internal combustion engine works, and the practice of building a modern car engine. One of the themes that comes out through these papers is that building production quality consensus engines is hard. And those ‘obvious’ performance optimisations you’re tempted to slip in along the way are almost certainly not a good idea (unless you verify them with the same degree of rigour that the original protocols were developed with). Bugs can be very subtle and only occur in deep system traces with multiple levels of failures.

Consensus is at the very core of distributed systems design, and bad things can happen when it goes wrong. In the debate that often rages about whether software engineering can really justify the ‘engineering’ tag, this is one case where true engineering discipline is required. You really want to be using an algorithm that has been formally modeled, with proofs of its important properties (as Raft was modeled in TLA+). Any subsequent optimisations you’re tempted to make need to be validated against this model – it’s all too easy to make an ‘innocent’ change and find out you’ve broken a subtle assumption somewhere along the line. Model checkers can explore permissible system traces to flush out deep and subtle bugs. And then you need to instrument your actual implementation to ensure that it faithfully follows the modeled system, and to catch any problems that occur in the real world. Alternatively you could use a consensus library that meets all these criteria, and plug in your state machine on top…

In Raft Refloated Howard et al. demonstrate just this kind of rigour. Here we find an independent implementation of Raft to assess how easy it is to understand and how complete the original specification was; a full distributed systems simulator for reproducing performance results and exploring scenarios; and a formal model in Statecall Policy Language (SPL) used to validate over 10,000 traces of the system. The source code is all available under the MIT license too:

Our source code is available as open-source software under a MIT license at https://github.com/heidi-ann/ocaml-raft with tag v1.0, and can be installed via the OPAM package manager as raft-sim.1.0. The datasets used are also available at: https://github.com/heidi-ann/ocaml-raft-data, also tagged as v1.0.

The paper includes a nice summary of the Raft protocol, but we can skip that having covered Raft yesterday. The project is written in OCaml.

We chose OCaml as the implementation language for reproduction (as compared to the original implementation’s C++) due to its static typing and powerful module system. The core protocol implementation is pure and does not include any side-effecting code, and uses algebraic data types to restrict the behaviour of the protocol to its own safety criteria. Where the static type system was insufficient, we made liberal use of assertion checks to restrict run-time behaviour.

By modeling Raft’s state transitions in SPL it is possible use model checking tools and also to generate OCaml code that acts as a safety monitor at run-time:

Raft’s state transition models (such as Figure 3) are encoded in Statecall Policy Language (SPL). SPL is a first order imperative language for specifying non-deterministic finite state automata (NFA). We chose to use SPL due to its ability to be compiled to either Promela, for model checking in SPIN, or to OCaml, to act as a safety monitor at run-time. Alternatives to SPL include using systems such as MoDist that model-check protocol implementations directly, or encoding the model directly in Promela, as has been recently done for Paxos.

The simulator is also built in OCaml. In simulation it is possible to have a holistic view of the cluster state to aid in verification.

In order to evaluate our Raft protocol implementation across a range of diverse network environments, we also built a message-level network simulation framework in OCaml. Beyond evaluating the performance of the protocol, we can also use our simulation traces to catch subtle bugs in our implementation or the protocol specification. Since such issues may only occur very rarely (e.g. once in 10,000 protocol runs), a fast simulator offers the unique opportunity to address them via simulation trace analysis. Furthermore, we can use our simulator’s holistic view of the cluster to ensure that all nodes’ perspectives of the distributed system are consistent with respect to the protocol. To meet these domain-specific requirements, we designed our own simulation framework, instead of opting for traditional event-driven network simulators like ns3 or OMNeT++.

Using the simulator the authors were able to reproduce the performance results from the original Raft paper. “We were then able to use our framework to rapidly prototype optimizations to the protocol by virtue of having calibrated our simulation by replicating the authors’ original experimental setup.”

• Instead of having a single timer used for both follower and candidate timeouts, elections proceed faster if two separate timers are used, with the candidate timeout set lower than the follower one. Under simulation of a highly contested environment, this led to leaders being established within 281ms compared to 1330ms without the optimization.
• Binary exponential backoff for candidates rejected by a majority of leaders also improves election times. However, combining this with the lower candidate timer performed slightly worse than just using lower candidate timers in isolation.
• A Tail at Scale effect exists for client command completions, with a small number of outliers (most commonly when a leader fails and a new one is subsequently elected) taking much longer than the normal case. The client commit timeout value is normally set much higher than the RTT to accommodate this. The introduction of a separate ClientCommit acknowledgement would enable the use of two distinct timers to separate the normal and election cases.

The simulation traces were checked using SPL, and at no point were safety guarantees compromised.

However, we did observe permanent livelock in some of our simulation traces, caused by the interaction between the extra condition on commitment (detailed in §2.3.3) and our placement of the client request cache. We recommend that if a client request is blocked by the extra condition on commitment, the leader should create a no-op entry in its log and replicate this across the cluster. We refer the reader to our technical report for a detailed analysis of this issue.

(The “extra condition on commitment” refers to the fact that a new leader can only commit entries from a previous term once it has successfully replicated an entry from the current term).

And this brings us to the big question: is Raft really easier to understand than the alternatives?

In our experience, Raft’s high level ideas were easy to grasp—more so than with Paxos. However, the protocol still has many subtleties, particularly regarding the handling of client requests. The iterative protocol description modularizes and isolates the different aspects of the protocol for understandability by a reader, but this in our experience hinders implementation as it introduces unexpected interaction between components (see previous section). As with Paxos, the brevity of the original paper also leaves many implementation decisions to the reader. Some of these omissions, including detailed documentation of the more subtle aspects of the protocol and an analysis of the authors’ design decisions, are rectified in Ongaro’s PhD thesis on Raft. However, this only became available towards the end of our effort. Despite this, we believe that Raft has achieved its goal of being a “more understandable” consensus algorithm than Paxos.