System and method for allocating storage in a fragmented storage space

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.

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.

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.