[發明專利]一種哈希樹緩存方法及裝置

在審

• 申請號: 202011190181.0
• 申請日: 2020-10-30
• 公開（公告）號: CN112286873A
• 公開（公告）日: 2021-01-29
• 發明（設計）人: 于超
• 申請（專利權）人: 西安奧卡云數據科技有限公司
• 主分類號: G06F16/13
• 分類號: G06F16/13;G06F16/172;G06F16/17;G06F16/182
• 代理公司: 西安維賽恩專利代理事務所(普通合伙) 61257
• 代理人: 李明全

本發明公開了一種哈希樹緩存方法及裝置，根據寫入數據的邏輯位置確定其在哈希樹中的位置信息，將寫入數據的哈希簽名和位置信息存儲在第一前置緩沖區；當第一前置緩沖區寫滿后，將其作為當前備用前置緩存區，并將其內部數據更新至哈希樹；當哈希樹的空間大小達到閾值時，將哈希樹持久化至磁盤；在本發明中由于引入了第一前置緩沖區、第二前置緩沖區，使得讀寫數據對應了前置緩沖區，有效地隔離了上述兩種互逆的哈希樹操作，改進了哈希樹操作的復雜度，可以實現用戶讀寫任務與哈希樹持久化并發執行，有效的提升了分布式存儲系統的確定寫性能。

技術領域

本發明屬于計算機存儲技術領域，尤其涉及一種哈希樹緩存方法及裝置。

背景技術

分布式存儲空間管理的基本方法是通過多種映射，將用戶可見的邏輯卷設備映射到分布在各個節點磁盤上的底層數據塊。而為了維護這種映射關系，系統需要對大量的元數據進行管理。

在所有的映射關系中，邏輯卷設備通常采用樹的方式實現從連續的虛擬地址空間映射到不連續的物理存儲空間。已有的存儲解決方案采用了基于哈希簽名的方式構造空間樹，一般稱之為哈希樹。根據內容生成哈希簽名，使用哈希簽名構造邏輯卷的空間樹。這種方案的優點是可以直接對數據進行校驗，使用樹節點上的哈希簽名與當前數據的哈希簽名比較，可以判斷數據真實性。

但是，基于哈希簽名的空間樹也存在缺點。當數據發生變化，樹節點上的哈希簽名必須跟著更新才能反映最新的數據。例如，邏輯卷設備發生了用戶寫任務，在指定位置的數據發生了改變，此時需要按照自頂向下的方式從磁盤讀入哈希樹上相應的分支上所有樹節點到葉子節點，更新底層葉子節點中的哈希簽名以映射新的數據。為了減少磁盤讀寫頻率，樹節點讀入系統內存后會駐留一段時間。但是如果邏輯卷設備的空間很大，按照目前4K數據塊構造哈希樹，哈希樹會占用大量的系統內存，如一個1TB的邏輯卷設備需要占用5GB內存。

因此，為了防止哈希樹占用大量內存，同時盡量減少磁盤讀寫，設計上一般會根據當前所占系統內存的大小采取自底向上的方式將樹節點持久化到磁盤。從哈希樹支持用戶寫任務與自身持久化的方式來看，前者需要自頂向下的方式修改哈希樹，把樹節點從磁盤讀入內存；后者需要自底向上的方式把樹節點持久化到磁盤上。這兩種互逆的操作，要求在同一時段只能執行一種操作，這樣大大影響了分布式存儲的寫性能。

發明內容

本發明的目的是提供一種哈希樹緩存方法及裝置，以提升分布式存儲系統的寫性能。

本發明采用以下技術方案：一種哈希樹緩存方法，包括以下步驟：

根據寫入數據的邏輯位置確定其在哈希樹中的位置信息，其中，位置信息包括葉子節點及偏移量；

將寫入數據的哈希簽名和位置信息存儲在第一前置緩沖區；第一前置緩沖區為當前活動前置緩存區；

當第一前置緩沖區寫滿后，將其作為當前備用前置緩存區，并將其內部數據更新至哈希樹；同時，將第二前置緩沖區作為當前活動前置緩存區；

當哈希樹的空間大小達到閾值時，將哈希樹持久化至磁盤。

進一步地，哈希樹包括多個葉子節點、多個樹節點及一個根節點；

其中，每個葉子節點中均存儲有多個哈希簽名；根節點和每個樹節點中均存儲有多個節點哈希簽名；其中，節點哈希簽名根據根節點/樹節點的子節點數據生成。

進一步地，將哈希樹持久化至磁盤包括以下步驟：

將哈希樹中每個葉子節點的所有哈希簽名均復制到磁盤中；

根據每個葉子節點的存儲內容生成節點哈希簽名，并更新至葉子節點對應的上一層的樹節點中；

根據下一層的樹節點的存儲內容生成節點哈希簽名，并更新至當前層的樹節點中，直至當前層樹節點為根節點；