Strong routing consistency protocol in structured peer-to-peer overlays

• US 20070204061A1
• Filed: 02/24/2006
• Published: 08/30/2007
• Est. Priority Date: 02/24/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Wei, Liu, Xuezheng
• Granted Patent: US 7,673,069 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

A structured peer-to-peer overlay performs a key-based routing (KBR) that achieves a strong routing consistency guarantee as well as reasonable scalability. The key space of the structured overlay is partitioned into zones, each separately managed by a group membership service that provides total ordering of membership query and change actions. The strongly consistent KBR has two phases: first, a key value is routed to a contact node in its zone via a weakly consistent KBR protocol; and then performing a lookup of the destination node for the key value by the contact node using the group membership service of the zone. By appropriately tuning the zone size, the strongly consistent KBR balances the trade-off between scalability and routing liveness. The KBR can maintain this balance by merging and splitting zones to account for system chum and scale changes.

Claims

1. A method of enforcing routing consistency in structured peer-to-peer overlays, the method comprising:

partitioning a key space of a structured peer-to-peer overlay into a plurality of zones, wherein at least one zone encompasses keys of plural nodes;

providing a group membership service per zone to manage nodes of their respective zones;

performing key-based routing within the structured peer-to-peer overlay by;

performing routing of a key value via a weakly consistent key-based routing to a node in the zone to which the key value belongs; and

querying the group membership service of the zone to determine a node to which the key value belongs.

2. The method of claim 1 wherein the weakly consistent key-based routing provides a property that routing the key value eventually routes to a node within the zone to which the key value belongs, but not necessarily always the same node.

3. The method of claim 1 wherein the group membership service of a zone provides total ordering of membership query and membership change actions.

4. The method of claim 3 wherein the group membership service further satisfies the properties of causality consistency, agreement and eventual convergence.

5. The method of claim 4 wherein the group membership service is implemented using a consensus procedure to totally order the membership query and member change actions, and uses an eventually perfect failure detector procedure to ensure convergence of its membership view to an actual set of nodes currently existing within the zone.

6. The method of claim 4 wherein the group membership service is implemented using a causal atomic broadcast primitives procedure to totally order the membership query and member change actions, and uses an eventually perfect failure detector procedure to ensure convergence of its membership view to an actual set of nodes currently existing within the zone.

7. The method of claim 1 further comprising determining a zone size in which to partition the key space, such that zones each contain a desired number of nodes greater than one that appropriately balances between scalability and consistency for an application implemented by the structured peer-to-peer overlay.

8. The method of claim 1 further comprising:

when a zone contains in excess of an overloaded number of nodes, re-partitioning the key space into a larger number of zones; and

when a zone contains less than an underloaded number of nodes, re-partitioning the key space into fewer zones.

9. The method of claim 8 wherein re-partitioning into a larger number of zones comprises splitting an overloaded zone in halves, and re-partitioning into fewer zones comprises merging an underloaded zone with a neighboring zone.

10. The method of claim 1 further comprising:

detecting when a zone is dead; and

reactivating the zone.

11. The method of claim 10 wherein said detecting when a zone is dead comprises detecting that a majority of nodes that are members of the zone according to the group membership service of the zone are no longer live.

12. A structured peer-to-peer overlay system with strongly consistent key-based routing, the system comprising:

a plurality of nodes, each node having a node ID within a key space and owning a range of key values, the key space being partitioned into zones, the nodes implementing a weakly consistent key-based routing protocol operating to route a query with a key value to an owning node for the key value;

a plurality of group membership services each separately managing a group of nodes whose node ID is contained in one of a plurality of zones into which the key space is partitioned, each group membership service providing an interface for receiving group membership query and membership change event actions from the nodes with total ordering of the membership query and change event actions via an incrementing membership view version number;

wherein the system provides strongly consistent key-based routing of a key value by first performing routing using the weakly consistent key-based routing to a contact node within the zone containing the key value, and the contact node then querying the group membership service of the zone to determine with a strong consistency guarantee to which node in the zone the key value belongs.

13. The structured peer-to-peer overlay system of claim 12 wherein the group membership services operate to reduce key version number changes by providing a stable select node action that returns a node for a key with a key version number that updates independently of the zone version number maintained by the group membership service, the group membership service further maintaining a key ownership data structure to record the key version numbers.

14. The structured peer-to-peer overlay system of claim 12 wherein the weakly consistent key-based routing protocol conforms to a property that routing the key value eventually routes to a node within the zone to which the key value belongs, but not necessarily always the same node.

15. The structured peer-to-peer overlay system of claim 12 wherein the group membership services satisfy the properties of causality consistency, agreement and eventual convergence.

16. The structured peer-to-peer overlay system of claim 12 wherein the group membership services further operate on a consensus basis to split zones whose node membership is overloaded, and to merge zones whose node membership is underloaded.

17. The structured peer-to-peer overlay system of claim 12 wherein the group membership services further operate on a consensus basis to remove and reactivate a zone that becomes dead.

18. One or more computer-readable media containing instructions which, when executed by a computer, cause the computer to perform a method for strongly consistent key-based routing in a structured peer-to-peer overlay, the structured peer-to-peer overlay having a key-space partitioned into zones separately managed by group membership services, the method comprising:

upon a node joining the structured peer-to-peer overlay, issuing a join action to a group membership service for a zone to which a node ID of the node belongs;

upon detecting failure of another node, issuing a remove action to a group membership service to which the other node belongs;

when routing a key value;

performing a lookup of a contact node in a zone for the key value using a weakly-consistent key-based routing protocol among nodes of the structured peer-to-peer overlay;

issuing a strongly consistent lookup request to the contact node;

upon receiving a strongly consistent lookup request from another requesting node, querying the group membership service of the zone to determine an owning node for the key value, and identifying the owning node to the other requesting node;

failing to route the key value if the contact node in the zone cannot be located via the weakly-consistent key-based routing protocol or the group membership service query fails; and

routing the key value to the owning node identified by the contact node.

19. The computer-readable media of claim 18 wherein the group membership service totally orders membership query and change actions by version numbers, and the routing further returns a version number that satisfies causality consistency, strong consistency and eventual consistency properties of strongly consistent key-based routing.

20. The computer-readable media of claim 18 wherein a node joining the structured peer-to-peer overlay first performs a lookup of a contact node in a zone for its node ID using the weakly-consistent key-based routing protocol to locate the group membership service for issuing the join action.