Performing file system operations in a distributed key-value store

Patent metadata

Field	Value
Publication number	US-11288248-B2
Application number	US-201916256739-A
Country	US
Kind code	B2
Filing date	Jan 24, 2019
Priority date	Jun 25, 2014
Publication date	Mar 29, 2022
Grant date	Mar 29, 2022

Abstract

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.

First claim

What is claimed is:

1. A system, comprising:
a processor, wherein the processor:
receives from a client a message to perform a requested file system operation associated with a key-value pair, wherein the requested file system operation is a read request or a write request, wherein the message at least includes a key, a version number associated with the key-value pair, and a sequence number associated with the requested file system operation;
in response to receiving the message:
compares, for the read request, the sequence number associated with the requested file system operation included in the message with a stored sequence number associated with the key;
determines, for the read request, whether the sequence number associated with the read request is greater than or equal to the stored sequence number associated with the key; and
performs a read operation in response to a determination that the sequence number associated with read request included in the message is greater than or equal to the stored sequence number associated with the key; or
compares, for the write request, 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, for the write request, 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 a 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, wherein the stored sequence number associated with the key is updated in the event the requested file system operation associated with the key is performed; and

a memory coupled to the processor, wherein the memory provides the processor with instructions.

2. The system of claim 1 , wherein in the event the sequence number associated with the requested file system operation is not greater than or equal to the stored sequence number associated with the key, the processor reports an error to the client.

3. The system of claim 1 , wherein in the event the sequence number associated with the read request included in the message is greater than or equal to the stored sequence number associated with the key, the processor reads data associated with the key.

4. The system of claim 3 , wherein to read the data associated with the key, the processor determines a consensus value between at least two of a plurality of nodes of the system.

5. The system of claim 3 , wherein in the event the sequence number associated with the read request included in the message is greater than the stored sequence number associated with the key, the processor converts the read operation associated with the read request to a write operation.

6. The system of claim 5 , wherein the write operation includes incrementing the stored sequence number associated with the key.

7. The system of claim 6 , wherein the processor returns the read data to the client.

8. The system of claim 1 , wherein, for the write request, in the event the sequence number associated with the requested file system operation is greater than or equal to the stored sequence number associated with the key, the processor writes data to the key.

9. The system of claim 8 , 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.

10. The system of claim 9 , wherein the processor updates the sequence number associated with the key.

11. The system of claim 10 , wherein the processor replicates the data to one or more other nodes of the system.

12. The system of claim 11 , wherein the data is replicated using a consensus algorithm.

13. The system of claim 1 , wherein the processor is associated with a first node of a plurality of nodes.

14. The system of claim 13 , wherein the plurality of nodes are configured to store corresponding portions of a distributed key-value store.

15. The system of claim 13 , wherein a value associated with the key is stored in at least two of the plurality of nodes.

16. The system of claim 13 , wherein a hashing mechanism is used to determine which node of the plurality of nodes to which a key-value pair is written.

17. A method, comprising:
receiving from a client a first message to perform a first requested file system operation associated with a first key-value pair, wherein the first requested file system operation is a read request, wherein the first message at least includes a first key, a version number associated with the first key-value pair, and a sequence number associated with the first requested file system operation;
in response to receiving the first message:
comparing the sequence number associated with the first requested file system operation included in the first message with a stored sequence number associated with the first key;
determining whether the sequence number associated with the first requested file system operation is greater than or equal to the stored sequence number associated with the first key; and
performing a read operation in response to determining that the sequence number associated with the first requested file system operation included in the first message is greater than or equal to the stored sequence number associated with the first key, wherein the stored sequence number associated with the first key is updated in the event a requested file system operation associated with the first key is performed;

receiving from the client a second message to perform a second requested file system operation with a second key-value pair, wherein the second requested file system operation is a write request, wherein the second message includes at least includes a second key, a version number associated with the second key-value pair, and a sequence number associated with the second requested file system operation;
in response to receiving the second message:
comparing the version number associated with the second key-value pair included in the second message with a stored version number associated with the second key-value pair, wherein the stored version number associated with the second key-value pair is incremented each time a value is written to the second key-value pair;
determining whether the version number associated with the second key-value pair included in the second message is equal to the stored version number associated with the second key-value pair; and
performing a write operation and incrementing the stored version number associated with the second key-value pair in response to determining that the version number associated with the key-value pair included in the second message is equal to the stored version number associated with the second key-value pair.

18. 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 first message to perform a first requested file system operation associated with a first key-value pair, wherein the first requested file system operation is a read request, wherein the first message at least includes a first key, a version number asso

Assignees

• Cohesity Inc

Inventors

• Reddy Vinay
• Aron Mohit
• Gupta Vipin
• Thomas Markose

Classifications

• G06F16/1774 Primary

  Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files · CPC title

• G06F16/2343

  Locking methods, e.g. distributed locking or locking implementation details · CPC title

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F16/951

  Indexing; Web crawling techniques · CPC title