[發明專利]同時適應磁盤與固態硬盤讀寫特性的海量數據存儲方法

有效

• 申請號: 201611255923.7
• 申請日: 2016-12-30
• 公開（公告）號: CN106708442B
• 公開（公告）日: 2020-02-14
• 發明（設計）人: 龔才鑫;龔奕利
• 申請（專利權）人: 硬石科技(武漢)有限公司
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 42222 武漢科皓知識產權代理事務所(特殊普通合伙)
• 代理人: 嚴彥

一種同時適應磁盤與固態硬盤讀寫特性的海量數據存儲方法，將一個塊中的記錄的完全排序改為部分部序，在每個塊的尾部加上布隆過濾器，包括建立稱為Log?Structured Append?Tree樹，樹中每個塊存儲的數據量達到閾值時，將塊內的數據直接追加到相應孩子塊內時，孩子塊的數據由若干個排序序列組成，而不是通過歸并排序的方式實現塊內完全排序；樹中每一個塊保存著布隆過濾器。依照本發明，在不犧牲任何其他性能的情況下，使得寫放大大大降低，大大增加了隨機寫效率，而且，對固態硬盤壽命起到了更好的保護和延長。在讀寫混合的場景中，隨機讀性能也有所增強，具有重要的市場價值。

技術領域

本發明屬于海量數據存儲領域，特別涉及存儲樹，該方法可同時適應磁盤與固態硬盤讀寫特性。

背景技術

現有的硬盤上常用的索引樹有B-tree、LSM-tree、buffer-tree等。其中B-tree是傳統的經典樹，但因為其在隨機寫的場景中不可避免的隨機寫磁盤，當存儲海量數據時性能較低，所以存儲海量數據時常常使用其變體，如BigTable中對B-tree的變體和LSM-tree的結合使用。對于海量數據的存儲，常使用LSM-tree或buffer-tree(又稱為fractal-tree)作為索引樹,這兩者的共同特點是將待寫入的記錄推遲寫，待積累到一定量時再批量處理。這樣可以較好的解決B-tree的隨機寫場景中引起的隨機寫磁盤的問題，使得寫吞吐量得到了較大的提升。

在隨機讀的場景中，因為LSM-tree和buffer-tree的層數較多且樹中的塊大小比B-tree的中的塊大小大很多，所以讀放大較大使得隨機讀性能有明顯降低。為了解決這個問題，bigtable/leveldb等項目在實現LSM-tree時，在每個節點保存了布隆過濾器信息，這樣可以很好的降低LSM-tree的讀放大，較好的解決隨機讀性能低的問題。

但不管是B-tree還是LSM-tree/buffer-tree，這些樹的寫放大都較大。由于磁盤吞吐量的限制，較大的寫放大限制了這些索引樹隨機寫性能的進一步實質性的提升，而且嚴重損害固態硬盤的壽命。較大的寫放大侵占了大部分的磁盤的吞吐量進而使得在讀寫混合的場景中，隨機寫影響隨機讀對磁盤性能的利用而使得隨機讀性能也會有一定程度的下降。

發明內容

本發明所要解決的問題是:傳統樹的較大的寫放大使得隨機寫效率低下的問題，在固態硬盤盤中較大的寫放大也嚴重的影響著固態硬盤的壽命。較大的寫放大侵占了大部分的機械磁盤或固態硬盤的吞吐量進而使得在讀寫混合的場景中，隨機寫影響隨機讀對機械磁盤或固態硬盤性能的利用而使得隨機讀性能也會有一定程度的下降。由此設計了稱為Log-Structured Append-Tree(日志結構的追加樹，簡稱LSA-tree)的樹。

本發明提供一種同時適應磁盤與固態硬盤讀寫特性的海量數據存儲方法，將一個塊中的記錄的完全排序改為部分部序，再在每個塊的尾部加上布隆過濾器，實現方式如下，內存中包括可變內存緩存、不可變內存緩存和樹的元數據信息，磁盤中的數據采用LSA-tree結構組織，設該樹分為n層，第i層中至少tⁱ個塊最多tⁱ+1個塊，1≤i≤n-1，參數t為相鄰兩層塊數閾值的倍數，最后一層小于等于tⁿ個塊；每個塊有一個鍵的范圍，當每個塊存儲的數據量達到相應閾值時，將塊內的數據刷入下一層中在范圍上有覆蓋重疊關系的塊中，將要刷的數據直接追加到相應的塊內時，某一塊的數據由若干個排序序列組成，而不是通過歸并排序的方式實現塊內完全排序；樹中每一個塊保存著布隆過濾器；

而且，后臺線程對LSA-tree樹中的塊的操作分為三類，包括下刷、分裂和合并；所有操作都只對非最后一層的塊發起處理；將當前層的某一塊與下層的一個或多個塊在鍵上的覆蓋重疊關系稱為父子關系，當前層的該塊稱為父親塊，下一層的一個或多個塊稱為孩子塊；

下刷操作是將塊內的數據下移至下一層中，但該塊的范圍仍保留，該塊所在層的塊的數目不發生變化；