大数据时代，无人不知 Google 的“三驾马车”。“三驾马车”指的是 Google 发布的三篇论文，介绍了 Google 在大规模数据存储与计算方向的工程实践，奠定了业界大规模分布式存储系统的理论基础，如今市场上流行的几款国产数据库都有参考这三篇论文。

• 《The Google File System》，2003 年

• 《MapReduce: Simplified Data Processing on Large Clusters》，2004 年

• 《Bigtable: A Distributed Storage System for Structured Data》，2006 年

其中，Bigtable 是数据存储领域的经典论文，这篇论文首次对外完整、系统的叙述了 Google 是如何将 LSM-Tree 架构应用在工业级数据存储产品中的。熟悉数据库的朋友，一定对 LSM-Tree 不陌生。LSM-Tree 起源于上世纪 70 年代，1996 年被正式提出，之后 Google 成功实现商业化应用。

LSM-Tree 的核心思想是“Out-of-Place Update”，可以将离散随机写转化为批量顺序写，这对机械硬盘作为主流存储介质的时代而言，能大幅度提升系统吞吐。现如今，已经有一大批成熟的 KV 存储产品采用了 LSM-Tree 架构，例如 DynamoDB, HBase, Cassandra 和 AsterixDB 等。然而，工程实践往往存在一种取舍，几乎很难找到一个完美契合所有应用场景的设计。LSM-Tree 在带来优秀的写入性能的同时，也带来了读写放大和空间放大问题。

随着硬件技术的发展，固态硬盘逐渐替代机械硬盘成为存储的主流，曾经的核心因素（随机写和顺序写的性能差异）现在也不再那么核心。那么现在存储系统设计的核心是什么呢？KeeWiDB 倒是可以给你答案！

高性能、低成本！如何减小固态硬盘擦除次数？如何延长使用寿命？这些都是 KeeWiDB 研发团队重点突破的地方。基于此，本文将重点阐述 KeeWiDB 中存储引擎的设计概览，详细介绍数据如何存储、如何索引，给读者提供一些 KeeWiDB 的思考和实践。

存储层

图 1 展示的是存储在磁盘上的数据文件格式，数据文件由若干个固定大小的 Page 组成，文件头部使用了一些 Page 用于存储元信息，包括和实例与存储相关的元信息，元信息后面的 Page 主要用于存储用户的数据以及数据的索引，尾部的 Chunk Page 则是为了满足索引对连续存储空间的需求。Page 至顶向下分配，Chunk Page 则至底向上，这种动态分配方式，空间利用率更高。

图 1 KeeWiDB 的存储层架构

和主流涉盘型数据库相似，我们使用 Page 管理物理存储资源，那么 Page 大小定为多少合适呢？

我们知道 OS 宕机可能产生 Partial Write，而 KeeWiDB 作为一个严格的事务型数据库，数据操作的持久性是必须满足的核心性质之一，所以宕机不应该对数据的可用性造成影响。

针对 Partial Write 问题，业界主流的事务型数据库都有自己的解决方案，比如 MySQL 采用了 Double Write 策略，PostgreSQL 采用了 Full Image 策略，这些方案虽然可以解决该问题，但或多或少都牺牲了一定的性能。得益于 SSD 的写盘机制，其天然就对物理页写入的原子性提供了很好的实现基础，所以利用这类硬件 4K 物理页写入的原子特性，便能够在保证数据持久性的同时，而不损失性能。此外，由于我们采用的索引相对稳定，其 IO 次数不会随着 Page 页大小改变而显著不同。故权衡之下，我们选择 4K 作为基本的 IO 单元。

至此，我们知道 KeeWiDB 是按照 4K Page 管理磁盘的出发点了，那么是否数据就能直接存储到 Page 里面呢？

如你所想，不能。针对海量的小值数据，直接存储会产生很多内部碎片，导致大量的空间浪费，同时也会导致性能大幅下降。解决办法也很直观，那就是将 Page 页拆分为更小粒度的 Block。

图 2 展示了 Page 内部的组织结构，主要包括两部分：PageHeaderData 和 BlockTable。PageHeaderData 部分存储了 Page 页的元信息。BlockTable 则是实际存储数据的地方，包含一组连续的 Block，而为了管理方便和检索高效，同一个 BlockTable 中的 Block 大小是相等的。通过 PageHeaderData 的 BitTable 索引 BlockTable，结合平台特性，我们只需要使用一条 CPU 指令，便能够定位到页内空闲的 Block 块。       

图 2 Page 组成结构

而为了满足不同用户场景的数据存储，存储层内部划分了多个梯度的 Block 大小，即多种类型的 Page 页，每种类型的 Page 页则通过特定的 PageManager 管理。

图 3 展示了 PageManager 的主要内容，通过 noempty_page_list 可以找到一个包含指定 Block 大小的 Page 页，用于数据写入；如果当前 noempty_page_list 为空，则从全局 Free Page List 中弹出一个页，初始化后挂在该链表上，以便后续用户的写入。当 Page 页变为空闲时，则从该链表中摘除，重新挂载到全局 Free Page List 上，以便其它 PageManager 使用。  

图 3 PageManager 组成结构

想必大家已经发现上面的数据块分配方式，和 tcmalloc，jemalloc 等内存分配器有相似之处。不同的是，作为磁盘型空间分配器，针对大块空间的分配，KeeWiDB 通过链表的方式将不同的类型的 Block 链接起来，并采用类似 Best-Fit 的策略选择 Block。如图 4 所示，当用户数据为 5K 大小时，存储层会分配两个 Block，并通过 Block 头部的 Pos Info 指针链接起来。这种大块空间的分配方式，能够较好的减小内部碎片，同时使数据占用的 Page 数更少，进而减少数据读取时的 IO 次数。       

图 4 Block 链式结构

以上便是用户数据在 KeeWiDB 中存放的主要形式。可以看出，用户数据是分散存储在整个数据库文件中不同 Page 上的，那么如何快速定位用户数据，便是索引的主要职责。

索引层

2.1 选型

KeeWiDB 定位是一个 KV 数据库，所以不需要像关系型数据库那样，为了满足各种高性能的 SQL 操作而针对性的建立不同类型的索引。通常在主索引上，对范围查询需求不高，而对快速点查则需求强烈。所以我们没有选择在关系型数据库中，发挥重要作用的 B-Tree 索引，而选择了具有常数级等值查询时间复杂度的 hash 索引。

hash 索引大体上存在两类技术方案 Static Hashing 和 Dynamic Hashing。前者以 Redis 的主索引为代表，后者以 BerkeleyDB 为代表。如图 5 所示，Static Hashing 的主要问题是：扩容时 Bucket 的数量翻倍，会导致搬迁的数据量大，可能阻塞后续的读写访问。基于此，Redis 引入了渐进式 Rehash 算法，其可以将扩容时的元素搬迁平摊到后续的每次读写操作上，这在一定程度上避免了阻塞问题。但由于其扩容时仍然需要 Bucket 空间翻倍，当数据集很大时，可能导致剩余空间无法满足需求，进而无法实现扩容，最终使得 Overflow Chain 过长，导致读写性能下降。       

图 5 Static Hashing 扩容示意图

Dynamic Hashing 技术旨在解决 Overflow Chain 过长的问题，核心思想是在 Bucket 容量达到阈值时，进行单个 Bucket 的分裂，实现动态扩容，而不是当整个 hash table 填充率达到阈值时才扩容。这样可以避免数据倾斜时，导致某个桶 Overflow Chain 过长，影响处理延迟。同时动态扩容每次只需一个 Bucket 参与分裂，扩容时搬迁数据量小。Dynamic Hashing 通常有两种选型：Extendible Hashing 和 Linear Hashing。这两种算法都实现了上述动态扩容的特性，但实现方式有所不同。

如图 6 所示，Extendible Hashing 使用 Depth 来表达参与运算的 hashcode 的最低有效位的长度。Local Depth 和 Bucket 绑定，表示其中元素指定的最低有效位相等，等价于 hash 取模。Global Depth 则表示全局参与运算的最低有效位长度的最大值，即代表当前逻辑 Bucket 的个数。Directory 是指针数组，用于指代逻辑 Bucket 的物理位置信息，和物理 Bucket 存在多对一的映射关系，当 Bucket 的 Local Depth 等于 Global Depth 时，映射关系为一对一。

图 6 Extendible Hashing 扩容示意图

我们看看 Extendible Hashing 是怎么处理扩容的。若插入元素后，Bucket 容量达到阈值，首先将该 Bucket 的 Local Depth 加 1，然后分情况触发扩容：

1. 若当前 Bucket 的 Local Depth < Global Depth，则只需要将该 Bucket 分裂，重设 Directory 指针即可。

2. 若当前 Bucket 的 Local Depth == Global Depth，则不仅需要分裂该 Bucket，同时还需要将 Directory 翻倍，并重设指针。

以图 6 为例，Bucket 2 中的元素在扩容前，参与运算的最低有效位为 10(Local Depth 等于 2)；在扩容时，首先将 Local Depth 加 1，然后最低有效位为 010 的元素保持不动，而其余有效位为 110 的元素，便被搬迁到物理 Bucket 6 中。由于 Global Depth 小于 Local Depth，所以需要对 Directory 数组翻倍扩容，然后将逻辑 Bucket 6 的位置信息，指向物理 Bucket 6。其余逻辑 Bucket 4，5 和 7，则分别指向现存的物理 Bucket 0，1，和 3。

Extendible Hashing 可以完全避免 Overflow Chain 的产生，使元素的读取效率很高，但也存在弊端：Directory 需要翻倍扩容，同时重设指针代价高。虽然 Directory 存储的只是位置信息，和 Static Hashing 相比空间利用率更高，但仍然无法避免当 Bucket 数量很大时，扩容对大块空间的需求。同时扩容需要重设的 Directory 指针数据量，可能会随着数据集的增大而增大。这对涉盘型数据库来说，需要大量的磁盘 IO，这会极大增加处理的长尾延迟。

Linear Hashing 和 Extendible Hashing 相似，若插入操作导致 Bucket 容量达到阈值，便会触发分裂。不同的是，分裂的 Bucket 是 next_split_index 指向的 Bucket，而不是当前触发分裂的 Bucket。这种按顺序分裂的机制，弥补了 Extendible Hashing 需要重设指针的缺点。如图 7 所示，当 Bucket 1 插入元素 17 后达到了容量限制，便触发分裂，分裂 next_split_index 指代的 Bucket 0，最低有效位为 000 的元素保持不动，把最低有效位为 100 的元素搬迁到新建的 Bucket 4 中，并将 next_split_index 向前递进 1。       

图 7 Linear Hashing 扩容示意图

Extendible Hashing 通过 Directory 指针数组索引 Bucket 位置信息，而 Linear Hashing 则通过两个 hash 表来解决定位问题。如图 8 所示，和采用渐进式 Rehash 的 Redis 相似，可以将 hash table 看作同时存在一小一大两个表，分别以 low_mask 和 high_mask 表征。当定位元素所属 Bucket 时，主要分为以下几步：

• 通过散列函数计算得到元素的 hashcode；

• 通过 low_mask 计算元素的候选 bucket_index，bucket_index = hashcode & low_mask；

• 若 bucket_index >= next_split_index，则其为目标 Bucket；

• 若 bucket_index < next_split_index，说明其对应的 Bucket 已经被分裂，那么参与运算的最低有效位数应该增加 1 位，即需要通过 high_mask 计算元素的目标 bucket_index，bucket_index = hashcode & high_mask。

图 8 Linear Hashing 访问示意图

当然 Linear Hashing 也存在一个缺点：如果数据不均匀，则可能导致某个 Bucket 无法及时分裂，进而产生 Overflow Chain。但相比 Static Hashing 而言，其长度要短很多。同时工程实践中，可以通过预分配一定数量的 Bucket，缓解数据倾斜的问题。如果再适当调小触发 Bucket 分裂的容量阈值，几乎可以做到没有 Overflow Chain。结合 Extendible Hashing 存在扩容时磁盘 IO 不稳定的问题，我们最终选择了 Linear Hashing 作为 KeeWiDB 的主索引。

2.2 详细设计

2.2.1 基础架构

接下来我们将走近 KeeWiDB，看看 Linear Hashing 的工程实践。如图 9 所示，整个索引可以概括为三层：HashMetaLayer，BucketIndexLayer 和 BucketLayer。下面我们将分别对每个层次的内容和作用作一个概述。     

图 9 Linear Hashing 实现架构图

HashMetaLayer

HashMetaLayer 主要用于描述 hash table 的元信息。如图 10 所示，主要包括以下内容：

• current_size: 当前 hash table 存储的元素个数；

• split_bucket_index: 下次需要分裂的 Bucket 逻辑编号；

• current_bucket_count: 当前使用的 Bucket 数量；

• low_mask: 用于映射 hash table 的小表，high_mask =（low_mask << 1) | 1；

• index_page_array: 用于存储分段连续的 IndexPage 的起始页的位置信息；

图 10 hash meta 组成结构

BucketIndexLayer

BucketIndexLayer 表示一组分段连续的 IndexPage 页面。IndexPage 主要用于存储物理 Bucket 的位置信息，其作用类似于 Extendible Hashing 的 Directory 数组。通过引入 BucketIndexLayer，可以使物理 Bucket 离散分布于数据库文件中，避免对连续大块存储空间的需求。引入额外的层次，不可避免的会导致 IO 和 CPU 的消耗，我们通过两个方面来减小消耗。

首先，通过 hash meta 存储的 index_page_array，将定位目标 Bucket 的时间复杂度做到常数级，减小 CPU 消耗。由于每个 IndexPage 所能容纳的 Bucket 位置信息数量是固定的，所以如果将 IndexPage 看作逻辑连续的 Page 数组时，就可以在 O(1)时间复杂度下计算出 Bucket 所属的 IndexPage 逻辑编号，以及其在 IndexPage 内部的偏移。再把分段连续的 IndexPage 的第一个页的物理位置信息记录在 index_page_array 数组中，定位到 IndexPage 的物理位置便也为常数级。如图 11 所示，连续的 IndexPage 的页面个数与 index_page_array 的数组索引的关系为分段函数。采用分段函数主要基于以下考虑：

• 减小空间浪费。使每次分配的 IndexPage 数量，随着数据量的增大而增大，而不是维持固定值，避免小数据量时造成空间浪费。特别是在多 DB 场景下(索引相互独立)，用户数据倾斜时，这种空间浪费会被放大；

• 增加空间使用的灵活性。每次分配 IndexPage 的数量也不能无限增大，避免无法分配大块的连续空间。

再者，我们通过内存缓存避免 IndexPage 的额外 IO 消耗，KeeWiDB 通过 10MB 的常驻内存，便可以索引数十亿个元素。    

图 11 index_page_array 结构示意图

读者可能有疑问，既然 IndexPage 可以做到分段连续，那为何不直接将 BucketPage 做到分段连续，这样可以避免引入 IndexPage，似乎还能减少 IO 次数。不这么做，是因为相同大小的连续空间，前者能索引的元素个数是后者的数百倍，所以在多 DB 场景下，前者更具有优势。与此同时，如果采用相似的索引策略，后者也并不能减小 IO 次数，因为 bucket_page_array 是 index_page_array 的数百倍大，这会导致 hash meta 无法存放在一个 Page 中，导致 IO 次数增加。所以，最终我们选择牺牲少量内存空间，以提高磁盘空间使用的灵活性。

BucketLayer

BucketLayer 则是最终存储 hash 元素，即用户数据索引的地方。每一个逻辑 Bucket 由一组物理 BucketPage 链接而成，即采用开链法解决 hash 冲突，只是链接的单位是 Page 页而不是单个元素。BucketPage 链表头称为 PrimaryBucketPage，其余则为 OverflowBucketPage。如图 12 所示，BucketPage 主要包括两方面内容：代表元信息的 Header 和存储数据的 Blocks。Header 存储的内容又可以分为两部分：表征 Bucket 结构和状态的 Normal Meta，以及表征 BucketPage 内部 Blocks 存储状态的 blocks map。Blocks 数组是实际存储元素的地方，其和元素一一对应。    

图 12 Bucket Page 组成结构

BucketPage 可以看作是一个按照元素 hashcode 排序的有序数组。元素查找主要分为三步：

• 首先通过 blocks_sort_map，二分查找与待查键 hashcode 相等的 index；

• 通过 index 内记录的 block_index，找到其对应的 Blocks 数组中的元素，即为候选索引；

• 通过该候选索引读取存储的用户数据，若存储的数据健与待查健二进制相等，则该索引即是目标索引。

更新操作只需要将查找到的 Blocks 数组中对应的 Block 替换为新的元素。而元素插入操作在查找无果的基础上，还需要以下几步：

• 通过 blocks_alloc_map 找到 Blocks 数组的空位，并将对应的 bit 位置 1；

• 将元素插入到该 Blocks 数组指定的空位中；

• 构建 index，更新 blocks_sort_map。

同样，元素删除操作在查找成功后，也需要额外几步：

• 通过 blocks_alloc_map 找到指定的 bit 位，将其置为 0；

• 删除 index，更新 blocks_sort_map。

除了用户触发的读写操作，hash table 自身还存在分裂和合并操作。如图 13 所示，展示了 Bucket 分裂和合并时的状态转化图，Bucket 主要存在五种状态：

• Normal：常规状态；

• BeingSplitted：分裂状态。触发分裂时，源端 Bucket 的状态；

• BeingMerged: 合并状态。触发合并时，源端 Bucket 的状态；

• BeingFilled：填充状态。触发分裂(合并)时，目的端 Bucket 的状态；

• BeingCleanup：清理状态。分裂(合并)完成时，源端 Bucket 的状态。

图 13 Bucket 状态转换图

如图 14 所示，Bucket 分裂操作主要分为三个阶段：

• Prepare 阶段：创建目的 Bucket 物理页，更新 hash table 结构，分别设置源端和目的端 Bucket 状态为 BeingSplitted 和 BeingFilled；

• Split 阶段：将源端 Bucket 的数据，按照 high_mask 重新 rehash，将不再属于该 Bucket 的数据拷贝至目的 Bucket；

• Cleanup 阶段：将不再属于源端 Bucket 的数据清理掉。

和分裂操作相似，Bucket 的合并操作也分为三个阶段：

• Prepare 阶段：分别设置源端和目的端 Bucket 状态为 BeingMerged 和 BeingFilled。

• Merge 阶段：将源端 Bucket 数据，拷贝至目的端 Bucket。

• Cleanup 阶段：清理源端 Bucket，更新 hash table 结构。

图 14 Bucket 分裂和合并示意图

那么，正常读写场景下，用户访问延迟有多大呢？现在我们梳理下，用户写入数据时典型的 IO 路径：

• 存储层分配数据 Block，用于存放用户数据，并构建用户数据索引信息；

• 查找主索引的元数据 HashMetaBlock；

• 通过用户数据键的 hashcode 值，计算得到目标 Bucket 逻辑编号，并定位 IndexPage；

• 通过 IndexPage 找到对应的 BucketPage，插入用户数据索引。

由于 HashMetaBlock 和 IndexPage 数据量很小(亿级数据集只需几兆空间)，可以直接缓存在内存中。那么一次典型的小值写入，平均只需要两次 IO：一次数据写入，一次索引写入，这样平均处理延迟就能维持在较低的水平。随着数据集的增大，写入可能触发分裂式扩容，而大多数场景下，扩容只会涉及 2 个 BucketPage，即只需要额外两次 IO，且 IO 次数不会随着数据量的增大而增大，这样处理的长尾延迟就相对稳定可控。

2.2.2 并发控制

读者通过架构篇可以了解到，KeeWiDB 采用了 Shared-Nothing 的架构设计，宏观上将数据集按 Slot 进行了拆分，每个线程独立负责部分 Slot 数据的读写，即发挥了多核并发的优势。而对于线程内部的读写访问，则引入了协程机制，来提高单核处理能力。协程级并发意味着可能存在多个协程同时访问系统资源，与主流关系型数据库相似，KeeWiDB 通过两阶段锁实现事务 serializable 级别的隔离性要求，关于事务的相关内容，后续我们会有专题进行详细介绍。这里我们主要讨论的是，存储引擎层是如何保障数据访问的并发安全。

hash 索引的并发控制，其核心是需要满足以下要求：

• 读取保障：不会读取到中间状态的值，记作 R-1；

• 读取保障：不会因为分裂(合并)，导致读取不到原本应该存在的值，记作 R-2；

• 写入保障：并发写入不会互相干扰，即写入满足原子性，记作 W-1；

• 写入保障：不会因为分裂(合并)，导致丢失更新，记作 W-2；

• 自恢复保障：不会因为中途宕机，导致 hash table 结构被破坏，无法恢复服务，记作 SR。

总体上，hash 索引主要采用了三种锁确保并发安全：

• Page 锁：读写物理锁，确保物理页访问的原子性；

• Bucket 锁：Bucket 级别读写逻辑锁，确保分裂(合并)时，写入的并发正确性；

• Exclusive 锁：特殊的 Page 写锁，该 Page 无他人引用。

什么是引用计数呢？如图 15 所示，Page 从磁盘加载上来之后，存储在 Cache 模块的 Buffer 数组中，并通过 PageDesc 索引。每当用户请求相关 Page，便使其引用计数加 1，释放 Page 则引用计数减 1，后台协程会通过算法周期性的选择引用计数为 0 的页淘汰。Exclusive 锁的含义就是除了请求者之外，无他人引用，即引用计数为 1。   

图 15 Page Cache 模块示意图

下面将分别从内部 hash table resize 和外部用户读写两个典型场景，简要描述我们是如何做到并发安全的。为了后续行文方便，现在对部分简写的含义作如下说明：

• PageWriteLock(X)，PageReadLock(X)：持有 X 资源的 Page 写锁或读锁。

• PageWriteUnlock(X)，PageReadUnlock(X)：释放持有的 X 资源的 Page 写锁或读锁。

• ExclusiveLock(X)，ExclusiveUnlock(X)：持有或释放 X 资源的 Exclusive 锁。

• BucketWriteLock(X)，BucketReadLock(X)：持有编号为 X 的 Bucket 的写锁或读锁。

• BucketWriteUnlock(X)，BucketReadUnlock(X)：释放持有的编号为 X 的 Bucket 的写锁或读锁。

• LoadFromDisk(X)：从磁盘加载 X 表征的物理页，存放在 Cache 模块中。若已经成功加载，则只将引用计数加 1。

• HMB：代表 HashMetaBlock。

• IP-X：代表逻辑编号为 X 的 IndexPage。

• B-X: 代表逻辑编号为 X 的 Bucket。

• PBP-X：代表 B-X 对应的 PrimaryBucketPage。

• OBP-X：代表 B-X 对应的 OverflowBucketPage。

hash table resize

由于合并操作和分裂操作，几乎互为相反操作。所以下面将主要以分裂为例，分析加入并发控制之后的分裂操作是如何处理的。       

图 16 hash 分裂并发控制示意图

如图 16 所示，Prepare 阶段的主要操作步骤如下：

• LoadFromDisk(HMB)，PageReadLock(HMB)；

• 根据 meta 信息，定位目标 Bucket 及其所属 IndexPage(此例为 B-0 和 IP-0)；

• 尝试按序获取 B-0 的 Bucket 读锁和 B-1 的 Bucket 写锁，PageReadUnlock(HMB)；

• 若 B-0 或 B-1 的 Bucket 锁未成功锁定，则释放已持有的锁，直接返回；

• LoadFromDisk(IP-0)，PageReadLock(IP-0)。获取 PBP-0 位置信息，PageReadUnlock(IP-0)；

• LoadFromDisk(PBP-0)，LoadFromDisk(PBP-1)；

• WriteLock(HMB)，WriteLock(IP-0)，PageWr iteLock(PBP-0)，PageWriteLock(PBP-1)；

• 更新 PBP-0 的状态为 BeingSplitted，更新 PBP-1 的状态为 BeingFilled；

• 将 PBP-1 的位置信息记录在 IP-0 中；

• 更新 HMB 元信息字段：next_split_index，current_Bucket_count；

• 写入表示数据修改的 WAL 日志；

• WriteUnlock(IP-0)，WriteUnlock(HMB)。

同时持有所有待修改页面 Page 锁的目的是：确保多页修改的原子性。极小部分场景下，WAL 日志写入可能引起协程切换，而后台 Page 刷脏协程可能获得执行权，如果此时不对所有页加锁，则可能导致部分页的修改持久化，而索引通常无法记录回滚日志，所以最终可能导致 hash table 结构的错乱。

Split 阶段的主要操作步骤如下：

• 遍历 PBP-0 中元素，按照 high_mask 进行 rehash，将不再属于 PBP-0 的元素拷贝至 B-1 链中；

• 若 B-0 还存在 Overflow Page，则 PageWriteUnlock(PBP-0)；

• LoadFromDisk(OBP-0)，PageReadLock(OBP-0)。遍历 OBP-0 中元素，按照 high_mask 进行 rehash，将不再属于 PBP-0 的元素拷贝至 B-1 链中；

• 若 B-0 还存在 Overflow Page，则 PageReadUnlock(OBP-0)，从步骤 3 开始重复执行，直到遍历完 B-0 整个链表；

• WriteLock(PBP-0)，WriteLock(PBP-1)；

• 更新 PBP-0 的状态为 BeingCleanup，更新 PBP-1 的状态为 Normal；

• WriteUnlock(PBP-0)，WriteUnlock(PBP-1)；

• BucketReadUnlock(0)，BucketWriteUnlock(1)。

在 Split 阶段数据拷贝过程中，若 B-1 当前 BucketPage 写满，则需要增加 Overflow Page 用于后续写入，而此操作涉及页面分配，可能让出执行权，所以为了避免影响 B-1 的并发读取操作，会首先将当前 BucketPage 的写锁释放。Cleanup 阶段的主要操作步骤如下：

• LoadFromDisk(PBP-0)；

• 尝试获取 PBP-0 的 Exclusive 锁，若获取失败，直接退出；

• 遍历 PBP-0 中元素，按照 high_mask 进行 rehash，将不再属于 PBP-0 的元素清理掉；

• 若 B-0 还存在 Overflow Page，则 PageWriteUnlock(PBP-0)；

• LoadFromDisk(OBP-0)，PageWriteLock(OBP-0)。遍历 OBP-0 中元素，按照 high_mask 进行 rehash，将不再属于 OBP-0 的元素清理掉；

• 若 B-0 还存在 Overflow Page，则 PageWriteUnlock(OBP-0)，从步骤 5 开始重复执行，直到遍历完 B-0 整个链表；

• WriteLock(PBP-0)，更新 PBP-0 的状态为 Normal，WriteUnLock(PBP-0)。

通过将分裂操作拆分为三个阶段，主要是为了提高等待磁盘 IO 时的并发度。当 Prepare 阶段完成时，新的 hash table 结构便对后续读写可见，不论是用户读写还是 hash table resize 操作都可以基于新的结构继续执行，即可能同时存在多个 Bucket 的并发分裂操作，这样就能有效避免某次 Bucket 分裂耗时过长(等待磁盘 IO)，导致其余 Bucket 无法及时分裂，进而影响访问延迟的问题。同时，将 Split 操作和 Cleanup 操作分开，也是为了能在等待新页分配的时候，可以释放 Page 锁，避免影响并发读写。

read && write

如图 17 所示，加入并发控制后，典型的写入流程主要分为以下几步：

• LoadFromDisk(HMB)，PageReadLock(HMB)。根据 meta 信息，定位目标 Bucket 及其所属 IndexPage(此例为 B-0 和 IP-0)，PageReadUnlock(HMB)；

• LoadFromDisk(IP-0)，PageReadLock(IP-0)。读取 PBP-0 的位置信息，PageReadUnlock(IP-0)；

• 获取 B-0 的 Bucket 读锁；

• 遍历 B-0 的链表，直到结束或找到待查元素，然后写入或更新相关元素。遍历过程中，在访问 BucketPage 前，先加写锁，访问完后立即解锁；

• 释放 B-0 的 Bucket 读锁。

图 17 hash 写入并发控制示意图

如图 18 所示，典型的读取流程主要分为以下几步：

• LoadFromDisk(HMB)，PageReadLock(HMB)。根据 meta 信息，定位目标 Bucket 及其所属 IndexPage(此例为 B-1 和 IP-0)，PageReadUnlock(HMB)；

• LoadFromDisk(IP-0)，PageReadLock(IP-0)。读取 PBP-1 的位置信息，PageReadUnlock(IP-0)；

• LoadFromDisk(PBP-1)，PageReadLock(PBP-1)；

• 若 PBP-1 当前状态为 BeingFilled，则 PageReadUnlock(PBP-1)，同时 LoadFromDisk(PBP-0)，持有 PBP-0 引用；

• 遍历 B-1 的链表，直到结束或找到待查元素。遍历过程中，在访问 BucketPage 前，先加读锁，访问完后立即解锁；

• 若 B-1 链表无法找到对应元素，且已经持有 PBP-0 的引用。则以遍历 B-1 链表相同的方式，遍历 B-0 链表；

• B 若持有 PBP-0 的引用，则释放它。     

图 18 hash 读取并发控制示意图

以上便是加入并发控制之后，hash 读写的主要流程，限于篇幅上述流程简化了部分故障恢复和冲突检测逻辑。现在我们来回顾下，前文提到的并发安全保障是否得到了满足。由于我们在读取 Page 前，都获取了该 Page 的读或写锁，所以保证了读写的原子性，即 R-1 和 W-1 得到保障。读取操作则通过事先持有待分裂 Bucket 的引用，避免了分裂过程中，无法读取到已存在的元素，即 R-2 也得到保障。写入操作通过事先获取 Bucket 逻辑读锁，保证了不会因为分裂操作，导致丢失更新的问题，即满足了 W-2 要求。最后通过保证 hash 结构变化的原子性，满足了故障重启后的自恢复性，即 SR 得到保障。

在保障了并发安全的前提下，hash 索引的并发度究竟如何呢？

在回答这个问题之前，我们先来回顾下这里使用的锁。由于我们探讨的是线程内多协程的并发，所以使用的并不是系统锁，而是简单的计数器，也就是说产生锁冲突之后，开销主要在于用户空间的协程上下文切换。那么锁冲突概率高吗？由于我们采用了非抢占式调度，所以除非当前协程主动让出执行权限，其他协程不会投入运行，也就不会产生冲突。

那什么时候让出执行权呢？绝大多数情况下，是在等待 IO 的时候。也就是说，在持有锁而让出执行权的情况下，可能会产生锁冲突。不管是读写操作还是分裂合并操作，对 Page 锁的应用都是：先加载页，再锁定资源。故一般不会出现 Page 锁冲突的情况，极少数情况下可能需要等待重做日志就绪，从而产生 Page 锁冲突。对处于 BeingFilled 状态 Bucket 的写入操作，会导致 Bucket 锁冲突，冲突概率随着 hash 表的增大而减小，且冲突时间和相关 Page 锁的冲突时间几乎相等。Exclusive 锁的冲突概率和 Bucket 锁类似。所以，工程实践中，我们会预分配一定数量的桶，以分散并发操作的 Page 页，进而减小锁冲突的概率，最终达到减小协程切换消耗的目的。

总结

本文主要介绍了 KeeWiDB 存储引擎的设计细节。首先，通过介绍存储层的基本组织结构，知道了我们使用 4K Page 作为管理整个存储文件的基本单元，而用户数据则是存储于 Page 内的 Block 中。接着，通过对比分析各类索引的特点，简述了我们选择 Linear Hashing 作为用户数据索引的主要原因。最后，深入分析了 Linear Hashing 在 KeeWiDB 中的工程实践，包括具体的组织架构，增删查改的大致流程，以及在协程架构下，如何做到并发安全的。

目前，KeeWiDB 正在公测阶段（点击进入），现已在内外部已经接下了不少业务，其中不乏有一些超大规模以及百万 QPS 级的业务，线上服务均稳定运行中。

腾讯云数据库公众号后台回复“KeeWiDB”，试试看，有惊喜。

关于作者

章俊，腾讯云数据库高级工程师，拥有多年的分布式存储、数据库从业经验，现从事于腾讯云数据库 KeeWiDB 的研发工作。