Storage dispersal system based on related, shared data storage space reservation

• US 5,860,132 A
• Filed: 12/19/1996
• Issued: 01/12/1999
• Est. Priority Date: 05/27/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Disney, Howard Alan, Carter, Robert Neil, Vomaska, William Otto, Goldsmith, Kevin Scott
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US08/773,810
• Time in Patent Office: 754 Days
• Field of Search: 711/115, 711/170, 711/171, 711/173, 707/1, 707/200
• US Class Current: 711/170
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0686 Libraries, e.g. tape libraries, jukebox
• CPC Class Codes: G11B 2220/20 Disc-shaped record carriers
• CPC Class Codes: G11B 2220/41 Flat as opposed to hierarchical combination, e.g. library of tapes or discs, CD changer, or groups of record carriers that together store one title
• CPC Class Codes: G11B 2220/90 Tape-like record carriers
• 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/11 by using information not detectable on the record carrier

Abstract

A system and method are provided for dispersing storage of a plurality of related and unrelated data items on a plurality of removable recordable media instances (RMIs). A first storage device is provided for storing a data item on a qualifying related RMI, the qualifying related RMI having one or more related data items stored on it and having sufficient actual storage space remaining for storing the data. A multiplier device is connected to the first storage device for multiplying the actual size of a data item, which is not stored by the first storage device because there is no qualifying related RMI, by a factor greater than one, to produce reserved storage space data which characterizes any other RMI that actually stores the data item. A second storage device, which is responsive to the multiplier device is provided for storing a data item on a qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and unreserved storage space remaining to store the data item and, if there is no qualifying unrelated RMI, then storing the data item on a new RMI the new RMI having no data stored on it. This arrangement provides for shared logical space reservation so that physical proximity of related data items is optimized with respect to a set of RMIs.

Claims

1. A unit for dispersing storage of a plurality of related and unrelated data items on a plurality of removable recordable media instances (RMIs) comprising:

reserving means for reserving storage space for any future related data items on an RMI;

(1) if a related data item is stored on a new RMI, the new RMI having no data item previously stored on it or (2) if the related data item is stored on a qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and unreserved storage space for storing the related data item; and

storing means, coupled to the reserving means, for storing the related data item on a qualifying related RMI, the qualifying related RMI having related data stored on it and having sufficient actual storage space for storing the related data item or, if there is no qualifying related RMI, then storing the related data item on said qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and unreserved storage space remaining to store the related data item or, if there is no qualifying unrelated RMI, then storing the related data item on a new RMI, the new RMI having no data items stored on it.

2. A unit as claimed in claim 1 including the reserving means including means for multiplying the actual size of the data item by a factor greater than one to provide the reserved storage space.

3. A unit as claimed in claim 1 including the storing means storing the data item on the qualifying unrelated RMI which has the least number unrelated collections of data items stored on it if there is more than one qualifying unrelated RMI.

4. A combination, including the unit of claim 1, the combination comprising:

a plurality of RMIs stored in respective locations in a library;

a writing device responsive to the storing means for writing data items to the RMIs; and

transport means responsive to the storing means for transporting selected RMIs between the library and the writing device.

5. A combination as claimed in claim 4 wherein the unit of claim 1 is a programmed digital device.

6. A combination as claimed in claim 4 including:

a plurality of workstations for generating data items D and for generating data fields which identify each data item D by subject matter (s) and actual size (a) required to store the data item D on a RMI, each workstation being connected to the reserving means and the storing means;

a read device connected to the workstations for reading data items D on the RMIs; and

said transport device also being responsive to the workstations for transporting selected RMIs between the library and the RMI reading device.

7. A combination as claimed in claim 6 wherein the reserving means include means for multiplying the actual size (a) data field of the data item D by a factor greater than one to provide the reserved storage space (r) data field.

8. A combination as claimed in claim 7 wherein the storing means stores the data item on the qualifying unrelated RMI which has the least number of unrelated collections of data items stored on it if there are more than one qualifying unrelated RMI.

9. A unit as claimed in claim 1 wherein the storage space reserved on said RMI is available for storing any additional data item related to any data item already stored on said RMI.

10. A unit as claimed in claim 9 including the reserving means including means for multiplying the actual size of the data item by a factor greater than one to provide the reserved storage space.

11. A unit as claimed in claim 9 including the storing means storing the data item on the qualifying unrelated RMI which has the least number unrelated collections of data items stored on it if there is more than one qualifying unrelated RMI.

12. A unit as claimed in claim 9 including the the unit of claim 1, the combination comprising:

a plurality of RMIs stored in respective locations in a library;

a writing device responsive to the storing means for writing data items to the RMIs; and

transport means responsive to the storing means for transporting selected RMIs between the library and the writing device.

13. A unit as claimed in claim 12 including:

a plurality of workstations for generating data items D and for generating data fields which identify each data item D by subject matter (s) and actual size (a) required to store the data item D on a RMI, each workstation being connected to the reserving means and the storing means;

a read device connected to the workstations for reading data items D on the RMIs; and

said transport device also being responsive to the workstations for transporting selected RMIs

between the library and the RMI reading device.

14. A unit as claimed in claim 13 wherein the reserving means include means for multiplying the actual size (a) data field of the data item D by a factor greater than one to provide the reserved storage space (r) data field.

18. A combination as claimed in claim 11 wherein the unit of claim 15 is a programmed digital device.

19. A combination as claimed in claim 11 including:

a plurality of workstations which generate data items D and data fields which identify each data item by subject matter (s) and actual size (a) required to store the data item on a RMI, each workstation being connected to the first and second storage means;

a read device connected to the workstations for reading data items on the RMIs; and

said transport device also being responsive to the workstations for transporting selected RMIs between the library and the RMI reading device.

20. A combination as claimed in claim 19 wherein the second storage means stores the data item on the qualifying unrelated RMI which has the least number of unrelated collections of data items stored on it if there is more than one qualifying unrelated RMI.

15. A unit for dispersing storage of a plurality of related and unrelated data items on a plurality of removable recordable media instances (RMIs) comprising:

first storage means for storing a data item on a qualifying related RMI, the qualifying related RMI having one or more related data items stored on it and having sufficient actual storage space remaining for storing the data item;

multiplier means, connected to the first storage means, for multiplying the actual size of a data item, which is not stored by the first storage means because there is no qualifying related RMI, by a factor greater than one, to produce reserved storage space data which is available for storing any additional data items related to said data item or to any unrelated data item previously stored on an RMI with said data item; and

second storage means responsive to the multiplier means for storing a data item on a qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and sufficient unreserved storage space remaining equal to or greater than said reserved storage space data to store the data item and, if there is no qualifying related RMI, then storing the data item on a new RMI, the new RMI having no data stored on it.

16. A unit as claimed in claim 15 wherein the second storage means stores the data item on the qualifying unrelated RMI which has the least number of unrelated collections of data items stored on it if there are more than one qualifying unrelated RMI.

17. A combination, including the unit of claim 15, the combination comprising:

a plurality of RMIs stored in respective library locations;

a writing device responsive to the first and second storage means for writing data items to the RMIs; and

transport means responsive to the first and second storage means for transporting selected RMIs between the library and the RMI writing device.

21. A unit for dispersing storage of a plurality of data items D across a plurality of removable recordable media instances (RMIs) comprising:

each data item D being part of a controlled data item D.sub.(s,a) where (s) is a data field indicating the subject matter of the data item and (a) is a data field indicating the actual amount of storage space needed on a RMI to store the data item;

each RMI being designated I_n(s'"'"',a'"'"',r'"'"') if the RMI is partially full by having one or more data items stored on it and by I.sub.(N+1) if the RMI is the N+1 RMI and is new because no data item has been stored on it, where n is the number of the RMI for all values of n from 1 to N, (s'"'"') is data indicating one or more subject matters of one or more data items stored on the nth RMI, (a'"'"') is a data field indicating actual storage space remaining on the nth RMI and (r'"'"') is a data field indicating the reserved storage space remaining on the nth RMI;

multiplier means for receiving actual size (a) data field of a controlled data item D.sub.(s,a) and multiplying it times a factor (t) greater than one to produce a data field representing a reserved size (r) of the controlled data item D.sub.(s,a), thereby providing a controlled data item D.sub.(s,r) which is the same as controlled data item D.sub.(s,a) except its data field size has been modified from actual size (a) data field to reserved size (r) data field;

RMI directory means for receiving subject matter data (s) field, actual size data (a) field and reserved size data (r) field of data items D stored on RMIs (I_n and I_N) for providing an updated RMI data field listing (p) of I_n(s'"'"',a'"'"',r'"'"') for all values of n from n=1 to n=N where for each RMI corresponding to I_n(s'"'"',a'"'"',r'"'"') an updated reserved size data r'"'"' is reserved storage reserved on said RMI corresponding to a data item stored on said RMI or a pool of combined reserved storages reserved on said RMI for said data item and one or more unrelated data items already stored on said RMI so that the updated reserved size data r'"'"' corresponds to reserved storage on said RMI which is available for storing any additional data items related to any data item already stored on the RMI;

first comparator and storage means responsive to the data listing (p) in the RMI directory means for receiving a controlled data item D.sub.(s,a) for storing the data item D part of the controlled data item D.sub.(s,a) on any reserved space and unreserved space, if needed, of a qualifying related RMI (I_n), the subject matter data (s) of controlled labeled data item D.sub.(s,a) comparing with subject matter data (s'"'"') of the qualifying related RMI (I_n) within the RMI data field listing (p) and the actual size data (a) of the controlled data item being equal to or less than the actual storage space data (a'"'"') remaining on the qualifying related RMI, and for indicating any data part D of controlled data item D.sub.(s,a) which is not stored because there is no qualifying related RMI;

the RMI directory means being connected to the first comparator and storage means for receiving (s) and (a) data fields of corresponding data items D stored on the RMIs (I_n) to recalculate the (s'"'"') and (a'"'"') data fields for the RMIs (I_n);

the multiplier means being responsive to the first comparator and storage means for receiving said actual size data (a) field of any controlled data item D.sub.(s,a) when the data portion D thereof is not stored by the first comparator means because there is no qualifying related RMI;

second comparator and storage means responsive to the data listing (p) in the RMI directory and the multiplier means for storing a data item D part of a controlled data item D.sub.(s,r) on a qualifying unrelated RMI (I_n), the reserved size (r) of the controlled data item D.sub.(s,r) being less than or equal to the remaining actual storage size (a'"'"') of the qualifying unrelated RMI and less than or equal to the remaining reserved storage size (r'"'"') of the qualifying unrelated RMI (I_n) and, if there is no qualifying unrelated RMI then storing the data item D part of the controlled data item D.sub.(s,r) on a new RMI (I_N+1), the new RMI having no data item D previously stored on it; and

the RMI directory means being connected to the second comparator means for receiving the (s), (a) and the (r) data of corresponding data items D stored on the RMIs (I_n and I_N+1) to recalculate the (s'"'"'), (a'"'"'), and (r'"'"') data for the RMIs (I_n).

22. A unit as claimed in claim 21 including the second comparator and storage means storing the data D corresponding to labeled data item D.sub.(s,r) on the qualifying unrelated RMI (I_n) which has the least number of unrelated collections of data items stored on it and, if there is more than one qualifying, unrelated RMI, then storing the data on the qualifying unrelated RMI which has the least n in the set n=1 to n=N.

23. A unit as claimed in claim 21 including the multiplier means multiplying the actual size data (a) field of the labeled data item (D_s,a) times a factor (t) which is in the range of 1 to some finite number.

24. A unit as claimed in claim 21 wherein N is an integer greater than one.

25. A combination including the unit of claim 21, the combination comprising:

a plurality of RMIs stored in respective locations in a library;

a writing device, responsive to the first and second comparator and storage means, for writing data items to the RMIs; and

transport means, responsive to the first and second comparator and storage means, for transporting selected RMIs between the library and the RMI writing device.

26. A combination as claimed in claim 25 wherein the unit of claim 21 is a programmed digital device.

27. A combination as claimed in claim 25 including:

a plurality of workstations for generating data items D and data fields which identify each data item D by subject matter (s) and actual size (a) required to store the data item D on a RMI, each workstation being connected to the first and second storing storage means;

a RMI read device connected to each workstation for reading data items on the RMIs; and

said transport device also being responsive to the workstations for transporting selected RMIs between the library and the RMI reading device.

28. A combination as claimed in claim 27 including:

the second comparator and storage means storing the data D part of controlled data item D.sub.(s,r) on the qualifying unrelated RMI (I_n) which has the least number of unrelated collections of data items stored on it and, if there is more than one such qualifying unrelated RMI, then storing the data on the qualifying unrelated RMI which has the least n in the set n=1 to n=N.

29. A combination as claimed in claim 28 including the multiplier means multiplying the actual size data (a) field of the controlled data item (D_s,a) time a factor (t) which is in the range of 1 to some finite number.

30. A combination as claimed in claim 29 wherein N is an integer greater than one.

31. A method of dispersing storage of a plurality of related and unrelated data items on a plurality of removable recordable media instances (RMIs) comprising the steps of:

reserving storage space for any future related data items on a RMI;

(1) if a related data item is stored on a new RMI, the new RMI having no data item previously stored on it or (2) if the related data item is stored on a qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and unreserved storage space for storing the related data item;

storing the related data item on a qualifying related RMI, the qualifying related RMI having related data stored on it and having sufficient actual storage space for storing the related data item or, if there is no qualifying related RMI, then storing the related data item on said qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and unreserved storage space remaining to store the related data item or, if there is no qualifying unrelated RMI, then storing the related data item on a new RMI, the new RMI having no data item stored on it.

32. A method as claimed in claim 31 including the step of:

when storing the data item on the qualifying unrelated RMI storing the data item on the qualifying unrelated RMI which has the least number of unrelated collections of data items stored on it if there is more than one qualifying unrelated RMI.

33. A method of dispersing storage of a plurality of related and unrelated data items on a plurality of removable recordable media instances (RMIs) comprising the steps of:

storing a data item on a qualifying related RMI, the qualifying related RMI having one or more related data items stored on it and having sufficient actual storage space remaining for storing the data item;

multiplying the actual size of a data item, which is not stored by the first storage means because there is no qualifying related RMI, by a factor greater than one, to produce reserved storage space data which is available for storing any additional data items related to said data item or to any unrelated data item previously stored on an RMI with said data item; and

storing said data item on a qualifying unrelated RMI, the qualifying unrelated RMI having one or more unrelated data items stored on it and having sufficient actual and sufficient unreserved storage space remaining equal to or greater than said reserved storage space data to store the data item and, if there is no qualifying related RMI, then storing the data item on a new RMI, the new RMI having no data stored on it.

34. A method as claimed in claim 33 including the step of:

when storing the data item on the qualifying unrelated RMI storing the data item on the qualifying unrelated RMI which has the least number of unrelated collections of data items stored on it if there are more than one qualifying unrelated RMI.

35. A method of dispersing storage of a plurality of data items D across a plurality of removable recordable media instances (RMIs) comprising the steps of:

providing controlled data item D.sub.(s,a), of which data item D is a part, where (s) is a data field indicating the subject matter of the data item and (a) is a data field indicating the actual amount of storage space needed on a RMI to store the data item;

designating each RMI I_n(s'"'"',a'"'"',r'"'"') if the RMI is partially full by having one or more data items stored on it and by I.sub.(N+1) if the RMI is the N+1 RMI and is new because no data item has been stored on it, where n is the number of the RMI for all values of n from 1 to N, (s'"'"') is a data field indicating one or more subject matters of one or more data items stored on the nth RMI, (a'"'"') is a data field indicating actual storage space remaining on the nth RMI and (r'"'"') is a data field indicating the reserved storage space remaining on the nth RMI;

receiving actual size data (a) field of a controlled data item D.sub.(s,a) and multiplying the actual size data (a) field times a factor (t) greater than one to produce a data field representing a reserved size (r) data field of the data item D, thereby providing a controlled data item D.sub.(s,r) which is the same as controlled data item D.sub.(s,a) except its data field size has been modified from actual size (a) data field to reserved size (r) data field;

receiving subject matter data (s) field, actual size data (a) field and reserved size data (r) field of data items D stored on RMIs (I_n and I_N) for providing an updated RMI data field listing (p) of I_n(s'"'"',a'"'"',r'"'"') for all values of n from n=1 to n=N where for each RMI corresponding to I_n(s'"'"',a'"'"',r'"'"') an updated reserved size data r'"'"' is reserved storage reserved on said RMI corresponding to a data item stored on said RMI or a pool of combined reserved storages reserved on said RMI for said data item and one or more unrelated data items already stored on said RMI so that the updated reserved size data r'"'"' corresponds to reserved storage on said RMI which is available for storing any additional data items related to any data item already stored on the RMI;

receiving data field listing (p) and a controlled data item D.sub.(s,a) for storing the data item D part of the controlled data item D.sub.(s,a) on any reserved space and unreserved space, if needed, of a qualifying related RMI (I_n), the subject matter data (s) of the controlled data item D.sub.(s,a) comparing with subject matter data (s'"'"') of the qualifying related RMI (I_n) within the RMI data field listing (p) and the actual size data (a) of the controlled data item being equal to or less than the actual storage space data (a'"'"') remaining on the qualifying related RMI, and for indicating any data portion D of controlled data item D.sub.(s,a) which is not stored because there is no qualifying related RMI;

receiving (s) and (a) data field of corresponding data items D stored on the RMIs (I_n) to recalculate the (s'"'"') and (a'"'"') data field for the RMIs (I_n);

storing the data item D part of a controlled data item D.sub.(s,r) on a qualifying unrelated RMI (I_n), the reserved size (r) of the controlled data item D.sub.(s,r) being less than or equal to the remaining actual storage size (a'"'"') of the qualifying unrelated RMI and less than or equal to the remaining reserved storage size (r'"'"') of the qualifying unrelated RMI (I_n) and, if said data item D is not stored because there is no qualifying unrelated RMI then storing the data item D part of the controlled data item D.sub.(s,r) on a new RMI (I_N+1), the new RMI having no data item D previously stored on it; and

receiving the (s), (a) and the (r) data fields of corresponding data items D stored on the RMIs (I_n and I_N+1) to recalculate the (s'"'"'), (a'"'"'), and (r'"'"') data fields for the RMIs (I_n and I_n+1).

36. A method as claimed in claim 35, including the steps of:

storing the data D part of the controlled data item D.sub.(s,r) on the qualifying unrelated RMI (I_n) which has the least unrelated data items stored on it and, if there is more than one qualifying unrelated RMI, then storing the data on the qualifying unrelated RMI which has the least n in the set n=1 to n=N; and

multiplying the actual size data (a) field of the controlled data item (D_s,a) times a factor (t) which is in the range of 1 to some finite number.