DS8000/DS6000的高速缓存（Cache）管理－SARC算法

点奈特

     在IBM官方网站找到了DS6000 cache的管理机制文章，以前看到数据库内存的管理机制往往都是按LRU的策略来管理的，而DS6000存储的cache将随机与顺序I/O访问分别实现管理，这样从应用角度考虑确实是个好的方法。以下是从官网上转载来的内容。
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在高速缓存大小有限的条件下，充分利用了有限的高速缓存空间，提供了更大的吞吐能力,使系统获得更快的响应时间。


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/99967/showart_1998200.html