最近接触存储的原理比较多，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下的资源有效性。