Storage system using fast storage and log-structured storage

The invention pertains to computer storage systems. More particularly, this invention relates to a computer storage system utilizing fast storage devices.

Disk arrays are used to provide storage for computer applications that need increased reliability in the face of component failures, as well as high performance for normal use. The disks in the disk arrays are often arranged as a redundant array of independent disks (RAID). The RAID arrays provide larger capacity, higher performance and, typically, higher availability for stored data than using disks individually. This is done by distributing the data across multiple disks and by including back-up information. The back-up information may be a copy of the data or enough parity information to regenerate the data if a disk or related component fails. Storing a copy of the data usually provides higher performance for read operations, as any of the available copies can be read.

One problem with the use of disks is that disks are relatively inefficient in accessing small amounts of data that are not sequentially laid out on the disk. In a typical 4 KB read, a current disk might require between 5 and 20 ms to position the disk head before beginning to transfer data, and less than 0.5 ms for transferring the data. A non-computer analogy is a repairman billing a customer 1 hour for traveling and 5 minutes for fixing an appliance. Since disk head positioning times are improving very slowly, positioning time is likely to remain an issue. When redundant copies of the data are stored in the array, small writes can be even more inefficient, because disk heads corresponding to each of the multiple copies must spend time to position themselves before writing a small amount of data.

According to an embodiment of the invention, a computer storage system comprises a controller configured to perform data operations and a storage device array including a first sub-array and a fast storage sub-array storing data redundant to data stored in the first sub-array. The first sub-array includes at least one log-structured storage device, and the fast storage sub-array includes at least one fast storage device.

According to another embodiment of the invention, a method for cleaning an extent comprises retrieving data being cleaned from the at least one fast storage device; and appending the data being cleaned to at least one current extent in at least one log-structured storage device.

According to yet another embodiment of the invention, a method comprises receiving a request to perform a data operation; determining whether the request provokes a write operation on the storage system; and in response to the request provoking a write operation, writing data to at least one log-structured storage device and writing redundant data to at least one fast storage device.

According to yet another embodiment of the invention, a method comprises determining whether at least one log-structured storage device failed; reading data from at least one fast storage device in response to the at least one log-structured storage device being failed, the read data including data redundant to the data stored on the at least one failed log-structured storage device; and writing the redundant data to a log-structured storage device that is operative in the storage system.

According to yet another embodiment of the invention, a computer storage apparatus comprises a controller means for performing data operations and a storage array means for storing data. The storage array means includes a first sub-array means for storing data using a log-structured algorithm and a fast storage sub-array means for storing data redundant to data stored in the first sub-array means, wherein the fast storage sub-array means includes one or more fast storage devices.

The present invention is illustrated by way of example and not limitation in the accompanying figures in which like numeral references refer to like elements, and wherein:

FIG. 1 illustrates a computer system, according to an embodiment of the invention;

FIG. 2 illustrates a storage device including a log-structured disk sub-array and fast storage devices, according to an embodiment of the invention;

FIG. 3 illustrates a flow diagram of a method for cleaning an extent in a log-structured disk, according to an embodiment of the invention;

FIGS. 4 and 5 illustrate flow diagrams of an exemplary method for performing input/output (I/O) operations on the computer system shown in FIG. 1 , according to an embodiment of the invention; and

FIG. 6 illustrates a flow diagram of an exemplary method for fault recovery, according to an embodiment of the invention.

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one of ordinary skill in the art that these specific details need not be used to practice the present invention. In other instances, well-known structures, interfaces, and processes have not been shown in detail in order not to unnecessarily obscure the present invention.

FIG. 1 illustrates a computer system 100 , according to an embodiment of the invention. The computer system 100 includes a storage device 110 connected to at least one client 120 (e.g., a server or another type of computing device) via a network 130 . The storage device 110 includes multiple magnetic disks 140 and multiple fast storage devices 150 connected to a controller 160 , which manages data operations for the disks 140 and the fast storage devices 150 .

The storage device 110 may optionally include one or more caches 145 for caching data for the disks 140 and the fast storage devices 150 . FIG. 1 illustrates one or more caches 145 connected to the disks 140 , the fast storage devices 150 , and the controller 160 . An optional buffer 142 , which may include volatile memory, can be used as a buffer for copying between the two sub-arrays 140 and 150 , such as for a fault recovery operation and for a compaction operation (also known as a cleaning operation). Alternatively, the cache 145 may be used as the buffer.

The fast storage devices 150 may include one or more of several kinds of storage devices which have a smaller overhead than conventional magnetic disks before starting data transfers. The fast storage devices 150 may have data transfer rates similar to and/or better than conventional magnetic disks, but shorter positioning times. One example of a fast storage device is a micro-electro-mechanical system (MEMS) storage device.

The controller is connected to the cache 145 for performing I/O operations in the storage device 110 . Also, the controller 160 may be connected to the disks 140 , the fast storage devices 150 , and the buffer 142 for performing cleaning operations (described in detail below) and other tasks. It will be apparent to one of ordinary skill in the art that the controller 160 may be a component separate from the disks 140 and the fast storage devices 150 . Furthermore, the controller 160 may be implemented with software components, instead of hardware components, or both software and hardware components. Also, the controller 160 may include one or more controllers. In addition, the computer system 100 is not limited to using the network 130 , and one or more clients 120 may be directly connected to the storage device 110 .

It will be apparent to one of ordinary skill in the art that the storage device 110 may include any type of persistent storage devices. The storage device 140 is not limited to magnetic hard disks and may alternatively include another type of storage media (e.g., optical disks, tapes, etc.). In addition, the fast storage devices 150 are not limited to MEMS and may include other fast storage devices, such as flash RAM, magneto-resistive RAM (MRAM), battery-backed DRAM or SRAM, etc. Also, the disks 140 and fast storage devices 150 may not be in one enclosure or even in one location. Furthermore, the disks 140 , the fast storage devices 150 , and the controller 160 may be connected via one or more networks.

In one embodiment, the storage device 110 includes two sub-arrays 140 and 150 . The disk sub-array 140 is an array of disks and the fast storage device sub-array 150 is an array of fast storage devices storing redundant data, which is a copy of the data stored on the disk sub-array. The disk sub-array 140 may have at least as much capacity as the fast storage sub-array 150 . The cache 145 may include a non-volatile memory for storing metadata, such as descriptions of where various data are located, and temporary storage for I/O operations.

FIG. 2 illustrates a log-structured disk (e.g., a disk using a log-structured algorithm for performing I/O operations) in the storage device 110 , according to an embodiment of the invention. A log-structured disk 140 a in the disk sub-array 140 and a fast storage device 150 a in the fast storage sub-array 150 are shown. The data stored on the fast storage sub-array 150 , including the fast storage device 150 a , may be striped, such as in a RAID 0 format. Updates to the data stored in the fast storage sub-array 150 are made in place (i.e., the data block being updated is over-written).

A log-structured layout may be used for the disks in the disk sub-array 140 . FIG. 2 shows a disk 140 a of the disk sub-array 140 employing a log-structured layout (any of the disks in the disk sub-array 140 may employ the log-structured layout), according to an embodiment of the invention. The space in the disk 140 a is divided into extents. An extent may include a predetermined number of data blocks. One of the extents is designated as a current extent, which will be used for writing data. Also, an extent is considered a dirty extent, if the extent contains the most recent updated version of at least one data block (i.e., valid data). Extents may also contain invalid data, i.e., one or more data blocks having a more recent copy in another extent. If an extent does not contain any valid data blocks, the extent is called a clean extent (i.e., all the data blocks in the clean extent have a more recent copy in some other extent). A dirty extent 151 and a current extent 152 are shown for the disk 140 a.

The controller 160 of FIG. 1 uses a log-structured algorithm, according to an embodiment of the invention, to perform I/O operations on the storage device 110 . For example, the controller 160 appends all data updates to a current extent to minimize disk head positioning time. A metadata is kept of data written to the storage device 110 for indicating the locations of the most recent copies of the data blocks. The metadata may indicate the location of the most recent version of a data block and the status of a data block (e.g., valid or invalid). The metadata may be stored in non-volatile memory, such as memory 145 , or in the fast storage sub-array 150 . The controller 160 may maintain the metadata, as described above.

FIG. 2 illustrates updating data block B. Instead of moving a disk head to a location of the data being updated, the update for data block B is written to the end of the current extent 152 (i.e., using the current extent as an append-only log). A metadata is updated to indicate that the previous data block is invalid. The extent containing valid data is marked as dirty (e.g., dirty extent 152 ) in the metadata. The previously-dirty extent 151 may eventually be marked as clean if all the data in that extent becomes invalid. Data may continue to be sequentially written to the current extent 152 until that extent is full, sustaining peak transfer rates for the disk 140 a . Then, another clean extent is selected.

An I/O operation which overwrites a data block may supersede portions of a previously-written extent on a disk, thus making the older extent sparsely populated with valid data. Such extents are transformed into usable empty space by cleaning, which also may be referred to as compacting. One extent may be cleaned at a time.

An extent may be cleaned during idle periods (when there are no I/O operations pending for the fast-store sub-array). The data corresponding to valid blocks in an extent being cleaned (e.g., the dirty extent 151 ) are read from the fast storage sub-array 150 storing a copy of the data in the disk sub-array 140 . By reading data from the fast storage sub-array 150 , the disk head needs not switch between the current extent and the extent being cleaned for cleaning. Furthermore, the fast storage sub-array 150 can read the valid data more efficiently due to its superior access characteristics, without incurring any disk-head seeks on the disk sub-array 140 .

FIG. 2 shows the dirty extent 151 . The dirty extent 151 includes valid data and invalid data. To clean the extent, the valid data (e.g., data blocks A and C) are read from the fast storage sub-array 150 and stored in the buffer 142 . The data blocks A and C may then be written to the end of the current extent 152 . After all the valid data is written to the current extent 152 , the dirty extent 151 is marked as clean in the metadata. Then, the extent 151 may be used as a current extent for appending data.

When the current extent 152 is filled, the nearest clean extent is chosen as the new current extent. If no clean extent is available, the extent with the greatest number of invalid blocks is selected or the controller 160 of FIG. 1 waits for a new clean extent to become available. Since most writes are appended to the current extent, no disk head seeks are required. By keeping data for cleaning in the buffer 142 , the disk 140 a can keep writing at all times (except when moving to a new current extent), thus maximizing its write throughput.

FIG. 3 illustrates a flow diagram of a method 300 for cleaning an extent in a log-structured disk, according to an embodiment of the invention. In step 310 , valid data in an extent being cleaned is identified. In step 320 , an idle time is detected for the fast storage sub-array 150 . An idle time may include a time when the level of activity for the fast storage sub-array 150 falls below a threshold. A timeout may be used to force a copy if an idle time is not detected within a predetermined period of time. In step 330 , a copy of the valid data is retrieved from the fast storage sub-array 150 and stored in the buffer 142 . In step 340 , the data from the buffer 142 is appended to the current extent(s). For example, when the current extent is filled, the nearest clean extent (if available) is chosen as the new current extent. If no clean extent is available, the extent with the greatest number of invalid blocks is selected or the controller 160 of FIG. 1 waits for a new clean extent to become available. According to an embodiment, the steps of the method 300 may be performed by the controller 160 of FIG. 1 .

FIG. 4 illustrates a flow diagram of a method 400 for performing I/O operations on the storage device 110 , according to an embodiment of the invention. The methods 400 – 600 are described below with respect to the computer system 100 shown in FIG. 1 , but may be applied to other systems. In step 405 , the controller 160 receives a request to perform a data operation. The request may be generated by one of the clients 120 .

In step 410 , the controller 160 determines whether the request provokes a write operation on the storage device 110 . Write operations may be provoked by write requests from a client 120 and requests from the controller 160 . If the request provokes a write operation, data is written to the cache 145 (step 420 ). Then, the data is written to the disk sub-array 140 and the fast storage sub-array 150 (steps 430 and 440 ). Data is written to the disk sub-array 140 using the log-structured algorithm. For example, the data is appended to a current extent and corresponding metadata is updated in a log. Write requests may be stored in the cache 145 until the sub-arrays 140 and 150 are available to perform the writes. It will be apparent to one of ordinary skill in the art that write requests from the controller 160 , such as requests for a destaging operation from the cache 145 , cause data to be written to the disk sub-array 140 and the fast storage sub-array 150 from the cache 145 (e.g., steps 430 and 440 ). Data is written to the disk sub-array 140 using the log-structured algorithm.

If a write operation is not found to be necessary in step 410 , the controller 160 determines whether a read operation is provoked (step 435 ). Read operations may be provoked by read requests, read-ahead requests, etc. Read operations may be provoked by requests from a client 120 and/or the controller 160 . In step 435 , if a read operation is provoked, the steps shown in FIG. 5 are performed.

FIG. 5 illustrates a flow diagram of a method 500 for performing a read operation, according to an embodiment of the invention. In step 500 , the controller 160 determines whether the requested data is in the cache 145 (step 505 ). If the requested data is in the cache 145 , the data is read from the cache 145 (step 535 ). If the requested data is not in the cache 145 , the controller 160 determines whether the fast storage sub-array 150 is busy (step 510 ). Generally reads are performed from the fast storage sub-array 150 to improve performance. A threshold may be set to determine whether the fast storage is busy (e.g., a predetermined number of I/O operations are pending for the fast storage sub-array 150 ).

If the fast storage sub-array 150 is not busy, the read is performed from the fast storage sub-array 150 (step 515 ). If the fast storage sub-array 150 is busy, then the controller 160 determines whether the disk sub-array 140 is busy (step 520 ). If the disk sub-array 140 is not busy, then the read is performed from the disk sub-array 140 (step 525 ). If the disk sub-array 140 is also busy, then the read may be performed from any of the sub-arrays 140 and 150 (step 530 ).

For fault recovery and to improve performance of I/O operations, two copies of data are stored in the storage device 110 (one copy on the disk sub-array 140 and one copy on the fast storage sub-array 150 ).

If a fast-storage device fails, the data is available in the disk sub-array 140 . When a fast-storage device is replaced, the data can be copied back from the disk sub-array in an order which is as close to sequential on the disk as possible. The data on the disk is copied back to the fast storage device in the sequential order to minimize disk head movement and to maximize the disk throughput.

If a disk fails, the data is available on the fast storage sub-array 150 . The data can be copied back to another disk from the fast store sub-array 150 when one becomes available, such as immediately if there is a hot spare disk or when the failed disk is replaced if there is not a hot spare. This copy can be made in the order which will cause the fewest disk head movements even if it causes non-contiguous accesses on the fast storage subarray 150 , because the positioning time for the fast-store copy is small.

FIG. 6 illustrates a flow diagram of a method 600 for recovering from a failed disk or fast storage device in the storage device 110 , according to an embodiment of the invention. In the step 605 , the controller 160 determines whether a disk of the disk sub-array 140 failed. Disk failure may be detected using conventional techniques. If a disk is failed, the controller 160 reads corresponding data from the fast storage sub-array 150 into the buffer 142 (step 610 ). Then, the controller 160 writes the data to the operative disk(s) (step 615 ) using the log-structured algorithm, such as appending data to a current extent. An operative disk or fast storage device may include a spare or a replacement.

In step 620 , the controller 160 determines whether a fast storage device of the fast storage sub-array 150 failed. Failure of a fast storage device may be detected using conventional techniques. If a fast storage device is failed, the controller 160 reads corresponding data from the disk(s) 140 into the buffer 142 (step 625 ). Then, the controller 160 writes the data to operative fast storage device(s) (step 630 ).

The steps of the method 600 may be performed in the background, giving priority to external I/O requests. Since the data read goes first into buffer 142 , the reading and writing can proceed asynchronously. For example, the reading can proceed when the device to be written to is busy if there is space in the buffer. Similarly, writing can proceed as long as there is data for that device in the buffer.

The methods 300 – 600 are exemplary embodiments, and it will be apparent to one of ordinary skill in the art that these methods are subject to many alternatives, modifications and variations without departing from the spirit and scope of the invention. For example, some of the steps in the methods 300 – 600 may be performed in different orders or simultaneously. For example, in the method 300 , the step 310 for identifying valid data and the step 320 for determining idle time may be performed in different orders. In the methods 400 and 500 , the controller may simultaneously perform or perform in a different order step(s) for determining whether a read or a write is provoked. In FIG. 4 , the step 430 for writing to disk(s) and the step 440 for writing to fast storage may be performed in parallel. These and other variations will be apparent to one of ordinary skill in the art.

While this invention has been described in conjunction with the specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. There are changes that may be made without departing from the spirit and scope of the invention.