# RCM: A Remote Cache Management Framework for Spark
## 4 Framework Implementation
### Cache Data Weight Generation Module  
CWG implements the function of the weight generation module. According to Section 3.1, CWG takes the response time of the query database, the number of queries, the data size and time loss into consideration. At the beginning, the original weight is obtained by the form of a cost ratio. To introduce the characteristic of time loss, a time loss function is given, which mirrors that the hit rate is reduced with the lapse of time. The final weight is obtained by the time loss function. Then, a candidate list is created by the weight sorting. According to Section 4.1, the basic data are collected by a status monitor and data collection module.  
The pseudocode of CWG is shown in Algorithm 1. When a new database query is sent, _QueryReq_ is given a non-null value, and the weight starts to be calculated (line 1). Firstly, basic variables are initialized (line 2 to line 4). The free space, _RestSpace_, is set to _MaxSpace_, which is the maximum value of cache resources. The response time of querying, \(T_{Query}\), is set to 0. The time cost of totally querying data, \(T_{cost}\), is set to 0. Then, basic data are extracted from _QueryReq_ (line 5 to line 15). The saving time of data, \(t_{start}\), is recorded if the data do not exist in the cache. The frequency of querying data adds one. Data size, _size_, is recorded. \(T_{Query}\) records the longest response time for sub-requests, while \(T_{cost}\) records the total time cost for current data. According to Equation (3), \(weight\_ori\) is calculated (line 16). According to Equation (4), \(weight\), which has taken time loss into consideration, is obtained (line 18). As a result, the \(weight\) and \(QueryReq\) are recorded in the candidates list (line 19). In the end, we give the analysis of complexity. CWG has two nested loops. Therefore, it has a time complexity of O (N). Due to the weight and QueryReq being recorded in the candidates list, which is two-dimensional, the space occupation of CWG is O (\(N^{2}\)).  
Figure 4: The flowchart of RCM.  
```
0:\(y\): is an accommodation coefficient to control the influence of time loss; \(HashMap<queryId,frequency>TaskList\): is a list of recording frequency for every query; \(RestSpace\): represents the size of free space in the cache; \(MaxSpace\): represents the total size of cache space; \(QueryReq\): is a request wrapper;
0:\(List<QueryReq,weight>candidates\): is the candidates data for saving in cache;
1:while\(QueryReq!=NULL\)do
2:\(RestSpace=MaxSpace\);
3:\(T_{Query}=0\);
4:\(T_{cost}=0\);
5:if\(TaskList[QueryREquationqueryId]==NULL\)then
6:\(t_{start}=current.time\) ;
7:endif
8:\(++\)\(TaskList[QueryREquationqueryId]\) ;
9:\(size=QueryREquationsize\);
10:for\(i=0\) to QueryREquationsubQuery.length\(-1\)do
11:if\(QueryREquationsubQuery[i].time>T\)then
12:\(T_{Query}=Query.REquationsubQuery[i].time\);
13:endif
14:endfor
15:\(T_{cost}=TaskList[QueryREquationqueryId]\times T_{Query}\);
16:\(weight\_ori=\frac{T_{cost}}{size}\);
17:\(t_{last}=current.time\);
18:\(weight=weight\_ori\times\frac{-y\times(t_{last}-t_{start})}{T_{rect}}\);
19:\(candidates.add(QueryReq,weight)\);
20:endwhile
```  
**Algorithm 1** CWG Algorithm.