US6052799A — System and method for recovering a directory for …

Claim 1

Independent Claim 236 words

In a storage system comprising an array of storage devices, including a processor and memory, having a plurality of data blocks organized on the storage devices in segments striped across the storage devices, wherein when a data block in a segment stored on the storage devices in a first location is updated, the updated data block is assigned to a different segment, written to a new storage location, and designated as a current data block, and the data block in the first location is designated an old data block, and having a main directory, stored in memory, containing the locations on the storage devices of the current data blocks, a method for recovering the main directory in the event the directory is damaged, comprising the steps of: a) storing on the storage devices, for each segment, a segment directory having information on the data blocks in the segment; b) periodically writing a checkpoint of the main directory to the storage devices; c) maintaining a list of closed segments written to the storage devices since the checkpoint of the main directory was written to the storage devices; and d) during a main directory recovery procedure performing the steps of: i) reading into memory the checkpoint of the main directory; and ii) for each segment as indicated by the closed segments list, using the information in the corresponding segment directory to update the checkpoint of the main directory.

Claim 2

Dependent Claim 236 words

In a storage system comprising an array of storage devices, including a processor and memory, having a plurality of data blocks organized on the storage devices in segments striped across the storage devices, wherein when a data block in a segment stored on the storage devices in a first location is updated, the updated data block is assigned to a different segment, written to a new storage location, and designated as a current data block, and the data block in the first location is designated an old data block, and having a main directory, stored in memory, containing the locations on the storage devices of the current data blocks, a method for recovering the main directory in the event the directory is damaged, comprising the steps of: a) storing on the storage devices, for each segment, a segment directory having information on the data blocks in the segment; b) periodically writing a checkpoint of the main directory to the storage devices; c) maintaining a list of closed segments written to the storage devices since the checkpoint of the main directory was written to the storage devices; and d) during a main directory recovery procedure performing the steps of: i) reading into memory the checkpoint of the main directory; and ii) for each segment as indicated by the closed segments list, using the information in the corresponding segment directory to update the checkpoint of the main directory.

Claim 3

Dependent Claim 32 words

The method of claim 1 wherein the checkpoint of the main directory is written to the storage device at regular intervals based on the number of segments written to the storage devices.

Claim 4

Dependent Claim 167 words

The method of claim 1 further comprising the steps of: periodically recycling segments having a relatively low occupancy value such that the current data blocks are rewritten to the storage device as part of different segments; maintaining a status listing for each segment including information on when that segment data was written to the storage devices, segment status, and the occupancy value for that segment; writing a checkpoint segment status listing and an empty closed segments list to the storage devices at the same time that the main directory is written to the storage devices; and during the main directory recovery procedure, for data blocks that have been updated since the previous checkpoint, using the closed segments list to identify the newly written segments and using the segment directories to identify the previous segments in which the data blocks previously resided; and using the current and previous lengths of the data blocks in the segment directories to update the occupancy values in the checkpoint segment status listing.

Claim 5

Dependent Claim 40 words

The method of claim 3 further comprising the step of: suspending memory updates to the segment status listing, the closed segments list, and main directory during the writing of the checkpoint segment status listing and the empty closed segments list.

Claim 6

Dependent Claim 57 words

The method of claim 4 further comprising the step of: at the same time that a closed segment is written to the storage devices, updating the closed segments list, writing the updated closed segments list to the storage devices, and writing the segment directory for that closed segment to the storage devices as part of the segment.

Claim 7

Dependent Claim 41 words

The method of claim 5 wherein a portion of the storage devices is partitioned as a control partition and the checkpoint of the main directory, the checkpoint segment status listing and the closed segments list are written to the control partition.

Claim 8

Dependent Claim 28 words

The method of claim 1 wherein each segment includes parity information used to reconstruct the data blocks of the segment in the event a storage device is damaged.

Claim 9

Dependent Claim 35 words

The method of claim 1 wherein the checkpoint of the main directory is written to two different locations on separate storage arrays, and a timestamp is written at the start and end of each copy.

Claim 10

Dependent Claim 160 words

A data storage system for storing electronic data for a data processing system, the data storage system comprising: an array of storage devices, including a processor and memory, having a plurality of data blocks organized on the storage devices in segments striped across the storage devices, wherein data blocks are designated as current data blocks and old data blocks; a main directory, stored in memory, containing the location on the storage devices of each of the current data blocks; a plurality of segment directories, each segment directory having information on the data blocks in a given segment; a checkpoint of the main directory periodically written to the storage devices; and a closed segments list of segments written to the storage devices since the checkpoint of the main directory was written to the storage devices, wherein the main directory is recoverable using the checkpoint directory and the information in the segment directories of the segments listed in the closed segments list.

Claim 11

Dependent Claim 160 words

A data storage system for storing electronic data for a data processing system, the data storage system comprising: an array of storage devices, including a processor and memory, having a plurality of data blocks organized on the storage devices in segments striped across the storage devices, wherein data blocks are designated as current data blocks and old data blocks; a main directory, stored in memory, containing the location on the storage devices of each of the current data blocks; a plurality of segment directories, each segment directory having information on the data blocks in a given segment; a checkpoint of the main directory periodically written to the storage devices; and a closed segments list of segments written to the storage devices since the checkpoint of the main directory was written to the storage devices, wherein the main directory is recoverable using the checkpoint directory and the information in the segment directories of the segments listed in the closed segments list.

Claim 12

Dependent Claim 29 words

The system of claim 9 wherein the main directory is written to the storage device at regular intervals based on the number of segments written to the storage devices.

Claim 13

Dependent Claim 45 words

The system of claim 9 wherein periodically closed segments having a relatively low occupancy value are recycled such that the current data blocks are rewritten to the storage device as a part of a different segment, and the recycled segment is designated a free segment.

Claim 14

Dependent Claim 126 words

The system of claim 11 further comprising: a segment status listing maintained in the memory for each segment including information on when a segment was written to the storage devices, segment status, and the occupancy value of the segment; and a checkpoint segment status listing stored on the storage devices, the checkpoint segment status listing and an empty closed segments list being written to the storage devices at the same time that the checkpoint of the main directory is written to the storage devices, wherein the checkpoint directory, the closed segments list, the segment directories of the segments on the closed segments list and the checkpoint segment status listing are used to recover a damaged main directory and update the segment status listing stored in memory.

Claim 15

Dependent Claim 52 words

The system of claim 12 wherein a portion of the storage devices is partitioned as a control partition and the checkpoint of the main directory, the checkpoint segment status listing and the closed segments list are written to the control partition, and each segment directory is written as part of the segment.

Claim 16

Dependent Claim 279 words

In a storage system comprising an array of storage devices, including a processor and memory, having a plurality of data blocks organized on the storage devices in segments striped An across the storage devices, and each segment includes parity information used to reconstruct the data blocks of the segment in the event a storage device is damaged, wherein when a data block in a segment stored on the storage devices in a first location is updated, the updated data block is designated a current data in block and written to a new storage location as part of a different segment, and the data block in the first location is designated an old data block, and having a main directory, stored in memory, containing the location on the storage devices of each of the current data blocks, a system for recovering the main directory in the event the main directory is damaged, comprising: means for storing on the storage devices, for each segment, and as part of the segment, a segment directory having information on the data blocks in the segment; means for periodically writing a checkpoint of the main directory to the storage devices; means for maintaining a list of closed segments written to the storage devices since the checkpoint directory was written to the storage devices wherein the closed segments list is updated on the storage devices each time a segment is closed; means for reading into memory the checkpoint of the main directory; means for reading into memory the checkpoint closed segments list; and means for using the information in the segment directories of the segments identified in the closed segments list to update the checkpoint directory.

Claim 17

Dependent Claim 279 words

In a storage system comprising an array of storage devices, including a processor and memory, having a plurality of data blocks organized on the storage devices in segments striped An across the storage devices, and each segment includes parity information used to reconstruct the data blocks of the segment in the event a storage device is damaged, wherein when a data block in a segment stored on the storage devices in a first location is updated, the updated data block is designated a current data in block and written to a new storage location as part of a different segment, and the data block in the first location is designated an old data block, and having a main directory, stored in memory, containing the location on the storage devices of each of the current data blocks, a system for recovering the main directory in the event the main directory is damaged, comprising: means for storing on the storage devices, for each segment, and as part of the segment, a segment directory having information on the data blocks in the segment; means for periodically writing a checkpoint of the main directory to the storage devices; means for maintaining a list of closed segments written to the storage devices since the checkpoint directory was written to the storage devices wherein the closed segments list is updated on the storage devices each time a segment is closed; means for reading into memory the checkpoint of the main directory; means for reading into memory the checkpoint closed segments list; and means for using the information in the segment directories of the segments identified in the closed segments list to update the checkpoint directory.

Claim 18

Dependent Claim 223 words

An article of manufacture for use in storing and managing a plurality of sets of data blocks in a computer system having memory and a group of storage devices, wherein each set of data blocks is stored in a segment striped across the group of storage devices, the article of manufacture having a computer program code embodied in said medium which causes the computer system to: update a data block in a segment stored on the storage devices in a first location by writing the updated data block to a new storage location, wherein the updated data block is designated a current data block and the data block in the first location is designated an old data block; maintain a main directory, stored in memory, containing the location on the storage devices of each of the current data blocks; store on the storage devices, for each segment, a segment directory having information on the data blocks in the segment; write a checkpoint of the main directory to the storage devices at periodic intervals; maintain a list of closed segments written to the storage devices since the checkpoint of the main directory was written to the storage devices; and recover a damaged main directory using the checkpoint directory and the information in the corresponding segment directory for each segment on the closed segments list.

Claim 19

Dependent Claim 223 words

An article of manufacture for use in storing and managing a plurality of sets of data blocks in a computer system having memory and a group of storage devices, wherein each set of data blocks is stored in a segment striped across the group of storage devices, the article of manufacture having a computer program code embodied in said medium which causes the computer system to: update a data block in a segment stored on the storage devices in a first location by writing the updated data block to a new storage location, wherein the updated data block is designated a current data block and the data block in the first location is designated an old data block; maintain a main directory, stored in memory, containing the location on the storage devices of each of the current data blocks; store on the storage devices, for each segment, a segment directory having information on the data blocks in the segment; write a checkpoint of the main directory to the storage devices at periodic intervals; maintain a list of closed segments written to the storage devices since the checkpoint of the main directory was written to the storage devices; and recover a damaged main directory using the checkpoint directory and the information in the corresponding segment directory for each segment on the closed segments list.

Claim 20

Dependent Claim 137 words

The article of manufacture as claimed in claim 15 wherein the program code further causes the computer to: recycle identified segments having a relatively low occupancy value by writing the current data blocks in the identified segment to the storage devices as part of different segments; maintain a segment status listing for each segment including information on when that segment was written to the storage devices, segment status, and the occupancy value of that segment; write a checkpoint segment status listing to the storage devices at the same time that the checkpoint directory is written to the storage devices; and recover a damaged segment status listing using the checkpoint segment status listing and updating the occupancy value in the checkpoint segment status listing for each of the segments affected by the segments on the closed segments list.

Claim 21

Dependent Claim 119 words

The article of manufacture as claimed in claim 15 wherein the program code further causes the computer to: suspend memory updates to the main LSA directory, the segment status listing and the closed segments list during the writing of the checkpoint segment status listing and the empty closed segments list; at the same time that a segment is written to the storage devices, update the closed segments list, write the updated closed segments list to the storage devices, and write the segment directory for that closed segment to the storage devices; and at the same time that the checkpoint of the main directory is written to the storage devices, write an empty closed segments list to the storage devices.

Claim 22

Dependent Claim 63 words

The article of manufacture as claimed in claim 17 wherein the program code further causes the computer to: partition a portion of the storage devices as a control partition wherein the checkpoint of the main directory, the checkpoint segment status listing and the closed segments list are written to the control partition; and write each segment directory as part of the corresponding segment.

Claim 23

Dependent Claim 33 words

The article of manufacture as claimed in claim 15 wherein each segment includes parity information used to reconstruct the current data blocks of the segment in the event a storage device is damaged.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-04-18	2003-10-18	2004-04-18	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-04-18	2007-10-18	2008-04-18	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-04-18	2011-10-18	2012-04-18	$7700.00	Window Closed / Lapsed

System and method for recovering a directory for a log structured array

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag