Transaction-based storage system and method that uses variable sized objects to store data

• US 7,386,663 B2
• Filed: 05/13/2004
• Issued: 06/10/2008
• Est. Priority Date: 05/13/2004
• Status: Active Grant

• Current Assignee: Robert E. Cousins
• Original Assignee: Robert E. Cousins
• Inventors: Cousins, Robert E.
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Ruiz, Aracelis
• Application Number:
  US10/845,546
• Publication Number:
  US 20050257083A1
• Time in Patent Office: 1,489 Days
• Field of Search: 711/114
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 2211/1026 Different size groups, i.e. non uniform size of groups in RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The present invention provides a storage system for storing variable sized objects. The storage system is preferably a transaction-based system that uses variable sized objects to store data. The storage system is preferably implemented using arrays disks that are arranged in ranks. Each rank includes multiple stripes. Each stripe may be read and written as a convenient unit for maximum performance. A rank manager is able to dynamically configure the ranks to adjust for failed and added disks by selectively shortening and lengthening the stripes. The storage system may include a stripe space table that contains entries describing the amount of space used in each stripe. An object map provides entries for each object in the storage system describing the location (e.g., rank, stripe and offset values), the length and version of the object. A volume index translates regions of logical storage into object identifiers. The storage system may implement various types of formats such as I-node, binary tree and extendible hashing formats.

Claims

1. A transaction-logging data storage system comprising:

a data storage subsystem that stores variable-size data objects, wherein the data storage subsystem is implemented using;

one or more storage devices comprising;

an array of data storage units, wherein the array is configured to provide one or more ranks, each of the one or more ranks providing stripes for storing data objects; and

a rank manager that performs configuration processing associated with the one or more ranks;

wherein the data storage subsystem is configured to write data corresponding to each of the stripes into the one or more ranks as a unit;

a stripe space table that keeps track of space usage in the data storage subsystem;

a mapping component that processes mapping information between data object identifiers and physical address information of the data objects within the data storage subsystem; and

at least one processing component that performs operations among the data storage subsystem, the mapping component and the stripe space table, wherein the operations are coordinated to implement logging data objects to be stored and logging changes to stored data objects;

wherein the mapping component includes one or more subcomponents that enable the transaction-logging data storage system to emulate one or more common data storage abstractions.

2. The system of claim 1 further comprising:

a stripe buffer for storing data objects to be written into a stripe.

3. The system of claim 2 wherein the system appends data objects to the stripe buffer until an append fails due to lack of free space in the stripe buffer, and then writes the contents of the stripe buffer into a corresponding stripe.

4. The system of claim 3 wherein the system appends data objects to the stripe buffer according to a write ordering policy.

5. The system of claim 2 wherein the at least one processing component compresses the contents of the stripe buffer as a unit.

6. The system of claim 1 further comprising:

a plurality of stripe buffers for storing data objects to be written into stripes, wherein the plurality of stripe buffers are configured to allows the system to handle multiple independent write operations concurrently.

7. The system of claim 6, wherein the at least one processing component is configured to execute a copy forward operation via one or more stripe buffers of the plurality of stripe buffers to free storage space in a first stripe, the copy forward operation comprising:

reading data objects contained in a first stripe; and

moving read data objects to a second stripe so that corresponding space is emptied in the first stripe.

8. The system of claim 1 wherein the at least one processing component includes a subcomponent executable to selectively compress the data objects.

9. The system of claim 1 wherein the system is adapted to perform a copy forward operation to free storage space in a first stripe, the copy forward operation comprising:

reading data objects contained in the first stripe; and

moving read data objects to a second stripe so that corresponding space is emptied in the first stripe.

10. The system of claim 9 wherein the copy forward operation further comprises:

compressing or incrementally recompressing the data objects prior to moving the data objects to a second stripe.

11. The system of claim 10 wherein the copy forward operation further comprises:

compressing or incrementally recompressing the data objects using a variety of conventional compression algorithms or conventional compression techniques prior to moving the data objects to a second stripe.

12. The system of claim 1, further comprising a plurality of data storage subsystems, wherein two or more of the data storage subsystems are implemented using different storage technologies, and wherein the at least one processing component manages data object storage as a function of the data storage technologies'"'"' implementations to optimize performance of the transaction-logging data storage system.

13. The system of claim 1, wherein the data storage abstractions do not consume actual storage space until data corresponding to allocated data objects are written.

14. The system of claim 1, wherein the data storage abstractions include provision of under-provisioned abstractions having capacities larger than actual storage space of the system.

15. The system of claim 1, wherein the mapping component is configured to present data storage abstractions that appear to have capacities larger than actual storage space of the system.

16. The system of claim 1 wherein the at least one processing component includes an executable subcomponent that performs one or both of compression and/or encryption of data objects as they are processed.

17. The system of claim 16 wherein the mapping component stores information required to decompress and/or decrypt the stored data objects within the data storage subsystem.

18. The system of claim 1, wherein sizes of stripes contained within the data storage subsystem may be different and may change as a function of available data storage units.

19. The system of claim 1, wherein the rank manager is configured to add a data storage unit initialized to zeros to a rank, reconfigure the rank, and change sizes of stripes within the rank.

20. The system of claim 1, wherein the rank manager is configured to omit a data storage unit from a rank, reconfigure the rank, and change sizes of stripes within the rank.

21. The system of claim 1 further comprising:

a non-volatile stripe buffer that stores data objects to be written into a stripe, wherein write operations of data objects to the stripe buffer are acknowledged asynchronously before the contents of the stripe buffer are written to the data storage subsystem.

22. The system of claim 1 further comprising:

a non-volatile stripe buffer that stores data objects to be written into a stripe, wherein the at least one processing component includes a subcomponent that, in the event of failure, writes the contents of the stripe buffer, at recovery time, to the data storage subsystem without data loss.

23. The system of claim 1 wherein the system maintains a list of stripes containing currently valid data objects and an order in which stripes were written to the data storage subsystem.

24. The system of claim 1 wherein the system maintains a list of data objects and an order in which data objects were written to the data storage subsystem.

25. The system of claim 1 wherein the mapping component further comprises a subcomponent that identifies currently valid data objects and creates a checkpoint by updating the mapping table.

26. The system of claim 25 wherein the mapping component further comprises a subcomponent that maps accesses to the data storage subsystem through a checkpoint to access a state of the data storage subsystem associated with a checkpoint.

27. The system of claim 25 wherein the mapping component further comprises a subcomponent configured to produce a list of data object versions associated with one or more checkpoints.

28. The system of claim 1 wherein the mapping component further comprises a subcomponent that identifies one or more versions of data objects associated with a deleted checkpoint and modifies the stripe space table to reflect space freed as a result of checkpoint deletion.

29. The system of claim 1 wherein at least one stripe space table is ordered via an algorithm that decides which stripe to select based on one or more characteristics selected from the group of characteristics composed of load sharing characteristics, stripe space usage characteristics, and/or performance characteristics.

30. A transaction-logging data storage system comprising:

a data storage subsystem that stores variable-size data objects, wherein the data storage subsystem is implemented using;

one or more storage devices comprising;

an array of data storage units, wherein the array is configured to provide one or more ranks, each of the one or more ranks providing stripes for storing data objects; and

a rank manager that performs configuration processing associated with the one or more ranks;

wherein the data storage subsystem is configured to write data corresponding to each of the stripes into the one or more ranks as a unit;

a stripe space table that keeps track of space usage in the data storage subsystem;

a mapping component that processes mapping information between data object identifiers and physical address information of the data objects within the data storage subsystem; and

at least one processing component that performs operations among the data storage subsystem, the mapping component and the stripe space table, wherein the operations are coordinated to implement logging data objects to be stored and logging chances to stored data objects;

wherein the mapping component includes one or more subcomponents that enable the transaction-logging data storage system to emulate two or more common data storage abstractions concurrently.

31. The system of claim 30, wherein the data storage abstractions are different and each data storage abstraction is associated with a subcomponent that is configured to access shared data storage subsystems.

32. The system of claim 30 further comprising a stripe buffer for storing data objects to be written into a stripe.

33. A transaction-logging data storage system comprising:

a component configured to write variable sized data objects corresponding to stripes into a data storage subsystem as a unit, wherein the component communicatively couples the transaction-logging data storage system to the data storage subsystem, and wherein the component manages data storage subsystem services to take on the features of a stripe-implemented storage technology;

a stripe space table that keeps track of space usage in the data storage subsystem;

a mapping component that processes mapping information between data object identifiers and physical address information of the data objects within the data storage subsystem; and

at least one processing component that coordinates operations among the data storage subsystem, the mapping component and the stripe space table, wherein the operations are coordinated to implement logging data objects to be stored and logging changes to stored data objects;

wherein the mapping component includes one or more subcomponents that enable the transaction-logging data storage system to emulate one or more common data storage abstractions.

34. The system of claim 33 further comprising:

a stripe buffer for storing data objects to be written into a stripe.

35. The system of claim 34 wherein the at least one processing component compresses the contents of the stripe buffer as a unit.

36. The system of claim 33 wherein the system appends data objects to the stripe buffer until an append fails due to lack of free space in the stripe buffer, and then to write the contents of the stripe buffer into a corresponding stripe.

37. The system of claim 36 wherein the system appends data objects to the stripe buffer according to a write ordering policy.

38. The system of claim 33 wherein the at least one processing component includes a subcomponent executable to selectively compress the data objects.

39. The system of claim 33, further comprising a plurality of components configured to write variable sized data objects, wherein two or more of the data storage subsystems are implemented using different storage technologies, and wherein the at least one processing components manage data object storage as a function of the data storage technologies'"'"' implementations to optimize performance of the transaction-logging data storage system.

40. The system of claim 33, wherein the data storage abstractions do not consume actual storage space until data corresponding to allocated data objects are written.

41. The system of claim 33, wherein the data storage abstractions include provision of under-provisioned abstractions having capacities larger than actual storage space of the system.

42. The system of claim 33, wherein the mapping component is configured to present data storage abstractions that appear to have capacities larger than actual storage space of the system.

43. The system of claim 33 wherein the at least one processing component includes an executable subcomponent that performs one or both of compression and/or encryption of data objects as they are processed.

44. The system of claim 43 wherein the mapping component stores information required to decompress and/or decrypt the stored data objects within the data storage subsystem.

45. The system of claim 33 further comprising:

a non-volatile stripe buffer that stores data objects to be written into a stripe, wherein write operations of data objects to the stripe buffer are acknowledged asynchronously before the contents of the stripe buffer are written to the data storage subsystem.

46. The system of claim 33 further comprising:

a non-volatile stripe buffer that stores data objects to be written into a stripe, wherein the at least one processing components includes an executable subcomponent that, in the event of failure, writes the contents of the stripe buffer, at recovery time, to the data storage subsystem without data loss.

47. The system of claim 33 further comprising:

a plurality of stripe buffers for storing data objects to be written into stripes, wherein the plurality of stripe buffers are configured to allow the system to handle multiple independent write operations concurrently.

48. The system of claim 47, wherein the at least one processing component is configured to execute a copy forward operation via one or more stripe buffers of the plurality of stripe buffers to free storage space in a first stripe, the copy forward operation comprising:

reading data objects contained in a first stripe; and

moving read data objects to a second stripe so that corresponding space is emptied in the first stripe.

49. The system of claim 33 wherein the system is adapted to perform a copy forward operation to free storage space in a first stripe, the copy forward operation comprising:

reading data objects contained in the first stripe; and

moving read data objects to a second stripe so that corresponding space is emptied in the first stripe.

50. The system of claim 49 wherein the copy forward operation further comprises:

compressing or incrementally recompressing the data objects prior to moving the data objects to a second stripe.

51. The system of claim 50 wherein the copy forward operation further comprises:

compressing or incrementally recompressing the data objects using a variety of conventional compression algorithms or conventional compression techniques prior to moving the data objects to a second stripe.

52. The system of claim 33 wherein the system maintains a list of stripes containing currently valid data objects and an order in which stripes were written to the data storage subsystem.

53. The system of claim 33 wherein the system maintains a list of data objects and an order in which data objects were written to the data storage subsystem.

54. The system of claim 33 wherein the mapping component further comprises a subcomponent that identifies currently valid data objects and creates a checkpoint by updating the mapping table.

55. The system of claim 54 wherein the mapping component further comprises a subcomponent that maps accesses to the data storage subsystem through a checkpoint to access a state of the data storage subsystem associated with a checkpoint.

56. The system of claim 54 wherein the mapping component further comprises a subcomponent configured to produce a list of data object versions associated with one or more checkpoints.

57. The system of claim 33 wherein the mapping component further comprises a subcomponent that identifies one or more versions of data objects associated with a deleted checkpoint and modifies the stripe space table to reflect space freed as a result of checkpoint deletion.

58. The system of claim 33 wherein at least one stripe space table is ordered via an algorithm that decides which stripe to select based on one or more characteristics selected from the group of characteristics composed of load sharing characteristics, stripe space usage characteristics, and/or performance characteristics.

59. A transaction-logging data storage system comprising:

a component configured to write variable sized data objects corresponding to stripes into a data storage subsystem as a unit, wherein the component communicatively couples the transaction-logging data storage system to the data storage subsystem, and wherein the component manages data storage subsystem services to take on the features of a stripe-implemented storage technology;

a stripe space table that keeps track of space usage in the data storage subsystem;

a mapping component that processes mapping information between data object identifiers and physical address information of the data objects within the data storage subsystem; and

at least one processing component that coordinates operations among the data storage subsystem, the mapping component and the stripe space table, wherein the operations are coordinated to implement logging data objects to be stored and logging changes to stored data objects;

wherein the mapping component includes one or more subcomponents that enable the transaction-logging data storage system to emulate two or more common data storage abstractions concurrently.

60. The system of claim 59, wherein the data storage abstractions are different and each data storage abstraction is associated with a subcomponent that is configured to access shared data storage subsystems.

61. The system of claim 59 further comprising a stripe buffer for storing data objects to be written into a stripe.