# RCM: A Remote Cache Management Framework for Spark
## 4 Framework Implementation
### Cache Replacement Module  
When the memory space of the cache server is insufficient, the cache replacement algorithm replaces low weight data with high weight data to maximize the sum of cache weights. According to the objective function Equation (5), it can be seen that this problem is a non-linear integer programming problem. It is difficult to obtain an accurate solution in polynomial time. Based on the greedy algorithm, CREP finds the optimal solution in the current round and obtains an approximate solution through an iteration process. Then, CREP is described in detail.  
The sub-problem of Equation (5) can be described as follows: Firstly, cache data of the lowest weight are removed. Then, the data of the candidate list are sorted by weight. Let \(F_{1 th}\) be the first data weight of candidate list. Let \(F_{2 th}\) be the first two data weights of the candidate list. Let \(F_{3 th}\) be the first three data weights of the candidate list, and so on; let \(F_{4 th}\) be the first k data weight of the candidate list. According to the principle of the greedy algorithm, cache servers store as many candidate data as possible within the size of the cache resource. Therefore, the sub-problem is defined as shown in Equation (10).  
\[\begin{split} Max(F_{1 th},F_{2 th},F_{3 th},...;F_{kth})\\ s.t.\qquad\sum_{i=1}^{k}CandidateSize_{i}<RestSpace\end{split} \tag{10}\]  
where \(RestSpace\) represents free cache resource before the replacement operation, and \(CandidateSize\) represents the size of candidate data. The sub-problem is solved after a round of cache replacement. Then, the solutions of all the sub-problems are merged to form the final solution set. The pseudocode of CREP is shown in Algorithm 2.  
```
1:\(RestSpace\): represents the size of free space in the cache; \(MaxSpace\): represents the total size of cache space; \(cacheDataList\): records cached data; \(QueryReq\): is a request wrapper; \(List<QueryReq,weight>candidates\): is the candidates data for saving in cache;
2:CWG ();
3:cacheDataList.orderByWeight ();
4:candidates.orderByWeight ();
5:whilecandidates.notEmpty () do
6: Remove (cacheDataList[cacheDataList.length-1]);
7:for i = 0 to \(candidates.length\)-1 do
8:if candidates[i][0].size <restSpace then
9: Save (candidates[i][0].data );
10:endif
11:endfor
12:endwhile
```  
**Algorithm 2** CREP Algorithm.  
If the cache resource is insufficient, CREP starts to work. At first, some pretreatments are performed (line 1 to line 3). The candidate data list can be obtained from the return result of the CWG algorithm. In order to accelerate the replacement operation, \(cacheDataList\) and \(candidates\) are sorted by weight. Then, candidate data try to replace low weight data in the cache. The process of replacement follows: Firstly, CREP removes the data of the lowest weight from \(cacheDataList\). Secondly, CREP tries to transfer the highest weight data from the candidates list to cache. Thirdly, the first two steps are repeated until the candidates list is empty (line 4-line 11). In the end, we give the analysis of complexity. CREP also has two nested loops. So, it has the time complexity of O (\(N^{2}\)). The space occupation of CREP has two parts, cacheDataList and candidates. They also are two-dimensional. However, the address of candidates is pointing to the address of the candidates list of Algorithm 1. It shared data in two algorithms. Therefore, Algorithm 2 has the space complexity of O (\(N^{2}\)).