《文件系统语义分析技术研究》由会员分享,可在线阅读,更多相关《文件系统语义分析技术研究(160页珍藏版)》请在金锄头文库上搜索。
1、分 类 号学号 512100200678545 学校代码10487密级 博 士 学 位 论 文 文件系统语义分析技术研究 学位申请人: 夏鹏 学 科 专 业: 计算机系统结构 指 导 教 师: 冯丹教授 答 辩 日 期:年 月 日 A Thesis Submitted in Partial Fulfi llment of the Requirements for the Degree of Doctor of Philosophy in Engineering Research on File Semantic Analysis in Large-Scale File System Ph.D.
2、 Candidate : Xia Peng Major: Computer Architecture Supervisor: Prof. FENG Dan Huazhong University of Science T = 1,2,.N Ds,t= 0,Others (式 4.5) 其中,哑变量Ds,t在波动子区间s取值1,而在其他子区间取值0。很明显,在对S个 周期哑变量的回归中,无需包含常数项。 分析文件系统负载时间序列,可以假定周期性是某种形式的污染,这种污染并 不会提供许多有用的信息,因此在做任何进一步的时间序列分析时间,周期性波动 应该移掉,然后再运用趋势分析法分析经周期调整后的时
3、间序列是否存在确定或者 随机趋势。这是用到的周期性波动移除方法就是双重差分法,考虑下面一个双重差 分: 1Yt= 1D1,t+ 2D2,t+ . + sDs,t+ t, t = 2,3,.,n(式 4.6) 其中s是一个周期内的波动子区间数,经过这样的预处理,周期内的各个波动子区间 的变化就能够被双重差分去除,差分后的时间序列通常适用于某一简单的移动平均 模型,并且只有少量的参数需要估计。不过,当该移动平均模型的参数估计值接近 于单位根时,就需要重新考量双重差分的合理性,因为此时可能意味着模型包含一 个一阶差分的项。 为了分析文件系统现象时间序列的周期性,考虑图4-2,其描绘了在整个HP Tr
4、ace时间周期内按照固定时间戳间隔内记录的请求条目数量的变化。很清楚的可以 看到文件数量在整个样本期显示出更明显的周期性变动,在样本期末其季节性还可 能有一些变化。为了考察和分析该数据的周期性,考虑表4.4列出的在不同变化下自 相关函数的估计值。由于该数据的统计单位是天,实验将时间戳按照2小时为单位将 每天划分为12个区间,因此每天有12个观测值,对应到表中统计的是自相关函数系 数的滞后期为12的倍数。其中,第二列是文件请求yt自身的自相关系数。显然,这 些自相关系数值大部分都是显著的,某些时间点的请求并不显著,甚至是相反的关 系,这是因为每日休息时间和工作时间的切换会导致对服务器请求的变化。
5、可以看 到,在滞后期12期的自相关系数值12yt比附近的值相对要大。对序列1yt也有同 样的结论,甚至在使用周期哑变量D1,t到D12,t对其进行修正得到(1yt)c以后,此结 105 华中科技大学博士学位论文 图 4-2 HP Trace文件请求量变化趋势曲线 论还是成立。这些由表4.4第三、四列都可以观测到。该表最后一列包含的是双重差 分112yt的自相关系数值,可以看到分析得到了自相关系数之的一个简单图式,也 就是说,其值仅仅在滞后12、24和36期是显著的。 周期性时间序列的分析过程:针对具有周期性特征的数据,其未经变换时间序 列yt的自相关系数值相对比较难解释,1yt在对周期哑变量作
6、回归后,其自相关系 数值会变得相对容易处理。最后在学习了周期数量s后syt能够比较明显的反应时间 序列的滞后期数,而经过双重差分后的时间序列能够帮助建立更加简单的文件请求 数量模型。 4.5异常观测值分析 在建立模型和对文件语义时间序列进行预测时,解释异常观测值是非常必要的。 事实上,忽视异常观测值至少会有以下三个主要的影响:首先,当利用包含异常观 测值的样本数据去估计参数时,很自然的,会出现误差。具体的,对所谓的可加的 异常观测值(Additive Outlier) ,估计参数值会偏向于零。而对一个所谓的序列均 值的水平迁移(Level Shift) ,估计参数值会偏向1。忽略异常观测值的第
7、二个主要 106 华中科技大学博士学位论文 表 4.4 HP Trace固定时间区间下文件请求量自相关函数估计 滞后期数yt1yt(1yt)c12yt112yt 10.64340.02940.0390.65060.1131 20.29470.24010.2550.21730.1386 30.11190.02670.03160.12070.0879 40.01450.00550.00230.49880.4805 50.14530.24210.30110.53220.1998 60.11120.02660.02010.42740.2416 70.09240.18890.13470.48710.18
8、98 80.06190.01960.02470.41840.4208 90.17720.00250.00280.08060.0799 100.28570.19830.29870.20960.0943 110.52830.03870.021110.56320.0889 120.80340.80410.53270.83800.7964 240.61830.64460.59980.68880.6145 360.50810.57710.49470.60570.5371 指在5%的水平下显著。被估计的自相关系数的渐进标准误差是0.067。 影响就是,在预测时忽略了与预测起始点非常接近的观测值时,则得到的
9、预测非常 不准确。最后一个影响就是,由包含异常观测点的样本数据估计模型时,得到的方 差2比实际的2要大得多,最终,这也意味着,其对应的预测区间就会变得相当的 宽。 4.6条件异方差分析 考虑数组异常观测值的一种做法就是采用上面一章提出的方法,将这些异常观 测数据的影响移除,从而对所分析的时间序列获得一个更清楚的认识。另一种方式 就是可以通过对这些异常点本身来构建序列模型以分析异常点成群出现这一现象。 由于一系列异常观测值可以被认为反映了一个多变的时期(Volatility Periods) ,最终 这样的一个时序模型也就能用于对波动的预测。也就是说,由于异常观测值群,文 件系统时间序列的方差随
10、时间改变,因此对水平数据的预测区间也同样是时变的。 直觉也不难发现,在该多变期,对于下一个观测存在更多的不确定性,进而预取区 间也就会更大。 107 华中科技大学博士学位论文 可以用自回归条件异方差模型(Autoregressive Conditional Heteroskedasticity)来 模拟时间序列变量波动性变化,考虑下面的模型: ht= + p i=1i 2 ti (式 4.7) 其中,系数需要通过观测样本进行估计,特别的,残差项满足形式: 2 t = htzt(式 4.8) 其中,zt满足标准正态同分布。为了确保非负,常数项(,i)必须为非负。并且如 果p i=1i 1,那么自
11、回归条件异方差模型具有弱平稳性,并且方差为: 2= 1 p i=1i (式 4.9) 针对该模型,有两点需要注意:首先自回归条件异方差模型是一种预测模型,因为 其是在考虑变量直到时刻t 1的所有信息的基础上预测t时刻的值;其次,基于自回 归条件异方差模型的预测是有条件的确定性预测,也就是说,该模型时刻t的均方误 差期望能够确定包含过去直到t 1时刻的误差。 4.7文件系统时间序列的非线性 文件语义时间序列的第五个也是最后一个特征就是非线性。尽管对非线性的最 好的定义就是“线性以外的一切” ,但对于文件系统时间序列来说,一个大的随机 观测冲击和一个小的随机观测冲击会有不同的影响。也就是说,在某种
12、意义上,随 机冲击的影响预期大小是不成比例的。此外,非线性也可能意味着,随机冲击的影 响与其是正冲击还是负冲击也是相关的。 4.8TiMiner时间序列分析模型 章节4.2提出了针对文件系统时间序列特征进行分析的模型,这些序列有一个共 同的特点,那就是比较简单有规则,可以直接利用现有经典的时间序列模型,并且 分析时不需要额外考虑太多文件系统场景的特殊性。本章重点讨论TiMiner时间序列 分析模型,该模型以经典时间序列模型为基础,充分考虑到文件系统语义环境来进 108 华中科技大学博士学位论文 ? ? ? ? ? ? ? 滞后期? 样本自相关 样本自相关函数 ? ? ? ? ? ? ? 滞后期
13、 样本偏自相关 样本偏自相关函数 图 4-3ARIMA(0,0,0)及其自相关函数和偏相自关函数图 行建模。作为开始,本章会首先讨论一下TiMiner模型的基础:差分自回归移动平均 模型。然后会提出如何利用该模型结合实际的场景对一个文件系统变量的时间序列 进行分析。 4.8.1差分自回归移动平均模型 差分自回归移动平均模型(Autoregressive Integrated moving average model) ,也 叫Box-Jenkins模型,或者ARIMA模型,给定一组时间序列数据,ARIMA模型通常 用于理解,分析和预测时间序列数据。该模型由三个子部分组成,分别是差分部分、 自相
14、关部分和移动平均部分。其中差分部分就是两个时间点观测值的差,可以表示 为Xt Xtk,k为滞后阶数;而自相关部分就是前面介绍的一系列时间点观测值Xt, Xt1,.,X1的线性组合来描述的线性回归模型;而移动平均部分就是一系列白噪 音(White Noise)的观测值t,t1,.,1的线性组合的来描述的线性回归模型。 109 华中科技大学博士学位论文 形式化的,可以用以下公式来表示差分自回归滑动平均模型: ARIMA(p,d,q) : (1 p i=1 iLi)(1 L)dXt= (1 + q i=1 iLi)t(式4.10) 其中,i是自相关系数,i是移动平均系数,L为滞后算子,d为差分次数,
15、而p和q分 别是自相关项数和移动平均项数。通常来说,为了确保研究时间序列的平稳性,要 求自相关系数满足以下条件42,43:| 1。差分自相关移动平均模型表示了时间序 列模型的一般模式。特别的,当参数d为0时,也就是ARIMA(p,0,q),该模型就成 为自相关移动平均模型ARMA(p,q);当参数p为0时,也就是ARIMA(0,d,q),就成 为差分移动平均模型IMA(p,q);当参数d和q均为0时,也就是ARIMA(p,0,0),就 成为自相关模型AR(p);当参数p和d均为0时,也就是ARIMA(0,0,q),就成为移动 平均模型MA(p)。 4.8.1.1第一阶段:确定差分阶数 运用ARIMA模型对文件系统时间序列进行分析的第一步就是需要根据时 间序列图形、自相关函数(Autocorrelation Function)图形和偏相关函数(Paritial Autocorrelation Function)图形识别其平稳性。如果确认序列是平稳的则说明差分次 数d为0,但是这一般是理想情况,现实中比较少的出现。因此,更多的时候是在分 析对象序列具有非平稳性的前提下对时间序列数据做平稳化处理,也就是