READ-MODIFY-WRITE PROTOCOL FOR MAINTAINING PARITY COHERENCY IN A WRITE-BACK DISTRIBUTED REDUNDANCY DATA STORAGE SYSTEM

• US 20110208995A1
• Filed: 02/22/2010
• Published: 08/25/2011
• Est. Priority Date: 02/22/2010
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: International Business Machines Corporation
• Inventors: Hafner, James L., Pandey, Prashant, Thakur, Tarun
• Granted Patent: US 8,103,903 B2
• Time in Patent Office: Days
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

Data storage reliability is maintained in a write-back distributed data storage system including multiple nodes, each node comprising a processor and an array of failure independent data storage devices. Information is stored as a set of stripes, each stripe including a collection of multiple data strips and associated parity strips, the stripes distributed across multiple corresponding primary data nodes and multiple corresponding parity nodes. A primary data node maintains the data strip holding a first copy of data, and each parity node maintains a parity strip holding a parity for the multiple data strips. A read-modify-write parity update protocol is performed for maintaining parity coherency, the primary data node driving parity coherency with its corresponding parity nodes, independently of other data nodes, in order to keep its relevant parity strips coherent.

Claims

1. A method of maintaining data storage reliability in a write-back distributed data storage system including multiple nodes, each node comprising an array of failure independent data storage devices, the method comprising:

storing information as a set of stripes, each stripe including a collection of multiple data strips and associated parity strips, the stripes distributed across multiple corresponding primary data nodes and multiple corresponding parity nodes;

a primary data node maintaining the data strip holding a first copy of data, and each parity node maintaining a parity strip holding a parity for the multiple data strips; and

performing a read-modify-write parity update protocol for maintaining parity coherency, a primary data node driving parity coherency with its corresponding parity nodes, independently of other data nodes, in order to keep its relevant parity strips coherent.

2. The method of claim 1, wherein:

each parity is calculated based on a different parity calculation formula; and

performing a read-modify-write parity update protocol further comprises;

the primary data node computing a difference between existing data and new data;

in a preparation phase;

the primary data node sending the difference to a first parity node, each parity node forwarding the difference to a next parity node in a predefined sequence;

each parity node reading the existing parity for the data, and computing a new parity from the difference;

starting from the last parity node in the sequence, each parity node sending an acknowledgement message to an immediately prior parity node in the sequence; and

the first parity node sending an acknowledgement message to the primary data node, indicating completion of the preparation phase.

3. The method of claim 2, wherein performing a read-modify-write parity update protocol further comprises:

in a commit phase;

the primary data node sending a commit message to the first parity node, each parity node forwarding the commit message to a next parity node in a predefined sequence;

each parity node committing its newly computed parity value;

starting from the last parity node in the sequence, each parity node sending an acknowledgement message to an immediately prior parity node in the sequence; and

the first parity node sending an acknowledgement message to the primary data node, indicating completion of the commit phase.

4. The method of claim 3 further comprising:

the primary data node maintaining at least two versions of the data for a strip, a fast write version and a parity-integrated version, wherein the fast write copy has been written into a storage system by a host or client and not integrated into a parity strip, and wherein the parity-integrated version has been incorporated into a process for defining a parity value; and

transitioning the fast write version to the parity-integrated version at completion of a parity update protocol at all relevant parity nodes, whereby the prior parity-integrated version may be discarded.

5. The method of claim 4 further comprising, in each parity node:

maintaining a working version of its parity strip value containing a current parity-integrated value for each of the data strips computed into that parity strip; and

at the end of the parity update as viewed by each parity node, the parity node transitioning the working version to the parity-integrated value and discarding a previous parity-integrated value.

6. The method of claim 3 further comprising:

during the preparation phase, upon a node failure, the lowest survivor node in a forward sequence driving an abort sequence for the read-modify-write parity update protocol; and

during the commit phase, upon a node failure, the lowest survivor node in the forward sequence driving a restart of the commit phase for the read-modify-write parity update protocol.

7. A write-back distributed data storage system for maintaining data storage reliability, comprising:

multiple nodes, each node comprising an array of failure independent data storage devices;

the nodes configured for storing information as a set of stripes, each stripe including a collection of multiple data strips and associated parity strips, the stripes distributed across multiple corresponding primary data nodes and multiple corresponding parity nodes, a primary data node configured for maintaining the data strip holding a first copy of data, and each parity node maintaining a parity strip holding a parity for the multiple data strips; and

the primary data node further configured for performing a read-modify-write parity update protocol for maintaining parity coherency, the primary data node driving parity coherency with its corresponding parity nodes, independently of other data nodes, in order to keep its relevant parity strips coherent.

8. The system of claim 7, wherein:

each parity is calculated based on a different parity calculation formula; and

the primary data node is further configured for computing a difference between existing data and new data;

in a preparation phase;

the primary data node sends the difference to a first parity node, each parity node forwards the difference to a next parity node in a predefined sequence;

each parity node reads the existing parity for the data, and computes a new parity from the difference;

starting from the last parity node in the sequence, each parity node sends an acknowledgement message to an immediately prior parity node in the sequence; and

the first parity node sends an acknowledgement message to the primary data node, indicating completion of the preparation phase.

9. The system of claim 8, wherein:

in a commit phase;

the primary data node sends a commit message to the first parity node, each parity node forwards the commit message to a next parity node in a predefined sequence;

each parity node commits its newly computed parity value;

starting from the last parity node in the sequence, each parity node sends an acknowledgement message to an immediately prior parity node in the sequence; and

the first parity node sends an acknowledgement message to the primary data node, indicating completion of the commit phase.

10. The system of claim 9, wherein:

the primary data node maintains at least two versions of the data for a strip, a fast write version and a parity-integrated version, wherein the fast write copy has been written into a storage system by a host or client and not integrated into a parity strip, and wherein the parity-integrated version has been incorporated into a process for defining a parity value.

11. The system of claim 10, wherein each parity node is further configured for:

maintaining a working version of its parity strip value containing a current parity-integrated value for each of the data strips computed into that parity strip; and

at the end of the parity update as viewed by each parity node, the parity node transitioning the working version to the parity-integrated value and discarding a previous parity-integrated value.

12. The system of claim 9, wherein:

during the preparation phase, upon a node failure, the lowest survivor node in a forward sequence drives an abort sequence for the read-modify-write parity update protocol; and

during the commit phase, upon a node failure, the lowest survivor node in the forward sequence drives a restart of the commit phase for the read-modify-write parity update protocol.

13. The system of claim 7, wherein:

the nodes are configured for storing information as plural stripes, each stripe including a collection of a data strip and associated parity strips, the stripes distributed across a primary data node and multiple corresponding parity nodes;

a specified parity node message forwarding order is maintained for each primary data node and corresponding parity nodes; and

each primary data node is configured for driving parity coherency with its corresponding parity nodes, independently of other data nodes, in keeping its relevant parity strips coherent.

14. A computer program product for maintaining data storage reliability in a write-back distributed data storage system including multiple nodes, each node comprising a an array of failure independent data storage devices, the computer program product comprising:

a computer readable medium having a computer usable program code embodied therewith, the computer usable program code comprising;

computer usable program code configured to store information as a set of stripes, each stripe including a collection of multiple data strips and associated parity strips, the stripes distributed across multiple corresponding primary data nodes and multiple corresponding parity nodes; and

computer usable program code configured for the primary data node to maintain the data strip holding a first copy of data, and each parity node to maintain a parity strip holding a parity for the multiple data strips and perform a read-modify-write parity update protocol for maintaining parity coherency, and the primary data node to drive parity coherency with its corresponding parity nodes, independently of other data nodes, in order to keep its relevant parity strips coherent.

15. The computer program product of claim 14 further comprising:

computer usable program code configured for calculating each parity based on a different parity calculation formula, and for the primary data node to compute a difference between existing data and new data;

computer usable program code configured for, in a preparation phase;

the primary data node to send the difference to a first parity node, each parity node forwarding the difference to a next parity node in a predefined sequence;

each parity node to read the existing parity for the data, and computing a new parity from the difference;

starting from the last parity node in the sequence, each parity node to send an acknowledgement message to an immediately prior parity node in the sequence; and

the first parity node to send an acknowledgement message to the primary data node, indicating completion of the preparation phase.

16. The computer program product of claim 15 further comprising:

computer usable program code for, in a commit phase;

the primary data node sending a commit message to the first parity node, each parity node forwarding the commit message to a next parity node in a predefined sequence;

each parity node committing its newly computed parity value;

starting from the last parity node in the sequence, each parity node sending an acknowledgement message to an immediately prior parity node in the sequence; and

the first parity node sending an acknowledgement message to the primary data node, indicating completion of the commit phase.

17. The computer program product of claim 16 further comprising:

computer usable program code configured for the primary data node maintaining at least two versions of the data for a strip, a fast write version and a parity-integrated version, wherein the fast write copy has been written into a storage system by a host or client and not integrated into a parity strip, and wherein the parity-integrated version has been incorporated into a process for defining a parity value;

computer usable program code configured for transitioning the fast write version to the parity-integrated version at completion of a parity update protocol at all relevant parity nodes, whereby the prior parity-integrated version may be discarded;

computer usable program code configured for each parity node performing;

maintaining a working version of its parity strip value containing a current parity-integrated value for each of the data strips computed into that parity strip; and

at the end of the parity update as viewed by each parity node, the parity node transitioning the working version to the parity-integrated value and discarding a previous parity-integrated value.

18. The computer program product of claim 16 further comprising:

computer usable program code configured for, during the preparation phase, upon a node failure, the lowest survivor node in a forward sequence driving an abort sequence for the read-modify-write parity update protocol.

19. The computer program product of claim 18 further comprising:

computer usable program code configured for, during the commit phase, upon a node failure, the lowest survivor node in the forward sequence driving a restart of the commit phase for the read-modify-write parity update protocol.

20. The computer program product of claim 14 further comprising:

computer usable program code configured for storing information as plural stripes, each stripe including a collection of a data strip and associated parity strips, the stripes distributed across a primary data node and multiple corresponding parity nodes;

computer usable program code configured for providing a specified parity node message forwarding order for each primary data node and corresponding parity nodes; and

computer usable program code configured for each primary data node driving parity coherency with its corresponding parity nodes, independently of other data nodes, in keeping its relevant parity strips coherent.