论文阅读笔记整理（持续更新）

KV存储

DyTIS: A Dynamic Dataset Targeted Index Structure Simultaneously Efficient for Search, Insert, and Scan

EuroSys 2023 Paper 泛读笔记

针对复杂数据集的索引，如何同时高效的支持搜索、插入和扫描。本文提出DyTIS：基于可扩展哈希结构，利用数据集键分布的累积分布函数（CDF），并随着数据集的增长学习和调整其结构；通过自然键顺序对键进行分组，并在每个存储桶中按排序顺序维护键，以支持哈希索引的扫描操作；通过重映射函数，将非均匀密钥重新分配到均匀分布中，同时保持密钥的自然顺序。

SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage

FAST 2021 Paper 泛读笔记

针对NVMe SSD和SATA SSD结合的异构存储系统，优化基于LSM-tree的KV存储。作者提出将大部分数据存储在SATA SSD上，将LSM树的顶层和预写式日志（WAL）存储在NVMe SSD上；通过SPDK实现快速且并行的访问，绕过Linux I/O堆栈，优化WAL写入；设计基于轮询I/O的异步请求处理流水线，去除了不必要的同步，将I/O等待与内存处理重叠，并自适应地协调前台/后台的I/O；根据KV工作负载自适应地对数据分区，利用SATA SSD的带宽缓解写放大。

ROART: Range-query Optimized Persistent ART

FAST 2021 Paper 泛读笔记

针对NVM场景下的持久存储设计，如何同时实现功能性（可变大小的key和范围查询）、性能（低持久性开销）、正确性（异常处理和内存安全）。作者提出基于基数树的持久索引：为了优化范围查询：提出叶子压缩方法，延迟了叶分割，并将多个叶节点压缩成一个叶数组；为了优化持久性开销：提出条目压缩，将关键字和子指针组合在一个8字节的条目中；为了优化持久性开销：选择性元数据持久化，以减少要持久化的元数据树量；为了优化持久性开销：提出最小有序分割，放松分割操作中的步骤顺序以减少sfence指令的数量；为了正确性：设计了快速的内存管理以防止内存泄漏，同时进行崩溃后垃圾收集，在恢复期间执行后台GC时，索引可以同时处理前台请求，实现立即重新启动服务。

KVIMR: Key-Value Store Aware Data Management Middleware for Interlaced Magnetic Recording Based Hard Disk Drive

ATC 2021 Paper 泛读笔记

针对基于IMR的HDD上的基于LSM-tree的KV存储优化。作者提出KV存储和HDD间的中间件：采用了压缩感知的路径分配方案，在保持数据文件（SSTables）同时最小化耗时的RMW，在压缩过程中有效地访问数据文件，补救了吞吐量下降，并提高了压缩效率；利用了合并RMW方法，以提高将KV存储系统的多路文件持久化到IMR路径的效率，其关键思想是将多个逐轨RMW重新排序为一个合并的RMW，同时仍确保崩溃一致性。

REMIX: Efficient Range Query for LSM-trees

FAST 2021 Paper 泛读笔记

针对LSM树同时优化读写性能的问题，现有方法通过压缩提升读性能，但会导致读放大或写放大。作者利用新存储硬件的性能，随机读和顺序读性能相近，因此提出构建逻辑排序视图优化范围查询，因为减少了真正的压缩操作，同时减少了写放大。

Differentiated Key-Value Storage Management for Balanced I/O Performance

ATC 2021 Paper 泛读笔记

同时优化LSM-tree的读、写、范围查询性能。作者提出使用传统的LSM树管理键，在LSM树的每个级别内具有完全排序，同时以一种协调的方式管理值，使其相对于键的完全排序具有部分排序的顺序，以保持高扫描性能；通过状态感知的惰性GC方案来实现高空间效率和高性能；提出了细粒度的KV分离，区分小型、中型和大型KV对的管理，以实现混合工作负载下性能平衡；提出了热感知多日志设计，用于有效管理大型KV对。

ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems

FAST 2023 Paper 泛读笔记

针对分离式内存系统中，KV存储性能不高的问题，由于内存节点资源有限，现有方法难以直接修改B树或学习索引的模型。作者提出提出了ROLEX，一种可扩展的面向RDMA的有序键值存储，使用分解存储系统的学习索引。包括几个优化点：插入和再训练操作解耦，使计算节点能够直接通过单边RDMA动词修改远程数据，而无需再训练模型，提高可扩展性；其他计算节点通过具有一致性保证的旧模型来识别新修改的数据；异步使用专用计算资源重新训练模型，以提高模型的准确性。

ADOC: Automatically Harmonizing Dataflow Between Components in Log-Structured Key-Value Stores for Improved Performance

FAST 2023 Paper 泛读笔记

对LSM-KV中写停顿现象进行分析，发现之前的分析原因是有效的，但并不普遍适用。通过实验分析写停顿的原因是数据溢出，指由于数据流入其中一个组件而导致LSM-KV系统中一个或多个组件迅速扩展。提出了ADOC（自动数据溢出控制）的调整框架，在组件之间平衡和协调数据流，以调整系统配置：线程数和批处理大小，而不是简单地等待溢出的数据按默认方式消耗。从而缓解写停顿的问题。

RubbleDB: CPU-Efficient Replication with NVMe-oF

ATC 2023 Paper 泛读笔记

在包含多个数据副本的KV存储系统中，如何减少压缩的CPU利用率。作者利用网络和NVME-oF，在单个节点上压缩，压缩后传输到其他复制节点上。为了实现文件系统的同步，提出为数据预分配固定的磁盘空间，通过维护映射表确保复制节点的文件系统同步。为了实现应用级同步，提出在副本之间应用版本编辑顺序的方法，确保各复制节点执行顺序一致，避免删除导致的节点间不一致问题。

All-Flash Array Key-Value Cache for Large Objects

EuroSys 2023 Paper 泛读笔记

针对AFA规模的KV缓存系统，用于大型对象。针对三个挑战：（1）庞大的元数据导致的高索引开销，（2）过期对象造成的空间浪费，（3）频繁的SSD故障导致的服务中断。为了解决这些问题并提高缓存命中率，提出三种技术：无视冲突的两级哈希表，使用紧凑的每个对象 16B 元数据，将整个哈希表存储在 SSD 中，将热门条目通过组相连缓存在 DRAM 中；近似TTL管理，将 TTL 相似的对象存储到同一空间，使用粗粒度分组快速识别过期对象；反应式容错机制，跨分片缓存空间处理故障，仅在故障显现时处理，将分片与故障隔离来保持高可用性，无需奇偶校验的开销。

Vigil-KV: Hardware-Software Co-Design to Integrate Strong Latency Determinism into Log-Structured Merge Key-Value Stores

ATC 2022 Paper 泛读笔记

针对生产环境的日志结构合并的键值存储（LSM KV），如何保证确定性的延迟。作者提出硬件和软件协同设计的框架：通过启用可预测的延迟模式（PLM）接口，在特定的时间窗口强制执行确定性的读取延迟；在系统级别上，通过在多个物理功能内部调度 PLM 的不同设备状态，来隐藏与 SSD 的内部任务和/或写服务相关的非确定性时间窗口；进一步调度压缩/刷新操作和客户端请求，将强大的延迟确定性集成到 LSM KV 中。

Tebis: Index Shipping for Efficient Replication in LSM Key-Value Stores

EuroSys 2022 Paper 泛读笔记

针对包含多个数据副本的KV存储系统，如何减少压缩和CPU利用率。作者提出只在主节点进行压缩，并将预构建的索引发送到备份节点，减少备份节点的I/O放大、CPU开销和内存利用率；提出备份节点上索引的高效重写机制，通过创建主备节点间段的映射，通过映射重写备份中的设备位置；利用RDMA进行数据传输，减少CPU开销和通信操作。

Building an Efficient Key-Value Store in a Flexible Address Space

EuroSys 2022 Paper 泛读笔记

针对数据管理应用程序需要按序排序数据，但现有文件系统无法支持原地更新，导致大量的数据重写和为支持原地更新的额外间接层开销。本文提出基于B+Tree优化的FlexTree，将地址空间移动时间减少到