元數據查詢方法和裝置的製作方法
2023-05-01 12:00:11
專利名稱：元數據查詢方法和裝置的製作方法
技術領域：
本發明涉及存儲技術，尤其涉及一種元數據查詢方法和裝置。
背景技術：
重複數據刪除也稱為智能壓縮或單一實例存儲，是一種可自動查找重複數據，將相同數據只保留一個副本，並使用指向單一副本的指針替換掉其他重複副本，以達到消除冗餘數據、降低存儲容量需求的存儲技術。現有重複數據刪除技術的元數據查詢方案中包括如下模塊元數據緩存(Metadata Cache)、布隆過濾器(Bloom Filter)、全索引表(Full Index Table)、容器(Container),其中，Metadata Cache用於緩存元數據；Bloom Filter用於過濾掉大部分的新數據塊，減少磁碟訪問次數；Full Index Table用於索引元數據在磁碟中的存儲位置；Container用於存放刪除重複數據後的數據塊和元數據。 現有的元數據查詢流程如下對於一個要查詢的元數據(Metadata)，首先在元數據緩存中查找，如果在緩存中找到相同的元數據，則該元數據對應的分塊是重複塊。如果在緩存中沒有找到，再到布隆過濾器中查找，如果沒有在布隆過濾器中找到，則對應的分塊一定是新塊。如果元數據在布隆過濾器中，就到索引表中查找對應的容器，如果能在索引表中找到，則對應的分塊是重複塊，並把對應的容器的元數據全部加載到緩存中。但是，現有技術中的索引表是全索引包含了所有分塊元數據的索引。由於這種索引表佔用的空間太大，存放在磁碟上就導致很多的磁碟IO操作，降低了查詢的性能。
發明內容
本發明實施例提供一種元數據查詢方法和裝置，用於提高查詢性能，降低佔用的內存空間。本發明實施例提供了一種元數據查詢方法，包括在要查找的元數據中抽樣出至少一個第一元數據；將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引是所述容器標識對應容器中存儲的元數據的至少部分特徵值；根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器；將所述選擇的容器中的元數據加載到元數據緩存中；從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。本發明實施例提供了一種元數據查詢裝置，包括抽樣模塊，用於在要查找的元數據中抽樣出至少一個第一元數據；確定模塊，用於將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引是所述容器標識對應容器中存儲的元數據的至少部分特徵值；選擇模塊，用於根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器；加載模塊，用於將所述選擇的容器中的元數據加載到元數據緩存中；查找模塊，用於從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。由上述技術方案可知，本發明實施例通過採用稀疏索引表且該稀疏索引表設置在內存中，可以避免磁碟IO操作，提高查詢性能；通過不設置布隆過濾，可以降低佔用的內存空間。
圖I為本發明元數據查詢方法一實施例的流程示意圖；圖2為本發明元數據查詢方法對應的結構示意圖；圖3為本發明中稀疏索引表的結構不意圖；圖4為本發明元數據查詢裝置一實施例的結構示意圖；圖5為本發明元數據查詢裝置另一實施例的結構示意圖。
具體實施例方式圖I為本發明元數據查詢方法一實施例的流程示意圖，包括步驟11 :在要查找的元數據中抽樣出至少一個第一元數據。例如，參見圖2，圖2所示的要查找的元數據為6個，可以從中抽樣出第2個和第5個，將第2個和第5個作為第一元數據。具體的抽樣方式可以是首先，將要查找的元數據分組，例如，將要查找的元數據依次選取相同數目的元數據作為一組；之後，在每個組中抽樣一個元數據，例如，在每個組中選擇一個哈希值最小的元數據作為抽樣的元數據。步驟12 :將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引為所述容器標識對應容器中存儲的元數據的至少部分特徵值。稀疏索引表用於表明元數據與容器的對應關係，例如，該稀疏索引表可以表明元數據的特徵值與容器標識(ID)的對應關係，或者表明元數據的部分的特徵值與容器ID的對應關係。本發明實施例以特徵值為哈希值，稀疏索引表表明元數據的部分的特徵值與容器標識的對應關係為例。稀疏索引表可以在寫入新數據塊時建立，例如，當抽樣一個元數據後，按照元數據部分的哈希值作為索引，在稀疏索引表中沒有找到可以對應的容器ID，那麼可以將該元數據寫入容器內，並在稀疏索引表中記錄該元數據寫入的容器的容器ID，並且該容器ID在稀疏索引表中位置的索引為該元數據的部分的哈希值。步驟13 :根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器。
根據同一個容器ID被查到的次數，選擇滿足設定條件的容器標識對應的容器可以包括對查找到的容器標識，按照同一容器標識被查詢到的次數從高到低的順序選擇設定個數的容器ID對應的容器，作為滿足設定條件的容器。例如，如果抽樣後的元數據中的6個均對應容器IDl，抽樣後的元數據中的5個均對應容器ID2，抽樣後的元數據中的4個均對應容器ID3，則同一個容器ID被查詢到的次數從高到低的順序是容器ID1、容器ID2和容器ID3。如果設定條件是選擇排序較高的2個，則選擇的容器就是容器IDl對應的容器I和容器ID2對應的容器2。對查找到的容器標識，選擇滿足設定條件的容器標識對應的容器的具體策略，可以根據不同情況來設定，例如，可以設定一個閾值，被查找到的次數大於等於該閾值的容器標識對應的容器，作為滿足設定條件的容器。本實施例按照被查詢到的次數從高到低的順序來選擇，僅僅是其中的一種方式。每個容器標識在所述索引表中位置的索引為所述容器標識對應容器中存儲的元數據的至少部分的特徵值；例如，稀疏索引表的第一個表項中記錄的是元數據的部分的哈希值為I對應的容器ID，第二個表項中記錄的是元數據的部分的哈希值為2對應的容器ID，其餘類推。
此時，稀疏索引表的大小為(磁碟容量/分塊大小)X抽樣率X 2，其中乘以2是為了減少哈希碰撞，提高索引的準確性。稀疏索引表所佔的內存空間=索引表的大小X8(以每個容器ID佔用64bit為例)字節。以磁碟容量為1PB，分塊大小為8KB，抽樣率為1/128為例，稀疏索引表佔用的內存空間為16GB。所述每個容器標識在所述索引表中的位置的索引可以通過以下方法獲得從容器中存儲的元數據中抽樣出至少一個第二元數據，將第二元數據中的特徵值，作為容器對應的容器標識在所述稀疏索引表中的位置的索引；或者，將第二元數據的部分特徵值作為容器對應的容器標識在所述稀疏索引表中位置的索引，其中，每個第二元數據的特徵值確定一個位置索引。需要說明的是，本發明實施例中，需要通過元數據的特徵值來作為第一元數據的查找索引以及容器標識的位置索引，顯然，獲取第一元數據中的特徵值作為索引的算法，和獲取第二元數據中的特徵值作為容器標識在稀疏索引表中的位置索引的算法，兩者需要一致。例如，第二元數據中取出特徵值的前3位作為容器標識在稀疏索引表中的位置索引，那麼相應的，第一元數據的查找索引也是取第一元數據中特徵值的前3位；又如第二元數據中取出全部特徵值作為容器標識在稀疏索引表中的位置索引，那麼相應的，第一元數據的查找索引也是取第一元數據中全部特徵值。另外，從容器中抽樣得到至少一個第二元數據，若第二元數據有兩個以上，那麼，每個第二元數據的特徵值都可以確定一個容器標識的位置索引。例如以第二元數據中全部特徵值作為容器A在稀疏索引表中的位置索引為例，從容器A中抽出了三個第二元數據，那麼在稀疏索引表中就可以為容器A確定三個位置，位置的索引就是第二元數據的特徵值。容器ID在稀疏索引表中位置的索引也可以採用二維方式確定，該位置的索引的二維示意圖可以如圖3所示，以位置的索引為抽樣元數據的部分的哈希值為例，可以用抽樣元數據的部分的哈希值的高m位表示一級索引表的偏移量，用抽樣元數據的部分哈希值的低n位表示二級索引表的偏移量，那麼，2"為二級索引表的大小，2n+m為稀疏索引表的大小。計算n、m時，可以採用2n =系統一次能夠分配的內存空間，得到n，再根據計算得到的n和2n+m =稀疏索引表佔用的內存空間，得到m。採用二維數組的方式可以避免需要一次分配較大的內存空間而導致的內存空間分配失敗。例如稀疏索引表需要8G空間，而內存一次能分配的空間只有1G，那麼就每次分配1G，共分配SG的空間；二維數組中，假設以一級索引表的表項為行索引，以二級索引表的表項為列索引，則該二維數組的行數共為2-行，列數共為2"列，每個一級索引表的表項對應2"個二級索引表的表項。該二維數組的第i行第j列保存的容器ID與特徵值的高m位 =i-1且低n位=j-1的元數據對應，i = I,. . . 2m,, j = I,. . . 2n。進一步的，當稀疏索引表所佔的內存空間小於作業系統一次能分配的最大內存空間時，可以採用一組數組方式進行組織。步驟14 :將所述滿足設定條件的容器中的元數據加載到元數據緩存中。參見圖2，容器中包含元數據部分和數據部分，將其中的元數據加載到元數據緩存中。步驟15 :從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。將要查找的元數據與元數據緩存中的元數據進行比較，如果要查找的元數據存在於元數據緩存中，則表明該元數據對應的數據塊為重複塊，否則為新塊。之後，可以將新資料庫寫入容器中，將重複數據塊刪除等後續處理。本實施例中由於稀疏索引表只記錄容器ID，所在空間較小，可以全部放置在內存中，因此訪問稀疏索引表時不會產生任何的磁碟IO操作，提高元數據查詢性能；本實施例中沒有布隆過濾器，並且稀疏索引表所佔內存比布隆過濾器小很多，可以降低對內存的需求。圖4為本發明元數據查詢裝置一實施例的結構示意圖，包括抽樣模塊41、確定模塊42、選擇模塊43、加載模塊44和查找模塊45 ;抽樣模塊41用於在要查找的兀數據中抽樣出至少一個第一元數據；確定模塊42用於將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引是所述容器標識對應容器中存儲的元數據的至少部分特徵值；選擇模塊43用於根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器；加載模塊44用於將所述選擇的容器中的元數據加載到元數據緩存中；查找模塊45用於從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。可選的，所述選擇模塊43具體用於對查找到的容器標識，按照同一容器標識被查詢到的次數從高到低的順序選擇設定個數的容器，作為滿足設定條件的容器。可選的，所述抽樣模塊41具體用於將要查找的元數據分為多個組，在每個組中抽樣一個元數據，將每個組中特徵值最小的元數據作為抽樣的第一元數據。可選的，參見圖5，該裝置還可以包括稀疏索引表設置模塊46，用於從容器中存儲的元數據中抽樣出至少一個第二元數據，將第二元數據中的特徵值，作為容器對應的容器標識在所述稀疏索引表中的位置的索引；或者，將第二元數據的部分特徵值作為容器對應的容器標識在所述稀疏索引表中位置的索引，其中，每個第二元數據的特徵值確定一個位置索引。可選的，所述稀疏索引表設置模塊46將第二元數據中的特徵值，作為容器對應的容器標識在所述稀疏索引表中的位置的索引或者將第二元數據的部分特徵值作為容器對應的容器標識在所述稀疏索引表中位置的索引，具體包括將稀疏索引表設置為表示行索引的一級索引偏移量和表示列索引的二級索引偏移量組成的二維表；如果容器標識位置的索引為所述抽樣的第二元數據的特徵值，則根據所述第二元數據的特徵值的高位確定所述一級索引偏移量，根據所述第二元數據的特徵值的低位確定所述二級索引偏移量；或者，如果所述位置的索引為所述第二元數據的部分特徵值，則根據所述第二元數據中的部分特徵值的高位確定所述一級索引偏移量，根據所述第二元數據中的部分特徵值的低位確定所述二級索引偏移量。本實施例中由於稀疏索引表所在空間較小，可以全部放置在內存中，因此訪問稀疏索引表時不會產生任何的磁碟IO操作，提高元數據查詢性能；本實施例中沒有布隆過濾 器，並且稀疏索引表所佔內存比布隆過濾器小很多，可以降低對內存的需求。本領域普通技術人員可以理解實現上述各方法實施例的全部或部分步驟可以通過程序指令相關的硬體來完成。前述的程序可以存儲於一計算機可讀取存儲介質中。該程序在執行時，執行包括上述各方法實施例的步驟；而前述的存儲介質包括R0M、RAM、磁碟或者光碟等各種可以存儲程序代碼的介質。最後應說明的是以上各實施例僅用以說明本發明的技術方案，而非對其限制；儘管參照前述各實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分或者全部技術特徵進行等同替換；而這些修改或者替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的範圍。
權利要求
1.一種元數據查詢方法，其特徵在於，包括 在要查找的元數據中抽樣出至少一個第一元數據； 將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引是所述容器標識對應容器中存儲的元數據的至少部分特徵值； 根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器； 將所述選擇的容器中的元數據加載到元數據緩存中； 從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。
2.根據權利要求I所述的方法，其特徵在於，所述每個容器標識在所述索引表中的位 置的索引通過以下方法獲得 從容器中存儲的元數據中抽樣出至少一個第二元數據，將第二元數據中的特徵值，作為容器對應的容器標識在所述稀疏索引表中的位置的索引；或者，將第二元數據的部分特徵值作為容器對應的容器標識在所述稀疏索引表中位置的索引，其中，每個第二元數據的特徵值確定一個位置索引。
3.根據權利要求I所述的方法，其特徵在於，所述根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器，包括 對查找到的容器標識，按照同一容器標識被查詢到的次數從高到低的順序選擇設定個數的容器，作為滿足設定條件的容器。
4.根據權利要求3所述的方法，其特徵在於，所述容器標識在所述稀疏索引表中位置的索引由表示行索引的一級索引偏移量和表示列索引的二級索引偏移量確定，如果所述位置的索引為所述抽樣的第二元數據的特徵值，則根據所述第二元數據的特徵值的高位確定所述一級索引偏移量，根據所述第二元數據的特徵值的低位確定所述二級索引偏移量； 或者，如果所述位置的索引為所述第二元數據的部分特徵值，則根據所述第二元數據中的部分特徵值的高位確定所述一級索引偏移量，根據所述第二元數據中的部分特徵值的低位確定所述二級索引偏移量。
5.根據權利要求I所述的方法，其特徵在於，所述在要查找的元數據中抽樣出至少一個第一元數據,包括 將要查找的元數據分為多個組，在每個組中抽樣一個元數據，將每個組中特徵值最小的元數據作為抽樣的第一元數據。
6.一種元數據查詢裝置，其特徵在於，包括 抽樣模塊，用於在要查找的元數據中抽樣出至少一個第一元數據； 確定模塊，用於將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引是所述容器標識對應容器中存儲的元數據的至少部分特徵值； 選擇模塊，用於根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器； 加載模塊，用於將所述選擇的容器中的元數據加載到元數據緩存中； 查找模塊，用於從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。
7.根據權利要求6所述的裝置，其特徵在於，所述選擇模塊具體用於 對查找到的容器標識，按照同一容器標識被查詢到的次數從高到低的順序選擇設定個數的容器，作為滿足設定條件的容器。
8.根據權利要求6所述的裝置，其特徵在於，所述抽樣模塊具體用於 將要查找的元數據分為多個組，在每個組中抽樣一個元數據，將每個組中特徵值最小的元數據作為抽樣的第一元數據。
9.根據權利要求6-8任一項所述的裝置，其特徵在於，還包括 稀疏索引表設置模塊，用於從容器中存儲的元數據中抽樣出至少一個第二元數據，將第二元數據中的特徵值，作為容器對應的容器標識在所述稀疏索引表中的位置的索引；或者，將第二元數據的部分特徵值作為容器對應的容器標識在所述稀疏索引表中位置的索弓I，其中，每個第二元數據的特徵值確定一個位置索引。
10.根據權利要求9所述的裝置，其特徵在於，所述稀疏索引表設置模塊將第二元數據中的特徵值，作為容器對應的容器標識在所述稀疏索引表中的位置的索引或者將第二元數據的部分特徵值作為容器對應的容器標識在所述稀疏索引表中位置的索引部分，具體包括 將稀疏索引表設置為由表示行索引的一級索引偏移量和表示列索引的二級索引偏移量組成的二維表； 如果容器標識位置的索引為所述抽樣的第二元數據的特徵值，則根據所述第二元數據的特徵值的高位確定所述一級索引偏移量，根據所述第二元數據的特徵值的低位確定所述二級索引偏移量；或者，如果所述位置的索引為所述第二元數據的部分特徵值，則根據所述第二元數據中的部分特徵值的高位確定所述一級索引偏移量，根據所述第二元數據中的部分特徵值的低位確定所述二級索引偏移量。
全文摘要
本發明實施例提供一種元數據查詢方法和裝置。該方法包括在要查找的元數據中抽樣出至少一個第一元數據；將抽樣得到的每個第一元數據中的至少部分特徵值作為索引，在內存中預置的稀疏索引表中查找對應的容器標識，所述稀疏索引表中記錄容器標識，每個容器標識在所述索引表中位置的索引是所述容器標識對應容器中存儲的元數據的至少部分特徵值；根據同一個容器標識被查到的次數，選擇滿足設定條件的容器標識對應的容器；將所述選擇的容器中的元數據加載到元數據緩存中；從所述元數據緩存中查找與所述要查找的元數據相同的數據塊。本發明實施例可以提高查詢性能，降低內存佔用空間。
文檔編號G06F17/30GK102663090SQ20121010293
公開日2012年9月12日 申請日期2012年4月10日 優先權日2012年4月10日
發明者劉強, 張程偉 申請人:華為技術有限公司