- osdi’23分离式内存中的ART树设计
论文题目：SMART: A High-Performance Adaptive Radix Tree for Disaggregated Memory
背景介绍
分离式内存的设计构思是通过把计算节点和内存结点进行池化，通过高速网络（RDMA）进行连接，最终实现数据的高速访问。现有的分离式内存索引结构都是基于b+树开发的，但是b+树会带来读写放大（具体表现为在定位一个键值对时需要层层访问b+树中间节点给计算节点侧）。为了实现本次设计，需要解决三个现有问题：
- 已有的基于锁结构的ART树设计不能够在分离式内存中获得很好的性能表现。使用RCU机制会导致频繁的地址修改（主要是在写入操作发生时）。
- 在并发访问ART树时，会发生过多的层级节点访问，造成了带宽浪费。
- ART树在计算节点端建立的缓存会很容易发生失效（比如节点的扩容或者缩容导致节点地址发生变化）。
动机分析
主要探究了sherman中的b+树的写放大情况。发现art树相比于b+树以及sherman中优化后的b-link树都有更小的读写放大表现。为了实现在分离内存中的ART树索引的构建，需要具体的解决三个问题：
- 基于锁控制的ART有着很差的写性能。简单来说，ART树在发生写入操作的时候会产生大量的异地更新操作（原子变量更新带来的）。这会最终导致热数据条目的缓存失效。
- client端有很多冗余的io请求，比如多个客户端同时请求同一个数据条目。
- art树结构变化带来的缓存失效问题。
SMART设计
针对动机中提出的三个问题，SMART提出了对应的解决方案：
- 上层节点使用了无锁化结构，叶子节点使用了锁结构保证并发。
- 提出了RDWC解决冗余io。
- 设计了一套缓存方案。
内部结点的无锁化结构实现
常见的art树节点通过把部分键和指针分开进行存储，这会导致一定程度上的读放大。通过把部分键嵌入进插槽中来保证发生修改操作的时候能够做到同步修改。内部节点没有使用锁结构
叶子结点的锁实现
通过一个checksum区域来实现乐观锁机制，主要解决了读写冲突。在写写冲突，使用了一个标记位来保证。
RDWC机制
类似于乐观锁的设计思路。通过在计算侧维护了一个基于哈希的表结构，通过给多个相同哈希值的key分配一个本地锁。在发生读写请求时，会把对应key的本地锁上锁，如果有其他的请求访问了这个本地锁，首先会检查当前获取锁的key与本次请求的key是否相同，如果不相同就正常发出远程的读写请求给内存侧。
- 读委托操作：第一个获取本地锁的读请求所在的客户端会被选举出来作为和远程内存侧通信的客户端，其余的都会被放在等待队列中等待。整个过程更像是第一次缓存失效（获取锁的客户端）以及延迟缓存命中的过程（等待的客户端）。
- 写合并操作：在每个计算节点上都建立了一个合并缓冲区。当发生了一个key的写入操作时，首先会添加进入本地缓冲区中，接着执行远程的叶子节点定位操作并进行上锁。当这些操作完成后，才会把整个合并缓冲区对该key进行写入的操作进行合并，通过一次写入操作就可以完成。
为了保证写后读的数据正确性以及读写操作的公平性，会让读写请求平等的去竞争本地锁，这样就能够保证读写请求落在了两个没有重叠的时间段中。
ART索引cache设计
通过在每个计算节点建立一个本地art上层的局部缓存来减少网络开销。
测试结果
大部分的测试和Sherman比较类似，唯一令人疑惑的点在于范围查询的时候，SMART仅仅是通过增加calue的大小来证明自己的范围查询优势，此外，测试仅仅使用了两台物理节点，不知道是否会对结果产生一定的影响。