学习了下LevelDB的实现原理,发现G厂大神Jeff Dean果然牛B,实现也很巧妙。 参考链接是这里

概览

  1. LevelDB是一个KV持久化存储引擎,它的特性是写非常快,读相对写较慢
  2. LevelDB是基于LSM(Log Structured Merge)实现,它会顺序地记录各种写操作
  3. LevelDB存储分为两部分,一部分在内存,另一部分在磁盘上。内存中方便快速查找, 查找失败后,去磁盘上查找。一段时间后或内存达到一定大小,会将内存中的compact成sst文件存在磁盘

内存存储

  1. 内存存储叫memTable,存储结构为跳表,存储为顺序存储,查找和写入都很快(O(log N))
  2. 删除操作在这里只是打上删除标记,真正的删除在compaction中做

日志

  1. 日志文件记录了每一步的操作,因为文件的append操作很快,所以LevelDB可以支持大量 的写操作
  2. 每次的写都会先在日志上记一笔,记完后去更新memTable
  3. 如果遇到重启等情况,LevelDB就会将已经持久化的文件与日志进行一个merge操作,这就是LSM, 与HBase的恢复操作很相似

磁盘存储

  1. 磁盘存储叫immuteTable,以一种分层的结构存储,层数从0到n(n会随着数据增多而增多), 层数越高表示数据越老旧(可能存在相同的key),除了层0,其他层之间的key都是不相交的
  2. 查找的顺序从这里已经可以得出来了memTable->层0->层1->…->层n,这也是LevelDB名字的由来, 那么数据是如何从memTable转移到层0
  3. 层数0是将memTable整个dump出来的结果,因此可能之间有相交,这个操作叫minor compaction
  4. major compaction是将层i合到i+1中去,合并是将层i中的一块合到整个层i+1中去, 这个过程类似归并排序,将参与的几个块全部取出来排序,再重新组合成新的层i+1,同时 会将重复的key弃掉
  5. 弃掉是指如果key已经出现在更低的层,则高级的层不需要记录这个key

文件格式

  1. 实际硬盘存储并非只有一种sst文件,分为三种:
  2. sst文件记录实际的数据,按顺序排列
  3. manifest文件是sst文件的索引表,记录各个层0文件的key range
  4. current文件记录当前的manifest文件是哪个
  5. sst文件存储的格式像这样:key共享长度,key非共享长度,value长度,key非共享内容, value内容。共享长度指的是相邻两个key的公共子串(可能不止两个),比如”the Car”和 “The Color”共享长度是5,即”The C”,后面非共享的部分分别为”ar”和”olor”
  6. manifest文件的作用主要是指示层0文件的key range,因为层0会有交叠的情况, 因此查询一个key时可能需要在多个层0文件中寻找(这里层0文件也要按新鲜度排序依次查询)

Cache

  1. 查询会先在memTable中找,如果没找到,会去读index,确定在哪个block中,再去block中读, 这至少需要2次磁盘读取
  2. 这里的cache分两种:
  3. TableCache的key为ssTable名称,值包括磁盘文件指针,以及表结构,表结构又包括 index内容及block信息。当查到某个table时,要判断这个key在不在table中,然后再去查 block
  4. BlockCache为可选项,它的key是block_id,value是block内容,这样就避免了一次读取。 这种适合热点读取,如果随机读取并不适合打开BlockCache

Version

  1. 当一次compaction结束后,会创建新版本,当前版本会指向新版本,可用的版本放在 VersionSet中,VersionEdit存在manifest中,表示版本更替的信息,用于重建数据