Parallel Snapshot Isolation

November 17, 2018

In “Transactional storage for geo-replicated systems,” Sovran et al present a key-value store designed specifically for applications that require data replication across distant sites. Their solution, Walter, is novel in that it combines the benefits of key-value storage (e.g. the high availability that we’ve seen in Dynamo and Cassandra) with the safety and sanity of ACID transactions. This is an attractive combination from the perspective of the applications developer, who would rather not have to attempt to manually implement all of those guarantees at the application layer.

Riddles of Consensus

November 17, 2018

The Byzantine General’s Problem, introduced in Lamport et al’s 1982 paper, presented one of the key problems in distributed consensus; namely that in a distributed system, we can’t always trust other system components. The solution to the problem is terrifically complex, and involved an immense amount of round trip communications between the participating replicas.

The Shared Log Abstraction

November 11, 2018

The evolution in thought around consensus algorithms, with Paxos and variants like Multi-Paxos, ePaxos, and the alternative Raft, share the fundamental characteristic of imagining the replica as more than just storage. The metaphors that are used in those papers include things like democracy and war, and cast replicas as entities in a (sometimes more, sometimes less contentious) exchange with each other. Sometimes there is an elected leader, sometimes an appointed leader, and sometimes each member of the group shares equally in the weight of governance. It is interesting, therefore, to read papers such as FAWN, Corfu, and Tango, which see replicas as much more passive participants in the overall replication process.

Wimpy Nodes, Wise Nodes

November 06, 2018

In a distributed storage system, one big question is how much state should be stored on any given node. Decentralized systems tend to give nodes a lot more state, so that they have enough information about the system as a whole to make more independent decisions. However, requiring nodes to maintain a large amount of state can cause problems and also be slow, which is why many distributed systems opt for architectures with strong leaders. In “Scalable Consistency in Scatter” and “FAWN: A Fast Array of Wimpy Nodes,” we see examples of papers that attempt to balance between decentralization and speed.

Predestination in Distributed Transactions

November 04, 2018

Unlike Spanner, which we explored in a recent post, and which uses the strategy of replicating commits, Calvin’s approach to distributed storage instead leverages a fully replicated log to coordinate distributed transactions across partitions and replicas.