| layout | post | |
|---|---|---|
| title | rystsov::Distributed register | |
| name | Distributed register | |
| tags |
|
|
| desc | How to update the write-once registor into a distributed fault-tolerance mutable register with the compare-and-set (CAS) concurrency control mechanism | |
| has_comments | true |
In the previous [article]({% post_url 2015-08-22-paxos-register %}) I showed how to create a write-once distributed register. But in real life we usually want to mutate state. So Let's fix it and design a mutable register.
Distributed mutable register is a little bit more complex system than the write-once register but it uses the same idea so if you understand the register then it should be easy to you to understand the current design.
The basic idea is to use a sequence of ordered registers to emulate a variable. For example to write a value we write it to the register with the lowest ID among empty registers. To read a value we read it from the register with the highest ID among filled registers.
Distributed system is by definition is a concurrent system too so its very important to provide concurrency control mechanisms like a compare-and-set (CAS) primitive. To support CAS primitive we must prevent modification of the past, e.g. edit of registers if a register with a higher ID has already chosen a value. We can achieve it by maintaining serializability between any successful register's modifications. Hopefully we can do it if we make the acceptors use the same promise. Let's take a look on the new acceptor's methods.
{% gist rystsov/a45793daa1662a921479 %}
You may be surprised since you don't see a sequence of the registers. Well, we always are interested only in the filled register with the largest ID so we don't store the whole sequence.
The API consist of two functions
{% gist rystsov/55b68e8ef68b977598b1 %}
The heart of the algorithm
{% gist rystsov/7f8db599d44ee635655f %}