FlatStore uses a log to save data into Persistent Memory. It can be applied to either a B-Tree index or Hash index.

Similar to KVell, FlatStore also employs in-memory index and save keys unordered on PM.

Log-structure

The idea of the log structure is widely used for SSD/HDD.

• It converts random write into sequential writes.
• It amortizes multiple small writes via batching.

Persistent Memory

PM based storage usually do not use log structure technique.

• PM shows very close performance for random/sequential access.
• It is not beneficial to batch data larger than a data block (64B/256B).

FlatStore

Insights: Selective Batch to maximize the potential performance.

• Small updates are appended to the per-core log.
• Large updates are stored separately.

Compacted log format

FlatStore incorporates the operation log technique (OpLog). The log entry only contains minimal information for describing each operation. If the key-value pair is large, FlatStore saves it separately with an allocator and reserve 40 bits in the log entry for the ptr. The size of each entry is restricted to be 16 bytes. Thus, 16 log entries can be flushed altogether in a 256B cacheline.

While storing the key-value pair separately, the Allocator will maintain certain metadata, such as a bitmap to indicate the allocated chunk. Those metadata can further verify the consistency. Thus, the allocator doesn’t need to flush the chunks as well as the metadata.

Pipelined Horizontal Batching

Log batching is another important technique in FlatStore.

If each working threads use a separate log, it would need to wait for a long time until a batch size is full. Thus, it will eventually result in more flushings and paddings in the log.

The horizontal batching merges log entries from multiple threads and flushes them together. It then updates the in-memory index. The Pipelined Horizontal Batching synchronizes the cores to allow each threads to continuously accept requests while merging the log entries.