Patent US5802599A successfully refreshed from Google Patents.
US5802599A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for allocating storage in a fragmented storage space
Assignee: International Business Machines Corp
•
Filing: 1996-07-30
•
Granted: 1998-09-01
•
Expires: 2016-07-30
Abstract
Abstract This invention provides a one-pass storage process to manage storage space in a storage hierarchy system wherein whole objects or fragments of whole objects can be retrieved efficiently. Metadata to represent appropriate geometric characteristics of storage devices, units of transfer to minimize retrieval time, and buffers, are used to control the storage allocation. A plurality of objects from an object set are aggregated into at least one object grouping for storage where the object grouping is smaller than a minimum storage size. For each object grouping and each object not in an object grouping, a determination is made of the total number of blocks of storage needed and a minimum transfer size. Extents of blocks are identified in the storage device of a size greater than the minimum transfer size totalling the total number of blocks of storage needed.
Inventors
- 👤 Luis Felipe Cabrera
- 👤 Robert M. Rees
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 12:52
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0682; G06F3/0602; G06F3/061; G06F3/0611; G06F3/0628; G06F3/0638; G06F3/0644; G06F3/0674; G06F2212/00; G06F2212/40; G06F2212/401
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
305 words
In a storage system having a central processing unit (CPU), memory and at least one storage device wherein data objects are stored in a plurality of storage units on the storage device having unused storage units interspersed with the storage units containing data objects, a method for allocating unused storage units for an object set of a plurality of related data objects, comprising the steps performed by the CPU of: (a) aggregating in memory for transference together to the storage device, at least two data objects from the object set that are of a size smaller than an optimal minimum storage size for transferring data objects to and from the storage device as determined for the storage system, into at least one object grouping of a size equal to or smaller than the optimal minimum storage size for the storage system; (b) determining the total number of storage units needed for each object grouping and each data object, larger than the optimal minimum storage size, in the object set not in an object grouping; (c) identifying the location and size of one or more extents of unused storage units between storage units containing data objects, of a size at least equal to the optimal minimum storage size, for storing each object grouping and each data object in the object set not in an object grouping; and (d) storing each object grouping and each data object in the object set not in an object grouping in the identified extents of a size at least equal to the optimal minimum storage size, so that the related data objects of the object set are stored as contiguously as possible for more efficient retrieval of the related data objects, and wherein all data objects in an object grouping are transferred together to the storage device for more efficient transference.
Claim 2
Dependent Claim
305 words
In a storage system having a central processing unit (CPU), memory and at least one storage device wherein data objects are stored in a plurality of storage units on the storage device having unused storage units interspersed with the storage units containing data objects, a method for allocating unused storage units for an object set of a plurality of related data objects, comprising the steps performed by the CPU of: (a) aggregating in memory for transference together to the storage device, at least two data objects from the object set that are of a size smaller than an optimal minimum storage size for transferring data objects to and from the storage device as determined for the storage system, into at least one object grouping of a size equal to or smaller than the optimal minimum storage size for the storage system; (b) determining the total number of storage units needed for each object grouping and each data object, larger than the optimal minimum storage size, in the object set not in an object grouping; (c) identifying the location and size of one or more extents of unused storage units between storage units containing data objects, of a size at least equal to the optimal minimum storage size, for storing each object grouping and each data object in the object set not in an object grouping; and (d) storing each object grouping and each data object in the object set not in an object grouping in the identified extents of a size at least equal to the optimal minimum storage size, so that the related data objects of the object set are stored as contiguously as possible for more efficient retrieval of the related data objects, and wherein all data objects in an object grouping are transferred together to the storage device for more efficient transference.
Claim 3
Dependent Claim
107 words
The method of claim 1 wherein one or more data objects are aggregated into an object grouping by performing the steps of: (a) for each data object in the object set smaller than the optimal minimum storage size, storing the data object in a buffer the size of the optimal minimum storage size; and (b) when a data object in the object set smaller than the optimal minimum storage size will not fit in a used buffer containing one or more other data objects, storing the object in a refreshed buffer, wherein the group of one or more objects in the used buffer are an object grouping.
Claim 4
Dependent Claim
92 words
The method of claim 1 wherein the extents of unused storage units for storing data objects of an object set are identified by performing the step of: traversing a listing of location identifiers and sizes of extents of unused storage units interspersed between storage units containing data objects once in a predetermined order while identifying unused extents of a size at least equal to the optimal minimum storage size until the total number of storage units needed for storing all data objects in the object set are identified or the listing ends.
Claim 5
Dependent Claim
82 words
The method of claim 3 wherein the listing of identifiers and sizes of extents of unused storage units is created by performing the steps of: (a) creating a bit map representation of the storage units of the storage device; (b) creating a linked list grouping extents based on the bit map representation wherein the linked list is the listing of identifiers and sizes of extents of unused storage units; and (c) updating the linked list as storage units are used and freed.
Claim 6
Dependent Claim
21 words
The method of claim 1 wherein the storage system comprises a server system in communication with a plurality of client systems.
Claim 7
Dependent Claim
25 words
The storage systems of claim 5 wherein the minimum storage size is determined as a factor of the object size and the storage device characteristics.
Claim 8
Dependent Claim
277 words
In a storage system comprising a server in communication with a plurality of clients, having a central processing unit (CPU), memory and at least one storage device wherein data objects are stored in one or more blocks on the storage device, a method for allocating unused blocks interspersed between used blocks on the storage device for an object set of at least one data object comprising the steps performed by the CPU of: (a) for each data object in the object set determining whether the data object fits in a buffer the size of an optimal minimum storage size for transferring data objects to and from the storage devices as determined for the storage system; (b) storing in the buffer data objects that fit in the buffer; (c) when a data object smaller than the buffer size does not fit in the buffer, requesting an identified extent of unused blocks on the storage device for the data objects in the buffer, and storing the data object smaller than the buffer size that does not fit in the buffer in the buffer after the data objects in the buffer have been stored in an identified extent of unused blocks on the storage device; (d) for each data object larger than the buffer size, requesting an identified extent of unused blocks on the storage devices for the total number of blocks needed for storage of the data object larger than the buffer size; and (e) only storing data objects of an object set on the storage device when a sufficient number of extents of unused blocks are identified to store all of the data objects of the object set.
Claim 9
Dependent Claim
277 words
In a storage system comprising a server in communication with a plurality of clients, having a central processing unit (CPU), memory and at least one storage device wherein data objects are stored in one or more blocks on the storage device, a method for allocating unused blocks interspersed between used blocks on the storage device for an object set of at least one data object comprising the steps performed by the CPU of: (a) for each data object in the object set determining whether the data object fits in a buffer the size of an optimal minimum storage size for transferring data objects to and from the storage devices as determined for the storage system; (b) storing in the buffer data objects that fit in the buffer; (c) when a data object smaller than the buffer size does not fit in the buffer, requesting an identified extent of unused blocks on the storage device for the data objects in the buffer, and storing the data object smaller than the buffer size that does not fit in the buffer in the buffer after the data objects in the buffer have been stored in an identified extent of unused blocks on the storage device; (d) for each data object larger than the buffer size, requesting an identified extent of unused blocks on the storage devices for the total number of blocks needed for storage of the data object larger than the buffer size; and (e) only storing data objects of an object set on the storage device when a sufficient number of extents of unused blocks are identified to store all of the data objects of the object set.
Claim 10
Dependent Claim
24 words
The method of claim 7 further comprising the step of a client requestor sending a list of objects to be stored to the server.
Claim 11
Dependent Claim
19 words
The method of claim 7 further comprising the step of notifying a requestor when an object cannot be stored.
Claim 12
Dependent Claim
59 words
The method of claim 7 further comprising the steps of: representing each block of the storage device by a bit in a bit map; and using the bit map representation to create an extent list, wherein the extent list comprises a plurality of pairs of values for the first unused block address and the number of contiguous unused blocks.
Claim 13
Dependent Claim
254 words
A storage allocation system for allocating storage for at least one object set of a plurality of objects in a computerized storage system having a central processing unit (CPU), memory and a storage device comprising: aggregating means for aggregating into at least one object grouping stored in a buffer in memory for transference together to the storage device, a plurality of objects from the object set that are smaller than an optimal minimum storage size for transferring objects to and from the storage device as determined for the storage system, the object grouping being at most the size of the optimal minimum storage size wherein objects from one object set are stored together in an object grouping separate from objects from another object set; means for determining a total number of storage units needed for each object grouping and each object in the object set not in an object grouping; identification means for identifying a set of one or more extents of unused storage units in the storage device interspersed between storage units containing objects, wherein each identified extent is larger than the optimal minimum storage size and the size of the set of one or more extents equals the total number of storage units needed; and means for storing each object grouping and each object not in an object grouping in the identified extents, so that objects in an object set are stored as contiguously as possible, and such that all objects in an object grouping are transferred together to the storage device.
Claim 14
Dependent Claim
254 words
A storage allocation system for allocating storage for at least one object set of a plurality of objects in a computerized storage system having a central processing unit (CPU), memory and a storage device comprising: aggregating means for aggregating into at least one object grouping stored in a buffer in memory for transference together to the storage device, a plurality of objects from the object set that are smaller than an optimal minimum storage size for transferring objects to and from the storage device as determined for the storage system, the object grouping being at most the size of the optimal minimum storage size wherein objects from one object set are stored together in an object grouping separate from objects from another object set; means for determining a total number of storage units needed for each object grouping and each object in the object set not in an object grouping; identification means for identifying a set of one or more extents of unused storage units in the storage device interspersed between storage units containing objects, wherein each identified extent is larger than the optimal minimum storage size and the size of the set of one or more extents equals the total number of storage units needed; and means for storing each object grouping and each object not in an object grouping in the identified extents, so that objects in an object set are stored as contiguously as possible, and such that all objects in an object grouping are transferred together to the storage device.
Claim 15
Dependent Claim
62 words
The system of claim 11 wherein said aggregating means comprises: a buffer, wherein the the optimal minimum storage size represents an upper fragmentation limit as determined for the storage system, which is a factor of a minimum allocation unit for the storage device; means for determining whether an object fits into said buffer; and means for storing an object in said buffer.
Claim 16
Dependent Claim
298 words
An article of manufacture for use in a computer system for storing an object set of a plurality of data objects in a plurality of storage units on a storage device having unused storage units interspersed with storage units containing data objects, the computer system having means to write data objects to the storage devices, said article of manufacture comprising a computer-readable storage medium having a computer code embodied in said medium which may cause the computer to: aggregate in a buffer for transference together to the storage device, at least two data objects from the object set that are of a size smaller than an optimal minimum storage size for transferring data objects to and from the storage devices as determined for the storage system, into at least one object grouping of a size equal to or smaller than the optimal minimum storage size for the storage system; determine the total number of storage units needed for each object grouping and each data object, larger than the optimal minimum storage size, in the object set not in an object grouping; identify the location and size of one or more extents of unused storage units between storage units containing data objects, of a size at least equal to the optimal minimum storage size, for storing each object grouping and each data object in the object set not in an object grouping; transfer all objects in an object grouping, as stored in the buffer, together to the one or more extents; and store each object grouping and each data object in the object set not in an object grouping in the identified extents of a size at least equal to the optimal minimum storage size, so that data objects in an object set are stored as contiguously as possible.
Claim 17
Dependent Claim
298 words
An article of manufacture for use in a computer system for storing an object set of a plurality of data objects in a plurality of storage units on a storage device having unused storage units interspersed with storage units containing data objects, the computer system having means to write data objects to the storage devices, said article of manufacture comprising a computer-readable storage medium having a computer code embodied in said medium which may cause the computer to: aggregate in a buffer for transference together to the storage device, at least two data objects from the object set that are of a size smaller than an optimal minimum storage size for transferring data objects to and from the storage devices as determined for the storage system, into at least one object grouping of a size equal to or smaller than the optimal minimum storage size for the storage system; determine the total number of storage units needed for each object grouping and each data object, larger than the optimal minimum storage size, in the object set not in an object grouping; identify the location and size of one or more extents of unused storage units between storage units containing data objects, of a size at least equal to the optimal minimum storage size, for storing each object grouping and each data object in the object set not in an object grouping; transfer all objects in an object grouping, as stored in the buffer, together to the one or more extents; and store each object grouping and each data object in the object set not in an object grouping in the identified extents of a size at least equal to the optimal minimum storage size, so that data objects in an object set are stored as contiguously as possible.
Claim 18
Dependent Claim
105 words
The article of manufacture of claim 13 wherein the computer program code embodied in the medium may cause the computer system to: for each data object in the object set smaller than the optimal minimum storage size, store the data object in a buffer the size of the optimal minimum storage size; and when a data object in the object set smaller than the optimal minimum storage size will not fit in a used buffer containing one or more other data objects, store the object in a refreshed buffer, wherein the group of one or more objects in the used buffer are an object grouping.
Claim 19
Dependent Claim
101 words
The article of manufacture of claim 14 wherein the extents of unused storage units for storing data objects of an object set are identified by the computer program code embodied in said medium causing the computer to: traverse a listing of location identifiers and sizes of extents of unused storage units between storage units containing data objects once in a predetermined order while identifying unused extents of a size at least equal to the optimal minimum storage size until the total number of storage units needed for storing all data objects in the object set are identified or the listing ends.
References Cited (Backward Citations)
US4758944A
Cited
US5034914A
Cited
US5155830A
Cited
US5375233A
Cited
US5384669A
Cited
US5276840A
Cited
US5479656A
Cited
US5394534A
Cited
US5454103A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-31 | 2002-03-02 | 2002-09-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-31 | 2006-03-02 | 2006-09-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-31 | 2010-03-02 | 2010-09-01 | $7700.00 | Window Closed / Lapsed |