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