Corfu: Global Sequencer (Part 3)
In the last post we outlined how to linearizable consistency without a global buffer. This introduced a write contention challenge. In this post we will get into Corfu’s simple fix for this issue.
Corfu uses a global ticket service which acts as a sequencer. The global sequence can be a simple 64bit counter representing the current position of the end of the log file. In Java the `AtomicLong::getAndIncrement` API will do the job. When a client wants to write to the end of the file it simply invokes the global sequencer service to obtain the next number. It then targets it’s write at that position within the global log file.
The global sequencer gives us zero contention with a very simple and very fast service. In the Corfu paper they find that they saturate other parts of their scalable system before the sequencer becomes a bottleneck. It is important to note is that the global sequencer isn’t required for either safety nor correctness. The sequencer is only an optimisation to avoid write contention. Safety is maintained using simple “write-once”. We only need an extra bit in the header of each position to track whether it has been written to. We then only need a trivial boolean check of that bit to have write-once semantics for safety.
In a later post we will have to consider what happens if the global sequencer crashes. Theoretically the system can continue to make some process under write contention. In practice I suspect that performance would be so degraded that the knock-on problems would be insurmountable. It is probably best to fail fast when the sequencer dies until it can be replaced. Exactly how that works we will save to a later post.