2pc and Paxos are solving the same problem Two Phase Commit, a.k.a 2pc, is a very well-known and intuitive algorithm, often used for coordinating transactions. Paxos is a well-known consensus algorithm, often used for replication on a stateful service. Paxos is less intuitive and harder to grasp. Atomic…
Why use small versions Almost all stateful services (data store, cache, etc.) have versions stored along with each piece of data. The version can be in the form of a timestamp, version (a.k.a logical clock), or even better -- Hybrid Logical Clock. If it's a data store, HLC…
This is my notes on the paper: Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases [https://www.allthingsdistributed.com/files/p1041-verbitski.pdf]. What's Amazon Aurora Functionally speaking, an instance of Aurora is same as an instance of MySQL. The differences are Aurora decouples compute from storage and it's…
2pc is a Blocking Protocol Two Phase Commit is a blocking protocol. It blocks when Coordinator is not available. Not only the transaction cannot make progress. Other transactions that conflict with the same set of keys are also blocked. Non-blocking 2pc Alternative Daniel Abadi proposed a non-blocking alternative for 2pc…
boost is THE C++ library out there. Many features were introduced in boost before adopted in C++ standard. I want to have it installed on my local Mac laptop, so I can easily play with it. homebrew formula not working brew install boost is the first thing I did and…
I was looking at a weird coredump the other day. From the core, the program was trying to write to virtual address 0x6 and crashed on memcpy. There's a piece of code looks like if (a == 1) { do_foo(); } else { do_bar(); } And from the coredump, a is indeed 1.…
-- Scalable Read Atomic Transaction for Partitioned Datastore A Story You are building a messaging app. You start with a non-partitioned single database, where you store unseen message count and the actual messages in two different tables. It served you well ... until more and more people are using your app…
The Paxos algorithm, when presented in plain English, is very simple. -- Leslie Lamport 2001 [1] I am going to try explain the single decree Paxos in a way, hopefully, that's easy to understand. To this day, IMO, John Ousterhout's lecture on Paxos is still THE BEST out there. The…