locker - atomic distributed "check and set" for short-lived keys
locker
is a distributed de-centralized consistent in-memory
key-value store written in Erlang. An entry expires after a certain
amount of time, unless the lease is extended. This makes it a good
practical option for locks, mutexes and leader election in a
distributed system.
In terms of the CAP theorem, locker
chooses consistency by requiring
a quorum for every write. For reads, locker
chooses availability and
always does a local read which can be inconsistent. Extensions of the
lease is used as an anti-entropy mechanism to eventually propagate all
leases.
It is designed to be used inside your application on the Erlang VM, using the Erlang distribution to communicate with masters and replicas.
Operations:
locker:lock/2,3,4
locker:update/3,4
locker:extend_lease/3
locker:release/2,3
locker:wait_for/2
locker:wait_for_release/2
Writes
To achieve "atomic" updates, the write is done in two phases, voting and commiting.
In the voting phase, the client asks every master node for a promise that the node can later set the key. The promise is only granted if the current value is what the client expects. The promise will block any other clients from also receiving a promise for that key.
If the majority of the master nodes gives the client the promise (quorum), the client can go ahead and commit the lock. If a positive majority was not reached, the client will abort and delete any promises it received.
Reads
locker
currently only offers dirty reads from the local node. If we
need consistent reads, a read quorum can be used.
Failure
"So, this is all fine and good, but what happens when something fails?". To make the implementation simple, there is a timeout on every promise and every lock. If a promise is not converted into a lock in time, it is simply deleted.
If the user process fails to extend the lease of its lock, the lock expires without consulting any other node. If a node is partitioned away from the rest of the cluster, the lock might expire too soon resulting in reads returning the empty value. However, a new lock cannot be created as a quorum cannot be reached.
Calling locker:wait_for_release/2
will block until a lock expires,
either by manual release or from a expired lease.
Lease expiration
Synchronized clocks is not required for correct expiration of a
lease. It is only required that the clocks progress at roughly the
same speed. When a lock is created or extended, the node will set the
expiration to now() + lease_length
, which means that the user needs
to account for the skew when extending the lease. With leases in the
order of minutes, the skew should be very small.
When a lease is extended, it is replicated to the other nodes in the cluster which will update their local copy if they don't already have the key. This is used to bring new nodes in sync.
Replication
A locker
cluster consists of masters and replicas. The masters
participate in the quorum and accept writes from the clients. The
masters implements strong consistency. Periodically the masters send
off their transaction log to the replicas where it is replayed to
create the same state. Replication is thus asynchronous and reads on
the replicas might be inconsistent. Replication is done in batch to
improve performance by reducing the number of messages each replica
needs to handle. Calling locker:wait_for/2
after a succesful write
will block until the key is replicated to the local node. If the local
node is a master, it will return immediately.
Adding new nodes
New nodes may first be added as replicas to sync up before being promoted to master. Every operation happening after the replica joined, will be also propagated to the replica. The time to catch up is then determined by how long it takes for all leases to be extended.
New nodes might also be set directly as masters, in which case the new node might give negative votes in the quorum. As long as a quorum can be reached, the out-of-sync master will still accept writes and catch up as fast as a replica.
Using locker:set_nodes/3
masters and replicas can be set across the
entire cluster in a "send-and-pray" operation. If something happens
during this operation, the locker cluster might be in an inconsistent
state.