FoundationDB Summit 2019

This talk describes the development of a new FDB memory storage engine based on the radix tree data structure. The default memory storage engine is a balanced binary search tree. Because Wavefront’s use case involves a large amount of prefix-overlap in keys, we decided to adopt a different data structure, the radix tree, to make our FDB clusters more space-efficient. This trie-based KV store has two main advantages:
(1) It is more space-efficient than the default engine when there is a large amount of key overlap (as in our time series workloads).
(2) The height and complexity of a radix tree depend on the length of the keys, not on the number of elements

Our presentation will include a brief introduction to radix tries followed by a deep dive into some of the optimizations we needed to make. Finally, we will show the performance comparison results using real-life Wavefront workloads.