关于数据库:万字长文对比分析了多款存储方案KeeWiDB最终选择自己来

大数据时代，无人不知 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 indexpagearray 构造示意图

读者可能有疑难，既然 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 的研发工作。