Log-structured block system and method

[0001] This application claims the benefit of U.S. Provisional Application No. 60/264,891, filed Jan. 29, 2001.

[0002] The present invention relates generally to data storage arrays. More particularly, the present invention relates to a log-structured block system within a data storage array.

[0003] Data mirroring is a common technique used to ensure reliability in data storage arrays. In a typical storage array that employs data mirroring, the mirroring is accomplished by writing the information at two different locations. Some prior art systems write the information 180° out of phase on the same disc; thus, reducing the capacity of the drive by at least half. On the other hand, some prior art systems write the data from one disc drive onto a second disc drive in the array; this method requires having a second drive for every first drive in the array. These prior art systems require twice as many of the number of drives in an array to meet the non-mirrored design requirements. Consequently, the prior art designs are expensive and inefficient solutions.

[0004] Further, in the prior art systems described above, the host has to wait until the array controller can give confirmation that both of the data locations have been written. While both of these writes may be performed at the same time, the simultaneous writing of both sets of data to two different locations is an inefficient process.

[0005] The prior art data mirroring systems fail to solve all of the problems associated with mirroring an array of drives. Therefore, a need exists for a solution to the problem of providing data mirroring at a more efficient rate and lower cost. More specifically, a need exists for a solution to the problem of mirroring fast input/output drives, while reducing the cost incurred in mirroring without decreasing the system performance.

[0006] The present invention provides a solution to this and other problems, and offers other advantages over the prior art.

[0007] The present invention relates to data storage systems that have log-structured block capabilities which solve the above-mentioned problems.

[0008] In accordance with one embodiment of the invention, a log-structured data writing method is provided in which logs are created. Subsequently the logs are written to a data storage medium. In addition, the invention also can be implemented as a log-structured block system itself.

[0009] In accordance with a another embodiment of the present invention, a data mirroring method is provided in which a mirror of data is created based on log-structured data. In addition, the invention also can be implemented as a data storage system.

[0010] These and various other features as well as advantages which characterize the present invention will be apparent upon reading of the following detailed description and review of the associated drawings.

[0017] Referring now to FIG. 1, a data storage array 100 is shown. A system, like the one shown in FIG. 1 includes an array controller 102, comparatively low capacity disc drives 104, 108, 112 and a comparatively high capacity disc drive 106. Array controller 102 contains a processor (not shown), memory (not shown), host and disc interfaces (not shown). Array controller 102 buffers the data to be mirrored and creates the control information necessary to mirror the data. Typically, the low capacity drives 104 will have a high input/output (I/O) rate and consequently high cost per megabyte. An example of a drive that provides a high I/O rate is a multi-actuator disc drive. The I/O rate is mostly dependent on the number of write or read requests the drives receive. Further, high capacity disc drive 106 will have a comparatively lower I/O rate and lower cost per megabyte than the low capacity disc drives 104. Preferably, the write requests are mirrored simultaneously by one of the methods listed below. Whichever method is used, the data is eventually written on the low I/O, high capacity drive 106. The write requests that are initially written on the high capacity drive 106 are written by a log-structured data writing method described below, the log-structured data writing being done in a sequential fashion. Thus, mirrored data from drive 104 may be followed by data from drive 108 or 112.

[0018] In a data storage array 100, write requests make up typically 25% to 50% of the total I/O requests. While the high I/O rate drives 104, 108, and 112 perform read requests, the high capacity drive 106 is enabled to perform housekeeping work to effectively move the sequentially written log-structured data to organized locations that are dedicated to be logical mirrors of drives 104, 108, and 112. The low number of write requests to the data storage array 100 will allow the high capacity, low I/O rate disc drive 106 the ability to move the mirrored data that was sequentially stored. Thus, in a preferred embodiment, a log-structured block system can provide a solution to allow a number of comparatively high I/O rate, small capacity drives 104, 108 and 112 to be mirrored onto a comparatively slower I/O rate, high capacity drive 106.

[0019] FIG. 2 is a diagram of a disc 200 intended to be a representation of the data layout of the preferred embodiment high capacity disc drive 106. Information is written to and read from tracks (not shown) on the disc 200 through the use of a transducer (not shown). The disc 200 includes an inner data zone 204 and an outer data zone 202 that can be used to mirror data from a first and second data source. A data source may consist of a disc drive, CD-ROM, ROM, RAM, a plurality of disc drives, etc. The disc 200 may be divided into as many data zones as deemed necessary by the design requirements of the data sources that will be mirrored. The disc 200 also includes areas 206, 208, 210 for writing log-structures. Preferably, inner data zone 204 and outer data zone 202 have the same data capacities as the two data sources that they mirror. The capacity for the log-structure areas 206, 208, 210 is a design variable that is chosen based on the characteristics of the system environment and the required optimizations. The log-structure areas 206, 208, 210 are located between the data zones 202 and 204 to minimize the movement between the actuator arms (not shown) and the data zones 202 and 204. Log-structure areas 208 and 210 may be used as data buffers to ensure that there is enough space available for the log-structures being written. The log-structure areas 208 and 210 may be combined into log-structure area 206 to make a larger area for storing the sequentially written log-structured data.

[0020] FIG. 3 illustrates a flowchart of two methods, the first method 350 for writing log-structured data and the second method 360 for mirroring data, both methods in accordance with embodiments of the present invention. The illustrated methods are usually represented as algorithms inside a controller such as controller 102. The controller 102 processes read and write commands for the low capacity, high I/O drives. When a write command is initiated, the controller 102 processes log-structured mirroring algorithm 300, which is a combination of the first method 350 for writing log-structured data and the second method 360 for mirroring data.

[0021] The log-structured mirroring algorithm 300 is based on log-structured block system (LSBS) concepts that are derived from the ideas used in log-structure file systems. Log-structure file systems write all files sequentially to a log on the disk drive. This improves both write performance and crash recovery. File reads are performed by properly indexing the logs. Cleaning operations that follow are used to throw away old data and logs that are of no value to recover disc space. A similar system can be used to create a high capacity log-structured disc drive. In the following description, a LSBS and associated mirroring methods are described.

[0022] When a write command is received, the controller 102 creates a log in the memory, step 302. FIG. 4 shows a simple memory log 400. The memory log 400 consists of a header 402 that contains the write request and other metadata. An example of metadata is a pointer 406 to the next write request. There may be other metadata such as write time (not shown). The pointer 406 is necessary because the amount of data 404 to be written to the disc 106 may have various lengths, thus the header and the data have a complete set of information to create a mirrored copy.

[0023] A number of memory logs 400 may be created in the memory before they are written to the disc 106. These memory logs 400 may be sequentially written in the memory (not shown) as shown in FIG. 5 or they may be written in a scatter gather manner if large blocks of sequential memory are not to be used for logs 400. Whichever write method is chosen, it is important to know the sequence in which the writes arrive and write them to the disc 106 in the same order. Writing the memory logs 400 sequentially to the high capacity drive 106 is faster than random writes. This should allow the high capacity drive 106 time to keep up with the low capacity drives, especially during the times when burst writes occur.

[0024] After the log is created in the memory, the controller 102 writes the log, step 304, to the high capacity disc drive 106. This may be done once a sufficient number of logs 400 are accumulated. Preferably, the logs 400 are written 304 when there is enough data so that one whole track can be written in one write operation. Such a method may require a non-volatile memory (not shown) for storing the logs until the write 304 to protect against data loss from power failure. This write to the high capacity disc 106 is preferably done as a sequential write. The amount of logs 400 being written 304 is a design choice of the system and many variations may be available, such as writing 304 when many tracks of data can be written.

[0025] Next, the mirror is created, step 306. Creating the mirror 306 is an independent process from creating the log(s) 302 and writing the log(s) 304. Thus, step 306 may be replaced by another operation such as restarting the method 350 or stopping the log writing method 350 until more writes are received.

[0026] Preferably, data mirroring method 360 has two operations. First, the logs 400 are read 308 from the high capacity disc 106 during light usage. This may be a sequential read operation performed during a time of low activity of read or write requests. Next, the mirror is created 310 on the high capacity disc 106. This is done by parsing each log entry 400 to decide what data zone and logical block number the data is to be written to on the high capacity disc drive 106. The information used to create the mirror of each log is stored in the log itself, usually as metadata 402. The metadata 402 includes information on where the log data 404 should be written respective of the location the corresponding data on the high I/O, low capacity drives. The information about where the log should be written is important because it specifies which high I/O disc drive the data belongs to and also the location, or logical block number, of the data on the corresponding high I/O disc drive. This information is useful, in step 306, to determine the appropriate location to write the mirrored data.

[0027] Finally, a write request is scheduled with the disc drive 106 to complete the mirroring. The data is usually written to the high capacity drive 106 by a random write operation. Generally, there will be a track seek operation before writing data to the disc 106 for each log entry 400.

[0028] Creating a memory log 302, writing the log 304, and creating a mirror 306 may all be done in parallel by the controller 102. Further, the controller 102 can perform other processes in parallel with the data mirroring processes. For example, the controller may parse incoming Command Data Blocks and send operations to the low capacity, high I/O rate drives 104. There are various software techniques and data structures that are well known in the industry that can be used to schedule, parallelize, and optimize these operations.

[0029] FIG. 6 illustrates a flowchart of a method for mirroring data in accordance with a preferred embodiment of the present invention. The above data mirroring method 600 recognizes three different situations and optimizes for each of them. These situations are (i) when writes are arriving extremely slow, (ii) when writes are arriving at a moderate rate, and (iii) when writes are arriving at a very fast rate.

[0030] The controller 102 determines which of the three optimizations it will perform based on monitoring the write rate 604. The rate at which the writes are arriving can be determined by comparing the number of writes over time to the I/O properties of the high capacity, low I/O drive 106 for various operations such as sequential writes and random writes. One method of determining the rate at which writes are arriving is to monitor the available capacity of the memory. As the memory is filled, the rate at which the writes are arriving may be high. If the memory is filling gradually, the rate at which the memory is arriving may be moderate and if the memory is being filled slowly, then the rate at which the writes are arriving may be low.

[0031] If the writes are arriving fast, the data mirroring algorithm 300 of FIG. 3 is performed in the corresponding steps 606, 608, 610, 612. Thus, there will not be much time to perform many functions other than creating the log, step 602, in memory and writing the logs, step 606, to the high capacity disc drive 106.

[0032] If the writes are arriving slowly, then priority should be given to reading logs 610 from the disc drive 106 and writing the mirror data 612. If there are no logs 400 present on the disc drive 106, creating the disc mirror 620 should be done by writing the mirror data 622 directly from memory (not shown) without doing the writing of the logs 606, or the reading the logs 610.

[0033] If the writes are arriving at a moderate rate, the logs 400 should be accumulated 630 in the memory (not shown) while other logs 400 are simultaneously read 610 from the high capacity disc drive 106 and written to create the data mirror 612. When a minimum amount of logs 400 are accumulated, the logs 400 are written 606. This is preferably done when there is enough data so that one whole track can be written in one write operation. The write 606 to the high capacity disc 106 is preferably done as a sequential write. When the logs 400 are written 606 is a design choice of the system and many variations may be available, such as writing 606 when many tracks of data can be written.

[0034] The amount of space (sectors and tracks) available in the areas 206, 208, 210 for writing log-structures will have to be determined for the performance of an individual system. The rate at which the writes arrive have to be balanced over time so that the logs 400 can be mirrored 608 and the areas 206, 208, 210 for writing log-structures on the disc drive 106 do not get consumed.

[0035] It is to be understood that even though numerous characteristics and advantages of various embodiments of the present invention have been set forth in the foregoing description, together with details of the structure and function of various embodiments of the invention, this disclosure is illustrative only, and changes may be made in detail, especially in matters of structure and arrangement of parts within the principles of the present invention to the full extent indicated by the broad general meaning of the terms in which the appended claims are expressed. For example, the particular elements may vary depending on the particular application for the data storage array while maintaining substantially the same functionality without departing from the scope and spirit of the present invention. In addition, although the preferred embodiment described herein is directed to log structured mirroring for a data storage system, it will be appreciated by those skilled in the art that the teachings of the present invention can be applied to other systems, like single drive mirroring systems, without departing from the scope and spirit of the present invention.