Front end bloom filters in distributed databases

• US 10,698,898 B2
• Filed: 01/24/2017
• Issued: 06/30/2020
• Est. Priority Date: 01/24/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Khandelwal, Sunil
• Primary Examiner(s): Alam, Shahid A
• Application Number:
  US15/414,325
• Publication Number:
  US 20180210959A1
• Time in Patent Office: 1,253 Days
• Field of Search: 707754
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Systems, methods, apparatuses, and software for distributed database systems in computing environments are provided herein. In one example, a method of operating a database system is provided that includes providing an interface to a database service that hosts at least a data store across a plurality of storage elements distributed with respect to each other, and receiving, in the interface, lookup requests to determine if first keys indicated by the lookup requests are present in the data store. The method includes processing the lookup requests with at least a bloom filter initialized with second keys associated with the data store to determine presence statuses of the first keys with respect to the data store, and indicating the presence statuses responsive to the lookup requests.

Claims

1. A computing apparatus comprising:

one or more computer readable storage media;

a processing system operatively coupled with the one or more computer readable storage media; and

program instructions stored on the one or more computer readable storage media, that when executed by the processing system, direct the processing system to at least;

provide an interface to a database service that hosts at least a data store spanning a plurality of storage elements distributed with respect to each other;

receive, in the interface, lookup requests issued by requesting entities to determine if target keys indicated by the lookup requests are presently stored by the data store;

process the lookup requests with at least a first bloom filter to determine presence statuses comprising absence or potential presence of the target keys in the data store, wherein the first bloom filter is initialized by at least performing a hashing process on data stored into the data store;

based at least on determining the target keys are absent from the data store, indicate to the requesting entities the absence as the presence statuses responsive to the lookup requests; and

based at least on determining the target keys are potentially present in the data store, process the target keys with one or more second bloom filters corresponding individually to the plurality of storage elements to determine which one or more storage elements among the plurality of storage elements potentially store the target keys, issue one or more queries to the one or more storage elements to determine confirmed presence statuses of the target keys, and indicate the confirmed presences statuses to the requesting entities.

2. The computing apparatus of claim 1, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

based at least on determining the one or more storage elements that potentially store the target keys, further perform a query process on the one or more storage elements to determine the confirmed presence statuses of the target keys being stored in the one or more storage elements, and indicate the confirmed presence statuses as the presence statuses responsive to the lookup requests.

3. The computing apparatus of claim 1, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

process the lookup requests with the first bloom filter without issuing key lookup requests to the plurality of storage elements.

4. The computing apparatus of claim 1, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

initialize at least the first bloom filter with the data responsive to data write events into the data store.

5. The computing apparatus of claim 1, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

initialize at least the first bloom filter with the data responsive to a startup event of the data store across the plurality of storage elements.

6. The computing apparatus of claim 5, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

initialize at least the first bloom filter using an archived version of the first bloom filter placed into a cached configuration with respect to the interface to the database service.

7. The computing apparatus of claim 6, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

further initialize the cached configuration of the first bloom filter responsive to data write events into the data store to establish a delta to the archived version of the bloom filter.

8. The computing apparatus of claim 1, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

select the first bloom filter among a set of bloom filters each designated to service ones of the lookup requests for an associated subdivision of the data store, the first bloom filter selected from among the set of bloom filters by at least processing properties of the lookup requests to determine subdivisions associated with the lookup requests.

9. A method of operating a distributed database system, the method comprising:

providing an interface to a database service that hosts at least a data store spanning a plurality of storage elements distributed with respect to each other;

receiving, in the interface, lookup requests issued by requesting entities to determine if target keys indicated by the lookup requests are presently stored by the data store;

processing the lookup requests with at least a first bloom filter to determine presence statuses comprising absence or potential presence of the target keys in the data store, wherein the bloom filter is initialized by at least performing a hashing process on data stored into the data store;

based at least on determining the target keys are absent from the data store, indicating to the requesting entities the absence as the presence statuses responsive to the lookup requests; and

based at least on determining the target keys are potentially present in the data store, processing the target keys with one or more second bloom filters corresponding individually to the plurality of storage elements to determine which one or more storage elements among the plurality of storage elements potentially store the target keys, issuing one or more queries to the one or more storage elements to determine confirmed presence statuses of the target keys, and indicating the confirmed presences statuses to the requesting entities.

10. The method of claim 9, further comprising:

based at least on determining the one or more storage elements, further performing a query process on the one or more storage elements to determine the confirmed presence statuses of the ones of the target keys in the one or more storage elements, and indicating the confirmed presence statuses as the presence statuses responsive to associated ones of the lookup requests.

11. The method of claim 9, further comprising:

processing the lookup requests with the first bloom filter without issuing lookup requests to the plurality of storage elements.

12. The method of claim 9, further comprising:

initializing the first bloom filter with the second keys responsive to data write events into the data store for data associated with the second keys.

13. The method of claim 9, further comprising:

initializing the first bloom filter responsive to a startup event of the data store across the plurality of storage elements.

14. The method of claim 13, further comprising:

initializing the first bloom filter using an archived version of the first bloom filter placed into a cached configuration with respect to the interface to the database service.

15. The method of claim 14, further comprising:

initializing further data into the cached configuration of the first bloom filter responsive to data write events into the data store for data associated with the further data, the further data initialized into the cached configuration of the first bloom filter to establish a delta to the archived version of the first bloom filter.

16. The method of claim 9, further comprising:

selecting the first bloom filter among a set of bloom filters each designated to service ones of the lookup requests for an associated subdivision of the data store, the first bloom filter selected from among the set of bloom filters by at least processing properties of the lookup requests to determine subdivisions associated with the lookup requests.

17. A computing apparatus comprising:

one or more computer readable storage media;

a processing system operatively coupled with the one or more computer readable storage media; and

program instructions stored on the one or more computer readable storage media, that when executed by the processing system, direct the processing system to at least;

provide an interface to a database service that distributes one or more databases over a plurality of data centers, the interface configured to receive requests issued by requesting entities for key lookups among the one or more databases;

responsive to the requests for key lookups, employ at least one primary bloom filter cached locally to the interface to determine if data keys indicated by the requests for key lookups are potentially present in or absent from the one or more databases distributed over the plurality of data centers, wherein the at least one primary bloom filter is initialized using current data keys corresponding to data presently stored in the one or more databases;

based at least on determining the data keys are absent from the one or more databases, indicate to the requesting entities presence statuses responsive to the requests for key lookups indicating absences of the data keys with respect to the one or more databases; and

based at least on determining the data keys are potentially present in the one or more databases, process the data keys with one or more secondary bloom filters corresponding individually to the plurality of data centers to determine which one or more data centers among the plurality of data centers potentially store the data keys, issue one or more queries to the one or more data centers to determine confirmed presence statuses of the data keys, and indicate the confirmed presences statuses to the requesting entities.

18. The computing apparatus of claim 17, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

based at least on determining the data keys are potentially present in the one or more data centers, further perform a query process on the one or more data centers to determine the confirmed presence states of the data keys in the one or more data centers, and indicate the confirmed presence states as the presence statuses responsive to associated ones of the requests for key lookups.

19. The computing apparatus of claim 17, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

initialize the at least one primary bloom filter with the current data keys responsive to a startup event of the one or more databases across the plurality of data centers;

initialize the current data keys into the at least one primary bloom filter using an archived version of the at least one primary bloom filter placed into a cached configuration with respect to the interface to the database service; and

initialize further keys into the cached configuration of the at least one primary bloom filter responsive to data write events into the one or more databases for data associated with the further keys, the further keys initialized into the cached configuration of the at least one primary bloom filter to establish a delta to the archived version of the at least one primary bloom filter.

20. The computing apparatus of claim 17, comprising further program instructions, when executed by the processing system, direct the processing system to at least:

select the at least one primary bloom filter among a set of bloom filters each designated to service ones of the requests for the key lookups for an associated subdivision of the one or more databases, the at least one primary bloom filter selected from among the set of bloom filters by at least processing properties of the requests for the key lookups to determine subdivisions associated with the requests for the key lookups.