发表于 分类于

引言

经过学习的哈希引擎深入，并开始接手公司哈希引擎开发，逐渐意识到哈希引擎的一些设计难点。本文主要针对非原子性读写这个难点谈谈。

hash引擎可以最简单的抽象为两大部份：

  1. 存储的读写操作。即从ssd中读出来数据，或将内存修改好的buffer数据落盘。
  2. 内存索引的修改操作。

这两大部份无法做到原子性，因为你不可能全程加大锁，对ssd的写操作假如需要sync，那耗费的时间难以接受。那么这个不能原子性就造成了今天要讨论的全部问题

存储引擎都会有垃圾回收与碎片整理，取决于其实现。假如是文件模式的哈希引擎（aerospike是自己管理ssd的block），其compaction和rocksdb基本原理类似，多个文件合并，对不能删除的数据迁移至新的文件即可。

而该compaction过程往往会成为并发问题的复杂性根源。

笔者目前只看过两种哈希引擎，分别是开源和当前公司内部的自研产品，分别为

  • taycan
  • aerospike

下面将针对这两个引擎的实现做分析探讨。

读失效

假设有这样一个场景。线程A和compaction线程B，他们操作的时间线如下

  1. A读取内存索引，找到了该key所在的ssd的位置
  2. B出于垃圾回收，将该key所在的位置迁移到了新的位置
  3. B迁移完该key后回写内存索引，修改其指向新位置
  4. A此时拿到的是旧位置，访问旧位置ssd的数据失效

这个场景很好理解。即A读到了内存索引被写(迁移)操作失效了。

taycan解决思路

不幸的是。在我写这篇文章的这一刻，该问题甚至没有解决，因为线上发生这个事情的概率太低了。因为compaction要刚好gc到这个key，触发时机也比较苛刻，所以没有解决。

但其实解决方案一年前便提出，也给出了代码mr，但没有合并。方案思路很简单：引用计数。

简而言之，必须实现多版本，一旦上面拿到了某个ssd的位置，便对该文件增加引用计数，以保留原来的文件，不能被compaction后删除，从而实现多版本。

但是这个不能删除的文件管理方式还没有完全定好，等未来有完整的方案思路了，我再继续补充。

aerospike的解决思路

我并没完全理解aerospike的解决代码，因为我没找到wblock的引用计数或相关步骤代码，可能其实现在sdk层。

它应该是采用了乐观锁的机制，因为aerospike并没有多版本的概念（起码在8.0事务能力前没有），当读到了错误的block数据，读操作会重新发起，重试再次读新位置。

持久删除

持久删除应该是最难最麻烦的一部份，aerospike甚至没有公开这部分的开源实现，导致taycan在实现时也只能摸着石头过河，实现的并不好。

首先持久删除肯定是要插入一条delete数据到ssd中，并且该delete数据绝不能在旧插入数据被回收前回收，否则recover会导致删除的数据又回来了。

假如同样有两个线程，线程A执行了delete命令，线程B为compaction线程做垃圾回收，时间线如下：

  1. B为了检查数据是否可以迁移，查key1的内存索引节点，发现是存在的（因为该时刻索引节点不存在就直接可以gc该key了）
  2. A往ssd插入key1的delete操作
  3. A回填索引，删除了key1在内存中的索引节点
  4. B迁移完key1后，回填索引，回填了key1的最新位置

可以看到，以上顺序导致了key1根本就没有被删除，因为key1的内存索引节点还存在，但是delete操作成功了，用户却以为删除了，风险极大。

同样还有第二个问题

  • delete该操作kv，在ssd中何时被清理？

因为delete操作实际是插入了一条delete信息在ssd中，那么随着delete该key次数的增多，会占用ssd的空间，该部份空间也是需要清理的。

taycan的解决思路

假如一条delete操作过来，taycan会做如下操作

  1. 将该delete信息，记录到某个map中，假如叫inflight_delete，存放所有将要删除的key
  2. 往ssd插入该delete key，value值为当前文件的seq_num
  3. 删除内存索引
  4. 删除inflight_delete中的该key

而compaction线程在扫描文件时，遇到key会做如下操作

  1. 检查该key在内存索引中是否存在，不存在直接gc掉
  2. 检查该key的版本号是否和内存索引的版本号一致，不一致直接gc掉
  3. 版本号一致，检查inflight_delete字典中是否存在该key，如果存在说明将要被删除，直接gc掉

可以看到以上过程解决了并发问题，但怎么解决的delete key本身被gc掉呢？

  1. 该delete key如果在内存索引中找到了节点，显然可以gc掉
  2. 若内存中没有对应索引节点，因value值存的当前文件的seq_num，判断该seq_num是否已经是最小的了，如果是，说明不会有旧版本的数据了，gc掉。

很明显，这种解决delete key本身被gc的方法并不是很完美，因为哈希引擎本身就不应该对文件的seq_num有多大的顺序预期。很容易导致很长时间都不gc掉。

aerospike的解决思路

首先几乎只有官方文档的介绍，代码中持久删除的部份全部被抹掉了。因此下文都是推断

  1. aerospike的defrag线程拿到某个需要gc的key时，会去取key对于的内存索引，取得时候加锁，并保持全程hold锁
  2. defrag线程迁移搬运该key到新的wblock，然后回填内存索引，最终才释放锁。

可以看到aerospike用这种方法实现了垃圾回收过程，ssd和内存操作的原子性。为什么全程hold锁不会损耗性能呢？因为都是内存操作，不会调用sync。

那aerospike怎么解决的gc掉delete key本身呢？

  1. 其删除操作不会真正删除内存索引节点，而是打上墓碑标记
  2. 因此扫到delete key本身时，很容易判断该delete key是不是最新的一个，不是直接删即可

那还是有问题，内存索引如果不回收，岂不是内存无限增大？

  1. aerospike有墓碑标记回收程序，定期扫描红黑树进行回收

而墓碑扫描程序，设计细节均未给出。