一种基于连续度聚类和时间序列的I/O区域预取方法

摘要

本发明公开了一种基于连续度聚类和时间序列的I/O区域预取方法。本发明根据I/O请求具有局部性的特征，在系统空闲时刻预测密集I/O访问的区域，并对预测的区域进行预取。它采用基于连续度的聚类算法，能高效、可靠的发现密集读请求的区域；其次是利用ARMA时间序列模型来预测未来密集读请求可能访问的区域和访问时刻。在同一测试环境下，对采用本发明储系统和现有的RAID系统进行了对比测试，在利用3个磁盘卷的负载测试表明：本发明聚类算法能正确的聚类读请求；同时基于AMRA时间序列的预测模型的动态预测算法的准确预取密集I/O区域。本发明能实用且高效的发现密集读请求访问的区域，并准确的预取密集读请求可能访问的区域，较大的提高存储系统性能。

主权项

1、一种基于连续度聚类和时间序列的I/O区域预取方法，其步骤包括：(1)在I/O请求密集时刻，将I/O流中的读请求根据物理块地址排序，形成一个对象链表；(2)将所有物理地址相连或重叠的对象合并成一个对象，其长度为各对象长度之和，按下述规则计算出所有对象的连续度：设对象p的长度为1，若其左侧或右侧无相连的对象，则设其连续度S_io(p)＝a₁；若其左侧或右侧有一个相连的对象，则设其连续度S_io(p)＝a₂；若两侧均有相连的对象，则设其连续度S_io(p)＝a₃，其中，a₃＞a₂＞a₁；(3)标记连续度大于阀值H_o的对象作为核心对象，其中，阀值H_o按照公式(1)计算，其中k为对象的数量：$H_o\ge \frac{\underset{i=1}{\overset{k}{\Sigma }}{S}_{\mathrm{io}}\left(p_i\right)}{k},i=1,···,k---\left(1\right)$(4)按照下述规则查找与每个核心对象可达或相连的所有对象，将其构造成簇：(A1)以核心对象o为中心，左右两侧距离d为半径的区域称为o的d-邻域；如果D是对象集合，p∈D，o∈D，若o是核心对象，p在o的d-邻域内，则称p是从o出发关于d直接可达；(A2)若存在一个对象链p₁，p₂，...，p_n；p_i∈D，1≤i≤n-1，n为对象链中对象的个数，p_i+1是从p_i出发，关于d直接可达，则p_n是从p₁出发关于d可达；(A3)在对象集合D中，o∈D，p∈D，q∈D，若存在p和q都是从o出发，关于d的可达，则称p、q是关于d的相连；(A4)将满足下面条件的所有对象构造成簇C：(I)如果p∈C且q是从p出发关于d的可达，则q∈C；(II)$\forall p,q\in C:$p、q是关于d的相连，则p∈C；(5)从形成的各簇中选择出连续度大于等于簇C阈值H_c的簇，形成有效结果簇，其中簇C阈值H_c按照公式(2)计算：$H_c=\frac{1}{2}[a_{3}l-2(a_3-a_2)]---\left(2\right)$其中l为簇所占空间长度；(6)如果是首次运行，重复步骤(1)至(5)，直至获取多个时间段的多个有效结果簇；否则转入步骤(7)；(7)从有效结果簇中获取访问区域信息，并以多个密集I/O访问的时间构成访问时间信息，分别形成读请求区域的时间序列和访问时间的时间序列T_c(t)，有效结果簇的中心点和簇半径构成访问区域，设有效结果簇的中心点值为P_BA(t)，对应有效结果簇的簇半径为R_(t)；(8)判断访问区域信息和访问时间信息是否满足ARMA时间序列是零均值的平稳时间序列，如果是，进入步骤(10)，否则进入步骤(9)；(9)对非平稳的序列进行平稳化处理；(10)将平稳的时间序列构造出ARMA时间序列预测模型，即P_BA(t)-φ₁P_BA(t-1)-…-φ_kP_BA(t-p)＝a_t-θ₁a_t-1-…-θ_qa^t-q    (5)R_(t)-φ₁R_(t-1)-…-φ_kR_(t-p)＝a_t-θ₁a_t-1-…-θ_qa_t-q          (6)T_c(t)-φ₁T_c(t-1)-…-φ_kT_c(t-p)＝a_t-θ₁a_t-1-…-θ_qa_t-q       (7)其中，φ_k、θ_q为待定系数，a_t为误差系数；(11)将最近I/O请求密集时刻及以前多个I/O请求密集时刻所获取的P_BA(t)、R_(t)和T_c(t)值带入公式(5)、(6)和(7)中，预测下一I/O请求密集时刻预取区域和预取时间值；(12)对预测的数据进行还原处理，形成还原后的预取时间的预测值和预取区域信息的预测值；(13)判断系统是否是空闲，如果系统空闲且符合下述预取时间，则进行预取，然后进入步骤(14)，否则重复步骤(13)；按照下述过程判断预取时间：(B1)假定某个I/O请求为最后一个密集I/O请求，且在σT_io时间内无I/O请求，则认为系统现处于空闲时刻，利用公式(8)计算σ的取值；$10\le \sigma \le \frac{\overline{H_n}-{\sigma }_H-\overline{t_p}-m\overline{t_t}}{\overline{T_{\mathrm{io}}}}---\left(8\right)$其中：$\overline{H_n}=\frac{\underset{i=1}{\overset{n}{\Sigma }}{H}_i}{n_a}---\left(9\right)$其中n_a为最近10个聚类区域的时间间隔，H_i为各聚类区域时间间隔，平均时间间隔为H_n，σ_H为平均时间间隔的均方差，平均密集I/O时间间隔为T_io，磁盘或阵列的平均定位延迟为t_p，传输一个数据块的时间为t_t，m为预取的数据块数量；(B2)设t₁、t₂分别为是预取的最早时刻和最后时刻，则t₁＝10T_io，t₂＝H_n-σ_H-t_p-mt_t，预测的预取时刻为T_c，实际预取时刻为T_p；按照下述方法得到预取时刻T_p，在T_p时刻进行预取：(I)如果t₂≥T_c≥t₁，则T_p＝T_c；(II)如果T_c≤t₁，则T_p＝t₁；(III)如果T_c≥t₂，则T_p＝t₂；(14)将预取的数据与实际的读访问数据对比，若二者的误差超过所规定的门限值时，进入步骤(10)，重新构造预测模型，否则进入步骤(15)；(15)重复步骤(1)-(15)，直到系统工作结束。