[發明專利]多線程持久性B+樹數據結構設計與實現方法

有效

• 申請號: 201811129623.3
• 申請日: 2018-09-27
• 公開（公告）號: CN109407979B
• 公開（公告）日: 2020-07-28
• 發明（設計）人: 舒繼武;陸游游;胡慶達;劉昊
• 申請（專利權）人: 清華大學
• 主分類號: G06F3/06
• 分類號: G06F3/06;G06F12/02
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張潤

1.一種多線程持久性B+樹數據結構設計與實現方法，其特征在于，包括以下步驟：

在預設的B+樹中引入一層基于鏈式結構的影子葉節點；

通過基于混合主存的數據布局策略將基于鏈表的葉節點存儲在NVM中，以生成基于數組結構的樹層，并且將索引數據結構的其他部分存儲在DRAM中，以生成基于鏈表結構的鏈層，使得通過分層的易失性樹結構和持久性鏈表結構的設計避免平衡和排序的持久化開銷；

設計嵌入式的細粒度鎖機制和樂觀寫機制，以分別用于讀寫操作之間和寫寫操作之間的并發控制，其中，所述樂觀寫機制為將樹節點和鏈表節點的并發控制機制進行分離，以將持久化延遲從樹節點粒度的加鎖路徑上移除。

2.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，其中，所述嵌入式的細粒度鎖機制為每個鏈表節點設計一個更新標記位和刪除標記位，以將不滿足預設條件的持久化延遲從讀操作的版本驗證路徑上移除。

3.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，位于所述DRAM中的基于數組結構的樹層，其每一個節點能容納預設數量的鍵值對，其中，樹節點的每個鍵值對指向下一層的樹節點或者鏈表節點，以在任意個樹節點的鍵值對數量超過或者低于預設闕值，樹節點會執行分裂或者合并操作，在上一層的樹節點中插入或者刪除一個鍵值對。

4.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，位于所述NVM中的基于數組結構的鏈層，將鏈層存儲在非易失主存中，其中，所述鏈層為一個有序的鏈表，每個鏈表節點僅存儲一個鍵值對，且用右指針相連，利用CPU原子操作保證其原子性和一致性的插入/刪除/更新操作。

5.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，每個樹操作均從根結點開始搜索，直到找到對應的葉節點，其中，在訪問任意一個樹節點之前，執行預取指令，將整個樹節點讀取到CPU緩存中，以掩蓋所述整個樹節點的訪存延遲，并且分別將鍵數組和值數組存放在不同的主存空間中，以只預取鍵數組，降低每次預取操作的數據總量。

6.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，選取預設閾值的鍵數組大小，使用線性查找操作取代二分查找操作，將所述線性查找操作放在主存空間上進行，并利用SIMD指令加速，其中，每個鍵值對配備1B的指紋，且每個指紋都是對應鍵值的哈希值，并將指紋數組存儲在葉節點的頭部。

7.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，其中，

1)對于讀寫操作間的沖突，則采用基于版本號的并發控制機制，其中，在每個樹節點上采用一個版本號計數器，版本號在每次樹節點狀態被改變的時候遞增，對于插入、刪除或者更新操作，在修改樹節點之前申請鎖，并將對應版本號置為臟，并在完成操作后且版本號加1后，釋放掉對應樹節點的鎖，且如果版本號被修改或者被加鎖，則讀操作就會重復執行1)過程，直到版本號驗證通過；

2)對于寫寫操作間的沖突，則采用樹節點粒度的鎖機制，其中，采用樹節點粒度的鎖確保修改不同樹節點的寫操作同時執行，葉節點之間通過右指針相連，并且預設所述葉節點的分裂方向只能從左往右，并自底向上申請所述樹節點的鎖，且在所述樹節點發生分裂或者刪除時，申請上一層樹節點的鎖，鏈表節點和葉節點的鍵值對有一一對應的關系，使得所述寫操作只有在獲取樹層對應葉節點的鎖之后，才會修改所述鏈表節點。

8.根據權利要求1所述的多線程持久性B+樹數據結構設計與實現方法，其特征在于，在每次分配和釋放一個鏈表節點之前，每次從系統主存分配器中分配一塊非易失主存空間，并且將所述非易失主存空間的地址和長度持久化到一個持久性鏈表中，并將分配到的所述主存空間分割成預設大小的主存塊，并通過一個易失性的空閑主存塊鏈表維護，以用于鏈層的主存分配和釋放操作，且在系統恢復時，恢復線程掃描持久性鏈表上的元數據信息和鏈層的節點，判斷出正在使用的和沒有被使用的主存塊，從而重建易失性的空閑主存塊鏈表。