基于leveldb谈谈MVCC多版本控制

最近接触存储的原理比较多,MVCC也是存储系统常用的技术手段。

MVCC多版本是一个解决并发问题的模型,或者说是一种设计思路。

why

如果有一份数据,无论它是存储在内存里还是磁盘上,当我们读取数据时可能有写操作正在修改它。传统思路就是将数据用一把互斥锁保护起来:

  • 读之前锁住,这样就不会有写操作。
  • 写之前锁住,这样就不会有读操作。

如果数据是内存里的一个哈希表,那么锁的代价还可以忍受,几乎总是瞬间可以完成。

然而存储系统一般都要和磁盘打交道,读请求是从磁盘上读取一个文件的某个偏移量,写请求可能需要删除旧的文件并创建一个修改过的新文件(一般存储不会覆盖修改数据,因为异常时可能写坏数据)。

如果仍旧为了保护数据而上锁,那么磁盘的缓慢操作将导致锁占用时间很长,从而直接降低了系统吞吐。如果不上锁,那么极有可能正在读某个文件的同时,文件被删除了,导致严重错误。这就是MVCC多版本技术出现的背景环境。

how

这里以leveldb为例,简明扼要的说明其MVCC的实现原理,相关技术文档在这里阅读:《leveldb实现解析.pdf》

这里盗图一张,它描述了leveldb的多版本设计原理。这里可能很多同学没接触过leveldb,我会简单讲一下其原理。

leveldb是一个K-V存储引擎,具有很高的读写性能,我们不谈其存储细节,只介绍几个与MVCC相关的核心概念来帮助理解。

  1. 写请求首先保存在内存中,当达到一定体积后写到磁盘上的sst文件中。
  2. 读请求首先在内存中查找,没找到则去磁盘上的若干sst文件中查找。
  3. 磁盘上的sst文件不断增加,会有策略job定时的将N个sst文件合并为1个更大的sst文件。

假设一个场景:读操作会去磁盘扫描sst文件查找对应的数据,而策略job可能恰好正在合并遍历中的某sst文件,同时向合并后的sst文件输出中,最后还会删除掉旧的sst文件。这意味着,正在读的sst文件可能被删除,或者正在输出中(不完整)。

按照我们悲观锁的思路,直接加一把大锁,那么读请求期间写请求无法进行,漫长的写期间读请求不能进行,基本这个leveldb就没法用了。

leveldb采用MVCC避免大锁,这里引入了几个概念:

  1. version edit:记录sst文件集合的变化。当合并N个sst生成1个大sst,被合并的sst不再有意义,合并生成的新sst包含了它们的数据,version edit记录的就是:合并了哪些sst,新增了哪个sst。
  2. version:代表一个版本,记录了数据库由哪些sst文件组成。当磁盘合并发生后,对应的version edit施加到最新的version上,从而产生新的version,它记录了当前最新的数据库sst集合。
  3. version set:指向最新的version。

大概了解上述抽象概念后,我们直接说明MVCC的设计原理。

version set全局唯一,其中current_指针指向最新的version:

这是version版本,files_保存了该版本数据库的所有sst文件。

next_,prev_是链表,说明多个version是串在一起的。这里就容易产生几个好奇:

  1. 为什么会有多个version?
  2. version是怎么产生的?

回想合并的过程,N个sst文件merge到1个sst文件后,虽然N个sst文件已经没有意义,但是leveldb并不会立即删除它们,这是为什么呢?这就涉及到读请求了。

某个时刻,读请求会根据version set里的current_找到最新version,并在这个version里保存的sst文件集合中寻找目标数据。此后假设发生了合并并产生了新的version,新version将更新到version set的current_字段成为新的链表头。如果此时立即删除被合并的sst文件,那么正在进行中的读请求就会出错,所以删除sst文件的动作并不是立即发生的。同时,因为读请求依据的是旧版本的version(sst文件集合),所以新合并生成的sst并不会被该读请求扫描到。

是不是已经有点多版本控制的感觉了?

在实现上来说,读请求引用了旧版本的version,而写请求需要设置新版本的version,那么旧版本的version何时释放内存呢?这里就采用了引用计数机制,最新的version默认是1个引用计数并保存在version set的链表头部(current_),当读请求到来后会对version set的current_增加1个引用计数。此后发生合并生成新version替换current_时,先释放旧version的1个引用计数(还剩余1个由读请求持有),然后替换current_为新的version对象。

当读请求结束后,会释放旧version的最后1个引用计数,此时引用计数降低为0,旧版本version进入析构函数。这里涉及另外一个重要设计,我们知道之前写请求(合并sst)完成时并没有删除被合并的sst文件,其目的是因为之前的读请求可能正在访问旧sst文件,特意延迟了删除操作。

那么,删除应该延迟到什么时候呢?其实只要涉及到这种资源持有问题一般都是采用引用计数,在version中的files中保存的FileMetaData也是基于引用计数的共享内存。

当合并旧version+version edit生成新version时,旧version中没有被合并的sst文件对应的FileMetaData的引用计数将+1并保存到新version中,而被合并的sst文件的FileMetaData的引用计数保持不变并且也不保存到新version中。当替换current_为新version时候会首先释放旧version的1个引用计数从而进入旧version析构。在version析构中,会释放每个FileMetaData的1个引用计数,对于那些在新version中已经被合并的sst文件来说,引用计数减少为0将完成最终删除。

可见,leveldb的MVCC实际上由几个重要部分组成:

  • sst文件的不变性:只合并生成新sst而不覆盖旧的,保障多版本都可以读到属于自己的数据。
  • version引用计数:保证某版本所有sst文件的资源有效性。
  • FileMetaData引用计数:保证单个sst文件在多version下的资源有效性。

 

如果文章帮助您解决了工作难题,您可以帮我点击屏幕上的任意广告,或者赞助少量费用来支持我的持续创作,谢谢~