# RCM: A Remote Cache Management Framework for Spark
## 4 Framework Implementation
### Cache Placement Module  
The computing nodes initiate a query for the cache server, and the cache server is responsible for responding to the query. Because of the computing and transmission process, different servers have different cooperation efficiencies for every computing node. According to Equation (9), the goal of the cache placement problem is to maximize the cooperation efficiency between computing nodes and servers. This problem is described as maximum weight matching in bipartite graph \(G=(V,E)\). In Figure 5, the left vertexes set of the bipartite graph, named \(X\), represents the computing nodes and the right vertexes set of the bipartite graph, named \(Y\), represents the cache servers. The edges, which connect \(X\) to \(Y\), represent cooperation efficiency with weight. In order to solve the maximum weight-matching problem in a bipartite graph, we adopt the Kuhn-Munkres (KM) algorithm [1] to find optimal solution. We define the items \(TX\)\((i)\) and \(SY\)\((j)\) for every \(i\in X\) and \(j\in Y\). If the \(edge_{ij}\) meets the condition that \(TX\)\((i)\)\(+\)\(SY\)\((j)\geq weight_{ij}\), these items are called \"feasible\". Let \(G\) be divided into different subgraphs. \(G^{\star}=(V,E^{\star})\) is called \"the equality subgraph\" only when all the edges of \(G^{\star}\) meet the condition that \(TX\)\((i)\)\(+\)\(SY\)\((j)\)\(=\)\(weight_{ij}\). When M' meets the condition that all vertices in X have been matched to Y, M' is called \"the perfect matching\" in \(G^{\star}\). Theorem 1: _Given feasible items, if there is M' in \(G^{\star}\), M' is also the optimal matching for \(G\)._  
Proof of Theorem 1.: Let \(P\) be equal to \(\sum_{i\in X}TX(i)+\sum_{j\in Y}SY(j)\). For all feasible items, the sum of all weights always meets \(\sum weight_{ij}\leq P\). If matching M meets the condition that \(\sum weight_{ij}=P\), M is the optimal matching. Then, considering the perfect matching M', the weight of any edge meets the condition that \(TX\)\((i)\)\(+\)\(SY\)\((j)\)\(=\)\(weight_{ij}\). So, the sum of all weights meets the condition that \(\sum weight_{ij}=P\), which means that M' is also the optimal matching for \(G\). Based on Theorem 1, our goal is to find \(M^{\prime}\) in \(G^{*}\). The KM algorithm searches the augmenting path in \(G^{*}\) to find a perfect match. If a perfect match is not found, some items of vertices are adjusted and add more edges to \(G^{*}\). CPL uses the KM algorithm to find the best match. In detail, we describe the procedures in Algorithm 3. ```
1:\(List<taskId>TX\): represents the item of the cache; \(List<serverId>SY\); represents the item of servers; \(List<flag>vistTX\): is the flag of visiting left vertices; \(List<flag>vistSY\): is the flag of visiting right vertices; \(List<taskId,serverId>efficiencyList\): is a list of recording cooperation efficiency between computing nodes and cache servers;
2:\(match[i]\): is the best matching result;
3:for i = 0 to N - 1 do
4: TX[i] = max (efficiencyList[i][j]), SY[i] = 0, match[i] = -1 ;
5:endfor
6:for i = 0 to N - 1 do
7:for j = 0 to N - 1 do
8: slack[j] = INF;
9:while TRUE do
10:for j = 1 to N do
11: visitTX[i] = FALSE, vistSY[i] = FALSE;
12:if FindPath (i) then
13: break;
14:else
15:\(\phi\) = min (slack[j] );
16:endif
17:endfor
18:for j = 1 to N do
19: visitTX[i] = FALSE, vistSY[i] = FALSE;
20:if vistTX[j] then
21: TX[j] = TX[j] - \(\phi\);
22:else if vistSY[j] then
23: SY[j] = SY[j] - \(\phi\);
24:else
25: Slack[j] = Slack[j] - \(\phi\);
26:endif
27:endfor
28:endfor
```  
**Algorithm 3** KM Algorithm. In the bipartite graph, \(TX\) represents the item of cache, and \(SY\) represents the item of servers. \(vistTX\) and \(vistSY\) represent the flag of visiting. \(efficiencyList\) records the cooperation efficiency between the nodes and servers. Firstly, to promise items \(TX\) and \(SY\) are feasible, \(TX\) is initialized to the maximum value of weight. \(SY\) is initialized to 0, and \(match[i]\) is initialized to \(-1\) (line 2).