FasterKV存储引擎介绍

导语：微软开源的FasterKV存储引擎，使用Hash作为主索引，基于Log追加写和原地更新的混合存储方式，无锁并发，性能亮眼。

介绍

微软开源的FasterKV存储引擎，使用Hash作为主索引，基于Log追加写和原地更新的混合存储方式，无锁并发，性能亮眼。

而另一类基于log存储的存储是使用hash作为主索引组织数据，如Bitcask，因为Hash，不具备范围查询这种重要的功能，但可以在其他方面发挥优势，如极高的性能的点查，FasterKV也是这类引擎。

FasterKV首次出现在微软2018年在Sigmod上发表的论文，代码也开源，其主要应用场景如下：

Faster = Log + KV，即Faster分两部分，即FasterLog和FasterKV，前者是Log存储引擎，可作为独立的组件使用，后者是在Log之上的KV存储引擎，Log是C#实现，KV有C#和C++两版本。

FasterKV具有极高的点查读写性能，在单机、数据全match内存的情况下，达1.5亿QPS。

架构

数据组织上，Faster是一个全局的Hash主索引，放内存中，hash-entry不存key，指向Record-list，每个Record即KV对。

Record是从内存中分配（如基于jemalloc的分配器），或从log中分配，log会追加写，通过log刷盘进行数据的持久化。和传统的Log追加写的方式不同（所有的修改操作都创建一个record副本追加在log尾部），Faster在最热的log（cache在内存中）采用原地更新（in-place-update），从而避免log的快速增长，这也是Faster极高写性能的核心之一。但原地更新，没有WAL，有宕机丢数据的风险。

Faster支持多线程并发，但经过对Hash主索引的巧妙设计，以及Epoch-Protection并发控制框架，整个系统是无锁（latch-free）并发的。

主要特性

主要功能特性：

- 基本的点查读写，read、upsert（replace）、delete

- 原子性的RMW（read-modify-write）

- 多级存储，内存、SSD、Azure Storage

- 多线程，Multi-threaded session model access

- Non-blocking（incremental）checkpoint & recovery

- Key iteration & Full log scan

- 变长key和value

- Log compaction

- 【新】client-server & scale out

- 【新】二级索引

- 【more】Roadmap - FASTER (microsoft.github.io)

API示例

public static void Test()
{
   using var settings = new FasterKVSettings<long, long>("c:/temp");
   using var store = new FasterKV<long, long>(settings);
   using var session = store.NewSession(new SimpleFunctions<long, long>((a, b) => a + b));
 
   long key = 1, value = 1, input = 10, output = 0;
   session.Upsert(ref key, ref value);
   session.Read(ref key, ref output);
   Debug.Assert(output == value);
   session.RMW(ref key, ref input);
   session.RMW(ref key, ref input, ref output);
   Debug.Assert(output == value + 20);
}

性能数据

单线程（数据全放内存）

多线程扩展性（数据全放内存），达1亿以上QPS

内存不足的情况，即使在内存受限的场景，写也能维持在极高的吞吐性能，根本原因是追加写+原地更新，都是内存热数据，不涉及写IO，而读操作则不一样。

技术细节

Hash主索引

Hash索引的桶大小是64字节（cache line的大小），每个桶存8个地址，即64bit，支持Atomic更新，即CAS。

每个地址，64bit中

- 只用48bit来存储记录的地址，在Intel平台的机器上这是足够的

- 15bit的tag保存key的hash值低15位，桶中的8个地址的8个tag保证唯一，有了这个tag，一定程度地减少了hash冲突检查

资料领取直通车：大厂面试题锦集+视频教程

Linux服务器学习网站：C/C++Linux服务器开发/后台架构师

 

- 也就是说，bucket_offset + tag唯一标识一个冲突链

- 最高位1bit用于一些场景下的并发控制

Record存储了变长key、value，其中还有一个64bit的Header，一方面这个Header可以存储地址，形成单向链表，另一方面64bit可以原子更新的，因此这个链表可以是无锁（latch-free）并发读写的。

无锁（Latch-free）读写

读、删除，计算key的hash值，找到hash_bucket_offset、tag，找到冲突链表，找到对应的Record，进行读、删除。

RMW（read-modify-write）还是有些区别，这里只看insert，如下图，两个线程并发，都往相同的tag插入新记录，插入记录时，线程通过CAS修改tag所在的8字节，若失败说明有其他线程已经插入，则当前重试，找到新的链表头，把当前记录插入链表头再修改桶中的地址，因为链表的header也是8字节，可以CAS原子性插入。

实际上还会更复杂，上述情况是有bug的，这就使用了64bit中的最高位1bit，进行并发控制（无锁），这里不展开，详情请看论文。

Rehash？

Faster也是维护2个版本的hash表，可能也是类似Redis的渐进式rehash，这里细节待研究。

Hybrid Log

从逻辑上，所有的record都是从一个连续的log中分配的，而hash中的地址就是指向log中的某个偏移地址

1. 新插入的record总是从log尾部创建，log尾部总是增长的
2. log分为几个区域，Mutable区域总是最热的数据，head offset之前的区域则是已刷盘的，而readonly offset之前的数据虽然还在内存中，但是是可刷盘的
3. 看其本质，其实和LSM-Tree存储是相通的（如RocksDB），图中mutable对应memtable，read only区域对应immemtable，stable对应SST。
4. 按传统log，任何修改总是在mutable中拷贝出一个副本，然后修改，写密集场景下，log增长特别迅速，导致IO刷盘次数多，也带来更多的垃圾版本数据，从而引入繁重的log compact。而hybrid log的mutable则是原地更新的，这是高性能的关键，看下面的第二张图，若不采用原地更新，性能差距是非常大的。
5. 见下面的第二张图，对于RMW，当key落在不同的区域，其写策略还是不一样的。
6. 虽然原地更新是高性能的关键，但是没有及时刷盘有宕机丢数据的风险，Faster如何解决？

并发控制

Faster的主索引设计上，虽然支持无锁并发，但有些涉及全局资源的竞争的场景（如rehash、log的增长和回收、checkpoint、recovery等），同样的latch-free技巧是无法解决的，传统做法是引入锁，但faster认为锁太重了，因此引入了一个新的无锁的并发控制框架，即epoch protection。

这样的并发框架，要求系统满足这样的前提条件：绝大多数情况下，没有全局资源的竞争冲突，确实，绝大多数情况下faster的读写可以使用CAS无锁并发，记录级别并发。

Epoch不是新东西，Epoch意思上是“时钟”的概念，单调递增，像Bw-tree、Silo等其他数据库，基于epoch实现具体的MVCC、GC等并发控制问题。而Faster则实现为一种通用的并发控制框架。

见下面两页PPT，大体总结如下：

1. 全局维护一个epoch E，单调递增，可以由任意一个线程推进增长
2. 每个线程维护本地epoch Et，时不时从全局的E拷贝刷新，每个线程Et刷新速度不一致
3. 有一个安全epoch Es，总有Es < Et < E
4. 每个线程要执行某个动作时，不是立即执行，而是等到所有线程达成一致之后才能执行，即这个动作注册为回调函数+当前Et，当Et变成安全时会触发
5. 本质上，这个框架是一种线程之间的一致性同步协议，挺好奇代码怎么写的

恢复

Hybrid log的性能关键是原地更新，但有宕机丢数据的风险，若引入传统WAL，那原地更新的意义不存，性能也大幅下降，如下Faster使用了组提交的WAL

分析一下，WAL瓶颈点在于，每个更新都要创建一个WAL log record，这正是原地更新要避免的点。

Faster受两个思想的启发（group commit和in-memory increment checkpoint），提出另一种checkpoint和恢复的方案，即concurrent prefix recovery。

从抽象上，大体思路是：

1. 每个线程维护一个逻辑上单调递增的时间序列（估计是epoch protection实现的），每个线程独立推进
2. 线程的每个写操作不用立即响应client，而是堆积，如下图中commit1和commit2之间
3. 全局的commit点就是所有线程的当前的T值，每次刷盘时，以这样的commit边界进行刷盘，然后这些可成功响应
4. 本质上，这种方案是合并累积多次更新刷盘，而且不同线程没有竞争瓶颈
5. 但可以想象，和原来相比，时延和吞吐都受到影响，但确实比group commit的WAL好

具体的，应用到hybrid log上，如下图，这里理解本质上是找到一个log offset作为commit边界，及时刷盘

性能数据相比WAL，好很多

二级索引

FasterKV作为纯粹的KV存储引擎，没有上层的模型逻辑，没有二级索引，而是微软的另一个项目FishStore，是以FasterKV作为底座的数据库，实现了模型层和二级索引，细节有待研究

FishStore/tutorial.md at master · microsoft/FishStore (github.com)

其他

代码量，感觉代码挺精简。

总结

FasterKV的核心内容总结如下

• Hash主索引，特点是latch-free，全放内存
• Hybrid log，追加写+原地更新
• 无锁并发控制框架，Epoch protection
• Checkpoint & Recovery，WAL，CPR（concurrent prefix recovery）
• 二级索引？Fishstore