Distributed file system using consensus nodes

• US 9,424,272 B2
• Filed: 09/30/2013
• Issued: 08/23/2016
• Est. Priority Date: 01/12/2005
• Status: Active Grant

• Current Assignee: Cirata Incorporated
• Original Assignee: WANdisco, Inc.
• Inventors: Shvachko, Konstantin V, Sundar, Jagane, Parkin, Michael, Aahlad, Yeturu
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US14/041,894
• Publication Number:
  US 20150067004A1
• Time in Patent Office: 1,058 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/166 File name conversion
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A cluster of nodes in a distributed file system may include; at least two namenodes, each coupled to a plurality of data nodes and each configured to store a state of a namespace of the cluster and each being configured to respond to a request from a client while other(s) of the namenodes are responding to other requests from other clients; and a coordination engine coupled to each of the namenodes. The coordination engine may be configured to receive proposals from the namenodes to change the state of the namespace by replicating, deleting and/or adding data blocks stored in the data nodes and to generate, in response, an ordered set of agreements that specifies an order in which the namenodes are to change the state of the namespace. The namenodes are configured to delay making changes thereto until after the ordered set of agreements is received from the coordination engine.

Claims

1. A computer-implemented method of implementing a distributed file system comprising an entire cluster comprising a plurality of data nodes configured to store data blocks of client files, the method, comprising:

coupling at least two active namenodes to a plurality of data nodes, each active namenode of the active namenodes being configured to store a state of a same namespace of the entire cluster, the namespace including at least a location within each data node of the plurality of data nodes of each data block of the client files across the entire cluster, said each active namenode of the at least two active namenodes being configured to respond to any request from any client of the distributed file system to generate a new data block or enable a new data block to be stored on any of the data nodes while at least one other of the active namenodes is responding to any other request from the same or any other client to generate another new data block or enable another new data block to be stored on any of the data nodes, only one of the active namenodes being configured to respond to requests from any client to replicate or delete data blocks from the data nodes;

receiving, by using a computer system, proposals from the active namenodes to change the state of the namespace, and

generating, in response to receiving the proposals, an ordered set of agreements that specifies an order in which the active namenodes are to change the state of the namespace and assigning a unique global sequence number (GSN) to each agreement of the ordered set of agreements, the GSN specifying an order in which the active namenodes are to apply changes to the state of the namespace, such that the active namenodes delay making the changes to the state of the namespace until the active namenodes receive the ordered set of agreements and apply the changes to the state of the namespace in the order specified by the GSN of each received agreement of the received agreements.

2. The computer-implemented method of claim 1, further comprising storing an image of the namespace and entries specifying updates to the namespace in local storage coupled to each active namenode of the plurality of active namenodes.

3. The computer-implemented method of claim 1 further comprising configuring the active namenode configured to enable replication and deletion of data blocks to periodically issue a block replicator heartbeat message.

4. The computer-implemented method of claim 3, further comprising triggering an election process to elect a new active namenode that is to be solely configured to enable replication and deletion of data blocks upon failure of the active namenode configured to enable replication and deletion of data blocks to periodically issue the block replicator heartbeat.

5. The method of claim 4 wherein the election process is configured to be initiated by any of the active namenodes.

6. The computer-implemented method of claim 1, further comprising configuring each active namenode of the active namenodes to enable data blocks stored on one of the plurality of data nodes to be replicated to a predetermined other one or other ones of the plurality of data nodes.

7. The computer-implemented method of claim 6, further comprising configuring at least one of the data nodes, upon receipt of data blocks, to send the data blocks to another of the plurality of data nodes identified by one of the active namenodes.

8. The computer-implemented method of claim 1, further comprising configuring each data node of the plurality of data nodes to periodically issue a heartbeat message to the active namenodes, indicating a current status of the data node.

9. The computer-implemented method of claim 8, further comprising configuring the active namenodes to consider a data node from which the heartbeat message has not been timely received to have failed.

10. The computer-implemented method of claim 1, further comprising configuring only one of the active namenodes to enable data blocks stored in a failed data node to be replicated to another selected one of the plurality of data nodes.

11. The computer-implemented method of claim 1, further comprising configuring each active namenode of the active namenodes to assign a unique block identifier (ID) to data blocks from within a sub-range of a larger range of block ID numbers that is separate from other respective sub-ranges of the larger range of block IDs from which other ones of the active namenodes assign block ID numbers.

12. The computer-implemented method of claim 1, further comprising setting a communication timeout configured such that, if an active namenode having received a client request has not responded thereto at an expiry of the communication timeout, the client request is made to another of the active namenodes.

13. The computer-implemented method of claim 1, further comprising enabling all of the active namenodes in the cluster to actively support client requests simultaneously.

14. The computer-implemented method of claim 1 wherein, upon failure of one of the active namenodes, making client requests previously made to the failed namenode to an other one of the active namenodes.

15. The computer-implemented method of claim 14 wherein, prior to making client requests to the other active namenode, waiting until the other active namenode updates its namespace.

16. The computer-implemented method of claim 1, further comprising each active namenode of the active namenodes, to prevent stale reads, submitting a coordinated read proposal to a coordination engine when a request is received to read a file that is determined to satisfy selected file name patterns and enabling the file to be read only upon receiving an agreement corresponding to the coordinated read proposal.

17. The computer-implemented method of claim 1, further comprising enabling a new active namenode to be brought into the cluster, wherein the new name node is configured to update the state of its namespace by at least one of:

loading a checkpoint comprising a prior image of the namespace, and

accepting agreements to its namespace from a coordination engine.

18. The computer-implemented method of claim 1, wherein the received proposals are configured to change the namespace by at least one of replicating, deleting and adding data blocks in at least one of the plurality of data nodes.

19. A non-transitory machine-readable medium having data stored thereon representing sequences of instructions which, when executed by computing devices, cause the computing devices to implement a distributed file system by:

coupling at least two active namenodes to a plurality of data nodes, each active namenode of the active namenodes being configured to store a state of a same namespace of an entire cluster, the namespace including at least a location within each data node of the plurality of data nodes of each data block of client files across the entire cluster, said each active namenode of the at least two active namenodes being configured to respond to any request from any client of the distributed file system to generate a new data block or enable a new data block to be stored on any of the data nodes while at least one other of the active namenodes is responding to any other request from the same or any other client to generate another new data block or enable another new data block to be stored on any of the data nodes, only one of the active namenodes being configured to respond to requests from any client to replicate or delete data blocks from the data nodes;

receiving proposals from the active namenodes to change the state of the namespace, and

generating, in response to receiving the proposals, an ordered set of agreements that specifies an order in which the active namenodes are to change the state of the namespace and assigning a unique global sequence number (GSN) to each agreement of the ordered set of agreements, the GSN specifying an order in which the active namenodes are to apply changes to the state of the namespace, such that the active namenodes delay making the changes to the state of the namespace until the active namenodes receive the ordered set of agreements and apply the changes to the state of the namespace in the order specified by the GSN of each received agreement of the received agreements.

20. The non-transitory machine-readable medium of claim 19, wherein the received proposals are configured to change the namespace by at least one of replicating, deleting and adding data blocks in at least one of the plurality of data nodes.