Log Structured Content Addressable Deduplicating Storage

• US 20100082529A1
• Filed: 03/31/2009
• Published: 04/01/2010
• Est. Priority Date: 05/08/2008
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Parab, Nitin, Mace, James E.
• Granted Patent: US 9,208,031 B2
• Time in Patent Office: Days
• US Class Current: 707/609
• 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-12. -12. (canceled)

13. A method of modifying data in a data storage system, the method comprising:

identifying a storage label and storage data associated with a storage operation;

generating a first transaction record associated with the storage operation;

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

modifying a portion of the data storage system associated with the storage label and the storage data based on the storage operation;

identifying a file system file associated with the portion of the data storage system;

performing an atomic file system operation on the file system file to indicate a committal of the storage operation;

generating a second transaction record, wherein the second transaction is adapted to indicate that the storage operation is complete; and

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

14. The method of claim 13, wherein the second transaction record includes a transaction identifier adapted to associate the second transaction record with the first transaction record.

15. The method of claim 14, wherein the first transaction record includes a copy of the transaction identifier.

16. The method of claim 13, wherein performing the atomic file system operation includes modifying an attribute of the file system file to indicate an association between the file system file and the first transaction record.

17. The method of claim 16, wherein the modified attribute includes a transaction indicator adapted to associate the file system file with at least the first transaction record.

18. The method of claim 16, wherein the storage operation is associated with an update intent.

19. The method of claim 18, wherein the update intent of the storage operation is to store a data segment at a storage location in a data segment storage data structure.

20. The method of claim 18, wherein the update intent of the storage operation is to store label metadata associated with the storage label.

21. The method of claim 18, wherein the update intent of the storage operation is to modify label metadata associated with the storage label.

22. The method of claim 21, wherein the update intent of the storage operation is to modify a reference count included in the label metadata associated with the storage label.

23. The method of claim 13, wherein performing the atomic file system operation includes deleting the file system file.

24. The method of claim 23, wherein the delete intent of the storage operation is to remove a data segment from a storage location in a data segment storage data structure, wherein the data segment represents at least a portion of file data associated with the file system file.

25. The method of claim 24, wherein the delete intent of the storage operation is to modify label metadata associated with the storage label.

26. The method of claim 25, wherein the delete intent of the storage operation is to modify a reference count included in the label metadata associated with the storage label.

27. The method of claim 13, 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.

28. A method of restoring a data storage system, the method comprising:

accessing a transaction log including transaction records associated with storage system operations;

identifying incomplete storage system operations from the transaction records;

analyzing file system attributes associated with the incomplete storage system operations to identify at least a portion of the incomplete storage system records that have been previously committed;

adding a portion of the transaction records associated with the portion of the incomplete storage system records to a list of storage operations to be reprocessed; and

reprocessing a portion of the storage system operations corresponding with the transaction records included in the list of storage operations to reconstruct a prior state of the data storage system.

29. The method of claim 28, the method comprising:

identifying completed storage system operations from the transaction records included in the transaction log;

adding a second portion of the transaction records associated with the completed storage system operations to the list of storage operations to be reprocessed.

30. The method of claim 28, wherein the file system attributes include transaction identifiers corresponding with the portion of the incomplete storage system records.

31. The method of claim 28, wherein the prior state represents a snapshot of the data storage system.

32. The method of claim 28, wherein the prior state represents the data storage system prior to a system restart.

33. The method of claim 28, wherein the file system attributes include the presence of a file associated with at least one of the identified incomplete storage system operations.

34. The method of claim 28, wherein the file system attributes include the absence of a file associated with at least one of the identified incomplete storage system operations.

35. The method of claim 28, wherein the prior state includes reference counts associated with data segments in a data segment storage data structure.

36. The method of claim 28, wherein identifying incomplete storage system operations from the transaction records comprises:

identifying a first transaction record in the transaction log indicating an initiation of a first storage system operation;

searching the transaction log for a second transaction record in the transaction log indicating a completion of the first storage system operation; and

in response to an absence of the second transaction record in the transaction log, selecting the first storage operation as an incomplete storage system operation.

37. The method of claim 28, wherein reprocessing the portion of the storage system operations comprises:

updating a label cache with label metadata determined from parameters included in the transaction records included in the list of storage operations.