lsm

· 713 words · 2 minute read

lsm 基本想法 🔗

  磁盘上的key/value存储, bytes -> bytes, order by key
  使用场景， 写多读少。

  • 分层，有序，面向磁盘的数据结构
  • 批量写，顺序写对硬件驱动友好
  • 顺序操作高吞吐

  应用：levelDB, RocksDB, HBase, TiDB, Cassandra

磁盘上的数据结构 🔗

  暂时不考虑level, merge, compaction, logs, 只考虑磁盘上的不可变的、排序的、字符串表的文件格式。

level db磁盘数据结构 🔗

  排序的表结构。   处理table结构的时候有两种思路： hash VS sorting✅。

image 

// leveldb/db/dumpfile.cc#DumpTable()
table format  default=2MB sorted by key

data block1
data block2
data block3

meta index
index block（index1(last key, offset, size), index2, index3）
footer(magicnumber, index.size, index.offset, meta index.size, meta index.offset)


data block format

entry(shared bytes, unshared bytes, value_length, key_delta, value)
restart （对key重新做前缀压缩， 默认16个entry，平衡解码时间和存储空间的开销）
type(是否压缩，压缩算法)
CRC32

entry format key的前缀压缩：

entries entrycontent shared unshared key_delta
entry1 compute 0 7 compute
entry2 computer 7 1 r
entry3 computes 7 1 s
entry4 computing 6 3 ing

写入 🔗

  写数据时， 写入内存有序树结构memtable, 并更新布隆过滤器。
  当memtable累积到阈值，一次性写入segment内部有序文件到磁盘。
  后台有专门的定期执行compact操作的线程合并segment文件。

读取 🔗

  查询布隆过滤器，若不存在则一定是不存在； 若存在，按照从新到老的顺序依次查询每个segment。

更新 🔗

删除 🔗

  删除时是覆盖写value为特殊标识位，而不是真执行查找并删除。

leveldb的使用 🔗

下载源代码编译生成libleveldb.a

  1. git clone
  2. cd leveldb
  3. mkdir build && cd build
  4. cmake -DCMAKE_BUILD_TYPE=Release ..
  5. make -j

demo程序链接时需要libleveldb.a

编译include：     g++ -std=c++11 -c  test_leveldb.cc -I/Users/brett/cplus_workspace/leveldb/include
链接libleveldb.a：g++ test_leveldb.o  /Users/brett/cplus_workspace/leveldb/build/libleveldb.a -lpthread -o test_leveldb
运行： ./test_leveldb

demo程序， include/leveldb/db.h：主要的 DB 接口

or

在CMakeLists.txt文件，增加一行if(NOT BUILD_SHARED_LIBS) leveldb_test("app/main.cc") cmake .. && cmake --build .

存储