Systems and methods for sequential resilvering

Implementations claimed and described herein provide systems and methods for the efficient rebuilding of a failed storage device through sequential resilvering. In one implementation, blocks for resilvering are discovered. The blocks correspond to input/output requests not successfully completed for a failed storage device. A coarse grained sorting of the blocks is performed based on a block location of each of the blocks on the failed storage device. The block locations of the blocks are stored in memory according to the coarse grained sorting. A fine grained sorting of the blocks is performed based on the coarse grained sorting of the blocks. The blocks are sequentially resilvered based on the fine grained sorting.

TECHNICAL FIELD

Aspects of the present disclosure relate to data storage systems, and in particular, to systems and methods for rebuilding a failed disk or other storage device in a data storage system.

BACKGROUND

The continuous expansion of the Internet, the expansion and sophistication of enterprise computing networks and systems, the proliferation of content stored and accessible over the Internet, and numerous other factors continue to drive the need for large sophisticated data storage systems. Consequently, as the demand for data storage continues to increase, larger and more sophisticated storage systems are being designed and deployed. Many large scale data storage systems utilize storage appliances that include arrays of storage media. These storage appliances are capable of storing incredible amounts of data. For example, at this time, Oracle's SUN ZFS Storage 7420 appliance can store over 2 petabytes of data (over 2 quadrillion bytes of data). Moreover, multiple storage appliances may be networked together to form a cluster, which allows for an increase in the volume of stored data.

Typically, these storage systems include a file system for storing and accessing files. In addition to storing system files (operating system files, device driver files, etc.), the file system provides storage and access of user data files. If any of these files (system files and/or user files) contain critical data, then it becomes advantageous to employ a data backup scheme to ensure that critical data is not lost if a file storage device fails. One data backup scheme that is commonly employed is mirroring. Mirroring involves maintaining two or more copies of a file, where each copy of the file is located on a separate file storage device (e.g., a local hard disk, a networked hard disk, a network file server, etc.). For example, storage appliances arranged in a cluster may be configured to mirror data so that if one of the storage appliances becomes inoperable, the data is available at another storage location.

When one or more file storage devices fails for any length of time, the file storage device(s) may become unsynchronized. However, when employing a mirroring scheme, the mirrors should be synchronized (i.e., the contents of each mirror are the same) to ensure critical data is backed up. If a mirror becomes unsynchronized, the simplest recovery scheme involves copying all of the data from a synchronized mirror to the unsynchronized mirror. However, copying all data from one file storage device to another file storage device may take a long time and reduce performance of the file storage devices significantly during the resynchronization process.

SUMMARY

Implementations described and claimed herein address the foregoing problems by providing systems and methods for efficient rebuilding of a failed data storage device. In one implementation, blocks for resilvering are discovered. The blocks correspond to input/output requests not successfully completed for a failed storage device. A coarse grained sorting of the blocks is performed based on a block location of each of the blocks on the failed storage device. The block locations of the blocks are stored on disk according to the coarse grained sorting. A fine grained sorting of the blocks is performed based on the coarse grained sorting of the blocks. The blocks are sequentially resilvered based on the fine grained sorting.

In another implementation, blocks are discovered for resilvering. An object array having a first temporary object is stored on disk, and a first subset of the blocks is sorted into the first temporary object based on a block location of each of the blocks. Each of the blocks in the first temporary object is read into a sorted tree and is sequentially resilvered based on the sorted tree. The first temporary object is deleted following the sequential resilvering of the blocks in the first subset.

In still another implementation, a storage pool having a plurality of storage devices configured to store data is in communication with a file system. The file system has at least one processor configured to identify a failed device in the plurality of storage devices. The failed device corresponds to blocks for which input/output requests were not successfully completed. The at least one processor of the file system is further configured to sequentially resilver the blocks based on a plurality of sorted trees. Each of the sorted trees corresponds to one of a plurality of temporary objects in an object array.

DETAILED DESCRIPTION

Aspects of the presently disclosed technology relate to systems and methods for sequential resilvering. When a disk in a storage pool fails, the data from the failed disk needs to be rebuilt on a spare disk as quickly as possible. A resilver is performed by traversing the data in a logical block order. File systems utilizing a copy-on-write transactional object model, such as Oracle's SUN ZFS storage appliances, generally reconstruct the data according to when the block was written. Copy-on-write involves all block pointers within the filesystem containing a checksum or hash of a target block, which is verified when the block is read. Rather than overwriting blocks containing active data in place, a new block is allocated, modified data is written to the new block, and any metadata blocks referencing the block are similarly read, reallocated, and written. Stated differently, when a block is updated with new data, it is written to a new location.

Conventional resilvering generally involves traversing metadata, issuing a repair I/O, traversing the next metadata, and so on. As such, file systems using copy-on-write, for example, may experience small random Input/Outputs (I/O's) to the drive during conventional resilvering, increasing resilvering time. Accordingly, in one aspect of the present disclosure, each block is described by a block id (i.e. the number of the block within a file or object). The block id is then mapped to a Data Virtual Address (DVA), which maps to a specific location on disk. During resilvering, the block locations are recorded on disk, the block locations are read and sorted, and the blocks are resilvered sequentially, thereby resulting in larger, sequential I/O's and significantly reduced resilvering times (e.g., a quarter of conventional resilvering times). Stated differently, in one aspect of the presently disclosed technology, resilvering is performed in two phases: a populating phase and an iterating phase. During the populating phase, an array of on-disk objects (buckets) is created. The number of buckets in the array is based on the amount of memory. For each block pointer that is on the disk to be resilvered, a disk offset describing the block location is appended to one of the buckets. The object written is based on the DVA offset. The iterating phase involves reading the block pointers in one of the buckets into a sorted tree (e.g., an Adelson Velskii Landis (AVL) tree) by block location disk offset. The AVL tree corresponds to a partially-balanced binary tree. The block pointers are then resilvered sequentially based on the sorted tree. The bucket is deleted, and the block pointers in the next bucket in the array are sorted. The iterating phase is repeated until all the buckets are deleted.

For example, for a 200 GB disk, 200 array buckets may be created. Any block that falls within the first 1 GB of the disk will be sorted into the first bucket, any block that falls within the second 1 GB of the disk will be sorted into the second bucket, and so on until the 200 GB disk is sorted into buckets. The blocks in the first bucket are sorted into a sorted tree based on block location disk offset, and all of the blocks in the first bucket are sequentially resilvered. As such, all of the blocks residing in the first 1 GB of the disk is sequentially written. This is repeated for the second 1 GB of the disk until all of the blocks are resilevered for the 200 GB disk.

While the various example implementations discussed herein reference mirrored storage appliances, it will be appreciated that the presently disclosed technology may be implemented in another computing contexts for rebuilding or copying data. Those skilled in the art will also appreciate that resilvering I/O requests may also be used to resilver one or more disks in the storage pool, where the data (or metadata) is stored in the storage pool using a Redundant Array of Inexpensive Disks (RAID) scheme. If the data (or metadata) is stored using a RAID scheme, then resilvering the disk may correspond to first reconstructing the data (or metadata) in accordance with the RAID scheme and then issuing a resilvering I/O to write the reconstructed data (or metadata) to the appropriate disk in the storage pool.

FIG. 1is an example network file system100implementing sequential resilvering systems and methods. In one implementation, the system100includes an application102interfacing with an operating system104. The operating system104includes functionality to interact with a file system106, which in turn interfaces with a storage pool118. The operating system104typically interfaces with the file system106via a system call interface108. The operating system104provides operations for users to access files within the file system106. These operations may include read, write, open, close, or the like. In one implementation, the file system106is an object-based file system (i.e., both data and metadata are stored as objects). More specifically, the file system106includes functionality to store both data and corresponding metadata in the storage pool118.

In one implementation, operations provided by the operating system104correspond to operations on objects. Stated differently, a request to perform a particular operation (i.e., a transaction) is forwarded from the operating system104, via the system call interface108, to a data management unit (DMU)110. In one implementation, the DMU110translates the request to perform an operation on an object directly to a request to perform a read or write operation (i.e., an I/O request) at a physical location within the storage pool118. A storage pool allocator (SPA)112receives the request from the DMU110and writes the blocks into the storage pool118. In one implementation, the storage pool118includes one or more physical disks120. . .120N. The storage capacity of the storage pool118may increase and decrease dynamically as physical disks120are added and removed from the storage pool118. In one implementation, the SPA112manages the storage space available in the storage pool118.

In one implementation, the SPA112includes an I/O manager116and other modules114, which may be used by the SPA112to read data from and/or write data to the storage pool118. In one implementation, the I/O management module114receives I/O requests and groups the I/O requests into transaction groups. The other modules114may include, without limitation, a compression module, an encryption module, a checksum module, and a metaslab allocator. The compression module compresses larger logical blocks into smaller segments, where a segment is a region of physical disk space. In one implementation, the encryption module provides various data encryption algorithms. The data encryption algorithms may be used, for example, to prevent unauthorized access. In one implementation, the checksum module calculates a checksum for data and metadata within the storage pool118. The checksum may be used, for example, to ensure data has not been corrupted. As discussed above, the file system106provides an interface to the storage pool118and manages allocation of storage space within the storage pool118. In one implementation, the SPA112uses the metaslab allocator to manage the allocation of storage space in the storage pool118.

Copy-on-write transactions may be performed for a data write request to a file. In one implementation, all write requests cause new segments to be allocated for the modified data. Thus, retrieved data blocks and corresponding metadata are never overwritten until a modified version of the data block and metadata is committed. Stated differently, the DMU110writes all the modified data blocks to unused segments within the storage pool118and subsequently writes corresponding block pointers to unused segments within the storage pool118. To complete a copy-on-write transaction, the SPA112issues an I/O request to reference the modified data block. Where one of the disks120. . .120N fails, an I/O request may not be successfully completed (i.e., the data was not stored on disk). The file system106may provide various systems and methods for identifying a failed disk and discovering blocks for resilvering. For example, a dirty time log may be maintained by the SPA112for the storage pool118with each entry identifying a failed disk and when the failed disk was offline or for individual disks120with entries tracking which I/O requests were not successfully completed to a disk120.

As can be understood fromFIG. 1, in one implementation, when one of the disks120. . .120N in the storage pool118fails, the file system106activates a spare disk for the data on the failed disk120to be reconstructed on the spare disk120N. The file system106discovers block locations corresponding to data stored on the failed disk120. The block locations are recorded on disk. Coarse sorting is performed where the blocks are sorted based on the block locations into one or more buckets based on the amount of disk memory. Fine grained sorting is performed on a first of the buckets where the blocks in the first bucket are sorted into an Adelson Velskii Landis (AVL) tree. The blocks are then sequentially resilvered based on the block location. Once all the blocks in the first bucket are resilvered, the bucket is deleted, and the blocks in the next bucket are sorted at a fine grained level. This process is repeated until all the blocks in each of the buckets are resilvered.

Stated differently, the file system106creates an array of on-disk objects. The number of objects in the array is based on the amount of memory in the disk120. For each block that is on the failed disk120, a disk offset describing the block location is appended to one of the objects, and the object written is based on the DVA offset. The file system106reads the blocks in the object into a sorted tree (e.g., an AVL tree) by block location disk offset. The AVL tree corresponds to a partially-balanced binary tree. The file system106sequentially resilvers the blocks based on the sorted tree. The file system106deletes the object and sorts the blocks in the next object in the array. The file system106repeats this until all the objects in the array are deleted.

FIG. 2is an example file200with sequential data. In one implementation, the file200includes blocks202-208. As can be understood fromFIG. 2, each of the blocks has a corresponding block id210, DVA offset212, and block on disk214. For example, the block id210for the blocks202-208is 0, 1, 2, and3, respectively, and the block on disk214for the blocks202-208is0,1,2,3, respectively. Accordingly, a resilver of the file200would be relatively efficient because the block on disk214is sequential for the blocks202-208:0,1,2,3.

In contrast, as can be understood fromFIG. 3, which illustrates an example file300after subsequent operations rewriting one block, a resilver of the file300will result in small random I/O's to the drive. In one implementation, the file300includes blocks302-308with one block rewritten. As can be understood fromFIG. 3, each of the blocks has a corresponding block id310, DVA offset312, and block on disk314. For example, the block id310for the blocks302-308is0,1,2, and3, respectively, and the block on disk314for the blocks302-308is1,3,4,5, respectively. Accordingly, a resilver of the file300would be relatively inefficient and result in small I/O's to the drive because the block on disk314is not sequential for the blocks302-308, with the order in which the blocks would be read and rewritten being:4,1,5,3.

To reduce random I/O's to the drive120, the file system106sorts and sequentially resilvers the data in the file300. Due to limited memory, in one implementation, the file system106does not sort all data at once. Instead, as can be understood fromFIG. 4, the file system106first performs a coarse grained sorting of the blocks302-308. Stated differently, the file system106traverses the failed disk120and sorts the blocks302-308into an array400of temporary objects (e.g., buckets402-404) based on the DVA312of the blocks302-308. Each of the buckets402-404is a temporary object that is appended to during the traverse. This temporary object can be stored persistently on disk and therefore does not need to be held in memory. In one implementation, the number of buckets402. . .404in the array400is based on a percentage of the amount of disk memory. For example, a 300 GB disk may be divided into five 60 GB buckets. The file system106sorts the blocks302-308into one of the buckets402-404based on the physical location of the block on the disk using the DVA312. In an example implementation, for the file300, any block with a DVA offset312of 0x0-0xeffffffff is sorted into a first bucket; any block with a DVA offset of 0xf00000000-0x1e00000000 is sorted into a second bucket; and so on.

Turning toFIG. 5, the file system106performs a fine grained sorting of the blocks. In one implementation, the file system106sorts the blocks in the first bucket402into a sorted tree500by block location disk offset. For example, for the file300, during fine grained sorting, the first bucket402having blocks with the DVA offset312of 0x0-0xeffffffff is sorted into the sorted tree500. In one implementation, the sorted tree500is an AVL tree. The file system106sequentially resilvers the blocks in the first bucket402based on the sorted tree500. Once all the blocks in the bucket402are resilvered, the file system106deletes the bucket402and sorts the blocks in the next bucket in the array400. For example, for the file300, the second bucket having a DVA offset312of 0xf00000000-0x1e00000000 are fine grained sorted and sequentially resilvered. The file system106repeats this until all the buckets402-404in the array400are deleted.

In one implementation, because the file system106may still issue writes to the storage pool118during resilvering operations, a block may no longer exist by the time it is to be resilvered, as shown inFIG. 3. Such freed blocks do not need resilvering, and thus in one implementation, are appended to the bucket402or removed during fine grained sorting.

FIG. 6illustrates example operations600for sequential resilvering. In one implementation, an operation602discovers blocks for resilvering. The operation602discovers the blocks by identifying a failed drive and traversing the data at a logical level. The operation602tracks each block in the failed disk and its corresponding DVA offset indicating a physical location of the block on the disk.

An operation604sorts the blocks into one or more buckets based on the DVA, and an operation606sorts each of the blocks in a first of the buckets into a sorted tree. An operation608resilvers the blocks in the first bucket sequentially by traversing the sorted tree. An operation610deletes the first bucket and the operations606-610are repeated until all the buckets are deleted.

As can be understood fromFIG. 7, a storage server702may be connected to one or more storage appliances706,708. Persistent memory704may be attached to the storage server702. The persistent memory704may include any persistent type of memory, such as a conventional spinning disk hard drive or a solid state hard drive.

The storage server702may be configured to direct data to and from the storage appliances706,708according to the systems and methods described herein. In one implementation, the storage server702may be configured to operate according to the NFS protocol. One or more clients710,712may have a need for data that is stored on one of the storage appliances706,708. The clients710,712may connect to the storage server702using the network714and request the data. The storage server702may then facilitate the transfer of the data from the storage appliances706,708to the requesting client(s)710,712. This may include acting as an intermediary by retrieving the data from the storage appliances706,708, temporarily holding it on the storage server702, and then forwarding the data over the network714to the client(s)710,712. In other cases, the storage server702may provide the client with information on how to obtain the data directly from the storage appliance706,708. For example, the storage server702may provide the client(s)710,712with metadata corresponding to the requested data stored on the storage appliance706,708. The metadata may include information regarding the location of the data in the storage appliance706,708. For example, in the case where the storage appliance706,708is a ZFS storage appliance, the metadata may include location information, such as in which zpool or virtual device the data is stored and any other information regarding the location of the data.

In one implementation, the storage server702includes the file system106configured to facilitate copy-on-write transactions to and from the storage appliances706,708. Where there is a failure of a storage device (e.g., one or more disks in the storage appliances706and708), the storage server702creates an array of on-disk objects. For each block that is on the failed device, a disk offset describing the block location is appended to one of the objects, and the object written is based on the DVA offset. The storage server702reads the blocks in the object into a sorted tree (e.g., an AVL tree) by block location disk offset. The storage server702sequentially resilvers the blocks based on the sorted tree. The storage server702deletes the object and sorts the blocks in the next object in the array. The storage server702repeats this until all the objects in the array are deleted.

Referring toFIG. 8, a general purpose computer system800includes one or more computing devices capable of executing a computer program product to execute a computer process. Data and program files may be input to the computer system800, which reads the files and executes the programs therein. Some of the elements of the general purpose computer system800are shown inFIG. 8, wherein a processor802is shown having an input/output (I/O) section804, a Central Processing Unit (CPU)806, and memory808.

There may be one or more processors802, such that the processor802of the computer system800comprises the CPU806or a plurality of processing units, commonly referred to as a parallel processing environment. The computer system800may be a conventional computer, a distributed computer, or any other type of computer, such as one or more external computers made available via a network architecture, for example as described with respect toFIG. 8. The presently described technology is optionally implemented in software devices loaded in the memory808, stored on a configured DVD/CD-ROM810or a storage unit812, and/or communicated via a wired or wireless network link814on a carrier signal, thereby transforming the computer system800inFIG. 8to a special purpose machine for implementing the operations described herein.

The I/O section804is connected to one or more user-interface devices (e.g., a keyboard816and a display unit818), the storage unit812, and a disk drive820. In one implementation, the disk drive820is a DVD/CD-ROM drive unit capable of reading the DVD/CD-ROM810, which typically contains programs and data822. In another implementation, the disk drive820is a solid state drive unit.

Computer program products containing mechanisms to effectuate the systems and methods in accordance with the presently described technology may reside in the memory804, on the storage unit812, on the DVD/CD-ROM810of the computer system800, or on external storage devices made available via a network architecture with such computer program products, including one or more database management products, web server products, application server products, and/or other additional software components. Alternatively, the disk drive820may be replaced or supplemented by a floppy drive unit, a tape drive unit, or other storage medium drive unit. The network adapter824is capable of connecting the computer system800to a network via the network link814, through which the computer system800can receive instructions and data embodied in a carrier wave. An example of such systems is personal computers. It should be understood that computing systems may also embody devices such as Personal Digital Assistants (PDAs), mobile phones, tablets or slates, multimedia consoles, gaming consoles, set top boxes, etc.

When used in a LAN-networking environment, the computer system800is connected (by wired connection or wirelessly) to a local network through the network interface or adapter824, which is one type of communications device. When used in a WAN-networking environment, the computer system800typically includes a modem, a network adapter, or any other type of communications device for establishing communications over the wide area network. In a networked environment, program modules depicted relative to the computer system800or portions thereof, may be stored in a remote memory storage device. It is appreciated that the network connections shown are examples of communications devices for and other means of establishing a communications link between the computers may be used.

In an example implementation, data resilvering software and other modules and services may be embodied by instructions stored on such storage systems and executed by the processor802. Some or all of the operations described herein may be performed by the processor802. Further, local computing systems, remote data sources and/or services, and other associated logic represent firmware, hardware, and/or software configured to control data access. Such services may be implemented using a general purpose computer and specialized software (such as a server executing service software), a special purpose computing system and specialized software (such as a mobile device or network appliance executing service software), or other computing configurations. In addition, one or more functionalities of the systems and methods disclosed herein may be generated by the processor802and a user may interact with a Graphical User Interface (GUI) using one or more user-interface devices (e.g., the keyboard816, the display unit818, and the user devices804) with some of the data in use directly coming from online sources and data stores.