System and Method for Using Bloom Filters to Determine Data Locations in Distributed Data Stores

• US 20130132408A1
• Filed: 11/23/2011
• Published: 05/23/2013
• 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
• Granted Patent: US 8,990,243 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: G06F 16/2255 Hash tables

Abstract

A server computing device identifies locations of a plurality of data items in a distributed data store. The server computing device generates at least one bloom filter that contains information to identify probable locations of the plurality of data items. The server computing device transmits the at least one bloom filter to one or more client computing devices, wherein the at least one bloom filter is usable by the one or more client computing devices to determine the probable locations of the data items.

Claims

1. A method comprising:

identifying, by a server computing device, locations of a plurality of data items in a distributed database;

generating, by the server computing device, at least one bloom filter that contains information to identify locations of the plurality of data items in the distributed database; and

providing the at least one bloom filter to one or more client computing devices.

2. The method of claim 1, further comprising:

generating a plurality of bloom filters, wherein each bloom filter of the plurality of bloom filters identifies whether there is a high probability that the plurality of data items are stored at a particular location.

3. The method of claim 1, further comprising:

receiving a query for a particular data item by the server computing device in response to a client computing device failing to locate the particular data item based on the at least one bloom filter;

determining a location of the particular data item;

notifying the client computing device of the location for the particular data item; and

generating a new bloom filter that identifies with high probability the location of the particular data item.

4. The method of claim 1, further comprising:

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

generating at least one new bloom filter that incorporates the changes.

5. The method of claim 1, wherein each of the data items comprises at least one of a database table, a database record, a database column or a database field, and wherein the at least one bloom filter is usable by the one or more client computing devices to determine the locations of the plurality of data items in the distributed database.

6. A method comprising:

receiving, by a client computing device, at least one bloom filter that probabilistically identifies locations of data items in a distributed database;

receiving a query for a particular data item;

using, by the client computing device, the bloom filter to identify a location of the data item in the distributed database; and

accessing the data item from the location without querying a name server.

7. The method of claim 6, further comprising:

receiving a response from the location that the particular data item is not present at the location;

querying the name server for a new location of the particular data item;

receiving a response that includes the new location for the particular data item; and

retrieving the particular data item from the new location.

8. The method of claim 7, further comprising:

receiving an updated bloom filter that probabilistically identifies the new location for the particular data item.

9. The method of claim 6, further comprising:

periodically receiving a new bloom filter that probabilistically identifies at least one of new locations of existing data items and locations of new data items.

10. The method of claim 6, wherein the at least one bloom filter identifies, for at least some data items, a plurality of locations in the distributed database for those data items.

11. The method of claim 6, wherein the data items comprise at least one of database tables, database records, database columns or database fields.

12. A computer readable storage medium having instructions that, when executed by a processing device, cause the processing device to perform a method comprising:

identifying, by the processing device, locations of a plurality of data items in a distributed database;

generating, by the processing device, at least one bloom filter that contains information to identify locations of the plurality of data items in the distributed database; and

providing the at least one bloom filter to one or more client computing devices.

13. The computer readable storage medium of claim 12, the method further comprising:

generating a plurality of bloom filters, wherein each bloom filter of the plurality of bloom filters identifies whether there is a high probability that the plurality of data items are stored at a particular location.

14. The computer readable storage medium of claim 12, the method further comprising:

receiving a query for a particular data item by the server computing device in response to a client computing device failing to locate the particular data item based on the at least one bloom filter;

determining a location of the particular data item;

notifying the client of the location for the particular data item; and

generating a new bloom filter that identifies with high probability the location of the particular data item.

15. The computer readable storage medium of claim 12, the method further comprising:

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

generating at least one new bloom filter that incorporates the changes.

16. The computer readable storage medium of claim 12, wherein each of the data items comprises at least one of a database table, a database record, a database column or a database field, and wherein the at least one bloom filter is usable by the one or more client computing devices to determine the locations of the plurality of data items in the distributed database.

17. A computer readable storage medium having instructions that, when executed by a processing device, cause the processing device to perform a method comprising:

receiving, by a client computing device, at least one bloom filter that probabilistically identifies locations of data items in a distributed database;

receiving a query for a particular data item;

using, by the client computing device, the bloom filter to identify a location of the data item in the distributed database; and

accessing the data item from the location without querying a name server.

18. The computer readable storage medium of claim 17, the method further comprising:

receiving a response from the location that the particular data item is not present at the location;

querying the name server for a new location of the particular data item;

receiving a response that includes the new location for the particular data item; and

retrieving the particular data item from the new location.

19. The computer readable storage medium of claim 17, wherein the at least one bloom filter identifies, for at least some data items, a plurality of locations in the distributed database for those data items, and wherein the data items comprise at least one of database tables, database records, database columns or database fields.

20. A system comprising:

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

identify locations of a plurality of data items in a distributed database;

generate at least one bloom filter that contains information to identify locations of the plurality of data items in the distributed database; and

provide the at least one bloom filter to one or more client computing devices.

21. The system of claim 20, further comprising:

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

receive the at least one bloom filter;

receive a query for a particular data item;

use the bloom filter to identify a location of the data item in the distributed database; and

access the data item from the location without querying the server computing device.

22. The system of claim 20, wherein the processing device is further configured to:

receive a query for a particular data item in response to a client computing device failing to locate the particular data item based on the at least one bloom filter;

determine a location of the particular data item;

notify the client computing device of the location for the particular data item; and

generate a new bloom filter that identifies with high probability the location of the particular data item.