论文阅读笔记整理（持续更新）_flor: an open high performance rdma framework over

KV存储

Replicating Persistent Memory Key-Value Stores with Efficient RDMA Abstraction

OSDI 2023 Paper 泛读笔记

针对使用RDMA优化PM KVS的复制，现有方法存在排队延迟和设备级写放大（DLWA）。本文提出了Rowan，通过RDMA单边动词处理PM KVS的复制写入。聚合来自不同服务器的并发远程写入，并以顺序（因此低DLWA）和单向（因此低延迟）的方式将这些写入降落到PM。（1）让接收器端的控制线程以递增的地址顺序将PM驻留缓冲区推入接收队列。发送方只需要为远程PM写入发出SEND，并等待接收方RNIC生成的ACK。（2）利用两个RNIC硬件功能，共享接收队列（SRQ）和多包接收队列（MP RQ），分别合并来自不同连接的写入并支持可变大小的写入。（3）最小化控制线程的任务来简化Rowan的控制路径。

Cooperative Concurrency Control for Write-Intensive Key-Value Workloads

ASPLOS 2023 Paper 泛读笔记

针对键值存储服务的优化，源系统为了高吞吐量，强制通过跨线程分区写入来避免同步，但会造成负载不平衡，在写为主的负载和读写倾斜的负载性能不佳。本文提出C-4，将写入请求分为两类：可以跨线程平衡的独立请求和必须排队的依赖请求。使用NIC动态分区独立写入，以增加当前KVS设计的负载平衡灵活性，并在KVS中添加软件层，将依赖写入压缩为批处理。

A Generic Service to Provide In-Network Aggregation for Key-Value Streams

ASPLOS 2023 Paper 泛读笔记

针对使用网络内聚合（INA）优化分布式键值存储，现有INA方案是一种同步聚合、而且缺乏系统范围的考虑因素。本文提出用于键值流的INA服务ASK，交换机和主机联合设计的系统，可编程交换机提供尽力而为的聚合服务，主机运行守护进程与应用程序交互。ASK针对流量特性、硬件限制和网络不可靠特性进行了深入优化：（1）协同设计交换机内存布局和主机分组，以实现矢量化，并支持可变长度密钥。（2）设计了主机滑动窗口方案和交换机重复数据消除逻辑，以实现可靠性和正确性，并通过重用主机服务中的持久连接，进一步提高了系统的可扩展性。（3）设计了影子复制机制，以周期性地从交换机获取中间结果，并重置交换机内存，从而使热键有第二次机会保留交换机内存。

In-Memory Key-Value Store Live Migration with NetMigrate

FAST 2024 Paper 泛读笔记

针对分布式键值存储在节点之间迁移键值数据，现有方法需要基于源或目的地或额外记录，在迁移过程中进行服务，造成额外延迟。本文提出NetMigrate，不使用额外资源进行迁移记录，核心思想是用网络跟踪迁移过程，因为网络可以查看集群中的所有数据移动。包括三个关键技术：（1）交换机资源有限的情况下跟踪迁移状态。利用概率数据结构，用布隆过滤器跟踪密钥是否已完成迁移，用计数布隆过滤器跟踪密钥当前是否正在迁移。（2）迁移过程中维护数据一致性。设计了一种错误处理方法，如果对数据所有权有绝对的信心，交换机将查询路由到相应的位置；否则，交换机会发出少量复制查询。（3）支持多样化的迁移策略。可以从源端调整其交换机上的数据结构和资源预算，以优化各种性能目标，例如最小化迁移时间和最大化查询吞吐量。

IonIa: High-Performance Replication for Modern Disk-based KV Stores

FAST 2024 Paper 泛读笔记

针对写优化键值存储（WO-KV）的副本管理。现有复制协议：浪费了高写性能，只提供了较低的写吞吐量，因为必须在单个线程上顺序写入；较差的读性能，将读取限制在只访问主副本。本文提出IONIA，利用了基于SSD的WO-KV存储的独特特性优化复制协议。（1）利用接口特性将并行执行推迟到后台，从而实现高吞吐量的一次往返（RTT）写入。（2）在任何副本上进行读取，同时无需强制写入所有副本。为了处理滞后的从副本，对于每个从副本的读取，IONIA在主副本处执行检查（一个元数据查询），以验证从副本返回的结果。（3）为了实现1RTT读取，IONIA将读取发送给从副本，同时将元查询并行发送给主副本。通过客户端一致性检查机制，主副本返回足够的关于正在读取的键的信息，而客户端则决定从副本结果是否为最新。

Calcspar: A Contract-Aware LSM Store for Cloud Storage with Low Latency Spikes

ATC 2023 Paper 泛读笔记

针对亚马逊EBS存储，探索其合同模型和延迟特性，发现超过付费IOPS的请求会显著增加延迟，而LSM存储又会放大工作负载的波动并产生内部请求拥塞。本文对亚马逊EBS下的LSM存储进行优化，来降低尾延迟：（1）利用波动感知缓存，通过热点感知进行主动预取，识别高负载时段的热点，并在低负载时段主动提取热点。通过偏移感知的被动缓存，在高负载期间利用时间局部性来挤出过时的预取数据，并在不发出额外请求的情况下适应热点转移。（2）利用拥塞感知的IOPS分配器为不同的内部请求分配优先级，采用多队列结构防止线程拥塞。通过机会压缩将不同LSM级别的写入请求分配到不同的优先级队列中，从而平衡读取放大和写入节流。

DEPART: Replica Decoupling for Distributed Key-Value Storage

FAST 2022 Paper 泛读笔记

对于KV存储中的副本管理进行优化，现有方法实验同一索引结构中管理所有副本，例如LSM-Tree，会导致复制冗余之外的大量I/O成本。本文提出副本解耦，将主副本和冗余副本分离。使用LSM树管理主副本，以便以更轻量级的方式保留LSM树的设计特性；使用两层日志来管理冗余副本，通过只追加的全局日志保证冗余副本写入速度，将全局日志根据用户需要拆分为多个本地日志，分别优化读（写）性能；按不同的密钥范围组织KV对，将恢复操作限制为仅访问KV对的相关范围，提升故障恢复性能。

Pacman: An Efficient Compaction Approach for LogStructured Key-Value Store on Persistent Memory

ATC 2022 Paper 泛读笔记

设计适合PM的日志结构键值存储Pacman，提出四个优化点：将压缩过程中的引用搜索卸载到服务线程，以减轻繁重的索引遍历开销；利用标记指针来减少高延迟的PM读取，将频繁访问的元数据存储在DRAM中，以减少小的随机PM写入，避免垃圾收集引入过多的PM访问；根据PM特性以批处理模式重新设计压缩管道，以降低持久性开销；以轻量级方式分离冷对象和热对象，以减少压缩中的PM数据复制。

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

EuroSys 2023 Paper 泛读笔记

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

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，同时仍确保崩溃一致性。

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动词修改远程数据，而无需再训练模型，提高可扩展性；其他计算节点通过具有一致性保证的旧模型来识别新修改的数据；异步使用专用计算资源重新训练模型，以提高模型的准确性。

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开销和通信操作。

ChameleonDB: a Key-value Store for Optane Persistent Memory

EuroSys 2021 Paper 泛读笔记

针对PM环境下的KV系统，利用PM的两个特点：作为块设备以256B为单元写入，具有高读取性能。设计了ChameleonDB，为混合内存/存储设备设计的KV存储系统。使用LSM树结构以低写放大的方式高效地接收写入；利用DRAM中的哈希表，以绕过LSM树的多个层级，实现快速读取；在后台维护LSM多级结构，以实现快速的崩溃恢复；使用动态读取保护模式，使用混合结构吸收突发的写入工作负载，避免读取长尾延迟。

Improving Performance of Flash Based Key-Value Stores Using Storage Class Memory as a Volatile Memory Extension

ATC 2021 Paper 泛读笔记

利用存储类存储器SCM（类似PM）优化KV存储的成本，作为DRAM和闪存的中间硬件，保证性能的同时降低成本。作者对Facebook上的所有基于闪存的KV存储部署进行分析，确定优化目标，为优化读性能；确定了RocksDB最大的内存消耗组件，用于提供读请求的块缓存，设计利用DRAM和SCM的延迟差异的混合分层缓存。DRAM充当第一层缓存，存储频繁访问的数据，SCM充当第二层缓存，存储不太经常访问的数据；设计了管理DRAM和SCM之间数据传输的缓存接纳和内存分配策略。

日志结构存储

MiDAS: Minimizing Write Amplification in Log-Structured Systems through Adaptive Group Number and Size Configuration

FAST 2024 Paper 泛读笔记

针对日志结构存储GC开销高的问题，如何降低写放大。本文提出MiDAS，采用多组的链式结构，按年龄隔离数据块。（1）使用分析模型，更新间隔分布（UID）和基于马尔可夫链的分析模型（MCAM），根据工作负载I/O模式动态调整组的数量及其大小，从而最大限度地减少数据块的移动。（2）将热块隔离到专用的HOT组，其中的HOT大小根据工作负载进行动态调整，以最小化总体写放大。

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

EuroSys 2022 Paper 泛读笔记

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