DS8000/DS6000的高速缓存(Cache)管理-SARC算法

绝大多数厂商在设计高端系统的高速缓存(Cache)系统时，其高速缓存的大小一般是引人注目的。但是，事实上，这些系统中，磁盘容量与高速缓存大小的比率一直保持几乎相同。

　　DS8000/DS6000使用由IBM 研究开发部门研发并拥有专利的SARC (Sequential Prefetching in Adaptive Replacement)高速缓存算法。该算法可以自动调节、自动优化，解决各种顺序和随机I/O流的负载。事实上，SARC从经典的ARC (Adaptive Replacement，对于ARC详细的说明请参阅N. Megiddo 和 D. S. Modha的，“Outperforming LRU with an adaptive replacement Cache algorithm,” IEEE Computer, vol. 37, no. 4, pp. 58–65, 2004. ) 高速缓存算法中得到灵感，并从中继承了很多优点。SARC算法基本上关注4个问题：

　　什么时候数据拷贝复制到高速缓存?

　　哪些数据拷贝复制到高速缓存?

　　当高速缓存充满后，哪些数据被清除?

　　算法怎么动态去适应不同的负载?

　　与其它厂商相比，DS8000/DS6000的高速缓存按照每单元4K字节(4k bite/pages，page也可称为cache page或slot的)组织起来。这种较小的单元分配，与用其它数值的相比，可以保证较小的I/O不会浪费高速缓存。事实上，绝大多数商业数据库的相关I/O均是 较小的。

　　拷贝到DS8000/DS6000 高速缓存中一些数据的结果能够触发两个动作：

　　请求页面调度paging;

　　预取Prefetching。 请求页面调度Demand paging 意味着8个磁盘块disk blocks(一个4K的高速缓存页)的一次高速缓存查找完成。页面调度对所有的卷都是有效的，保证在高速缓存中能够找到最近被使用的I/O。

　　预取Prefetching则意味着，数据在被请求之前就已经“投机的“被拷贝到高速缓存中。对预取，是一个对未来需要访问的数据的预测。因为有效的成熟的预取计划需要大量的page访问历史(事实上，在现实环境中，往往是不可行的)。SARC对顺序I/O负载上使用预取功能。顺序访问模式大多出现在音、视频、数据库检索、拷贝、以及恢复领域。顺序预取的目标是及时发现顺序I/O访问并有效的提前将数据装入高速缓存，以减少高速缓存不能命中的情况。

　　对于预取，高速缓存管理采用一种跟踪机制(track)。一个track通常是128个磁盘块disk blocks(16个 高速缓存的page)。当发现一个顺序访问模式后，计数器保持纪录所有正在被访问的track以及它的前身。只有当计数器确认一个连续访问模式时，顺序预取功能才激活。通过这种方法，DS8000/DS6000可以监视出应用程序读I/O的模式，并动态的确定使用高速缓存的最佳时机：

　　恰当的pages被请求

　　请求的page加上剩余的数据在磁盘track上

　　一个全部的disk track(或一组disk track)之前没有被请求

　　事实上，决定在什么时候和什么数据被预取，应以每一个应用为基础，而不是整个系统。该算法可敏感的区分同时正在运行的不同应用的不同数据参考模型。

　　顺序和随机(非顺序)数据被分开为2个列表(参看图1)。当高速缓存充满的时候，算法来决定哪些page被清除出去。当一个随机的I/O page装载到高速缓存中，作为最近常用数据，内存分页将其添加到随机列表(RANDOM List) 顶部的MRU区域(Most Recently Used)。未来没有更多I/O访问下，它下降到RANDOM List底部的LRU区域( Least Recently Used)。而一个顺序访问的page装载到高速缓存中，通过顺序预取添加到顺序列表SEQ list的MRU顶部接着进入。另外通过规则控制这个page在两个列表的之间的迁移，因此相同的page不会出现两次。

　　

　　图1 SARC算法对于随机和顺序数据的高速缓存列表

　　跟随负载压力的变化，算法交易高速缓存空间在随机(random)和顺序(seq)之间动态自适应的改变。这使得SARC可以抵抗无休止的扫描，所以，一次性的顺序请求不会“污染”整个高速缓存。SARC为顺序列表还保持一个期望的大小。这个期望将根据I/O负载进行不断的变化，用以修改两个列表的大小。例如，如果SEQ list底部(LRU)的部分被发现比RANDOM 底部(LRU)的部分更加有价值，期望的大小将增加;反之，期望的大小将减小。

　　此外，SARC算法动态更改不仅是两个列表的大小，而且可决定这种大小改变的速度 - 用一个比率来体现。在稳定的状态下，根据高速缓存的丢失率( miss rate)，“无用”的pages被不断驱逐出高速缓存。大的丢失率( miss rate)加快驱逐“无用”的pages，而小的丢失率( miss rate)将延缓这种“动作”。

　　这样，与其它存储系统相比，DS8000/DS6000在高速缓存大小有限的条件下，充分利用了有限的高速缓存空间，提供了更大的吞吐能力,使系统获得更快的响应时间。