PERFORMING FILE SYSTEM OPERATIONS IN A DISTRIBUTED KEY-VALUE STORE
Techniques are disclosed for managing a high performance, fault-tolerant, strongly consistent, distributed key-value store system. The key-value store may store information, such as metadata for a distributed file system. Fault-tolerance means that the distributed key-value store continues to provide access to values in the key-value store in spite of a certain number of node failures. To provide this capability, the key-value store may store copies of (key, value) pair on N+1 nodes in order to provide fault tolerance for the failure of up to N nodes. In addition, metadata describing which nodes store a given value is stored on 2N+1 nodes and the distributed key-value store is sized such that there are 3N+1 nodes in a cluster. Doing so allows the key, value store to tolerate a failure of N nodes, while still maintaining a consistent and available key-value store.
1 . (canceled)
2 . A system, comprising:
a processor, wherein the processor:
receives from a client a message to perform a write operation associated with a key-value pair, wherein the message at least includes a key, a version number associated with the key-value pair, and a sequence number associated with the write operation;
in response to receiving the message:
compares the version number associated with the key-value pair included in the message with a stored version number associated with the key-value pair, wherein the stored version number associated with the key-value pair is incremented each time a value is written to the key-value pair;
determines whether the version number associated with the key-value pair included in the message is equal to the stored version number associated with the key-value pair; and
performs the write operation and increments the stored version number associated with the key-value pair in response to a determination that the version number associated with the key-value pair included in the message is equal to the stored version number associated with the key-value pair; and
a memory coupled to the processor, wherein the memory provides the processor with instructions.
3 . The system of claim 2 , wherein in the event the sequence number associated with the write operation is not greater than or equal to a stored sequence number associated with the key, the processor reports an error to the client.
4 . The system of claim 2 , wherein in the event the sequence number associated with the write operation is greater than or equal to a stored sequence number associated with the key, the processor writes data to the key.
5 . The system of claim 4 , wherein the key is associated with at least the stored version number associated with the key-value pair, the stored sequence number associated with the key, and the data.
6 . The system of claim 5 , wherein the processor updates the sequence number associated with the key.
7 . The system of claim 6 , wherein the processor replicates the data to one or more other nodes of the system.
8 . The system of claim 7 , wherein the data is replicated using a consensus algorithm.
9 . The system of claim 2 , wherein the processor is associated with a first node of a plurality of nodes.
10 . The system of claim 9 , wherein the plurality of nodes is configured to store corresponding portions of a distributed key-value store.
11 . The system of claim 9 , wherein a value associated with the key is stored in at least two of the plurality of nodes.
12 . The system of claim 9 , wherein a hashing mechanism is used to determine which node of the plurality of nodes to which a key-value pair is written.
13 . A method, comprising:
receiving from a client a message to perform a write operation associated with a key-value pair, wherein the message at least includes a key, a version number associated with the key-value pair, and a sequence number associated with the write operation;
in response to receiving the message:
comparing the version number associated with the key-value pair included in the message with a stored version number associated with the key-value pair, wherein the stored version number associated with the key-value pair is incremented each time a value is written to the key-value pair;
determining whether the version number associated with the key-value pair included in the message is equal to the stored version number associated with the key-value pair; and
performing the write operation and incrementing the stored version number associated with the key-value pair in response to a determination that the version number associated with the key-value pair included in the message is equal to the stored version number associated with the key-value pair.
14 . The method of claim 13 , further comprising reporting an error to the client in response to determining that the sequence number associated with the write operation is not greater than or equal to a stored sequence number associated with the key.
15 . The method of claim 13 , further comprising writing data to the key in response to a determination that the sequence number associated with the write operation is greater than or equal to a stored sequence number associated with the key.
16 . The method of claim 14 , wherein the key is associated with at least the stored version number associated with the key-value pair, the stored sequence number associated with the key, and the data.
17 . The method of claim 15 , further comprising updating updates the sequence number associated with the key.
18 . The method of claim 17 , further comprising system replicating the data to one or more other nodes of the system.
19 . The method of claim 18 , wherein the data is replicated using a consensus algorithm.
20 . A computer program product, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:
receiving from a client a message to perform a write operation associated with a key-value pair, wherein the message at least includes a key, a version number associated with the key-value pair, and a sequence number associated with the write operation;
in response to receiving the message:
comparing the version number associated with the key-value pair included in the message with a stored version number associated with the key-value pair, wherein the stored version number associated with the key-value pair is incremented each time a value is written to the key-value pair;
determining whether the version number associated with the key-value pair included in the message is equal to the stored version number associated with the key-value pair; and
performing the write operation and incrementing the stored version number associated with the key-value pair in response to a determination that the version number associated with the key-value pair included in the message is equal to the stored version number associated with the key-value pair.
21 . The computer program product of claim 19 , further comprising instructions for reporting an error to the client in response to determining that the sequence number associated with the write operation is not greater than or equal to a stored sequence number associated with the key.