Back to results
US 10,884,643 B2Granted
Variable length deduplication of stored data
AssigneeBottomline Technologies, Inc.
InventorsZenon Buratta, Andy Dobbels
Life of this patent
Estimating the term…
Abstract
A computer-implemented method for providing tenant aware, variable length, deduplication of data stored on a non-transitory computer readable storage medium. The method is performed at least in part by circuitry and the data comprises a plurality of data items. Each of the plurality of data items is associated with a particular tenant of a group of tenants that store data on the storage medium.
Claims18
A computer-implemented method for providing variable length, deduplication of data stored on a non-transitory computer readable storage medium, wherein the method is performed at least in part by circuitry, the data comprises a plurality of data items, the method comprising:
- receiving, from the storage medium, a set of data items;
- combining unique contiguous blocks found in one of the data items by:
- receiving, from the storage medium, the contiguous unique blocks, wherein each block of the contiguous unique blocks has been found in only one of the data items;
- for each particular block in the contiguous unique blocks:
- determining the particular data item that the particular block was found in;
- identifing at least one other block of the contiguous unique blocks that is found only in the determined data item and where a combination of the particular block and the at least one block is a contiguous block found in the determined data item;
- combining the particular block and the at least one other block into a combined block;
- storing the combined block on the storage medium;
- removing from the storage medium the particular block and the identified at least one other block;
- and
- updating a deduplicated copy of the particular data item to:
- replace the storage identifiers associated with the particular block and the at least one other block with a storage identifier describing a location of the combined block on the storage medium;
- and
- replace the location identifiers associated with the particular block and the at least one other block with a location identifier associated with the storage identifier of the combined block and describing a location of the combined block in the particular data item;
- for each respective data item of the set of data items, generating a deduplicated version of the respective data item on the storage medium, wherein the generation of the deduplicated version of the respective data item comprises:
- determining a plurality of blocks included in the respective data item;
- creating the deduplicated version of the respective data item;
- performing deduplication comprising:
- for each respective block of the determined plurality of blocks:
- determining if the respective block exists on the storage medium;
- when the respective block does not exist on the storage medium, storing the respective block on the storage medium;
- updating the deduplicated version of the respective data item to include:
- the storage identifier describing a location of the respective block on the storage medium;
- and
- the location identifier associated with the storage identifier of the respective block and describing a location of the respective block in the respective data item;
- and
- storing the deduplicated version of the respective data item in the storage medium.
24 more elements
A data deduplication device for providing variable length, deduplication of data, the device comprising:
- a non-transitory computer readable storage medium stores the data, wherein the data comprises a plurality of data items;
- circuitry configured to:
- receive, from the storage medium, a set of data items;
- combine unique contiguous blocks found in one of the data items through reception, from the storage medium, of the contiguous unique blocks, wherein each block of the contiguous unique blocks has been found in only one of the data items;
- for each particular block in the contiguous unique blocks:
- determine the item that the particular block was found in;
- identify at least one other block of the contiguous unique blocks that is found only in the determined data item and where a combination of the particular block and the at least one block is a contiguous block found in the determined data item;
- combine the particular block and the identified at least one other block into a combined block;
- store the combined block on the storage medium;
- remove from the storage medium the particular block and the identified at least one other block;
- and
- update a deduplicated copy of the particular data item to:
- replace the storage identifiers associated with the particular block and the at least one other block with a storage identifier describing a location of the combined block on the storage medium;
- and
- replace the location identifiers associated with the particular block and the at least one other block with a location identifier associated with the storage identifier of the combined block and describing a location of the combined block in the particular data item;
- for each respective data item of the set of data items, generate a deduplicated version of the respective data item on the storage medium, wherein the generation of the deduplicated version of the respective data item comprises:
- determining a plurality of blocks included in the respective data item;
- creating the deduplicated version of the respective data item;
- performing deduplication comprising:
- for each respective block of the determined plurality of blocks:
- determining if the respective block exists on the storage medium;
- when the respective block does not exist on the storage medium, storing the respective block on the storage medium;
- updating the deduplicated version of the respective data item to include:
- the storage identifier describing a location of the respective block on the storage medium;
- and
- the location identifier associated with the storage identifier of the respective block and describing a location of the respective block in the respective data item;
- storing the deduplicated version of the respective data item in the storage medium.
24 more elements
A computer-implemented method for combining unique contiguous blocks generated during data deduplication of data stored on a non-transitory computer readable storage medium, wherein the method is performed at least in part by circuitry, the data comprises a plurality of data items, the method comprising:
- receiving, from the storage medium, a set of unique blocks, wherein each block of the set of unique blocks has been found in only one data item;
- for each particular block in the set of unique blocks:
- determining a particular data item that the particular block was found in;
- identifying at least one other block of the set of unique blocks that is found only in the determined data item and where a combination of the particular block and the at least one block is a contiguous block found in the determined data item;
- combining the particular block and the identified at least one other block into a combined block;
- storing the combined block on the storage medium;
- removing from the storage medium the particular block and the identified at least one other block;
- updating a deduplicated copy of the particular data item to:
- replace the storage identifiers associated with the particular block and the at least one other block with a storage identifier describing a location of the combined block on the storage medium;
- and
- replace the location identifiers associated with the particular block and the at least one other block with a location identifier associated with the storage identifier of the combined block and describing a location of the combined block in the particular data item.
8 more elements
Dependencies are inferred from the claim text.