uTree：把整颗B+树放进内存里

这是一篇2020年发表在VLDB上的文章：uTree: a Persistent B+-Tree with Low Tail Latency。主要讲了B+树结构的优化。此前其实以及有很多文章基于新的存储介质PM对B+树结构索引的优化，但大多数优化都着重于减少对于NVM flush的次数，而这篇论文则从一个新的角度进行了优化。

本文仅作为读书笔记使用，有兴趣的同学推荐去看一看原文，里面的一些idea还是非常新颖的。

0.前情提要：

1. PM 的性能

PM在读上的性能，几乎可以媲美DRAM，但是它的性能是非对称的（asymmetric），这也就表明了它虽然读性能优秀，但是写的性能则相对而言较为拉跨。根据文章中对傲腾的设备进行测试表明，读的带宽可以来到39GB/S，而写的带宽最大也只有13.2GB/s。

2. B+ 树在PM上的 tail latency：

首先说一下tail latency的定义

Tail latency, also known as percentile latency, refers to latencies clients see fairly infrequently.

意思就是说那么少见的但又很大的延迟，基本可以理解为一批操作里面回馈最慢的那几个。举个例子，比如说你用知乎的搜索引擎搜了好几次东西，然后有几次的反馈慢的离谱，这个就是tail latency。

OK，回到B+树，导致中B+树索引中的tail latency的原因主要有两个。

一个叫做结构优化操作（structual refinement operation，SRO），用人话就是说你树里面节点（无论是internal node还是leaf node）中的那些数据都是存储在一个连续的空间里头的，然后为了搜扫的高效性，这些东西都必须是有序的，而维护一个有序的线性表的开销其实是很高的，需要不断地shift数据；还有与它类似的就是结构变化上的操作，比如merge和split，这个也会引起数据的改动，但是相比于SRO而言并没有那么频繁。

还有一个东西叫做并发，这玩意儿就很好理解了，两个线程都要改一个东西，那其中一个肯定得等另一个改完了再去改啊。这个在DRAM上还不算太大的事情，毕竟DRAM的写性能也很好，但是在PM上就成为了性能瓶颈之一了（毕竟PM的写性能只有读性能的1/3），你写的慢，另一个线程等的时间也就越长。

这两个东西，导致了B+树在PM上的性能非常不稳定，如果SRO出现和线程竞争出现的少，那么表现得就好，但是如果一批操作中有若干个操作触发了SRO，那么整体得表现就会大打折扣。

1. uTree的设计

2.1 uTree的结构

uTree采用了一锅端的结构：它把整颗B+树都放进了DRAM里面。那你肯定要想，掉电怎么办？系统崩溃怎么办？OK，它给所有的叶子节点又做了一层链表，称为shadow array list层，里面存放着key和value，并存放在PM中。B+树的叶子节点中的指针指向这array list。如下图所示：

所有的实际数据都被持久化在PM中，当系统崩溃时可以利用PM中的数据在DRAM中重构这颗B+树。

讲完结构之后我们在来聊一聊如何在uTree上进行增删改查。

2.2 uTree的使用流程

这里仅讨论单线程情况下的流程，并发控制会在之后再聊。

• Put 操作

1. 通过B+树索引找到在array list中的插入位置
2. 在PM中的array list中插入这个数据
3. 修改DRAM中的B+树索引

如下图所示：

• Get 操作

直接通过DRAM中的B+树索引去找PM中对应得array list的entry，找到就返回，没找到就返回空。

• Delet操作

delete的过程和Put的过程非常相似，直接上图：

• scan 操作

scan 操作和传统的B+树本质上没有区别。

uTree首先通过DRAM 中的B+树结构找到大于等于start key的key，然后在PM层的list 中不断使用next指针去访问下一个entry，直至query 结束。

2.3 uTree 的 tail latency

OK，讲完结构和操作流程，再来聊一聊为什么这样设计可以减少tail latency。

可能你已经发现了一点，减少tail latency 的核心就是减少在PM上的SRO。

首先把整颗B+树放在DRAM中，由于DRAM的写性能要大大好于PM，所以BP树部分的SRO开销自然就减少了。但是在PM中的link list部分呢？那部分新加的链表难道不会增加额外的开销吗？

这时候就要聊到链表和线性表的不同了。对于一个有序的有n个元素的线性表（即占连续内存的表），插入一个新entry后，为了维护其有序性，需要不断地对原有的项进行移动，这个开销平均下来是O(n/2)。那么链表是多少呢？精通初级数据结构的你肯定知道是O(1)。所以这样，在PM上的开销就很好的节省了下来。

这个idea确实非常的简单，但又非常精彩，有点大道至简的味道。

2. 并发控制

文章提出了一种叫做 Coordinated Concurrency Control的方案来做并发控制，名字太长太复杂了，直接来看系统遇到并发问题的时候怎么做。

这部分可能比较枯燥，但并不复杂，很容易就可以想明白，当然前提是你有一点关于并发控制的背景知识。

两个线程（一黑一白）同时在一个leaf node上插入值。

首先它们在step 1中通过B+树获取了各自的pointer，这里使用乐观并发控制，并不需要加锁。随后在setp 2系统使用CAS指令将新建节点插入link list中（即修改新建节点 predecessor的next 指针），这里有一点需要注意的是，CAS只允许一个线程修改一个值，同时如果这个值和它预取的值不一样，那么这次修改就会失败。这也就是说，如果之前已经有一个线程完成了link list的修改，同时还没有来得及在array layer中完成第三步（回忆put操作，在B+树索引中的修改永远放在最后进行）

那么这个线程的操作就会失败，随后重头再来。（这边很难用较短的篇幅讲清楚，当然和本人语文水平也有关系）。最后在step 3中，两个线程获取当前leaf node的锁，并对leaf node进行修改。

由于加锁的操作都是在DRAM中进行的，所以程序运行的效率变得更高：

• Put Delete 冲突

线程A想要插入一个 list node，但是它的predecessor 已经被线程B删除，同时在线程A扫描索引前并没有完成在索引中的跟新，这时候就发生了Put Delete 冲突：

uTree的解决方案是在PM 的list layer每一项的pointer部分中embed一个delete bit，线程在实际删除这个node之前首先修改这个bit。当一个node在link list插入时，先检查它的predecessor的delete bit是否为0，如果为1，说明它已经没了，则从头开始进行插入操作（retry）。

许多B+树都采用乐观并发控制，给树的叶子节点加上一个version。uTree也采取了类似的操作，但是它们的这个version filed移动到了PM的link list的next pointer 里面。注意：64位linux 系统中的指针是8byte的，但实际有效位只有后面6个byte，剩下的两个byte可以拿来做各种优化：

当我们进行get操作的时候，首先检查这个node的version field，如果是奇数的话，则说明有其他线程正在写这个list node，直接进行retry，如果是偶数的话，则可以直接进行读取。

在我们进行update操作时，同样首先检查version filed，如果发现是奇数，则说明有线程正在对这个node进行修改，retry，如果是偶数的话，则将version filed+1，随后进行修改，修改完成后再+1.（一共加两次，保证consistency）

上述的操作就保证了一个node的version field是奇数时，有且只有一个线程在修改它；当version field是偶数时，读写操作都不会在上面被阻塞。