[發明專利]用于數據去重復的可縮放塊存儲

有效

• 申請號: 201110385918.9
• 申請日: 2011-11-17
• 公開（公告）號: CN102541751A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 張震河;P·A·奧爾泰安;R·卡拉赫;A·古普塔;J·R·本頓;R·德塞
• 申請（專利權）人: 微軟公司
• 主分類號: G06F12/06
• 分類號: G06F12/06;G06F17/30
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 羅婷婷

1.一種方法(700)，包括：

將數據流解析(702)成數據塊序列；

確定(704)所述數據塊序列中的任何一個數據塊是否被存儲在包括多個數據塊的塊容器中；以及

將所述數據塊序列中被確定為沒有存儲在所述塊容器內的各數據塊以相鄰的排列并在所述塊容器中以與所述數據流中的順序相同的順序存儲(706)在所述塊容器中。

2.根據權利要求1所述的方法，其特征在于，還包括：

生成所述數據塊序列中的每一個數據塊的元數據，所述數據塊序列中的數據塊的元數據包括該數據塊在所述數據流中的偏移、指向該數據塊在所述塊容器中的位置的指針、以及該數據塊的位置指示符。

3.根據權利要求2所述的方法，其特征在于，還包括：

生成所述數據流的流映射，所述流映射包括所生成的元數據；以及

將所述流映射持久存儲在塊存儲中，所述塊存儲包括所述塊容器。

4.根據權利要求1所述的方法，其特征在于，還包括：

將第二數據流解析成第二數據塊序列；

確定所述第二數據塊序列的第一組數據塊包括一個或多個數據塊，該一個或多個數據塊是已經存儲在所述塊容器中的各數據塊的重復，并確定所述第二數據塊序列的第二組數據沒有被存儲在所述塊容器中；

將所述第二組數據塊以接著所述第一數據塊序列中的已存儲數據塊的相鄰的排列并以與所述第二數據流中的順序相同的順序存儲在所述塊容器中；以及

存儲所述第一組數據塊中的每一個數據塊的、指向已經存儲在所述塊容器中的相應數據塊的指針。

5.如權利要求4所述的方法，其特政在于，所述第二數據流中的每一個數據塊具有相關聯的元數據，該相關聯的元數據包括該數據塊在所述第二數據流中的偏移、指向該數據塊在所述塊容器中的位置的指針、以及該數據塊的位置指示符，其中所述第一數據塊序列中的每一個數據塊具有所述位置指示符的第一值，所述方法還包括：

將所述第一值分配給所述第一組數據塊中的每一個數據塊的位置指示符；

選擇與所述第二數據流相關聯的新位置指示符值；以及

將所述新位置指示符值分配給所述第二組數據塊中的每一個數據塊的位置指示符。

6.根據權利要求1所述的方法，其特征在于，還包括：

響應于對數據流的請求：

執行第一查找，以在所述塊容器中定位所請求的數據流的第一組數據塊中的第一個數據塊，

從所述塊容器順序地讀取所述第一組數據塊，

執行第二查找，以在所述塊容器中定位所請求的數據流中的第二組數據塊中的第一個數據塊，

從所述塊容器順序地讀取所述第二組數據塊，

7.根據權利要求1所述的方法，其特征在于，還包括：

生成與所述塊容器相關聯的重定向表，所述重定向表存儲關于數據塊位置改變的信息。

8.根據權利要求7所述的方法，其特征在于，還包括：

接收對數據塊的請求，所述請求包括該數據塊的標識符，所述數據塊標識符包括塊容器標識符、局部標識符、塊容器階段值和第一塊偏移值；

確定所述塊容器的與在所述請求中接收到的塊容器標識符相匹配的階段指示并不與在所述請求中接收到的塊容器階段值相匹配；

搜索所述重定向表，以得到包括所述局部標識符的匹配的條目，該條目包括與所述第一塊偏移值不同的第二塊偏移值；以及

從所述塊容器檢索在所述第二塊偏移值處的數據塊。

9.如權利要求8所述的方法，其特征在于，所述塊容器的所述階段指示以及所述塊容器標識符被包括在所述塊容器的頭部中，所述方法還包括：

修改所述塊容器的內容；

將一個或多個條目添加到所述重定向表中，所述一個或多個條目指示所述塊容器中的一個或多個數據塊由于所述修改而改變的塊偏移值；以及

由于所述修改，增加所述塊容器頭部中的所述階段指示。

10.如權利要求7所述的方法，其特征在于，所述關于數據塊位置改變的信息將不可變的每個容器的塊標識符映射至新偏移值。

11.根據權利要求8所述的方法，其特征在于，還包括：

在與所述數據流相關聯的流映射中將所述第一塊偏移值替換成所述第二塊偏移值；以及

從所述重定向表中刪除所述條目。