Techniques for ensuring consistency of data updates transactions in a distributed storage system

• US 9,881,044 B2
• Filed: 12/30/2014
• Issued: 01/30/2018
• Est. Priority Date: 12/31/2013
• Status: Active Grant

• Current Assignee: ReduxIO Systems Ltd. (Reduxio Systems, Inc.)
• Original Assignee: ReduxIO Systems Ltd. (Reduxio Systems, Inc.)
• Inventors: Peleg, Nir, Sagi, Or
• Primary Examiner(s): Mackes, Kris
• Assistant Examiner(s): Htay, Lin Lin
• Application Number:
  US14/586,391
• Publication Number:
  US 20150186450A1
• Time in Patent Office: 1,127 Days
• Field of Search: 707690
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

A method and system for ensuring consistency in data updates transactions in a distributed storage system (DSS) are provided. The method includes receiving an aggregated transaction request comprising monotonous transaction requests, wherein each monotonous transaction request is initiated by at least one computing node of a plurality of computing of nodes in the DSS, wherein the root computing node and the plurality of computing nodes are arranged in a tree structure; generating a range of transaction indexes based on the aggregated transaction request; and passing the generated range of transaction indexes along the plurality of computing nodes according to their respective level in the tree structure hierarchy, wherein each of the plurality of computing nodes initiating the monotonous transaction request is allocated with a unique portion of the aggregated transaction indexes, thereby ensuring time-order access to at least one storage device in the DSS.

Claims

1. A method for ensuring consistency in data updates transactions in a distributed storage system (DSS), comprising:

receiving, at a root computing node in the DSS, an aggregated transaction request comprising transaction requests, wherein each transaction request includes at least one operation of updating data in the DSS and wherein each transaction request is initiated by at least one computing node of a plurality of computing nodes in the DSS and wherein the root computing node and the plurality of computing nodes are arranged in a tree structure;

generating a range of increasing transaction indexes based on the aggregated transaction request, wherein each of the transaction indexes determines a time-order access to at least one storage device in the DSS by the at least one computing node of the plurality of computing nodes;

aggregating, by each computing node of the plurality of computing nodes directly connected to the root computing node, transaction requests received from nodes at a lower hierarchy, wherein the aggregation of transaction requests results with the aggregated transaction request;

sending the aggregated transaction request to the root computing node; and

passing the generated range of transaction indexes along the plurality of computing nodes according to their respective level in the tree structure hierarchy, wherein each of the plurality of computing nodes initiating the transaction request is allocated with a unique portion of the aggregated transaction indexes, thereby ensuring time-order access to the at least one storage device in the DSS.

2. The method of claim 1, wherein the root computing node is a node in any computing node of the plurality of computing nodes selected to be at a higher hierarchy of the tree structure.

3. The method of claim 1, wherein the selection of the root computing node is based on at least one of:

an arbitrary selection and a preconfigured policy.

4. The method of claim 3, wherein the range of transaction indexes further determines time-order access to the at least one storage device in the DSS during a time frame.

5. The method of claim 1, wherein each one of the plurality of computing nodes is a computing device including any one of:

a cellular phone, a smartphone, a tablet device, a notebook computer, a personal computer (PC), a laptop, and a wearable computing device.

6. The method of claim 1, wherein the plurality of computing nodes, the root computing node, and the at least one storage device are communicatively connected by a network.

7. A non-transitory computer readable medium having stored thereon instructions for causing one or more processing units to execute the method comprising:

receiving, at a root computing node in the DSS, an aggregated transaction request comprising transaction requests, wherein each transaction request includes at least one operation of updating data in the DSS and wherein each transaction request is initiated by at least one computing node of a plurality of computing nodes in the DSS and wherein the root computing node and the plurality of computing nodes are arranged in a tree structure;

generating a range of increasing transaction indexes based on the aggregated transaction request, wherein each of the transaction indexes determines a time-order access to at least one storage device in the DSS by the at least one computing node of the plurality of computing nodes;

aggregating, by each computing node of the plurality of computing nodes directly connected to the root computing node, transaction requests received from nodes at a lower hierarchy, wherein the aggregation of transaction requests results with the aggregated transaction request;

sending the aggregated transaction request to the root computing node; and

passing the generated range of transaction indexes along the plurality of computing nodes according to their respective level in the tree structure hierarchy, wherein each of the plurality of computing nodes initiating the transaction request is allocated with a unique portion of the aggregated transaction indexes, thereby ensuring time-order access to the at least one storage device in the DSS.

8. A distributed storage system, comprising:

at least one storage device; and

a plurality of computing nodes communicatively connected to the at least one storage device, wherein one of the plurality of computing nodes is configured to operate as a root computing node, wherein the root computing node is further configured to;

receive an aggregated transaction request comprising transaction requests, wherein each transaction request includes at least one operation of updating data in a distributed storage system (DSS) and wherein each transaction request is initiated by at least a first computing node of the plurality of computing nodes in the DSS and wherein the plurality of computing nodes are arranged in a tree structure;

generate a range of increasing transaction indexes based on the aggregated transaction request, wherein each of the transaction indexes determines a time-order access to at least one storage device in the DSS by a computing node;

aggregate, by each computing node of the plurality of computing nodes directly connected to the root computing node, transaction requests received from nodes at a lower hierarchy, wherein the aggregation of transaction requests results with the aggregated transaction request;

send the aggregated transaction request to the root computing node; and

pass the generated range of transaction indexes along the plurality of computing nodes according to their respective level in the tree structure hierarchy, wherein each computing node initiating the transaction request is allocated with a unique portion of the aggregated transaction indexes, thereby ensuring time-order access to the at least one storage device in the DSS.

9. The distributed storage system of claim 8, wherein the root computing node is any computing node of the plurality of computing nodes selected to be at a higher hierarchy of the tree structure.

10. The distributed storage system of claim 8, wherein the selection of the root node is based on at least one of:

an arbitrary selection and a preconfigured policy.

11. The distributed storage system of claim 8, wherein the range of transaction indexes further determines time-order access to the at least one storage device in the DSS during a time frame.

12. The distributed storage system of claim 8, wherein each one of the plurality of computing nodes is a computing device including any one of:

a cellular phone, a smartphone, a tablet device, a notebook computer, a personal computer (PC), a laptop, and a wearable computing device.

13. The distributed storage system of claim 8, wherein the plurality of computing nodes and the at least one storage device are communicatively connected by a network.