High-performance log-structured RAID

• US 7,047,358 B2
• Filed: 12/09/2002
• Issued: 05/16/2006
• Est. Priority Date: 12/26/2001
• Status: Expired due to Fees

• Current Assignee: BOON Storage Technologies Incorporated, Middlefield Ventures, Inc. (Intel Corporation), Jeffrey Caspe, Middlefiled Ventures, Inc., Nike Partmers, L.P., Nike Partners, L.P., Thomas R. Hutchison
• Original Assignee: BOON Storage Technologies Incorporated, Middlefield Ventures, Inc. (Intel Corporation), Jeffrey Caspe, Nike Partners, L.P., Synapse Fund II, LLC (Synapse Capital LLC), Thomas R. Hutchison
• Inventors: Yeo, Boon-Lock, Lee, Edward K.
• Primary Examiner(s): Bragdon, Reginald G.
• Assistant Examiner(s): Walter, Craig E
• Application Number:
  US10/314,204
• Publication Number:
  US 20030120864A1
• Time in Patent Office: 1,254 Days
• Field of Search: 711/114, 711/112, 711/138, 707/202, 714/13
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 2211/1009 Cache, i.e. caches used in RAID system with parity
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

This invention describes a high-performance, log-structured implementation of a RAID subsystem that can be efficiently implemented in software. The methods described here allow the RAID subsystem to achieve high performance without using specialized hardware such as non-volatile memory or hardware XOR/DMA engines. Furthermore, the RAID implementation described here is well suited for supporting many functions required for advanced storage virtualization such as virtual disks, graceful addition and removal of disks, tolerating multi-disk failures, and snapshots.

Claims

1. A method of storing data on a disk storage subsystem comprising:

receiving a request to write data; and

appending each write operation to a first log to identify a storage location of data written to the disk storage subsystem, wherein the first log consists of a sequence of segments, the segments consist of a sequence of variable length stripes, a length of a stripe varies based on a quantity of disks addressed by a stripe, and wherein appending each write operation to the first log further includes writing a sequence number in each sector that is written to the first log.

2. The method of claim 1, wherein the stripes consist of a sequence of pages.

3. The method of claim 2, wherein the pages consist of a sequence of contiguous sectors.

4. The method of claim 3, wherein each page in the same segment is located on a separate disk.

5. The method of claim 1, wherein updates to the disk storage subsystem include sequential segments added to the first log.

6. The method of claim 1, further including identifying an end of the first log by scanning forward in the first log until the sequence numbers decrease.

7. The method of claim 1, wherein appending the first log is performed in only one synchronous disk write operation.

8. The method of claim 1, further including a garbage collection process that includes periodically scanning segments to identify and remove overwritten pages, collect pages that have not been overwritten and append the pages that have not been overwritten to the first log.

9. The method of claim 1, further including generating a separate metadata log, the metadata log mapping virtual disk addresses to physical disk addresses.

10. The method of claim 9, wherein generating the metadata log includes periodically writing checkpoints.

11. The method of claim 1, wherein the disks of the disk storage subsystem reside remotely from a system requesting the write operation, and wherein the disks are accessed over a network connection.

12. The method of claim 1, wherein data written to the first log within a most recent predetermined period of time, is protected from being overwritten.

13. A machine readable-medium, having stored thereon a set of instructions, which when executed, perform a method of storing data on a disk storage subsystem comprising:

receiving a request to write data; and

appending each write operation to a first log to identify a storage location of data written to the disk storage subsystem, wherein the first log consists of a sequence of segments, the segments consist of a sequence of variable length stripes, a length of a stripe varies based on a quantity of disks addressed by a stripe, wherein appending each write operation to the first log further includes writing a sequence number in each sector that is written to the first log.

14. The machine readable-medium of claim 13, wherein the stripes consist of a sequence of pages.

15. The machine readable-medium of claim 14, wherein the pages consist of a sequence of contiguous sectors.

16. The machine readable-medium of claim 15, wherein each page in the same segment is located on a separate disk.

17. The machine readable-medium of claim 13, wherein updates to the disk storage subsystem include sequential segments added to the first log.

18. The machine readable-medium of claim 13, further including identifying an end of the first log by scanning forward in the first log until the sequence numbers decrease.

19. The machine readable-medium of claim 13, wherein appending the first log is performed in only one synchronous disk write operation.

20. The machine readable-medium of claim 13, further including a garbage collection process that includes periodically scanning segments to identify and remove overwritten pages, collect pages that have not been overwritten and append the pages that have not been overwritten to the first log.

21. The machine readable-medium of claim 13, further including generating a separate metadata log, the metadata log mapping virtual disk addresses to physical disk addresses.

22. The machine readable-medium of claim 21, wherein generating the metadata log includes periodically writing checkpoints.

23. The machine readable-medium of claim 13, wherein the disks of the disk storage subsystem reside remotely from a system requesting the write operation, and wherein the disks are accessed over a network connection.

24. The machine readable-medium of claim 13, wherein data written to the first log within a most recent predetermined period of time is protected from being overwritten.

25. A data processing system, comprising:

a processor; and

a memory coupled to the processor for storing instructions, which when executed from the memory, cause the processor to perform a method of storing data on a disk storage subsystem, the method including

receiving a request to write data, and

appending each write operation to a first log to identify a storage location of data written to the disk storage subsystem, wherein the first log consists of a sequence of segments, the segments consist of a sequence of variable length stripes, a length of a stripe varies based on a quantity of disks addressed by a stripe, wherein appending each write operation to the first log further includes writing a sequence number in each sector that is written to the first log.