Distributed key-value store

Patent metadata

Field	Value
Publication number	US-10235404-B2
Application number	US-201414315128-A
Country	US
Kind code	B2
Filing date	Jun 25, 2014
Priority date	Jun 25, 2014
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

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

We claim:

1. A method for accessing metadata in a distributed key-value store stored on a plurality of computing nodes, the method comprising:
performing, by a first one of the computing nodes, a file operation associated with the distributed key-value store, wherein the file operation associated with the distributed key-value store comprises a read/write operation and the file operation is associated with a first lock, wherein the first lock is associated with a first lock sequence number;
receiving, by the first one of the computing nodes, a message from a requesting client to perform a read operation to read a value stored in the distributed key-value store for the first key, wherein the message includes the first key and a second lock sequence number associated with the first key and wherein the requesting client holds a second lock for at least the first key, wherein the second lock sequence number is greater than the first lock sequence number;
determining that the second lock sequence number is greater than a stored sequence number stored with the first key in the distributed key-value store, wherein the stored sequence number is associated with a last read or write operation performed on a key value;
upon determining the second lock sequence number is greater than the stored sequence number stored with the first key in the distributed key-value store:
reading the value of the first key; and
converting the read operation to a write operation on the first key, wherein the write operation updates the stored sequence number;

returning the value of the first key to the requesting client;
receiving, by a second one of the computing nodes, a second message from the requesting client to perform a write operation to write a new value in the key-value store for a second key, wherein the second message includes the second key, the new value, a third lock sequence number and a version number, and wherein the requesting client holds a lock for at least the second key; and
upon determining the third lock sequence number is equal to or greater than a stored sequence number stored with the second key in the key value store and that the version number in the request matches a stored version number stored with the second key in the key value store, writing the new value in the distributed key-value store for the second key and incrementing the stored version number.

2. The method of claim 1 , wherein reading the value of the first key comprises, reaching consensus between at least two of the plurality of computing nodes regarding the value of the first key.

3. The method of claim 1 , further comprising:
upon determining the second lock sequence number is greater than the stored sequence number, updating the stored sequence number to a value of the lock sequence number.

4. The method of claim 1 , further comprising:
obtaining, by the requesting client, the second lock for at least the first key, wherein the second lock includes the second lock sequence number, and wherein the second lock sequence number is greater than any previous lock sequence number issued with a lock for the first key.

5. The method of claim 1 , further comprising:
identifying, by the requesting client, the first one of the computing nodes as operating as a primary node for the first key value.

6. The method of claim 5 , wherein the requesting client identifies the first one of the computing nodes by hashing the key value to identify a hash bucket, and wherein the first computing node holds a lock on keys which hashes to the identified bucket.

7. The method of claim 1 , wherein in the event the second lock sequence number is less than the stored sequence number stored with the first key in the distributed key-value store, the read operation is rejected.

8. The method of claim 1 , wherein the distributed key-value store can tolerate at most N node failures, wherein the first key and the value is stored on at least N+1 of the computing nodes, wherein location metadata indicating which of the computing nodes store the first key and the value is stored on at least 2N+1 nodes.

9. The method of claim 1 , wherein the metadata stores file system metadata for a distributed file system, and wherein the value includes at least a location of a file system object corresponding to the key or a file system object.

10. A system for providing a distributed key-value store stored on a plurality of computing nodes, each computing node comprising:
a processor; and
a memory storing one or more applications executed to manage access to the (k,v) key values stored by the key value store by performing on operation, the operation comprising:
performing, by a first one of the computing nodes, a file operation associated with the distributed key-value store, wherein the file operation associated with the distributed key-value store comprises a read/write operation and the file operation is associated with a first lock, wherein the first lock is associated with a first lock sequence number;
receiving, by the first one of the computing nodes, a message from a requesting client to perform a read operation to read a value stored in the distributed key-value store for the first key, wherein the message includes the first key and a second lock sequence number associated with the first key and wherein the requesting client holds a lock for at least the first key, wherein the second lock sequence number is greater than the first lock sequence number;
determining that the second lock sequence number is greater than a stored sequence number stored with the first key in the distributed key-value store, wherein the stored sequence number is associated with a last read or write operation performed on a key value;
upon determining the second lock sequence number is greater than the stored sequence number stored with the first key in the distributed key-value store:
reading the value of the first key; and
converting the read operation to a write operation on the first key, wherein the write operation updates the stored sequence number;

returning the value of the first key to the requesting client;
receiving, by a second one of the computing nodes, a second message from the requesting client to perform a write operation to write a new value in the key-value store for a second key, wherein the second message includes the second key, the new value, a third lock sequence number and a version number, and wherein the requesting client holds a lock for at least the second key;
upon determining the third lock sequence number is equal to or greater than a stored sequence number stored with the second key in the key value store and that the version number in the request matches a stored version number stored with the second key in the key value store, writing the new value in the distributed key-value store for the second key and incrementing the stored version number.

11. The system of claim 10 , wherein reading the value of the first key comprises, reaching consensus between at least two of the plurality of computing nodes regarding the value of the first key.

12. The system of claim 10 , wherein the operation further comprises:
upon determining the second lock sequence number is greater than the stored sequence number, updating the stored sequence number to a value of the lock sequence number.

13. The system of claim 10 , wherein the operation further comprises:
obtaining, by the requesting client, the second lock for at least the first key, wherein the second lock includes the second lock sequence number, and wherein the second lock sequence number is greater than any previous lock sequence number issued with a lock fo

Assignees

• Cohesity Inc

Inventors

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

Classifications

• G06F17/30864

  Physics · mapped topic

• G06F17/30171

  Physics · mapped topic

• G06F17/3033 Primary

  Physics · mapped topic

• G06F17/30362

  Physics · mapped topic

• G06F16/1774 Primary

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