Fast Retrieval Of Related Data Partitioned Across A Distributed Key-Value Store

• US 20180285427A1
• Filed: 03/31/2017
• Published: 10/04/2018
• Est. Priority Date: 03/31/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: KAPLAN, Shai, OLIVER, Yaniv Joseph, LIRAN, Noam, PREIZLER, Ido Yehiel
• Granted Patent: US 10,496,664 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A device configured to operate in a distributed network system includes a key-value processing system to generate at least one of a first request and a second request. The first request is to retrieve a selected one of a plurality of sub-groups of data. The first request includes a plurality of keys each including a first value identifying the selected one of the plurality of sub-groups and a respective one of a plurality of second values. Each of the second values identifies a respective subset of data within the selected one of the plurality of sub-groups. The second request is to retrieve a selected one of the subsets of data within the selected one of the plurality of sub-groups and includes a key. The key includes the first value and a selected one of the second values, and the selected one of the second values corresponds to a hash value.

Claims

1. A device configured to operate in a distributed network system, the device comprising:

a key-value processing system to selectively generate at least one of

a first request to retrieve, from a storage cluster, a selected one of a plurality of sub-groups of data, wherein the first request includes a plurality of keys, wherein each of the plurality of keys includes (i) a first value identifying the selected one of the plurality of sub-groups and (ii) a respective one of a plurality of second values, wherein each of the plurality of second values identifies a respective subset of data within the selected one of the plurality of sub-groups, and

a second request to retrieve, from the storage cluster, a selected one of the subsets of data within the selected one of the plurality of sub-groups of data, wherein the second request includes a key, wherein the key includes the first value and a selected one of the second values, and wherein the selected one of the second values corresponds to a hash value; and

a network interface to

transmit the at least one of the first request and the second request, and

receive at least one of the selected one of the plurality of sub-groups of data and the selected one of the subsets of data.

2. The device of claim 1, wherein the first value identifies a tenant associated with the storage cluster and the second values each identify a respective user within the tenant.

3. The device of claim 2, wherein each of the second values correspond to a hashed username of the respective user.

4. The device of claim 1, wherein each of the plurality of keys corresponds to x|h(y), wherein x is the first value, h(y) is the second value, y is a username associated with one of the subsets of data, and h(y) is a hash value resulting from applying a hash function to the username.

5. The device of claim 1, wherein the network interface is further to receive (i) a first subset of data within a first sub-group of data from a first key-value storage node of the storage cluster and (ii) a second subset of data within the first sub-group of data from a second key-value storage node of the storage cluster.

6. The device of claim 1, wherein, to generate the first request to retrieve the selected one of the sub-groups of data, the device is further to generate the plurality of keys such that each of the plurality of keys includes a different one of the second values.

7. The device of claim 6, wherein the plurality of keys include p of the second values, wherein p is an integer greater than one, and wherein p corresponds to a hash range.

8. The device of claim 7, wherein p is less than a quantity of users associated with a respective one of the sub-groups of data.

9. The device of claim 1, wherein the key-value processing system includes:

a processor; and

a tangible machine readable medium storing machine readable instructions that, when executed by the processor, configure the key-value processing system to retrieve the at least one of the first request and the second request.

10. A method for operating a device in a distributed network system, the method comprising:

selectively generating, using the device, at least one of

a first request to retrieve, from a storage cluster, a selected one of a plurality of sub-groups of data, wherein the first request includes a plurality of keys, wherein each of the plurality of keys includes (i) a first value identifying the selected one of the plurality of sub-groups and (ii) a respective one of a plurality of second values, wherein each of the plurality of second values identifies a respective subset of data within the selected one of the plurality of sub-groups, and

a second request to retrieve, from the storage cluster, a selected one of the subsets of data within the selected one of the plurality of sub-groups of data, wherein the second request includes a key, wherein the key includes the first value and a selected one of the second values, and wherein the selected one of the second values corresponds to a hash value;

transmitting the at least one of the first request and the second request from the device; and

receiving, at the device, at least one of the selected one of the plurality of sub-groups of data and the selected one of the subsets of data.

11. The method of claim 10, wherein the first value identifies a tenant associated with the storage cluster and the second values each identify a respective user within the tenant.

12. The method of claim 11, wherein each of the second values correspond to a hashed username of the respective user.

13. The method of claim 10, wherein each of the plurality of keys corresponds to x|h(y), wherein x is the first value, h(y) is the second value, y is a username associated with one of the subsets of data, and h(y) is a hash value resulting from applying a hash function to the username.

14. The method of claim 10, further comprising receiving (i) a first subset of data within a first sub-group of data from a first key-value storage node of the storage cluster and (ii) a second subset of data within the first sub-group of data from a second key-value storage node of the storage cluster.

15. The method of claim 10, wherein generating the first request to retrieve the selected one of the sub-groups of data includes generating the plurality of keys such that each of the plurality of keys includes a different one of the second values.

16. The method of claim 15, wherein the plurality of keys include p of the second values, wherein p is an integer greater than one, and wherein p corresponds to a hash range.

17. The method of claim 16, wherein p is less than a quantity of users associated with a respective one of the sub-groups of data.

18. The method of claim 10, further comprising generating a third request to store data, as one of the subsets of data, within the selected one of the plurality of sub-groups of data.

19. A key-value processing system for a device in a distributed network system, the key-value processing system comprising:

a processor; and

a tangible machine readable medium storing machine readable instructions that, when executed by the processor, configure the key-value processing system to

selectively generate at least one of

a first request to retrieve a selected one of a plurality of sub-groups of data, wherein the first request includes a plurality of keys, wherein each of the plurality of keys includes (i) a first value identifying the selected one of the plurality of sub-groups and (ii) a respective one of a plurality of second values, wherein each of the plurality of second values identifies a respective subset of data within the selected one of the plurality of sub-groups, and

a second request to retrieve a selected one of the subsets of data within the selected one of the plurality of sub-groups of data, wherein the second request includes a key, wherein the key includes the first value and a selected one of the second values, and wherein the selected one of the second values corresponds to a hash value.

20. The key-value processing system of claim 19, the instructions further to configure the key-value processing system to:

transmit the at least one of the first request and the second request; and

receive at least one of the selected one of the plurality of sub-groups of data and the selected one of the subsets of data.