Note: I used DTO objects that represent the messages received from Binance. They are located in the namespace BinanceDto. IO and marshalling are important in real-world use case but out of scope here. Price and quantity values in my DTOs are "stringify" to mimic the messages sent by Binance. Parsing decimal numbers is a "real concern" that led to the creation of dedicated library such as https://github.com/lemire/fast_double_parser (I used its Java version written by the same author to compare it with the most famous one: Javolution, and the former is way faster). I used a simple way to convert those strings into double in my order book implementations but in reality this should be done beforehand with an efficient library.

To implement the order book, I tried four different implementations that all implements the interface IOrderBook with the basic operations. The first one is the most simple that helps me building the API, writing the tests and the benchmarks from which I built three different implementations by iterating.

The first one is making use of a Red-Black Tree because of its properties that ensure efficient search, insertion, and deletion operations with a guaranteed logarithmic height (O(logN) average and worst case). I started to code my own implementation by discovered that there was already one implemented in the .NET core library so I decided to give it a go (it also saved me a lot of time). The class in which it is used is OrderBook.

First impl: class OrderBook.

The second one is similar to the first one but uses a "trick" to not have to store two pair of double wrapped in KeyValuePair object (see SortedDictionary impl.). It packs the two doubles into a single long by making the assumption that each double multiplied by a certain scaling factor can fit into a 32-bits integer. See the class OrderBookPacked for more details. We could even refine this trick by knowing by advance the range of prices and quantities and store those doubles in smaller data types (<32 bits like byte, short, char....). In addition, min and max values are tracked at each add/remove operations in order to provide in O(1) time the response to “what are the best bid and offer?” instead of having to iterate over the tree to find them.

Trick:

public class Bits
{
    
    public static long Pack(int i1, int i2)
    {
        long packed1 = (long)i1 << 32;
        long packed2 = i2 & 0xFFFFFFFFL;
        return packed1 | packed2;
    }

    public static int Unpack1(long packed)
    {
        return (int)(packed >>> 32);
    }

    public static int Unpack2(long packed)
    {
        return (int)(packed & 0xFFFFFFFFL);
    }
}

Second impl: class OrderBookPacked.

For the third, I wanted to try an array based over a pointer-based data structure to see if it can leverage modern pipelining (SIMD), caching CPUs, branching... I created a custom Binary Heap that can store long only (it could be generalized to any type though) and used the same trick presented above (packing of two integers into long). SPOILER ALERT: This implementation yields worst results compared to its predecessor due to the fact insertion time with this custom impl. of Binary Heap is O(N). See details in the class BinaryHeapLong.

Third impl: class OrderBookHeap.

Finally, I propose a thread safe version of the order book using the Left-Right algorithm. with the underlying structure being the one implemented for OrderBookPacked. This algorithm suits well for this use case because with the Binance API, we would subscribe to a list of symbols and would receive updates via websocket channels. One per symbol => only one writer per symbol/multiple readers. Note for the reader: I started by implementing LR algorithm in Java and ported it to C#. The Java impl. can be found at the end of this document.

Fourth impl: class ThreadSafeOrderBookPacked.

The benchmark results are presented at the end of this document. The fourth implementation has also be benchmarked to see the impact of the LR algo. usage and the impact of volatile operations.

The unit tests can be found in PricePointBook.UnitTests directory. The main test classes are in PricePointBook.UnitTests.OrderBook and inherit from the same base test class to test the different implementations.

Note: ThreadSafeOrderBookPacked should be stress tested to make sure it is really thread safe!

Performed on my local machine with the following specs:

BenchmarkDotNet v0.13.10, macOS Sonoma 14.0 (23A344) [Darwin 23.0.0]
Apple M2 Max, 1 CPU, 12 logical and 12 physical cores
.NET SDK 7.0.403
  [Host]     : .NET 7.0.13 (7.0.1323.51816), Arm64 RyuJIT AdvSIMD
  DefaultJob : .NET 7.0.13 (7.0.1323.51816), Arm64 RyuJIT AdvSIMD

The benchmarks use data generated in PricePointBook.Benchmarks.DataGenerator. I paid attention to generate a correct dataset by making sure that price updates and removals have actually an impact on the order book (they exist in the current state of the order book, it is not a simple Random.nextDouble()!).

Different scenarios are tested in the benchmarks with different ratio of updates/removals.

Benchmarks are using the following framework benchmarkdotnet framework. Luckily for me, it is quite similar to https://github.com/openjdk/jmh.

To run the benchmarks, go to PricePointBook.Benchmarks directory and run:

dotnet run -c Release

It runs the benchmarks for a single implementation. To change the implementation, (un)comment the relevant part of code in MyBenchmarks.cs

private readonly IOrderBook _orderBook = new OrderBookPacked();
// private readonly IOrderBook _orderBook = new OrderBook();
// private readonly IOrderBook _orderBook = new OrderBookHeap();
// private readonly IOrderBook _orderBook = new ThreadSafeOrderBookPacked();

With initial capacity for the array = 2048

Comparison between the first three implementations (impl 1 = OrderBook, impl 2 = OrderBookPacked, impl 3 = OrderBookHeap):

We can see that the best implementation is 2. It is 15% faster than 1 for the Initialize phase and as fast as 1 for the Updates phase. 3 is out of the picture due to its run-time complexity. Array-based data structure and all the benefits that comes with does not change anything here in a positive way. What is noticeable also between 1 and 2 is the amount of memory used. 2 uses less memory (usage of long instead of KeyValuePair<double, double>) as a real advantage + less transient memory generated. No Gen1 for 2. And for Gen0, about 13 times less for the Initialize phase. I am not sure why I am not seeing for the Updates phase.

Comparison of impl 2 (OrderBookPacked) and impl 4 (ThreadSafeOrderBookPacked): Without surprise, 4 is twice slower as 2 and consumes the double of memory.

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Consumer;
import java.util.function.Supplier;

/**
 * http://concurrencyfreaks.blogspot.com/2013/12/left-right-classical-algorithm.html
 */
public class Main {

  static class ThreadSafeObject<T> {

    final Supplier<T> factory;

    final Object[] instances;

    AtomicInteger readIndex = new AtomicInteger(0); // 0 or 1

    AtomicInteger[] readIndicator = new AtomicInteger[2];

    AtomicInteger leftRight = new AtomicInteger(0); // 0 or 1

    Lock lock = new ReentrantLock();

    ThreadSafeObject(Supplier<T> factory) {
      this.factory = factory;
      this.instances = new Object[]{factory.get(), factory.get()};
    }

    public void read(Consumer<Object> action) {

    }

    public void write(Consumer<Object> action) {

    }
  }

  Object[] objects = new Object[2];

  AtomicInteger readIndex = new AtomicInteger(0); // 0 or 1

  AtomicInteger[] readIndicator = new AtomicInteger[2];

  AtomicInteger leftRight = new AtomicInteger(0); // 0 or 1

  Lock lock = new ReentrantLock();

  public void read(Consumer<Object> action) {
    int rIndex = readIndex.get();
    readIndicator[rIndex].incrementAndGet(); // arrive, being the read
    int index = leftRight.get();
    Object obj = objects[index];
    try {
      action.accept(obj); // Do some read stuff with obj
    } finally {
      readIndicator[rIndex].decrementAndGet(); // depart, read is over
    }
  }

  public void write(Consumer<Object> action) {
    lock.lock();
    try {
      int index = leftRight.get();
      int writeIndex = index == 0 ? 1 : 0;
      Object obj = objects[writeIndex];
      action.accept(obj); // Do some write stuff with obj...
      leftRight.set(writeIndex); // toggle. Future read with use the newly edited version

      int rIndex = readIndex.get();
      int newRIndex = rIndex == 0 ? 1 : 0;
      while (readIndicator[newRIndex].get() != 0) {
        Thread.yield();
      }

      // Toggle readIndex
      readIndex.set(newRIndex);

      while (readIndicator[rIndex].get() != 0) {
        Thread.yield();
      }

      obj = objects[index];
      action.accept(obj); // Do some write stuff with obj...
    } finally {
      lock.unlock();
    }
  }
}