万字长文!对比分析了多款存储方案,KeeWiDB最终选择自己来

万字长文!对比分析了多款存储方案,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则至底向上,这种动态分配方式,空间利用率更高

file
图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块

file
图2 Page组成结构

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

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

file
图3 PageManager组成结构

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

file
图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过长,导致读写性能下降。

file
图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时,映射关系为一对一。

file
图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。

file
图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。

file
图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。下面我们将分别对每个层次的内容和作用作一个概述。

file
图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的起始页的位置信息;

file
图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的常驻内存,便可以索引数十亿个元素

file
图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数组是实际存储元素的地方,其和元素一一对应。

file
图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的状态。

file
图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结构。

file
图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。

file
图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

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

file
图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读锁。

file
图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的引用,则释放它。

file
图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的研发工作。

原文地址:https://www.cnblogs.com/tencentdb/archive/2022/11/27/16929984.html