Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-18
2004-04-27
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S763000, C714S770000
Reexamination Certificate
active
06728922
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to data storage systems.
2. Related Art
Many computer applications need to store and retrieve information. Information can be stored on hard disks, floppy disks, CD-ROMs, semiconductor RAM memory and similar storage devices. Many of these storage systems are susceptible to data loss of various forms including disk failures. A solution to the problem of disk failure involves use of a RAID (redundant array of independent disks) system. RAID systems use multiple hard drives and space to store parity data generated from the data drives, either on a separate drive (known as the parity disk) or spread out among the multiple drives. The use of multiple hard drives makes it possible to replace faulty hard drives without going off-line; data contained on a drive can be rebuilt using the other data disks and the parity data. If a hard drive fails, a new hard drive can be inserted which the system is running by “hot-swapping” while on-line. The RAID can rebuild the data on the new disk using the other data disks and the parity data. The performance of a RAID system is improved by disk striping, which interleaves bytes or groups of bytes across multiple drives, so more than one disk is reading and writing simultaneously.
Another problem with storage devices is that they are susceptible to data corruption of various forms, including bit miswrites. While RAID allows a user to determine, using parity data, that there has been corruption of some data included in a stripe, the parity data does not include enough information to restore the corrupted data. More specifically, parity data does not allow a user to determine which data in the stripe has been corrupted; thus we do not know which data is trustworthy.
Checksums are another form of redundant data that can be written to individual disks. The combination of parity bits across the disks and checksums within each disk includes enough information, that the corrupted data can be restored in RAID and other redundant systems.
A second known problem is that disk drives in earlier data detection systems are formatted in a manner incompatible with a standard checksum system. More specifically, the disk drives do not have any space available to store checksum information.
A third known problem is that the prior art of storing checksums does not provide for recovery of lost writes, including writes that did not make it to a disk drive. In such systems, updates to the data and to the checksum occur in one I/O. Recovery in such systems may be incomplete if that particular I/O becomes “lost”.
Accordingly, it would be advantageous to provide an improved technique for the error checking and correction of data storage systems. This is achieved in an embodiment of the invention that is not subject to the drawbacks of the related art.
SUMMARY OF THE INVENTION
The invention provides an improved method and apparatus for a data storage system to be upgraded dynamically including multiple stages to provide redundant data for error checking without needing to take the system off-line.
In a first aspect of the invention, the data storage system is a RAID system composed of multiple hard disk drives and a controller for the drives. Additional redundant data (including data known as checksums) need to be stored on a formatted system that is in use (e.g. “on-line”). In a preferred embodiment including a set of consecutive blocks on the same disk, numbers
0
-
63
, checksums are computed from the data in blocks
0
-
62
and placed in block
63
. Similar to parity bits, checksums do not provide adequate information on their own because they are limited to detecting errors. The combination of (1) parity bits across the RAID system stored on the parity disk, (2) the remaining uncorrupted data in the data disks and (3) checksums within each disk includes sufficient information so as to enable restoration of corrupt data in RAID systems and other similar devices.
In a second aspect of the invention, a data storage system can be upgraded by following a step-wise procedure that involves reserving permanent checksum blocks and writing the checksums to the checksum blocks. The checksums are placed in permanently reserved checksum block locations after first moving data already in the reserved blocks to unoccupied and unreserved data storage blocks.
In a third aspect of the invention, the checksum block includes a collection of checksums. In a preferred embodiment, this checksum block is one of a set of 64 blocks (
0
-
63
) that form a megablock. There are 63 data blocks and 1 checksum block in a megablock. The checksums come in the following form: block checksums (8 byte ID and 4 Adler bytes from the location and data of the block 4K bytes ) and checksum blocks (a collection of 64 of these block checksums). The 64
th
block checksum in the checksum block checks the checksum block itself. In other embodiments, other formats of data and algorithms other than Adler's can be used.
In a fourth aspect of the invention, new data is written to data blocks in the previously upgraded system. New checksums are computed and written to new checksum blocks that are separate from the data blocks. Corrupted data can be identified on a particular disk drive in a RAID and other redundant data storage systems and restored using the other data disks and the parity disk while the system is on-line.
In a fifth aspect of the invention, data and checksums are stored in separate blocks. Two separate I/Os are performed (one I/O to updated the data and the second to updated the checksum). This separation allows recovery of information if data fails to be written to a disk or is otherwise “lost”.
In a preferred embodiment, the invention is operative on a RAID system for a file server. However, in other embodiments, the invention is applicable to any computer data storage system such as a database system or a store and forward system such as cache or RAM.
REFERENCES:
patent: 4527232 (1985-07-01), Bechtolsheim
patent: 4742447 (1988-05-01), Duvall et al.
patent: 4742450 (1988-05-01), Duvall et al.
patent: 4761785 (1988-08-01), Clark et al.
patent: 4875159 (1989-10-01), Cary et al.
patent: 4937763 (1990-06-01), Mott
patent: 5008786 (1991-04-01), Thatte
patent: 5043876 (1991-08-01), Terry
patent: 5067099 (1991-11-01), McCown et al.
patent: 5088081 (1992-02-01), Farr
patent: 5144659 (1992-09-01), Jones
patent: 5146588 (1992-09-01), Crater et al.
patent: 5155835 (1992-10-01), Belsan
patent: 5163131 (1992-11-01), Row et al.
patent: 5163148 (1992-11-01), Walls
patent: 5195100 (1993-03-01), Katz et al.
patent: 5218695 (1993-06-01), Noveck et al.
patent: 5218696 (1993-06-01), Baird et al.
patent: 5222217 (1993-06-01), Blount et al.
patent: 5235601 (1993-08-01), Stallmo et al.
patent: 5274799 (1993-12-01), Brant et al.
patent: 5274807 (1993-12-01), Hoshen et al.
patent: 5297265 (1994-03-01), Frank et al.
patent: 5305326 (1994-04-01), Solomon et al.
patent: 5315602 (1994-05-01), Noya et al.
patent: 5333305 (1994-07-01), Neufeld
patent: 5335235 (1994-08-01), Arnott
patent: 5357509 (1994-10-01), Ohizumi
patent: 5379417 (1995-01-01), Lui et al.
patent: 5490248 (1996-02-01), Dan et al.
patent: 5502836 (1996-03-01), Hale et al.
patent: 5649152 (1997-07-01), Ohran et al.
patent: 5668943 (1997-09-01), Attanasio et al.
patent: 5668958 (1997-09-01), Bendert et al.
patent: 5675726 (1997-10-01), Hohenstein et al.
patent: 5678006 (1997-10-01), Valizadeh et al.
patent: 5737744 (1998-04-01), Callison et al.
patent: 5742752 (1998-04-01), DeKoning
patent: 5819292 (1998-10-01), Hitz et al.
patent: 5819310 (1998-10-01), Vishlitzky et al.
patent: 5828876 (1998-10-01), Fish et al.
patent: 5829046 (1998-10-01), Tzelnic et al.
patent: 5835953 (1998-11-01), Ohran
patent: 5907672 (1999-05-01), Matze et al.
patent: 5948110 (1999-09-01), Hitz et al.
patent: 5950225 (1999-09-01), Kleiman
patent: 5963962 (1999-10-01), Hitz et al.
patent: 6000039 (1999-12-01), Tanaka et al.
patent: 6061770 (2000-05-01), Franklin
patent: 6076148 (2000-06-01), Kedem
patent: 6101585 (
Edwards John K.
Kleiman Steven R.
Rowe Alan
Sundaram Rajesh
Viswanathan Srinivvasan
Network Appliance Inc.
Swernofsky Law Group PC
Ton David
LandOfFree
Dynamic data space does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic data space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic data space will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244669