Monday, 14 November 2011

The LMAX disruptor and Baker's Treadmill

A new retail financial trading platform called LMAX recently published their work on new software technology for low-latency servers that they call the "disruptor":

We have noticed a striking similiarity between their disruptor and an old garbage collection algorithm from 1992 called Baker's Treadmill:

The LMAX disruptor and the story behind it are very interesting in their own right and well worth reading up on. In their system, binary messages come from the "receiver" and are distributed to the "journaller", "replicator" and "unmarshaller" in parallel and the "unmarshaller" then passes on the deserialized messages to the "consumer". The core of their idea is to accomplish all of this message passing using a single shared data structure, the disruptor, rather than using several separate concurrent queues.

Baker's Treadmill is a low-latency garbage collection algorithm. Allocated blocks in the heap are linked together to form a cyclic doubly-linked list that is divided into four segments using four iterators that chase each other around the ring as heap blocks are allocated, traced and freed. In addition to making all of the necessary operations incremental, this algorithm is interesting because it migrates heap blocks between its "to", "from", "new" and "free" spaces without physically copying them as so-called copying GC algorithms do (e.g. Cheney semi-space or the nursery in a generational GC). Although this kind of logical migration is very valuable it is surprisingly uncommon in GC research literature. The VCGC algorithm is another example of a GC algorithm that logically migrates heap blocks between "young", "old" and "dead" spaces or "epochs" as the authors call them.

Beyond the striking resemblance of the disruptor to the Treadmill, there are some important differences:

  • The disruptor is a thread-safe concurrent data structure whereas the Treadmill was designed for single-threaded use.
  • The disruptor was designed to flow data from producers to consumers whereas the Treadmill also requires the ability to move an element from one segment of the ring to another.

Despite these differences, we think it is interesting to observe the similarities between these two different data structures and to note that they were both designed for low latency. Given that Baker's Treadmill is now quite dated in terms of low latency GC algorithms, perhaps future work on low-latency data structures can borrow from more recent GC theory?

No comments: