leveldb存储引擎.pdfVIP

LevelDB存储引擎 网易杭州研究院胡争 （博客：openinx.github.io） LevelDB简介 • 基于LSM实现的KV存储引擎 • Google实现/单机 C++ • 写入性能极高(40W/s) • 读性能比写性能差(6W/s) • 支持快照读一致性 • 支持崩溃恢复 • 采用snappy数据压缩 LSM 相关产品 BigTable RocksDB HBase Cassandra WiredTiger LevelDB InfluxDB Part.1 数据结构 LevelDB-LSM结构 Memory Disk Level-0 Level-1 Level-2 …… …… Memtable Immutable Table SSTable LevelDB-LSM性质 • Memtable/ ImmutableTable • 4M左右内存块 （可调整） • 存放有序键值对 • 内存结构为skiplist • 数据先写入Memtable，再通过Compaction方式异步下推落盘。 • SSTable • 层次结构 （而不是严格树形结构） • SSTable存放有序键值对 • Level-0层SSTable之间可能存在Range交集 • Level-i （i0 ）层SSTable之间不存在Range交集 • Level-i层SSTable个数数量级在10^i • Level-i层中每一个SSTable最多与Level-(i+1)层的10个SSTable有交 集 • 数据新鲜度：MemtableImmutableTableLevel0Level1... SSTable存储结构 BloomFilter原理 • 随机化算法 (BloomFilter) • 解决的根本问题： – 判断一组key是否在集合中。 – 答案只有两种：可能存在 or 不存在。 – 每个键值消耗10bit ，理论上可以保证可能存在出错的概率1%. • 特点： – 随机化 – 空间换时间 – 过滤不必要的查询 前缀压缩 • 压缩规则： – 一个restart-point对应一个前缀压缩组； – 一个key和上一个key公共前缀长度0，则key放入相同前缀压缩组； – 一个key和上一个key公共前缀长度=0，则新建一个前缀压缩组。 • 查找规则： – 多个前缀压缩组之间二分查找； – 前缀压缩组内线性查找； • 配置参数：block_restart_interval – 前缀压缩