Determining data location in a distributed data store

• US 8,990,243 B2
• Filed: 11/23/2011
• Issued: 03/24/2015
• Est. Priority Date: 11/23/2011
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Little, Mark Cameron
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US13/304,203
• Publication Number:
  US 20130132408A1
• Time in Patent Office: 1,217 Days
• Field of Search: None
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2255 Hash tables

Abstract

A computing device identifies a location of a data item in a distributed data store. The computing device generates at least one probabilistic data structure that contains information to identify a probable location of the data item. The computing device transmits the at least one probabilistic data structure to one or more client computing devices, wherein the at least one probabilistic data structure is usable by the one or more client computing devices to determine the probable location of the data item.

Claims

1. A method comprising:

identifying, by a processing device of server computing device, a first possible location of a data item in a distributed database, wherein the first possible location of the data item is on a second server in the distributed database;

generating, by the processing device, a first probabilistic data structure that comprises information to identify the first possible location of the data item in the distributed database;

providing the first probabilistic data structure to a client computing device before the client computing device sends a request for the data item, wherein the client computing device is not involved with an operation to generate the first probabilistic data structure;

receiving, by the processing device, a query for the data item in response to the client computing device failing to locate the data item in view of the first probabilistic data structure;

determining a second possible location of the data item by querying a name server comprising an index to identify locations of data items stored in the distributed database;

generating a second probabilistic data structure to identify the second possible location of the data item; and

providing the second probabilistic data structure to the client computing device.

2. The method of claim 1, wherein the first probabilistic data structure is to identify whether there is a high probability that the data item is stored at the first possible location within the distributed database.

3. The method of claim 1, further comprising:

notifying the client computing device of the second possible location for the data item.

4. The method of claim 1, further comprising:

determining that a threshold number of changes have been made to the distributed database; and

generating a third probabilistic data structure to incorporate the changes.

5. The method of claim 1, wherein the data item comprises at least one of a database table, a database record, a database column or a database field, and wherein the first probabilistic data structure is usable by one or more client computing devices to determine the first possible location of the data item in the distributed database.

6. A method comprising:

receiving, by a processing device of a client computing device, a probabilistic data structure to probabilistically identify a first possible location of a data item in a distributed database, wherein the client computing device is not involved with an operation to generate the probabilistic data structure;

receiving, by the processing device, a query for the data item;

using, by the processing device, the probabilistic data structure to identify the first possible location of the data item in the distributed database, wherein the first possible location of the data item is on a second server in the distributed database;

attempting to access, in view of the probabilistic data structure, the data item from the first possible location at the second server without querying a name server;

receiving a response, via the second server, that the data item is not present at the second server;

querying the name server for an exact location of the data item, wherein the name server comprises an index to identify locations of data items stored in the distributed database;

receiving a response that comprises the exact location of the data item; and

accessing the data item at the exact location.

7. The method of claim 6, further comprising:

periodically receiving a new probabilistic data structure to probabilistically identify at least one of a new location of an existing data item or a location of a new data item.

8. The method of claim 6, wherein the probabilistic data structure identifies, for the data item, a plurality of possible locations in the distributed database for the data item.

9. The method of claim 6, wherein the data item comprises at least one of a database table, database record, database column or database field.

10. A non-transitory computer readable storage medium having instructions that, when executed by a processing device, cause the processing device to perform operations comprising:

identify, by the processing device, a first possible location of a data item in a distributed database;

generate, by the processing device, a first probabilistic data structure that comprises information to identify the first possible location of the data item in the distributed database, wherein the first possible location of the data item is on a second server in the distributed database;

provide the first probabilistic data structure to a client computing device, wherein the client computing device is not involved with an operation to generate the probabilistic data structure;

receive, by the processing device, a query for the data item in response to the client computing device failing to locate the data item in view of the first probabilistic data structure;

determine a second possible location of the data item by querying a name server comprising an index to identify locations of data items stored in the distributed database;

generate a second probabilistic data structure to identify the second possible location of the data item; and

provide the second probabilistic data structure to the client computing device.

11. The non-transitory computer readable storage medium of claim 10, the operations further comprising:

wherein the first probabilistic data structure is to identify whether there is a high probability that the data item is stored at the first possible location within the distributed database.

12. The non-transitory computer readable storage medium of claim 10, the operations further comprising:

notify the client computing device of the second possible location for the data item.

13. The non-transitory computer readable storage medium of claim 10, the operations further comprising:

determine that a threshold number of changes have been made to the distributed database; and

generate a third probabilistic data structure to incorporate the changes.

14. The non-transitory computer readable storage medium of claim 12, wherein the data item comprises at least one of a database table, a database record, a database column or a database field, and wherein the first probabilistic data structure is usable by the client computing device to determine the locations of a plurality of data items in the distributed database.

15. A non-transitory computer readable storage medium having instructions that, when executed by a processing device of a client device, cause the processing device to perform operations comprising:

receive, by the processing device, a probabilistic data structure to probabilistically identify a plurality of possible locations of a data item in a distributed database, wherein the client computing device is not involved with an operation to generate the probabilistic data structure;

receive a query for the data item;

use, by the processing device, the probabilistic data structure to identify a first possible location of the data item in the distributed database, wherein the first possible location of the data item is on a second server in the distributed database;

access, in view of the probabilistic data structure, the second server for the data item without querying a name server;

receive a response, via the second server, that the data item is not present at the second server;

query, by the processing device, the name server for an exact location of the data item, wherein the name server comprises an index to identify locations of data items stored in the distributed database and the exact location is on a third server in the distributed database; and

accessing the data item at the third server.

16. The non-transitory computer readable storage medium of claim 15, wherein the data item comprises at least one of a database table, database record, database column or database field.

17. A system comprising:

a server computing device comprising a memory and a processing device coupled to the memory, wherein the processing device is to;

identify a first possible location of a data item in a distributed database;

generate a probabilistic data structure that comprises information to identify the first possible location of the data item in the distributed database, wherein the first possible location of the data item is on a second server in the distributed database; and

provide the probabilistic data structure to a client computing before the client computing device sends a request for the data item, wherein the client computing device is not involved with an operation to generate the probabilistic data structure

receive a query for the data item in response to the client computing device failing to locate the data item in view of the probabilistic data structure;

determine an exact location of the data item by querying a name server comprising an index to identify locations of data items stored in the distributed database; and

provide the exact location of the data item to the client computing device.

18. The system of claim 17, further comprising:

a client computing device, networked to the server computing device, the client computing device comprising an additional processing device to;

receive the probabilistic data structure;

use the probabilistic data structure to identify the first possible location of the data item in the distributed database; and

access, in view of the probabilistic data structure, the data item from the first possible location without querying the server computing device.