科创中国

电子信息技术

本发明公开了一种用于数据恢复的缓存替换方法，包括：数据备份步骤：在数据备份过程中，按照数据块的备份顺序记录各数据块所属容器的ID，得到该数据备份的容器访问顺序；哈希表生成步骤：根据数据备份的容器访问顺序信息，建立哈希表，其中：哈希表使用容器ID作为键，相同容器ID被映射到一起，并按访问时间排序组成队列；数据恢复步骤：在数据块进行恢复时，根据恢复缓存中的容器恢复数据块，所述恢复缓存中存储有根据所述哈希表确定的最近将被访问到的N个容器，所述N为所述恢复缓存中能够存储容器的个数。本发明还提供了相应的缓存替换系统。本发明方法最优缓存替换策略的缓存命中率更高，减少了读取容器的次数，增加了恢复性能。

数据去重的这种存储方式导致了数据碎片的产生，即一次备份的数据块被离散地分布在磁盘上。例如，重复的数据块存放在旧容器内，新容器只有新的数据块(这些新数据块可能在数据流上的距离很远)。当恢复一次备份数据时，需要按顺序依次恢复数据块，当需要的数据块在某个容器中时，就将整个容器预取到恢复缓存中来。恢复缓存通常使用最近最少访问替换算法(LRU)。由于新容器中的数据块并不是按顺序访问，因此需要频繁地交替访问新旧容器，对一个容器的多次访问(读取其中的数据块)可能相隔很长时间，这就为恢复缓存替换方法提出了挑战。传统的LRU并不是最有效的,较低的恢复缓存命中率导致恢复性能下降。与LRU不同的是，最优恢复缓存替换方法是根据未来的访问信息，替换掉未来最久不会被访问的元素。然而，由于最优恢复缓存替换方法需要知道未来数据的访问模式，导致难以实现。

冯丹，1970年5月生，湖北京山人，华中科技大学计算机学院院长，教授，博士生导师。信息存储系统教育部重点实验室副主任，武汉光电国家实验室（筹），兼任中国计算机学会外部设备专业委员会委员，中国计算机学会信息存储技术专业委员会委员，中国电子工业标准化技术协会海量存储标准工作委员会副主任委员武汉市科学技术协会常委，武汉市政协委员，第十三届全国人大代表。