Systems for storing files in a distributed environment

• US 8,914,333 B2
• Filed: 04/08/2014
• Issued: 12/16/2014
• Est. Priority Date: 05/24/2011
• Status: Active Grant

• Current Assignee: Red Lambda Incorporated
• Original Assignee: Red Lambda Incorporated
• Inventors: Bird, Robert, Whitlock, Matthew
• Primary Examiner(s): To, Baoquoc N
• Application Number:
  US14/247,770
• Publication Number:
  US 20140222829A1
• Time in Patent Office: 252 Days
• Field of Search: 707/673
• US Class Current: 707/673
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

A system and method for storing data-files stored on distributed devices connected to a network. Data-elements of the data-files are allocated to data-blocks stored on the distributed devices. Key-identifiers are calculated for each of the data-blocks based on the allocated data-elements. The key-identifiers are stored in distributed tables stored on the distributed devices. Index-nodes are generated for the data-files based on the data-blocks. A Paxos algorithm is executed for the index-nodes based on the key-identifiers to provide a consensus of the data-files that are stored on the plurality of distributed devices.

Claims

1. A system for storing data, comprising:

data-blocks stored on a plurality of distributed devices, wherein each one of the plurality of distributed devices comprises a processor, the plurality of distributed devices are adapted to be connected via a network, the plurality of distributed devices store data-files, the data-files comprising data-elements;

the stored data-elements are allocated via the processors to the data-blocks;

key-identifiers calculated for each of the data-blocks, the key-identifiers are based on the allocated data-elements of the corresponding data-blocks;

distributed tables that store the key-identifiers, the distributed tables are stored on the plurality of distributed devices;

index-nodes for the data-files generated based on the data-blocks, the index-nodes comprising a list of the data-blocks, the index-nodes are stored in a metadata-store; and

,

a Paxos algorithm executed for the index-nodes based on the key-identifiers to provide a consensus of the data-files that are stored on the plurality of distributed devices.

2. The system of claim 1, wherein the key-identifiers comprise hash values, wherein the distributed tables are distributed hash tables.

3. The system of claim 1, wherein the data-blocks are binary large objects, wherein each of the binary large objects is less than a maximum predetermined size.

4. The system of claim 3, wherein each of the binary large objects is associated with a unique address, wherein each unique address is based on the allocated data-elements of the corresponding binary large object.

5. The system of claim 1, wherein the stored data-files are allocated to data-blocks based on a Kademlia algorithm.

6. The system of claim 1, wherein the data-blocks are logically grouped together, and wherein each one of the data-blocks are read and written as a single unit.

7. The system of claim 1, further comprising:

directory index-nodes generated for a plurality of index-nodes, wherein the directory index-nodes are stored in the metadata-store.

8. The system of claim 1, wherein the plurality of processors are adapted to communicate across the network.

9. The system of claim 1, wherein the key-identifiers are globally unique block-identifiers.

10. The system of claim 1, further comprising:

a request received to modify an index-node;

a Paxos algorithm configured for a quorum of nodes that correspond to the data-blocks having near-values in the distributed table, wherein the near-values are hash values that are within a predetermined range of a hash value of the index-node;

the index-node configured based on an outcome of the Paxos algorithm; and

,

the nodes in the quorum configured based on the modified index-node, wherein a consensus of the nodes is provided based on the outcome of the Paxos algorithm.

11. The system of claim 10, wherein the consensus is provided by executing voting-rounds for a quorum of nodes.

12. The system of claim 11, wherein the voting-rounds comprise:

round-invitations transmitted to the nodes in the quorum, wherein the nodes in the quorum are acceptors;

replies received from each acceptor, wherein the replies are round-acceptances comprising a last-voted-value and a round-number, wherein the round-number represents the voting-round in which the corresponding acceptor voted the last-voted-value; and

,

a value configured based the last-voted-values received from the acceptors.

13. The system of claim 12, further comprising:

vote-invitations transmitted to the acceptors, wherein the vote-invitations comprise the selected value.

14. The system of claim 12, wherein the value is selected based on the last-voted-values from a majority of the acceptors.

15. The system of claim 12, further comprising:

a value-announcement transmitted from the acceptors to the nodes in the quorum, wherein the value-announcement comprises the selected value, wherein the nodes in the quorum reject a value that is different from the selected value.

16. The system of claim 1, wherein at least one of the index-nodes is encoded based on an Abstract Syntax Notation One (ASN.1) encoding standard.

17. The system of claim 1, wherein at least one of the index-nodes is encoded based on a Distinguished Encoding Rules (DER) message-transfer syntax.

18. The system of claim 17, wherein the Distinguished Encoding Rules (DER) message-transfer syntax is based on a X.690 International Telecommunication Union (ITU)-T recommendation.

19. The system of claim 1, further comprising:

a round-invitation received by an acceptor from a coordinator, wherein the round-invitation comprises a generation-number;

an inquiry transmitted by the acceptor to the coordinator, only if the generation-number in the round-invitation is greater than a generation-number of the acceptor;

a notification transmitted by the acceptor to the coordinator, only if the generation-number in the round-invitation is less than the generation-number of the acceptor; and

,

only if the generation-number in the round-invitation is equal to the generation-number of the acceptor, then;

(i) a round-begun notification transmitted by the acceptor to the coordinator, only if a round-number in the round-invitation is less than the record-number of the acceptor;

(ii) the round-invitation ignored by the acceptor, only if the round-number in the round-invitation is equal to the round-number of the acceptor; and

,

(iii) the round-number updated in the acceptor to match the round-number in the round-invitation and a round-acceptance transmitted to the coordinator, only if the round-number in the round-invitation is greater than the round-number in the acceptor.

20. The system of claim 1, further comprising:

a round-acceptance received by a coordinator from an acceptor, wherein the round-acceptance comprises a generation-number;

the round-acceptance ignored by the coordinator, only if the generation-number in the round-acceptance is different from the generation-number of the coordinator; and

,

only if the generation-number of the coordinator is equal to the generation-number of the round-acceptance, then;

(i) the round-acceptance ignored by coordinator, only if the round-number in the round-acceptance is different from the round-number on the coordinator; and

,

(ii) only if the round-number in the round-acceptance is equal to the round-number on the coordinator, then;

(a) the round-acceptance ignored by coordinator, only if the coordinator has already received a round-acceptance from the acceptor in the current generation and round; and

,

(b) a last-voted-value tracked by the coordinator in the round-acceptance received from the acceptor, only if the coordinator has not already received a round-acceptance from the acceptor in the current generation and round.

21. The system of claim 1, further comprising:

a round-acceptance received by a coordinator from a majority of acceptors, wherein the majority of acceptors are acceptors that received round-invitations from the coordinator, wherein the round-acceptance comprises a generation-number;

a last-voted-value selected by the coordinator, wherein the last-voted-value is a value that the coordinator received from the acceptor in the highest-numbered round;

only if the acceptors failed to vote in the current generation, a proposed-value selected by the coordinator; and

,

a vote-invitation transmitted by the coordinator to each of the acceptors, wherein the vote-invitation is the proposed-value only if the acceptors failed to vote in the current generation, wherein the vote-invitation is the last-voted-value only if the acceptors voted in the current generation.

22. The system of claim 1, further comprising:

a vote-invitation received by an acceptor from a coordinator, wherein the vote-invitation comprises a generation-number;

the vote-invitation ignored by the acceptor, only if the generation-number in the vote-invitation is different from the generation-number on the acceptor; and

,

only if the generation-number of the acceptor is equal to the generation-number of the vote-acceptance, then;

(i) a round-begun notification transmitted by the acceptor to the coordinator, only if a round-number in the vote-invitation is less than the record-number of the acceptor; and

,

(ii) only if a round-number in the vote-invitation is equal to the record-number of the acceptor, then;

(a) the vote-acceptance ignored by acceptor, only if the acceptor has already voted in the current generation and round; and

,

(b) a vote-announcement transmitted from the acceptor to learners listed in the vote-invitation, only if the acceptor has not already voted in the current generation and round.

23. The system of claim 1, further comprising:

a vote-announcement received by a learner from an acceptor, wherein the vote-announcement comprises a generation-number;

the vote-announcement ignored by the learner, only if the generation-number in the vote-announcement is different from the generation-number of the learner; and

only if the generation-number of the learner is equal to the generation-number of the vote-announcement, then;

(i) the vote-announcement ignored by the learner, only if the round-number in the vote-announcement is less than the round-number of the learner; and

,

(ii) only if a round-number in the vote-announcement is equal to or greater than the record-number of the learner, then;

(a) the vote-acceptance ignored by learner, only if the learner has already received a vote-announcement from the acceptor in the current generation and round; and

,

(b) the vote received from the acceptor tracked by the learner, only if the learner has not already received a vote-announcement from the acceptor in the current generation and round.

24. The system of claim 1, further comprising:

a vote-announcement received by a learner from a majority of acceptors, wherein the vote-announcements have a pre-determined majority-number for determining a quantity needed for the majority of acceptors, wherein the vote-announcements comprise a generation-number and a value; and

,

only if the values of all of the vote-announcements are equal, then the learner tracks the value of the vote-announcements and the learner increments the generation-number for a next-iteration of the Paxos algorithm.

25. The system of claim 1, further comprising:

a round-begun notification received by the coordinator to the acceptor;

the round-begun notification ignored by the coordinator, only if the generation-number in the round-begun notification is different from the generation-number on the coordinator; and

,

only if the generation-number in the round-begun notification is equal to the generation-number on the coordinator, then;

(i) the round-begun notification ignored by the coordinator, only if the round-number in the round-begun notification is less than or equal to the round-number on the coordinator; and

,

(ii) a new round-number selected by the coordinator that is greater than the round-number in the round-begun notification and a round-invitation transmitted to each of the acceptors, only if the round-number in the round-begun notification is greater than the round-number on the coordinator.

26. The system of claim 1, further comprising:

an inquiry received from a sender by a receiver, wherein the sender is a sending-node, wherein the receiver is a receiving-node;

a notification transmitted by the receiver to the sender, wherein the notification comprises a generation-number and a value of the receiver; and

,

only if the sender receives the notification, then;

(i) the notification ignored by the receiver, only if the generation-number in the notification is less than the generation-number of the receiver; and

,

(ii) only if the generation-number in the notification is equal to or greater than the generation-number on the receiver, the value in the notification tracked by the receiver and the generation-number in the receiver set to a number equal to one value greater than the generation-number in the notification for the next-iteration of the Paxos algorithm.

27. A non-transitory computer readable medium having computer readable instructions stored thereon for execution by a processor, wherein the instructions on the non-transitory computer readable medium are adapted to:

allocating data-elements of stored data-files to data-blocks, wherein the stored data-files are stored on a plurality of distributed devices, wherein the plurality of distributed devices are connected to a network, wherein the data-blocks are stored on the plurality of distributed devices;

calculating key-identifiers for each of the data-blocks, wherein the key-identifiers are based on the allocated data-elements of the corresponding data-blocks;

storing the key-identifiers in distributed tables, wherein the distributed tables are stored on the plurality of distributed devices;

generating index-nodes for the data-files based on the data-blocks, wherein the index-nodes comprise a list of the data-blocks, wherein the index-nodes are stored in a metadata-store; and

,

executing a Paxos algorithm for the index-nodes based on the key-identifiers to provide a consensus of the data-files that are stored on the plurality of distributed devices.