Patent Description:
RAID systems and RAID methods are commonly used in storage media such as servers storing important data. Various configurations are possible such as a method of simply distributing data across storage media during the input/output of data or the copying/storing of data. In addition to payload data, RAID systems and RAID methods may also store parity information (hereafter, 'parity') in one or more of the storage media storing data. Thus, should an error occur in the stored data (whether stored across the storage media or another storage medium), it may be appropriately restored. As a result, a RAID may increase data stability by preventing data loss and balance input/output (I/O) operations, thereby improving overall server performance.

As will be appreciated by those skilled in the art, a number of RAID configurations are widely used. For example, in a so-called RAID level <NUM> or RAID level <NUM> system, data is distributed and stored across storage media and parity bits are used in the systems to ensure data integrity. That is, in RAID level <NUM>, one parity bit per data chunk is distributed and stored, and in RAID level <NUM>, two parity bits per data chunk are distributed and stored. However, when a RAID level <NUM> or RAID level <NUM> system is used, since it includes one or two spare storage regions, a rebuild process must be performed on a corresponding spare storage region when a data failure occurs.

Here, the rebuild process may generate lost data by accessing parity bits and data included across the entire RAID system. Accordingly, the rebuild process requires considerable time and may significantly influence the overall I/O performance of the RAID system due to the use of system resources during the rebuild process.

<CIT> discloses: A data storage system includes a controller, a hot spare storage device and a plurality of primary storage devices. The controller utilizes the hot spare storage device to mirror only a subset of each stripe of logical pages written across the data storage array, where the subset includes a logical page determined by a write input/output operation (IOP) policy. In response to receipt of a write IOP, the controller writes a stripe including a plurality of logical data pages and a logical data protection page across the plurality of primary storage devices and mirrors the logical page determined by the write IOP policy on the hot spare storage device. In response to a failure of a storage device among the plurality of primary storage devices, contents of the failed storage device not already mirrored on the hot spare storage device are rebuilt on the hot spare storage device.

<NPL>, discloses high performance and high reliability RAIS5 storage architecture with adaptive stripe.

<CIT> introduces an apparatus for a redundant array of independent disk (RAID) reconstruction, at least including a RAID group and a processing unit. The processing unit starts an unused-space scan procedure to determine a logical address range that is a candidate to be skipped for the RAID group and send the logical address range to a stripe reconstruction procedure; and starts the stripe reconstruction procedure to receive the logical address range from the unused-space scan procedure, determine a stripe of drives of the RAID group to be skipped from being reconstructed according to the logical address range, and omit a reconstruction to the determined strip.

Embodiments of the invention provide redundant array of independent disks (RAID) storage devices, host devices and RAID systems capable of reducing the execution time for a rebuild process, and reducing the overall number of input/output (I/O) required for the rebuild operation by accessing and rebuilding data only in an actually used region.

Embodiments of the present invention are defined in the appended claims.

Certain embodiments of the invention are illustrated, wholly or in relevant part, in the accompanying drawings.

In the written description that follows, terms such as "unit" or "module" denote one or more functional block(s), some of which may be illustrated in the accompanying drawings, that may be implemented in hardware, software or a combination of hardware/software, and that may be variously configured to perform one or more function(s).

Exemplary redundant array of independent disks (RAID) systems according to embodiments of the invention will now be described with reference to <FIG>.

Figure (<FIG> is a block diagram illustrating a RAID system <NUM> according to embodiments of the invention, and <FIG> is a block diagram further illustrating in one example the RAID controller <NUM> of <FIG>.

Referring to <FIG>, the RAID system <NUM> may generally include the RAID controller <NUM> and memory devices <NUM> connected to one or more host devices (e.g., host devices <NUM> and <NUM>) via a connect network <NUM>.

Here, the memory devices <NUM> may include nonvolatile memory devices, wherein respective nonvolatile memory devices communicate with the RAID controller <NUM> through at least one channel among a plurality of channels. In some embodiments, the memory devices <NUM> may include nonvolatile semiconductor memory devices (e.g., NAND flash memory devices) and/or one or more solid state drive(s) (SSD).

In some embodiments, the memory devices <NUM> may include first memory device(s) that store data chunks and at least one parity corresponding to the data chunks, as well as second memory device(s) that provide a spare memory region.

The RAID controller <NUM> may be implemented as a separate hardware card to manage the memory devices <NUM> as hardware, and/or as a chipset to manage the memory devices <NUM> as firmware.

In the illustrated example of <FIG>, the RAID controller <NUM> is connected between a first host device <NUM> and a second host device <NUM>, and the memory devices <NUM>. The RAID controller <NUM> may be configured to access the memory devices <NUM> in response to requests from the host devices <NUM> and <NUM>. For example, the RAID controller <NUM> may be configured to control various data access operation (e.g., data read, data write, and data discard operations) performed by the memory devices <NUM>. In this regard, the one or more data access operations may be referred to as a RAID operation, wherein the memory devices <NUM> may be controller to perform various RAID operations during foreground and/or background operating modes. Hence, in some embodiments, a rebuild operation may be performed as a foreground operation or as a background operation.

Although specifically illustrated in <FIG>, the RAID controller <NUM> may be configured to provide an interface between the memory devices <NUM> and the first host device <NUM>. In addition, the RAID controller <NUM> may be configured to drive firmware for controlling the memory devices <NUM>.

Referring to <FIG>, the RAID controller <NUM> may further include, in relevant part, a host interface <NUM>, a RAID processing unit <NUM>, a random access memory (RAM) <NUM>, an internal memory <NUM> and a memory interface <NUM>.

The host interface <NUM> may facilitate the use of one or more protocol(s) for data exchange between the first host device <NUM> and the RAID controller <NUM>. For example, the RAID controller <NUM> may be configured to communicate with a host through at least one of various interface protocols such as a universal serial bus (USB) protocol, a multimedia card (MMC) protocol, a peripheral component interconnection (PCI) protocol, a PCI-express (PCI-E) protocol, an advanced technology attachment (ATA) protocol, a serial-ATA protocol, a parallel-ATA protocol, a small computer small interface (SCSI) protocol, a serial attached SCSI (SAS) protocol, an enhanced small disk interface (ESDI) protocol, and an integrated drive electronics (IDE) protocol.

The RAID processing unit <NUM> may be used to control the overall operation of the RAID controller <NUM>. In some embodiments, the RAID processing unit <NUM> may perform a RAID operation or a background operation on the memory devices <NUM>.

The RAM <NUM> may be used as a working memory for the RAID controller <NUM> and may be implemented using various types of volatile and/or nonvolatile memory. For example, the RAM <NUM> may be implemented using at least one of a dynamic RAM (DRAM), a static RAM (SRAM), a phase-change RAM (PRAM), a magnetic RAM (MRAM), a resistive RAM (RRAM) and a flash memory.

The internal memory <NUM> may be used as a buffer memory. In some embodiments, the internal memory <NUM> may include a read only memory (ROM), a programmable read only memory (PROM), an erasable PROM (EPROM), an electrically erasable programmable read only memory (EEPROM), a PRAM, a flash memory, an SRAM, or a DRAM. The memory <NUM> may store preset information, programs, or commands related to the operation or state of the RAID controller <NUM>.

The internal memory <NUM> may also include a count table <NUM> associated with certain embodiments of the invention, one example of which is described in relation to <FIG> hereafter.

The RAID controller <NUM> may be used to control the performing (or execution) of a RAID rebuild operation on the memory devices <NUM>. For example, the RAID controller <NUM> may perform a RAID rebuild operation on the memory devices <NUM> on a stripe-by-stripe basis. Example of possible rebuild operations performed on the memory devices <NUM> by the RAID controller <NUM> will be described hereafter in some additional detail.

The memory interface <NUM> may include a protocol for data exchange between the memory devices <NUM> and the RAID controller <NUM>.

In some embodiments, the RAID controller <NUM> and the memory devices <NUM> may be integrated into a single semiconductor device, such as (e.g.,) a memory card functioning as a SSD. When the RAID controller <NUM> and the memory devices <NUM> are integrated into a single semiconductor device used as an SSD, the operating speed of a host connected to the RAID system <NUM> may be markedly improved. However, the inventive concept is not limited thereto, and the RAID controller <NUM> and the memory devices <NUM> may alternately be implemented as physically separate (e.g., mechanically attachable/detachable) components.

Here, in embodiments wherein the RAID controller <NUM> and the memory devices <NUM> are integrated into a memory card, the memory card may be configured to operate as a personal computer (PC) card (Personal Computer Memory Card International Association (PCMCIA)), a compact flash (CF) card, a smart media card (SM or SMC), a memory stick, a multimedia card (MMC, RS-MMC or MMCmicro), an SD card (SD, miniSD, microSD or SDHC), or a universal flash storage (UFS).

In should be further noted that the memory devices <NUM> may be variously packaged using one or more techniques, such as package on package (PoP), ball grid arrays (BGAs), chip scale packages (CSPs), plastic leaded chip carrier (PLCC), plastic dual in-line package (PDIP), die in waffle pack, die in wafer form, chip on board (COB), ceramic dual in-line package (CERDIP), plastic metric quad flat pack (MQFP), thin quad flatpack package (TQFP), small outline integrated circuit (SOIC), shrink small outline package (SSOP), thin small outline package (TSOP), thin quad flatpack package (TQFP), system in package (SIP), multi-chip package (MCP), wafer-level fabricated package (WFP), and wafer-level processed stack package (WSP).

<FIG> is a block diagram illustrating another RAID system according to embodiments of the inventive concept, and <FIG> is a block diagram further illustrating in one example the host device <NUM> of <FIG> and <FIG>.

Here, the RAID system of <FIG> does not include a RAID controller, like the RAID controller <NUM> of <FIG>. Instead, the RAID system of <FIG> includes the first host device <NUM> and the second host device <NUM> connected to memory devices <NUM> via the connect network <NUM>, wherein at least one of the nonvolatile memory devices <NUM> stores RAID software. That is, the host device <NUM> may build at least one of the nonvolatile memory devices <NUM> as a RAID by executing software booted by an operating system (e.g., upon power-up of the RAID system).

For example, referring to <FIG>, the first host device <NUM> may include a host processing unit <NUM>, a RAM <NUM>, an internal memory <NUM> and a RAID interface <NUM>.

The host processing unit <NUM> may be used to control the overall operation of the host device <NUM>. For example, the first host device <NUM> may perform a RAID operation or a rebuild operation on the memory devices <NUM>.

The RAM <NUM> may be used as a working memory for the first host device <NUM> and may be variously implemented using volatile memory and/or nonvolatile memory as previously described.

The internal memory <NUM> may be used as a buffer memory, and may be variously implemented using a cache, a ROM, a PROM, an EPROM, an EEPROM, a PRAM, a flash memory, an SRAM and/or a DRAM. In some embodiments, the memory <NUM> may store preset information, programs, commands, etc., related to the operation or an operating state of the first host device <NUM>.

In some embodiments, the internal memory <NUM> may include a count table <NUM> according to embodiments of the invention. (See, e.g., <FIG>).

The RAID interface <NUM> may enable a protocol that facilitates the exchange of data between the memory devices <NUM> and the first host device <NUM>.

In the written description that follows, a RAID control module will be described. The RAID control module may be the RAID controller <NUM> described in in relation to <FIG> or it may be the first host device <NUM> described in relation to <FIG>.

<FIG> is a conceptual diagram illustrating a rebuild operation that may be performed by a RAID control module according to embodiments of the invention.

In the illustrative example, memory devices <NUM> are assumed to include a first memory device Disk <NUM>, a second memory device Disk <NUM>, a third memory device Disk <NUM>, and a fourth memory device Disk <NUM> (collectively "Disk <NUM> through Disk <NUM>"), each respectively configured as a first memory device to store data chunks and parity, as well as a Spare Disk configured as a second memory device to provide spare memory space. It is further assumed that a data access operation directed to the second memory devices Disk <NUM> (a first memory device) has failed. Accordingly, the RAID system according to the embodiments of the invention will rebuild data stored on the failed memory device (i.e., Disk <NUM>) using the Spare Disk.

However, those skilled in the art will recognize that the number of first memory devices storing data and/or parity and the number of second memory devices providing spare memory space may vary by RAID system design.

In some embodiments, P parity may be stored in relation to data stored in the first memory devices, and Q parity (additional to the P parity) may also be stored in relation to data stored in the first memory devices. However, Q parity may be parity generated in a different way than P parity.

In some embodiments, the first memory devices (Disk <NUM> through Disk <NUM>) included in the RAID system may include so-called "stripes" respectively distinguished as rows. Each stripe may include a plurality of data chunks and one or two parities corresponding to the stored data chunks belonging to the same stripe. The parities may be, for example, parities generated by performing an XOR operation on the data chunks belonging to the same stripe.

In the illustrated embodiment of <FIG>, three (<NUM>) data chunks and one parity are assumed for illustrative purposes. , wherein the data chunks and parity are respectively indicated by A through D without distinction.

As noted above, a second memory device (Spare Disk) has previously been allocated a spare region before the rebuild operation is performed. Thus, the Spare Disk may, wholly or in part, an empty data region before the rebuild operation.

In some embodiments, wherein the memory devices <NUM> are integrated into a single semiconductor device as described above, the first memory devices and the second memory device may be implemented using memory cells provided by a semiconductor package.

Once the failed first memory device (Disk <NUM>) is identified, a rebuild operation may be performed, wherein the rebuild operation is performed by the RAID controller <NUM> of <FIG> or the host device <NUM> of <FIG>.

In some more specific embodiments, an XOR operation may be performed on a stripe by strip basis for the non-failed, first memory devices (e.g., Disk <NUM>, Disk <NUM> and Disk <NUM>), and the results of the XOR operations may be stored in the second memory device (Spare Disk). Thus, during the rebuild operation, an XOR operation may be performed on A0, A2 and A3 stored in respective first rows of the non-failed, first memory devices (Disk <NUM>, Disk <NUM> and Disk <NUM>), and a value of As obtained by performing the XOR operation may be stored in a first row of the second memory device (Spare Disk).

However, when data chunks are stored in only part(s) of each one of the first memory devices (Disk <NUM> through Disk <NUM> in the illustrated example of <FIG>, including first through fourth rows), it may be difficult for the RAID controller <NUM> of <FIG> or the host device <NUM> of <FIG> to identify (or differentiate) "used region(s)" from "unused region(s)" for each of the first memory devices (Disk <NUM> through Disk <NUM>).

In this regard, the count table <NUM> or <NUM> is be used to store information associated with used region of a first memory device. For example, in some embodiments, the count table <NUM> or <NUM> may be implemented using a Bloom filter method, wherein a data structure is used to check whether a data chunk exists in a memory device. If it is determined that a data chunk exists in a specific region of a memory device according to the Bloom filter method, there may occur a false positive in which the data chunk does not actually exist, but never occurs a false negative in which it is determined, on the contrary, that the data chunk does not exist in the specific region of the memory device although the data chunk exists. That is, there is no risk of missing a data chunk when the used region of the memory device is checked.

Accordingly, the RAID controller <NUM> of <FIG> or the host device <NUM> of <FIG> is be used to identify used region(s) of a first memory device by checking a corresponding count table <NUM> or <NUM>, and accesses only the identified used region, thereby reducing the time required to perform a rebuild operation, as compared with approaches that require accessing the entire first memory device during the rebuild operation. In addition to reducing rebuild time, the number of I/O operations that must be performed during the rebuild operation may be reduced, thereby improving overall performance of the RAID system.

The count table <NUM> or <NUM> includes "buckets," wherein buckets may be implemented as an array of one row, and each row of buckets may be a position corresponding to a used region of a first memory device.

Thus, the count table <NUM> or <NUM> generates a hash value by performing hash modulation at least one based on a logical block address (LBA) at which data chunks or at least one parity are stored in each of the first memory devices Disk <NUM> through Disk <NUM> and may store a count in a bucket corresponding to the hash value in the count table <NUM> or <NUM>. This exemplary approach will be described in some additional detail with respect to <FIG>.

<FIG> is a flowchart summarizing in one example a rebuild operation that may be performed by a RAID system according to embodiments of the invention. (Here, the same exemplary RAID system of <FIG> is assumed for descriptive purposes).

Accordingly, a RAID control module may rebuild data for a failed first memory device (Disk <NUM>) in a second memory device (Spare Disk) (S30).

To rebuild the data, the RAID control module may perform a hash modulation based on LBAs of used regions for the non-failed, first memory devices (Disk0, Disk <NUM> and Disk <NUM>) (S31). In some embodiments, the hash modulation may be performed multiple times using different types of hash functions. In some embodiments, the number of times the hash modulation is performed may be further increased to produce different hash values that are not redundant. An exemplary approach will be described in some additional detail with respect to <FIG>.

Thus, the RAID control module may begin a rebuild process when one of the first memory devices <NUM> fails (S30) using a hash modulation performed based on LBA(s) associated with each of the first memory devices <NUM> (S31). Then, if values of all buckets corresponding to the LBA are zero (S32=YES), the LBA is excluded from an XOR operation (S34) because it is an LBA to which data has never been previously written. However, if the values of all buckets corresponding to the LBA are not zero in a count table <NUM> or <NUM> (S32=NO) as a result of performing the hash modulation based on the LBA in operation S31, a determination may be made that data has previously been written to the LBA. Accordingly, data of the failed first memory device being rebuilt in the second memory device may be allocated to the spare region (S33). That is, when rebuilding data in the second memory device, the RAID control module may calculate a hash value for the LBA of each of the non-failed, first memory devices (Disk <NUM>, Disk <NUM> and Disk <NUM>) using the second memory device (Spare Disk) and may further update the count table by increasing or decreasing a count in a bucket corresponding to the hash value (S35).

<FIG> is a table listing an example of a hash modulation that may be performed by a RAID system according to embodiments of the invention.

Here, it is further assumed that data is stored in a first memory device (e.g., Disk <NUM>) according to eight (<NUM>) constituent stripes. For example, it is assumed that in Disk <NUM> of <FIG> LBAs for rows of data chunks are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, respectively.

It is also arbitrarily assumed that a hash modulation is performed four (4x) times on the LBA of each row. The hash modulation may be performed using different hash functions f1(x) through f4(x) as shown in the table. In some embodiments, the f1(x) may produce the remainder of the LBA divided by <NUM> as a first hash value, f2(x) may produce a value obtained by adding the remainder of the LBA divided by <NUM> to the first hash value as a second hash value, f3(x) may produce a value obtained by adding the remainder of the LBA divided by <NUM> to the second hash value as a third hash value, and f4(x) may produce a value obtained by adding <NUM> to the third hash value as a fourth hash value.

Hence, in the case of a first row, the first hash value is <NUM> because f1(x)=<NUM>%<NUM>=<NUM>, the second hash value is <NUM> because f2(x)=<NUM>+<NUM>%<NUM>=<NUM>+<NUM>=<NUM>, the third hash value is <NUM> because f3(x)=<NUM>+<NUM>%<NUM>=<NUM>+<NUM>=<NUM>, and the fourth hash value is <NUM> because f4(x)=<NUM>+<NUM>=<NUM>, and in the case of a second row, the first hash value is <NUM> because f1(x)=<NUM>%<NUM>=<NUM>, the second hash value is <NUM> because f2(x)=<NUM>+<NUM>%<NUM>=<NUM>+<NUM>=<NUM>, the third hash value is <NUM> because f3(x)=<NUM>+<NUM>%<NUM>=<NUM>+<NUM>=<NUM>, and the fourth hash value is <NUM> because f4(x)=<NUM>+<NUM>=<NUM>.

Likewise, the values of f1(x) through f4(x) may be calculated for each row to produce the first through fourth hash values as shown in each row of <FIG>.

As for each hash value of each column, the first hash values are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> in which <NUM> and <NUM> (i.e., two hash values) are redundant. However, the fourth hash values are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> in which <NUM> (i.e., only one hash value) is redundant. If different hash functions are continuously applied as in the illustrated example, the number of redundant hash values in the same column (the same time) may be gradually reduced.

<FIG> is a flowchart summarizing in one example a method of updating a count table when data is written to a RAID system according to embodiments of the invention, <FIG> is a conceptual diagram further illustrating the method of <FIG>, and <FIG> is an exemplary count table reflecting the result of hash modulation of <FIG>.

Referring to <FIG>, when a data chunk (DATA) is written to at least one the first memory devices (S10), an LBA corresponding to a used region of the first memory device to which the data chunk has been written has specific data. A RAID control module performs hash modulation on the LBA at least once (S11), and a resulting hash value calculated through the hash modulation increases a count (e.g., adds +<NUM>) at a corresponding bucket position in a count table by one (S12). And when the hash modulation is performed a number of times, the step of increasing the count at a bucket position corresponding to a hash value may be repeated to appropriately update the count table (S13).

Referring to <FIG> and <FIG>, when the LBA is <NUM>, the first through fourth hash values are <NUM>, <NUM>, <NUM> and <NUM>, and when the LBA is <NUM>, the first through fourth hash values are <NUM>, <NUM>, <NUM> and <NUM>.

Thus, each hash value corresponds to positional information of a bucket in the count table. That is, whenever data is written to or discarded from a first memory device, the RAID control module may re-calculate a corresponding hash value and appropriately vary (increase or decrease) a count in a bucket corresponding to the hash value.

Extending the working example in this regard, when a data chunk or parity is written to the first row of the first memory device (Disk <NUM>), the LBA of the first row has a specific value. If the LBA is <NUM>, the first through fourth hash values may be calculated as <NUM>, <NUM>, <NUM>, and <NUM>, respectively, and the count table <NUM> or <NUM> may increase the count by one at bucket positions [<NUM>], [<NUM>], [<NUM>], and [<NUM>] corresponding to the first through fourth hash values.

Likewise, when a data chunk or parity is written to the second row of the first memory (Disk <NUM>), if the LBA of the second row is <NUM>, the first through fourth hash values may be calculated as <NUM>, <NUM>, <NUM>, and <NUM>. In this case, the count table <NUM> or <NUM> increases the count by one at bucket positions [<NUM>], [<NUM>], [<NUM>], and [<NUM>] corresponding to the first through fourth hash values.

Similarly, when data chunks or parity are written to the other rows (e.g., the third through eighth rows) of the first memory device (Disk <NUM>), the first through fourth hash values may be calculated for the LBA (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, or <NUM>) of each row as illustrated in <FIG>. When the count in the count table <NUM> or <NUM> is increased by one at bucket positions corresponding to the calculated first through fourth hash values (f1(x) through f4(x)) of each row, the count table may be updated as illustrated in <FIG>.

In some embodiments, the number of count tables may be equal to the number of first memory devices. In addition, a count table for a used region to which data has been written may be created for each of the first memory devices Disk <NUM> through Disk <NUM>. Alternatively, in some other embodiments, since data associated with multiple first memory devices may be divided into data chunks and used after load balancing at the same ratio according to RAID configuration, the number of count tables may be less than the number of first memory devices.

The above example related to <FIG>, <FIG> serve to illustrate hash modulation on any one first memory device (e.g., Disk <NUM>) included in multiple memory devices in which data chunks and/or parity are used in a number of stripes (e.g., <NUM>). However, this is merely an example and the number of stripes in the used region, the number of first memory devices, as well as the number of count tables may vary with design.

<FIG> is a flowchart summarizing in one example a method of updating a count table when data is discarded from a RAID system according to embodiments of the invention, and <FIG> is a conceptual diagram illustrating the count table during the method of <FIG>.

Referring to <FIG>, when data chunks are discarded from at least one of the first memory devices (S20), used region(s) of the first memory device may be changed as a result. Therefore, the host device <NUM> or the RAID controller <NUM> may perform hash modulation on LBAs of the changed used region (S21). If buckets corresponding to all LBAs of the first memory device on which the hash modulation is performed have a count of zero (S23=YES), the first memory device may be identified as a first memory device which has never previously been used and the method may skip to the updating of the count table (S25). However, if at least one of the buckets corresponding to the LBAs of the first memory device on which the hash modulation is performed does not have a count of zero (S23=NO), the count of the count table may be varied (increased or decreased) by determining that a used region exists. That is, a hash value may be calculated through hash modulation for an LBA whose data state has been changed, and the count in a bucket at a position corresponding to the hash value in the count table is increased or decreased by one (S24). When the hash modulation is performed a plurality of times according to some embodiments, the RAID control module may calculate a hash value each time and update of the count table by repeating an operation of increasing or decreasing the count by one at a bucket position corresponding to each of the hash values of all times (S23).

Referring to <FIG>, <FIG> and <FIG>, when the LBA is <NUM> in the illustrated embodiment, the first through fourth hash values are <NUM>, <NUM>, <NUM> and <NUM>. When the LBA is <NUM>, the first through fourth hash values are <NUM>, <NUM>, <NUM> and <NUM>.

In the example illustrated in <FIG>, when hash modulation is performed on the LBAs of the first row and the second row of a first memory device, buckets [<NUM>] through [<NUM>] in the count table <NUM> or <NUM> have a count of <NUM>.

If a data chunk stored in the second row of the first memory device is discarded, the first through fourth hash values for the LBA <NUM> of the second row should be subtracted from the previous count table. That is, when the LBA is <NUM>, one is subtracted from buckets [<NUM>][<NUM>][<NUM>][<NUM>] corresponding to the first through fourth hash values <NUM>,<NUM>,<NUM> and <NUM>.

In this manner, whenever data is discarded from a first memory device, the host device <NUM> or the RAID controller <NUM> may check (or verify) the used region of the first memory device by updating the count table based on the LBA of a position from which the data has been discarded.

<FIG> is a flowchart summarizing a method of operating a RAID system according to embodiments of the invention.

Here, a host device may send a command for a RAID operation to the RAID system (S100). The RAID system may perform a RAID operation (e.g., a data read, data write, or data discard operation) as a foreground or a background operation on at least one of the first memory devices, and the host device may update a count table for the at least one of the first memory devices by reflecting the result of the RAID operation (S101).

If at least one first memory device fails during the RAID operation (S201), the RAID system identifies the failed state of the first memory device to the host device. The host device than checks used regions of the first memory devices based on a last updated count table (S102) and sends a rebuild command to the RAID system based on the checked used regions (S103).

The RAID system reads data chunks or parity by accessing only the used regions of at least two first memory devices according to the rebuild command of the host device and sends the read data chunks or parity to the host device (S202), and the host device performs a rebuild operation on the read data chunks or parity (S104). For example, the rebuild operation may progress using an XOR operation.

When the host device sends the result of the operation to a second memory device in the RAID system, the second memory device may store (write) a received XOR operation value of each row in a corresponding row (S203).

Since the data storage state of the second memory device has been changed according to the result of the XOR operation, the host device updates the count table by performing hash modulation on an LBA based on the changed used region (S105). The count table may reflect, in real time, changes in the used regions of the first memory devices excluding the failed first memory device and a used region of the second memory device. When the XOR operation for the entire used regions is finished, the host device ends the rebuild operation (S106).

<FIG> is a flowchart summarizing illustrating a method of operating a RAID system according to embodiments of the invention.

Referring to <FIG>, a host device may send a command for a RAID operation to the RAID system (S110). The RAID system may performs a RAID operation (e.g., a data read, data write or data discard operation) as a foreground or a background operation on at least one of the first memory devices and update a count table for the at least one first memory device (S211).

In some embodiments, the host device may request the RAID system to send a count table according to a system setting or a user's instruction (S111). The RAID system may send a last updated count table to the host device according to the request (S212).

The host device may send a command for a RAID operation to the RAID system by referring to the count table received in operation S212 (S112). For example, the host device may send a read command by referring to the count table. The RAID system may perform a RAID operation according to the received command (S213), and the host device may continuously update the count table based on the operation result of the RAID system (S113). If at least one first memory device fails during the RAID operation (S215), the RAID system informs the host device of the failed state of the first memory device. The host device checks used regions of the first memory devices based on the last updated count table (S114) and sends a rebuild command for the checked used regions to the RAID system (S115).

The RAID system reads data chunks or parity by accessing only the used regions of at least two first memory devices according to the rebuild command previously received (S115) and sends the read data chunks or parity to the host device, and the host device performs a rebuild operation on the read data chunks or parity (S116). For example, the rebuild operation may progress using an XOR operation.

When the host device sends the result of the operation to a second memory device in the RAID system, the second memory device may store (write) a received XOR operation value of each row in a corresponding row (S217).

According to some embodiment, the RAID system may update the count table by performing hash modulation on a used region of the second memory device after the result of the XOR operation (S218). Alternatively, according to some embodiments, the RAID system may update the count table by receiving, in real time or after the XOR operation, the count table updated (S113) and stored in the host device. Accordingly, the count table may reflect changes in the used regions of the first memory devices excluding the failed first memory device and the used region of the second memory device. When the XOR operation for the entire used regions is finished, the host device terminates the rebuild operation (S117).

Alternately, the host device may request the count table only when necessary instead of continuously updating the count table. Therefore, the host device may operate at low cost.

<FIG> is a block diagram illustrating a data center <NUM> that may include a RAID memory device according to embodiments of the invention.

Referring to <FIG>, the data center <NUM> may be a facility that collects various data and provides services and may also be referred to as a data storage center. The data center <NUM> may be a system for operating a search engine and a database and may be a computing system used by companies such as banks or government agencies. The data center <NUM> may include application servers <NUM> through 1100n and storage servers <NUM> through <NUM>. The number of application servers <NUM> through 1100n and the number of storage servers <NUM> through <NUM> may be variously selected depending on embodiments. The number of application servers <NUM> through 1100n may be different from the number of storage servers <NUM> through <NUM>.

The application server <NUM> or the storage server <NUM> may include at least one of a processor <NUM> or <NUM> and a memory <NUM> or <NUM>. For example, in the case of the storage server <NUM>, the processor <NUM> may control the overall operation of the storage server <NUM> and access the memory <NUM> to execute a command and/or data loaded in the memory <NUM>. According to some embodiments, the memory <NUM> may include a count table. The memory <NUM> may be a double data rate synchronous DRAM (DDR SDRAM), a high bandwidth memory (HBM), a hybrid memory cube (HMC), a dual in-line memory module (DIMM), an Optane DIMM, or a nonvolatile DIMM (NV[M]DIMM).

Depending on embodiments, the number of processors <NUM> and the number of memories <NUM> included in the storage server <NUM> may be variously selected. In an embodiment, the processor <NUM> and the memory <NUM> may provide a processor-memory pair. In an embodiment, the number of processors <NUM> may be different from the number of memories <NUM>. The processor <NUM> may include a single-core processor or a multi-core processor. The above description of the storage server <NUM> may be similarly applied to the application server <NUM>.

Depending on embodiments, the application server <NUM> may not include a storage device <NUM>. The storage server <NUM> may include one or more storage devices <NUM>. The number of storage devices <NUM> included in the storage server <NUM> may be variously selected depending on embodiments.

The application servers <NUM> through 1100n and the storage servers <NUM> through <NUM> may communicate with each other through a network <NUM>. The network <NUM> may be implemented using Fibre Channel (FC) or Ethernet. Here, the FC may be a medium used for relatively high-speed data transmission and may use an optical switch that provides high performance/high availability. The storage servers <NUM> through <NUM> may be provided as file storage, block storage, or object storage according to an access method of the network <NUM>.

In an embodiment, the network <NUM> may be a storage dedicated network such as a storage area network (SAN). For example, the SAN may be an FC-SAN using an FC network and implemented according to an FC protocol (FCP). For another example, the SAN may be an IP-SAN using a TCP/IP network and implemented according to an SCSI over TCP/IP or Internet SCSI (iSCSI) protocol. In another embodiment, the network <NUM> may be a general network such as a TCP/IP network. For example, the network <NUM> may be implemented according to a protocol such as FC over Ethernet (FCoE), network attached storage (NAS), or NVMe over Fabrics (NVMe-oF).

The application server <NUM> and the storage server <NUM> will hereinafter be mainly described. The description of the application server <NUM> may also be applied to another application server 1100n, and the description of the storage server <NUM> may also be applied to another storage server <NUM>.

The application server <NUM> may store data requested to be stored by a user or a client in one of the storage servers <NUM> through <NUM> through the network <NUM>. In addition, the application server <NUM> may obtain data requested to be read by a user or a client from one of the storage servers <NUM> through <NUM> through the network <NUM>. For example, the application server <NUM> may be implemented as a web server or a database management system (DBMS). The application server <NUM> may be the host of <FIG> described according to some embodiments.

The application server <NUM> may access a memory 1120n or a storage device 1150n included in another application server 1100n through the network <NUM> or may access memories <NUM> through <NUM> or storage devices <NUM> through <NUM> included in the storage servers <NUM> through <NUM> through the network <NUM>. Accordingly, the application server <NUM> can perform various operations on data stored in the application servers <NUM> through 1100n and/or the storage servers <NUM> through <NUM>.

For example, the application server <NUM> may execute a command for transferring or copying data between the application servers <NUM> through 1100n and/or the storage servers <NUM> through <NUM>. Here, the data may be transferred from the storage devices <NUM> through <NUM> of the storage servers <NUM> through <NUM> to the memories <NUM> through 1120n of the application servers <NUM> through 1100n via the memories <NUM> through <NUM> of the storage servers <NUM> through <NUM> or directly. The data transferred through the network <NUM> may be data encrypted for security or privacy.

For example, the application server <NUM> may configure the application servers <NUM> through 1100n and/or the storage servers <NUM> through <NUM> as a RAID. Thus, when any one server fails, the application server <NUM> may execute a command for rebuilding data between the other application servers <NUM> through 1100n and/or storage servers <NUM> through <NUM>. In this case, the application server <NUM> may include a count table as metadata in the memory <NUM> in an example or may request a count table from the other application servers <NUM> through 1100n and/or storage servers <NUM> through <NUM> configured in the RAID to perform a rebuild operation.

In the storage server <NUM>, for example, an interface <NUM> may provide a physical connection between the processor <NUM> and a controller <NUM> and a physical connection between an NIC <NUM> and the controller <NUM>. For example, the interface <NUM> may be implemented as a direct attached storage (DAS) interface that connects the storage device <NUM> directly to a dedicated cable. In addition, for example, the interface <NUM> may be implemented as various interfaces such as advanced technology attachment (ATA), serial-ATA (SATA), external SATA (e-SATA), small computer small interface (SCSI), serial attached SCSI (SAS), peripheral component interconnection (PCI), PCI express (PCIe), NVM express (NVMe), IEEE <NUM>, universal serial bus (USB), secure digital (SD) card, multi-media card (MMC), embedded multi-media card (eMMC), universal flash storage (UFS), embedded universal flash storage (eUFS), compact flash (CF), and a card interface.

The storage server <NUM> may further include a switch <NUM> and the NIC <NUM>. The switch <NUM> may selectively connect the processor <NUM> and the storage device <NUM> or may selectively connect the NIC <NUM> and the storage device <NUM> under the control of the processor <NUM>.

In an embodiment, the NIC <NUM> may include a network interface card, a network adapter, or the like. The NIC <NUM> may be connected to the network <NUM> by a wired interface, a wireless interface, a Bluetooth interface, an optical interface, or the like. The NIC <NUM> may include an internal memory, a digital signal processor (DSP), a host bus interface, etc. and may be connected to the processor <NUM> and/or the switch <NUM> through the host bus interface. The host bus interface may be implemented as one of the above-described examples of the interface <NUM>. In an embodiment, the NIC <NUM> may be integrated with at least one of the processor <NUM>, the switch <NUM>, and the storage device <NUM>.

In some embodiments, the processor <NUM>, the memory <NUM>, the switch <NUM>, and the NIC <NUM> may be included in the RAID controller <NUM> described in <FIG> or in the host device <NUM> described in <FIG>.

In a storage server (<NUM>-<NUM>) or an application server (<NUM>-1100n), a processor may send a command to a storage device (<NUM>-1150n , <NUM>- <NUM>) or a memory (<NUM>-1120n, <NUM>-<NUM>) to program or read data. Here, the data may be data that has been error-corrected through an error correction code (ECC) engine. The data may be data processed by data bus inversion (DBI) or data masking (DM) and may include cyclic redundancy code (CRC) information. The data may be data encrypted for security or privacy.

The storage device (<NUM>-1150n, <NUM>-<NUM>) may send a control signal and a command/an address signal to a NAND flash memory device (<NUM>-<NUM>) in response to the read command received from the processor. Accordingly, when data is read from the NAND flash memory device (<NUM>-<NUM>), a read enable (RE) signal may be input as a data output control signal, causing the data to be output to a DQ bus. Data strobe (DQS) may be generated using the RE signal. The command and the address signal may be latched in a page buffer according to a rising edge or a falling edge of a write enable (WE) signal.

Claim 1:
A redundant array of independent disks, RAID, storage device (<NUM>, 1150n, <NUM>, <NUM>) comprising:
a memory device (<NUM>) including first memory devices configured to store at least one of data chunks and corresponding parity and a second memory device configured to serve as a spare memory region; and
a RAID controller (<NUM>) including a RAID internal memory (<NUM>) configured to store a count table (<NUM>, <NUM>) and configured to control performing of a rebuild operation in response to a command received from a host (<NUM>, <NUM>),
wherein upon identification of a failed first memory device, the RAID controller (<NUM>) accesses used regions of non-failed first memory devices based on the count table (<NUM>, <NUM>) and rebuilds data of the failed first memory device using the second memory device,
wherein the count table (<NUM>, <NUM>) stores count table information indicating used regions in at least one of the first memory devices,
wherein in response to a RAID operation on the first memory devices, the RAID controller (<NUM>) is configured to generate hash values (<NUM>, <NUM>) by performing hash modulation based on a logical block address, LBA, at which the at least one of the data chunks and the corresponding parity are stored, and to store counts corresponding to a number of times the hash modulation is performed on the LBA in buckets of the count table (<NUM>, <NUM>),
wherein the RAID controller (<NUM>) does not perform the rebuild operation when count values of all buckets in the count table (<NUM>, <NUM>) are zero.