Apparatus, system, and method for selecting a space efficient repository

An apparatus, system, and method are disclosed for selecting a space efficient repository. A cache receives write data. A destage module destages the data sequentially to a coarse grained repository such as a stride level repository and destages a directory entry for the data to a coarse grained directory such as a stride level directory if the data satisfies a repository policy. In addition, the destage module destages the data to a fine grained repository such as a track level repository overwriting an existing data instance and destages the directory entry to a fine grained directory such as a track level directory if the data does not satisfy the repository policy.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to selecting a repository and more particularly relates to selecting a space efficient repository.

2. Description of the Related Art

Data storage devices store increasing amounts of critical data for organizations and individuals. The data storage devices may be hard disk drives, optical storage devices, holographic storage devices, semiconductor storage devices, and micromechanical storage devices. In one embodiment, data is written to a controller. The controller may destage the data to a storage device. As used herein, destage refers to encoding the data on the storage device. The controller may also stage the date from the storage device and communicate the data to a host. As used herein, stage refers to retrieving data from a storage device.

Because of the value of the data, the data may be redundantly stored on a plurality of storage devices so that if a storage device is lost, the data may still be recovered. For example, a data storage system may employ a redundant array of independent disks (RAID) to store data on a plurality of hard disks. The data may be divided into a plurality of portions of varying granularity such as coarse grained and fine grained. Each portion may be written as a strip to a different hard disk. As used herein, a strip refers to a portion of data written to one hard disk. A strip typically comprises a fixed number of fine grained structures such as tracks, data blocks, or the like. In addition, parity data may be calculated for the data and the parity data written to a hard disk. A group of strips that share parity data comprise a coarse grained structure such as a stride.

Unfortunately, when only a few tracks of a data set are modified, the data storage system must still calculate parity data for the data set before the data blocks are written to the storage device. Data sets with a relatively small number of modified tracks to be destaged are referred to herein as random data. As a result, the data storage system may accumulate data blocks substantially equivalent to a stride in a cache before writing the data blocks sequentially to the storage devices. However, the frequent destaging of random data may consume excessive storage device space.

SUMMARY OF THE INVENTION

From the foregoing discussion, there is a need for an apparatus, system, and method that select a space efficient repository. Beneficially, such an apparatus, system, and method would select an efficient repository for storing data.

The present invention has been developed in response to the present state of the art, and in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available redundant storage methods. Accordingly, the present invention has been developed to provide an apparatus, system, and method for selecting a space efficient repository that overcome many or all of the above-discussed shortcomings in the art.

The apparatus for selecting a repository is provided with a plurality of modules configured to functionally execute the steps of receiving write data, destaging the data sequentially to a coarse grained repository, or destaging the data to a fine grained repository. These modules in the described embodiments include a cache and a destage module.

The cache receives write data. The destage module destages the data sequentially to the coarse grained repository and destages a directory entry for the data to a coarse grained directory if the data satisfies a repository policy. In addition, the destage module destages the data to the fine grained repository overwriting an existing data instance and destages the directory entry to a fine grained directory if the data does not satisfy the repository policy.

A system of the present invention is also presented for selecting a repository. The system may be embodied in a data storage system. In particular, the system, in one embodiment, includes a plurality of storage devices and a controller. The controller includes a cache and a destage module.

The storage devices store data. In addition, the storage devices are organized as a stride level repository and a track level repository. The controller manages the storage devices.

The cache receives write data. The destage module destages the data sequentially to the stride level repository and destages a directory entry for the data to a stride level directory if the data satisfies a repository policy. In addition, the destage module destages the data to the track level repository overwriting an existing data instance and destages the directory entry to a track level directory if the data does not satisfy the repository policy.

A method of the present invention is also presented for selecting a repository. The method in the disclosed embodiments substantially includes the steps to carry out the functions presented above with respect to the operation of the described apparatus and system. In one embodiment, the method includes receiving write data, destaging the data sequentially to a coarse grained repository, or destaging the data to a fine grained repository.

A cache receives write data. A destage module destages the data sequentially to the coarse grained repository and destages a directory entry for the data to a coarse grained directory if the data satisfies a repository policy. In addition, the destage module destages the data to the fine grained repository overwriting an existing data instance and destages the directory entry to a fine grained directory if the data does not satisfy the repository policy.

The present invention selects either a coarse grained repository or a fine grained repository to receive destaged data. In addition, the present invention may support efficient storage and retrieval of the data. These features and advantages of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.

DETAILED DESCRIPTION OF THE INVENTION

Many of the functional units described in this specification have been labeled as modules, in order to more particularly emphasize their implementation independence. Modules may include hardware circuits such as one or more processors with memory, Very Large Scale Integration (VLSI) circuits, gate arrays, programmable logic, and/or discrete components. The hardware circuits may perform hardwired logic functions, execute computer readable programs stored on tangible storage devices, and/or execute programmed functions. The computer readable programs may in combination with a computer system perform the functions of the invention.

FIG. 1is a schematic block diagram illustrating one embodiment of a data storage system100in accordance with the present invention. The system100includes one or more client computers110, a network115, a router120, an internal network125, one or more servers130, a storage communications channel150, and one or more storage subsystems140.

As used herein, the client computers110are referred to as clients110. The servers130may also be configured as mainframe computers, blade centers comprising multiple blade servers, and the like. Although for simplicity four clients110, one network115, one router120, one internal network125, two servers130, one storage communications channel150, and three storage subsystems140are shown, any number of clients110, networks115, routers120, internal networks125, servers130, storage communications channels150and storage subsystems140may be employed. One of skill in the art will also readily recognize that the system100could include other data processing devices such as bridges, scanners, printers, and the like.

Each storage subsystem140includes one or more storage controllers160and one or more storage devices170. The storage devices170may be hard disk drives, optical storage devices, magnetic tape drives, micromechanical storage devices, holographic storage devices, and semiconductor storage devices. In addition, the storage devices170may also be configured as a redundant array of independent disks (RAID).

In one embodiment, the system100provides data storage and data manipulation services for the clients110. For example, a client110may access data stored on a storage device170of a storage subsystem140by communicating a request through the network115, the router120, the internal network125, a server130, and the storage communications channel150to a controller160for the storage device170. The controller160may retrieve the data from the storage device170and communicate the data to the client110.

The network115connecting the clients110and the servers130may be selected from a local area network (LAN), a wide area network (WAN), the Internet, an Ethernet network, a token ring network, or the like. The network115may comprise one or more nodes those may provide one or more physical and/or logical paths for transferring the data. The internal network125and the storage communications channel150may be for example a LAN, a WAN or the like.

In one embodiment, the storage devices170store data redundantly. Thus if the storage device170fails, client data can be recovered from the other storage devices170. The present invention organizes a plurality of repositories on the storage devices170and selects a repository to improve the performance of the storage devices170as will be described hereafter.

FIG. 2Ais a schematic block diagram illustrating one embodiment of storage devices170of the present invention. The storage devices170are the storage devices ofFIG. 1. The description of the storage devices170refers to elements ofFIG. 1, like numbers referring to like elements. Four storage devices170are shown, although any number of storage devices170may be employed.

Each storage device170is organized with a plurality of strips210,220,230,240. For simplicity, each storage device170is shown with only four strips210,220,230,240, although a storage device170may be organized as any number of strips210,220,230,240.

In one embodiment, client data may be destaged to each of the four storage devices170. For example, a controller160may destage the data to strip0210aof the storage device1170a, strip1220aof storage device2170b, and strip2230aof storage device3170c. The controller160may further calculate parity data from the data and destage the parity data to strip P0240aof storage device4170das is well known to those of skill in the art. A group of strips that share parity data is configured as a stride. For example, strip0210a, strip1,220a, strip2,230a, and strip P0240amay form a first stride, strip3210b, strip4220b, strip5,240b, and strip P1230bmay form a second stride, strip6210c, strip7230c, strip8240cand strip P2220cmay form a third stride, and stripe9220d, strip A230d, strip B240d, and strip P3210dmay form a fourth stride.

If storage device3170cfails, the data of strip2230amay be recovered from strip0210a, strip1220a, and strip P0240aas is well known to those of skill in the art. Unfortunately, each time data is modified, the parity data must be recalculated and the modified data and parity data destaged to a stride. Thus, frequent small modifications to data may consume significant bandwidth of the data storage system100.

FIG. 2Bis a schematic block diagram illustrating one alternate embodiment of storage devices170of the present invention. The storage devices170ofFIG. 2Aare shown. However, storage devices1-3170a-cstore the client data, while storage device4170dstores only parity data. In one embodiment, strip0210a, strip1,220a, strip2230a, and strip P0240aform a first stride, strip3210b, strip4,220b, strip5230b, and strip P1240bform a second stride, strip6210c, strip7,220c, strip8230c, and strip P2240cform a third stride, and strip9210d, strip A,220d, strip B230d, and strip P3240dform a fourth stride.

As with the storage devices170ofFIG. 2A, data may be recovered if any of the storage devices170fail. There is also a bandwidth penalty for recalculating the parity data each time data is destaged to the storage devices170. The present invention destages redundant data while reducing the bandwidth penalty and efficiently using storage space as will be described hereafter.

FIG. 3is a schematic block diagram illustrating one embodiment of a repository selection apparatus300of the present invention. The apparatus300may be embodied in one or more controllers160ofFIG. 1. The description of the apparatus300refers to elements ofFIGS. 1-2B, like numbers referring to like elements. The apparatus300includes a coarse grained repository, a coarse grained directory, a fine grained repository, a fine grained directory, a cache325, a destage module330, a repository policy335, and a history module340. A stride level repository305is used herein as exemplary of the coarse grained repository, a stride level directory310is used herein as exemplary of the coarse grained directory, a track level repository315is used herein as exemplary of the fine grained repository, and a track level directory320is used herein as exemplary of the fine grained directory. However, one of skill in the art will recognize that the present invention may be practiced with other coarse grained and fine grained data storage organizations and structures.

The stride level repository305comprises a plurality of strides. In one embodiment, an administrator assigns a specified number of strides to the stride level repository305. Alternatively, the controller160dynamically adds strides to and removes strides from the stride level repository305. For example, the controller160may add ten thousand (10,000) strides to the stride level repository305if a number of free strides falls below a specified threshold.

The stride level directory310stores one or more entries for each data set stored in this stride level repository305. For example, a first data set may be stored on a first stride with three strips210a,220a,230aalong with parity data stored on a fourth strip240a.The stride level directory310may store an entry specifying a location for each strip210a,220a,230a,240astoring data and/or parity data. In one embodiment, the entries of the stride level directory310are destaged to a stride of a storage device170. Alternatively, the entries of the stride level directory310are stored in semiconductor memory of the controller160.

The track level repository315also comprises a plurality of strides. The administrator may assign a specified number of strides to the track level repository315. Alternatively, the controller160may dynamically add strides to and remove stride from the track level repository315.

The track level directory320stores one or more entries for each data set stored in the track level repository315. For example, a second data set may be destaged to three strips210b,220b,230bof a second stride with parity data destaged to a fourth strip240b. The track level directory320may store an entry for each strip210b,220b,230b,240bof the stride of the second data set. In one embodiment, the entries of the track level directory320are destaged to a stride of a storage device170. Alternatively, the entries of the track level directory320may be stored in semiconductor memory of the controller160.

In one embodiment, the track level directory320comprises one or more data sets distinct from the stride level directory310. For example, the track level directory320may be stored on a first storage device area and the stride level directory310stored on a second storage device area. Alternatively, the stride level directory320and track level directory320share one or more data sets, with stride level directory entries and track level directory entries distinguished by data flags, and words, and the like.

In one embodiment, the strides of the stride level repository305are organized sequentially on the storage devices170. The strides of the track level repository315may also be organized sequentially on the storage devices170. In a certain embodiment, the stride level repository305is organized on storage devices170that are distinct from the storage devices170of the track level repository315.

In a certain embodiment, the stride level repository305and track level repository315share common storage devices170. The strides of the stride level repository305may be intermixed with the strides of the track level repository315. Alternatively, strides of the stride level repository305may be segregated from the strides of the track level repository315on each storage device170.

The cache325receives write data and temporarily stores the data before the data is destaged to a storage device170. For example, a client110may communicate write data to a controller160for storage on a storage device170. The controller160may store the data in the cache325. In addition, a controller160may destage the data to the storage device170. The cache325may be a semiconductor memory. Alternatively, the cache325may be a hard disk drive.

The destage module330destages the data sequentially to the stride level repository305and destages a directory entry for the data to a stride level directory310if the data satisfies the repository policy335. In addition, the destage module330may destage the data to the track level repository315overwriting an existing data instance and destage the directory entry to a track level directory320if the data does not satisfy the repository policy335. In one embodiment, the destage module330comprises executable code stored on a computer usable medium such as the storage devices170ofFIG. 1and/or semiconductor memory of the controller160and executed by a processor of the controller160.

The history module340stores a history of access to the stride level repository305and the track level repository315. In one embodiment, the history module340comprises executable code stored on a computer usable medium such as storage devices170and/or semiconductor memory of the controller160and executed by a processor of the controller160.

The repository policy335may comprise executable code and data stored on a computer usable medium and executed by a processor of the controller160. The controller160may determine whether or not the repository policy335is satisfied, and select either the stride level repository305or the track level repository315for destaging data as will be described hereafter. An administrator may select the repository policy335.

In one embodiment, the server130manages the controller160. The server130may direct the controller160to modify the repository policy335. In one embodiment, the controller160downloads the repository policy335from the server130. The repository policy335may be configured as an initialization file.

FIG. 4is a schematic flow chart diagram illustrating one embodiment of a selection method400of the present invention. The method400substantially includes the steps to carry out the functions presented above with respect to the operation of the described apparatus and system ofFIGS. 1-3. In one embodiment, the method400is implemented with a computer program product comprising a computer useable medium having a computer readable program. The computer readable program may be integrated into a computing system, such as the controller160, wherein the program in combination with the computing system is capable of performing the method400.

The method400starts and the cache325receives405write data. A client110may communicate the write data to the controller160for storage on a storage device170. In one embodiment, the write data comprises modified data of one or more data sets previously retrieved from a storage device170through the controller160by the client110.

In one embodiment, the history module340stores410a history of access to the stride level repository305and the track level repository315. The history may include a record of whether each data set is destaged to the stride level repository305or the track level repository315. In addition, the history may also include data characteristics of each data set destaged to the stride level repository305and the track level repository315. For example, the history may record whether a data set comprises random data, sequentially organized data, data that is read sequentially, compressed data, and the like.

The destage module330determines415if the repository policy335is satisfied. In embodiment, the repository policy335is not satisfied for compressed data in the cache325. For example, the destage module330may determine415the write data is compressed from write data metadata. The destage module330may then determine415that the repository policy335is not satisfied for the compressed write data.

In one embodiment, the destage module330determines415that the repository policy335is satisfied for sequential data stored in the cache325. For example, if a data set stored in the cache325comprises multiple sequential data tracks, the destage module330may determine that the data set is sequential data. As a result, the destage module330may determine415that the repository policy335is satisfied.

In a certain embodiment, the destage module330determines415that the repository policy335is satisfied for random data that is subsequently destaged sequentially. For example, the destage module330may project from the history that random data of a data set will be subsequently destaged sequentially. As a result, the destage module330may determine415that the repository policy335is satisfied for the random data.

The destage module330may determine415that random data satisfies the repository policy335if the random data is destaged sequentially. For example, the destage module330may extrapolate the history to project that a data set may be sequentially staged. The destage module330may therefore determine415that the repository policy335is satisfied although the data is random because the data will be subsequently staged sequentially.

In one embodiment, the destage module330determines415that the repository policy335is satisfied in response to a software hint from an application. For example, a database application may indicate to the destage module330through the software hint that data sets should be destaged sequentially. The hint may be configured as a message communicated as a data packet. Alternatively, the hint may comprise specified data words in metadata of a data set.

In one embodiment, the application may provide the software hint when initializing communication with the controller160. Alternatively, the application may provide the software hint each time the application writes data from a client110to the controller160.

In an alternate embodiment, the destage module330determines415that a specified client110always satisfies the repository policy335. In addition, the destage module330may determine415that a specified client110never satisfies the repository policy335.

In one embodiment, the destage module330may modify the repository policy335. The destage module330may modify the repository policy335based on bandwidth of the data storage system100, a time of day, a day of the week, and a fullness of the storage devices170of the data storage system100. For example, the destage module330may modify the repository policy335so that the repository policy335is always satisfied when the bandwidth of the data storage system100exceeds and bandwidth threshold.

An alternate example, the destage module330may modify the repository policy335so that the repository policy335is not satisfied between the hours of 12 a.m. and 4 a.m. each morning. Similarly, the destage module330may modify the repository policy335so the repository policy335is not satisfied on weekends.

If the repository policy335is satisfied, the destage module330destages420the data sequentially to the stride level repository330. The strides receiving the data may not store a previous instance of the data. For example, the data may have been previously staged from a first set of strides. The destage module330then sequentially destages420the modified data to a second set of strides. As a result, the data may be destaged efficiently and rapidly.

The sequential strides may be included in the stride level repository330. Alternatively, the sequential strides may be assigned to the stride level repository330after the data is destaged420to sequential strides.

In addition, the destage module330destages425a directory entry for the data to the stride level directory310and the method400ends. For example, the destage module330may destage a directory entry for each stride receiving data and/or parody data. The directory entry may be destaged to a storage device170. Alternatively, the directory entry may be destaged to a semiconductor memory.

In one embodiment, the destage module330destages420the data to the stride level repository305and destages425the directory entry for the data to the stride level directory310for each write after the repository policy is satisfied for a first write. The destage module330may continue to destage420the data to the stride level repository305and destage425the directory entry for the data to the stride level directory310until the repository policy335is not satisfied for a specified number of writes.

If the repository policy335is not satisfied, the destage module330destages430the data to the track level repository315, overwriting an existing data instance. For example, a data instance may have been staged from a first set of strides. The destage module330may destage430the modified data to the first set of strides, overriding the existing data instance.

The destage module330further destages435the directory entry to the track level directory320and the method400ends. In one embodiment, the destage module330does not destage a new directory entry to the track level directory320if the new directory entry is identical to a previous directory entry for the data.

The method400selects between the stride level repository305and the track level repository315in order to use storage space on the storage devices170and data storage system bandwidth most efficiently. For example, if the repository policy335is not satisfied, the destage module330destages430data to the track level repository315as it is not necessary to sequentially destage the data. Alternatively, if the repository policy is satisfied the destage module330destages420the data to the stride level repository305for efficiency in destaging and staging the data.

FIG. 5is a schematic block diagram illustrating one embodiment of cache data500of the present invention. The data may reside in the cache325ofFIG. 3. The description of the data500refers to elements ofFIGS. 1-4, like numbers referring to like elements. The data500includes one or more data tracks505. In the depicted example, the data tracks505are from a common file or data set.

The data tracks505are example of sequential data. The data505may be efficiently destaged sequentially to the stride level repository305. Sequentially destaging the data505may further allow the data505to be efficiently staged sequentially from the storage devices170.

FIG. 6is a schematic block diagram illustrating one alternate embodiment of cache data600of the present invention. The data may reside in the cache325ofFIG. 3. The description of the data600refers to elements ofFIGS. 1-4, like numbers referring to like elements. The data600includes one or more data tracks605,610,615. In the depicted example, the data tracks605,610,615are from three distinct Lyle sort data sets.

The data tracks605,610,615are exemplary of random data. The data tracks605,610,615may be efficiently destaged to the storage devices170overwriting previous instances of the data tracks605,610,615.

For example, instances of data track6of file1605, data track5of file2610, data track9of file3615a, and data track8of file3615dmay each have been staged from one or more storage devices170. The destage module330may subsequently destage430modified instances data track6of file1605, data track5of file2610, data track9of file3615a, and data track8of file3615doverwriting previous instances. The data tracks605,610,615may be efficiently destaged to the track level repository315as destaging the data tracks605,610,615sequentially to the stride level repository305may consume excessive storage space.

The present invention selects either a stride level repository or a track level repository to receive destaged data. In addition, the present invention may support efficient storage and retrieval of the data. The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.