Eviction
Evict的实质主要是将内存中的page淘汰出内存，简单来说，当cache里面的“脏页”达到一定比例或cache使用量达到一定比例时，wt就会触发相应的evict page线程来将pages（包含干净的pages和脏pages）按一定的算法（LRU队列）淘汰出去，以便腾挪出内存空间，保障后面新的插入或修改等操作。
这个流程中存在两个淘汰队列分别为待淘汰的填充队列（evict_fill_queue)和当前淘汰队列（evict_current_queue)，evict会不断地将符合淘汰条件的page交替待淘汰queue，然后会从淘汰队列中将page淘汰出内存。待淘汰queue和当前淘汰queue角色会进行切换。
Evict有两种触发方式，一种是WiredTiger内部线程触发，另一种为用户操作（search/insert等）触发，这里我们将两者分别称为内部evict与外部evict，本文主要介绍内部evict。
首先来了解一下cache所管理的空间。
WT cache管理的空间就是内存page的内存空间，page的内存分为几部分：
- 从磁盘上读取到的已经刷盘的数据，即前文描述的dsk内存缓存。
- Page在内存中新增的修改事务数据。
- Page基本的数据结构所有的内存空间。
WT维护了每个page的内存总量，总的内存使用量mem_size，以及增删改造成的脏页数据总量dirty_mem_size。每次对页进行载入、增删改、分裂和销毁时对上面的数据做原子增加或者减少计数，这样可以精确计算到当前系统中WT引擎内存占用量。
那么结合cache所管理的空间，这里简要介绍page eviction相关的几个参数：
| 参数名称 | 默认配置值 | 含义 |
|---|---|---|
| eviction_target | 80 | 当cache使用量达到该百分比时触发内部evict，能够淘汰clean page |
| eviction_trigger | 90 | 当cache使用量达到该百分比时触发内部或外部evict，能够淘汰clean page |
| eviction_dirty_target | 5 | 当cache“脏”数据量达到该百分比时触发内部evict，只能淘汰dirty page |
| eviction_dirty_trigger | 20 | 当cache“脏”数据量达到该百分比时触发内部或外部evict，只能淘汰dirty page |
| memory_page_max | 5MB | 内存中page允许的最大数据量，但并不是严格控制的 |
外部evict
当用户操作（insert/search等）开始某事务时将调用cache check（__wt_cache_eviction_check)函数判断是否触发全局的evict（可以理解为触发内部evict），此时需要满足的条件是cache使用量达到eviction_trigger或者cache dirty数据量达到evict_dirty_trigger。
此外，每次需要读取内存page时，可能会对page当前的数据量进行判断，当超过memory_page_max时，如果满足in-memory split的条件时，进行在内存上完成的page split，否则直接在该用户线程上对该page进行evict。
内部evict
内部evict包括page的选取（evict pass）以及page的淘汰（evict page）两个完整流程。
基本思路是一个线程阶段性的去扫描各个btree，并把btree可以进行淘汰的数据page添加到一个lru queue中，每个btree每次扫描最多选取一定数量的page，每个btree扫描结束后记录下btree内当前访问所在的位置，作为下次该btree阶段性扫描的起始位置，并在整个扫描结束后记录下当前扫描的btree对象，作为下次阶段性扫描的起始位置。然后对queue中的数据页按照访问热度排序，当queue中有足够多的page后，各个淘汰线程按照淘汰优先级对queue中的数据页进行淘汰，整个过程是周期性重复。
从线程工作内容来说，内部evict的线程可以分为server线程与worker线程，server线程负责扫描内存中的btree，将符合条件的page加入lru queue，并且在evict很繁忙的时候也会参与page的淘汰；worker线程负责执行page的淘汰，包括内存page的写盘（reconcile）、结构更新等。
server线程与worker线程事实上为一组evict线程，线程通过抢占锁的形式转变为server线程，同一时间只会有一个server线程和多个worker线程。
evict pass策略
前面介绍过evict pass是一个阶段性扫描的过程，整个过程分为扫描阶段、评分排序阶段和evict调度阶段。扫描阶段是通过扫描内存中btree，检查btree在内存中的page对象是否可以进行淘汰。扫描步骤如下：
- 根据上次evict pass最后扫描的btree和它对应扫描的位置作为本次evict pass的起始位置，如果当前扫描的btree被其他事务线程设成独占访问方式，跳过当前btree扫描下个btree对象。
- 进行btree遍历扫描，如果page满足淘汰条件，将page的ref对象添加到evict queue中，淘汰条件为：
- 根据前述触发条件判断clean page/dirty page是否能够淘汰
- 如果page是数据页，page当前最新的修改事务必须早以evict pass事务。
- 如果page是btree内部索引页，page当前最新的修改事务必须早以evict pass事务且当前处于evict queue中的索引页对象不多于一定数量。
- 当前btree不处于正建立checkpoint状态
- 如果本次evict pass当前的btree有超过100个page在evict queue中或者btree处于正在建立checkpoint时，结束这个btree的扫描，切换到下一个btree继续扫描。
- 如果evict queue填充满时或者本次扫描遍历了所有btree，结束本次evict pass。
评分排序阶段是在evict pass后进行的，当queue中有page时，会根据每个page当前的访问次数、page类型和淘汰失败次数等计算一个淘汰评分，然后按照评分从小打到进行快排，排序完成后，会根据queue中最大分数和最小分数计算一个淘汰边界，queue中所有大于淘汰边界的page不列为淘汰对象。
**WT为了让internal page尽量保存在内存中，在评分的时候internal page的分值会加上1000分，让internal page免受淘汰。**事实上，从源码反映出，当internal page的子page仍然alive时，是不允许被淘汰的。
evict page
evict page其实就是将evict queue中的page数据先写入到磁盘文件中，然后将内存中的page对象销毁回收。
page的写过程在WT中称为reconcile。由前文已知，in-memory page与 on-disk extent是不同的数据组织结构，两者的上限在实际场景中也不相同，in-memory page的默认上限memory_page_max是5MB，而on-disk extent的默认上限根据类型不同而不同，leaf extent的默认上限leaf_page_max是32KB，internal extent的默认上限internal_page_max是4KB。如果page的内存空间在reconcile时超过75%的memory_page_max，那么需要page做split操作（为了与in-memory split区分开，这里我们称为on-disk split）。
整个写过程步骤如下：
- 以row array为轴，扫描整个row array（即dsk内存缓冲区）、update list array和insert skiplist array，将每个需要写盘的k/v转换成cell_t对象，并将其依次存入一个缓冲区（chunk）中，该chunk最终将作为extent写入磁盘，因此缓冲区头部会预留page header与block header的空间。
- 判断这个缓冲区是否超出了对应类型的on-disk extent上限，如果超过了，进行on-disk split操作，简单来说可以理解为3～6步
- 根据page对象中的wt_page_header的信息将它对应的信息写入到chunk头位置。
- 选择当前btree文件的空闲块中大小最合适的块，裁选出所需大小的块（如果没有这样的空闲块，那么向文件末尾写入），得到将写入btree文件的偏移地址，计算chunk，也即extent的checksum
- 根据extent的信息填充block_header,将整个extent写入到btree的文件当中并返回extent address。
- 将该chunk加入到一个链表中，并维护该chunk写盘的address cookie
- 重复步骤1～6，直到所有需要写盘的k/v cell_t都完成写盘操作
下图描述了某page完成reconcile后发生的变化：
如上图所示，在page完成reconcile后，由于进行了on-disk split，原page一分为三，原extent由于不再被使用，能够进行回收（磁盘块的管理与checkpoint相关，这里不详细描述）。
每个新page对应盘上新的extent，而新extent的addr与key并没有直接更新到父节点，而是通过off-page addr以及instantiated key的形式保留在内存，并设置父节点为脏节点，当父节点被evict从而reconcile时，再随着父节点写到盘上。当内存用量小时，每个page在reconcile时的chunk能够保留在内存，作为__wt_page的dsk内存缓冲区。
参考文献
袁荣喜.WiredTiger文档.
郭远威.WiredTiger存储引擎系列文章.
阿里云.WiredTiger page逐出.
