Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-07-06
2003-10-21
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S111000, C711S114000, C711S004000
Reexamination Certificate
active
06636941
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to electronic data storage systems, and specifically to nonvolatile storage systems which are able to recover from system failure.
BACKGROUND OF THE INVENTION
Methods for efficiently storing data, and recovering the stored data in the event of a computer system failure, are known in the art. The methods rely on storing information additional to the data to a non-volatile memory, typically a disk, and using the additional information to recover the stored data when the failure occurs.
U.S. Pat. No. 5,345,575 to English et al., whose disclosure is incorporated herein by reference, describes a disk controller comprising a memory. The memory contains a table mapping logical addresses of data blocks stored on a disk to labels identifying physical storage locations. In addition to writing the data to a storage location, the disk controller writes the associated logical address of each storage location, a time stamp, and data indicating where in a sequence of data blocks a specific data block occurs. The additional information is used to recover from system failures by reading from substantially the whole disk.
U.S. Pat. No. 5,481,694 to Chao et al., whose disclosure is incorporated herein by reference, describes an electronic data storage system comprising a memory, a plurality of magnetic disk units, and a controller. The memory comprises a table cross-referencing logical addresses with physical addresses on the disk units, a list of physical addresses containing obsolete data, and a list of physical addresses for segments on the disk units which are able to receive data. When data are written to the disk units, a tag comprising the logical address and a sequence number for multiblock writes is written with the data. To recover from a system failure, a checkpoint log and checkpoint segments stored on the disk units recover the table and lists.
U.S. Pat. No. 5,708,793 to Franaszek et al., whose disclosure is incorporated herein by reference, describes a method for optimizing a disk for a random write workload. The method comprises maintaining a mapping of logical to physical addresses within a disk controller. Data are written to the disk at a free disk location, the location being chosen to minimize time taken to write to the location.
In an article by de Jonge et al., “The Logical Disk: A New Approach to Improving File Systems,” in
Proceedings of the
14
th Symposium on Operating Systems Principles
, pp. 15-28, December 1993, which is incorporated herein by reference, the authors describe a logical disk wherein an interface is defined to disk storage which separates file management and disk management. The interface uses logical block numbers and block lists, and supports multiple file systems.
In an article by English et al., “Loge: a self-organizing disk controller,” in
Proceedings of the USENIX Winter
1992
Technical Conference
, pp. 237-251, January 1992, which is incorporated herein by reference, the authors describe a system for storing data to a disk using a translation table and an allocation map. A trailer tag comprising a block address and a time stamp is written to the disk together with the stored data. The information in the trailer tag enables the system to recover from a failure.
In an article by Chao et al., “Mime: a high performance parallel storage device with strong recovery guarantees,” HPL-CSP-92-9, published by Hewlett-Packard Company, November 1992, which is incorporated herein by reference, the authors describe a disk storage architecture similar to that of Loge, as described above. In Mime, the trailer tag comprises a block address, a sequence number for multiblock writes, and a last-packet-in-multiblock-write flag. As in Loge, the trailer tag information enables the system to recover from a failure.
SUMMARY OF THE INVENTION
It is an object of some aspects of the present invention to provide apparatus and methods for improved storage of electronic data in a non-volatile memory.
It is a further object of some aspects of the present invention to provide apparatus and methods for improved recovery of data in the event of a failure in a computing system.
In preferred embodiments of the present invention, an enhanced storage system (ESS) for data storage comprises a non-volatile on-disk storage medium which is written to and read from by a disk arm and a disk head, which are typically industry-standard components. The ESS uses data structures which are maintained in volatile memory, some of which data structures are used to generate incremental system data regarding read and write operations to the storage medium. The data structures comprise, inter alia, a table which translates between logical addresses and disk sector addresses, and an allocation bitmap which shows whether a disk sector address is available to be written to. The translation table is referred to by the ESS before any read, write, allocate, or delete, operation to the disk is performed, and the allocation bitmap is updated before and after each write.
The physical locations for successive writes to the disk are allocated so as to maintain the disk arm moving, insofar as possible, in a preferred direction. Each time user data are written to a given block on the disk, a tag containing incremental system data is also written to the same block. The system data are used subsequently, if needed, to enable the system to recover in case a failure, such as a power failure, occurs before the locations of all of the blocks have been written to the disk in a checkpoint operation, described below. (The locations of the blocks are stored in the translation table.) The incremental system data point forward to the next block to be written to, so that blocks are “chained” together and can be conveniently found and recovered.
Periodically and/or on demand, preferably when the disk arm has to move opposite to the preferred direction, the storage system writes checkpoint data to the disk. The checkpoint data comprise the translation table and the allocation bitmap and data pointing to the beginning of a block chain. Most preferably, the checkpoint data are written to a predetermined region of the disk. Thus the checkpoint data can be used as a starting point when recovering from a failure.
The enhanced storage system of the present invention comprises a rich set of disk operations and thus has a number of advantages over systems known in the art:
By having the majority of write operations to the disk occurring on a preferred direction of motion of the disk arm, disk write time is improved. (If most reads are supplied by cache hits, disk write time is optimized.)
In the event of a volatile memory failure, a complete recovery is possible from checkpoint data and incremental system data that have been stored on the disk.
Since the ESS chains together blocks which are written to the disk, recovery from a failure is linear with the number of block write operations since the last checkpoint. Thus recovery takes substantially the same amount of time as was taken for the write operations performed since the last checkpoint, so that recovery time is optimized.
As a natural extension of the forward chaining of blocks, the ESS supports allocation and write, and deletion of blocks that withstand failures, so avoiding leakage of blocks, unlike other methods known in the art.
No extra input or output disk operations are required at the time of reading to or writing from the disk. All information necessary for a complete recovery from a disk failure is incorporated into blocks comprising user data as the data blocks themselves are written to the disk.
All information for a complete disk recovery is written to the disk, so that the disk may be transferred from one disk host and used in another disk host.
In some preferred embodiments of the present invention, a disk is partitioned so that a first part is operated as a data storage system according to the present invention as described herein, and a second part of the disk is operated as a conventional storage sys
Gold Israel
Satran Julian
Sheinwald Dafna
Darby & Darby
Elmore Stephen
International Business Machines - Corporation
Kim Matthew
LandOfFree
Enhanced stable disk storage does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced stable disk storage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced stable disk storage will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3171049