[發明專利]基于兄弟組的內容可尋址存儲

有效

• 申請號: 201310032546.0
• 申請日: 2013-01-28
• 公開（公告）號: CN103226561A
• 公開（公告）日: 2013-07-31
• 發明（設計）人: 伯特蘭·塞爾勒特;羅杰·博達梅爾;埃馬努埃萊·阿爾蒂埃里
• 申請（專利權）人: 阿普賽爾有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/02
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 余剛;吳孟秋

相關申請的交叉參考；權益聲明

本申請要求于2012年1月26日提交的美國繼續臨時專利申請第13/358,742號的權益，其全部內容引用于此。申請人據此取消母申請或其審查歷史中對權利要求范圍的任何放棄，并建議本申請的權利要求可比母申請中的權利要求的范圍更寬。

技術領域

本發明涉及存儲系統，更具體地，涉及用于在系統的存儲容量增大時以不引起過度開銷和數據的移動的方式存儲片（chunk）的技術。

背景技術

用于訪問存儲的數據項的信息在本文中被稱為存儲項的“訪問關鍵字”。在典型的文件系統中，基于（a）項所存儲的位置以及（b）項的名稱或標識符來檢索存儲項。例如，如果名稱為“foo.txt”的文件位于名稱為“c:/myfiles/text”的目錄下，則應用程序（application，應用）可使用路徑名“c:/myfiles/text/foo.txt”作為訪問關鍵字來從文件系統檢索文件。因為傳統的訪問關鍵字基于被檢索的項的位置，當項被移動時訪問關鍵字改變。另外，項的每個副本具有不同的訪問關鍵字，因為每個副本被存儲在不同的位置。

與傳統的文件系統相比，內容可尋址存儲（CAS：content?addressable?storage）系統允許應用程序基于從項的內容生成的哈希值來從存儲器檢索項。因為CAS系統基于為項產生的哈希值而在項上執行存儲器相關的操作，并且哈希值基于項的內容而不是該項所存儲的位置，因此請求操作的應用程序可在不知道項的存儲副本的數量或位置的情況下如此做。例如，CAS系統可在位置A、B和C存儲項X的多個副本。通過向CAS系統發送基于項X的內容的哈希值，期望檢索項X的應用程序將如此做。基于該哈希值，CAS系統將向應用程序提供從位置A、B和C中的一個檢索到的項X的副本。這樣，應用程序將獲得項X，而不知道項X實際存儲在什么地方、項X存在多少副本、或者實際獲得檢索到的副本的具體位置。

存儲諸如文件或消息的數字項經常涉及對“片（chunk）存儲系統”進行調用。片存儲系統是在無需理解數字信息本身的格式或內容的情況下執行存儲操作的存儲系統。這樣的存儲系統之所以被稱為片存儲系統是因為該系統將所有形式的數字項視為這些項僅是數據的不透明片。例如，相同的片存儲系統可被用于字符處理應用程序、圖像管理應用程序、以及日歷系統，以各自存儲文件、圖像和約會。然而，從片存儲系統的觀點來看，僅一種項被存儲：數字信息的不透明片。

片存儲系統可被實現為CAS系統。例如，片存儲系統可通過對片應用加密哈希函數（例如，MD5、SHA-1或SHA2）來生成用于該片的哈希值。之后片存儲可存儲該片，并且保持將哈希值與該片所存位置相關聯的索引。當應用程序隨后請求檢索該片時，應用程序向片存儲系統提供哈希值。片存儲系統使用該索引來定位于哈希值相關的片，并向請求的應用程序提供如此定位的片。

片存儲系統可以以各種方式配置。美國申請第13/358,742描述了如何使用各種結構塊片存儲（building?block?chunk?store）可構成更大的合成片存儲。在確定使用何種結構塊片存儲、以及應如何布置這些片存儲的過程中，片存儲的有意使用是一個因素。

被配置為在不同的結構塊片存儲處存儲不同的片的片存儲系統是一種分布式哈希表，其中，通過對片應用哈希函數而產生的哈希值確定了最終將由哪個結構塊片存儲來存儲該片。例如，考慮包括兩個片存儲CS1和CS2的簡單情形。假設哈希函數產生0和1,000,000之間的哈希值，哈希至落入0和500,000之間的值的片可存儲在CS1處，而哈希至落入500,001和1,000,000之間的值的片可存儲在CS2處。

片可以哈希至的值的整個范圍（例如，0至1,000,000）被稱作“哈希空間”。哈希空間的一部分被稱作“哈希段”。在具有多個結構塊片存儲的系統中，不同的哈希段可被分配給不同的結構塊片存儲。在以上給出的示例中，CS1被分配0至500,000的哈希段，CS2被分配500,001和1,000,000的哈希段。

因為不同的片存儲被分配不同的哈希段，因此片存儲系統必須能夠基于由片生成的哈希值來確定對該片的操作中需要涉及哪個片存儲。盡管以穩定狀態保持哈希段至片存儲的映射相對來說直截了當，但當向系統加入新的片存儲和/或現有片存儲失效時保持變得日益困難。在任一情況下，可能需要修改哈希段至片存儲的映射。為了保持一致性，對映射的任何這種改變還會需要片在片存儲間重新分配。這樣的重新分配操作在時間和計算資源方面都是昂貴的。