Brief Announcement: Demand-Aware Consistent Hashing with Bounded Loads & Greedy Routing

We consider a set of $n$ servers $S$, and a set of $m$ items $V$. The server that an item $v$ is currently in is its host server, $host(v)$. The frequency of an item $v$, noted by $freq(v)$, is the number of repetitions of an item in the request sequence $\sigma$ with size $|\sigma |$. We assume that all servers have the same capacity for items. We allow each server to hold up to $c$ items from set of items $V$. We define the number of items in a server $s$ as its load and also the storage utilization as number of items divided by capacity, in other words $utilization=\frac{m}{c}$.

A server graph, is an overlay network that connects servers to each other. For a constant outgoing degree $b$, we use a $b$-ary de Bruijn graph of dimension $d$ [7]. We choose $b$ such that $b^d$ is bigger than number of servers . In such a construction, each server is assigned a $d$-digit sID (server ID) in base $b$. Each server is connected, through a directed connection, to at most $b$ other servers. It is known that such a graph results also in in-going degree of $b$ (considering self loops) [14]. Figure 1 shows an example of de Bruijn graphs with $8$ servers, considering $b=2$ and $d=3$. For each item $v$, we consider an item ID, vID, which is in base $b$, with length $\gamma =2\cdot d$. The first $d$ digits of vID determines source of an item: source of item $v$ is the server that has sID equal to the first $d$ digits of vID an item. The rest of digits helps us in the local routing.

By considering greedy routing, we choose the next server which minimize the distance on the directed server graph to the destination. It is known that the greedy routing results in distance at most $d$ between any two servers in a de Bruijn graph of dimension $d$ [14]. We note that this greedy distance is on the directed server graph.

For a source server $s$, GreedyTree of source $s$, denoted by GTree(s), is a sub-tree of the server graph, rooted in $s$. This tree is constructed by taking a union of unique greedy paths from $s$ to all other servers. See an example of GreedyTree in Figure 2(b).

In global search method, all servers maintain a global map. This map keeps track of sID of the host of items that are sourced in the server. When we start searching for an item from its source, we consider access to sID when following the greedy path toward the host of the item.

The local search builds on top of the greedy routing, and finds the item solely based on the vID of items. The local search works in two phases.

1. 1.

   In the first phase, we take a walk on the server graph. The steps of this walk are only determined by the vID of the item, without the need to access a global map. For an item $v$, we determine the $i$-th step of the walk as follows: we go to the neighboring server that has $(i+d)$-th digit of vID of $v$ as its rightmost digit.

2. 2.

   After $d$ steps of the walk, when we reach the last digit of vID, we start the second phase, and follow a Hamiltonian path from that server, to find a suitable server. We follow the Hamiltonian cycle that is created by a $d$ digit $b$-ary Gray code [8]

To find an item, we start from the source of the item, and follow the above-mentioned phases, until we reach the item. We eventually find such a host server, given that we visit all server during the second phase of the local search. Procedure 1 recaps a local search step.

Distance of an item $v$, $di{s}_A(v)$, is the number of steps that search algorithm $A$ requires to find item $v$. For a given search algorithm $A$ we define the offline access cost as ${\sum }_{v\in V}di{s}_A(v)\cdot freq(v)$.

Following is the formal problem tackled by this paper:

We benefit from an elaborate collection of items in each server by assigning a fixed fraction of the capacity to a certain source. This fraction depends on the distance of the source to the current server.

We define $fra{c}_{s,t}$, as the fraction of server $s$ dedicated to the source $t$. Consider $A$ as the adjacency matrix of the server graph, and $A[s,t]$ as the value in row $s$ and column $t$ of it. For any given distance $d$, we allocate $A^d[s,t]\times \frac{c}{b^{2\cdot d-1}}$¹¹1$A^d[s,t]$ determines the number of walks from $s$ to $t$, and remember that $b$ is the outgoing degree of a server. fraction of server $t$ to $s$. If there is a leftover capacity in a source, we dedicate it to the same source. See an example of capacity division inside a server in Figure 2(a).

A fractional tree of a source $s$, is source tree of $s$ in which we only consider the capacities allocated to source $s$. See an example of fractional tree in Figure 2(b).

The virtual source of an item $v$ is initially its source, $s=source(v)$. The virtual source of an item changes, when that items reach a leaf of the $GTree(s)$. This way, we can ensure that $v$ can always find a spot to placed in, even if its source is heavily loaded. See an example of capacity assigned to a server in its Tree in Figure 2(b).

Similar to the A-DACH, L-DACH (as an acronym for local demand-aware consistent hashing) starts by sorting items based on their frequencies. It then goes over the items of the sorted list, one by one. For each item, it finds the closest server, using the local routing, that has an empty spot in its fraction of capacity for the virtual source of the item.