Corfu: Scaling log replication (Part 1)
Corfu: A distributed shared log is a paper running to 25 pages brought to my attention by The Morning Paper. Corfu takes log replication to a whole new level. Corfu achieves linearizable consistency of a fault tolerate distributed log using very simple write-once techniques. The real eye open is that it implements a distributed log interface without an IO bottleneck. The paper proudly points out that after 40 years of research this is a game changer. This series of posts will build up a simple fictional example that demonstrates the key techniques. Then I will glue it all together to describe how Corfu itself works and demystify the role Paxos plays.
The first thing I notice when reading the Corfu paper is that no formal proof of safety is presented. This is a bit of a surprise given that the paper achieves a step change in performance. The reason for this is that Corfu bootstraps itself from a strongly consistent configuration distributed by a conventional consensus algorithm:
We do not discuss the details of the actual consensus protocol here, as there is abundant literature on the topic. Our current implementation incorporates a Paxos-like consensus protocol using storage units in place of Paxos-acceptors. [page 12]
Using this consistent configuration Corfu builds a distributed log using very simple, and I would say very elegant, mechanisms.
In the following series of posts I will give a quick “from basics” overview of the techniques used in Corfu. I will then explain Corfu in terms of them.
To name the interesting techniques in the paper:
- Global Log to give Linearizable Consistency covered in Part 2
- Global Sequencer eliminating write contention covered in Part 3
- Stripe And Mirror for “RAID 10”-like resilience and concurrency of writes covered in Part 4
- Copy Collection for garbage collection covered in Part 5
- Write-Once data safety
- Write Ordering to avoid corruption due to concurrent thread updates
- Collaborating Threads fixing up possible crash consistency problems
- Paxos Configurator for cluster consistency
Those are my names for the techniques. There may be more formal names for what I describe in the following posts. Please post a comment if I have missed a Corfu technique else if a given technique has a more established name.