Log structured content addressable deduplicating storage

• US 8,266,114 B2
• Filed: 09/22/2008
• Issued: 09/11/2012
• Est. Priority Date: 09/22/2008
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Mace, James E., Parab, Nitin
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US12/235,325
• Publication Number:
  US 20100082547A1
• Time in Patent Office: 1,450 Days
• Field of Search: 1/1, 707/607, 707/625, 707/648, 707/674, 707/692, 707/661, 707/999.204, 707/999.206, 711/1, 711/4, 711/100, 711/101, 711/111, 700/1, 700/90, 700/91
• US Class Current: 707/692
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1865 Transactional file systems

Abstract

A log structured content addressable deduplicated data storage system may be used to store deduplicated data. Data to be stored is partitioned into data segments. Each unique data segment is associated with a label. The storage system maintains a transaction log. Mutating storage operations are initiated by storing transaction records in the transaction log. Additional transaction records are stored in the log when storage operations are completed. Upon restarting an embodiment of the data storage system, the transaction records from the transaction logs are replayed to recreate the state of the data storage system. The data storage system updates file system metadata with transaction information while a storage operation associated with the file is being processed. This transaction information serves as atomically updated transaction commit points, allowing fully internally consistent snapshots of deduplicated volumes to be taken at any time.

Claims

1. A method of storing data in a data storage system, the method comprising:

identifying a first storage label associated with a reference operation, wherein the first storage label is associated with a first previously stored data segment;

generating a first transaction record including an identifier associated with the storage operation;

storing the first transaction record in a transaction log data structure;

searching a label cache to locate first label metadata matching the first storage label;

in response to locating the first label metadata matching the first storage label in the label cache, changing a reference count included in the first label metadata, wherein the reference operation includes a reference count that specifies the number of occurrences of the first storage label referencing the first data segment;

in response to not locating the first label metadata matching the first storage label in the label cache;

generating a second transaction record indicating that the label metadata matching the storage label is not located in the label cache;

storing the second transaction record in the transaction log data structure;

searching the transaction log data structure to identify a plurality of transaction records, including the second transaction record, that indicate that a set of label metadata, including the first label metadata, corresponding with a plurality of storage labels, including the first storage label, are not located in the label cache;

searching at least one label metadata archive to locate each of the set of the label metadata matching the each of the plurality of storage labels, including the first label metadata matching the first storage label;

in response to locating the first label metadata matching the first storage label in the at least one label metadata archive, changing the reference count included in the first label metadata; and

generating a third transaction record including the identifier, wherein the third transaction record is adapted to indicate that the reference operation is complete; and

storing the third transaction record in the transaction log data structure.

2. The method of claim 1, wherein changing the reference count included in the label metadata includes increasing the reference count.

3. The method of claim 2, wherein in response to locating the label metadata matching the storage label in the label metadata archive, the method further comprises:

copying at least one data segment associated with the label from a data segment archive associated with the label metadata archive to a storage location in a data segment storage data structure;

retrieving a copy of the matching label metadata from the label metadata archive;

updating the copy of the matching label metadata to include the storage location; and

storing the updated copy of the matching label metadata in the label cache.

4. The method of claim 2, wherein:

the reference operation is associated with a reference increment value; and

increasing the reference count includes adding the reference increment value to the reference count.

5. The method of claim 1, wherein identifying the storage label associated with the reference operation comprises:

receiving unsegmented data;

partitioning the unsegmented data to form at least the data segment;

determining if the data segment storage data structure includes a copy of the data segment; and

in response to the determination that the data segment storage data structure includes the copy of the data segment, generating the reference operation.

6. The method of claim 5, wherein determining if the data segment storage data structure includes a copy of the data segment comprises:

generating the storage label; and

searching the data segment storage data structure using the storage label to determine if the data segment storage data structure includes a copy of the data segment.

7. The method of claim 5, wherein partitioning the unsegmented data includes determining a frequency value indicating the number of occurrences of the data segment included in the unsegmented data.

8. The method of claim 1, wherein the storage label is based at least in part on at least one data characterization of the data segment.

9. The method of claim 8, wherein the data characterization is based on at least a first hash of the data segment.

10. The method of claim 9, wherein the data characterization includes a second hash based on at least the first hash of the data segment.

11. The method of claim 1, wherein changing the reference count includes decreasing the reference count.

12. The method of claim 11, wherein searching at least one label metadata archive to locate the label metadata matching the storage label and, in response to locating the label metadata matching the storage label in the label metadata archive, changing the reference count included in the label metadata are performed after storing the second transaction record.

13. The method of claim 12, wherein searching at least one label metadata archive to locate the label metadata matching the storage label and, in response to locating the label metadata matching the storage label in the label metadata archive, changing the reference count included in the label metadata are performed by a background application process.

14. The method of claim 1, wherein the data segment includes a portion of data from a group consisting of:

a file;

a database record;

an object including object data and object methods;

a data structure; and

application data.

15. The method of claim 1, comprising:

identifying a file system file associated with the reference operation; and

initiating an atomic file system operation on the file system file;

receiving an indication that the atomic file system operation on the file system file is complete; and

in response to the indication that the atomic file system operation is complete, generating and storing the second transaction record to indicate a committal of the storage operation.

16. The method of claim 1, wherein the reference count includes occurrences of the storage label included in a hierarchy of storage labels.

17. The method of claim 1, wherein:

the reference operation is associated with a first reference count value;

the plurality of transaction records includes a fourth transaction record associated with a second reference operation, wherein the second reference operation is associated with the first storage label and a second reference count value; and

changing the reference count included in the first label metadata comprises;

adding the first and second reference count values to create an accumulated reference count value; and

changing the reference count included in the first label metadata by the accumulated reference count value.