What is an efficient data structure to save order book states?

Question

First of all, I am aware of the highly related question What is an efficient data structure to model order book?, but my question is a bit different here.

I want to save the order book states after the arrival of each message, which includes add, cancel and trades. For example, assume we're using a B-Tree with double-linked lists, after each message I'll serialize it to disk.

These operations are done offline by replaying historical data, so I don't care too much about performance and I don't really need to implement the matching myself. My main purpose is to be able to fast recover what the order book looks like given some specific message and then generate some snapshot in future research, so that I do not have to replay all the data every time.

Therefore, I'm mostly interested in how to effectively save these order book states to achieve low disk usage and fast loading. For some liquid instruments there could be millions of messages and it seems unrealistic to save all the snapshots, especially when they are highly redundant and serially correlated. I'm thinking about only saving the changes of order books as sequences as somthing like "price 100 + vol 1000, price 101 - vol 100", but then it would be path dependent.

Any suggestions?

Answer 1

One approach would be to make a snapshot every $n$ messages with $n$ chosen such that applying $n$ messages to a given orderbook is fast enough for you. This gives a reduction in storage requirements by a factor approximately $n$ and it should be quick to apply a limited number of messages.

If you can play the messages backwards as well, the expected time to replay to a certain message halves.