SCALABLE LOOKUP SERVICE FOR DISTRIBUTED DATABASE

• US 20100312749A1
• Filed: 06/04/2009
• Published: 12/09/2010
• Est. Priority Date: 06/04/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Leshinsky, Yan Valerie, Murphy, Elissa E.S., Brahmadesam, Murali
• Application Number:
  US12/478,039
• Publication Number:
  US 20100312749A1
• Time in Patent Office: Days
• US Class Current: 707/609
• 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

An embodiment of the invention is directed toward locating a file chunk in a distributed database. A hash partition containing a hash of a location of the file chunk is determined. A node hosting the hash partition is determined. A list of database partitions containing the file chunk is requested from the node. A list of database partitions is received.

Claims

1. One or more computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of locating a file chunk in a distributed database, the method comprising:

determining a hash partition containing a hash of a location of the file chunk;

determining a node hosting the hash partition;

requesting from the node a list of one or more database partitions containing the file chunk; and

receiving the list of one or more database partitions.

2. The media of claim 1, wherein determining a hash partition includes determining a value of a hash function for the file chunk and determining the hash partition containing the value.

3. The media of claim 2, wherein determining a node includes utilizing a chunk hash lookup service to map the hash partition containing the value to a particular node.

4. The media of claim 3, wherein the chunk hash lookup service maps the hash partition containing the value to two or more nodes.

5. The media of claim 4, wherein one of the two or more nodes is chosen as the node hosting the hash partition based on load information.

6. The media of claim 1, wherein the list of one or more database partitions is determined by applying one or more filters to a hash related to the file chunk.

7. The media of claim 6, wherein each of the one or more filters is related to a particular database partition.

8. The media of claim 7, wherein the one or more filters are Bloom filters.

9. The media of claim 1, wherein the one or more database partitions in the list contain the file chunk with a given probability.

10. The media of claim 1, further comprising searching each of the one or more database partitions for the file chunk.

11. One or more computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of locating a file chunk in a distributed database, the method comprising:

receiving a request for a list of one or more database partitions containing the file chunk;

applying each of a number of filters to a hash related to the file chunk, each of said number of filters being related to a particular database partition;

based on the application of the number of filters, determining a list of one or more database partitions containing the file chunk; and

replying to the request with a message containing the list.

12. The media of claim 11, wherein the request includes the hash related to the file chunk.

13. The media of claim 11, wherein applying each of a number of filters includes applying one or more subsets of the filters in parallel.

14. The media of claim 11, wherein the number of filters are Bloom filters.

15. The media of claim 11, wherein the one or more database partitions in the list contain the file chunk with a given probability.

16. The media of claim 11, further comprising recalculating each of the number of filters.

17. The media of claim 16, wherein the recalculating is a background process.

18. One or more computer-readable media having computer-executable instructions embodied thereon that, when executed, cause a computing device to perform a method of locating a file chunk in a distributed database, the method comprising:

receiving a request for a list of one or more database partitions containing the file chunk, the request including a hash related to the file chunk;

applying each of a number of Bloom filters to a hash related to the file chunk, each of said number of Bloom filters being related to a particular database partition;

based on the application of the number of Bloom filters, determining a list of one or more database partitions containing the file chunk with a given probability; and

replying to the request with a message containing the list.

19. The media of claim 18, wherein applying each of a number of Bloom filters includes applying one or more subsets of the Bloom filters in parallel.

20. The media of claim 18, wherein each of the one or more database partitions are located at different nodes.