[發明專利]基于Cuckoo哈希的文件系統目錄管理方法及系統

有效

• 申請號: 202110356654.8
• 申請日: 2021-04-01
• 公開（公告）號: CN113094336B
• 公開（公告）日: 2022-11-01
• 發明（設計）人: 陳志廣;鄭先淇;盧宇彤;胡澤杰;羅嘉文
• 申請（專利權）人: 中山大學
• 主分類號: G06F16/13
• 分類號: G06F16/13
• 代理公司: 湖南兆弘專利事務所(普通合伙) 43008
• 代理人: 譚武藝

本發明公開了一種基于Cuckoo哈希的文件系統目錄管理方法及系統，本發明包括對目錄中作為目標文件的子目錄或子文件讀取元數據的步驟：接收針對目標文件的讀請求，迭代采用Cuckoo哈希的第i個哈希函數對目標文件的名稱filename進行哈希計算，根據哈希計算結果確定目錄的哈希表對應的第i個備選數據塊；若第i個備選數據塊存在目標文件的名稱filename則讀出目標文件的元數據并返回，結束；否則繼續迭代，直至迭代結束返回不存在目標文件的消息。本發明在文件訪問的關鍵路徑上延遲小，能夠實現并發讀操作，能夠顯著加速應用程序針對大目錄的數據訪問。

技術領域

本發明涉及計算機信息存儲技術，具體涉及一種基于Cuckoo哈希的文件系統目錄管理方法及系統。

背景技術

文件系統是一種常用的數據組織方法，目前各行業的大部分數據均保存在各類文件系統中。隨著數據量的不斷增長，文件系統的規模越來越大，單個目錄內包含的子文件或子目錄越來越多，在一個大目錄中查找特定的文件會引入很大的延遲。大目錄問題已成為設計高性能文件系統面臨的重要挑戰。當前的文件系統均采用復雜的數據結構為每個目錄下的所有子目錄或子文件建立一個索引，以便在文件訪問時能夠通過索引結構找到對應的文件。例如，著名的EXT類文件系統采用HTree結構為每個目錄下的子目錄和子文件建立索引。如圖1所示，HTree是一個兩級的樹形結構，第一級是根節點，第二級為葉子節點。每個節點內部保存大量的條目(Entry)，且這些條目之間是有序的，葉子節點中的每個條目對應一個子目錄或子文件。一個子目錄或子文件要插入到HTree中時，先采用一個哈希函數根據文件名計算出對應的哈希值。因為節點中的各個條目按照哈希值排序，可采用二分法查找根節點中的各個條目，從而導向到正確的葉子節點。葉子節點中的條目也是按照哈希值排序的，將待插入文件對應的條目插入到葉子節點中正確的位置即可。類似地，BtrFS采用B+樹為每個目錄建立一個索引。不同于EXT類文件系統，BtrFS并沒有限制B+樹的深度，因此相比于只有兩級的HTree表現出更好的可擴展性。IndexFS采用GIGA+建立索引，GIGA+本質上也是一種樹形結構，但具有更好的分裂性能。

EXT、BtrFS、IndexFS等文件系統采用層次式的樹形結構為每個目錄內的子目錄和子文件建立索引。當應用程序訪問一個大目錄中的某個文件時，不可避免的要經歷很長的訪問延遲。主要原因在于：在樹形結構中檢索一個目標對象需要從根節點一直查找到葉子節點，即找到一條從根節點通往葉子節點的路徑，此過程無法并發操作，只能從根節點開始逐層分析、確定下一層的走向、最終達到葉子節點，每解析一層都涉及大量的數據讀寫和計算，從而引入很大的延遲。以EXT文件系統采用的HTree為例，在HTree中檢索一個文件需要先從存儲設備中讀出根節點并實施二分查找，確定目標葉子節點后將該節點從存儲設備上讀出，并再次實施二分查找，以上過程涉及兩次不可并發讀操作。類似地，BtrFS在B+樹中查找一個文件時需要從B+樹的根節點逐層檢索到葉子節點，在每一次都需要至少一次讀操作和相應的計算分析，且各層之間的操作是不能并發的。隨著單個目錄內的子文件和子目錄總數越來越多，B+樹的深度不斷增大，在B+樹中檢索文件的延遲也會相應地增長。總之，采用樹形結構為大目錄建立索引會在文件訪問的關鍵路徑上引入很大的延遲。

發明內容

本發明要解決的技術問題：考慮到當前文件系統采用樹形結構為大目錄建立索引，樹形結構不利于并發處理，這是文件訪問延遲的關鍵所在，本發明提供一種基于Cuckoo哈希的文件系統目錄管理方法及系統，本發明采用哈希表為每個目錄中的子目錄和子文件建立索引，哈希表是一種平面化的數據結構，適合于并發處理，在文件訪問的關鍵路徑上延遲小，能夠實現并發操作，能夠顯著加速應用程序針對大目錄的數據訪問。

為了解決上述技術問題，本發明采用的技術方案為：

一種基于Cuckoo哈希的文件系統目錄管理方法，包括對目錄中作為目標文件的子目錄或子文件讀取元數據的步驟：

1)接收對目錄中目標文件的讀請求；

2)針對目標文件讀取Cuckoo哈希的num個哈希函數對應的備選數據塊；