Formica: simplified MICA key-value storage
This directory contains a simple implementation of MICA's key-value store, which uses a lossy hash table and circular log to get good single-core performance.
The Formica implementation, is introduced in this blog post summarising the original paper.
There are three store implementations here in store.cc:
FormicaStoreis a reimplementation of MICA's lossy hash and circular log
StdMapStoreis a key-value store that uses a lossless
std::mapas an index, and Formica's
CircularLogas a backing store.
ChainedLossyHashStoreis a key-value store that uses a linearly-chained hash table with limited chain sizes. Values are stored in the chain nodes themselves; there is no separation of index and storage.
Here's their relative performance, measured on my 2013 Macbook Pro with 16GB of memory:
To build, see the instructions in the root-level.