減少存儲介質中的數據冗餘的方法
2023-12-01 10:32:16 1
專利名稱：減少存儲介質中的數據冗餘的方法
技術領域：
本發明涉及數據存儲技術，尤其涉及一種在塊存儲介質的數據存儲中減少數據冗餘的方法。
背景技術：
隨著信息技術的發展，數據信息正以爆炸式的速度增長，人們對數據存儲容量的需求也越來越多，而這種爆炸式的需求增長，同時也帶來了大量的數據冗餘，這既是對存儲介質的浪費，也不利於在網絡應用中滿足存儲的需求，因此，需要提出新的技術方案來減少大量數據存儲所產生的大量的數據冗餘。然而，目前為止，尚未發現有可顯著減少數據冗餘的實用方案。
發明內容
鑑於現有的數據存儲技術的上述缺陷，本發明的目的是解決現有技術的存儲介質中存在過多的數據冗餘的問題。
為實現上述目的，本發明提供了一種減少存儲介質中的數據冗餘的方法，包括將所述存儲介質的數據存儲空間劃分為訪問區和公共存儲區，所述公共存儲區用於儲存實際塊數據，所述訪問區包括線性地址表；和利用所述線性地址表作為對所述公共存儲區的數據地址索引，對所述公共存儲區中的實際塊數據進行數據處理。
優選地，所述線性地址表由指針構成，所述指針所指地址為所述公共存儲區中存儲的實際數據的存儲地址，並且多個所述指針可以指向同一數據的地址。
優選地，所述實際數據以元數據的形式存儲在所述公共存儲區中，所述元數據包括基本塊和基本塊鍵值，所述基本塊鍵值為所述基本塊的索引，並根據所述基本塊確定，例如，可利用哈希算法從所述基本塊中計算出來。
另外，所述訪問區還可包括磁碟基本數據區。
利用本發明的方法，可以避免相同數據塊的重複存儲，減少存儲介質的浪費。
圖1是本發明一個實施例的訪問區的示意圖；圖2是本發明一個實施例的公用存儲區的示意圖；
圖3是本發明的數據模型及操作示意圖。
具體實施例方式
下面結合附圖詳細介紹本發明，附圖僅用於說明，不是對本發明專利範圍的限制。
針對現有的大多數塊存儲介質，本發明提供了一種減少數據冗餘的方法。塊存儲介質主要是以塊為單位對存儲介質進行訪問，並且按照線性的方式進行尋址，例如一個塊大小為512k，則地址為1的塊實際上代表存儲介質0～524288位元組的數據，而地址為2則代表524289～1048577位元組的數據，以此類推...。本發明的方法將原來整個的線性的塊數據存儲空間構建成訪問區和公共存儲區兩部分。其中訪問區包括所存儲的實際數據的一個線性地址表。該線性地址表由元數據指針構成，元數據指針所指地址為在公共存儲區中存儲的某個塊數據的地址，可以由多個指針指向公共存儲區中的同一個塊數據，這樣可以避免相同數據塊的重複存儲。
可以認為，塊數據的冗餘量與塊數據的大小成反比。不同的文件系統，甚至同樣的文件系統所產生的塊大小都會不同，因此需要將實際文件系統所處理的塊大小與本發明中的所進行冗餘操作的塊大小區分開，在本發明中，進行冗餘操作的最小塊數據為基本塊，其它所有塊數據的大小都應該是它的整數倍。
為便於以下對本發明具體實施方案的說明，首先定義下面的術語1.基本塊大小(BBS)指對塊數據進行操作的最小單位2.基本塊(BBL)指本方法中進行最小操作的數據實體3.元數據指針(MDP，即基本塊指針)元數據在公共存儲區內的偏移量4.存儲介質容量(SMC)物理存儲介質的真實容量；5.操作塊大小(SBS)外界對存儲介質進行操作時的塊數據的大小6.基本塊鍵值(BBK)該值由基本塊數據通過哈希算法獲得，作為基本塊數據索引。當然，也可採用其它適合的算法來獲得基本塊數據7.基本塊鍵值大小(BBKS)該鍵值的取值將影響到對基本塊數據索引的效率8.元數據(MD)
由基本塊和基本塊鍵值組成的數據單元9.顯示存儲容量(DSC)指由計算機讀取並顯示給用戶的介質的存儲容量如圖1所示，在本發明的一個實施方案中，訪問區由磁碟基本信息及線性地址表所組成。其中磁碟基本信息部分主要用來記錄磁碟的一些基本信息，這些信息包括磁碟容量、基本塊數據大小、廠家信息以及保留字等。線性地址表由一系列元數據指針所組成，每一個元數據指針都指向公共存儲區的一個基本塊數據，一個或者多個基本塊組成一個操作塊。多個這樣的地址組成了線性地址表。
如圖2所示，在本發明中，公用存儲區用來存放基本塊數據，公共存儲區是一個以基本塊為單位進行訪問的線性的地址空間，其最小單元(元數據)由一個基本塊和一個基本塊鍵值組成。基本塊鍵值由基本塊數據通過適當的哈希算法獲得，並作為基本塊數據的索引值。當寫入的時候，需要將需寫入的數據塊依據哈希算法計算出哈希值，並與已經存在的基本塊的鍵值(哈希值)進行比較，從而確定是否已經存在相同的數據塊，通過該值，可以很快地索引到某一個基本塊數據，這對於某個基本塊數據的寫入十分重要。
在本發明中，採用哈希算法從基本塊數據得到基本塊鍵值，通過該算法構建一個哈希表。由於具體實現的算法可以有很多種，本方法並不規定具體的實現，而只是就實現公共存儲區的構建和操作對該算法的要求提出約束條件1.該算法必須能真實反映基本塊數據的均勻分布。假如一個數據塊大小是8位，則每一位都有可能是0，也有可能是1，這意味著由8位0或1組成的數可能是0～255中的任何一個。對於這個範圍的數而言，都一定是會出現的，算法必須能真實地反應這種出現的可能。即使通過基本塊鍵值不能一次就決斷出塊數據，也必須能在一個有限的最小次數內決斷出塊數據。
2.通過該算法，基本塊鍵值的大小能夠反映出基本塊的內容，也就是說，基本塊數據的內容遞增或遞減(以前面一個8位數據塊為例，當該數據塊以0～255的方向遞增時，通過算法獲得的基本塊鍵值也應該是遞增的，反之亦然。)所得出的基本塊鍵值也會相應遞增或遞減，它們是線性正比關係。
3.通過該算法，必須能得到恰當的基本塊鍵值大小、元數據指針大小、以及基本塊大小。實際上，針對具體存儲介質，在實際存儲介質大小已經確定的情況下，選取最小的元數據指針大小(即該指針是一個32位的指針或者16位的，甚至8位的)，並且在考慮到性能的情況下，選取最恰當的基本塊鍵值大小和基本塊大小都是非常重要的。好的哈希算法可以在保持恰當的最大決斷次數的情況下計算出更小的鍵值。
m-元數據指針數目；x-塊冗餘數
A)考慮到沒有任何一個冗餘存在的情況，冗餘數為0實際存儲容量＝m*(MDP的大小+BBKS+BBS)顯示已存儲容量＝m*BBSB)考慮到所有塊都冗餘的情況，冗餘數為m-1實際存儲容量＝m*MDP的大小+BBKS+BBS顯示已存儲容量＝m*BBSC)考慮到中間狀況，有部分塊冗餘，冗餘數為x實際存儲容量＝m*MDP的大小+(m-x)(BBKS+BBS)顯示已存儲容量＝m*BBS那麼此時剩餘容量＝(SMC-(m*MDP的大小+(m-x)(BBKS+BBS)))/(MDP的大小+BBKS+BBS)*BBS＝(SMC+x*(BBKS+BBS)/(MDP的大小+BBKS+BBS)-m)*BBS可以很直觀地了解到，元數據的尺寸越大，則m與MDP的值越小，它們成反比關係MDP的大小＝f1(1/MD的大小)；m＝f2(1/MD的大小)式中，f1和f2分別表示MDP的大小與MD的大小的函數關係。在基於前兩個原則的情況下，元數據的大小越大，必然會導致BBKS增大，而BBS過小，針對一個比較大的實際的存儲設備，為了能夠尋址則會產生一個比較大MDP，從而導致實際上存儲空間利用率的下降；而針對確定的BBS，過小的BBKS則造成決斷次數的增加(為了獲得更小的BBKS而形成的哈希算法計算出的更小的BBK將會導致一個BBK面對更多的BBL)，從而造成性能上的下降。因此需要平衡這幾者之間的關係，以保證x*BBS-((m-x)*BBKS+m*MDP)的值最大化。這也是本發明的目的所在。其中，x*BBS是所節約下來的空間，((m-x)*BBKS+m*MDP)是為了節約空間所造成的必然的開銷。
圖3是本發明的數據模型及操作示意圖，如圖3所示，本發明的方法涉及以下的塊數據操作1.讀取讀取塊數據是最簡單的，當需要讀取一個操作塊的時候，這個操作塊是由一個或者多個元數據指針所指的元數據所組成，通過讀出這些元數據並合併，合併只是按照該基本塊地址指針在訪問區中的順序將其所指的基本塊數據進行簡單的合併即可，就可以得出所需要的數據了。
2.寫入寫入塊數據則相對複雜一些，首先將要寫入的操作塊拆分成若干個基本塊，並計算每一個基本塊的鍵值，通過該鍵值在公共存儲區中進行決斷，當無法決斷出該基本塊時，即認為該基本塊為新的數據，將其與鍵值作為元數據寫入公共存儲區，並將元數據指針保存到訪問區的線性地址表中。如果該基本塊被決斷，則只是簡單地將元數據指針保存到訪問區即可。
3.刪除刪除也比較簡單，將相應的元數據指針與基本塊鍵值置為0即可。
以上所述僅為本發明的優選實施方案，不是對本發明專利範圍的限制，凡利用本發明的說明書及附圖內容所作的等效結構變換，都包括在本發明的專利範圍內。
權利要求
1.一種用於減少存儲介質中數據冗餘的方法，其特徵在於，所述方法包括將所述存儲介質的數據存儲空間劃分為訪問區和公共存儲區，所述公共存儲區用於儲存實際塊數據，所述訪問區包括線性地址表；和利用所述線性地址表作為對所述公共存儲區的數據地址索引，對所述公共存儲區中的實際塊數據進行數據處理。
2.根據權利要求1所述的方法，其特徵在於，所述線性地址表由指針構成，所述指針所指地址為所述公共存儲區中存儲的實際數據的存儲地址。
3.根據權利要求2所述的方法，其特徵在於，有多個所述指針指向同一數據的地址。
4.根據權利要求2所述的方法，其特徵在於，所述實際數據以元數據的形式存儲在所述公共存儲區中，所述元數據包括基本數據塊和基本塊鍵值，所述基本塊鍵值為所述基本塊的索引。
5.根據權利要求4所述的方法，其特徵在於，所述基本塊鍵值是根據所述基本塊計算出來的。
6.根據權利要求5所述的方法，其特徵在於，所述基本塊鍵值是利用哈希算法從所述基本塊中計算出來的。
7.根據權利要求3所述的方法，其特徵在於，所述實際數據以元數據的形式存儲在所述公共存儲區中，所述元數據包括基本數據塊和基本塊鍵值，所述基本塊鍵值為所述基本塊的索引。
8.根據權利要求7所述的方法，其特徵在於，所述基本塊鍵值是根據所述基本塊計算出來的。
9.根據權利要求1到8任一項所述的方法，其特徵在於，所述數據處理包括對所述存儲介質的數據進行讀取、寫入和刪除。
10.根據權利要求9所述的方法，其特徵在於，所述訪問區進一步包括磁碟基本數據區。
全文摘要
本發明公開了一種減少塊存儲介質中數據冗餘的方法，用以解決存儲介質中數據冗餘過多的問題，該方法將所述塊存儲介質的塊數據存儲空間劃分為訪問區和公共存儲區兩部分，實際塊數據存儲在所述公共存儲區中，所述訪問區包括一個線性地址表，所述線性地址表由指針構成，所述指針所指地址為所述公共存儲區中存儲的某個實際數據的存儲地址，多個所述指針可以指向同一數據的地址。利用該方法可避免相同數據塊的重複存儲，產生良好的經濟效益。
文檔編號G06F12/02GK1716215SQ20041006264
公開日2006年1月4日 申請日期2004年6月30日 優先權日2004年6月30日
發明者塗維山 申請人:深圳市朗科科技有限公司