FASTER 研究论文导读：从 SIGMOD 核心 KV 存储到 CPR 恢复、弹性扩展与缓存优化的论文

数据库
缓存
KV存储

【免费下载链接】FASTER

Fast persistent recoverable log and key-value store + cache, in C# and C++.

项目地址：https://gitcode.com/gh_mirrors/fa/FASTER

导读：本文围绕仓库官方研究索引页 docs/_docs/95-research-papers.md 展开，完整梳理 FASTER 项目十年研究脉络中的 10 篇代表性论文，涵盖核心系统、单机恢复、扩展性、分布式恢复、缓存与二级索引六大主题。同时给出每篇论文在当前 C#/C++ 仓库中的对应实现路径、关键 API 与测试用例，帮助读者建立"论文概念 → 源码证据"的双向映射，快速上手源码阅读与二次开发。

论文索引总览：官方按主题分组的 FASTER 研究路线图

95-research-papers.md是 FASTER 文档站"Technical Details（技术细节）"版块下的官方论文索引页，与 90-td-introduction.md（技术细节入口，其中收录了主论文与恢复论文的入口链接）同属一个系列。该页面按6 个研究方向、收录了2018—2022 年间 10 篇论文，每一篇都与仓库中可定位的具体实现一一对应：

主题	论文	发表场合	仓库对照
核心系统	FASTER: A Concurrent Key-Value Store with In-Place Updates	SIGMOD 2018	FASTER.cs、LightEpoch.cs
核心系统	FASTER: An Embedded Concurrent Key-Value Store for State Management	PVLDB 2018	同上（系统论文的期刊版）
核心系统	Performant Almost-Latch-Free Data Structures Using Epoch Protection	DaMoN 2022	LightEpoch.cs、EpochProtectedVersionScheme.cs
单机恢复	Concurrent Prefix Recovery: Performing CPR on a Database	SIGMOD 2019	Recovery.cs、IndexRecovery.cs
扩展性	Achieving High Throughput and Elasticity in a Larger-than-Memory Store	PVLDB 2021（arXiv:2006.03206）	CacheStore 示例、ResizableCacheStore 示例
分布式恢复	Asynchronous Prefix Recoverability for Fast Distributed Stores	SIGMOD 2021	cs/remote（FASTER.server / FASTER.client）
缓存	CompuCache: Remote Computable Caching using Spot VMs	CIDR 2022	读缓存（ReadCache）设施与缓存示例
缓存	Redy: Remote Dynamic Memory Cache	PVLDB 15(4), 2022	同上
二级索引	FishStore: Fast Ingestion and Indexing of Raw Data（demo）	VLDB 2019	关联研究系统（仓库内未含实现）
二级索引	FishStore: Faster Ingestion with Subset Hashing	SIGMOD 2019	同上

原文档在每篇论文后附有 PDF 外链（微软研究院 / arXiv / 作者主页）。本文不重复输出外部链接，读者可回到原文档页 95-research-papers.md 获取全文，这里聚焦论文主题与仓库源码的对应关系。

核心系统：FASTER 的两篇奠基论文与无锁化数据结构的证明

文档"Core FASTER System"小节收录了三篇论文，构成了整个项目最底层的技术支柱。

论文 1：FASTER 主论文（SIGMOD 2018）

Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, Mike Barnett.FASTER: A Concurrent Key-Value Store with In-Place Updates. 2018 ACM SIGMOD International Conference on Management of Data (SIGMOD '18), Houston, TX, USA, June 10, 2018.

论文 2：嵌入式系统版（PVLDB 2018）

同一作者团队。FASTER: An Embedded Concurrent Key-Value Store for State Management. PVLDB 2018, Rio de Janeiro, Brazil, August 2018.

论文 3：Epoch 保护机制（DaMoN 2022）

Tianyu Li, Badrish Chandramouli, Sam Madden.Performant Almost-Latch-Free Data Structures Using Epoch Protection. DaMoN, 2022.

论文要义：混合日志 + 就地更新 + 无锁并发

FASTER 论文提出的核心模型是：一个主哈希索引叠加在一条横跨内存与磁盘的 hybrid log（混合日志）之上。写入路径支持in-place update（就地更新），即对热数据直接在现有位置修改而不是追加，从而同时获得内存 KV 存储的读性能和日志型存储的写吞吐；当内存不足时，数据以 page 为单位换入换出到外部存储（本地磁盘或云端）。这正是文档 25-fasterkv-recovery.md 开头所复述的架构描述："FASTER basically consists of a primary hash index operating over a hybrid log that spans disk and main memory"。

在 C# 仓库中，这一模型的落点清晰可循：

顶层入口 FASTER.cs 定义FasterKV，其 Checkpoint/Recover 系列公开 API 正是论文"checkpoint-based recovery"的实现面：
- TakeFullCheckpointAsync/TakeIndexCheckpointAsync/TakeHybridLogCheckpointAsync（FASTER.cs#L312-L409）；
- Recover()的多个重载（FASTER.cs#L427-L479）；
就地更新与 RMW 的具体实现在 cs/src/core/Index/FASTER/Implementation 目录下：InternalUpsert.cs、InternalRMW.cs、InternalRead.cs、InternalDelete.cs分别对应 UPSERT / RMW / READ / DELETE 四条操作路径；
混合日志的分页分配与管理在 cs/src/core/Allocator（BlittableAllocator.cs、VarLenBlittableAllocator.cs、GenericAllocator.cs等），内存页调度与溢出相关测试可见 paging_test.h 与 malloc_fixed_page_size_test.cc（C++ 端）。

Epoch 保护：论文 3 对应的核心数据结构

"Almost-Latch-Free"（几乎无锁）论文描述的 epoch protection 机制，在仓库中就是 LightEpoch.cs。从源码可以看到其精妙设计（LightEpoch.cs#L15-L103）：

缓存行对齐：常量kCacheLineBytes = 64，线程状态表按缓存行对齐以避免伪共享；
线程表容量：kTableSize = max(128, ProcessorCount * 2)，随机器核心数自适应；
drain list：大小 16 的EpochActionPair环形槽，存放"当某个 epoch 变得安全可回收后要执行的动作"（如内存页回收、索引扩容回调）；
两个全局水位：CurrentEpoch（全局当前纪元）与SafeToReclaimEpoch（可安全回收的最新纪元）——这正是论文中"延迟回收（deferred reclamation）"的落地形态。

基于 epoch 的版本化方案还有专门实现 EpochProtectedVersionScheme.cs，其行为由 SimpleVersionSchemeTest.cs 覆盖；另有一组基准测试 LightEpochTests.cs 用于度量 epoch 保护的开销。C++ 端同样移植了该机制，见 light_epoch.h。

单机恢复：Concurrent Prefix Recovery（CPR，SIGMOD 2019）

文档"Single-Node Recovery"小节仅收录一篇，但它是 FASTER 恢复模型的理论基石：

Guna Prasaad, Badrish Chandramouli, Donald Kossmann.Concurrent Prefix Recovery: Performing CPR on a Database. SIGMOD 2019, Amsterdam, Netherlands, June 2019.

CPR 的核心理念

文档 25-fasterkv-recovery.md 专门用一节介绍了 CPR 的通俗解释：CPR 基于周期性 group commit（组提交），但刻意不使用昂贵的 WAL（预写日志），因为 WAL 会毁掉 FASTER 的高性能。取而代之的是两条支柱：

前缀语义：提交状态被描述为"会话 i 中直到序号 Ti 的所有操作均已持久化"，而不是逐个操作确认；
异步增量检查点：用非阻塞的增量 checkpointing 代替 WAL 实现可扩展、无瓶颈的组提交。

用户侧模型：每个会话（session）的操作（Read/Upsert/RMW）携带单调递增的序列号；调用 checkpoint API 后，每个会话最终收到一个commit point，包含 (1) 一个序列号，保证该序号之前（且之后不含）的所有操作已随该 checkpoint 持久化；(2) 一个可选的 exception list，列出因会话在 checkpoint 时刻不活跃而未提交的操作。

源码中的 CPR 落点

CPR 在仓库中的实现集中在 cs/src/core/Index/Recovery 目录：

Recovery.cs 是恢复主流程，RecoveryStatus类（Recovery.cs#L17-L51）用ReadStatus/FlushStatus两个环形缓冲跟踪每页的读取与落盘进度，配合SemaphoreSlim实现同步/异步两种等待语义；
RecoverHybridLog（Recovery.cs#L610）按 checkpoint 类型分发恢复路径：Snapshot走RecoverHybridLogFromSnapshotFile（Recovery.cs#L734），FoldOver直接在主日志上回放；
索引的"模糊恢复"（fuzzy recovery，即索引 checkpoint 与日志 checkpoint 不必精确对齐）实现在 IndexRecovery.cs#L25-L85（RecoverFuzzyIndex/RecoverFuzzyIndexAsync），其单测可见 ComponentRecoveryTests.cs#L167-L185；
公开 API 层：Recover(int numPagesToPreload = -1, bool undoNextVersion = true, long recoverTo = -1)支持恢复到指定序列号（recoverTo），这对应 CPR 论文的"前缀恢复"能力（FASTER.cs#L427）。

一个最小可运行的 CPR 使用范式

文档 25-fasterkv-recovery.md 给出的示例（在 SimpleRecoveryTest.cs 等测试中有同构实现）完整展示了"周期检查点 + 崩溃后恢复 + 会话续跑"三步曲：

// 1. 周期性地发起 FoldOver 日志检查点（非阻塞） (_, _) = fht.TakeHybridLogCheckpointAsync(CheckpointType.FoldOver).GetAwaiter().GetResult(); // 2. 崩溃重启后恢复 fht.Recover(); // 3. 用相同会话 ID 续跑：ResumeSession 返回 CommitPoint， // 其中 UntilSerialNo 即"已持久化的前缀序号" using var session = fht.ResumeSession(new SimpleFunctions<long, long>(), "s1", out CommitPoint cp); var seq = cp.UntilSerialNo + 1; // 从断点之后继续发操作

其中TakeHybridLogCheckpointAsync支持CheckpointType.Snapshot（把内存日志整体快照到独立 snapshot 文件，可配tryIncremental增量快照）与CheckpointType.FoldOver（直接落主日志、写小元数据文件info.dat，天然增量）。C++ 移植版同样具备完整恢复能力（见 cc/README.md），恢复状态机在 recovery_status.h，日志元数据读取示例在 cc/playground/recovery-info，恢复测试见 f2_recovery_test.cc。

扩展性：Larger-than-Memory Store（PVLDB 2021）

文档"Scale-Out"小节：

Chinmay Kulkarni, Badrish Chandramouli, Ryan Stutsman.Achieving High Throughput and Elasticity in a Larger-than-Memory Store. Proc. VLDB Endow. Volume 14, Issue 8, 2021（原文标注 arXiv:2006.03206）。

论文要义与仓库对应

这篇论文探讨的是 FASTER 作为"内存放不下的存储"时的扩展能力：如何在不牺牲吞吐的前提下利用比内存更大的数据集，并保持弹性伸缩。对应到仓库，最直接的落地机制是read cache（读缓存）：混合日志的主日志（main log）常驻最近写入的数据，而读缓存用独立的内存页集合为"写少读多"的工作负载缓存磁盘侧数据，从而把读放大压到最低。

配置入口非常直观：

var logSettings = new LogSettings { LogDevice = log, ObjectLogDevice = objlog, // 启用读缓存：缓存逻辑位于主日志之外，专门服务磁盘页的重复读 ReadCacheSettings = useReadCache ? new ReadCacheSettings() : null, // PageSizeBits = 12, // 4K 页（低内存占用演示） // MemorySizeBits = 20 // 主日志内存 1M };

这段代码取自 cs/samples/CacheStore/Program.cs#L32-L39。LogSettings中的MemorySizeBits/PageSizeBits分别以 2 的幂定义主日志内存总量与页大小，二者共同决定混合日志的分页调度节奏。相关工程实践还有：

ResizableCacheStore 示例：用CacheSizeTracker/LogSizeTracker动态调整缓存与日志容量，体现论文的"elasticity"主题（示例中同样以ReadCacheSettings构造读缓存，见 Program.cs#L351）；
测试侧：读缓存链与正确性由 ReadCacheChainTests.cs、NativeReadCacheTests.cs、ObjectReadCacheTests.cs 覆盖；
并发玩法见 cs/playground/CacheStoreConcurrent。

C++ 端对应的扩展形态则走向了双层索引架构：F2Kv类（f2.h#L20）将"热存储（内存哈希索引 MemHashIndex）+ 冷存储（磁盘两层索引 ColdIndex）"配对成一个整体（mem_index.h#L39、cold_index.h#L44），可视为 Larger-than-Memory 方向在 C++ 移植版上的延续演化。

分布式恢复：Asynchronous Prefix Recoverability（SIGMOD 2021）

文档"Distributed Recovery"小节：

Tianyu Li, Badrish Chandramouli, Jose M. Faleiro, Samuel Madden, Donald Kossmann.Asynchronous Prefix Recoverability for Fast Distributed Stores. SIGMOD 2021, Virtual Event, China, June 2021.

论文要义

把单机的 CPR 前缀恢复思想推广到多节点：每个分片（shard）独立维护自己的提交前缀，节点间以异步方式传播提交信息，使得分布式存储即使在不同节点故障与恢复进度不一致的情况下，也能在全局范围内给出可验证的一致性恢复语义，避免传统两阶段提交的同步开销。

仓库中的分布式实现

虽然仓库以单机 FASTER 核心为主体，但cs/remote/目录完整承载了远程化（remote）方向：

服务端：cs/remote/src/FASTER.server 提供FasterServerTcp（FasterServerTcp.cs）、FixedLenServer、VarLenServer、GenericServer等，底层会话由 BinaryServerSession.cs 处理请求-响应的编解码与异步回填；
客户端：cs/remote/src/FASTER.client 的ClientSession.cs、ClientSessionAsync.cs、FasterKVClient.cs提供与本地IClientSession对齐的调用面；
测试：cs/remote/test/FASTER.remote.test 中的FixedLenBinaryTests.cs、VarLenBinaryTests.cs、FixedLenBinaryPubSubTests.cs覆盖了远程读写、订阅与畸形请求处理；
入门示例：FixedLenServer、FixedLenClient、VarLenServer、VarLenClient。

缓存方向：CompuCache 与 Redy（CIDR / PVLDB 2022）

文档"Caching"小节收录两篇论文：

Q. Zhang, P. Bernstein, D. Berger, B. Chandramouli, V. Liu, B. T. Loo.CompuCache: Remote Computable Caching using Spot VMs. CIDR, 2022.
Q. Zhang, P. Bernstein, D. Berger, B. Chandramouli.Redy: Remote Dynamic Memory Cache. PVLDB, 15(4), 2022.

这两篇论文是同一研究线在"远端可计算缓存"方向的延伸：CompuCache 探讨利用 Spot VM 的闲置算力在远端做可下推计算的缓存；Redy 则是面向远端动态内存的缓存系统。需要说明的是，这两套系统属于相关研究项目，本仓库并未包含其实现；它们之所以出现在 FASTER 的论文索引中，是因为 FASTER 本身就是"cache + store"混合定位的载体。仓库内最接近的工程实体是上文提到的读缓存（read cache）与 CacheStore 示例（该示例注释明言 "This sample shows the use of FASTER as a cache + key-value store"），以及在 CacheStoreConcurrent 中把ReadCacheSettings作为开关与 KV 存储并用的实践。

二级索引与数据摄取：FishStore（VLDB 2019 / SIGMOD 2019）

文档"Secondary Indexing"小节：

Badrish Chandramouli, Dong Xie, Yinan Li, Donald Kossmann.FishStore: Fast Ingestion and Indexing of Raw Data. VLDB 2019, Los Angeles, California, USA, August 2019（demo paper）。
Dong Xie, Badrish Chandramouli, Yinan Li, Donald Kossmann.FishStore: Faster Ingestion with Subset Hashing. SIGMOD 2019, Amsterdam, Netherlands, June 2019.

FishStore 瞄准的是"原始数据的高速摄取与索引"：通过subset hashing（子集哈希）对无模式数据流做按需、低成本的索引构建，支撑二级索引类查询。需要如实说明：FishStore 是 FASTER 研究线下的独立系统，从当前仓库目录结构看并未包含其源码实现，FASTER 核心自身聚焦于点查询（point lookup）之上的主索引。若要理解"索引到底长什么样"，可读 C++ 端的两类主索引定义——内存热索引 MemHashIndex 与磁盘冷索引 ColdIndex（注释明确写着 "On-disk, two-level hash index"），它们展示了 FASTER 主索引由内存桶表到溢出桶/磁盘分页的多级结构，这与 FishStore 论文中"哈希 + 分层存储"的思路一脉相承。

把论文读进代码：仓库导航指南

论文索引页是"理论入口"，若要亲手验证每个概念，推荐按下面的映射路径深入（均为仓库内已有文件）：

想验证的论文概念	优先阅读
整体架构（hash index + hybrid log）	docs/_docs/20-fasterkv-basics.md、cs/src/core/Index/Common/LogSettings.cs
磁盘读的生命周期（PendingContext → AsyncIOContext → CompletePending）	docs/_docs/82-code-structure.md
CPR / checkpoint / 恢复	docs/_docs/25-fasterkv-recovery.md、Recovery.cs、SimpleRecoveryTest.cs、RecoveryChecks.cs
Epoch / 无锁并发	LightEpoch.cs、SimpleVersionSchemeTest.cs
读缓存 / 大内存扩展	CacheStore 示例、ResizableCacheStore 示例、ReadCacheChainTests.cs
远程化 / 分布式	cs/remote/README.md、FasterServerTcp.cs、FASTER.remote.test
自定义类型与就地更新	cs/samples/StoreCustomTypes、cs/samples/StoreVarLenTypes、cs/src/core/Index/FASTER/Implementation/InternalRMW.cs
C++ 移植版（含 F2 双层索引）	cc/README.md、docs/_docs/29-fasterkv-cpp.md、f2.h、cold_index.h
FASTER Log（可恢复日志库）	docs/_docs/40-fasterlog-basics.md、FasterLog.cs、FasterLogSettings.cs

结语：一条推荐的研读路径

对刚接触 FASTER 的读者，建议按"主论文（SIGMOD 2018）→ CPR（SIGMOD 2019）→ 扩展（PVLDB 2021）→ 分布式（SIGMOD 2021）"的顺序阅读：前两篇解决"单机为什么快、怎么恢复"，后两篇解决"怎么变大、怎么跨机"。每读一篇，回到上表的仓库对照项去翻对应源码——你会发现文档中抽象的概念几乎都能在 cs/src/core、cc/src、cs/remote 中找到逐行的实现细节，这正是论文索引页最有价值的用法：它不仅是文献清单，更是整个 FASTER 代码库的"阅读地图"。