Data overlay, self-organized metadata overlay, and associated methods

• US 7,313,565 B2
• Filed: 02/19/2004
• Issued: 12/25/2007
• Est. Priority Date: 02/19/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zheng, Shi, Shu-Ming
• Primary Examiner(s): Lu; Kuen S.
• Application Number:
  US10/782,527
• Publication Number:
  US 20050187946A1
• Time in Patent Office: 1,405 Days
• Field of Search: 707/10, 707/100, 707/3, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A data overlay is described which is built as a data structure on top of a logical space defined by a distributed hash table (DHT) in a peer-to-peer (P2P) network environment. The data overlay can assume a topology of a tree having a plurality of tree nodes. Each of the tree nodes has a zone allocated to it that maps to a corresponding zone associated with a DHT node in the logical space of the DHT. Procedures are described for “growing” this tree structure, such that the tree structure is self-organizing and self-healing on the same scale as the underlying DHT. Other procedures are described for using the tree structure to gather information from the DHT nodes and to disseminate information to the DHT nodes.

Claims

1. A method for building a data overlay, comprising:

providing a distributed hash table (DHT) that governs the insertion and retrieval of objects into and from a peer-to-peer system, wherein the distributed hash table includes a logical space including a plurality of DHT nodes having an associated plurality of DHT zones;

building the data overlay as a data structure on top of the logical space of the distributed hash table by associating objects in the data structure with the DHT nodes, and by establishing links between the objects in the data structure;

wherein each link includes a first field that provides a hardwired pointer that points from a first object to a second object, and a second field that provides a soft-state pointer that points from the first object to a DHT node which hosts the second object;

wherein the building of the data overlay makes use of a first primitive for setting a reference that establishes a pointer to an object in the distributed hash table, a second primitive for returning an object referenced by a pointer, and a third primitive for deleting an object referenced by a pointer; and

wherein the data structure facilitates dissemination of information to the DHT nodes and gathering of information from the DHT nodes.

2. The method according to claim 1, wherein the data overlay has a topology of a tree, the tree having a plurality of tree nodes associated with respective DHT nodes, wherein each tree node has a respective tree node zone associated therewith which corresponds to a part of the logical space of the distributed hash table.

3. The method according to claim 2, wherein each tree node in the data overlay includes a key member which identifies a key associated with its respective tree node zone.

4. The method according to claim 3, wherein the key has a value that is a function of coordinates that identify the center of the respective tree node zone.

5. The method according to claim 2, wherein each tree node in the data overlay includes an operation member which defines an operation that is to be performed on data that is passed through the tree node.

6. The method according to claim 2, wherein each tree node in the data overlay includes a report member which defines a report type that is to be generated using the tree node.

7. The method according to claim 2, wherein the building of the data overlay comprises:

establishing a root tree node, the root tree node having a tree node zone corresponding to an entire span of the logical space of the distributed hash table.

8. The method according to claim 2, wherein the building of the data overlay comprises:

examining a tree node zone associated with a particular tree node to determine whether the tree node zone is smaller than or equal to a DHT zone associated with the particular tree node'"'"'s hosting DHT node; and

adding a child node associated with the particular tree node if the examining determines that the tree node zone is not smaller than or equal to the associated DHT zone.

9. The method according to claim 8, further comprising repeating the examining and the adding for each tree node in the tree.

10. A computer readable store including machine readable instructions for implementing the building of objects in the data overlay according to the method of claim 8.

11. A computer readable store having stored thereon a data overlay produced according to the method of claim 1.

12. A computer readable store having stored thereon a data overlay having the topology of a tree produced according to the method of claim 2.

13. A computer readable store having stored thereon a data structure, comprising:

a logical space of a distributed hash table (DHT), including a plurality of DHT nodes having a plurality of associated DHT zones, wherein the distributed hash table governs the insertion and retrieval of objects into and from a peer-to-peer system;

a data overlay implemented as a data structure on top of the logical space of the distributed hash table logical space by associating objects in the data structure with the DHT nodes, and by establishing links between the objects in the data structure;

wherein each link includes a first field that provides a hardwired pointer that points from a first object to a second object, and a second field that provides a soft-state pointer that points from the first object to a DHT node which hosts the second object;

wherein building of the data overlay makes use of a first primitive for setting a reference that establishes a pointer to an object in the distributed hash table, a second primitive for returning an object referenced by a pointer, and a third primitive for deleting an object referenced by a pointer; and

wherein the data structure facilitates dissemination of information to the DHT nodes and gathering of information from the DHT nodes.

14. The distributed computer readable store of claim 13, wherein the data overlay has a topology of a tree, the tree having a plurality of tree nodes associated with respective DHT nodes, wherein each tree node has a respective tree node zone associated therewith which corresponds to a part of the logical space of the distributed hash table.

15. A method for passing data through a data overlay, comprising:

providing a distributed hash table (DHT) that governs the insertion and retrieval of objects into and from a peer-to-peer system, wherein the distributed hash table includes a logical space including a plurality of DHT nodes having a plurality of associated DHT zones;

building a data overlay as a data structure on top of the logical space of the distributed hash table by associating objects in the data structure with the DHT nodes, and by establishing links between the objects in the data structure;

wherein each link includes a first field that provides a hardwired pointer that points from a first object to a second object, and a second field that provides a soft-state pointer that points from the first object to a DHT node which hosts the second object;

wherein the building of the data overlay makes use of a first primitive for setting a reference that establishes a pointer to an object in the distributed hash table, a second primitive for returning an object referenced by a pointer, and a third primitive for deleting an object referenced by a pointer; and

wherein the data overlay defines a plurality of interconnected nodes, and wherein the data structure facilitates dissemination of information to the DHT nodes and gathering of information from the DHT nodes; and

routing data through the data overlay by passing the data through its interconnected nodes.

16. The method according to claim 15, wherein the data overlay has a topology of a tree, the tree having a plurality of tree nodes associated with respective DHT nodes, wherein each tree node has a respective tree node zone associated therewith which corresponds to a part of the logical space of the distributed hash table.

17. The method according to claim 16, wherein the routing of data through the data overlay includes gathering data from DHT nodes and passing the data up through the tree nodes to a root node of the tree.

18. The method according to claim 16, wherein the routing of data through the data overlay includes disseminating data from a root node of the tree, through the tree nodes, to the DHT nodes.

19. The method according to claim 16, wherein each tree node includes an operation member which defines an operation that is to be performed on data that is passed through the tree node.

20. A computer readable store including machine readable instructions for implementing the routing of data through the data overlay according to the method of claim 15.

21. A peer-to-peer system including a plurality of machines interacting in peer-to-peer fashion, comprising:

a logical space of a distributed hash table (DHT), including a plurality of DHT nodes having a plurality of associated DHT zones, wherein the distributed hash table governs the insertion and retrieval of objects into and from the peer-to-peer system; and

a data overlay implemented as a data structure on top of the logical space of the distributed hash table by associating objects in the data structure with the DHT nodes, and by establishing links between the objects in the data structure

wherein each link includes a first field that provides a hardwired pointer that points from a first object to a second object, and a second field that provides a soft-state pointer that points from the first object to a DHT node which hosts the second object;

wherein building of the data overlay makes use of a first primitive for setting a reference that establishes a pointer to an object in the distributed hash table, a second primitive for returning an object referenced by a pointer, and a third primitive for deleting an object referenced by a pointer;

wherein the data overlay uses services provided by the distributed hash table in routing from one object to another in the data structure, and wherein the data structure facilitates dissemination of information to the DHT nodes and gathering of information from the DHT nodes; and

wherein the logical space of the distributed hash table and the data overlay are implemented in distributed fashion in respective stores of the plurality of machines in the peer-to-peer system.

22. The system according to claim 21, wherein the data overlay has a topology of a tree, the tree having a plurality of tree nodes associated with respective DHT nodes, wherein each tree node has a respective tree node zone associated therewith which corresponds to a part of the logical space of the distributed hash table.

23. The system according to claim 22, further including routing logic configured to route data through the data overlay by passing the data through the tree nodes.

24. The system according to claim 23, wherein the routing logic is configured to route the data through the data overlay by gathering data from DHT nodes and passing the data up through the tree nodes to a root node of the tree.

25. The system according to claim 23, wherein the routing logic is configured to route data through the data overlay by disseminating data from a root node of the tree, through the tree nodes, to the DHT nodes.