Log-structured write cache for data storage devices and systems

• US 20040128470A1
• Filed: 12/27/2002
• Published: 07/01/2004
• Est. Priority Date: 12/27/2002
• Status: Active Grant

• Current Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Original Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Inventors: Hetzler, Steven Robert, Smith, Daniel Felix
• Granted Patent: US 7,010,645 B2
• Time in Patent Office: Days
• US Class Current: 711/209
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/312 In storage controller

Abstract

A log-structured write cache for a data storage system and method for improving the performance of the storage system are described. The system might be a RAID storage array, a disk drive, an optical disk, or a tape storage system. The write cache is preferably implemented in the main storage medium of the system, but can also be provided in other storage components of the system. The write cache includes cache lines where write data is temporarily accumulated in a non-volatile state so that it can be sequentially written to the target storage locations at a later time, thereby improving the overall performance of the system. Meta-data for each cache line is also maintained in the write cache. The meta-data includes the target sector address for each sector in the line and a sequence number that indicates the order in which data is posted to the cache lines. A buffer table entry is provided for each cache line. A hash table is used to search the buffer table for a sector address that is needed at each data read and write operation.

Claims

1. A data storage system comprising:

a medium for storing data as data blocks, each data block associated with a sector address;

a write cache having a plurality of cache lines, each cache line having a plurality of data blocks, line meta-data having information on the sector addresses where the data blocks in said cache line will be written to, and a sequential number indicating the order of the data blocks in said cache line relative to the data blocks in other cache lines,

wherein the write cache acts as a sequentially written staging area for data to improve performance of the system.

2. The storage system as recited in claim 1, wherein each cache line further comprises a parity block to enable the recovery of data in the cache line in the event of partial loss of the cache line.

3. The storage system as recited in claim 1, wherein write data is posted to the write cache before being written to the system at the sector addresses.

4. The storage system as recited in claim 1, wherein the write cache is maintained in a non-volatile memory of the system.

5. The storage system as recited in claim 1 further comprising a write cache control for interacting with a host system and the write cache.

6. The storage system as recited in claim 1, wherein the line meta-data includes a sequence number for identifying the cache line.

7. The storage system as recited in claim 1, wherein the line meta-data includes a line buffer table having a plurality of entries, each entry having a target sector address and a bitmap indicating sector locations in a block that are occupied.

8. The storage system as recited in claim 7, wherein the line buffer tables for all of the cache lines are integrated into a buffer table to allow a sector address to be searched.

9. The storage system as recited in claim 8, wherein the buffer table is searched using a hash table.

10. The storage system as recited in claim 9 further comprising a cache control for managing the buffer table and the hash table.

11. The storage system as recited in claim 1, wherein the medium includes a snapshot of the line meta-data for the entire write cache, the snapshot being used for recovering data in case of a system shutdown.

12. The storage system as recited in claim 1, wherein the cache lines are grouped together as clusters on the medium.

13. The storage system as recited in claim 1, wherein the system is a disk drive.

14. The storage system as recited in claim 1, wherein the system is a optical disk drive.

15. The storage system as recited in claim 1, wherein the system is a disk array.

16. The storage system as recited in claim 1, wherein the system is a storage server.

17. A method for improving the performance of a data storage system having a medium for storing data as data blocks, each data block associated with a sector address, the method comprising the steps of:

providing a write cache on the medium, the write cache having a plurality of cache lines, each cache line having a plurality of data blocks, line meta-data having information on the sector addresses where the data blocks in said cache line will be written to, and a sequential number indicating the order of the data blocks in said cache line relative to the data blocks in other cache lines; and

staging write data in the write cache as sequentially written data to improve performance of the system.

18. The method as recited in claim 17, wherein the step of staging includes the steps of:

receiving a plurality of data blocks to be written to the system;

storing the data blocks in one of the cache lines;

generating meta-data for the cache line, the meta-data including a sequence number for the cache line and the addresses for the data blocks; and

storing the meta-data in the cache line.

19. The method as recited in claim 18 further comprising the steps of:

computing a plurality of parity blocks for data in the cache line; and

writing the parity blocks to the cache line.

20. The method as recited in claim 17 further comprising the steps of:

providing a snapshot area on the medium; and

writing a copy of the meta-data for the cache lines in the snapshot area after data is written into the write cache.

21. The method as recited in claim 20 further comprising the step of determining a state of the write cache following an initialization based on the snapshot meta-data.

22. The method as recited in claim 21, wherein the step of determining includes the steps of:

reading the snapshot meta-data;

determining the cache lines that contain currently cached data; and

determining the state of the write cache based on the meta-data associated with the determined cache lines.

23. A computer-program product for use with a storage system to improve the performance of the system, the system having a medium for storing data as data blocks, each data block associated with a sector address, the computer-program product comprising:

a computer-readable medium;

means, provided on the computer-readable medium, for providing a write cache on the medium, the write cache having a plurality of cache lines, each cache line having a plurality of data blocks, line meta-data having information on the sector addresses where the data blocks in said cache line will be written to, and a sequential number indicating the order of the data blocks in said cache line relative to the data blocks in other cache lines; and

means, provided on the computer-readable medium, for staging write data in the write cache as sequentially written data to improve performance of the system.

24. The computer-program product as recited in claim 23, wherein said means for staging includes:

means, provided on the computer-readable medium, for receiving a plurality of data blocks to be written to the system;

means, provided on the computer-readable medium, for storing the data blocks in one of the cache lines;

means, provided on the computer-readable medium, for generating meta-data for the cache line, the meta-data including a sequence number for the cache line and the addresses for the data blocks; and

means, provided on the computer-readable medium, for storing the meta-data into the cache line.

25. The computer-program product as recited in claim 24 further comprising:

means, provided on the computer-readable medium, for computing a plurality of parity blocks for data in the cache line; and

means, provided on the computer-readable medium, for writing the parity blocks to the cache line.

26. The computer-program product as recited in claim 23 further comprising:

means, provided on the computer-readable medium, for providing a snapshot area on the medium; and

means, provided on the computer-readable medium, for writing a copy of the meta-data for the cache lines in the snapshot area after data is written into the write cache.

27. The computer-program product as recited in claim 26 further comprising means, provided on the computer-readable medium, for determining a state of the write cache following an initialization based on the snapshot meta-data.

28. The computer-program product as recited in claim 27, wherein said means for determining comprises:

means, provided on the computer-readable medium, for reading the snapshot meta-data;

means, provided on the computer-readable medium, for determining the cache lines that contain currently cached data; and

means, provided on the computer-readable medium, for determining the state of the write cache based on the meta-data associated with the determined cache lines.