多用户存储中自适应动态预取策略*

唐丽梅，邢素霞，陈天华

(北京工商大学 计算机与信息工程学院，北京 100048)

预取Cache技术是解决Cache失效开销的关键技术。由于多用户产生的海量数据访问往往耗时巨大，因此有必要根据多用户存储请求结构设计特定的Cache预取优化机制。通常采用的优化策略可以分为两类：

(1)二级 Cache结构预取[1]。该策略根据 Cache结构设计，通过减小Cache访问的延迟，提高二级Cache命中率[2]；适应面广，可以应用在储存优化系统中,但是对于多用户海量随机访问，预取效率很难有所提高。

(2)自适应预取策略[3]。该策略考虑了预取的盲目性问题，通过调整预取长度提高预取效率。但是自适应预取只是在连续数据请求的情况下有效，在用户请求地址完全不连续的情况下，预取数据基本失效。由于自适应预取算法将多用户数据请求当成随机数据请求，基本上不预取数据，因此预取性能受到限制。

通过构建一个智能动态预取策略的优化系统对多用户访问服务系统进行优化。其中预取的数据是优化系统能否发挥作用的一个重要因素。因此选择动态调整Cache大小和调整预取长度相结合的方式。实现了多用户数据存储设备通过网络为所有工作站的共享。

1 相关工作

[1]通过分析Cache失效行为特性,设计了一种步长自适应的二级Cache预取机制，该预取机制动态调整预测访存模式及预测量。文中所选算法基于自适应算法，该算法仅对用户数据保存在某一磁盘的连续地址有效,对多用户访问的非连续地址访问对象预取失效。虽然多用户的数据请求之间的逻辑存储地址信息是不连续的，但对于每个用户的数据请求的逻辑存储地址的分布是连续的，可以把这种数据请求当作不完全的随机请求，而且是有一定跨度的有规律请求，因此可以通过分解多用户数据来获得若干个顺序数据请求。再利用自适应方式调整Cache,从而产生本文的多用户Cache自适应动态预取算法。

引入Cache结构之后，CPU的访存时间由Cache命中时间、Cache失效率[4]、Cache失效开销这三个因素共同决定，其决定关系如下：

Cache访存时间=Cache命中时间+Cache失效率×Cache失效开销

本文的主要设计工作包括：

(1)分析多用户请求信息特性，设计一种识别不同用户数据、调度相应Cache的预取机制。

(2)分析多用户请求的Cache失效开销，调整阈值参数，实时统计命中率。通过分析多用户请求系统Cache开销函数，选择合适的Cache结构参数，最大可能地提高 Cache性能[5]。

2 多用户Cache自适应动态预取机制

2.1 识别多用户数据请求

多用户通过网络服务器系统对存放在磁盘阵列中的数据发出请求，此时的数据请求序列特点是有规律的随机数据请求,每个用户的数据请求逻辑存储地址的分布是连续的[3]。针对多用户，引入每个用户的唯一标识ID,由此产生分布式访问各磁盘组的请求序列。磁盘阵列控制器在接收到主机发送过来的、包含逻辑地址数据信息的多个用户读请求命令后，将该命令进行预命令分解，并生成各物理盘的磁盘读请求子命令。子命令信息包括逻辑首地址、数据长度、用户ID号及访问次数。只要将请求的逻辑首地址和数据长度与Cache组中记录的值相比较，就可以快速查找出当前请求的数据是否在Cache组中。多用户访问预取的整个流程如图1所示。

2.2 工作流程

磁盘阵列包括N个磁盘Cache组,每个磁盘Cache组中有M个Cache区。Cache区数目则是根据磁盘阵列接收顺序请求的数目和预取阈值H确定。本算法将每个顺序请求定位调度给Cache组中相应的Cache区间。图2中A、B、C缓存区间分别代表调度给 A、B、C三个用户的请求序列的Cache区间，这三个顺序请求序列交错组成一个磁盘组随机请求序列。

在多用户查询Cache组过程中，无论是否命中Cache区间，都要对Cache进行更新。Cache区间的具体更新过程如下：

(1)若命中预取区间，则将命中项计数器Count值加1。然后将新命中数据块放入Cache区地址单元的头部。

(2)若没有命中Cache组中的任何一个有效项,则所有有效项的Count计数值减1，同时在预取Cache组中分配一个新区间，并将该区间的Count值置1。在Cache组内淘汰Count值最小的Cache数据块。

动态Cache预取算法用来以优化自适应算法的另一措施是通过预取命中率实时统计来调整预取长度参数。通过设置一个窗口函数[5]，在窗口滑动之前，Cache命中次数为H，统计出滑动到某一位置时Cache命中次数Hs。这样就可以得到Cache命中率p=H/Hs。下面定义命中率的函数f(p)。设当前窗口长度为Dcur,滑动后的长度为 Dnext，则 Dnext=Dcurf(p)；其中 f(p)是 p的增函数，且当p＞0.5 时，f(p)＞1；当 p＜0.5 时，f(p)＜1。 这样，当 Cache命中率较高时，窗口不断增大，直到达到系统允许的最大值；当Cache命中率较低时，窗口不断减小，直到预取值为0。

2.3 算法分析

多用户系统存在多个用户共享一台服务器的情况。多用户访问采取M/G/1排队模型[6],两个参数为λ1和λ2的poisson流请求同时进入服务器处理系统。用户向共享服务器发出请求命令,服务器空闲时用户能够得到立即服务，否则排队等待。

多用户访问泊松输入如图3所示。服务器处理两种请求：(1)常规请求,不能直接从本地磁盘上的预读Cache中得到用户请求响应；(2)预取请求，可以由Cache直接响应的请求。所有用户发出的服务器请求具有相同的优先级，它们加入同一个队列等待服务。假设用户请求不调用磁盘数据传输时，则消耗的系统资源非常少，因此当用户请求可从缓存Cache中满足时，此次请求将不会产生系统代价。

(1)代价函数C

对于一个给定的系统，用户的数据请求到达率为λ。假设系统中的数据块访问率都为p(p＞0或p=0)，预取不影响用户的关于访问下一个数据块的可能性p。在数据已经被预取情况下，用户仍然以相同的概率λ发出请求。常规请求到达率和预取请求到达率分别为λ1、λ2。因此，用户能从本地Cache缓存中获得请求响应的概率为 λ-λ1，等价于 pλ2，因为在缓存 Cache中的所有数据块被访问的概率为p。即如式(1)，在泊松流请求系统中，x单位时间内响应数据请求的时间t为：

其中，s平均大小的为请求数据块，b为网络带宽[7]，与当前的网络负载有关。忽略在本地缓存中获取数据的代价，f为系统的负载。在多用户系统中，一个常规请求的代价是该系统的资源代价和响应延迟代价[7]之和：

其中,aIO为将单位大小的数据从磁盘介质上读到内存中(或将内存中的数据写到磁盘上)的代价因子，它与磁盘的读写速度、系统内存等资源有关；aT为在单位时间内通过网络传输数据所需的代价因子。

多用户的请求到达率为泊松流 λ,有 Pλ2的概率能从本地Cache缓存中得到响应，有λ1以常规访问送到服务器访问磁盘。因此用户请求得到响应的的平均代价为：

其中,0＜λ2＜λ/p， 0＜p＜1。

(2)预取率 λ2的最佳值

假设p和 λ都已知,希望找到 λ2的预取值，从而最大限度地减少每个用户请求的平均代价C。λ2的值一旦被确定，可以通过计算公式 λ1=λ-pλ2计算得到。

在 p=1，λ2=λ 时以及 P=0，λ2=0时均可得到最小代价C，此时所有请求数据都可以从Cache缓存中获取。考虑 0＜p＜1的情况，代价函数 C对 λ2进行求导,通过 2次求导可得到极值位置：

在稳定系统中 b＞(λ+(1-p)λ2)s。 当 pb＞λs时， 代价函数 C对 λ2的 2阶导数一直小于 0，这表明在 dC/dλ2=0处代价函数C取得最大值。求解 dC/dλ2=0,得到 λ2′为：

代价函数 C在λ2′=0处取得最大值，系统代价随着λ2增加而减少。 给定 λ2、p、(aIO/aT)值，随着 λ2在变化范围 [0,(λ/p)]内增加，更多的预取数据块被概率p访问到，同时系统代价函数C减小。因此预取所有概率p的数据块将使访问代价函数降低到最小值。pb＜λs的情况，对于所有 λ2，有 dC/dλ2＞0，即随 λ2的增加代价函数C的值也同步增加，此时数据都不能被预取。

(3)预取阈值

在pb＞λs这样的系统中找到一个预取的阈值 H，当p＞H，λ2′＜0时，所有用户请求数据可以通过访问概率 p从Cache缓存中得到，将预取阈值设置为H。当且仅当式 p＞H成立，系统的代价函数 C在 λ2＜0获得最小值,其中 f=(λs/b) 。

容易证明 H＞f,如果 p＞H，则 p＞f，得到 pb＞λS，λ2′＜0。p取决于负载f、带宽b和固定的aIO/aT。当系统的负载f增加时，预取阈值有增大的倾向，即更少的数据块需要预取。当(aIO/aT)比值很小时，则增加负载不与预取阈值同步增大。此时f负载较低时，预取不能节省大量时间；随着负载的增加，它需要更长的时间来传输文件，预取可以节省更多的时间。因此，可通过减小阈值来增加预取数。可以证明，当且仅当b＞(aIO/aT)以及固定的aIO/aT时，减小阈值随负载f从0增加而减小。预取阈值H在负载时取得最小值。

3 测试及分析

本文以视频服务器为例对以上算法进行验证。在视频网络服务器系统中模拟5个用户访问1 000个共享数据,并让用户对服务器进行长时间的访问。记录用户对磁盘阵列中数据不同访问次数下的预取命中率，动态预取算法与自适应[6]预取的命中率对比如图4所示，明显看到动态Cache预取算法具有更好的预取效果。

使用Iometer测试软件模拟在多用户数据请求条件下，分别测试自适应预取策略和动态预取算法性能。将磁盘阵列上的硬盘分为5个分区,模拟5个吧顺序用户请求,两种算法测试性能对比如表1所示。

表1 自适应算法和动态Cache预取测试性能对比

动态Cache预取算法在达到2个用户数时，体现出更大的优越性，此时常规自适应预取算法的I/O传输率下降了60%，而动态Cache预取算法的I/O传输率没有任何下降。但是Cache组Cache区间的个数与多用户请求序列数必须同比增加，否则算法的性能下降很大。原因是当顺序请求序列数大于磁盘Cache组的Cache区间数时，导致Cache命中率下降。因此通过相应加大磁盘Cache组中Cache区间的数目来实现高效的磁盘预取性能。

在单和多用户系统中，固定式aIO/aT，系统容量越大，预取阈值就越高。然而，仅在多用户系统中的预取阈值受系统负载f的影响。通过分析3个重要函数：代价函数C、预取率 λ2的最佳值及预取阈值 H，达到动态调整系统缓存负载f来获得最小的预取阈值H，识别并分解多用户个人信息，动态调度Cache区间，减小Cache负载，从而得到最高预取命中率，解决了多用户访问共享服务系统中预取失效率高的问题。

参考文献

[1]靳强,郭阳,鲁建壮.一种步长自适应二级Cache预取机制[J].计算机工程与应用,2011,47(29)：56-59.

[2]徐炜遐,李琼,蒋艳凰.一种自适应负载的I/O调度算法[J].计算机工程与科学,2009,31(11)：1-29.

[3]张敏.一种基于SAS技术的高性能硬件磁盘阵列的设计与实现[D].江西：南昌大学,2007.

[4]张燕,胡英坚,姜涛.基于排队网络RAID存储系统的性能评价模型[J].长春工业大学报(自然科学版),2010,1(3):471-475.

[5]姜国松,谢长生,丁红,等.RAID控制器中I/O调度算法研究[J].小型微型计算机系统,2008，29(4)：773-776.

[6]王培.网格环境下基于滑动窗口的信任模型研究[D].秦皇岛：燕山大学,2010.

[7]ALEXANDER T.Performance,reliability,and perform ability aspects of Hierarchical RAID[C].Proceedings-6th IEEE International Conference on Networking,Architecture,and Storage,NAS2011.