System and method for allocating storage in a fragmented storage space
First Claim
1. 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
15 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9, 10)
-
-
11. 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. - View Dependent Claims (12)
-
-
13. 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. - View Dependent Claims (14, 15)
-
Specification