Clustering

To achieve the goal of reducing the number of replicas in the system, we essentially want to cluster mutually interested objects on the same node, thereby, limiting the number of remote interest links. Each node $sid_n$ periodically performs the following heuristic to determine if it should migrate a primary object $guid_x$ to another node $sid_m$. Let $interests(x,k)$ denote the set of objects that $guid_x$ is interested in on $sid_k$, and $interested(x,k)$ be 1 if $k$ maintains at least one object interested in $guid_x$, and 0 otherwise. We define $weight(x,k)$ as:

$$weight(x,k) ~~=~~ u_x \cdot interested(x,n) ~~+ \hspace{-0.3in}\sum_{y \in interests(x,k)}\hspace{-0.3in} u_y~.$$

This value is the maximum aggregate savings (to the entire system) of placing $guid_x$ on $sid_k$ instead of placing $guid_x$ outside the system the entire system. Note that a node outside the system maintaining $guid_x$ would have to receive updates for objects on $sid_k$ that $guid_x$ is interested in and transmit updates to $sid_x$ if some object on $sid_x$ has an interest in $guid_x$.

If $weight(x,m) > weight(x,n)$, it implies that $guid_x$ has a higher weighted interest in objects on $sid_m$ than on the current node, $sid_n$. Hence, we should migrate $guid_x$ to $sid_m$ if the migration would not push $sid_m$ over $highwater$; i.e.,

$$highwater ~~>~~ load_m + f_x + \sum_{k \neq m} weight(x,k)~.$$

This is in fact a conservative, worst-case estimate of how much we will increase $sid_m$'s load, since it may already have replicas for $guid_x$'s interests. If we have multiple such candidates, then we migrate $guid_x$ to the one with the largest $weight(x,\cdot)$ value.

Variants of this heuristic examining multiple primary objects at a time could perform more optimal clustering. However, the above approach is cheap and can be run frequently.