CN101236530B - High speed cache replacement policy dynamic selection method - Google Patents
High speed cache replacement policy dynamic selection methodDownload PDFInfo
- Publication number
- CN101236530B CN101236530BCN2008100571727ACN200810057172ACN101236530BCN 101236530 BCN101236530 BCN 101236530BCN 2008100571727 ACN2008100571727 ACN 2008100571727ACN 200810057172 ACN200810057172 ACN 200810057172ACN 101236530 BCN101236530 BCN 101236530B
- Authority
- CN
- China
- Prior art keywords
- cache
- module
- replacement strategy
- data
- access
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Memory System Of A Hierarchy Structure (AREA)
Abstract
Description
Translated fromChinese技术领域technical field
高速缓存替换策略的动态选择方法属于存储系统领域，尤其涉及其中的高速缓存领域。A method for dynamically selecting a cache replacement strategy belongs to the field of storage systems, and in particular relates to the field of cache.
背景技术Background technique
高速缓存替换策略的动态选择方法是指：目前已有的高速缓存替换策略很多，不同的策略在不同的负载上有不同的效果；本方法根据负载的变化动态地选择最适合当前负载的高速缓存替换策略，并进行在线切换，从而提高存储系统高速缓存的命中率，最终提高存储系统的整体性能。传统的高速缓存替换策略有的专门针对某些特征的负载或环境，如智能写(WOW)策略针对写操作比较昂贵的RAID5等设备，而双局部性策略(DULO)在顺序写为主的负载上有较好的效果。对于未知的或变化的负载来说，很难从这些策略中进行选择。另外一些高速缓存替换策略可以根据负载的变化自适应地调整自身，如自适应低负载策略(ARC)，多队列策略(MQ)等，这些策略可以取得普遍比较好的效果，但在特定负载上无法得到最好的效果。于是有人提出了从多个高速缓存替换策略中选择的思想，自适应多专家策略(ACME)提出了多专家系统用于高速缓存替换策略的选择，但它的CPU和内存开销都比较大，且缺少实现验证。The dynamic selection method of the cache replacement strategy refers to: there are many existing cache replacement strategies, and different strategies have different effects on different loads; this method dynamically selects the most suitable cache for the current load according to the change of the load Replace the policy and perform online switching, thereby improving the hit ratio of the storage system cache, and ultimately improving the overall performance of the storage system. Some traditional cache replacement strategies are specially designed for loads or environments with certain characteristics. For example, the smart write (WOW) strategy is aimed at devices such as RAID5 with relatively expensive write operations, while the dual locality strategy (DULO) is used for sequential write-based loads. have a better effect. For unknown or changing loads, it can be difficult to choose among these strategies. Other cache replacement strategies can adaptively adjust themselves according to load changes, such as adaptive low-load strategy (ARC), multi-queue strategy (MQ), etc. These strategies can achieve generally better results, but on specific loads Can't get the best results. So someone proposed the idea of selecting from multiple cache replacement strategies. Adaptive multi-expert strategy (ACME) proposed a multi-expert system for the selection of cache replacement strategies, but its CPU and memory overhead are relatively large, and Missing implementation validation.
本发明提出了一种新的高速缓存替换策略的动态选择方法，通过异步策略选择将策略选择的过程和普通的高速缓存访问流程分离开来，从而降低了CPU和内存开销，通过在线策略切换将选择结果立即投入使用，以尽快提高性能。The present invention proposes a new method for dynamically selecting a cache replacement strategy, which separates the process of strategy selection from the ordinary cache access process through asynchronous strategy selection, thereby reducing CPU and memory overhead, and switching the strategy online through online strategy switching Selection results are used immediately to improve performance as quickly as possible.
发明内容Contents of the invention
本发明的目的在于提供一种能适用于多种高速缓存系统的替换策略选择方法，能够从多个候选高速缓存替换策略中选择最适合当前负载的策略并进行在线切换，从而提高系统的性能。同时尽量减小选择过程带来的CPU和内存开销。本发明的重点在于高速缓存替换策略的模块化设计和在线切换，以及最优高速缓存替换策略的动态选择过程。The purpose of the present invention is to provide a replacement strategy selection method applicable to various cache systems, which can select the most suitable strategy for the current load from multiple candidate cache replacement strategies and perform online switching, thereby improving system performance. At the same time, the CPU and memory overhead caused by the selection process are minimized. The focus of the invention lies in the modular design and online switching of the cache replacement strategy, and the dynamic selection process of the optimal cache replacement strategy.
本发明的特征在于：所述方法是在高速缓存存储器系统内的一个数字集成电路上依次按以下步骤实现的：The present invention is characterized in that: the method is realized in the following steps on a digital integrated circuit in the cache memory system:
步骤(1).初始化，设置以下模块：Step (1). Initialize and set up the following modules:
高速缓存替换策略模块，高速缓存服务模块，访问记录采集器模块以及访问记录分析器模块，其中：A cache replacement policy module, a cache service module, an access record collector module and an access record analyzer module, wherein:
1)高速缓存替换策略模块，设立以下接口描述命中和替换时的逻辑：1) The cache replacement strategy module sets up the following interface to describe the logic of hit and replacement:
a.初始化接口，为用户指定的或第一次运行时确定的或切换后的当前高速缓存策略模块分配内存，初始化数据结构；a. Initialize the interface, allocate memory for the current cache policy module specified by the user or determined when running for the first time or after switching, and initialize the data structure;
b.释放用接口，释放即将被替换的高速缓存替换策略模块，包括释放数据结构和内存，供被替换的高速缓存替换策略模块卸载时使用；b. release interface, releasing the cache replacement strategy module to be replaced, including releasing data structure and memory, for use when the replaced cache replacement strategy module is unloaded;
c.更新用接口，当高速缓存数据块被命中时，更新该块的优先级；c. The interface for updating, when the cache data block is hit, the priority of the block is updated;
d.插入用接口，当插入新的高速缓存数据块时，设置该块的优先级；d. The interface for inserting, when inserting a new cache data block, setting the priority of the block;
e.替换用接口，取优先级最低的高速缓存数据块为被替换块时使用；e. Replacement interface, used when taking the cache data block with the lowest priority as the replaced block;
所述高速缓存替换策略模块共有以下五种：最近被使用，双队列，多队列，自适应低负载和低最近相关度，各有一个固定的入口函数register，以便把自己的接口实现注册给所述高速缓存服务模块，The cache replacement strategy module has the following five types: recently used, double queue, multi-queue, adaptive low load and low recent correlation, and each has a fixed entry function register, so that its own interface is registered to all The cache service module described above,
在各高速缓存替换策略模块中，处于运行状态的为当前高速缓存替换策略模块，其余则为候选高速缓存替换策略模块；In each cache replacement strategy module, the current cache replacement strategy module is in running state, and the rest are candidate cache replacement strategy modules;
2)高速缓存服务模块，把包括磁盘在内的低速存储设备的数据缓存在内存中，当用户访问数据时直接进行内存访问，该高速缓存服务模块设有：高速缓存数据、高速缓存元数据以及哈希表，其中2) The high-speed cache service module caches the data of low-speed storage devices including disks in the memory, and directly performs memory access when the user accesses the data. The high-speed cache service module is equipped with: cache data, cache metadata and hash table, where
a.高速缓存数据，是缓存好的磁盘数据，被分成多个固定大小的高速缓存数据块，块的大小为4KB，a. Cache data, which is cached disk data, is divided into multiple fixed-size cache data blocks, and the block size is 4KB.
b.高速缓存元数据，用于维护和管理所述高速缓存数据，其中包括：b. Cache metadata for maintaining and managing said cache data, including:
1)每个高速缓存数据块的物理地址；1) the physical address of each cache data block;
2)每个高速缓存数据块符号位用于标志该块是否已被写入磁盘；2) Each cache data block sign bit is used to mark whether the block has been written to disk;
3)一个最近被使用队列，用于记录所述高速缓存数据块的优先级顺序；3) a recently used queue for recording the priority order of the cache data blocks;
c.哈希表，以所述高速缓存数据块的地址作为关键字，对应的高速缓存元数据为数据，构成一个数据查找表，用于确定一个高速缓存数据块是否在所述高速缓存存储器中；c. Hash table, with the address of the cache data block as a key, and the corresponding cache metadata as data, forming a data lookup table for determining whether a cache data block is in the cache memory ;
所述高速缓存服务模块依次按以下顺序实现高速缓存服务：The cache service module implements the cache service in the following order:
a.当用户访问数据时，该高速缓存服务模块首先根据其中数据给定的高速缓存数据块的地址查找哈希表；a. When the user accesses the data, the cache service module first searches the hash table according to the address of the cache data block given by the data;
b.若所述地址已在哈希表中，则高速缓存命中，通过更新用接口，调用所述当前高速缓存替换策略模块的命中功能，直接访问高速缓存，读出数据返回给用户；b. If the address is already in the hash table, the cache is hit, and the hit function of the current cache replacement strategy module is invoked through the update interface to directly access the cache, and the read data is returned to the user;
c.若地址不存在于哈希表中，则为高速缓存缺失，判断高速缓存数据块是否已全部被占用：c. If the address does not exist in the hash table, it means that the cache is missing, and it is judged whether all the cache data blocks have been occupied:
若未全部被占用，则取出一个未占用的高速缓存数据块，通过所述插入用接口，调用所述当前高速缓存替换策略模块的插入功能，把数据调入所述未占用的高速缓存数据块，If not all are occupied, then take out an unoccupied high-speed cache data block, call the insertion function of the current high-speed cache replacement strategy module through the interface for insertion, and transfer data into the unoccupied high-speed cache data block ,
若高速缓存数据块已用完，则通过替换用接口，调用所述当前高速缓存替换策略模块的替换功能，找到一个在所述高速缓存数据块中优先级最低的高速缓存数据块作被替换块，把数据读入替换出的高速缓存数据块，再返回给用户；If the cache data block has been used up, then through the replacement interface, call the replacement function of the current cache replacement policy module to find a cache data block with the lowest priority in the cache data block as the replaced block , read the data into the replaced cache data block, and return it to the user;
3)访问记录采集器模块，记录从所述高速缓存服务模块输入的访问信息，其中包括：磁盘号、访问地址和大小，先存储在内存缓冲区中，当存满时，把这些访问信息写入到磁盘文件中；3) access record collector module, records the access information imported from the high-speed cache service module, including: disk number, access address and size, which are first stored in the memory buffer, and when it is full, write these access information into a disk file;
4)访问记录分析器模块，从所述访问记录采集器模块收到已采集到设定的n条访问记录的信息后，把各访问记录依次导入各候选高速缓存替换策略模块，记录所述各候选高速缓存替换策略模块的命中次数，取命中次数最多的候选高速缓存替换策略模块为最优策略模块，把结果通知所述高速缓存服务模块；4) The access record analyzer module, after receiving the information of the set n access records collected from the access record collector module, imports each access record into each candidate high-speed cache replacement strategy module in turn, and records each access record The number of hits of the candidate cache replacement strategy module, the candidate cache replacement strategy module with the largest number of hits is the optimal strategy module, and the result is notified to the cache service module;
步骤(2).依次按以下步骤执行高速缓存替换策略的动态选择方法：Step (2). Carry out the dynamic selection method of cache replacement policy in turn according to the following steps:
步骤(2.1).初始化高速缓存服务模块：Step (2.1). Initialize the cache service module:
分配和初始化所有高速缓存数据块；Allocate and initialize all cache data blocks;
分配和初始化所有的通用高速缓存数据块描述符，所述高速缓存数据块用于记录该高速缓存数据块的地址和符号位，“通用”两字是指各高速缓存替换策略模块都需用到的；Allocate and initialize all common cache data block descriptors, the cache data block is used to record the address and sign bit of the cache data block, the word "general" means that each cache replacement strategy module needs to use of;
初始化哈希表和最近被使用队列；Initialize the hash table and recently used queue;
步骤(2.2).当前高速缓存替换策略模块的初始化：Step (2.2). Initialization of the current cache replacement policy module:
步骤(2.2.1).确定一个高速缓存替换策略模块为当前高速缓存替换策略模块：Step (2.2.1). Determine a cache replacement strategy module as the current cache replacement strategy module:
当由用户指定时，默认取上次运行结束时所用的模块；When specified by the user, defaults to the module used at the end of the last run;
当第一次运行时取最近被使用高速缓存替换策略模块；Fetch the most recently used cache replacement strategy module when running for the first time;
步骤(2.2.2).高速缓存服务模块调用所述register函数注册该当前高速缓存替换策略模块，再通过初始化接口初始化所述当前高速缓存替换策略模块；Step (2.2.2). The cache service module calls the register function to register the current cache replacement strategy module, and then initializes the current cache replacement strategy module through the initialization interface;
步骤(2.3).在用户访问数据时，高速缓存服务模块按步骤(1)所述方法插入用户访问数据为高速缓存数据块；Step (2.3). When the user accesses data, the cache service module inserts the user access data as a cache data block according to the method described in step (1);
步骤(2.4).访问记录采集器采集用户访问记录；Step (2.4). The access record collector collects user access records;
步骤(2.5).访问记录分析Step (2.5). Access record analysis
当访问记录采集器采集到所述n条访问记录后，由访问记录分析器模块通过自己设定的一个虚拟的高速缓存服务模块来记录当访问记录依次访问各候选高速缓存替换策略模块时的记录命中次数，挑选命中次数最高的候选高速缓存替换策略模块为最优策略模块；After the access record collector collects the n access records, the access record analyzer module records the records when the access records sequentially access each candidate cache replacement strategy module through a virtual cache service module set by itself Number of hits, selecting the candidate cache replacement strategy module with the highest number of hits as the optimal strategy module;
步骤(2.6).切换高速缓存替换策略模块，Step (2.6). Switch cache replacement strategy module,
首先高速缓存服务模块通过当前正处于运行状态的高速缓存替换策略模块的释放用接口释放策略元数据，所述策略元数据是指各高速缓存替换策略模块所特有的元数据；First, the cache service module releases policy metadata through the release interface of the cache replacement strategy module currently in running state, and the strategy metadata refers to the unique metadata of each cache replacement strategy module;
然后，高速缓存服务模块通过访问记录命中次数最高的那个新的高速缓存替换策略模块的初始化接口分配新的策略元数据空间；Then, the cache service module allocates a new strategy metadata space by accessing the initialization interface of the new cache replacement strategy module with the highest number of access record hits;
最后，高速缓存服务模块通过新的高速缓存替换策略模块的插入用接口把高速缓存中已有的高速缓存数据块依次导入新的高速缓存替换策略模块以重建新的策略元数据。Finally, the cache service module sequentially imports the existing cache data blocks in the cache into the new cache replacement strategy module through the insertion interface of the new cache replacement strategy module to rebuild new strategy metadata.
所述的访问记录采集次数n＝1,000,000。在执行完步骤(2.6)后，若本轮为第一轮，则返回步骤(2.4)。若本轮策略选择得出的与上一轮相同，则结束，否则，转步骤(2.4)。在执行完步骤(2.6)后，卸载高速缓存替换策略模块。The number of access record collections n=1,000,000. After step (2.6) is executed, if the current round is the first round, return to step (2.4). If the result of this round of strategy selection is the same as the previous round, then end, otherwise, go to step (2.4). After step (2.6) is executed, the cache replacement policy module is uninstalled.
本发明的优点如下：The advantages of the present invention are as follows:
(1)高速缓存服务模块通过固定接口使用高速缓存替换策略模块，可以在任意两个高速缓存替换策略模块之间进行切换，也可以部署新出现的高速缓存替换策略模块，从而可以尽快利用最新的科研成果。(1) The cache service module uses the cache replacement strategy module through a fixed interface, can switch between any two cache replacement strategy modules, and can also deploy a new cache replacement strategy module, so that the latest cache replacement strategy module can be used as soon as possible. Scientific research results.
(2)通过异步策略选择，将访问记录采集与分析过程和普通的高速缓存访问流程分离开来，减小策略选择过程带来的CPU和内存开销，从而降低高速缓存访问的平均响应时间。(2) Through asynchronous policy selection, the access record collection and analysis process is separated from the ordinary cache access process, reducing the CPU and memory overhead brought by the policy selection process, thereby reducing the average response time of cache access.
(3)通过多轮策略选择，平衡策略选择过程的时间和准确度，在保证选择准确度的前提下减少访问记录分析所需的时间，最终减小策略选择过程的开销，并尽快将结果投入使用。(3) Through multiple rounds of strategy selection, balance the time and accuracy of the strategy selection process, reduce the time required for access record analysis on the premise of ensuring the accuracy of the selection, and finally reduce the cost of the strategy selection process, and put the results into it as soon as possible use.
本发明在清华大学计算机系高性能计算技术研究所进行了测试。结果表明，高速缓存替换策略的动态选择方法可以根据负载情况选出最优的高速缓存替换策略，有效提高了高速缓存系统I/O访问的命中率，降低了平均响应时间。The present invention has been tested in the Institute of High Performance Computing Technology, Department of Computer Science, Tsinghua University. The results show that the dynamic selection method of cache replacement strategy can select the optimal cache replacement strategy according to the load conditions, which effectively improves the hit rate of cache system I/O access and reduces the average response time.
对海量数据分级存储方法的测试分成模拟测试和实际系统测试两部分，模拟测试的环境为Xeon 700MHz*4，1GB内存，我们使用了Cello，SPC-1 Websearch，SPC-1 Financial和TPCC四种trace进行了模拟，测试结果见表1，可以看出本方法可以选出命中率最高的策略。图5和图6描述了两种情况下的命中率变化情况，可以看出通过策略选择，本方法选出了最优的策略，命中率高于其他的自适应策略。The test of the mass data hierarchical storage method is divided into two parts: simulation test and actual system test. The environment of the simulation test is Xeon 700MHz*4, 1GB memory, and we use Cello, SPC-1 Websearch, SPC-1 Financial and TPCC four traces The simulation is carried out, and the test results are shown in Table 1. It can be seen that this method can select the strategy with the highest hit rate. Figure 5 and Figure 6 describe the change of the hit rate in the two cases. It can be seen that through the strategy selection, this method selects the optimal strategy, and the hit rate is higher than other adaptive strategies.
实际系统测试的环境为：一台机器作为iSCSI的目标器端，在上面架设了我们的高速缓存系统，它的配置为Xeon 2.8GHz CPU，4GB内存和6块IBM磁盘。一台机器作为iSCSI前端，安装了Windows 2000和Microsoft iSCSI Initiator。在前端使用我们开发的trace播放器播放SPC-1 Websearch和TPCC两种负载，测试结果见表2，表3和图7，图8。表2给出了Websearch负载上测到的平均响应时间，可以看出本方法的平均响应时间低于其他的自适应算法，图7给出了一种情况下的平均响应时间变化情况，可以看出通过策略选择，本方法可以降低高速缓存系统的平均响应时间。表3给出了TPCC负载上测到的平均响应时间，图8出了一种情况下的平均响应时间变化情况，可以看出类似的趋势。The actual system test environment is: a machine is used as the target of iSCSI, and our cache system is set up on it. Its configuration is Xeon 2.8GHz CPU, 4GB memory and 6 IBM disks. A machine is used as the iSCSI front end, with Windows 2000 and Microsoft iSCSI Initiator installed. Use the trace player we developed to play SPC-1 Websearch and TPCC loads on the front end. The test results are shown in Table 2, Table 3 and Figure 7, Figure 8. Table 2 shows the average response time measured on the Websearch load. It can be seen that the average response time of this method is lower than other adaptive algorithms. Figure 7 shows the change of the average response time in one case. You can see Through strategy selection, this method can reduce the average response time of the cache system. Table 3 shows the average response time measured on the TPCC load, and Figure 8 shows the change of the average response time in one case, and a similar trend can be seen.
附图说明Description of drawings
图1.整体体系结构。Figure 1. Overall architecture.
图2.接口和数据结构设计。Figure 2. Interface and data structure design.
图3.高速缓存访问基本流程。Figure 3. Basic flow of cache access.
图4.策略选择过程。Figure 4. Policy selection process.
图5.(W3，4G)下的命中率变化情况：Figure 5. Changes in hit rate under (W3, 4G):
-■-最近被使用(LRU)；- ■- Recently Used (LRU);
-★-低最近相关度(LIRS)；-★-Low nearest correlation (LIRS);
-◇-本方法。-◇-This method.
图6.(T2，256M)下的命中率变化情况：Figure 6. Changes in hit rate under (T2, 256M):
-■-最近被使用(LRU)；- ■- Recently Used (LRU);
-★-低最近相关度(LIRS)；-★-Low nearest correlation (LIRS);
-◇-本方法。-◇-This method.
图7.(W3，3G)的平均响应时间：Figure 7. Average response time for (W3, 3G):
-■-最近被使用(LRU)；- ■- Recently Used (LRU);
多队列(MQ)； Multi-queue (MQ);
-◇-本方法；-◇-this method;
图8.(T1，512M)的平均响应时间：Figure 8. Average response time for (T1, 512M):
-■-最近被使用(LRU)；- ■- Recently Used (LRU);
-◇-本方法；-◇-this method;
具体实施方式Detailed ways
本发明可以在由任意高速和低速存储设备组成的二级存储体系结构中实现。高速存储设备一般为内存，或者固态磁盘，具有速度快，价格高，容量小，断电易失的特点。根据数据访问局部性的原则，它们缓存最近访问的数据，从而提高整个系统的性能。低速存储设备一般为普通磁盘，具有速度慢，价格低，容量大，非易失的特点。它们存储了所有的数据。The present invention can be implemented in a secondary storage architecture composed of arbitrary high-speed and low-speed storage devices. High-speed storage devices are generally memory or solid-state disks, which have the characteristics of high speed, high price, small capacity, and volatile when power off. According to the principle of locality of data access, they cache the most recently accessed data, thereby improving the performance of the overall system. Low-speed storage devices are generally ordinary disks, which have the characteristics of slow speed, low price, large capacity, and non-volatile. They store all data.
高速缓存替换策略的动态选择方法主要由高速缓存服务模块，高速缓存替换策略模块，访问记录采集模块和访问记录分析模块组成。本方法的体系结构如图1所示。The dynamic selection method of the cache replacement strategy is mainly composed of a cache service module, a cache replacement strategy module, an access record collection module and an access record analysis module. The architecture of this method is shown in Figure 1.
模块(1).高速缓存替换策略模块Module (1). Cache Replacement Policy Module
高速缓存替换策略模块描述了高速缓存系统命中和替换时的逻辑。高速缓存服务模块通过一统一接口访问高速缓存替换策略模块的逻辑功能。高速缓存替换策略模块的接口和数据结构设计如图2所示。高速缓存替换策略模块有一固定入口函数register，它通过该函数把自己的接口实现注册给高速缓存服务模块。The cache replacement policy module describes the logic for cache system hit and replacement. The cache service module accesses the logical functions of the cache replacement policy module through a unified interface. The interface and data structure design of the cache replacement policy module are shown in Figure 2. The cache replacement strategy module has a fixed entry function register, through which it registers its own interface implementation with the cache service module.
它提供了五种功能供高速缓存服务模块使用It provides five functions for use by the cache service module
1)初始化，当高速缓存系统初始化时此功能被调用；1) Initialization, this function is called when the cache system is initialized;
2)卸载，当高速缓存模块卸载时此功能被调用；2) unload, this function is called when the cache module is unloaded;
3)高速缓存数据块插入，当新的高速缓存数据块加入时此功能被调用；3) cache data block insertion, this function is called when a new cache data block is added;
4)高速缓存数据块命中，当高速缓存数据块命中时此功能被调用；4) The cache data block hits, and this function is called when the cache data block hits;
5)高速缓存数据块替换，当新的高速缓存数据块替换旧的高速缓存数据块的时候此功能被调用。5) Cache data block replacement, this function is called when a new cache data block replaces an old cache data block.
用来管理高速缓存的数据称为高速缓存元数据，包括高速缓存数据块描述符用来记录数据块对应的地址和符号位；哈希表用来记录一个数据块是否在高速缓存中；最近被使用队列用来表示数据块的优先级顺序。本方法将高速缓存数据块描述符分为通用高速缓存数据块描述符和策略高速缓存数据块描述符，分别组合成通用元数据和策略元数据。通用元数据指基本所有策略都要用到的元数据，而策略元数据指各策略特有的元数据。通用元数据由高速缓存服务模块分配和维护，而策略元数据由高速缓存替换策略模块自行维护和使用。The data used to manage the cache is called cache metadata, including the cache data block descriptor used to record the address and sign bit corresponding to the data block; the hash table is used to record whether a data block is in the cache; Queues are used to indicate the priority order of data blocks. In the method, cache data block descriptors are divided into general cache data block descriptors and policy cache data block descriptors, which are combined into general metadata and policy metadata respectively. Common metadata refers to metadata that is used by almost all policies, and policy metadata refers to metadata specific to each policy. Common metadata is allocated and maintained by the cache service module, while policy metadata is maintained and used by the cache replacement policy module itself.
本方法实现了最近被使用(LRU)，双队列(2Q)，低最近相关度(LIRS)，自适应低负载(ARC)和多队列(MQ)五种高速缓存替换策略模块，其中处于运行状态的为当前高速缓存替换策略模块，其他的为候选高速缓存替换策略模块，本方法可以将一个候选高速缓存替换策略模块动态切换成当前高速缓存替换策略模块，This method implements the recently used (LRU), dual queue (2Q), low recent correlation (LIRS), adaptive low load (ARC) and multi-queue (MQ) five cache replacement strategy modules, which are in the running state is the current cache replacement strategy module, and the others are candidate cache replacement strategy modules. This method can dynamically switch a candidate cache replacement strategy module to the current cache replacement strategy module.
策略切换的过程如下：首先高速缓存服务模块调用旧高速缓存替换策略的卸载函数释放策略元数据，然后高速缓存服务模块调用新高速缓存替换策略的初始化函数分配新的策略元数据，最后高速缓存服务模块调用新高速缓存替换策略的插入函数将高速缓存中已有的数据块依次导入新的高速缓存替换策略模块并建立策略元数据。The process of policy switching is as follows: first, the cache service module calls the unload function of the old cache replacement policy to release policy metadata, then the cache service module calls the initialization function of the new cache replacement policy to allocate new policy metadata, and finally the cache service module The module calls the insertion function of the new cache replacement strategy to import the existing data blocks in the cache into the new cache replacement strategy module in turn and establishes the strategy metadata.
模块(2).高速缓存服务模块Module (2). Cache service module
高速缓存服务模块为用户提供高速缓存服务，它将磁盘等低速设备的数据缓存在内存中，当数据再次访问时就直接进行内存访问，从而大大提高访问速度。高速缓存服务模块利用当前高速缓存替换策略模块的高速缓存数据块替换功能确定哪些数据块可以被放置在高速缓存中。高速缓存服务模块可以根据访问记录分析器模块的分析结果在候选高速缓存替换策略模块中选择命中率最高的高速缓存替换策略模切换为当前高速缓存替换策略模块。高速缓存服务模块主要有以下组成部分和逻辑：The high-speed cache service module provides users with high-speed cache services. It caches the data of low-speed devices such as disks in the memory, and directly performs memory access when the data is accessed again, thereby greatly improving the access speed. The cache service module utilizes the cache data block replacement function of the current cache replacement policy module to determine which data blocks can be placed in the cache. The cache service module may select the cache replacement strategy module with the highest hit rate among the candidate cache replacement strategy modules according to the analysis result of the access record analyzer module and switch to the current cache replacement strategy module. The cache service module mainly has the following components and logic:
高速缓存数据：缓存的磁盘数据，被分成多个固定大小的高速缓存数据块。块的大小可以由用户指定，默认为4KB。Cache Data: Cached disk data, divided into fixed-size cache data blocks. The block size can be specified by the user and defaults to 4KB.
高速缓存元数据：用于维护和管理高速缓存的数据，包括每个高速缓存数据块的物理地址，每个高速缓存数据块的符号位标志该块是否已被写入磁盘，一个最近被使用队列用于记录高速缓存数据块的优先级。Cache metadata: data used to maintain and manage the cache, including the physical address of each cache data block, the sign bit of each cache data block to indicate whether the block has been written to disk, a recently used queue Used to record the priority of cache data blocks.
哈希表：用高速缓存数据块的地址作为关键字，对应的高速缓存元数据作为数据的数据查找表，用于确定一个数据块是否在高速缓存中。Hash table: The address of the cache data block is used as a key, and the corresponding cache metadata is used as a data lookup table for determining whether a data block is in the cache.
高速缓存服务模块的基本流程如图3所示，当应用访问数据时，首先通过访问地址检查对应的数据块是否已经在高速缓存中，如果是的话为高速缓存命中，直接从高速缓存中访问即可，如果不是的话为高速缓存缺失，这时检查是否还有空余的高速缓存数据块，如果有的话直接将被访问的块读入该高速缓存数据块，如果没有的话从高速缓存的所有数据块中选出一被替换块，然后将被访问的块读入该替换块，这时再从高速缓存中访问数据块。The basic process of the cache service module is shown in Figure 3. When an application accesses data, it first checks whether the corresponding data block is already in the cache through the access address. Yes, if not, the cache is missing. At this time, check whether there are free cache data blocks. If so, directly read the accessed block into the cache data block. If not, read all the data from the cache. Select a block to be replaced from the block, then read the accessed block into the replacement block, and then access the data block from the cache.
模块(3).访问记录采集器模块Module (3). Access record collector module
当用户访问高速缓存服务模块时，访问记录采集器模块记录这次访问的信息，包括磁盘号，访问地址和大小。访问记录采集器模块首先将这些信息记录在内存缓冲区中，当缓冲区满时，将这些信息写入到磁盘文件中。When a user accesses the cache service module, the access record collector module records the information of this access, including disk number, access address and size. The access record collector module first records the information in the memory buffer, and when the buffer is full, writes the information into the disk file.
模块(4).访问记录分析器模块Module (4). Access record analyzer module
当访问记录采集器模块采集到1,000,000条记录后，访问记录分析器模块即开始工作，整个过程如图4所示。访问记录分析器模块首先建立一虚拟的高速缓存服务模块，它除了不存高速缓存数据外，其他都同高速缓存服务模块相同。接着访问记录分析器模块为虚拟高速缓存服务模块指定一高速缓存策略模块，然后根据访问记录依次访问虚拟高速缓存服务模块，记录命中次数。通过对所有候选高速缓存策略模块重复上述过程，访问记录分析器模块可以得到所有候选高速缓存策略模块的命中次数，挑选命中次数最高的策略为最优策略并进行策略切换。如果本次挑选出的策略和上一轮相同，则策略选择过程结束，否则访问记录采集器再采集1,000,000条访问记录，再由访问记录分析器模块进行分析。这样的多轮策略选择过程既可以保证分析的准确性，也可以避免过多的访问记录采集和分析过程。When the access record collector module collects 1,000,000 records, the access record analyzer module starts to work, and the whole process is shown in Figure 4. The access record analyzer module first establishes a virtual high-speed cache service module, which is the same as the high-speed cache service module except that it does not store cache data. Then the access record analyzer module designates a cache policy module for the virtual cache service module, and then accesses the virtual cache service module sequentially according to the access records, and records the number of hits. By repeating the above process for all candidate cache policy modules, the access record analyzer module can obtain the hit times of all candidate cache policy modules, select the policy with the highest hit times as the optimal policy, and switch the policy. If the policy selected this time is the same as the previous round, the policy selection process ends, otherwise, the access record collector will collect another 1,000,000 access records, and then the access record analyzer module will analyze them. Such a multi-round policy selection process can not only ensure the accuracy of the analysis, but also avoid excessive collection and analysis of access records.
当多轮策略选择结束后，高速缓存系统进入正常运行阶段，该阶段没有访问记录采集和分析的过程，几乎没有附加的CPU和内存开销。访问记录分析的时间Ta，访问记录采集的时间Tc和正常运行阶段的时间Tr有如下关系：Ta＜＜Tc＜＜Tr，这说明正常运行阶段占了大部分时间，保证了整个系统的CPU和内存开销比较小。After multiple rounds of strategy selection, the cache system enters the normal operation stage, in which there is no process of access record collection and analysis, and there is almost no additional CPU and memory overhead. The time Ta of access record analysis, the time Tc of access record collection, and the time Tr of the normal operation phase have the following relationship: Ta << Tc << Tr , which means that the normal operation phase accounts for most of the time, ensuring The CPU and memory overhead of the entire system is relatively small.
所述的高速缓存替换策略的动态选择方法依次含有以下步骤：The dynamic selection method of the cache replacement strategy contains the following steps in turn:
步骤1：高速缓存服务模块初始化Step 1: Cache service module initialization
高速缓存服务模块的初始化包括：The initialization of the cache service module includes:
1)分配和初始化所有高速缓存数据块；1) Allocate and initialize all cache data blocks;
2)分配和初始化所有的通用高速缓存数据块描述符；2) allocate and initialize all common cache data block descriptors;
3)初始化哈希表3) Initialize the hash table
4)初始化最近被使用队列4) Initialize the recently used queue
步骤2：当前高速缓存替换策略模块初始化Step 2: Current cache replacement policy module initialization
高速缓存服务模块首先确定一高速缓存替换策略模块为当前策略模块，这可以由用户指定，默认取上次运行结束时使用的模块，如果第一次运行的话取最近被使用策略模块。然后高速缓存服务模块调用高速缓存替换策略模块的register函数注册该模块，最后调用该策略模块的初始化接口函数初始化该策略模块。The cache service module first determines a cache replacement strategy module as the current strategy module, which can be specified by the user, and defaults to the module used at the end of the last run, and if it is run for the first time, it takes the most recently used strategy module. Then the cache service module calls the register function of the cache replacement strategy module to register the module, and finally calls the initialization interface function of the strategy module to initialize the strategy module.
步骤3：应用访问Step 3: App Access
高速缓存服务模块首先检查哈希表，如果对应数据块的地址已经在高速缓存中，则直接访问高速缓存。如果不在高速缓存中，检查高速缓存是否已满，如果未满则直接将其调入高速缓存并访问，如果已满则先选出被替换块，然后将被访问块调入并访问。The cache service module first checks the hash table, and if the address of the corresponding data block is already in the cache, it directly accesses the cache. If it is not in the cache, check whether the cache is full, if it is not full, directly transfer it into the cache and access it, if it is full, first select the block to be replaced, and then transfer the block to be accessed and access it.
步骤4：访问记录采集Step 4: Access Record Collection
访问记录采集模块记录应用访问的信息，包括访问的盘号，起始地址和大小。访问记录采集模块首先将信息记录在内存缓冲区中，当内存缓冲区满的时候再将其写入磁盘文件。The access record collection module records the information accessed by the application, including the accessed disk number, starting address and size. The access record acquisition module first records the information in the memory buffer, and then writes it to the disk file when the memory buffer is full.
步骤5：访问记录分析Step 5: Access Record Analysis
当访问记录采集器模块采集到1,000,000条记录后，访问记录分析器模块首先建立一虚拟高速缓存服务模块。接着访问记录分析器模块为虚拟高速缓存服务模块指定一高速缓存策略模块，然后根据访问记录依次访问虚拟高速缓存服务模块，记录命中次数。通过对所有候选高速缓存策略模块重复上述过程，访问记录分析器模块可以得到所有候选高速缓存策略模块的命中次数，挑选命中次数最高的策略为最优策略。After the access record collector module collects 1,000,000 records, the access record analyzer module first establishes a virtual cache service module. Then the access record analyzer module designates a cache policy module for the virtual cache service module, and then accesses the virtual cache service module sequentially according to the access records, and records the number of hits. By repeating the above process for all candidate cache policy modules, the access record analyzer module can obtain the hit times of all candidate cache policy modules, and select the policy with the highest hit times as the optimal policy.
步骤6：策略切换Step 6: Policy Switching
高速缓存服务模块调用卸载接口函数释放旧的策略模块，然后调用最优策略模块的register和初始化接口函数，最后将高速缓存中已有的数据块通过插入接口函数导入新的高速缓存替换策略模块，完成切换过程。The cache service module calls the unloading interface function to release the old strategy module, then calls the register and initialization interface functions of the optimal strategy module, and finally imports the existing data blocks in the cache into the new cache replacement strategy module through the insertion interface function, Complete the switching process.
步骤7：多轮策略选择Step 7: Multiple rounds of strategy selection
如果本轮策略选择得到的最优策略同上一轮相同，则结束，否则跳转步骤4，进行下一轮访问记录采集和分析。如果本轮就是第一轮的话一定跳转步骤4。If the optimal strategy obtained in this round of strategy selection is the same as the previous round, then end, otherwise skip to step 4 to collect and analyze the next round of access records. If this round is the first round, skip to step 4.
步骤8：策略选择重启Step 8: Policy selection restart
当高速缓存服务模块发现策略的命中率显著下降时，重新启动策略选择过程，即重新进行步骤4-7。When the cache service module finds that the hit ratio of the strategy drops significantly, it restarts the strategy selection process, that is, repeats steps 4-7.
步骤9：高速缓存服务模块卸载Step 9: Cache service module uninstallation
1)将所有未写入磁盘的数据块写入磁盘1) Write all data blocks not written to disk to disk
2)释放策略模块，释放其内存和数据结构2) Release the policy module, release its memory and data structure
3)释放所有的通用元数据，包括通用高速缓存数据块描述符，哈希表和最近被使用队列3) Release all general metadata, including general cache data block descriptors, hash tables and recently used queues
4)释放所有的高速缓存数据块4) Release all cache data blocks
表1各种策略和负载下的命中率情况Table 1 Hit ratio under various strategies and loads
表2Websearch负载上的平均响应时间(毫秒)Table 2 Average response time (ms) on Websearch load
表3TPCC负载上的平均响应时间(毫秒)Table 3 Average response time on TPCC load (ms)
Claims (5)
Translated fromChinesePriority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2008100571727ACN101236530B (en) | 2008-01-30 | 2008-01-30 | High speed cache replacement policy dynamic selection method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2008100571727ACN101236530B (en) | 2008-01-30 | 2008-01-30 | High speed cache replacement policy dynamic selection method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101236530A CN101236530A (en) | 2008-08-06 |
| CN101236530Btrue CN101236530B (en) | 2010-09-01 |
Family
ID=39920160
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2008100571727AExpired - Fee RelatedCN101236530B (en) | 2008-01-30 | 2008-01-30 | High speed cache replacement policy dynamic selection method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101236530B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11010295B2 (en) | 2017-09-05 | 2021-05-18 | International Business Machines Corporation | Asynchronous update of metadata tracks in response to a cache hit generated via an i/o operation over a bus interface |
Families Citing this family (39)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7490197B2 (en) | 2004-10-21 | 2009-02-10 | Microsoft Corporation | Using external memory devices to improve system performance |
| US9032151B2 (en) | 2008-09-15 | 2015-05-12 | Microsoft Technology Licensing, Llc | Method and system for ensuring reliability of cache data and metadata subsequent to a reboot |
| US7953774B2 (en) | 2008-09-19 | 2011-05-31 | Microsoft Corporation | Aggregation of write traffic to a data store |
| CN101478472B (en)* | 2008-10-21 | 2011-09-07 | 北京闪联讯通数码科技有限公司 | Socket data transmission processing method and apparatus |
| KR101023877B1 (en)* | 2009-04-17 | 2011-03-22 | (주)인디링스 | Cache and Disk Management Method and Controller Using the Method |
| CN101556557B (en)* | 2009-05-14 | 2011-03-23 | 浙江大学 | Object file organization method based on object storage device |
| CN101866321B (en)* | 2010-06-13 | 2012-03-21 | 北京北大众志微系统科技有限责任公司 | Adjustment method and system for cache management strategy |
| CN101916302B (en)* | 2010-09-01 | 2012-11-21 | 中国地质大学（武汉） | Three-dimensional spatial data adaptive cache management method and system based on Hash table |
| CN102137139A (en)* | 2010-09-26 | 2011-07-27 | 华为技术有限公司 | Method and device for selecting cache replacement strategy, proxy server and system |
| US8504774B2 (en)* | 2010-10-13 | 2013-08-06 | Microsoft Corporation | Dynamic cache configuration using separate read and write caches |
| US8839275B1 (en) | 2011-06-06 | 2014-09-16 | Proximal Data, Inc. | Method for intercepting input/output requests and responses |
| CN103207838B (en)* | 2012-01-17 | 2016-03-30 | 展讯通信（上海）有限公司 | Improve the method for chip performance |
| US9104552B1 (en) | 2012-06-23 | 2015-08-11 | Samsung Electronics Co., Ltd. | Method for the use of shadow ghost lists to prevent excessive wear on FLASH based cache devices |
| WO2014094306A1 (en)* | 2012-12-21 | 2014-06-26 | 华为技术有限公司 | Method and device for setting working mode of cache |
| WO2014120215A1 (en)* | 2013-01-31 | 2014-08-07 | Hewlett-Packard Development Company, L.P. | Adaptive granularity row-buffer cache |
| CN104104710B (en)* | 2013-04-15 | 2017-05-24 | 同济大学 | Low energy consumption-based data cache method in mobile cloud computing environment |
| CN104598394A (en)* | 2013-10-31 | 2015-05-06 | 中国石油天然气集团公司 | Data caching method and system capable of conducting dynamic distribution |
| US20150286571A1 (en)* | 2014-04-04 | 2015-10-08 | Qualcomm Incorporated | Adaptive cache prefetching based on competing dedicated prefetch policies in dedicated cache sets to reduce cache pollution |
| CN105094686B (en) | 2014-05-09 | 2018-04-10 | 华为技术有限公司 | Data cache method, caching and computer system |
| CN104077241B (en)* | 2014-07-14 | 2017-10-17 | 华为技术有限公司 | Cache life cycle algorithm switching handling method and device |
| CN104572502B (en)* | 2015-01-12 | 2018-06-19 | 浪潮电子信息产业股份有限公司 | Self-adaptive method for cache strategy of storage system |
| CN104731980A (en)* | 2015-04-17 | 2015-06-24 | 吉林大学 | Method and device for management of cache pages |
| CN105095354A (en)* | 2015-06-19 | 2015-11-25 | 北京奇虎科技有限公司 | Data updating method and data updating device |
| CN105512051B (en)* | 2015-12-16 | 2019-03-12 | 鸿秦（北京）科技有限公司 | A kind of self learning type intelligent solid-state hard disk cache management method and device |
| CN105740167B (en)* | 2016-01-28 | 2018-12-07 | 浪潮(北京)电子信息产业有限公司 | A kind of method and system that file system cache is deleted |
| CN108073527B (en)* | 2016-11-07 | 2020-02-14 | 华为技术有限公司 | Cache replacement method and equipment |
| US10430706B2 (en)* | 2016-12-01 | 2019-10-01 | Via Alliance Semiconductor Co., Ltd. | Processor with memory array operable as either last level cache slice or neural network unit memory |
| CN106649041A (en)* | 2016-12-27 | 2017-05-10 | 郑州云海信息技术有限公司 | Device and method for automatically testing storage caching mode |
| CN110249318A (en)* | 2017-02-07 | 2019-09-17 | 华为技术有限公司 | Cache replacement system and method |
| CN106873917A (en)* | 2017-02-24 | 2017-06-20 | 深圳市中博睿存信息技术有限公司 | A kind of object storage system based on disk |
| CN107220188B (en)* | 2017-05-31 | 2020-10-27 | 中山大学 | Self-adaptive buffer block replacement method |
| CN109656832A (en)* | 2017-10-11 | 2019-04-19 | 深圳市中兴微电子技术有限公司 | A kind of look-up method, computer readable storage medium |
| CN109298972B (en)* | 2018-09-06 | 2019-11-15 | 高盈量化云科技（深圳）有限公司 | A kind of High Availabitity policy engine |
| CN109669882B (en)* | 2018-12-28 | 2021-03-09 | 贵州华芯通半导体技术有限公司 | Bandwidth-aware dynamic cache replacement method, apparatus, system, and medium |
| CN110032528A (en)* | 2019-04-19 | 2019-07-19 | 苏州浪潮智能科技有限公司 | Internal storage data lookup method, device, equipment and the storage medium of storage system |
| US11023150B2 (en)* | 2019-07-01 | 2021-06-01 | International Business Machines Corporation | Block mode toggling using hybrid controllers |
| CN110992671B (en)* | 2019-12-16 | 2020-11-20 | 宁波三星医疗电气股份有限公司 | Ammeter address forwarding method, device and system and electronic equipment |
| CN113342706A (en)* | 2021-05-13 | 2021-09-03 | 武汉大学 | Write-optimized extensible hash index structure based on nonvolatile memory and inserting, refreshing and deleting methods |
| US11886342B2 (en) | 2021-12-01 | 2024-01-30 | International Business Machines Corporation | Augmenting cache replacement operations |
- 2008
- 2008-01-30CNCN2008100571727Apatent/CN101236530B/ennot_activeExpired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11010295B2 (en) | 2017-09-05 | 2021-05-18 | International Business Machines Corporation | Asynchronous update of metadata tracks in response to a cache hit generated via an i/o operation over a bus interface |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101236530A (en) | 2008-08-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101236530B (en) | High speed cache replacement policy dynamic selection method | |
| US8595463B2 (en) | Memory architecture with policy based data storage | |
| US8200949B1 (en) | Policy based allocation of register file cache to threads in multi-threaded processor | |
| JP5379358B2 (en) | Multi-level memory architecture with data prioritization | |
| CN101292228B (en) | Lock indicator for conversion lookaside buffer | |
| US8990505B1 (en) | Cache memory bank selection | |
| US20110252215A1 (en) | Computer memory with dynamic cell density | |
| Basu et al. | Scavenger: A new last level cache architecture with global block priority | |
| CN103019955B (en) | The EMS memory management process of PCR-based AM main memory application | |
| CN104166634A (en) | Management method of mapping table caches in solid-state disk system | |
| JP5328792B2 (en) | Second chance replacement mechanism for highly responsive processor cache memory | |
| CN110795363B (en) | Hot page prediction method and paging method for storage medium | |
| CN103678169A (en) | Method and system for efficiently utilizing solid-state disk for caching | |
| US8583890B2 (en) | Disposition instructions for extended access commands | |
| Quan et al. | Prediction table based management policy for STT-RAM and SRAM hybrid cache | |
| Xu et al. | Frequent access pattern-based prefetching inside of solid-state drives | |
| Zhang et al. | Write-back aware shared last-level cache management for hybrid main memory | |
| Jung et al. | Fass: A flash-aware swap system | |
| CN117312188A (en) | Hybrid SSD data cache prefetch system and method | |
| Wang et al. | Leaderkv: Improving read performance of kv stores via learned index and decoupled kv table | |
| Salkhordeh et al. | An efficient hybrid I/O caching architecture using heterogeneous SSDs | |
| CN108537719B (en) | A system and method for improving the performance of a general-purpose graphics processor | |
| CN114911724A (en) | Access structure of multi-bank-based cache prefetching technology | |
| US20040078544A1 (en) | Memory address remapping method | |
| CN100380347C (en) | Semiconductor device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee | Granted publication date:20100901 Termination date:20170130 |