High-performance log-structured RAID

• US 20030120864A1
• Filed: 12/09/2002
• Published: 06/26/2003
• Est. Priority Date: 12/26/2001
• Status: Active Grant

• Current Assignee: BOON Storage Technologies Incorporated, Middlefield Ventures, Inc. (Intel Corporation), Jeffrey Caspe, Middlefiled Ventures, Inc., Nike Partners, L.P., Thomas R. Hutchison
• Original Assignee: BOON Storage Technologies Incorporated
• Inventors: Yeo, Boon-Lock, Lee, Edward K.
• Granted Patent: US 7,047,358 B2
• Time in Patent Office: Days
• 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 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.

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 subsystem include sequential segments added to the log.

6. ) The method of claim 1, wherein appending each write operation to the log further includes writing a sequence number in each sector that is written to the log.

7. ) The method of claim 6, further including identifying an end of the log by scanning forward in the log until the sequence numbers decreases.

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

9. ) 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.

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

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

12. ) The method of claim 1, wherein the disk of the disk storage subsystem reside remote from a system requesting the write operation, wherein the disk are accessed over a network connection.

13. ) 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.

14. ) 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 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.

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

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

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

18. ) The machine readable-medium of claim 14, wherein updates to the disk subsystem include sequential segments added to the log.

19. ) The machine readable-medium of claim 14, wherein appending each write operation to the log further includes writing a sequence number in each sector that is written to the log.

20. ) The machine readable-medium of claim 19, further including identifying an end of the log by scanning forward in the log until the sequence numbers decreases.

21. ) The machine readable-medium of claim 14, wherein appending the log is performed in only one synchronous disk write operation.

22. ) The machine readable-medium of claim 14, 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.

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

24. ) The machine readable-medium of claim 23, wherein generating the metadata log includes periodically writing checkpoints.

25. ) The machine readable-medium of claim 14, wherein the disk of the disk storage subsystem reside remote from a system requesting the write operation, wherein the disk are accessed over a network connection.

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