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

有效

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

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

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

2)針對目標文件讀取Cuckoo哈希的num個哈希函數對應的備選數據塊， 包括：根據Cuckoo哈希的第1個哈希函數對目標文件的名稱filename進行哈希計算的哈希計算結果確定目錄的哈希表對應的第1個備選數據塊，以第1個備選數據塊為起始地址，一次性連續讀取N個備選數據塊，使得N個備選數據塊中包含Cuckoo哈希的所有num個哈希函數對應的備選數據塊，其中N為一次性連續讀備選數據塊的數量；

3)初始化循環變量i的值為1；

4)針對目標文件，根據Cuckoo哈希的第i個哈希函數對目標文件的名稱filename進行哈希計算的哈希計算結果，確定目錄的哈希表對應的第i個備選數據塊中的目標位置，并判斷目標位置是否存在匹配的哈希計算結果，若存在則直接從目標位置讀出目標文件的元數據并返回，結束；否則，將循環變量i的值加1，若循環變量i的值超過哈希函數總數量num，則跳轉執行下一步，否則跳轉執行步驟4)；

5)返回不存在目標文件的消息，結束；

所述Cuckoo哈希的num個哈希函數中，第1個哈希函數的計算函數表達式為h(x)＝hash(x)，其中hash為預設的哈希值計算函數，x為目標文件的名稱filename；后續任意第i個哈希函數的計算函數表達式為：

h_i(x)＝h_i-1(x)+neatest_prime(h(x)％N)

上式中，h_i(x)表示第i個哈希函數的哈希計算結果，h_i-1(x)表示第i-1個哈希函數的哈希計算結果，neatest_prime(h(x)％N)表示計算比h(x)％N小的最大素數，h(x)為第1個哈希函數的計算結果，％為模運算，N為一次性連續讀備選數據塊的數量。

2.根據權利要求1所述的基于Cuckoo哈希的文件系統目錄管理方法，其特征在于，還包括往目錄中創建作為目標文件的子目錄或子文件的步驟：

S1)接收對目標文件的創建請求；

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

S3)初始化循環變量i的值為1；

S4)針對目標文件，根據Cuckoo哈希的第i個哈希函數對目標文件的名稱filename進行哈希計算的哈希計算結果，確定目錄的哈希表對應的第i個備選數據塊中的目標位置，若目標位置為空閑位置，則將目標文件的元數據信息以及哈希計算結果寫入該空閑位置，結束；否則，將循環變量i的值加1，若循環變量i的值超過哈希函數總數量num，則跳轉執行步驟S5)，否則跳轉執行步驟S4)；

S5)觸發遷移操作將第i-1個備選數據塊中對應的哈希表位置的遷移文件的元數據遷移出來形成空閑位置，并將目標文件的元數據信息以及哈希計算結果寫入該空閑位置。

3.根據權利要求2所述的基于Cuckoo哈希的文件系統目錄管理方法，其特征在于，步驟S5)中將第i個備選數據塊中對應的哈希表位置的遷移文件的元數據遷移出來的步驟包括：

S5.1)針對遷移文件，判斷針對目標文件讀取Cuckoo哈希的num個哈希函數對應的備選數據塊是否已經包含遷移文件與Cuckoo哈希的num個哈希函數對應的全部備選數據塊，如果尚未包含全部備選數據塊，則將未包含的備選數據塊讀出；

S5.2)初始化循環變量j的值為2；

S5.3)根據Cuckoo哈希的第j個哈希函數對目標文件的名稱filename進行哈希計算的哈希計算結果，確定目錄的哈希表對應的第j個備選數據塊中的目標位置，若目標位置為空閑位置，則將遷移文件的元數據信息以及哈希計算結果寫入該空閑位置，結束；否則，將循環變量j的值加1，若循環變量j的值超過哈希函數總數量num，則跳轉執行下一步，否則跳轉執行步驟S5.3)；

S5.4)觸發遷移操作將第j-1個備選數據塊中對應的哈希表位置的遷移文件的元數據遷移出來形成空閑位置，并將遷移文件的哈希計算結果寫入該空閑位置；然后將第j-1個備選數據塊中對應的哈希表位置遷移出來的文件作為新的遷移文件，跳轉執行步驟S5.1)。