Multi-level cache management of quantitative trading platform

User experience and return time of backtesting results show a negative correlation. For the convenience of denotation and computation, we assume that user experience is bad when experience value is large. Experience value is positively related to time. Since there are different types of users, experience function for each kind of user is distinct. For example, we can assume that experience value of users who pay increases fast with time and that of free users grows slowly or even stays unchanged. When making agreements with users, user experience functions are different. The main functions are shown in Figure 1. Assume that f (t) is the user experience function, where t is the return time of backtesting results. In Figure 1(a), it is a linear function and formalised as f (t) = a · t, where a is the slope. In Figure 1 (b), it is a piecewise function and formalised as f(t)={c10<t≤t1c2t1<t≤t2c3t2<t f(t) = \left\{ {\matrix{ {{c_1}} & {0 < t \le {t_1}} \cr {{c_2}} & {{t_1} < t \le {t_2}} \cr {{c_3}} & {{t_2} < t} \cr } } \right.\; , where c_1, c_2, and c₃ are constants, and t₁ and t₂ are segmentation times. In Figure 1(c), it is a combination of linear and piecewise functions and formalised as f(t)={at0<t≤t1at1t1<t≤t2c3t2<t f(t) = \left\{ {\matrix{ {{\rm{at}}} & {0 < t \le {t_1}} \cr {a{t_1}} & {{t_1} < t \le {t_2}} \cr {{c_3}} & {{t_2} < t} \cr } } \right.\; . In Figure 1(d, e) they are combinations and separately formalised as f(t)={c10<t≤t1c2t1<t≤t2c2+a(t−t2)t2<t f(t) = \left\{ {\matrix{ {{c_1}} & {0 < t \le {t_1}} \cr {{c_2}} & {{t_1} < t \le {t_2}} \cr {{c_2} + a(t - {t_2})} & {{t_2} < t} \cr } } \right.\; , f(t)={c10<t≤t1(c3−c1)(t2−t1)(t−t1)t1<t≤t2c3t2<t f(t) = \left\{ {\matrix{ {{c_1}} & {0 < t \le {t_1}} \cr {{{({c_3} - {c_1})} \over {({t_2} - {t_1})}}(t - {t_1})} & {{t_1} < t \le {t_2}} \cr {{c_3}} & {{t_2} < t} \cr } } \right.\; , where (c3−c1)(t2−t1) {{({c_3} - {c_1})} \over {({t_2} - {t_1})}} is the slope of Figure 1(e). In Figure 1(f), it is a non-linear function and formalised as f (t) = a^t−^c|a > 1, where parameter a can adjust the growth rate of experience value and parameter c controls the growth rate of the initial value. The experience value increases fast as time is large.

Fig. 1

Several common user experience functions are given above and the platform can use various functions as well. Different parameters are set to determine distinct experience loss rate according to user categories. Experience loss rate denotes the decline rate of user experience over time, which quantifies the effects of backtesting return time on experience value. The function provides a basis for multi-level cache management.

Different users have diverse demands for query time. Moreover, different weights are used in user experience functions in terms of user importance. The above way could unify the optimised objective. In addition, user experience is related to the profit of the service provider. The global objective of optimising user experience is the same as maximising the profits of the service provider.

The framework of multi-level cache management on quantitative trading platform is demonstrated in Figure 2, which periodically manages cached data. The platform predicts the access volume of different data during the next period and adjusts the cached data in multi-level caching devices according to access volume and user experience function. When a user accesses data based on quantitative trading platform, the cached data are first obtained. If cached data cannot be fetched, it searches data from the database.

Fig. 2

The cached data are stored in permanent storage media in the form of software function, i.e. they are stored into memory or disc by means of object or object serialisation. The caching characteristics of the software function are always returning the same results for the same input parameters, just like the decoration function ‘lru_cache’ in Python.

In theory, storage is finished by assigning storage space for cached data. For the convenience of adding, deleting and merging operations, the fixed amount of storage is set for each kind of caching device. Since the value and space of different caching devices are distinct, the fixed sizes for different devices are variously set. Generally, the fixed size of a device is proportional to the total storage space and inversely proportional to the times of additions and deletions on the device.

In Figure 2, the module of access volume record records user access volumes of different data in each period. Based on historical data, the access volume of the next period can be predicted using statistics or machine learning algorithm.

When performing backtesting, time-series data are accessed generally by the function: getData(t_b,t_e,s), where t_b is the start time, t_e is the end time and s is the target of stock data. After time-series data are fetched, filter operation is further executed. It is observed that the triple < t_b,t_e,s > could only determine a set of cached data. If n_b,e,s denotes access volume of the data determined by a triple and h_b,e,s is the amount of space taken up by the data, a piece of data on the platform is formalised as < t_b,t_e,s,n_b,e,s,h_b,e,s >.

Access volumes of different cached data next period can be predicted based on historic data. The common ways are historical statistics and machine learning. Historical statistics get the average value or weighted average value as a prediction value. Assume that q_t is the access volume to be predicted. We know q_t = ∑_i∈[1,n] α_iq_t−i,∑_i∈[1,n] α_i = 1 stands, where q_t−_i is the historical access volume of the ith period before current period. It is obtained through statistical data of the first n periods. Data in each period have a weight of α_i. Machine learning can use RNN, LSTM and GRU algorithms, and the prediction approaches are not our concerns.

Performing data merging for the overlapping part can save cached space. We assume that there are two pieces of data: e₁ =< t₁,t₃,s,n_1,3,s,h_1,3,s > and e₂ =< t₂,t₄,s,n_2,4,s,h_2,4,s >, where t₁ < t₂ < t₃ < t₄ stands. The cached data determined by < t₁,t₃,s > and < t₂,t₄,s > have an overlapping part. As shown in Figure 3, the shadow area denotes the overlapping part. It is easily seen that data merging can save more space than that saved by separately caching. Without loss of generality, we use e₃ to denote the item after merging e₁ and e₂, and formalised as e₃ =< t₁,t₄,s,n_1,4,s,h_1,4,s >, n_1,4,s = n_1,3,s + n_2,4,s,h_1,4,s = h_1,3,s + h_2,4,s − h_overlap, where h_overlap is the size of overlapped data.

Fig. 3

The method of determining data overlapping is as follows. (1) All the required data to be accessed are segmented and stored logically. (2) Assume that s_i is the identification of a piece of stock data. Logical hash index for s_i is constructed. (3) Logical hash index links to physical address of different levels of caching devices. (4) Based on hash indexes and their links, it is easy to determine whether there are overlapped data on the same level.

Since the determination of overlapped data is based on the hash index, its time cost is small. When the cached data are overlapped, the data on the same level of caching device are deleted directly.

Merging operation would change the value of cached data. Value is positively correlated with access value and negatively correlated with data size. Ignoring the other factors, the value of cached data can be computed as pb,e,s=nb,e,shb,e,s {p_{b,e,s}} = {{{n_{b,e,s}}} \over {{h_{b,e,s}}}} . After merging, the value of p_b,e,s may increase or decline. Let us consider the following example. There are two data segments n_1,3,s = 6, h_1,3,s = 6, p_1,3,s = 1 and n_2,4,s = 12, h_2,4,s = 6, p_2,4,s = 2. When data merging is done and the space is h_1,4,s = 10, we get p_1,4,s = (n_1,3,s + n_2,4,s)/h_1,4,s = 1.8, where its value is lower than p_2,4,s. If the space is h_1,4,s = 6, we get p_1,4,s = (n_1,3,s + n_2,4,s)/h_1,4,s = 3, where its value is higher than p_1,3,s and p_2,4,s.

p_b,e,s can determine whether the cached data are placed into cache and which kind of cache they are placed into. For the case of p_1,3,s > p_1,4,s, i.e. the value p_1,4,s after merging cached data < t₁,t₄,s > is smaller than the value p_1,3,s of cached data < t₁,t₃,s >, merging operation may lead to failing to be placed into cache some data that could have been cached. Therefore, our proposed merging algorithm conforms to the rule of not reducing value. The value after merging should not be smaller than that of any data before merging.

Based on the above considerations, we introduce our stock merging algorithm of cached data, which is called the value-first cached data merging algorithm. It first tries to merge data with high merging values, then places the merged data into cache and continually do merging until all the data cannot be merged again. Its concrete steps are shown in Algorithm 1, which just gives the merging method for a stock. Since the data are not overlapped between stocks, merging operations for other stocks also use Algorithm 1.

When a user accesses a set of time-series data and data are cached using the merging method, the data need to be restored. Our method is to scratch the required data in memory. Taking python as an example, cached data are first converted into DataFrame and then the selection is done. Since interception operation of data is easy and done in memory, the time lost accessing data from merged data and original data can be ignored.

In the experiments, we test how cached data merging operation (CDMO)-multi-level cache placement (MPC) performs in user experience for different cache capacities. CDMO-MPC means that Algorithm 1 is first used to merge cached data and then the data are placed using Algorithm 2. Two kinds of users are introduced: advanced and common. Functions in Figure 1(a) and (e) are, respectively, their user experience functions. The indicator is the average value of user experience. Our proposed MPC algorithm is compared with two classical algorithms: Least Recently Used (LRU) and Least Frequently Used (LFU). Before making comparisons, the two algorithms are improved as follows. (1) First place data with high priority into the advanced cache. (2) The replaced data from the advanced cache are placed into the next lower level of cache. (3) The replaced data from the upper level of cache are placed into the next lower level, and the rest can be done in the same manner.

We use three caching media: memory, solid-state disc and disc and set their ratio of capacities as 1:10:100. In Figure 4, the horizontal ordinate represents the capacity of memory and that of the other caching devices that can be computed. We can see that MPC performs largely better than LRU and LFU in user experience, especially for small caching capacity.

Fig. 4

In this section, the effect of different cache combinations on user experience is validated. We separately set three combinations of caching devices: just memory, memory-SSD and memory-SSD-disc. As shown in Figure 5, MPC is >50% better than the other algorithms in the average value of user experience, no matter for which cache combinations. The main reason is that our proposed MPC algorithm aims to optimise the user experience. The user experience of MPC improves 61% than LFU in a just-memory environment. In the memory-SSD environment, the user experience of MPC improves 75%. In the memory-SSD-disc environment, it improves 81%. As shown in experiments, the MPC approach has a better optimising performance for the case of multiple caching devices.

Fig. 5

In this section, we test the CDMO algorithm. Four different combinations of algorithms are introduced. CDMO-MPC is to first use CDMO to merge data and then use MPC to place data. NoMerge-MPC is directly using MPC to place data without merging. CDMO-LRU is to first use CDMO and then execute LRU. NoMerge-LRU is to directly use LRU to place data without merging operation. The horizontal ordinate is memory capacity and the ratio of memory, SSD and disc is 1 10 100. From Figure 6, it is seen that both CDMO-MPC and CDMOLRU perform better than their corresponding algorithms without merging operation, especially when caching capacity is small. In addition, NoMerge-MPC has a better user experience than CDMO-LRU, since MPC plays a fairly good role in optimising user experience.

Fig. 6

Here, we demonstrate the effects of user experience and access rate of MPC for different users. Advanced users and common users are set, and for user experience functions, refer to Section 6.1. Our comparison object is LRU. Figure 7 shows that common users have a better experience than advanced users for MPC, while LRU has little difference for different users. That is because MPC is driven by user experience. For accessing rate, MPC also shows a larger difference than LRU for two kinds of users, and MPC has a slower accessing rate for the common user than LRU. That is due to much more resources taken up by the advanced users.

Fig. 7