File system for a plurality of storage classes

Claims

We claim:

1. An apparatus for controlling accesses to data in data files by a plurality of users of a data processing system, the data processing system including internal storage, external storage storing data files, a plurality of access paths between internal storage and external storage, and a file user interface by which the plurality of users request access to data files, the apparatus comprising:

first means, coupled to the file user interface and the internal storage, for allocating the internal storage for temporary storage of current data to be accessed by the plurality of users, for deallocating internal storage from old data stored in the internal storage, and for generating requests for accesses with external storage for transfer of the current data to the allocated internal storage, and of updated old data from the deallocated internal storage; and

second means, coupled to the first means and the external storage and responsive to the requests for accesses, for managing transfers between internal storage and external storage through the plurality of access paths.

2. The apparatus of claim 1, wherein the second means includes:

logical mapping means, responsive to the requests for accesses to external storage, for assigning a logical address to data subject of each access, and

external mapping means, responsive to the logical address, for mapping the logical address to external storage and carrying out the access subject of the request with external storage.

3. The apparatus of claim 2, wherein there is a plurality of physical storage classes characterized by prespecified parameters that map the logical address of a data file subject of the access to locations in external memory, and the external mapping means includes:

means, responsive to the logical address, for identifying one of the plurality of storage classes; and

means, responsive to the identified storage class, for carrying out the access with the locations in external memory to which the prespecified parameters map data files in the identified storage class.

4. The apparatus of claim 3, wherein the second means further includes:

means, responsive to the identified storage class, for generating error codes for data subject of an access for transfer of data from internal storage to external storage; and

means, responsive to the identified storage class, for detecting and correcting errors in data subject of an access for transfer of data from external storage to internal storage.

5. The apparatus of claim 3, wherein storage classes in a subset of the plurality of storage classes are characterized by parameters specifying a cell of data, the cell including a plurality of local cells that may be accessed across a plurality of access paths in parallel, a cell of data being specified by a first parameter W defining a number of access paths to corresponding local cells of data for parallel access to a cell, wherein W local cells define a cell, and a second parameter D defining a number of blocks of data from the data files in the storage class within each local cell.

6. The apparatus of claim 5, wherein a block of data is a basic unit of transfer across an access path between external storage and internal storage, and there is at least one block of data in each local cell.

7. The apparatus of claim 5, wherein a block of data is a basic unit of transfer across an access path between external storage and internal storage, and storage classes in a subset of the plurality of storage classes are each further characterized by a reliability parameter that specifies an error recovery algorithm, and the external mapping means further includes:

means, responsive to the reliability parameter, for generating error codes for data subject of an access for transfer of data from internal storage to external storage; and

means, responsive to the reliability parameters, for detecting and correcting errors in data subject of an access for transfer of data from external storage to internal storage.

8. The apparatus of claim 5, wherein a block of data is a basic unit of transfer across an access path between external storage and internal storage, and storage classes in a subset of the plurality of storage classes are each further characterized by a reliability parameter that specifies one of a plurality of error recovery algorithms, and the external mapping means further includes:

means, responsive to the reliability parameter, for implementing the error recovery algorithm.

9. The apparatus of claim 8, wherein one of the plurality of error recovery algorithms provides for replication of local cells of data subject of an access for transfer of data from internal storage to external storage, and for storage of replicated local cells in external storage across independent access paths in parallel, and for selection of a best one of replicated local cells of data subject of an access for transfer of data from external storage to internal storage.

10. The apparatus of claim 8, wherein one of the plurality of error recovery algorithms provides for generation of an error code for each cell, and storage of the error code to a local cell within the cell in external storage in parallel with storage of the data subject of an access for transfer of data from internal storage to external storage; and for detection and correction of errors in data subject of an access for transfer of data from external storage to internal storage.

11. The apparatus of claim 8, wherein the error code comprises bitwise parity over the local cells of data within the cell.

12. The apparatus claim 8, wherein for a local cell including N bits, the error code comprises N.times.N bit code, where M is a number greater than one, stored in M local cells within the cell.

13. The apparatus of claim 1, wherein the apparatus further includes:

means, coupled to the first means, for specifying dependencies by users on locations in the internal storage allocated to the plurality of users and wherein said first means is responsive to the specified dependencies in allocating and deallocating the internal storage.

14. The apparatus of claim 13, wherein the dependencies specified by the means for specifying are programmable through the data processing system for global balancing of the allocation and deallocation of internal storage for the plurality of users.

15. The apparatus of claim 13, wherein the first means includes:

means, responsive to the dependencies, for locating, journaling and releasing locations to allocate and deallocate the locations in internal storage for the plurality of users.

16. The apparatus of claim 1, wherein there is a plurality of physical storage classes characterized by prespecified parameters that map data files subject of accesses to locations in external memory, and the second means includes:

means, responsive to requests for accesses, for identifying one of the plurality of storage classes assigned to a data file subject of an access; and

means, responsive to the identified storage class, for carrying out the access with the locations in external memory to which the prespecified parameters map data files in the identified storage class.

17. The apparatus of claim 16, further including:

means, coupled to the second means, for assigning data files to storage classes.

18. The apparatus of claim 17, further including means for programming the means for assigning for dynamic allocation of external memory.

19. The apparatus of claim 1, wherein the second means includes means, responsive to a single request for access with external storage, for carrying out the access subject of the request across a subset of the plurality of access paths in parallel.

20. The apparatus of claim 1, wherein there is a plurality of physical storage classes characterized by prespecified parameters that map the data file subject of the access to locations in external memory, and the second means includes:

means, responsive to a request for access with external storage, for identifying one of the plurality of storage classes assigned to a data file subject of request for access; and

means, responsive to an identified storage class that maps a data file to a plurality of locations accessible through a subset of the plurality of access paths, for carrying out the access through the subset of the plurality of access paths in parallel.

21. The apparatus of claim 1, wherein there is a plurality of the first means and a plurality of the second means, to support continuous operation in the event of a single point of failure.

22. The apparatus of claim 1, wherein the external storage includes a plurality of physical storage devices, and the second means includes:

means, independent of the first means, for carrying out transfer of data from data files stored in a first device to a second device in the plurality of physical storage devices.

23. The apparatus of claim 20, wherein the second means further includes:

means, independent of the first means, for carrying out transfer of data in data files assigned to a first storage class from locations identified in the first storage class to locations identified in a second storage class in the plurality of storage classes.

24. An apparatus for controlling access to data in data files by a plurality of users of a data processing system, the data processing system including internal storage, external storage, a plurality of access paths between internal storage and external storage, and a file user interface by which the plurality of users requests access to data files, wherein there is a plurality of physical storage classes characterized by prespecified parameters that map a data file subject of an access to locations in external memory, the apparatus comprising:

first means, coupled to the file user interface and the internal storage, for allocating the internal storage for temporary storage of current data in the data files to be accessed by the plurality of users, for deallocating internal storage from old data stored in the internal storage, and for generating requests for accesses with external storage for transfer of current data to allocated internal storage, and of updated old data from deallocated internal storage; and

means, coupled to the first means, for specifying dependencies by users on locations in the internal storage allocated to the plurality of users, wherein the first means is responsive to the specified dependencies in allocating and deallocating the internal storage;

logical mapping means, responsive to the requests for accesses with external storage, for assigning a logical address to data subject of each access;

external mapping means, responsive to the logical address, for identifying one of the plurality of storage classes; and

means, responsive to the identified storage class, for carrying out the access with the appropriate locations in external memory through a subset of the plurality of access paths.

25. The apparatus of claim 24, wherein the first means includes:

means, responsive to the dependencies, for locating, journaling and releasing locations to allocate and deallocate the locations in internal storage for the plurality of users.

26. The apparatus of claim 24, wherein the dependencies specified by the means for specifying are programmable through the data processing system for global balancing of the allocation and deallocation of internal storage for the plurality of users.

27. The apparatus of claim 24, wherein the means for carrying out the access is responsive to a single request for access with external storage to transfer data across a subset of the plurality of access paths in parallel.

28. The apparatus of claim 27, wherein storage classes in a subset of the plurality of storage classes are characterized by parameters specifying a cell of data, the cell including a plurality of local cells that may be accessed across a plurality of access paths in parallel, a cell of data being specified by a first parameter W defining a number of access paths to corresponding local cells of data for parallel access to a cell, wherein W local cells define a cell, and a second parameter D defining a number of blocks of data in the data files in the storage class within each local cell.

29. The apparatus of claim 28, wherein a block of data is a basic unit of transfer across an access path between external storage and internal storage, and there is at least one block of data in each local cell.

30. The apparatus of claim 24, wherein the means for carrying out accesses with external storage further includes:

means, responsive to the identified storage class, for generating error codes for data subject of an access for transfer of data from internal storage to external storage; and

means, responsive to the identified storage class, for detecting and correcting errors in data subject of an access for transfer of data from external storage to internal storage.

31. The apparatus of claim 28, wherein a block of data is a basic unit of transfer across an access path between external storage and internal storage, and storage classes in a subset of the plurality of storage classes are each further characterized by a reliability parameter that specifies an error recovery algorithm, and the means for carrying out accesses with external storage further includes:

means, responsive to the reliability parameter, for generating error codes for data subject of an access for transfer of data from internal storage to external storage; and

means, responsive to the reliability parameter, for detecting and correcting errors in data subject of an access for transfer of data from external storage to internal storage.

32. The apparatus of claim 28, wherein a block of data is a basic unit of transfer across an access path between external storage and internal storage, and storage classes in a subset of the plurality of storage classes are each further characterized by a reliability parameter that specifies one of a plurality of error recovery algorithms, and the means for carrying out accesses with external storage further includes:

means, responsive to the reliability parameter, for implementing the error recovery algorithm.

33. The apparatus of claim 32, wherein one of the plurality of error recovery algorithms provides for replication of local cells of data subject of an access for transfer of data from internal storage to external storage, and for storage of replicated local cells in external storage across independent access paths in parallel, and for selection of a best one of replicated local cells of data subject of an access for transfer of data from external storage to internal storage.

34. The apparatus of claim 32, wherein one of the plurality of error recovery algorithms provides for generation of an error code for each cell, and storage of the error code to a local cell within the cell in external storage in parallel with storage of the data subject of an access for transfer of data from internal storage to external storage; and for detection and correction of errors in data subject of an access for transfer of data from external storage to internal storage.

35. The apparatus of claim 32, wherein the error code comprises bitwise parity over the local cells of data within the cell.

36. The apparatus of claim 32, wherein for a local cell including N bits, the error code comprises a N.times.N bit code, where M is a number greater than one, stored in M local cells within the cell.

37. An apparatus in communication with a data processing system for storing a data file for sequential transfers to the data processing system, the data file including a plurality of local cells, each local cell including at least one block of data, wherein a block is a basic unit of transfer between the data processing system and the apparatus, the apparatus comprising:

a plurality of storage means for storing data;

a plurality of logical input/output paths P.sub.n, for n equal to 1 through N, each path coupled to a subset of the plurality of storage means and to the data processing system, so that local cells of data may be transmitted in parallel through the N paths between the data processing system and the plurality of storage means; and wherein

the local cells in the data file are stored in the plurality of storage means in a sequence of local cells LC.sub.i for i equal to 1 to X, and wherein local cell LC.sub.i is stored in a storage P.sub.n+k means coupled to path P.sub.n ; and local cell LC.sub.i+l is stored in a storage means coupled to path P.sub.n+k, where k is not equal to zero.

38. The apparatus of claim 37, wherein the data file includes S cells of data, each cells including W local cells, where W is less than or equal to N and S equals X/W rounded to the next higher integer, each cell including at least one local cell storing an error correction code for the cell, and all local cells in a given cell stored in storage means coupled to different paths.

39. The apparatus of claim 38, wherein the error correction code for a given cell comprises a bitwise exclusive-OR of all local cells in the cell, except the error correction code.

40. The apparatus of claim 39, wherein the local cells in the data file containing the error correction codes are stored in storage means coupled to a single path.

41. The apparatus of claim 39, wherein the local cell in the data file containing the error correction code for cell j, is stored in a storage means coupled to path P(((j-1)modW)+1).

42. The apparatus of claim 38, wherein each local cell includes L bits, and the error correction code comprises a L.times.M bit code, where M is an integer greater than one.

43. An apparatus in communication with a data processing system for storing a data file for sequential transfers to the data processing system, the data file including a plurality of local cells, each local cell including at least one block of data that can be manipulated by the data processing system as a unit for access to the data file, the apparatus comprising:

a plurality of storage means for storing data;

a number W of logical input/output paths, path 1 through path W, each path coupled to a subset of the plurality of storage means and to the data processing system, so that blocks of data may be transmitted in parallel through the W paths between the data processing system and the plurality of storage means; and wherein

the data file is stored in the plurality of storage means in a sequence of X local cells, and local cell 1 in the sequence is stored in a storage means coupled to path 1, local cell 2 is stored in a storage means coupled to path 2, local cell W is stored in a storage means coupled to Path W, local cell W+1 is stored in a storage means coupled to path 1, local cell W+2 is stored in a storage means coupled to path 2, local cell 2W is coupled to a storage means coupled to path W, and local cell X is stored in a storage means coupled to path (((X-1)modW)+1).

44. The apparatus of claim 43, wherein the data file includes S cells of data, each cell including up to W local cells, where S equals X/W rounded to the next higher integer, each cell including at least one local cell storing an error correction code for the cell.

45. The apparatus of claim 44, wherein the error correction code for a given cell comprises a bitwise exclusive-OR of all local cells in the cell, except, for the local cell storing the error correction code.

46. The apparatus of claim 45, wherein the local cells in the data file containing the error correction codes are stored in storage means coupled to a single path.

47. The apparatus of claim 45, wherein the local cell in the data file containing the error correction code for cell j, is stored in a storage means coupled to path P(((j-1)modW)+1).

48. The apparatus of claim 44, wherein each local cell includes L bits, and the error correction code comprises a L.times.M bit code, where M is an integer greater than one.

49. An apparatus in communication with a data processing system for storing a data file for sequential transfers to the data processing system, the data file including a sequence of local cells LC.sub.i for i equal to 1 through X, each local cell including at least one block of data that can be manipulated as a unit by the data processing system for access to the data file, the apparatus comprising:

a plurality of storage means for storing data;

a plurality of logical input/output paths P.sub.n, n equal to 1 through W, each path coupled to a subset of the plurality of storage means and to the data processing system, so that blocks of data may be transmitted in parallel through the plurality of paths between the data processing system and the plurality of storage means; and

means, coupled to the plurality of paths, for allocating the sequence of local cells LC.sub.i, for i equal to 1 to X, to at least a subset of the plurality of storage means, so that local cell LC.sub.i is stored in a storage means coupled to path P.sub.n, local cell LC.sub.i+1 is stored in a storage means coupled to path P.sub.n+k P.sub.k, where k is not equal to zero.

50. The apparatus of claim 49, wherein local cell LC.sub.i is stored in a storage means coupled to path P.sub.n, and n is equal to (((i-1)modW)+1), for i equal to 1 to X.

51. An apparatus in communication with a data processing system for storing a data file for sequential transfers to the data processing system, the data file including a sequence of local cells LC.sub.i, for i equal to 1 through X, each local cell including at least one block of data that can be manipulated as a unit through the data processing system by users of the data file, the apparatus comprising:

a plurality of storage means for storing data;

a plurality of logical input/output paths P.sub.n, for n equal to 1 through W, each path coupled to a subset of the plurality of storage means and to the data processing system, so that blocks of data may be transmitted in parallel through the plurality of paths between the data processing system and the plurality of storage means;

means, coupled to the plurality and paths to receive the blocks of data, for generating an error correction code ECC.sub.s for each set s of E local cells, where s goes from 1 to S, and S is equal to X/E rounded to the next larger integer; and

means, coupled to the plurality of paths and to the means for generating an error correction code ECC.sub.s, for mapping the sequence of local cells LC.sub.i, for i equal to 1 to X, and error correction codes ECC.sub.s, for s equal to 1 to S, to at least a subset of the plurality of storage means, so that all local cells in the set s, and error correction code ECC.sub.s, define a cell, and local cells in the cell and each are stored in storage means coupled to different paths.

52. The apparatus of claim 51, wherein the error correction codes ECC.sub.s are generated by taking the bitwise exclusive-OR of all local cells of data in the cell.

53. The apparatus of claim 52, wherein the means for mapping maps all error correction codes to storage means coupled to a single path.

54. The apparatus of claim 52, wherein the means for mapping maps error correction code ECC.sub.s to a storage means coupled to path P.sub.(((s-1)modW)+1)

55. The apparatus of claim 51, wherein the error correction codes are multiple bit Hamming codes.

56. The apparatus of claim 51, wherein the error correction code ECC.sub.s has a size equal to M local cells, and E is equal to W minus M.

57. An apparatus in communication with a data processing system for storing a plurality of data files for sequential transfers to the data processing system, each data file including a sequence of local cells LC.sub.i, for i equal to 1 through X, where X is a parameter associated with each data file, each local cell including at least one block of data that can be manipulated as a unit through the data processing system by users of the data file, the apparatus comprising:

a plurality of storage means for storing data;

a plurality of logical input/output paths P.sub.n, n equal to 1 through N, each path coupled to a subset of the plurality of storage means and to the data processing system, so that data may be transmitted in parallel through the plurality of paths between the data processing system and the plurality of storage means; and

means, coupled to the plurality of paths and to the data processing system, and responsive to parameters associated with each data file by the data processing system, for mapping the sequence of local cells LC.sub.i, for i equal to 1 to X, for each data file to at least a subset of the plurality of storage means, so that local cell LC.sub.i of a given data file is stored in a storage means coupled to path P.sub.n, and local cell LC.sub.i+1 of the given data file is stored in a storage means coupled to path P.sub.k, where k is not equal to n.

58. The apparatus of claim 57, wherein the number of blocks per local cell is an additional parameter associated with each data file by the data processing system, and to which the means for mapping is responsive.

59. The apparatus of claim 57, wherein a number W of local cells equal a cell, and the number W is an additional parameter associated with each data file by the data processing system.

60. The apparatus of claim 59, wherein local cell LC.sub.i is stored in a storage means coupled to P.sub.n, and n is equal to (((i-1)mod W)+1), for i equal to 1 to X.

61. An apparatus in communication with a data processing system for storing a plurality of data files for sequential transfers to the data processing system, each data file including a sequence of local cells LC.sub.i, for i equal to 1 through X, where X is a parameter associated with each data file, N local cells equal a cell, and each local cell includes at least one block of data that can be manipulated as a unit through the data processing system by users of the data file, the apparatus comprising:

a plurality of storage means for storing data;

a plurality of logical input/output paths P.sub.n, n equal to 1 through N, each path coupled to a subset of the plurality of storage means and to the data processing system, so that data may be transmitted in parallel through the plurality of paths between the data processing system and the plurality of storage means;

means, coupled to the plurality of paths and the data processing system to receive the blocks of data, for generating and error correction code ECC.sub.s, for storage in Z local cells, for a set s of E local cells of data, where s goes from 1 to S, and S equal to X/E rounded to the next larger integer, and N is equal to Z+E; and

means, coupled to the plurality of paths and to the data processing system, and responsive to the parameters associated with each data file by the data processing system, for mapping the sequence of local cells LC.sub.i, for i equal to 1 to X, and the error correction codes ECC.sub.s, for s equal to 1 to S, for each data file to a subset of the plurality of storage means, so that all local cells of data in a given set and the local cells or error correction codes for the given set equal a cell of W local cells and each local cell in a cell is stored in storage means coupled to different paths.

62. The apparatus of claim 61, wherein the number of blocks per local cell is an additional parameter associated with each data file by the data processing system, and to which the means for mapping is responsive.

63. The apparatus of claim 61, wherein W is a parameter associated with each data file by the data processing system.

64. The apparatus of claim 61, wherein there is a plurality of types or error correction codes, and the type of error correction code is a parameter associated with each data file by the data processing system.

65. The apparatus of claim 64, wherein a first type of error correction code is generated by taking the bitwise exclusive-OR of all local cells in the set.

66. The apparatus of claim 64, wherein a first type of error correction code is generated by taking the bitwise exclusive-OR of all local cells in the set, and the means for mapping maps all error correction codes to storage means coupled to a single path.

67. The apparatus of claim 64, wherein a second type of error correction code is generated by taking the bitwise exclusive-OR or all local cells in the set, and the means for mapping maps error correction code ECC.sub.s to a storage means coupled to path P.sub.(((s-1)modW)+1).

68. The apparatus of claim 64, wherein one type of the error correction codes is a multiple bit Hamming code generated over all local cells in the set.

BACKGROUND OF THE INVENTION

1. Limited Copyright Waiver

A portion of the disclosure of this patent document contains material to which the claim of copyright protection is made. The copyright owner has no objection to the facsimile reproduction by any person of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.

2. Field of the Invention

The present invention relates to systems providing an interface and establishing access paths between users of data in a data processing system and facilities storing such data. In particular, the present invention provides a file system adaptable to optimize use of a plurality of access paths and available storage hardware to meet operational requirements of the system.

3. Description of Related Art

Computer systems are being developed in which the amount of data to be manipulated by the system is immense. For instance, data storage systems have been proposed that are capable of handling amounts of data on the order of exabytes, spread across hundreds of direct access storage devices (DASDs). Individual files for such systems have been proposed to be as high as ten gigabytes (10.sup.10 bytes) Such large storage systems should be very reliable, since restoring an entire storage system after a crash could take many hours or days. In addition, these storage systems should sustain very high data transfer rates to allow for efficient use of the data. Further, it is desirable that there be no single point of failure which could cause such a large data system to go out of service. The requirements for size, speed and reliability of such data systems will continue to keep pace with increases in capacity of supercomputers at the high end, and with increasing numbers of large data storage systems being used by slower computers.

Prior art file systems which provide an interface between users of data, buffers in the computer system and external storage to the computer system, have operated by establishing a single access path for any individual request by a user to a file. This is absolutely reasonable as long as there are very few devices storing the data. But, in configurations with many storage devices and many independent access paths through which the data may be transferred in parallel in response to each individual request, the one access path per request limitation of system control programs greatly restricts the response time for a given task requiring transfer of data between external to internal storage.

Prior art file systems can be characterized with reference to the diagram shown in FIG. 1. The computer system in which the prior art file system runs would include a plurality of application programs A, corresponding to users of data. Some of the application programs will be part of processing subsystems (SS), such as database drivers and the like. These application programs A, or subsystems, will generate access requests through a user interface I, to the buffer space in the computer. If data required by a given transaction is not located in the buffer space, then the system control program SCP establishes an access path through device drivers by which the required data can be retrieved from non-volatile storage.

Management of the buffer space is a major operational bottleneck for data processing systems with multiple users and large numbers of data files. In UNIX, the buffer space is managed in a least recently used manner, such that when the buffer space is full, a page is released from the buffer according to a simple algorithm to make space for the current transaction. However, there is no guarantee that the space being released is not critical data for another program running in the system, because all users share the same buffer pool. Also, when very large migration of data takes place, the buffer pool can be quickly depleted for use by the migration transaction, effectively locking out other users of the system during the migration.

In other operating systems, such as MVS, the buffer space is allocated to a group of buffer pools. Each buffer pool is managed essentially independently by the users or subsystems accessing the buffer space. By dividing up the buffer space among users, better control over availability of pages of data can be exercised, such as required in transaction control systems that perform a journal function for each transaction. However, by statically allocating buffer space among a plurality of users, inefficiencies arise that influence the overall performance of the data processing system. For instance, a given subsystem may be active during a particular time of day and inactive during another time. However, without action on the part of the subsystem, its buffer space will remain allocated throughout the day leaving a large amount of buffer space unavailable for use.

The problem of efficiently allocating buffer space among users in MVS-based systems is a major operational problem that consumes a great deal of resources and renders operation of the data processing system extremely complex to users.

Accordingly, a file system is needed that is capable of exploiting large numbers of access paths, and providing efficient access to files which range in size from a few bytes to hundreds of gigabytes and beyond. The file system must be extended to allow for efficient journaling of transactions and database processing. Also, it is desirable that operation of the file system be convenient and automated and that it be adaptable to emerging storage device technology. Further, it is desirable to provide a file system that will allow continuous access to data concurrently with maintenance, migration and error correction on files being used.

SUMMARY OF THE INVENTION

The present invention provides an apparatus for managing data files for access by a plurality of users of a data processing system that includes internal storage for buffering, external storage, and a file user interface by which the plurality of users request access to data files. The apparatus comprises a first level, coupled to the file user interface and the internal storage for allocating the internal storage for temporary storage of data to be accessed by the plurality of users, and generating requests for transactions with external storage in support of such allocations. A second level is coupled to the first level and the external storage and responds to the request for transactions with the external storage for managing the transactions for storage of data to, and retrieval of data from, the external storage.

The system may include large numbers of storage devices and access paths through which data can be transferred between the internal storage and the storage devices. In such a system, the second level defines a plurality of physical storage classes which are characterized by pre-specified parameters that allocate data files subject of transactions to locations in external memory. In response to requests for transactions, the second level identifies one of the plurality of storage classes assigned to the data file subject of the transaction and carries out the transaction with the appropriate locations in external memory.

At least one of the plurality of storage classes provides for utilization of a plurality of access paths in parallel for transactions involving data files assigned to such storage class. Further, at least one pre-specified parameter for storage classes identifies a level of reliability desired for the subject data files. The second level in response to that parameter, generates error correction codes, or performs duplication for mirroring-type reliability systems, and allocates the mirrored data or generated error correction codes to locations in external memory. For transactions retrieving data from allocated data files, the second level includes means for detecting and correcting errors.

The first level includes a means such as dependency graphs for specifying dependencies for locations in the internal storage allocated among the plurality of users. In response to the dependencies, the first level provides for locating, journaling and releasing locations in a manner transparent to the plurality of users. By specifying dependencies in an appropriate manner, global balancing of the internal storage can be achieved.

By providing for dynamic allocation of storage classes, along with error correction that is transparent to users, the file system will exhibit a high degree of fault tolerance while assuring continuous operation during error correction transactions and transactions that may require re-allocation of data from one storage device to another.

In a preferred system, one of the storage classes will provide for record level striping. Thus, according to another aspect, the present invention provides an efficient method of performing data input-output within a computer system consisting of parametric record-level striping, to achieve high data transfer rates, which in combination with error correction codes and recovery methods, also achieves improved data availability and reliability for very large file systems. According to this aspect, the present invention can be characterized as an apparatus for storing a data file which includes a sequence of local cells LC.sub.i for i equal to one through X. Each local cell in the file includes at least one basic unit of transfer (block) by users of the data file. The apparatus comprises a plurality of storage units for storing data, such as magnetic tapes, magnetic disks, or any other non-volatile storage device. A plurality of input-output (I/O) paths, P.sub.n, for n equal to 1 through N, is included. Each path in the plurality is coupled with a subset of the plurality of storage units, so that blocks of data can be transmitted in parallel through the plurality of paths to and from the plurality of storage units. A control unit is coupled to the plurality of paths, for allocating the sequence of local cells LC.sub.i, to at least a subset of the plurality of storage units, so that local cell LC.sub.i is stored in a storage unit coupled to path P.sub.n, and local cell LC.sub.i+1 is stored in a storage unit coupled to path P.sub.k, where k is not equal to n.

According to one embodiment of the present invention, the path on which local cell LC.sub.j is stored, is equal to (((j-1)modN)+1); an N local cell define a cell that can be accessed through the N access paths in parallel. Alternatively, parametric selection of different methods of assignment of local cells across the paths, can be made on the same set of storage units, so that the speed of individual devices, size of cells and local cells for given files and the amount of data manipulation by programs using the files can be matched.

According to another aspect of the present invention, for every N-1 local cells in the file, a correction block is generated, consisting of correction codes for the N-1 local cells. By providing an additional path across which correction blocks can be allocated within a data file, corrections of previously uncorrectable errors detected during accesses through a given path, can be made. To increase performance for some file systems, the allocation of error correction blocks can be rotated across the N paths for file systems that will require multiple accesses to the correction blocks. Further, the error correction scheme can be expanded to provide for multiple error correction, using additional paths for correction blocks.

A file system according to the present invention is adaptable to a wide variety of operational requirements. For instance, one storage class can be defined that reflects a standard UNIX file system structure. Of course, a storage class can be defined to meet other existing file system structures as well.

Many applications require high speed sequential processing. One storage class could be defined according to the present invention, that reflects device geometry like tracks and cylinders, in order to take advantage of the highest speed transfer rates of individual devices. Further, by providing a number of access paths in parallel, each path providing maximum transfer speed for devices to which the path attaches, extremely high sequential processing speeds can be achieved.

Operational databases, on the other hand, typically require efficient random access to small objects which are contained within blocks as well as high sequential access speeds for batch processing, copying images and database recovery. By using proper storage class definition, the sequential access can be executed as fast as required. The reliability requirements can be satisfied through proper reliability parameters. Finally, a high random update rate may best use a reliability feature such as mirroring, while a low random update may best use parity-based reliability systems.

Non-operational databases such as CAD/CAM databases are often characterized by large objects comprising several megabytes of data. Using a storage class that could contain an average object in a few cells, would be very beneficial to the performance of such a system.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a file system according to the prior art.

FIG. 2 is a block diagram of a file system encompassing the present invention.

FIG. 3 is a block diagram illustrating data flow through levels of a file system according to the present invention.

FIG. 4 is a diagram illustrating a structure of the levels of the file system according to the present invention.

FIG. 5 is a block diagram of a computer system with a data storage subsystem having a plurality of input-output paths and a large number of physical storage devices.

FIG. 6 is a schematic diagram of a data file according to the present invention.

FIG. 7 is a diagram illustrating the logical disk and available path concepts

FIG. 8 illustrates the logical organization of a data file according to the present invention, without error correction.

FIG. 9 illustrates I