Data protection in a heterogeneous random access storage array

Described herein are embodiments of a process for efficiently allocating RAID stripes across an array of disks (e.g., SSDs). In some embodiments, the process can be used to allocate RAID stripes across a “heterogeneous” storage array (i.e., an array of different sized disks). Also described herein are embodiments of a storage system that utilize said processing.

BACKGROUND

Storage systems may utilize an array of random access storage device such as solid-state drives (SSDs, also known as solid-state disks) to provide high performance scale-out storage.

RAID (Redundant Array of Inexpensive/Independent Disks) can provide increased resiliency and reliability to storage arrays. RAID allows reconstruction of failed disks (and parts of disks) through the use of redundancy. RAID 6 defines block-level striping with double distributed parity (N+2) and provides fault tolerance of two disk failures, so that a storage array can continue to operate with up to two failed disks, irrespective of which two disks fail. The double parity provided by RAID 6 also gives time to rebuild the array without the data being at risk if a single additional disk fails before the rebuild is complete. To provide efficient reads, data is stored “in the clear,” whereas parity information can be based on a suitable coding scheme.

U.S. Pat. No. 8,799,705, issued on Aug. 5, 2014, which is hereby incorporated by reference in its entirety, describes a data protection scheme similar to RAID 6, but adapted to take advantage of random access storage.

Existing RAID techniques may be designed to work with an array of disks having equal storage capacity (or “size”). Over time, disk capacities may increase, making it desirable or even necessary to use larger disks when expanding a storage array. Replacing legacy disks with larger disks can be wasteful.

SUMMARY

Described herein are embodiments of a process for efficiently allocating RAID stripes across an array of disks (e.g., SSDs). In some embodiments, the process can be used to allocate RAID stripes across a “heterogeneous” storage array (i.e., an array of different sized disks). Also described herein are embodiments of a storage system that utilize said processing.

According to one aspect of the disclosure, a method comprises: aggregating chunks of data to fill a stripe with N data chunks; determining free capacity information for a plurality of disks within a storage array; selecting, from the plurality of disks, N+k disks based upon the free capacity information; generating k parity chunks using the N data chunks within the stripe; and writing each of the N data and k parity chunks to a respective one of the N+k disks.

In some embodiments, wherein selecting N+k disks based upon the free capacity information comprises selecting a set of N+k disks having a largest free capacity among the plurality of disks. In certain embodiments, wherein each of the plurality of disks is divided into a plurality of fixed-size chunks, wherein determining free capacity information for a plurality of disks comprises calculating a number of unoccupied chunks within each disk. In one embodiment, selecting a stripe to fill having a largest number of unoccupied data chunks. In certain embodiments, aggregating chunks of data comprises aggregating the chunks of data in a write cache. In some embodiments, the plurality of disks includes a plurality of solid state drives (SSDs). In various embodiments, at least two of the disks within the storage array have different capacities.

According to another aspect of the disclosure, a system comprises a processor and a memory storing computer program code that when executed on the processor causes the processor to execute embodiments of the method described hereinabove.

According to yet another aspect of the disclosure, a computer program product may be tangibly embodied in a non-transitory computer-readable medium, the computer-readable medium storing program instructions that are executable to perform embodiments of the method described hereinabove.

The drawings are not necessarily to scale, or inclusive of all elements of a system, emphasis instead generally being placed upon illustrating the concepts, structures, and techniques sought to be protected herein.

DETAILED DESCRIPTION

Before describing embodiments of the structures and techniques sought to be protected herein, some terms are explained. As used herein, the term “storage system” may be broadly construed so as to encompass, for example, private or public cloud computing systems for storing data as well as systems for storing data comprising virtual infrastructure and those not comprising virtual infrastructure. As used herein, the terms “client” and “user” may refer to any person, system, or other entity that uses a storage system to read/write data.

As used herein, the term “storage device” may refer to any non-volatile memory (NVM) device, including hard disk drives (HDDs), flash devices (e.g., NAND flash devices), and next generation NVM devices, any of which can be accessed locally and/or remotely (e.g., via a storage attached network (SAN)). The term “storage array” may be used herein to refer to any collection of storage devices. In some embodiments, a storage array may provide data protection using RAID 4, RAID 5, RAID 6, or the like.

As used herein, the term “random access storage device” may refer to any non-volatile random access memory (i.e., non-volatile memory wherein data can be read or written in generally the same amount of time irrespective of the physical location of data inside the memory). Non-limiting examples of random access storage devices may include NAND-based flash memory, single level cell (SLC) flash, multilevel cell (MLC) flash, and next generation non-volatile memory (NVM). For simplicity of explanation, the term “disk” may be used synonymously with “storage device” herein.

While vendor-specific terminology may be used herein to facilitate understanding, it is understood that the concepts, techniques, and structures sought to be protected herein are not limited to use with any specific commercial products.

FIG. 1shows a storage system100according to an illustrative embodiment of the disclosure. The storage system100may include a plurality of components102a-102d(generally denoted102herein), and a storage array106comprising a plurality of disks108a. . .108n(generally denoted108herein). In some embodiments, the disks108correspond to SSDs. In various embodiments, the storage array106is heterogeneous, meaning that the disks108may have different storage capacities (or “sizes”).

In the embodiment shown, the system components include a routing subsystem102a, a control subsystem102b, a data subsystem102c, and a write cache102d. In one embodiment, the components102may be provided as software components, i.e., computer program code that, when executed on a processor, may cause a computer to perform functionality described herein. In a certain embodiment, the storage system100includes an operating system (OS) and one or more of the components102may be provided as user space processes executable by the OS. In other embodiments, a component102may be provided, at least in part, as hardware such as digital signal processor (DSP) or an application specific integrated circuit (ASIC) configured to perform functionality described herein.

The routing subsystem102amay be configured to receive read and write requests from clients116using, for example, an external application programming interface (API) and to translate client requests into internal commands. In some embodiments, the routing subsystem102ais configured to receive Small Computer System Interface (SCSI) commands from clients. In certain embodiments, the system100may store data in fixed-size chunks, for example 4K chunks, where each chunk may have a unique hash value (referred to herein as a “chunk hash”). In such embodiments, the routing subsystem102amay be configured to split data into fixed-size chunks and to calculate the corresponding chunk hashes. In one embodiment, chunk hashes are calculated using Secure Hash Algorithm 1 (SHA-1) processing. In some embodiments, a chunk corresponds to a fixed number of contiguous blocks within a storage device.

The control subsystem102bmay be configured to maintain a mapping between I/O addresses associated with data and the corresponding chunk hashes. As shown inFIG. 1, this mapping may be maintained using a data structure112, referred to herein as an “I/O address to chunk hash mapping table” or “A2H table,” according to some embodiments. In one embodiment, I/O addresses may be logical addresses used by clients to access data within the storage system100.

The data subsystem102cmay be configured to maintain a mapping between chunk hashes and physical storage addresses (i.e., storage locations within the storage array106and/or within individual disks108). As shown inFIG. 1, this mapping may be maintained as a data structure114, referred to herein as a “hash to physical address mapping table” or “H2P table,” according to some embodiments. The data subsystem102cmay also be configured to read and write data from/to the storage array106(and/or to individual disks108therein). In some embodiments, the data subsystem102cmay access the storage array106via a driver or other type of interconnect.

As shown, in some embodiments, the system may include a write cache102dthat may be configured to cache content data prior to writing to the storage array106. Thus, the data subsystem102cmay be configured to send writes to the write cache102dand, once enough writes have been collected, to commit the writes to disk108. In one embodiment, the write cache102dmay form a portion of the data subsystem102c.

It will be appreciated that combinations of the A2H112and H2P114tables can provide multiple levels of indirection between the logical (or “I/O”) address a client116uses to access data and the physical address where that data is stored. Among other advantages, this may give the storage system100freedom to move data within the storage array106without affecting a client's116access to that data (e.g., if a disk108fails).

In various embodiments, the storage system100may provide data protection through redundancy such that if a disk108fails, the data stored therein may be recovered using information stored within other disks of the storage array106to a replacement disk. In certain embodiments, the storage system may be configured to provide double parity data protection. Thus, the storage system100may be able to tolerate the loss of at least two disks108concurrently. In one embodiment, data subsystem102cmay implement a data protection scheme similar to RAID 6, but adapted to take advantage of random access storage. In various embodiments, the storage system100can use data protection techniques described within U.S. Pat. No. 8,799,705, issued on Aug. 5, 2014, which is hereby incorporated by reference in its entirety.

Unlike some existing RAID systems, the storage system100may use fine granularity to obviate the need to keep dedicated spare disk space, according to some embodiments. In particular, the disks108can be logically divided into relatively small chunks (e.g., 4K chunks). A RAID stripe includes of N+k such chunks, N of which comprise data (e.g., user data or other content) and k of which comprise parity information calculated based on the N chunks. Because data is stored in relatively small chunks, a single write request received from a client116can result in many writes to the disk array106. Moreover, updating any chunk within a stripe may require updating the k parity chunks.

According to some embodiments, the data subsystem102cmay aggregate chunk writes using the write cache102d, which caches content data prior to writing to the disk array106. In some embodiments, the data subsystem102cmay seek to aggregate enough chunks to fill a stripe so that an entire stripe can be written to disk(s) at the same time, thereby minimizing the number of parity updates. The data subsystem102ccan choose to write aggregated data to a new stripe or to an existing stripe with unused chunks (or “holes”). Such holes can result from client116updates when content-based addressing is used: if a client116updates the same I/O address with different content, a new chunk hash may be calculated that results in the data being written to a different physical storage location. In one embodiment, the data subsystem102may select an existing stripe with the largest number of unused (or “unoccupied”) disk chunks. In some embodiments, the stripe size can be dynamic. For example, a maximum stripe size may be defined (e.g., 23+2) and, if no such stripes are available when writing (due to holes created by “old” blocks), a smaller stripe size can be used (e.g., 10+2).

In various embodiments, the data subsystem102cmay be configured to use a data protection scheme that does not require equal-sized disks108, embodiments of which are described below in conjunction withFIGS. 2 and 3.

In some embodiments, the system100includes features used in EMC® XTREMIO®.

FIG. 2illustrates a process for data protection in a heterogeneous random access storage array, according to embodiments of the disclosure. A storage array200includes a plurality of disks (referred to generally herein as disks202), with six (6) disks202a-202fshown in this example. In one embodiment, a storage array200includes at least twenty five (25) disks202.

Each disk202has a given capacity, which may be the same as or different from any other disk202. A disk202may logically be divided up into relatively small fixed-size chunks (e.g., 4K chunks). In the simplified example ofFIG. 2, disks202aand202dare assumed to have capacity to store six (6) chunks each, disks202band202care assumed to have capacity to store ten (10) chunks each, and disks202eand202fare assumed to have capacity to store thirteen (13) chunks each. In practice, each disk202may be capable of storing millions of chunks.

The process can provide N+k RAID protection, while utilizing the available capacity of disks202. In an embodiment, most or all of the capacity can be utilized. A stripe may include N data chunks (denoted inFIG. 2as DS,0, DS,1, . . . DS,Nfor some stripe S) and k parity chunks (denoted inFIG. 2as PS,0, PS,1, . . . PS,kfor some stripe S). In the embodiment shown, N=3 and k=2. Each disk202may be split up into relatively small chunks. Each chunk may be either occupied by a data chunk (“D”), a parity chunk (“P”), or is unoccupied (denoted using hatching inFIG. 2). For example, in the example shown, a first disk202amay include two data chunks D1,0and D2,2and four unoccupied chunks.

For a given stripe, each of its N+k chunks should be stored on different disks202to provide the desired RAID protection. This is illustrated byFIG. 2, where three stripes (S=1, S=2, and S=3) each have five chunks stored across five different disks202. For example, stripe S=1 has a first data chunk D1,0on disk202a, a second data chunk D1,1on disk202b, a third data chunk D1,2on disk202d, a first parity chunk P1,0on disk202d, and a second parity chunk P1,1on disk202e.

For L disks, there are

(LN+k)
(“L choose N+k”) possible layouts for a stripe. The choice of which disks202are used to store individual stripes can affect allocation efficiency over the entire array200. Choosing the optimal layout for a given stripe can be viewed as an optimization problem that may increase in complexity as the number of disks L increases and/or as the stripe size N+k approaches L/2.

To reduce complexity, a heuristic for chunk allocation may be used in some embodiments. Consider each disk202as a pool of X fixed-size chunks, where X may vary between disks202. Per stripe, choose N+k disks202across which to store the stripe based upon the amount of free (or “unused”) capacity within each disk202. In some embodiments, free capacity is measured as the number of unoccupied chunks on a disk. In certain embodiments, free capacity is measured as a percentage (e.g., a percentage of chunks that are unoccupied). When writing a stripe, the set of N+k disks that have largest free capacity may be used.

In some embodiments, the data subsystem102ckeeps track of which stripes are allocated to which disks202. In one embodiment, the data subsystem102ctracks the number of unoccupied chunks per disk202.

As an example, assume that the data subsystem102c(FIG. 1) is ready to write a stripe to a storage array200in the state shown inFIG. 2. The data subsystem102cmay have collected enough writes in the write cache102dto fill a stripe. The chunk allocation heuristic determines that disk202ahas four (4) unoccupied chunks, disk202bhas six (6) unoccupied chunks, disk202chas six (6) unoccupied chunks, disk202dhas three (3) unoccupied chunks, disk202ehas nine (9) unoccupied chunks, and disk202fhas ten (10) unoccupied chunks. Thus, in some embodiments, for N=3 and k=2, the five (5) disks with the largest free capacity are202f,202e,202c,202b, and202a(in order of available chunks from highest to lowest and assuming free capacity is measured by available chunks). The data subsystem102cmay write the N data chunks and k parity chunks to those disks, one chunk per disk.

FIG. 3is a flow diagram showing illustrative processing that can be implemented within a storage system, such as storage system100ofFIG. 1. Rectangular elements (typified by element302inFIG. 3), herein denoted “processing blocks,” represent computer software instructions or groups of instructions. Alternatively, the processing and decision blocks may represent steps performed by functionally equivalent circuits such as a digital signal processor (DSP) circuit or an application specific integrated circuit (ASIC). The flow diagrams do not depict the syntax of any particular programming language. Rather, the flow diagrams illustrate the functional information one of ordinary skill in the art requires to fabricate circuits or to generate computer software to perform the processing required of the particular apparatus. It should be noted that many routine program elements, such as initialization of loops and variables and the use of temporary variables are not shown. It will be appreciated by those of ordinary skill in the art that unless otherwise indicated herein, the particular sequence of blocks described is illustrative only and can be varied without departing from the spirit of the concepts, structures, and techniques sought to be protected herein. Thus, unless otherwise stated the blocks described below are unordered meaning that, when possible, the functions represented by the blocks can be performed in any convenient or desirable order.

FIG. 3illustrates a process300for allocating chunks to a stripe, according to embodiments of the disclosure. In the embodiment shown, the process300may seek to aggregate enough chunks to fill a stripe and then to write the entire stripe to disk(s) at the same time. Thus, at block302, the process may begin by selecting a stripe to be filled. The selected stripe could be an existing stripe with unused chunks, or it could be a new stripe. In one embodiment, the process may select an existing stripe with the largest number of unused chunks.

At block304, requests to write chunks of data may be received. In some embodiments, the requests may be received in response to user/client writes. At block306, writes may be aggregated until there are enough writes to fill the stripe with N data chunks. In some embodiment, the process can aggregate N−M writes, where N is the number of data chunks that can be stored within the stripe and M is the number of those chunks that are currently occupied. In some embodiments, writes can be aggregated using a write cache102d(FIG. 1).

At block308, the free capacity of each disk within a storage array may be determined. In some embodiments, a disk's free capacity is measured as the number of unoccupied chunks on that disk.

At block310, N+k disks may be selected using the disk free capacity information. In the embodiment shown, the set of N+k disks with the largest free capacity may be selected. At block312, k parity chunks may be generated using the N data chunks within the stripe (i.e., the data chunks aggregated at block306in addition to any existing data chunks within the stripe). Any suitable technique can be used to generate the parity chunks. At block314, the N data chunks and the k parity chunks may be written to the selected N+k disks. In some embodiments, one chunk may be written to each of the selected N+k disks.

FIG. 4shows an illustrative computer (e.g., physical or virtual) or other processing device400that can perform at least part of the processing described herein. In some embodiments, the computer400forms a part of a storage system, such as storage system100ofFIG. 1. The computer400may include a processor402, a volatile memory404, a non-volatile memory406(e.g., hard disk or SSD), an output device408and a graphical user interface (GUI)410(e.g., a mouse, a keyboard, a display, for example), each of which is coupled together by a bus418. The non-volatile memory406is configured to store computer instructions412, an operating system414, and data416. In one embodiment, the computer instructions412are executed by the processor402out of volatile memory404. In some embodiments, an article420comprises non-transitory computer-readable instructions.

In the embodiment shown, computer instructions412may include routing subsystem instructions412athat may correspond to an implementation of a routing subsystem102a(FIG. 1), control subsystem instructions412bthat may correspond to an implementation of a control subsystem102b, data subsystem instructions412cthat may correspond to an implementation of a data subsystem102c, and write cache instructions412dthat may correspond to an implementation of a write cache102d. As shown, in some embodiments, non-volatile memory406may be configured to store data416aused by a write cache102d. In certain embodiments, write cache data416amay be stored in volatile memory404.

Having described certain embodiments, which serve to illustrate various concepts, structures, and techniques sought to be protected herein, it will be apparent to those of ordinary skill in the art that other embodiments incorporating these concepts, structures, and techniques may be used. Elements of different embodiments described hereinabove may be combined to form other embodiments not specifically set forth above and, further, elements described in the context of a single embodiment may be provided separately or in any suitable sub-combination. Accordingly, it is submitted that scope of protection sought herein should not be limited to the described embodiments but rather should be limited only by the spirit and scope of the following claims.