High performance multiple-unit electronic data storage system with checkpoint logs for rapid failure recovery
First Claim
1. An electronic data storage system comprising a memory;
- a plurality of storage units each having a plurality of segments for storing blocks of data, each segment identified by a physical address; and
a controller in communication with the memory and the storage units, the controller operative;
to maintain in the memory an index containing entries each having a logical address and a corresponding physical address, an obsolete list containing physical addresses of segments that contain obsolete data, and a free list containing physical addresses of segments that are available to receive data for storage, andin response to a write command that provides a preselected logical address and an associated block of data for storage, to (a) select a physical address from the free list according to a predefined criterion, (b) obtain a next sequence number from a set of sequential numbers, (c) append to the block a tag that includes the sequence number, the preselected logical address, and an end flag, (d) store the block and its tag in the segment of the selected physical address, (e) delete the selected physical address from the free list, (f) enter the preselected logical address and the selected physical address in the index, (g) delete any previous index entry that contains a logical address which is the same as the preselected logical address, and (h) list the physical address from any such deleted entry in the obsolete list.
5 Assignments
0 Petitions
Accused Products
Abstract
An electronic data storage system including a memory, a plurality of magnetic disk units, and a controller. The memory contains an index cross-referencing logical address with physical addresses, an obsolete list and a free list. In response to a "write " command, the controller selects a physical address according to which segment can be used the most quickly, appends a tag to the data to be written, and writes the data to the selected segment. Appropriate entries are made in the index and the free list. The system recovers from memory loss by using a checkpoint log and a set of checkpoint segments on the disk that together contain backups of the index and other critical information needed to restore the system. Group indices are used for roll-back groups; operations on data in a group are invisible outside the group until after a "commit " command is issued.
-
Citations
15 Claims
-
1. An electronic data storage system comprising a memory;
- a plurality of storage units each having a plurality of segments for storing blocks of data, each segment identified by a physical address; and
a controller in communication with the memory and the storage units, the controller operative;to maintain in the memory an index containing entries each having a logical address and a corresponding physical address, an obsolete list containing physical addresses of segments that contain obsolete data, and a free list containing physical addresses of segments that are available to receive data for storage, and in response to a write command that provides a preselected logical address and an associated block of data for storage, to (a) select a physical address from the free list according to a predefined criterion, (b) obtain a next sequence number from a set of sequential numbers, (c) append to the block a tag that includes the sequence number, the preselected logical address, and an end flag, (d) store the block and its tag in the segment of the selected physical address, (e) delete the selected physical address from the free list, (f) enter the preselected logical address and the selected physical address in the index, (g) delete any previous index entry that contains a logical address which is the same as the preselected logical address, and (h) list the physical address from any such deleted entry in the obsolete list. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- a plurality of storage units each having a plurality of segments for storing blocks of data, each segment identified by a physical address; and
-
11. In an electronic data storage system of the kind having a plurality of storage units each having a plurality of segments for storing blocks of data, each segment identified by a physical address, a data storage and retrieval method comprising:
-
maintaining an index of logical addresses and corresponding physical addresses; maintaining an obsolete list containing physical addresses of segments that contain obsolete data; maintaining a free list containing physical addresses of segments that are available to receive data for storage; selecting a physical address from the free list for storing a block of data; storing the block at the selected physical address; removing the selected physical address from the free list; entering the selected physical address and a predetermined logical address in the index; deleting any previous index entry that contains a logical address which is the same as the predetermined logical address; and entering any physical address contained in any such deleted entry in the obsolete list. - View Dependent Claims (12, 13, 14, 15)
-
Specification