Systems and methods for dynamic mapping for locality and balance

Patent metadata

Field	Value
Publication number	US-9934323-B2
Application number	US-201314043730-A
Country	US
Kind code	B2
Filing date	Oct 1, 2013
Priority date	Oct 1, 2013
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

To dynamically map nodes for locality and balance, computer implemented methods, systems, and computer readable media, in an embodiment, may compute histograms for nodes in a first partition. Histograms may be computed for nodes in a second partition. The second partition may be selected as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition. The first partition may be selected as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition. At least a portion of the set of nodes in the first partition may be mapped to the second partition and at least a portion of the set of nodes in the second partition may be mapped to the first partition based on load balancing.

First claim

What is claimed:

1. A computer implemented method comprising:
computing, with a computer system, a respective histogram for each node in a first partition, wherein the histogram for a node in the first partition indicates, for each partition in a set of partitions, a corresponding total weight of edges of the node that are connected to the partition;
computing, with the computer system, a respective histogram for each node in a second partition, wherein the histogram for a node in the second partition indicates, for each partition in the set of partitions, a corresponding total weight of edges of the node that are connected to the partition;
selecting, with the computer system, the second partition as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition and on a probability algorithm relating to a gain in edge locality, the probability algorithm being defined based on a total number of connected nodes within a partition and a total number of connected nodes within partitions that result in a gain;
selecting, with the computer system, the first partition as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition;
determining, by the computer system, that remapping (i) at least a portion of the set of nodes in the first partition to the second partition and (ii) at least a portion of the set of nodes in the second partition to the first partition results in both the first partition and the second partition satisfying a threshold load balance, wherein at least some of the nodes in the set correspond to users of the social networking system, and wherein the load for a partition is measured based at least in part on an amount of data transferred by users mapped to the partition; and
remapping, with the computer system, at least the portion of the set of nodes in the first partition to the second partition and at least the portion of the set of nodes in the second partition to the first partition.

2. The computer implemented method of claim 1 , further comprising:
computing, with the computer system, histograms for nodes in a third partition;
selecting, with the computer system, the third partition as a candidate partition for another set of nodes in the first partition based on the histograms for the nodes in the first partition;
selecting, with the computer system, the first partition as a candidate partition for a set of nodes in the third based on the histograms for the nodes in the third partition; and
remapping, with the computer system, at least a portion of the other set of nodes in the first partition to the third partition and at least a portion of the set of nodes in the third partition to the first partition based on load balancing.

3. The computer implemented method of claim 1 , further comprising:
sorting, with the computer system, the set of nodes in the first partition based on a gain in edge locality; and
sorting, with the computer system, the set of nodes in the second partition based on a gain in edge locality.

4. The computer implemented method of claim 1 , wherein a difference between a number of nodes in the first partition remapped to the second partition and a number of nodes in the second partition remapped to the first partition is within a threshold.

5. The computer implemented method of claim 1 , wherein a difference between a weight of nodes in the first partition remapped to the second partition and a weight of nodes in the second partition remapped to the first partition is within a threshold.

6. The computer implemented method of claim 1 , further comprising:
computing, with the computer system, a first total node weight of the first partition before the remapping.

7. The computer implemented method of claim 6 , further comprising:
computing, with the computer system, a second total node weight of the first partition after the remapping.

8. The computer implemented method of claim 1 , wherein the computer system is a non-distributed system, the method further comprising:
loading, with the computer system, a node graph into memory, wherein the node graph comprises the nodes in the first partition and the nodes in the second partition.

9. The computer implemented method of claim 1 , wherein the computer system is a distributed system, the method further comprising:
loading, with the computer system, different portions of a node graph across the distributed system, wherein the node graph comprises the nodes in the first partition and the nodes in the second partition.

10. The computer implemented method of claim 9 , further comprising receiving current partition IDs of connected nodes associated with each of the nodes in the first partition.

11. The computer implemented method of claim 10 , wherein the histograms for the nodes in the first partition are computed based on the current partition IDs.

12. The computer implemented method of claim 11 , further comprising providing a current partition ID of each of the nodes in the first partition.

13. The computer implemented method of claim 12 , wherein candidate partitions are selected based on a locality gain threshold.

14. The computer implemented method of claim 9 , further comprising:
generating, with the computer system, a record of all partition pairs for a plurality of partitions that indicates nodes to be remapped.

15. The computer implemented method of claim 1 , wherein the node graph is supported by a social networking system.

16. A system comprising:
at least one processor, and
a memory storing instructions configured to instruct the at least one processor to perform:
computing a respective histogram for each node in a first partition, wherein the histogram for a node in the first partition indicates, for each partition in a set of partitions, a corresponding total weight of edges of the node that are connected to the partition;
computing a respective histogram for each node in a second partition, wherein the histogram for a node in the second partition indicates, for each partition in the set of partitions, a corresponding total weight of edges of the node that are connected to the partition;
selecting the second partition as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition and on a probability algorithm relating to a gain in edge locality, the probability algorithm being defined based on a total number of connected nodes within a partition and a total number of connected nodes within partitions that result in a gain;
selecting the first partition as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition;
determining that remapping (i) at least a portion of the set of nodes in the first partition to the second partition and (ii) at least a portion of the set of nodes in the second partition to the first partition results in both the first partition and the second partition satisfying a threshold load balance, wherein at least some of the nodes in the set correspond to users of the social networking system, and wherein the load for a partition is measured based at least in part on an amount of data transferred by users mapped to the partition; and
remapping at least the portion of the set of nodes in the first partition to the second partition and at least the portion of the set of nodes in the second partition to the first partition.

17. A non-transitory computer storage medium stor

Assignees

• Facebook Inc

Inventors

• Presta Alessandro
• Shalita Alon Michael

Classifications

• G06Q10/40

  Business processes related to social networking or social networking services · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06Q10/101

  Collaborative creation, e.g. joint development of products or services · CPC title

• G06Q50/01

  Physics · mapped topic

• G06F17/30958 Primary

  Physics · mapped topic