LevelDB 版本信息相关的数据结构解析2

2022-04-18 00:00:00 版本 文件 生成 引用 写入

LevelDB 版本信息相关的数据结构解析2

  • 上篇介绍了leveldb中涉及版本信息的一些数据结构Version、VersionSet、VersionEdit，本篇文章来介绍下版本管理是如何进行的。

  • 首先我们可以回忆下leveldb读取一条key的流程：首先在memtable中读取，找到则返回；否则要去sst文件中读取。遇到个问题就是，我们如何可以快速的从众多的sst文件中找到具体包含我们目标key的文件。其实在leveldb中有一个版本信息记录了每个sst文件在哪一个level上，每个文件中包含的key的大小范围。那这样，我们要定位到目标key在哪个sst文件中就方便多了，这个版本就想索引一样帮助我们快速定位sst文件。

  • 第二个问题：那么有一个版本就够了吗？可以看到一个版本可以表征一个状态下的sst文件情况，随着新的数据不断写入memtable，当memtable被写满了之后，就会转换为level 0层的一个sst文件，或者由level n层和level n+1层的sst合并成新的sst文件，这样就产生了一个新的版本，所以leveldb也需要去管理这些版本。也可以从另外一个角度去看这个问题：假设使用了整个数据库的迭代器，在迭代数据库时，leveldb是提供了一个一致性的视图，也就是只能看到迭代前的写入，而迭代后的写入是看不到，在实现的时候，迭代器会引用这个版本，以及里面的sst，直到迭代结束。如果在迭代过程中，存在删除数据，直接删除某个文件，那么就无法引用到这个文件了，就会出错。所以需要多个版本，有一个版本是当前版本，当新生成版本后，旧的版本如果有被其它线程引用，也需要保留，直到不被引用后，才会被删除，所以一个时刻可能有多个版本存在。

  • 我来简单总结下leveldb管理版本用到的一些类：

    • Version 表示一个版本，主要记录的是这个版本包含的sst的信息

    • VersionSet 表示一个版本集合，其中保存了节点为Version的一个双链表，其中有一个Version是当前版本，因为只有一个实例，还保存了其它的一些全局的元数据，Dummy Version是链表头

    • VersionEdit保存了要对Version做的修改，在一个Version上应用一个VersionEdit，可以生成一个新的Version 可以说 Version1 + VersionEdit1 = Version2

    • Builder是一个帮助类，帮助Version上应用VersionEdit，生成新版本

  • 版本管理的基本工作流程：

    • VersionSet里保存着当前版本，以及被引用的历史版本

    • 进行Compaction时，会将更改的内容写入到一个VersionEdit中，包含新增的文件，删除的文件

    • 利用Builder将VersionEdit应用到当前版本上面生成一个新的版本

    • 将新版本链接到VersionSet的双链表上面

    • 将新的版本设置为当前版本

    • 将旧的当前版本Unref，就是引用计数减1

  • 版本控制中使用了引用计数来管理历史版本:

    • 假设一个没有被访问的数据库，这时候只有一个版本，也就是当前版本v1，它的引用计数是1

    • 假设有一个迭代器开始访问数据库，这时候它会对当前版本v1 Ref，引用计数变成了2

    • 其它线程不断写入，导致了Compaction的生成，这时候生成了一个新的版本v2成为了当前版本，引用计数为1，然后对v1 Unref，这时候v1的引用计数为1

    • 因为v1的引用计数为1，所以不会被删除，迭代器线程还可以继续访问v1

    • 迭代器结束后，对v1进行Unref，这时候v1的引用计数变为0，就会从链表上删除了，这时候又只剩下v2版本了

    • 版本里面的sst也是采用引用计数来管理的，每个版本引用一个sst时会Ref，删除版本时会Unref，如果一个sst的计数为0，那么这个sst就可以被删除了

  • 版本变迁的写入，当需要生成一个新版本时，都会向manifest写入一条新记录，记录了新版本相对旧版本有哪些变化，主要包括以下几部分：

    • 写入时刻的日志编号

    • 写入时刻下个可用文件的编号

    • 写入时刻上一个用掉的SequenceNumber

    • compact_pointer_数组，可能有多条记录，有level和对应的internal key

    • 记录删除了哪些文件，记录了level和对应的file number

    • 当前存在的sst文件，包含元数据，包括在哪一level，文件编号，文件大小，里面的小键和大键

  • Builder的作用

    • 可能会问：有了VersionEdit，就可以构造出另外一个版本，为什么还需要Builder。

    • 我们知道，当有VersionEdit改变版本时，直接引用到当前的Version生成一个新的Version就可以了。

    • 正常情况下，一次compaction或者memtable写入后sst后，会产生一个VersionEdit，将这个VersionEdit应用到当前Version上生成一个新的Version。但是在版本变更时，也会将VersionEdit的内容写入manifest中。每当重新打开一个数据库时，需要读取manifest重新构造版本信息，这个版本信息由初始的Version和多个VersionEdit生成，如果直接用VersionEdit应用就会产生成多个版本，进行了很多重复的操作，无疑会降低效率

    • 所以，才引入了Builder，使用Builder，可以将多个VersionEdit的内容累积到Builder上，然后一次性应用到当前Version即可生成新的Version。

来自：https://mp.weixin.qq.com/s/wDginxfAN1NgUMD1UV9v8Q

相关文章