Replica/cache locator, an overlay network and a method to locate replication tables and caches therein
A replica/cache locator, a method to locate replication tables and caches in an overlay network having multiple nodes and an overlay network. In one embodiment, the method includes: (1) determining a network distance between a first node of the multiple nodes in the overlay network and each of the remaining multiple nodes, (2) calculating m clusters of the multiple nodes based on the network distances and (3) designating at least a single node from the m clusters to include a replication table of the first node.
1. A replica/cache locator, comprising:
a coordinate determiner configured to calculate network virtual coordinates between a first node in an overlay network and each remaining node in said overlay network;
a node clusterer coupled to said coordinate determiner and configured to calculate m clusters of nodes in said overlay network based on said network virtual coordinates; and
a replica/cache manager coupled to said node clusterer and configured to designate a node from at least one of said m clusters to include a replication table of said first node and more than one node in each of said m clusters to include a cache of said first node, said nodes designated by said replica/cache manager based on locations of said nodes in said overlay network.
2. The replica/cache locator as recited in claim 1 wherein said coordinate determiner is configured to update said network virtual coordinates by forwarding a query to a randomly selected replica node, cache node or said first node.
3. The replica/cache locator as recited in claim 1 wherein said coordinate determiner is configured to calculate said network virtual coordinates based on multiple queries.
4. The replica/cache locator as recited in claim 1 wherein said coordinate determiner is configured to calculate said network virtual coordinates between a first node in an overlay network and each remaining node in said overlay network by piggybacking on queries exchanged between said first node and said each remaining node.
5. The replica/cache locator as recited in claim 1 wherein said replica/cache manager is configured to designate multiple nodes from said m clusters to include a replication table of said first node.
6. The replica/cache locator as recited in claim 2 wherein said replica/cache manager is further configured to designate more than one node in each of said m clusters to include a cache of said first node based on reducing latency associated with responding to said queries.
7. The replica/cache locator as recited in claim 6 wherein said replica/cache manager is further configured to use different goals for designating said node for said replication table of said first node and said more than one nodes for said cache of said first node.
8. The replica/cache locator as recited in claim 1 wherein said replica/cache manager is configured to designate at most a single node in each of said m clusters to include said replication table.
9. A computer implemented method to locate replication tables in an overlay network having multiple nodes, comprising:
determining network virtual coordinates between a first node of said multiple nodes in said overlay network and each of remaining nodes of said multiple nodes;
calculating m clusters of said multiple nodes based on said network virtual coordinates; and
designating a node from at least one of said m clusters to include a replication table of said first node and more than one node in each of said m clusters to include a cache of said first node, wherein each node of said overlay network is configured to know the location of said designated nodes.
10. The method as recited in claim 9 wherein said designating includes designating no more than a single node in each of said m clusters to include said replication table.
11. The method as recited in claim 9 wherein said replication table includes a copy of a content table of said first node and said content table is a sorted partition of domain data of said overlay network in a key-value pair form.
12. The method as recited in claim 9 wherein said m clusters have an unequal amount of nodes.
13. The method as recited in claim 9 wherein each of said multiple nodes are coupled via said virtual coordinate system.
14. The method as recited in claim 9 further comprising designating at most a single node from any one of said m clusters to include said replication table of said first node.
15. The method as recited in claim 9 wherein at least four nodes are designated to include said replication table.
16. The method as recited in claim 9 wherein said designating is based on reliability of components of said network.
17. The method as recited in claim 9 wherein said designating is based on availability requirement of said network.
18. An overlay network, comprising:
multiple nodes coupled in a ring, wherein at least a first node of said multiple nodes includes:
a content table having a sorted partition of domain data in a key-value pair form;
a flat routing table configured to associate an IP address of each of said multiple nodes with a corresponding range of keys; and
wherein each node of said multiples nodes includes a replica/cache locator, including:
a coordinate determiner configured to determine network virtual coordinates between said first node and each remaining node of said multiple nodes;
a node clusterer coupled to said coordinate determiner and configured to calculate m clusters of said multiple nodes based on said network virtual coordinates; and
a replica/cache manager coupled to said node clusterer and configured to designate a node from at least one of said m clusters to include a replication table of said first node and more than one node in each of said m clusters to include a cache of said first node.
19. The overlay network as recited in claim 18 , wherein each node of said multiple nodes is configured to send said network virtual coordinates to a new node in said overlay network, wherein said new node in said overlay network is configured to transform said network virtual coordinates to be centered at said new node based on queries associated with said new node.
20. The overlay network as recited in claim 18 wherein said node clusterer is further configured to calculate said m clusters based on dynamic information associated with some of said multiple nodes.
21. The overlay network as recited in claim 20 wherein one of said m clusters includes more nodes than at least another of said m clusters, said one including said some of said multiple nodes with said dynamic information.
22. A computer implemented method to locate caches in an overlay network having multiple nodes, comprising:
determining network virtual coordinates between a first node of said multiple nodes in said overlay network and each of said remaining nodes of said multiple nodes;
calculating, by employing a processor, m clusters of said multiple nodes based on said network virtual coordinates; and
designating a node from at least one of said m clusters to include a replication table of said first node and more than one node in each of said m clusters to include a cache of said first node based on reducing latency associated with responding to said queries.
23. The method as recited in claim 22 , wherein said designating includes designating a number of nodes for a replication table of said first node, said number based on a network availability requirement and independent of a number of clusters in said m clusters.
24. The method as recited in claim 23 , wherein said designating includes designating at most a single node in each of said m clusters to include said replication table.