大数据时代，无人不知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的研发工作。