论文阅读 | SMART：A High-Performance Adaptive Radix Tree for Disaggregated Memory
文章提出了一个适用于分离式内存架构的基数树。主要工作由复旦大学和华为云完成，发表于OSDI'23。
Paper Link: https://www.usenix.org/conference/osdi23/presentation/luo
Open Source: https://github.com/dmemsys/SMART
分离式内存（Disaggregated Memory，DM）最近几年发展得如火如荼，先前已经有不少研究探讨DM上的索引结构了。B+树作为使用最广的索引结构，自然已经有人研究过怎么将它适配于DM，比如说Sherman。
但是B+树也有它的问题：读写放大。这一点主要体现在对叶子节点的读写上，B+树的每个叶子节点保存了多个Key-Value（KV）对，运行在计算节点上的进程要搜索某一个Key时，得把整个叶子节点都读回来。假设一个叶子节点包含了32个KV对，那就有32倍的读放大。写放大也是一样的道理。尽管Sherman对B+树的写做了优化，解决了写放大问题，但读放大问题依然存在。读写放大问题在DM架构上的影响还是非常明显的，毕竟浪费的是网络带宽。文章就做了些实验比较Sherman和ART（SOTA基数树），总结了两个结论：
B+树的吞吐量受到了带宽的限制。这一点可以很容易从图1的(a)和(b)看出来，随着客户端数量上升，Sherman的吞吐量首先达到上限，ART的吞吐量上限是Sherman的两倍还多。而且单个叶子节点存放的KV对越多，Sherman的吞吐量越低。可能大伙觉得，多读回来的数据可以作为缓存啊，这不就把读放大问题完美解决。但是实验(c)显示，即使给到了600MB的缓存，吞吐量依然受限于网络带宽无法继续提升（文章没有做解释）。相反，ART的吞吐上限受制于RNIC的IOPS，比Sherman好很多。
网络拥塞的提前发生加剧了B+树的延迟。在相同吞吐量下，由于读写放大，Sherman占用的网络带宽比ART高得多，这导致了网络拥塞提前发生。一旦网络拥塞发生，延迟就开始提高了。从实验(d)可以看出来，Sherman的P99延迟增长速度是相当快。
基于这两个观察，文章就得出一个结论：比起B+树，基数树更适合用于DM架构。当然ART也不是完美的，要想将ART适配于DM架构，仍然有三个问题需要解决：
有锁并发控制导致写性能低下。现有的ART都使用了有锁并发控制来实现同步。但是在DM架构上，锁操作开销是很大的，每一次锁操作都是一次网络往返（RDMA_CAS）。而且，忙等待之类的锁冲突机制还会在上锁失败时不断重试，进一步加剧RNIC的IOPS浪费。一个可能的解决方案是设计无锁算法。但是无锁算法依赖于out-of-place的更新模式（只更新8字节地址保证更新的原子性）。但是这种更新模式又会导致计算节点本地缓存的频繁失效，造成缓存抖动问题。
同节点客户端的重复I/O浪费RNIC的IOPS。前面有提到，ART能够突破B+树受到的带宽限制，但依然受限于RNIC的IOPS。IOPS吃紧的情况下，还是有浪费的情况。比如说，位于同一个计算节点的多个客户端，要读内存池的同一个KV对，每个客户端都会发起一个网络I/O，这种不必要的重复I/O就是对IOPS的严重浪费了。写也是同理。
ART的结构特征加剧了计算端缓存失效问题。路径压缩和适应性节点（根据需要修改节点内指针数组长度）是ART降低内存开销重要的结构特征。但这就会引入ART内部节点父子关系的变化或节点类型变化等等问题，进而引入计算端缓存失效的可能性。如果没有合适的判别机制，可能会导致错误的数据访问。
本文就针对前面提出的三点挑战，进行了针对性设计，提出了SMART，一个面向DM架构的高性能ART。
SMART
SMART针对三点挑战，分别提出了三个设计来解决问题。
层次化的ART并发控制
SMART的节点被分为内部节点（Internal Node）和叶子节点（Leaf Node）两种。所谓层次化的并发控制，意思就是内部节点采用无锁并发，而叶子节点采用有锁并发。
内部节点主要由三个部分组成。第一部分是Reverse Pointer，这里存储指向父节点的指针；第二部分是Header，存放了当前节点深度Depth、节点类型Typenode（NODE_4/NODE_16/NODE_64/NODE_256）、压缩的Partial Key数组和当前数组大小Sizearray；第三部分就是Slot数组，保存了子节点的信息，每个Slot由对应Partial Key、是否为叶子节点的标记位Leaf、子节点类型Typenode（若为内部节点）或子节点长度（若为叶子节点），以及48位地址组成。
叶子节点也由若干部分构成，包括指向父节点的Reverse Pointer，用于标记KV是否被删除的有效位Valid，校验和Checksum，固定长度的KV对，以及在尾部的锁Lock。
发现了么？SMART把内部节点的每一部分都设计为了8字节大小，这样就可以直接使用RDMA CAS操作直接原子地进行修改了，不用上锁。而对于叶子节点，仍然采用了锁机制。写者之间会直接用互斥锁进行同步，在写之前进行上锁；读者则采用乐观策略，将节点内容读回后通过校验和检查内容是否一致，不一致则重新读。此外，可以看到SMART将锁放置在了叶子节点的尾部，这样客户端就可以在写回数据的时候顺便释放锁了，因为RDMA保证了写的顺序性，释放锁时前面的数据一定已经完成修改了。
为了更好地展示SMART的各种操作，文章用图展示了对一颗ART树进行一系列操作的变换过程：
读委托写合并
这个机制用于解决同一计算节点上不同客户端对相同Key重复读的I/O浪费问题。
SMART客户端在读时会对Key计算一个哈希值，并且在尝试在本地对这个哈希值上锁，成功上锁的客户端就会开始执行正常的RDMA读流程，并且进入一个读时间窗口（Time Window）。如果上锁失败，则说明这个哈希值已经被其它客户端上锁了，这时候就会去比较被上锁的Key（也就是正在执行读的Key）究竟是不是同一个Key。如果不是同一个Key，那客户端就会直接进入正常的读流程，从内存池读回目标KV对；如果是同一个Key，那客户端就不会去内存池读，而是进入一个等待队列。持有锁的客户端在读回目标KV后，会将它分享给等待队列中的每一个客户端，从而就可以通过一次网络I/O完成多个读操作。
写合并也是差不多的思路。成功拿到锁的客户端会维护一个写缓存（WCB），在写窗口期间，其它客户端对同一个Key的写都会转变成对WCB的写。和读委托稍微不同的是，写时间窗口在持有锁的客户端给目标叶子节点上锁后就结束了。在成功对叶子节点上锁后，持有锁的客户端就会将WCB内的值写入内存池，从而完成写操作。如此一来，多个客户端对同一Key的写也由一次网络I/O完成。
但是简单将读委托和写合并一起实施，也会有问题。例如A发起对K的读，B对K先写后读。A先从内存池读到K的旧值，但数据仍然还在网络通路上。随后B将新值写入内存池，然后发起读加入等待队列。A读的数据返回计算节点，分享给B，此时从B的视角看就是写入的新值没能成功读回，因果一致性遭到破坏。所以，为了让避免这种情况发生，SMART设计了一种机制，简单地来说，当读写并发的时候，如果写比读先完成（网络先返回），那当读数据返回时，只有写完成之前发起请求的读者可以被共享数据，其余读者需要自行发起网络请求读取新数据。（这一部分论文没有交代清楚，强烈建议看代码是怎么实现的）。
ART缓存
SMART客户端会在本地节点也维护一棵ART缓存树，它的结构如图6所示。缓存树的叶子节点就是缓存条目，缓存了内存池中某个内部节点的信息：深度Depth、节点地址Node Address、以及它的子节点信息Slot数组（这里的Slot和前面提到的内存池的Slot结构一致）。那要怎么判断缓存是否还有效呢？文章分了三大缓存失效场景类型来讨论：
父子节点关系的变化。这种缓存失效类型一般发生在节点分裂。验证方法是根据缓存条目的目标Slot读回目标节点数据，然后比较读回数据中的Reverse Pointer和缓存条目的Node Address是否相同，即可判断缓存是否失效。
节点类型发生变化。验证方式是，根据缓存条目的目标Slot读回目标节点数据，查看读回数据中的Typenode和缓存中的Typenode是否相同，即可判断缓存是否失效。
节点是否删除。对于内部节点，验证读回的数据中Typenode是否为NODE_0，判断节点是否已删除；对于叶子节点，验证读回数据中的Valid位，以判断节点是否已删除。
实验
直接看论文吧。
结论
文章针对DM架构上B+树读写放大严重的问题，设计了适用于DM架构的基数树SMART。其中精心设计了树的节点数据结构，使得内部节点可以利用RDMA CAS操作实现无锁并发控制。同时为了保留对叶子节点的in-place-update更新模式，对叶子节点的更新仍然采用有锁并发控制，但是将锁放置在节点最后，利用RDMA更新的顺序保证，优化网络I/O次数。
比较亮眼的是读委托写合并机制，这个实打实降低了对热点Key访问的网络I/O次数，最重要的是这个机制对上层是透明的，可以移植在其它场景下，优化网络I/O。