Computer file directory system

• US 5,590,320 A
• Filed: 09/14/1994
• Issued: 12/31/1996
• Est. Priority Date: 09/14/1994
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: Smart Storage, Inc. (Dell Technologies Inc.)
• Inventors: Maxey, David
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): PHAM, CUAN
• Application Number:
  US08/306,194
• Time in Patent Office: 839 Days
• Field of Search: 395/600, 395/700, 395/575, 395/650, 395/800, 395/425
• US Class Current: 1/1
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G11B 2220/213 Read-only discs
• CPC Class Codes: G11B 2220/2545 CDs
• CPC Class Codes: G11B 27/002 Programmed access in sequence to a plurality of record carriers or indexed parts, e.g. tracks, thereof, e.g. for editing; transfer of record carriers from magazine G11B15/68, G11B17/10; G11B17/22
• CPC Class Codes: G11B 27/329 on a disc [VTOC]

Abstract

The computer system disclosed herein provides an aggregated directory facility which can encompass the file contents of a large number of high capacity storage devices such as CD ROMS and which enables a user to deal those files as though they were in a single physical volume. An age based caching system facilitates access to the most frequently used portions of the aggregated directory.

Claims

1. In a computer system providing data access to a plurality of individually replaceable physical data volumes each of which contains at least one directory identifying named and timed data files which are contained in the respective volume with the possibility existing that files with the same name may exist on different ones of said volumes with different time indicia;

a method of providing, to a user, an aggregated file listing, said method comprising;

generating from said directories respective volume directory tables containing file names and respective media locations where respective file data may be read, said volume directory tables including also

a pointer identifying any next predecessor in time file with the same name if extant in the plurality of physical data volumes, and

a pointer identifying any next superseding in time file with the same name if extant in the plurality of physical data volumes

generating from said directories a path table which provides, for each directory, a logical access path together with a pointer location containing a pointer identifying at least one volume directory table corresponding to a physical volume where the file data may be read,

whereby said listing may be updated when an available volume is changed by updating the respective volume directory table and the related pointers in other volume directory tables without accessing all directories.

2. A computer implemented method of aggregating directory listings from a succession of individually replaceable data volumes having respective designations, said method comprising:

providing a path table data structure for holding entries for respective volume designations;

for each new data volume, generating a volume directory table;

for each directory in each new volume in succession, performing the steps of;

searching the path table for an existing entry matching the designation of the current volume directory

if no match is found, making a new entry in the path table corresponding to the current volume directory

if a match is found, adding to the matching existing entry a pointer to the corresponding volume directory table

for each file in the current data volume directory, searching the volume directory tables of matching directory designators for matching file names and,

if matching file names are found, linking the matching file names with pointers identifying a sequence of the files.

3. A computer implemented method for providing access to an aggregated directory listing assembled from a succession of data volumes, said method comprising:

providing a path table data structure for holding entries for respective volume designations;

for each new data volume, generating a volume directory table;

for each directory in each new volume in succession, performing the steps of;

searching the path table for an existing entry matching the designation of the current volume directory

if no match is found, making a new entry in the path table corresponding to the current volume directory

if a match is found, adding to the matching existing entry a pointer to the corresponding volume directory table

for each file in the current data volume directory, searching the volume directory tables of matching directory designators for matching file names and,

if matching file names are found, linking the matching file names with pointers identifying a sequence of the files;

storing said path table data structure and said volume directory tables in a rotating disk memory and having in response to a request for directory data identified by disk location information, hashing that information to obtain an entry location into a list having elements corresponding to cache locations in random access memory, said table including, for each entry location, key data which can be matched to disk location information and age data identifying how recently the corresponding cache location has accessed data in response to a request;

if the key data matches the request, providing the requested data from the corresponding cache location;

if the key data does not match the request, initiating successive entries into said list at successive locations, each of which is separated from the previous location by a predetermined number of locations, and comparing the key data with the request for each entry;

during the succession of entries, storing the identity and age data of the least recently accessed entry position encountered during the succession of entries;

if no match is found within a predetermined succession of said entries, reading the requested data from disk and storing it at the corresponding least recently accessed cache location encountered during the succession of tries.

4. In a computer file system in which file directories are stored in rotating disk memory having relatively long latency, a system for caching portions of said directories in random access memory having relatively short latency, said system comprising:

a cache address list providing a plurality of entry positions corresponding to cache memory locations and, with each position, an age data field representing how recently that position provided cached directory data;

means for hashing disk location data to obtain a corresponding entry position in said list;

means for determining if an entry read from said list corresponds to a given file name;

means for reading, from said list, an entry based on given disk location data and submitting the entry read to said determining means;

means operative, if an entry read corresponds to the given disk location data, for accessing directory data from the corresponding random access memory cache location, and for updating said age data field,

iterative means operative, if an entry read does not correspond to the given file name, for successively reading from said list at positions each of which is spaced from the last read entry position by a predeterminable number of entry positions along said list, said iterative means being operative to maintain a record identifying which of the successive positions read in response to a given file name held the least recently accessed directory data, together with corresponding age data, said iterative means being operative also, after a predeterminable number of reads from said list, to initiate a read of the requested directory data from rotating memory, to store a corresponding block of said directory information in the random access cache memory location identified by said least recently accessed list position, and to update the corresponding age record.

5. In a computer system having rotating disk memory having relatively long latency and random access memory having relatively short latency, a method of caching selected data from said disk memory into random access memory, said method comprising:

in response to a request for data identified by disk location information, hashing that information to obtain an entry position into a list having elements corresponding to cache locations, said table including, for each entry position, key data which can be matched to disk location information and age data identifying how recently the corresponding cache location has provided data in response to a request;

if the key data matches the request, accessing the requested data from the corresponding cache location;

if the key data does not match the request, initiating successive entries into said list at positions, each of which is separated from the previous position by a predetermined number of positions, and comparing the key data with the request for each entry;

during the succession of entries, storing the identity and age data of the least recently accessed cache location corresponding to the list positions encountered during the succession of entries;

if no match is found within a predetermined succession of said entries, reading the requested data from disk and storing it at the corresponding least recently accessed cache location encountered during the succession of tries.