萬字長文!對比分析了多款存儲方案,KeeWiDB最終選擇自己來

来源:https://www.cnblogs.com/tencentdb/archive/2022/11/27/16929984.html
-Advertisement-
Play Games

大數據時代,無人不知Google的“三駕馬車”。“三駕馬車”指的是Google發佈的三篇論文,介紹了Google在大規模數據存儲與計算方向的工程實踐,奠定了業界大規模分散式存儲系統的理論基礎,如今市場上流行的幾款國產資料庫都有參考這三篇論文。 《The Google File System》,200 ...


大數據時代,無人不知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的研發工作。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1. 查看Linux伺服器版本信息 # cat /etc/redhat-release CentOS Linux release 7.4.1708 (Core) 2. 禪道開源版安裝包下載 wget http://dl.cnezsoft.com/zentao/9.8.2/ZenTaoPMS.9.8. ...
  • 目錄 一.OpenGL 色階 1.Windows OpenGL ES 版本 2.Windows OpenGL 版本 二.OpenGL 色階 GLSL Shader 三.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 基礎 零基礎 Ope ...
  • 我們都知道在Java編程中多線程的同步使用synchronized關鍵字來標識,那麼這個關鍵字在JVM底層到底是如何實現的呢。 我們先來思考一下如果我們自己實現的一個鎖該怎麼做呢: 首先肯定要有個標記記錄對象是否已經上鎖,執行同步代碼之前判斷這個標誌,如果對象已經上鎖線程就阻塞等待鎖的釋放。 其次要 ...
  • JZ7重建二叉樹 描述 給定節點數為 n 的二叉樹的前序遍歷和中序遍歷結果,請重建出該二叉樹並返回它的頭結點。 例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6} 提示: 1.vin.length == pre.length 2.pre 和 vin ...
  • 本文是對Datawhale的動手學數據分析課程的學習總結,記錄了整體的學習過程、答案以及個人感想,代碼較為詳細。 ...
  • 簡介 本文的初衷是希望幫助那些有其它平臺視覺演算法開發經驗的人能快速轉入Halcon平臺下,通過文中的示例開發者能快速瞭解一個Halcon項目開發的基本步驟,讓開發者能把精力完全集中到演算法的開發上面。 首先,你需要安裝Halcon,HALCON 18.11.0.1的安裝包會放在文章末尾。安裝包分開發和 ...
  • 一、併發與競爭簡介 併發:多個“用戶”同時訪問一個共用的記憶體。 競爭:多個“用戶”同時訪問一段共用的記憶體並對其修改,就會造成數據混亂,甚至程式崩潰,這就是競爭。 二、造成併發與競爭的原因 1、多線程併發訪問, Linux 是多任務(線程)的系統,所以多線程訪問是最基本的原因。 2、搶占式併發訪問, ...
  • Systemd為Linux中的初始化init系統,用於啟動與停止服務進程,設計目標為:儘可能啟動更少進程、更多進程並行啟動;Systemd使用Linux的CGroup特性用來跟蹤與管理進程的生命周期,在服務啟動時會併發創建依賴的服務進程,子進程繼承父進程CGroup相關服務進程歸屬與同一個CGrou ...
一周排行
    -Advertisement-
    Play Games
  • 1.部署歷史 猿友們好,作為初來實習的我,已經遭受社會的“毒打”,所以請容許我在下麵環節適當吐槽,3Q! 傳統部署 ​ 回顧以往在伺服器部署webapi項目(非獨立發佈),dotnet環境、守護進程兩個逃都逃不掉,正常情況下還得來個nginx代理。不僅僅這仨,可能牽扯到yum或npm。node等都要 ...
  • 隨著技術的進步,跨平臺開發已經成為了標配,在此大背景下,ASP.NET Core也應運而生。本文主要基於ASP.NET Core+Element+Sql Server開發一個校園圖書管理系統為例,簡述基於MVC三層架構開發的常見知識點,前一篇文章,已經簡單介紹瞭如何搭建開發框架,和登錄功能實現,本篇... ...
  • 這道題只要會自定義cmp恰當地進行排序,其他部分沒有什麼大問題。 上代碼: 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,s,h1,h2,cnt; 4 struct apple{ 5 int height,ns;//height為蘋 ...
  • 這篇文章主要描述RPC的路由策略,包括為什麼需要請求隔離,為什麼不在註冊中心中實現請求隔離以及不同粒度的路由策略。 ...
  • 簡介: 中介者模式,屬於行為型的設計模式。用一個中介對象來封裝一系列的對象交互。中介者是各對象不需要顯式地相互引用,從而使其耦合鬆散,而且可以獨立地改變他們之間的交互。 適用場景: 如果平行對象間的依賴複雜,可以使用中介者解耦。 優點: 符合迪米特法則,減少成員間的依賴。 缺點: 不適用於系統出現對 ...
  • 【前置內容】Spring 學習筆記全系列傳送門: Spring學習筆記 - 第一章 - IoC(控制反轉)、IoC容器、Bean的實例化與生命周期、DI(依賴註入) Spring學習筆記 - 第二章 - 註解開發、配置管理第三方Bean、註解管理第三方Bean、Spring 整合 MyBatis 和 ...
  • 簡介: 享元模式,屬於結構型的設計模式。運用共用技術有效地支持大量細粒度的對象。 適用場景: 具有相同抽象但是細節不同的場景中。 優點: 把公共的部分分離為抽象,細節依賴於抽象,符合依賴倒轉原則。 缺點: 增加複雜性。 代碼: //用戶類 class User { private $name; fu ...
  • 這次設計一個通用的多位元組SPI介面模塊,特點如下: 可以設置為1-128位元組的SPI通信模塊 可以修改CPOL、CPHA來進行不同的通信模式 可以設置輸出的時鐘 狀態轉移圖和思路與多位元組串口發送模塊一樣,這裡就不給出了,具體可看該隨筆。 一、模塊代碼 1、需要的模塊 通用8位SPI介面模塊 `tim ...
  • AOP-03 7.AOP-切入表達式 7.1切入表達式的具體使用 1.切入表達式的作用: 通過表達式的方式定義一個或多個具體的連接點。 2.語法細節: (1)切入表達式的語法格式: execution([許可權修飾符] [返回值類型] [簡單類名/全類名] [方法名]([參數列表]) 若目標類、介面與 ...
  • 測試一、虛繼承與繼承的區別 1.1 單個繼承,不帶虛函數 1>class B size(8): 1> + 1> 0 | + (base class A) 1> 0 | | _ia //4B 1> | + 1> 4 | _ib //4B 有兩個int類型數據成員,占8B,基類邏輯存在前面 1.2、單個 ...