Faster: A Concurrent Key-Value Store with In-Place Updates

FASTER 是微软实现的 k/v 存储引擎,提供 ReadUpsertRmwDelete 接口,对 key/value 的类型没限制,支持 persistencerecovery。 在 2.60GHz Intel Xeon CPU E5-2690 v4 CPUs, 2 sockets and 14 cores (28 hyperthreads) per socket, 256GB RAM, 3.2TB FusionIO NVMe SSD drive 的单机上开启 56 线程压测可达每秒 1.6 亿次操作:纯读操作,纯内存,key/value 都是 8 bytes integer

Faster 的代码也在 github 上开源了,不过只是个原型,论文里也有很多没解决的问题。

Architecture

FASTER 整个架构分为 4 个部分:

  • code-generation
  • epoch protection framework
  • latch-free hash table
  • hybrid-log

image

使用

FASTER 的使用比较麻烦,内部的很多机制如 epoch protection frameworkdisk i/o 等都需要用户配合使用:

  • 线程开始时调用 Acquire 注册该线程。
  • 线程调用一系列命令。
  • 线程要定期调用 RefreshCompletePending 操作。
  • 最后调用 Release 解除线程的注册。

C++ 的实现如下,StartSessionAcquireStopSessionRelease

    // Register thread with FASTER
    store.StartSession();

    // Process the batch of input data
    for(uint64_t idx = 0; idx < kNumOps; ++idx) {
      RmwContext context{ AdId{ idx % kNumUniqueKeys}, 1 };
      store.Rmw(context, callback, idx);

      if(idx % kCheckpointInterval == 0) {
        Guid token;
        store.Checkpoint(nullptr, hybrid_log_persistence_callback, token);
        printf("Calling Checkpoint(), token = %s\n", token.ToString().c_str());
      }
      if(idx % kCompletePendingInterval == 0) {
        store.CompletePending(false);
      } else if(idx % kRefreshInterval == 0) {
        store.Refresh();
      }
    }
    // Make sure operations are completed
    store.CompletePending(true);

    // Deregister thread from FASTER
    store.StopSession();

Code-generation

FASTERkey/value 的类型没要求,而且支持 Rmw,所以需要用户提供相应的逻辑。FASTER 通过 code-generation 生成代码调用用户提供的接口。

C++ 中是用模板实现的,是为了避免虚函数的性能损耗。 以 Read 操作为例:

  • FASTERRead 接口如下,需要传入用户定义的类 RC(Read Context)
    template <class RC>
    inline Status Read(RC& context, AsyncCallback callback, uint64_t monotonic_serial_num);
    
  • RC 需要实现几个 implicit interface:
    /// The implicit and explicit interfaces require a key() accessor.
    inline const AdId& key() const { // 返回要查找的 key
      return key_;
    }
    
    inline void Get(const value_t& value) { // 将 key 对应的 value 保存在 result
      *result_ = value.num_clicks;
    }
    inline void GetAtomic(const value_t& value) {
      *result_ = value.atomic_num_clicks;
    }
    
  • FASTER 内部调用会调用 RC 的接口:
    inline const key_t& key() const final {
      return read_context().key();
    }
    
    inline void Get(const void* rec) final {
      const record_t* record = reinterpret_cast<const record_t*>(rec);
      read_context().Get(record->value());
    }
    inline void GetAtomic(const void* rec) final {
      const record_t* record = reinterpret_cast<const record_t*>(rec);
      read_context().GetAtomic(record->value());
    }
    

Epoch Protection Framework

提高 scalability 的关键是避免线程间的同步,因为当核数越来越多时,同步的代价越来越大。FASTER 的绝大多数操作是不需要同步的, 当需要同步时使用 Epoch Protection Framework 实现线程间状态的 lazy coordination:

  • 使用 atomic variable 维护全局递增的 Epoch,可以被任意线程读取、增加。
  • 每个线程定期从全局的 Epoch 中获取 thread-local epoch
  • 当所有线程的 thread-local epoch 都大于某个 epoch 时,该 epoch 是安全的。
  • 增加全局 Epoch 时可以注册 <Epoch - 1, trigger action>,当 Epoch - 1 安全时,trigger action 会被调用。

举个例子,多线程情况下如何安全的释放内存。最常用的方法是 refcount,当 refcount0 时释放内存,但是 atomic variable 在核数多时,同步代价就很大,性能很差,而且 refcount 不是 通用的解决办法,还会增加内存使用。用 epoch 解决办法如下:

  • 当需要释放内存时,一个线程增加全局的 Epoch 并注册 <Epoch - 1, free old memory>
  • 所有线程定期调用 Refresh 增加自己的 thread-local epoch
  • Epoch - 1 安全时,能够保证没有线程会访问之前的内存,可以安全释放。

对全局 Epoch 的修改是 write-release,读取是 read-acquire,所以修改 Epoch 之前的操作都会对之后读取 Epoch 的线程可见,从而实现了状态的同步。而且每个线程增加 thread-local epoch 都是 主动调用 Refresh,是在操作的边界,保证了 epoch safe 时没有线程在访问之前的状态,之后的操作都会访问最新的状态。

FASTER 的实现也很简单:

  • 全局的原子变量 current_epoch
  • 数组保存所有线程的 thread-local epoch,不是原子变量,使用 acquire/release 语义遍历来计算 safe epoch
  • 固定大小的数组保存 <epoch, trigger action> 对,epoch 使用原子变量,起到锁的作用,使用 CAS 实现插入并保证唯一执行。

Latch-free Hash Table

FASTER 的索引是 latch-free hash table,而且支持 resize。和一般的 hash table 实现相同,使用 hash(key) 找到 hash bucket,使用链表解决冲突。 hash table 天然并发友好,因为不同 bucket 间不需要同步。

FASTER 使用 cache-aligned 数组保存 hash buckets,每个 hash bucket64 字节,包含 8hash entry,使用 tag 区分 entry:

  • 7 个分别指向链表尾部的 RecordRecord header 会保存上一个 Record 地址。
  • 最后一个为 overflow bucket entry 指向相同索引不同 taghash bucket,用于解决 hash entry 的冲突。 image

查找 key 的过程如下:

  1. 计算 key hashkey hash 也和 hash bucket entry 的格式对应:
    struct KeyHash {
      union {
       struct {
         uint64_t address_ : 48;
         uint64_t tag_ : 14;
         uint64_t not_used_ : 2;
       };
       uint64_t control_;
      };
    };
    
  2. address & (size - 1) 找到对应的 hash bucket
  3. 遍历 hash bucket 比较 tag 找到对应的 hash entry
  4. 遍历 hash entry 指向的链表,找到相同的 keyRecord

hash bucket 内部还要划分 hash entry 的原因是:因为 hash bucket 间不需要同步,所以要按 cacheline 对齐来避免 false sharing,至少要 64 字节, 若每个 hash bucket 指向一个链表就太浪费内存,所以这里划分了 8entry,还能减少 hash collision 提高性能。

hash entryrecord header 中使用 48 bits 保存地址,而我们都知道 64 位机器的指针大小为 64 位,这是因为:

  • 64 位机器一般使用少于 64 bits 的物理地址,比如 Intel 使用 48 bits
  • 为了实现 latch-free,要使用原子操作设置 hash entry,而 64 位机器最多提供 64 bits 的原子操作,但我们需要一些 bits 来实现一些逻辑,如 entrytentative bit

插入的过程很简单,先找到对应的 entry:

  • entry 存在,则 CAS 设置 entry 指向新的 Record 链表尾即可,失败的话就重试。
  • entry 不存在,则找到空闲的 entry 设置。但这里不能直接 CAS,因为有可能导致相同的 tag 使用多个 entry:
    • T1 找到 g5 为空闲,准备设置。
    • 其他线程删除 keyg3 清空。
    • T2 插入相同 hashkey,找到 g3 为空闲,导致使用了不同的 entryimage

FASTER 使用 tentative bit 实现了 two-phase insert 来解决这个问题:

  • CAS 设置空闲 entry 时,先设置 tentative bit,该 entry 目前无法使用。
  • 重新遍历 bucket 查找是否有相同 tagentry:
    • 有:清理 entry,重试。
    • 没有:重置 tentative bit,完成。

相当于乐观锁,先插入,然后看是否冲突,冲突则回滚重试。

Hybrid-log

latch-free hash table 搭配不同的 Record Allocator 即可实现多样的存储,如搭配 malloc 就是内存数据库但不支持持久化和恢复。需要注意的是即使 index 是并发安全的, 不代表数据访问是并发安全的(隔离性、memory safety 等),这些需要其他策略来保证,比如采用 append-only + MVCC。而在 FASTER 中, 具体的逻辑是由用户实现的,比如之前的压测场景,value8 bytes integer,可以保证更新和读取操作是原子的,FASTER 内部使用 epoch protection 来保证 memory safety。更复杂的场景可以 使用 record-level lock

Record Allocator 分配 logical address 而不是 physical address 即可支持大于内存的存储,如论文里提到的 Append-Only-Log:

  • 从固定大小的 circular buffer 分配 Record 内存,buffer 划分为固定大小的 pageRecord Address 代表 <page, offset>
  • 所有的写、更新操作都新分配内存,更新 index(append-only)。
  • 当进入新的 page 时,之前的 page 可以写到磁盘。
  • 写到磁盘的 page 会被循环使用,Head OffsetTail Offset 确定在内存的范围。 image

若读取的 Address 小于 Head Offset 就会从磁盘中读取,磁盘中数据格式和 buffer 一样,所以通过 <page, offset> 即可找到数据。FASTER 使用 direct i/o 来减少内存拷贝,async i/o 来避免阻塞, 每个线程 i/o 操作的结果会保存在 concurrent queue 中,需要用户主动调用 CompletePending 处理。

Tail Offset 增大进入新的 page 时,之前的 page 可以写到磁盘,但是要保证该 page 的所有写操作完成(因为内存分配出去不代表线程都更新完成了)。当 Head Offset 增大要复用之前的 page 时,要保证这个 page 没有其他线程访问且已被写到磁盘。 这都是通过 epoch protection framework 实现的:

  • 进入新的 page 时,注册 <epoch, flush page>。当 epoch 安全时,可以保证该 page 所有操作都完成。
  • 要复用 page 时,注册 <epoch, set page closed-status>。当 epoch 安全时,可以保证该 page 没有线程访问。

Append-Only-Log 的缺点是当写入很多时,page 的写磁盘就会成为瓶颈。Hybrid-Log 支持了 in-place update 能够解决 update-intensive 的场景:

  • 减少数据拷贝。
  • 减少 page 的分配也就减少了状态同步和磁盘 i/o

in-place update 的困难在于 FASTER 为了性能,没有 WAL,采用的是 Hybrid-LogWAL,但 Recovery 要求 Monotonicityin-place update 很难保证,举个例子:

  • 按顺序写 page 到磁盘。
  • 一个更新操作更新了下一个待写入到磁盘的 page,然后该 page 写到磁盘。
  • 若此时机器挂掉,就不符合 Monotonicity 了(新的写入保存了,之前的写入没了)。

Hybrid-Log 为了解决这个问题将整个 Circular Buffer 划分为 3 个区域:

  • Stable:数据在磁盘上。
  • Read-Only:只读区域,等待写入到磁盘上成为 Stable
  • Mutableupdate in-placeimage

更新 Read-Only 区域的数据采用 RCUMutable 创建新的数据,从而保证了所有的更新都在 Mutable 区域,而 Mutable 要先变成 Read-Only 才能写到磁盘,所以能够保证 Monotonicity。 其实就相当于 Mutable 区域是 in-place updatememtableMutable 转为 Read-Only 就是 memtable compaction 只不过这里不是由其他线程写到磁盘,而是工作线程使用 async i/o 写。

因为完全的 latch-free 仍有许多细节需要考虑,比如论文里提到的 fuzzy region

其他

  • FASTERhash table 支持 resize,但是是阻塞的,每个线程负责一定数量的 bucket。而且 rehash 不是准确的,当遇到在磁盘上的 Record 时为了效率会添加到所有可能的 hash bucket 中,索引使用的内存就会增加。
  • FASTERGC 指清理磁盘上的 log,实现很暴力,直接增加 hybrid-logbegin address 清理磁盘上对应的文件(hybrid-log 在磁盘上划分为一个个 segment file),然后清理 hash table 中所有 address 小于 begin addressRecord
  • FASTER 支持 indexhybrid-logCheckpoint,来加快重启速度,具体实现就是把 hash tablehybrid-log 都写到磁盘,但因为 Checkpoint 过程中还会更新,所以仍是 fuzzy 的。

Summary

FASTER 论文中有很多未解决的问题,开源的实现也只是个原型,有很多局限性:

  • in-place update 局限性很大,只适合 update-intensive,而且如果新 value 大小比之前大,仍然需要分配新的内存。
  • 对读操作没优化,一种解决办法是读磁盘上的数据时也在 Mutable 区域创建一个拷贝。
  • 没有 WALGC 太暴力,FASTER 更适合做 cache
  • 使用麻烦,接口暴露内部实现。
  • 开源实现中很多未实现,如 Delete 操作、hash table 是纯内存的。
  • 许多操作实现为阻塞式的,如 hash table resize

分类:

更新时间: