Storage system, information processor, and computer-readable recording medium having stored therein program for generating parity

Abstract

A storage system includes a first information processor, a second information processor, and a superordinate device. The first information processor includes a first memory device that stores therein the data, a difference generator that generates difference data representing a difference between updating data received from the superordinate device and the data stored in the first memory device before updating, a second memory device stores therein the generated difference data, and a data transmitter that transmits the stored difference data to the second information processor. The second information processor includes a third memory device that stores therein the parity, a data receiver that receives the difference data transmitted from the data transmitter, and a parity difference applier that generates a post-updating parity that is to be written into the third memory device by applying the received difference data to the stored parity before the updating.

Claims

1. A distributed storage system comprising: a first information processor that stores data; a second information processor that is communicably connected to the first information processor and that stores a parity of the data stored in the first information processor; and a host device that is communicably connected to the first information processor, the first information processor comprising: a first memory device that stores the data; a difference generator that generates difference data representing a difference between updated data received from the host device and the data stored in the first memory device; a second memory device stores the difference data generated by the difference generator; and a data transmitter that transmits the difference data stored in the second memory device to the second information processor, the second information processor comprising: a third memory device that stores the parity; a data receiver that receives the difference data transmitted from the data transmitter; and a parity difference applier that generates an updated parity that is to be written into the third memory device by applying the difference data received by the data receiver to the parity stored in the third memory device.

2. The storage system according to claim 1, the first information processor further comprising a data difference applier that generates updated data that is to be written into the first memory device by applying the difference data stored in the second memory device to the data stored in the first memory device.

3. The storage system according to claim 1, wherein the difference generator generates the difference data by calculation using the updated data received from the host device and the data stored in the first memory device on a Galois Field.

4. The storage system according to claim 1, wherein the difference data to be stored in the second memory device is used as a journal of data to be written into the first memory device and a parity to be written into the third memory device.

5. An information processor for a distributed storage system including a host device and a second information processor, the information processor comprising: a first memory device that stores the data; a difference generator that generates difference data representing a difference between updated data received from the host device and the data stored in the first memory device; a second memory device stores the difference data generated by the difference generator; and a data transmitter that transmits the difference data stored in the second memory device to the second information processor which stores a parity of the data stored in the first memory, the difference data being used for generating an updated parity in the second information processor.

6. The information processor according to claim 5, further comprising a data difference applier that generates updated data that is to be written into the first memory device by applying the difference data stored in the second memory device to the data stored in the first memory device.

7. The information processor according to claim 5, wherein the difference generator generates the difference data by calculation using the updated data received from the host device and the data stored in the first memory device on a Galois Field.

8. The information processor according to claim 5, wherein the difference data to be stored in the second memory device is used as a journal of data to be written into the first memory device and a parity to be stored in the second information processor.

9. A non-transitory computer-readable recording medium storing a program for generating a parity, the program causing a computer provided for an information processor for a distributed storage system including a host device and a second information processor to execute: storing data in a first memory; generating difference data representing a difference between updated data received from the host device and the data stored in the first memory device provided for the information processor; storing the generated difference data in a second memory device provided for the first information processor; and transmitting the difference data stored in the second memory device to the second information processor which stores a parity of the data stored in the first memory, the difference data being used for generating an updated parity in the second information processor.

10. The non-transitory computer-readable recording medium according to claim 9, wherein the program further causes the computer to execute generating updated data that is to be written into the first memory device by applying the difference data stored in the second memory device to the data stored in the first memory device.

11. The non-transitory computer-readable recording medium according to claim 9, wherein the program further causes the computer to execute generating the difference data by calculation using the updated data received from the host device and the data stored in the first memory device on a Galois Field.

12. The non-transitory computer-readable recording medium according to claim 9, wherein the difference data to be stored in the second memory device is used as a journal of data to be written into the first memory device and a parity to be stored in the second information processor.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a diagram schematically illustrating the functional configuration of a storage system according a first embodiment;

(2) FIG. 2 is a diagram schematically illustrating the functional configuration of a CPU included in a data node of the first embodiment;

(3) FIG. 3 is a diagram schematically illustrating the functional configuration of a CPU included in a parity node of the first embodiment;

(4) FIG. 4 is a sequence diagram denoting a process of writing a journal and a process of applying the journal in a storage system of the first embodiment;

(5) FIG. 5 is a diagram denoting a process of writing a journal in a storage system of the first embodiment;

(6) FIG. 6 is a diagram is a diagram denoting a process of applying a journal in a storage system of the first embodiment;

(7) FIG. 7 is a diagram denoting a process of writing a journal in a traditional storage system; and

(8) FIG. 8 is a diagram is a diagram denoting a process of applying a journal in a traditional storage system.

DESCRIPTION OF EMBODIMENTS

(9) Hereinafter, description will now be made in relation to a storage system, an information processor, and a computer-readable recording medium having stored therein a program for generating a parity with reference to accompanying drawings. However, the embodiment to be detailed below is are merely example and does not intend to exclude another modification and application of techniques that are not referred in this description. In other words, various changes and modification can be suggested without departing from the gist of the embodiment.

(10) The accompanying drawings may include other elements and functions in addition to those appearing in the drawings.

(11) Like reference numbers designate the same or the substantially same parts or elements in the accompanying drawings, so repetitious description is omitted here.

(A) First Embodiment

(12) (A-1) System Configuration:

(13) FIG. 1 schematically illustrates the functional configuration of a storage system according to a first embodiment.

(14) A storage system 100 illustrated in FIG. 1 provides a memory region to a non-illustrated host device (superordinate device), and functions as a distributed storage system that distributedly stores data into multiple data nodes 1. The storage system 100 includes multiple (three in the illustrated example) data nodes 1 (data nodes #1-#3; first information processors) and multiple (two in the illustrated example) parity nodes 2 (parity nodes #1 and #2; second information processors). This means that FIG. 1 illustrates an example that the stripe of the Erasure Code consists of three data chunks and two parity chunks. Each data node 1 is communicably connected to each parity node 2 via, for example, a LAN cable.

(15) Hereinafter, each individual data node is specified by “data node #1”, “data node #2”, or “data node #3”, but an arbitrary data node is represented by “data node 1”. Likewise, each individual parity node is specified by “parity node #1” or “parity node #2”, but an arbitrary parity node is represented by “parity node 2”.

(16) A data node 1 stores therein data received from an external device such as the non-illustrated host device, and includes a CPU 11, a memory 12, a file store (first memory device) 13, and a journal disk (second memory device) 14.

(17) The file store 13 is a known device that readably and writably stores therein data received by the data node 1, and is exemplified by an HDD or an SSD.

(18) The journal disk 14 is a known device that readably and writably stores therein a journal (updating history, updated difference), which is a record of data received by the data node 1a, and is exemplified by an HDD or an SDD.

(19) The memory 12 is a memory device including a Read Only Memory (ROM), and a Random Access Memory (RAM). In the ROM of the memory 12, a program such as Basic Input/Output System (BIOS) is written. A software program stored in the memory 12 is appropriately read by the CPU 11, which then executes the program. The RAM of the memory 12 is used as a primary recording memory and a working memory.

(20) The CPU 11 is a processor that executes various controls and calculations, and achieves various functions by executing an OS and a program stored in the memory 12. Specifically, as will be detailed below by referring to FIG. 2, the CPU 11 functions as a data receiver 111, a file store reader 112, a difference generator 113, a journal writer 114, a journal reader 115, a difference applier (data difference applier) 116, a file store writer 117, and a data transmitter 118.

(21) A program (program for generating a parity) that achieves the functions of the data receiver 111, the file store reader 112, the difference generator 113, the journal writer 114, the journal reader 115, the difference applier 116, the file store writer 117, and the data transmitter 118 is provided in the form of being recorded in a tangible and non-transitory computer-readable storage medium, such as a flexible disk, a CD (e.g., CD-ROM, CD-R, and CD-RW), a DVD (DVD-ROM, DVD-RAM, DVD-R, DVD+R, DVD-RW, DVD+RW, and HD DVD), a Blu-ray disk, a magnetic disk, an optical disk, and an magneto-optical disk. A computer reads the program from the recording medium using a non-illustrated medium reader and stores the read program in an internal or external storage device for future use. Alternatively, the program may be recorded in a recording device (recording medium), such as a magnetic disk, an optical disk, or a magneto-optical disk, and may be provided from the recording device to the computer via a communication path.

(22) Further alternatively, in achieving the functions of the data receiver 111, the file store reader 112, the difference generator 113, the journal writer 114, the journal reader 115, the difference applier 116, the file store writer 117, and the data transmitter 118, the program stored in an internal memory device (corresponding to the memory 12 in this embodiment) is executed by the microprocessor (corresponding to the CPU 11 in this embodiment) of the computer. For this purpose, the computer may read the program stored in the recording medium and execute the program.

(23) A parity node 2 is a node that stores therein a parity of data stored in the data node 1, and includes a CPU 21, a memory 22, and a file store 23 (third memory device).

(24) The file store 23 is a known device that readably and writably stores therein a parity of data to be stored in the data node 1, and is exemplified by an HDD or an SSD.

(25) The memory 22 is a memory device including a ROM and a RAM. In the ROM of the memory 22, a program such as the BIOS is written. A software program stored in the memory 22 is appropriately read by the CPU 21, which then executes the program. The RAM of the memory 22 is used as a primary recording memory and a working memory.

(26) The CPU 21 is a processor that executes various controls and calculations, and achieves various functions by executing an OS and a program stored in the memory 22. Specifically, as will be detailed below by referring to FIG. 3, the CPU 21 functions as a data receiver 211, a file store reader 212, a difference applier (parity difference applier) 213, and a file store writer 214.

(27) A program (program for generating a parity) that achieves the functions of the data receiver 211, the file store reader 212, the difference applier 213, and the file store writer 214 is provided in the form of being recorded in a tangible and non-transitory computer-readable storage medium, such as a flexible disk, a CD (e.g., CD-ROM, CD-R, and CD-RW), a DVD (DVD-ROM, DVD-RAM, DVD-R, DVD+R, DVD-RW, DVD+RW, and HD DVD), a Blu-ray disk, a magnetic disk, an optical disk, and an magneto-optical disk. A computer reads the program from the recording medium using a non-illustrated medium reader and stores the read program in an internal or external storage device for future use. Alternatively, the program may be recorded in a recording device (recording medium), such as a magnetic disk, an optical disk, or a magneto-optical disk, and may be provided from the recording device to the computer via a communication path.

(28) Further alternatively, in achieving the functions of the data receiver 211, the file store reader 212, the difference applier 213, and the file store writer 214, the program stored in an internal memory device (corresponding to the memory 22 in this embodiment) is executed by the microprocessor (corresponding to the CPU 21 in this embodiment) of the computer. For this purpose, the computer may read the program stored in the recording medium and execute the program.

(29) FIG. 2 schematically illustrates the functional configuration of a CPU included in each data node of this embodiment.

(30) The data receiver 111 receives data (updating data) from an external device such as a non-illustrated host device. Specifically, the data receiver 111 of each of the data nodes #1-#3 segments data that the corresponding node received from the external device into chunks in a unit of several bytes (e.g., four bytes) and receives the segmented chunks. Storing data into the file store 13 of a data node 1, calculating of a parity in a parity node 2, and storing of a parity into the file store 23 are carried out in units of a segmented chunk.

(31) The file store reader 112 reads data stored in the file store 13. Specifically, the file store reader 112 reads, when the data receiver 111 receives updating data, pre-updating data stored in a region to be updated of the file store 13. The file store reader 112 further reads pre-updating data stored in the file store 13 at the timing of applying a journal that is to be detailed below.

(32) The difference generator 113 generates difference information. Specifically, the difference generator 113 generates difference information representing a difference between the updating data received by the data receiver 111 and the pre-updating data read from the file store 13 by the file store reader 112. As described above, since a parity is calculated in units of a segmented chunk in the first embodiment, the difference generator 113 performs a subtraction of the bit length on the Galois Field using the updating data (post-updating image) and pre-updating data (pre-updating image) along the following expression.
ΔD=D.sub.ai−D.sub.bi  [Expression 1]

(33) Here, the term D.sub.ai represents a post-updating image; the term D.sub.bi represents a pre-updating image; and the negative sign “−” represents the subtraction on the Galois Field. Consequently, the difference generator 113 defines the difference segmented in units of several bytes.

(34) The journal writer 114 writes data into a journal. Specifically, the journal writer 114 writes the difference data generated by the difference generator 113 to be a journal into the journal disk 14.

(35) The data node 1a of the traditional system illustrated in FIGS. 7 and 8 writes a post-updating image to be a journal. In contrast, the journal writer 114 of the data node 1 of this embodiment writes a Galois updating difference calculated by the difference generator 113 to be the journal.

(36) The journal reader 115 reads data from a journal. Specifically, the journal reader 115 reads the difference data written by the journal writer 114 from the journal disk 14 at a timing of applying a journal. Here, examples of the timing of applying a journal is a timing at which the void volume of the journal disk 14 runs short or when a predetermined time has elapsed since the previous applying of a journal.

(37) The difference applier 116 generates post-updating data to be written into the file store 13. Specifically, the difference applier 116 applies (for example, adds) the difference data that the journal reader 115 has read from the journal disk 14 to the pre-updating data that the file store reader 112 has read from the file store 13. Consequently, the difference applier 116 generates a post-updating data.

(38) The file store writer 117 writes data into the file store 13. Specifically, the file store writer 117 writes the post-updating data generated by the difference applier 116 into the file store 13.

(39) The data transmitter 118 transmits data to the parity node 2. Specifically, the data transmitter 118 transmits the difference data read by the journal reader 115 from the journal disk 14 to the parity node 2.

(40) The traditional data node 1a described by referring to FIGS. 7 and 8 forwards the calculated updating difference to the parity node 2a after the completion of the process in the data node 1a (or in parallel with the process of writing of the journal). In contrast, the data transmitter 118 in the data node 1 of this embodiment forwards the updating difference read from the journal disk 14 to the parity node 2 at any timing until the journal is invalidated.

(41) Alternatively, the data transmitter 118 may transmit the difference data to multiple parity nodes 2 for maintain data redundancy. In this case, the parity nodes 2 execute the process in parallel with one another.

(42) FIG. 3 schematically illustrates the functional configuration of the CPU included in the parity node of the first embodiment.

(43) The data receiver 211 receives data from the data node 1. Specifically, the data receiver 211 receives the difference data transmitted from the data transmitter 118 of the data node 1.

(44) The file store reader 212 reads a parity from the file store 23. Specifically, the file store reader 212 reads, when the data receiver 211 receives the difference data, pre-updating parity stored in the file store 23.

(45) The difference applier 213 generates a post-updating parity to be written into the file store 23. Specifically, the difference applier 213 applies (for example, adds) the difference data received by the data receiver 211 to the pre-updating parity that the file store reader 212 has read from the file store 23. Consequently, the difference applier 213 generates the post-updating parity.

(46) The file store writer 214 writes a parity into the file store 23. Specifically, the file store writer 214 writes the post-updating parity generated by the difference applier 213 into the file store 23.

(47) The traditional parity node 2a illustrated in FIGS. 7 an 8 writes a post-updating parity into the file store 23a and further generates a post-updating parity by applying the difference data to a pre-updating parity. The parity node 2a writes the generated post-updating parity as a journal into the journal disk 24a, in contrast, the parity node 2 according to this embodiment is not equipped with a journal disk to store a journal, and the file store writer 214 writes a Galois updating difference forwarded from the data node 1 directly into the file store 23.

(48) In the first embodiment, there is no need to apply a journal to the file store 23 of the parity node 2 each time a journal is generated. Specifically, the data node 1 is allowed to forward a journal (difference data) of the sum of several journals in a lump to the parity node 2, which then applies the forwarded journals to the file store 23 all at once. Hereinafter, the reason for the above will now be detailed.

(49) Representing a generation matrix for a linear block code by (a.sub.ij) and representing a data chunk by D.sub.i, the parity chunk P.sub.i is represented by the following expression. Here, the symbols i and j are natural numbers; the symbol i represents the parity number and the symbol j represents a value specifying a coefficient depending on data.
P.sub.i=a.sub.i1D.sub.1+a.sub.i2D.sub.2+ . . . +a.sub.inD.sub.n  [Expression 2]

(50) Here, representing a Galois difference journal of one or more pieces of data D.sub.k by ΣΔD.sub.k, the post-updating image D.sub.k′ of a data chunk is represented by the following expression.
D′.sub.k=D.sub.k+ΣΔD.sub.k  [Expression 3]

(51) Accordingly, the post-updating image P.sub.i′ of a parity chunk is represented by the following expression.

(52) $\begin{array}{cc}\begin{array}{c}{P}_i^{\prime }=a_{i1}{D}_1+\mathrm{.Math.}+a_{\mathrm{ik}}{D}_k^{\prime }+\mathrm{.Math.}+a_{\mathrm{in}}{D}_n\\ =a_{i1}{D}_1+\mathrm{.Math.}+a_{\mathrm{ik}}\left(D_k+.Math.\Delta D_k\right)+\mathrm{.Math.}+a_{\mathrm{in}}{D}_n\\ =P_i+a_{\mathrm{ik}}.Math.\Delta D_k\end{array}\hspace{1em}& \left[\mathrm{Expression}4\right]\end{array}$

(53) The Galois difference journal ΣΔD.sub.k of a data chunk is recorded as a journal of a parity chunk without being modified, and a product of the journal of a parity chunk and the coefficient (a.sub.ik) is added to the pre-post image of the parity chunk. This calculates the post-updating image P.sub.i′ of the parity chunk.

(54) (A-2) Operation:

(55) Description will now be made in relation to a process of writing a journal and a process of applying a journal in a storage system of an example of the first embodiment along the sequence diagram FIG. 4 (steps S1-S13) with reference to FIGS. 5 and 6. Here, steps S1-S4 of FIG. 4 and symbols A1-A4 of FIG. 5 represent a process of writing a journal and steps S5-S13 of FIG. 4 and symbols A5-A13 of FIG. 6 represent a process of applying a journal.

(56) FIGS. 4-6 describe a process of writing a journal and a process of applying a journal in the data node #2 and the parity node #2. For simplification, illustration of the functional configurations of the data nodes #1 and #3 and parity node #1 is omitted, and illustration of the memory 12 and the memory 22 respectively provided in the data node #2 and the parity node #2 is also omitted illustrated.

(57) The data receiver 111 of the data node #2 receives updating data “7” from a non-illustrated host device (see step S1 of FIG. 4 and symbol A1 of FIG. 5).

(58) The file store reader 112 reads pre-updating data “4” from the file store 13 (see step S2 of FIG. 4 and symbol A2 of FIG. 5).

(59) The difference generator 113 calculates the difference between the updating data received by the data receiver 111 and the pre-updating data read by the file store reader 112 (see step S3 of FIG. 4 and symbol A3 of FIG. 5). In the example of FIG. 5, the difference generator 113 calculates the difference data to be the value “3” obtained by subtracting the pre-updating data “4” from the updating data “7”.

(60) The journal writer 114 writes the difference data “3” generated by the difference generator 113, as the journal, into the journal disk 14 (see step S4 of FIG. 4 and symbol A4 of FIG. 5).

(61) The journal reader 115 reads the difference data (journal) “3” written by the journal writer 114 from the journal disk 14 at the timing of applying a journal (see step S5 of FIG. 4 and symbol A5 of FIG. 6).

(62) The file store reader 112 reads the pre-updating data “4” from the file store 13 (see step S6 of FIG. 4 and symbol A6 of FIG. 6).

(63) The difference applier 116 applies the difference data read by the journal reader 115 to the pre-updating data read by the file store reader 112 (see step S7 of FIG. 4 and symbol A7 of FIG. 6). In the example of FIG. 6, the difference applier 116 generates the post-updating data “7” by adding the difference data “3” to the pre-updating data “4”.

(64) The file store writer 117 writes the post-updating data “7” generated by the difference applier 116 into the file store 13 (see step S8 of FIG. 4 and symbol A8 of FIG. 6).

(65) The data transmitter 118 forwards the difference data “3” read by the journal reader 115 to the parity node #2 (see step S9 of FIG. 4 and symbol A9 of FIG. 6) in parallel with the process of steps S6-S8 of FIG. 8 (symbols A6-A8 of FIG. 6).

(66) The data receiver 211 of the parity node #2 receives the difference data “3” forwarded by the parity node #1 (see step S10 of FIG. 4 and symbol A10 of FIG. 6).

(67) The file store reader 212 reads the pre-updating parity “2” from the file store 23 (see step S11 of FIG. 4 and symbol A11 of FIG. 6).

(68) The difference applier 213 applies the difference data received by the data receiver 211 to the pre-updating parity read by the file store reader 212 (see step S12 of FIG. 4 and symbol A12 of FIG. 6). In the example of FIG. 6, the difference applier 213 generates the post-updating parity “5” by adding the difference data “3” to the pre-updating parity “2”.

(69) The file store writer 214 writes the post-updating parity “5” generated by the difference applier 213 into the file store 23 (see step S13 of FIG. 4 and symbol A13 of FIG. 6).

(70) The above procedure completes the process of writing a journal and the process of applying the journal.

(71) (A-3) Effects:

(72) In the data node 1, the difference generator 113 generates the difference data representing the difference between the updating data received from the superordinate device and the pre-updating data stored in the file store 13. Then, the journal disk 14 stores the difference data generated by the difference generator 113.

(73) In the parity node 2, the data receiver 211 receives the difference data transmitted from the data transmitter 118 of the data node 1. The difference applier 213 generates the post-updating parity to be written into the file store 23 by applying the difference data received by the data receiver 211 to the pre-updating parity stored in the file store 23.

(74) This allows the distributed storage system 100 to have a less disk volume. Specifically, the parity node 2 has no need to have a journal disk, so that the storage resource of the parity node 2 can be more effectively used. The parity node 2 does not have to write a journal and consequently the load on the disk I/O can be lightened when a journal is to be applied. Furthermore, a process of applying a journal to the file store 23 of the parity node 2 can be precisely accomplished.

(75) In the data node 1, the difference applier 116 generates the post-updating data to be written into the file store 13 by applying the difference data stored in the journal disk 14 to the pre-updating data stored in the file store 13.

(76) This can precisely accomplish the process of applying a journal to the file store 13 of the data node 1.

(77) The difference generator 113 generates the difference data through the calculation on the Galois Field using the updating data received from the superordinate device and the pre-updating data stored in the file store 13.

(78) This allows the difference generator 113 to easily calculate the difference.

(B) Others

(79) The technique disclosed above is not limited to the foregoing embodiment and various changes and modifications can be suggested without departing from the spirit of the above embodiment. The configurations and steps of the above embodiment can be omitted, selected, or combined according to the requirement.

(80) The disclosed storage system allows a distributed storage system to have a less disk volume.

(81) All examples and conditional language recited herein are intended for the pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present inventions have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.