关键词: 日志结构合并树, 键值存储, 读取性能, 布隆过滤器, 存储管理, 热度预测

Abstract:

Bloom filters are often used in the LSM(Log-Structured-Merge) tree to reduce unnecessary disk I/O. However, users cannot refine the granularity of Bloom filters infinitely, because in some workflows with huge data volume and small data items, these metadata require a lot of storage space. Secondly, in some memory-constrained environments, the cache cannot accommodate more filter data, resulting in frequent data exchange between memory and disk. In view of the above problems, we propose a heterogeneous Bloom filter scheme in LSM tree. The hotness prediction model is maintained at each layer of the LSM tree, and the newly generated disk components are distributed with different granularity according to the predicted hotness. And a specific cache management scheme is used to maintain the filter data in memory cache and deal with changes in workflow hotness. It is experimentally proven that the proposed scheme improves read throughput by 22%~53% over LevelDB with the original LSM tree structure while maintaining the same storage occupation and memory consumption.

Key words: log-structured-merge-tree, key-value store, read performance, Bloom filter, storage management, hotness prediction