背景

MongoDB默认使用的存储引擎是wiredtiger，而wiredtiger使用MVCC来实现并发控制，会在内存中维护文档的多版本并提供无锁访问，这会带来更好的并发性能，但也会带来更多的内存占用。所以wiredtiger内部使用了多种方法来尽快逐出内存中的数据页，以留下更多的内存给其它读写访问。

下面，我们会先详细介绍wiredtiger中用户表在磁盘和内存中的组织形式，然后通过了解文档的事务可见性，来说明内存page中哪些文档会被逐出到用户表文件中。最后介绍对部分不能逐出到用户表文件的文档，如何使用las逐出方式将其逐出到磁盘中。

page在磁盘的格式

在磁盘上，我们需要一种便于磁盘读写和压缩的格式保存page，这种格式的数据被称为extent。当内存压力小时，extent会在内存中也缓存一份，以减小用户的访问延迟。它由page header、block header和kv列表三部分组成，其中page header存储了extent经过解压和解密后在内存中的大小。block header存储了extent在磁盘中的大小和checksum值。kv列表中的key和value都是由cell和data两部分组成，cell存储了data的数据格式和长度，data就是具体的k/v值。

长度超过leaf_value_max的数据被称为overflow data（MongoDB中leaf_value_max的默认值是64MB，由于mongodb的文档大小不超过16MB，所以不会出现超过该值的情况）。wiredtiger会将该overflow data保存为一个单独的overflow extent存在表文件中，并用overflow extent address（包含overflow extent的offset和size）替换该value值。 wt extent

事务可见性

先看下wiredtiger的事务策略，它的隔离级别是基于snapshot技术来实现，支持read uncommited、read commited和snapshot三种隔离级别，而在MongoDB中使用的是snapshot隔离级别。

在内存中，wiredtiger的page由 在内存中已持久化的文档（上面的extent数据） 和 在内存中未持久化的文档 这两种文档组成，而内存中未持久化的文档又分为未提交的文档 和 已提交的文档。 未提交的文档都是 部分事务可见的文档（修改文档的事务可见，其他read commited或snapshot事务不可见），而已提交的文档分为 所有事务可见的已提交的文档 、 部分事务可见的已提交的文档 和 所有事务都不可见的已提交的文档。对于同个key，按照更新顺序从新到老，已提交文档的顺序是：部分事务可见的已提交的文档 < 所有事务可见的已提交的文档 < 所有事务都不可见的已提交的文档。若一个key在某个时刻的值是所有事务可见的，则早于该时刻的旧值肯定就是所有事务都不可见的，所以对于同一个key，只会有一个文档是所有事务可见的。 wt txn wiredtiger默认是通过内部的txn_id来标识全局顺序，为了保证全局顺序跟MongoDB的server层一致，和支持基于混合逻辑时钟的分布式事务，Wiredtiger还支持事务时间戳txn_ts，所以在判断全局可见性时，既要判断txn_id也要判断txn_ts。

那怎么判断哪些已提交的文档是所有事务可见的，哪些是部分事务可见的，哪些又是所有事务都不可见的呢？判断的规则在wiredtiger中是在__wt_txn_visible_all中实现的，遍历上面的key的更新列表，第一个满足下面条件的文档就是所有事务可见的已提交的文档：不仅要求该文档的txn_id要小于所有正在运行事务（包含可能正在运行的checkpoint事务）的snap_min的最小值（snap_min表示事务t在做snapshot时其他正在运行的事务id的最小值），而且要求该文档的txn_ts要小于所有正在运行事务的read_timestamp（读取数据的时间点）和server层最早可读取数据的时间点。不满足该条件的都是部分事务可见的文档，而满足该条件且除所有事务可见的已提交的文档外的其它文档都是所有事务不可见的已提交文档。

参照下图，我们举例说明，假设所有事务都是使用snapshot隔离级别，现在事务t1、t2、t3、t5已经提交，只有事务t10还在运行中，而在事务t10开始时，事务t1和t2已经提交，但事务t3和t5还未提交。那么事务t10的snap_min就是min(t3,t5)=t3，也就是说事务t10无法看见事务t3和事务t5所更新的文档，即使现在t3和t5事务已经提交，但是事务t3之后已提交的新文档{Key1, Value1-3}和{Key3,Value3-1}对于事务t10也是不可见的，所以只有早于事务t3提交的文档{Key1, Value1-2}、{Key3, Value3-1}才是所有事务可见的文档，而早于它们的{Key1, Value1-1}则是所有事务不可见的文档。 wt update list 下图是对应内存中leaf page的结构，它包含了在内存中已持久化的文档（Leaf Extent中的文档）和在内存中未持久化的文档（Modify中的文档），其中的紫色文档是部分事务可见的未提交的文档，红色文档是部分事务可见的已提交的文档，绿色文档是所有事务可见的已提交的文档，灰色文档是所有事务不可见的已提交的文档。 wt update btree

page逐出的方式

在以下4种情况下会进行page逐出： 1）cursor在访问btree的page时，当发现page的内存占用量超过了memory_page_max（mongodb的默认值是10MB），就会对它做逐出操作，以减小page的内存占用量。 2）eviction线程根据lru queue排序逐出page 3）内存压力大时，用户线程会根据lru queue排序逐出page 4）checkpoint会清理它读进cache的page

page逐出在wiredtiger代码中是在__wt_evict中实现的。__wt_evict会依据当前cache使用率情况，分为内存使用低逐出和内存使用高逐出两种。若内存使用率bytes_inmem/cache_size < (eviction_target+eviction_trigger)/200 且 脏页使用率bytes_dirty_leaf/cache_size < (eviction_dirty_target+eviction_dirty_trigger)/200，则被认为是内存使用低，反之是内存使用高。

在wiredtiger和mongodb中，eviction_target默认值是80，eviction_trigger默认值是95，eviction_dirty_target默认值是5，eviction_dirty_trigger默认值是20，所以内存使用低逐出的判断规则也就是：内存使用率<87.5%且脏页使用率<17.5%。

内存使用低逐出

它主要有3个目标： 1) 从page在内存中未持久化的文档（Modify中的文档）里，删除“所有事务不可见的已提交文档”，减少内存的占用。 2) 将page中最新的“已提交文档”持久化到磁盘，以减少下一次checkpoint所需的时间。 3) 在内存中依然保留该page，避免下次操作读到该page时需要访问磁盘，增大访问延迟。

内存使用低逐出会先将最新的“已提交文档”以extent格式逐出到表文件tablename.wt中，同个key的文档只会持久化一个value值。如果page的modify中有新写的key或者对已有key的更新，那么取出最新的已提交value值，若没有，则从leaf extent中取出其原始的value值。当内存使用率低时，最新的已提交文档在内存中会组成新的extent并替代老的extent关联到page上，并释放内存中老的extent。最后从modify中删除“所有事务不可见的已提交文档”。

如下图所示，最新的已提交文档是“部分事务可见的已提交的文档”（红色文档），也就是说红色文档{Key1,Value1-3}和{Key3,Value3-1}会被更新到新的leaf extent中，删除所有事务不可见的文档Value1-1，而其他的文档仍然要保留在modify中。 wt mem low 那最新的已提交的文档Value1-3和Value3-1都已持久化了，为什么还要在modify中保留它们呢？因为Value1-3和Value3-1是部分事务可见的，对于其它不可见的事务来说，它们还需要看到其之前的文档Value1-2和Value3，所以这些文档依然都要保留。

内存使用高逐出

它主要有2个目标： 1) 尽可能删除内存中page的modify和extent，大幅减少内存的占用。如果因含有未提交的文档，而无法删除modify和extent。那么也要降级为内存使用低逐出，适当减少内存的占用。 2) 将page中最新的“已提交文档”持久化到磁盘，并减少下一次checkpoint的时间

内存使用高逐出根据page的modify包含的文档种类不同，对应有不同的处理方式。具体有以下三种情况： 1）page的modify不包含“部分事务可见的文档” 2）page的modify不包含“部分事务可见的未提交的文档” 3）page的modify包含“部分事务可见的未提交的文档”

我们先介绍page的modify不包含“部分事务可见的文档”的情况，也就是说page的modify中只包含所有事务可见的已提交文档（绿色文档），和所有事务不可见的已提交文档（灰色文档），如下图所示。由于所有事务不可见的已提交文档（灰色文档）是需要被删除的，这样modify中所剩下的“所有事务可见的已提交文档”（绿色文档）就是最新的“已提交的文档”，而内存使用高逐出会将这些绿色文档组成新的extent逐出到表文件tablename.wt中，所以modify中的数据都已被逐出，不再需要保留。最后清理内存中page的extent和modify，并将新的extent在文件中的offset和size关联到page上，便于下次访问时从磁盘中读出extent。 wt mem high1 对于page的modify不包含“部分事务可见的未提交的文档”，也就是说page中只包含部分事务可见的已提交的文档（红色文档），所有事务可见的已提交文档（绿色文档），和所有事务不可见的已提交文档（灰色文档），如下图所示。内存使用高逐出不仅会将最新的“已提交文档”逐出到表文件tablename.wt中，而且还会判断是否满足使用las逐出的条件，如果满足，那么las逐出还会将modify中除“所有事务不可见的已提交文档”（灰色文档）之外的其它文档逐出到表WiredTigerLAS中，后续会被持久化到表文件WiredTigerLAS.wt中。

在下图中，最新的“已提交文档”是部分事务可见的已提交的文档（红色文档），所以红色文档{Key1,Value1-3}和{Key3,Value3-1}会被更新到新的leaf extent中。除“所有事务不可见的已提交文档”（灰色文档）之外的其它文档就是部分事务可见的已提交的文档（红色文档）、所有事务可见的已提交文档（绿色文档），包括{Key1,Value1-3}、{Key1,Value1-2}、{Key3,Value3-1}、{Key3,Value3}，它们会被写到表WiredTigerLAS中。 wt mem high2 如果page的modify包含“部分事务可见的未提交的文档”，或者page的modify不包含“部分事务可见的未提交的文档”但不满足las逐出的条件，那么modify中的数据就不能被逐出，这就导致内存使用高逐出会降级为内存使用率低逐出。而内存使用率低在删除“所有事务不可见的已提交文档”后，还需要在内存中保留modify和extent，使得该page就只能释放少量的内存，但一个表中有很多page，可能某些page满足第一种情况page的modify不包含“部分事务可见的文档”，释放这种page后再次从磁盘中读取的代价较低，优先被逐出。

读取逐出的page

根据内存使用率低逐出和内存使用率高逐出的结果，逐出后的page有以下三种形式： 1) page的modify和extent仍然在内存中 2) page的extent在磁盘文件tablename.wt中 3) page的extent在磁盘文件tablename.wt中，modify在表WiredTigerLAS中

第1种情况最简单，操作直接访问内存中page的文档即可。第2种情况需要先从磁盘上的tablename.wt文件中读出extent并关联到page上，然后才能访问。第3种情况在第2种情况的基础上，还要从表WiredTigerLAS中读取出该page的所有相关文档，并重建出page的modify。

LAS逐出

las逐出既然可以确保清理内存中的page，为什么内存高逐出方法不都采用las逐出呢？一方面是因为wiredtiger只有redo日志，要求文档只有提交后才能被持久化，而las逐出的文档在写入表WiredTigerLAS后就可以被持久化，所以包含“部分事务可见的未提交的文档”的page不可以执行las逐出。另一方面las逐出的代价较高，需要将“包含部分事务可见的已提交的文档”和“所有事务可见的已提交文档”一个一个写入表WiredTigerLAS中，后续若有操作访问该page时，还需要一个一个文档从表WiredTigerLAS中读取出来，所以基于读写性能考虑，进行las逐出的条件很苛刻。

las逐出不仅要page符合las逐出的条件，而且要整个cache的使用也符合las逐出的条件。先看下整个cache使用所需符合的las逐出条件：内存卡主超过2s（内存卡主是指 内存使用率bytes_inmem/cache_size > eviction_trigger/100 或 脏页使用率bytes_dirty_leaf/cache_size > eviction_dirty_trigger/100) 或 近期逐出的page更适合做las逐出（page中“部分事务可见的文档”/“在内存中未持久化的文档”>80%）。而page需符合las逐出的条件是page逐出不需要分页，且page的modify中所有文档都是“已提交的文档”。

las逐出过程通过cursor，在一个事务中将一个page的modify中“包含部分事务可见的已提交的文档”和“所有事务可见的已提交文档”写入表WiredTigerLAS。为了便于之后读取或者清理表WiredTigerLAS中的数据，写入表WiredTigerLAS的文档格式除了包含原始的key和value外，还需要保存更多的数据，如下图所示。page在las逐出时会有一个唯一的las逐出自增id，便于读取page时查找。page在las逐出时是先按照key从小到大遍历，对于每个key又按照update从新到旧遍历，且每个key最新的update类型会特殊标记为BIRTHMARK（例如文档{Key1,Value1-3}和{Key3,Value3-1}的类型），为了让las清理便于识别不同key的分界点。

表WiredTigerLAS文档的key：las逐出自增id，btree的id，本次las逐出的序号，原始key 表WiredTigerLAS文档的value：update的事务id，update的事务开始时间，update的事务持久化时间，update的事务状态，update类型，原始value wt las 为了性能考虑，使用了read uncommited隔离级别（由于read committed需要访问全局事务表，来分析哪些事务可见）。las逐出一个page的所有文档时，是放在一个事务中的，为了保证原子性。

LAS清理

las清理的目的是为了确保WiredTigerLAS文件大小不会持续增加。las清理线程每隔2s会通过cursor遍历一遍表WiredTigerLAS，当它发现标记为BIRTHMARK的update时，它会检查该update对应的文档当前是不是所有事务可见的，如果是的话，那么就删除该key对应的update列表。

由于las逐出和las清理可能并发执行，如果las清理也使用read uncommited隔离级别，就可能导致las清理该key的update列表中的部分update的情况（例如清理了{Key1,Value1-3}，保留了{Key1,Value1-2}）。这是因为当las逐出在一个事务中先写完{Key1,Value1-3}时，las清理就能看到刚写的{Key1,Value1-3}，这时如果发现{Key1,Value1-3}已经全局可见了，las清理就会清理update列表，而这时只清理{Key1,Value1-3}，等las清理完并遍历到下一个key后，las逐出才继续写了{Key1,Value1-2}，这样就导致在表WiredTigerLAS中残留value1-1的情况。

这样之后访问该page时会出现读不到{Key1,Value1-3}，只能读到{Key1,Value1-2}的情况，造成数据不一致（虽然在extent中有{Key1,Value1-3}，但查找时会优先访问modify中的文档），所以las清理要使用read commited隔离级别。