US 7,096,341 B1 · System and method for reference count regeneration

Abstract

In a data storage system in which there can be multiple references to a single instance of an object, a method for regenerating the number of references to each object instance. The method includes radix sorting the references to the objects to generate a reference list, counting the references to each unique object and merging the counts with the object descriptions, placing the count of the number of references to each object into the respective object description. The sorting, counting and merging techniques used by this method generate sequential memory access patterns that enable efficient use of low-cost memory and block-oriented memory access interconnect fabric protocols. Furthermore, multiple instances of the sorting, counting and merging processes can be used in parallel to reduce the time required to regenerate the reference counts for a large number of objects.

Claims20

Dependent claims

In a disk-based data storage system, a method for reference count regeneration, the method comprising:

sorting a virtual track table (VTT) to generate a reference list wherein the reference list contains each reference made by an entry in the VTT to an entry in a track number table (TNT);
counting the number of references in the reference list that refer to each unique entry in the TNT to generate a respective reference count list;
and
merging the reference count list with the TNT to generate an updated TNT.

1 more element

In a disk-based data storage system, a method for reference count regeneration, the method comprising:

radix sorting a virtual track table (VTT) to generate a reference list that comprises a plurality of sub-lists wherein each of the sub-lists contains references to a unique range of entries in a track number table (TNT);
counting the references in the reference list that refer to each unique entry in the TNT to generate a respective reference count list;
and
merging the reference count list with the TNT to generate an updated TNT.

1 more element

Dependencies are inferred from the claim text.

System and method for reference count regeneration

Life of this patent

System and method for reference count regeneration

Life of this patent

Abstract

Claims20