Corfu: Scaling log replication (Part 1)

by simbo1905

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.