Methods for storing files in a distributed environment
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.
1. The method for storing data, comprising the steps of: 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.
2. The method of claim 1 , wherein the key-identifiers comprise hash values, wherein the distributed tables are distributed hash tables.
3. The method 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 method 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 method of claim 1 , wherein the stored data-files are allocated to data-blocks based on a Kademlia algorithm.
6. The method 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 method of claim 1 , further comprising the step of: generating directory index-nodes for a plurality of index-nodes, wherein the directory index-nodes are stored in the metadata-store.
8. The method of claim 1 , wherein the steps are performed by a plurality of processors operably connected to the distributed devices and adapted to communicate across the network.
9. The method of claim 1 , wherein the key-identifiers are globally unique block-identifiers.
10. The method of claim 1 , further comprising the steps of: receiving a request to modify an index-node; executing a Paxos algorithm 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; modifying the index-node based on an outcome of the Paxos algorithm; and, modifying the nodes in the quorum based on the modified index-node, wherein a consensus of the nodes is provided based on the outcome of the Paxos algorithm.
11. The method of claim 10 , wherein the consensus is provided by executing voting-rounds for a quorum of nodes.
12. The method of claim 11 , wherein the voting-rounds comprise the steps of: sending round-invitations to the nodes in the quorum, wherein the nodes in the quorum are acceptors; receiving replies 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, selecting a value based the last-voted-values received from the acceptors.
13. The method of claim 12 , further comprising the steps of: sending vote-invitations to the acceptors, wherein the vote-invitations comprise the selected value.
14. The method of claim 12 , wherein the value is selected upon receiving the last-voted-values from a majority of the acceptors.
15. The method of claim 12 , further comprising the steps of: sending a value-announcement 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 method 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 method 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 method 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 method of claim 1 , further comprising the steps of: receiving a round-invitation by an acceptor from a coordinator, wherein the round-invitation comprises a generation-number; sending an inquiry by the acceptor to the coordinator, only if the generation-number in the round-invitation is greater than a generation-number of the acceptor; sending a notification 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) sending a round-begun notification 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) ignoring the round-invitation by the acceptor, only if the round-number in the round-invitation is equal to the round-number of the acceptor; and, (iii) updating the round-number in the acceptor to match the round-number in the round-invitation and sending a round-acceptance to the coordinator, only if the round-number in the round-invitation is greater than the round-number in the acceptor.
20. The method of claim 1 , further comprising the steps of: receiving a round-acceptance by a coordinator from an acceptor, wherein the round-acceptance comprises a generation-number; ignoring the round-acceptance 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) ignoring the round-acceptance 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) ignoring the round-acceptance by coordinator, only if the coordinator has already received a round-acceptance from the acceptor in the current generation and round; and, (b) tracking by the coordinator a last-voted-value 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 method of claim 1 , further comprising the steps of: receiving a round-acceptance 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; selecting, by the coordinator, a last-voted-value, 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, selecting a proposed-value by the coordinator; and, sending, by the coordinator, a vote-invitation 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 method of claim 1 , further comprising the steps of: receiving a vote-invitation by an acceptor from a coordinator, wherein the vote-invitation comprises a generation-number; ignoring the vote-invitation 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) sending a round-begun notification 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) ignoring the vote-acceptance by acceptor, only if the acceptor has already voted in the current generation and round; and, (b) sending a vote-announcement 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 method of claim 1 , further comprising the steps of: receiving a vote-announcement by a learner from an acceptor, wherein the vote-announcement comprises a generation-number; ignoring the vote-announcement 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) ignoring the vote-announcement 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) ignoring the vote-acceptance by learner, only if the learner has already received a vote-announcement from the acceptor in the current generation and round; and, (b) tracking by the learner the vote received from the acceptor, only if the learner has not already received a vote-announcement from the acceptor in the current generation and round.
24. The method of claim 1 , further comprising the steps of: receiving a vote-announcement 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 method of claim 1 , further comprising the steps of: receiving a round-begun notification by the coordinator to the acceptor; ignoring the round-begun notification 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) ignoring the round-begun notification 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) selecting, by the coordinator, a new round-number that is greater than the round-number in the round-begun notification and sending a round-invitation 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 method of claim 1 , further comprising the steps of: receiving an inquiry from a sender by a receiver, wherein the sender is a sending-node, wherein the receiver is a receiving-node; sending a notification 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) ignoring the notification 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, then the receiver tracks the value in the notification and the receiver sets the generation-number in the receiver to a number equal to one value greater than the generation-number in the notification for the next-iteration of the Paxos algorithm.