（计算机系统结构专业论文）基于对象相关性的缓存策略的设计与实现.pdf

华 中 科 技 大 学 硕 士 学 位 论 文 ii 摘 要 对象存储系统作为近几年兴起的一种存储技术，越来越在高性能存储领域受到 重视，研究对象的相关性对于优化对象存储系统的管理策略和性能都有着重要意 义。 在对象存储系统中，元数据的管理和请求都统一由元数据服务器来统一管理和 处理，一个性能良好的缓存模块可以大大缓解在元数据端查询的瓶颈。因此选择在 元数据服务器端实现了一个基于对象相关性的数据预取模块。依据历史访问次序和 对象语义两个方面进行数据信息的挖掘，建立对象相关性的评价模型。然后提出了 一种基于对象相关性的有向带权图的缓存算法，实现对象存储系统中元数据服务器 的缓存功能。 通过引入机器学习中的方法对缓存模型进行改进。使用线性回归分析的方法， 建立线性方程组来进一步改进和评价公式中的影响因子，以获取更准确的影响因 子。使用加强学习的方法，在缓存算法中增加了反馈的机制。 最后对缓存模型进行了测试。利用 hp trace 数据对数据预取模块进行了测试， 并且对测试结果数据进行回归分析，计算出线性拟合后的评价公式，并对拟合的结 果进行了校验，实验表明回归模型对原始数据结构拟合得比较好，分析预测结果比 较准确。 关键词：相关性、对象存储系统、数据挖掘、机器学习 973项目 2004cb318201，新世纪人才计划 ncet- 04- 0693，国家自然科学基金 60703046 、60873028， 国家 863计划项目 2009aa01a401、2009aa01a402；教育部创新团队 irt0725。 华 中 科 技 大 学 硕 士 学 位 论 文 iii abstract as a innovative storage technology, object- based storage has become more and more popular in both academia. meanwhile object relativity is significant to improving the data manage strategy and performance. the analysis result of object relativity could be apply in many area. relativity describe the data relationship and access sequence in access behavior it can be divided into tow main factor, history access sequence and semantic similarity which has its own computing way. so we can just compute both of them separately then join them two with a weight number. then the relativity evaluation mode will be created. in object- based storage system, meta data is uniformly maintained in meta data server which has only one node in the whole system. so a well- designed cache module will help reduce the bundle of meta data query in mds. so we choose to realize a cache module based on relativity computing algorithm. some study in machine learning area can help improve the relativity evaluation mode, such as regression analysis and reinforce learning. the former help to describe the relativity mode and the latter help to improve the algorithm dynamical. at last we give a performance test to the cache module and analyze the best weight value of factors. and the result prove the improvement of cache perfecting algorithm which base on relativity. key words：relativity；object- based storage；data mining；machine learning this work was supported by the national basic research program of china (973 program) under grant no.2004cb318201, the program for new century excellent talents in university ncet- 04- 0693 , and the national science foundation of china no.60703046 and no.60873028, the national hightechnology research and development program(863program) of china under grant no.2009aa01a401, 2009aa01a402， changjiang innovative group of education of china no. irt0725. 独创性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究 工作及取得的研究成果。近我所知，除文中已标明引用的内容外，本论 文不包含任何其他人或集体已经发表或撰写过的研究成果。对本文的研 究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识 到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、 使用学位论文的规定， 即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允 许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存和汇编本学位论文。 保密?，在_年解密后适用本授权书。 本论文属于 不保密? （请在以上方框内打“ v” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪 论 在网络存储领域，基于对象的存储是一种比较新颖的数据组织的思路，综合了 传统的网络存储体系 nas 和 san 的优点，提供了一个对象的接口，使用户能够直 接在网络上对数据进行访问。在产业界，基于对象存储的产品，例如 panasas，lustre 也越来越受到重视，对象存储也被认为很有可能是下一代存储系统的核心组织模 式。 对象存储系统的特点就是，按照对象来进行数据的组织，不仅仅包含了数据的 内容，还提供了丰富的数据的属性描述，即一般称为对象的元数据信息。基于这些 元数据信息，可以在安全性，可扩展性、数据布局、qos 等领域对数据提出许多策 略和基于这些策略的应用。 1.1 对象相关性的研究背景 从数据中提取和挖掘更多的信息一直是传统的文件系统的研究领域中的重点 研究之一，对象存储系统提供了比传统的文件系统更多的信息，挖掘对象之间的相 关性，可以更好的对数据的组织和应用提供策略的依据、例如数据预取、数据布局、 数据检索等应用都可以在基于数据相关性的基础上进行优化。 对象相关性的研究是建立在对象存储和文件访问相关性的基础之上的，传统的 对于文件的相关性研究主要是从文件的历史访问次序来入手进行挖掘。而对象相关 性的挖掘不在局限于文件，而是建立在对象的数据组织模式之下，具有更加丰富的 信息。 1.1.1 基于对象存储的组织模式 传统的存储系统组织形式都离不开文件的概念，数据的组织和管理都交给文件 系统来进行，文件系统的下层连接着块存储设备，在存储设备这一层上是没有文件 这个概念的，对象存储系统的出现改变了这一局面。 对象是数据的一种逻辑组织形式123。对象是文件和磁盘块之间的逻辑抽象。 华 中 科 技 大 学 硕 士 学 位 论 文 2 对象向上提供调用接口，使磁盘相关操作透明。 对象存储系统是基于对象存储设备4（object- based storage device，osd）为 核心来构建存储系统。对象存储设备是一种智能的数据存储设备，它能够具备传统 的文件系统中的某些特性，可以自动管理设备上的数据分布。对象存储的提出，改 变了传统的数据的组织形式，将文件系统的某些功能下移导了存储设备端。提出了 对象的概念替代传统的文件接口。对象指的就是数据和数据属性的集合，属性可以 包括基于文件的类型，权限，操作类型、数据分布和服务质量等。在 osd 中，对 象由一个统一的对象 id 来描述，通过各种基于对象 id 的偏移计算方法进行存储设 备的寻址访问对象。 而元数据服务器主要是用于实现元数据管理，权限控制、数据和元数据请求的 分离。一部分文件系统的操作，例如目录的创建、读写，文件的移动，chmod 命令 等操作均实际上是可以不需要对存储设备的发出 i/o 请求的，通过元数据服务器集 中管理和处理这类元数据的操作，可以较好的提高系统整体的性能。 在对象存储系统中，发生一次完整的 i/o 往往需要经过一个三方通信的过程。 即客户端先和元数据服务器交互，完成身份和操作的验证，获取对象 id 等元数据信 息，然后和对象存储设备进行交互，获取数据。客户端主要是对用户提供一个透明 的文件请求的接口，以兼容传统的基于文件的应用程序。而用户不需要关心数据的 存放位置和对象的具体信息。 目前基于对象存储上的研究有很多，从系统层面上的应用有 lustre 文件系统5， panasas6，ceph7对象存储系统等系统。 1.1.2 数据预取模型 传统文件系统中数据预取的研究主要还是基于对文件的历史访问次序的挖掘， 这种基于文件历史访问次序的预取模型主要分为两类：动态访问预取模型和静态访 问预取模型8。 静态访问预取模型，对于特定文件需要预取的文件是不变的。这类代表的预取 模型是stable first successor （fs） 9算法， 一旦确定了文件的第一个后继 （successor） ， 以后每次该文件被访问，都会选取该后继（successor）预取，预取选择不会随着访 问的推移而改变。这类算法的优势是计算预取过程的代价小，预取速度快。 华 中 科 技 大 学 硕 士 学 位 论 文 3 动态访问预取模型，每个文件记录的预取文件结果会随着访问的推移而改变， 代表的预取模型包括了 last successor（ls）10算法，该算法会选取最近的一个后 继结点作为该文件的预取结果，会随着访问的推移而改变。这类算法的优势是能够 较好的适应系统数据的变化。 大部分的数据预取算法都是基于 fs 和 ls 基础上衍生而来的。 比较值得注意的 是 plns 算法 11对于 ls 算法中加入了统计进程访问的因素。即属于同一个进程访 问的文件，彼此之间连续访问的可能性更大。 1.2 国内外研究现状 综合国内外对于数据预取以及相关性方面的研究，主要有历史访问次序，文件 语义，隐式探测 3 个方面的研究。 1.2.1 历史访问次序研究 基于历史访问次序的研究主要是对历史访问序列提出各种各样的信息挖掘算 法，试图找到一定的规律。 recent popularity 12是应用较为广泛的数据预取算法这个算法是在统计了大量 文件访问次序后根据最近访问次数的频率来进行预取的算法。在这个算法中，会首 先为每一个文件记录他的后继的次序。然后以 ls 算法通过提取最后 j 个后继某个 文件发生的次数 k 来对文件后继发生的频率进行评价。 probability graph 13算法是一个基于图的访问预取模型， 首先它们为文件建立一 个以访问关系为基础的图，接着它们会对每一个文件的访问频率做一个统计。在途 中有向连接表示文件之间的访问次序，边的权值就是每个文件的访问次数，那么这 样一个图就记录了每个文件的访问关系的可能性来评价文件的关系，如果有一个文 件仅有一个后继文件，那么他就有最高的顺序访问可能性，如果有若干个，那么就 以发生顺序访问的次数作为可能性。这个模型就是记录访问次序后通过简单的访问 次序频率的记录来评价下次预取的文件，而没有考虑其他的因素，比如说固定次序 问题。因此纯粹的通过访问频率来按照概率预取的命中率随着文件访问形式的日益 复杂命中率会越来越低 finite multi- order context models14（fmoc）模型是另外一种基于树型的预取 华 中 科 技 大 学 硕 士 学 位 论 文 4 模型，即有限多次序上下文模型。 （这里需要说明一点，就是此类算法统计的是文 件访问次序图，而上面说的 probability graph统计的是文件访问关系图，这两种统 计的最大区别是文件访问次序图会针对每一个出现在访问次序中的文件作为图中 描述的一部分。因此，同一个文件因为所属的访问次序不同在访问次序图中可能会 有多个节点来表示，而在文件访问关系图中，一个节点唯一的表示一个文件，当两 个文件之间发生了访问次序的关系时就会建立一个有向的访问链接） root a(4)b(2)c(4) a(1) b(1) b(1)c(1) c(1)b(1) c(1) b(1) a(3)b(1) c(1)b(1)c(1) 图 1 - 1 f m o c 算法模型 按照以上的原则就会得到这样一个访问树，这里一般会定义一个树的深度，就 是对一个文件统计多少个他的后继，这个参数是一个资源和性能平衡的结果。很明 显，该算法就是在文件访问次序树的基础上应用 probability graph模型提出的访问 概率，对文件进行预取。 此外基于访问序列研究的模型还包括了 pcm15，epcm16，noah17，nexus18 等模型，比较典型的算法还有 fss19算法，pbs20算法。 1.2.2 文件语义的研究 语义系统的研究最早出自 mit，基本理念就是发现现实文件之间除了元数据可 以找到两个文件的联系以外，通过对具体数据内容的挖掘，数据应用的分析可以找 到更多关于文件之间的联系。 mit 的研究人员开发了一个转换器（transducer） ，通过这个模块，语义文件系 统能够理解包括文本，程序，目标代码，邮件，图像，名字服务数据库，文献目录 以及其他文件系统包含的文件。根据具体的文件类型，提取不同的能够代表该文件 的属性信息。 华 中 科 技 大 学 硕 士 学 位 论 文 5 semantic file system 20 21开发了以下的一些功能：首先，通过建立一个基于已 有文件系统目录结构的虚拟目录，这个虚拟目录的最主要的任务是将文件访问进行 关联。其次就是 transducer 对文件属性的提取，它将文件表示成为一组和文件相关 的属性信息。 针对不同类型的文件，提取的属性组信息是完全不同的，因为每种类型的文件 都有自己的语义特点， 比如对于编译生成的.o 文件， 记录了他的作者 （就是用户名） ， 以及导入和导出的相应的模块。而对于一个邮件文件，记录的就是它的发送人，接 受人信息，以及邮件主体和内容信息。而对于一个文本文件，则记录了作者信息， 章节信息和内容信息。所以根据这些建立一个虚拟目录，可以丰富查找的内容，更 加准确的建立用户输入的搜索信息和目标信息之间的联系，便于更快的定位。 从语义方面可以获得更多关于文件本身的特性信息，便于根据这些信息针对不 同的类型制定策略以提高效率，因此不断的将这方面的研究应用到不同的领域。比 较多的是将不同的文件/目录或者数据以一组形如a1，a2，a3的语义向量的 形式代表，当有另一串文本时需要判断之间相似度时，会同样被转换成一组语义向 量。随后用各种算法进行语义关联度的计算。 1.2.3 隐式探测技术 2003 年提出了 sds(semantically- smart disk system)介绍的是一种智能语义磁 盘设备22，他和传统的磁盘设备不同在于，它可以感知上层的文件系统是如何使用 它的，而且能够感知文件系统的相关信息。其总体思路大概是，在文件系统建立 （格 式化）之后，启动一个探测进程，不断的对该分区上的文件系统进行一些读写操作。 并且将具体的操作传给 sds，sds 然后观察每次操作对应的磁盘 block 的改变，不 断的去学习这些规律，从而逐渐掌握文件系统中的目录，文件是怎么分布的。从而 可以加速以后的文件系统的请求。 1.3 对现有研究成果的分析 关于文件访问次序关系算法主要的落脚点还是文件访问次序关系为主，尤其是 在研究的初期，基本上纯粹的研究访问顺序，希望通过对访问顺序的研究，找到某 种规律，并对以后的访问次序进行预测。 华 中 科 技 大 学 硕 士 学 位 论 文 6 应当说仅仅的考虑文件次序，而忽略文件间语义关系是完全不够的，因此后续 出现了基于进程/程序的文件序列研究，随后又加入了考虑用户名的因素，将这些作 为评价文件关系的要素。 隐式探测数据的思路关相当具有想象力的算法，即本质的想法实际上还是利用 了反馈来进行增强学习。但是这个算法过于复杂，在实际的系统中大量的操作必然 会导致性能的下降，因为相当于自己维护了一套元数据的信息表，存取资源的开销 也是不容忽视的，尤其是当系统应用特别大的情况下，元数据 hash 表将是一个异 常庞大的结构。如果考虑使用机器学习的方法，可以由较为简单的算法入手。 结合对象存储系统的背景，可以得出以下的几点启发。 (1) 对象存储系统中，了解和研究对象的相关性可以更好的对数据的组织提出 策略。而对象本身提供了较文件更为丰富的属性，可以加以利用，挖掘对 象之间的相关性。 (2) 目前对数据预取方法的研究有很多，但是主要都偏向于对文件的历史访问 次序的算法，而很少有研究是将文件语义相关性分析结合进来的。但是可 以从文件请求的数据中发现二者之间应该有联系的，而不是孤立存在的， 因此可以结合语义属性和历史访问次序综合评价文件的相关性。 (3) 隐式探测的方法提供了一种很好的反馈加强学习的示例，在实现数据预取 时也是可以建立结果的反馈和输入情况，不断的进行评价模型精确和完善。 1.4 本文研究的目的和内容 研究对象存储系统的相关性可以有效的改进对象存储系统的数据管理策略，一 个好的相关性模型可以准确的对数据的访问序列进行预测，还有助于发现数据之间 的关联性。信息检索，数据预取，数据分布等多项领域都可以很好的利用相关性的 分析结果。 本文结合了传统数据预取领域中历史访问次序和语义信息两方面的因素，提出 了一种新的相关性评价模型。同时基于该评价模型设计和实现了一套预取算法，应 用在课题组 hoss 系统中客户端和元数据服务器的交互里，然后进一步引入回归分 析和加强学习的方法来不断改进对象相关性的评价模型和算法的质量。最后通过大 量的 trace 数据进行缓存的测试和分析来验证和改善对象的相关性模型。 华 中 科 技 大 学 硕 士 学 位 论 文 7 本文共分六章。 第一章，详细介绍了对象存储相关性研究的背景和研究现状，并进行了分析。 第二章，首先给出了对象相关性的定义，分析了对象相关性的影响因素，然后 提出了对象相关性的评价模型。 第三章，介绍了一个基于对象相关性的缓存模型，详细讨论了缓存模型和算法 的实现。 第四章，引入了回归分析和加强学习的方法对数据预取模型进行了优化。 第五章，使用 hp trace 对缓存模型进行测试，对测试的结果进行了多方面的对 比和分析，进一步对第二章第四章的内容进行验证。 第六章，全文总结，展望未来工作。 1.5 本章小结 研究数据访问的相关性的目的就是对数据的组织和管理提出更好的策略，研究 对象相关性可以帮助改进对象存储系统中许多方面的应用，例如数据预取，数据布 局，数据安全，数据检索等。 从目前国内外的相关研究分支和研究情况来看，大多数数据预取以及文件相关 性的研究主要还是在针对历史访问次序的挖掘上，但是仅仅简单依赖历史访问次序 是不够的，近年来对文件语义方面的研究成果对改进相关性分析是一个很好的补 充。另外一个值得注意的研究是隐式探测技术，借鉴了机器学习的方法，能够根据 当前的反馈结果不断的自我完善。 根据对相关研究的分析，本文提出了一种新的对象相关性的模型，结合了历史 访问次序和文件语义两方面的因素，并且应用到实际系统中，然后使用机器学习的 一些方法来进行改进。 华 中 科 技 大 学 硕 士 学 位 论 文 8 2 对象相关性评价模型 本章针对目前对象存储系统中，对于对象相关性评价方法的不足，结合了对象 的历史访问次序和语义，提出了一种新的评价方法。首先本章定义了对象相关性， 然后分析了对象相关性的影响因素，接着给出了对象相关性的核心算法。 2.1 对象相关性 对象是对象存储系统中数据的组织单元，和文件的概念相比，对象不仅仅包含 了数据的内容，还包含了对数据的属性的描述，文件可以由一个或多个对象组成， 并分布在不同的存储节点上。 对象比文件提供了更丰富的数据的描述， 比如对象名、 对象大小、对象类型、对象所属的用户等等，可以用于挖掘更多的用户访问规律。 不同的对象之间存在着相关关系，相关是比较宽泛的说法，这种对象之间的相 关关系可以来自很多方面。从对象的归属来看，属于同一个文件的多个对象之间是 具有相关关系的，从对象的访问行为上来看，在一定时间内，两个对象总是被连续 的访问，那么他们也是具有相关关系的，从对象的属性来看，具有相同属性的对象 之间也是相关的。本文主要关注的是对象的访问行为，因此重点从这个思路上去讨 论对象的相关性。 可以借助信息检索领域中的相关性的概念来理解信息存储领域的相关性，在信 息检索中，衡量检索结果的质优的量化标准主要有两项，检索结果的相关性与重要 性。例如对于互联网上搜索引擎的检索结果往往多达几十万条，搜索引擎综合检索 结果的相关性和重要性对结果进行排名，尽量让用户有比较好的搜索体验，能够迅 速获取自己想要的优质信息。搜索引擎里的相关性的计算主要来自网页 url 的正 向与反向链接23，url 之间的链接构成了网页相关的基础，对于存储系统来说，可 以认为在一定得访问步骤内的存储单元是具有这种类似 url 链接的相关关系的。 综合以上对于对象存储系统中对象的相关关系的理解提出以下两点定义。 定义一： 在一定访问步骤内，两个对象a，b被先后访问，则称这两个对象相关，记为 arb，对象a，b被访问的事件记为ae，be； 华 中 科 技 大 学 硕 士 学 位 论 文 9 定义二： 如果对象a，b相关，在一定步骤内，访问完a后访问b的概率称为对象a和 b相关性，记为( , )r a b。 ( , )(|)bar a bp ee=，(01)r 当0r =则表示对象a，b之间没有相关性，具有独立的访问特征，当1r =则 表示a，b完全相关。 对象相关性已经给出了形式化的定义，是一个条件概率的描述。但是直接从定 义的描述公式去计算这个条件概率是非常困难的。一个可行的思路是通过分析历史 已经出现的访问序列，从中挖掘出一定的访问规律，这一部分的分析结果称为对象 的历史访问次序的相关性。另外一个思路是借鉴语义文件系统的相关研究，从对象 的共有的属性入手去挖掘对象的属性和访问关系的联系，这一部分的分析结果称作 对象的语义相关性。综合这两个方面的分析，对象相关性可以进一步分解为对象的 历史访问相关性和语义相关性。 记( , )f a b为对象a，b的历史访问次序相关性，记( , )s a b为对象a，b的语 义相关性，则对象的相关性计算公式可以描述如下： ( , )( , )( , )r a bf a bs a b=+，(01) （2 - 1 ） 式 2- 2 将对象相关性的计算分解成为了对历史访问次序相关性的计算和对对象 语义相关性的计算，本章 2.2 小节 和 2.3 小节 分别分析了这两种相关性，并给出 了具体可行的计算方法。 2.2 对象的历史访问次序的相关性 历史访问次序的相关性的研究，是从过去已经发生的访问序列中寻找规律，根 据访问序列中众多文件和对象被访问的频次来预测即将发生的访问。大部分的数据 预取方面的研究也都是基于历史访问序列提取访问信息，挖掘访问行为。 类似对象的相关性的定义，对象的历史访问次序的相关性也可以用条件概率的 形式给出，并且由于历史的访问次序都是已知的，可以很容易的计算出这个条件概 率。为了计算对象之间的历史访问相关性，需要完整的记录对象在一定步骤之内的 华 中 科 技 大 学 硕 士 学 位 论 文 10 前驱与后继的出现情况，称追踪步骤数目的最大值为监测窗口，在监测窗口之内， 计算给定的对象a，b之间的历史访问相关性，就可以用a，b先后出现的概率来 表示： ( , )(|)/abaf a bp b ann= （2 - 2 ） 其中abn表示文件b作为文件a的后继被访问的次数，an表示文件被a访问的 总次数，这样(|)p b a就表示文件b作为文件a的后继被访问的概率。 如果依次访问了对象,a d a b c a b d c，那么依据式 （2- 2） 计算， 文件b作 为文件a的后继一共出现了 2 次，a本身出现了 3 次， 那么( , )(|)2/3f a bp b a=。 结合传统的数据预取领域的算法，可以继续对该公式做一些细化。对于数据预 取而已，主要还是利用了访问的局部性原理，例如 lru 算法，总是换出哪些最久 没有被访问的缓存单元，不仅仅单纯考虑缓存单元被访问的频次，还考虑频次发生 的间隔时间，或者说访问间隔。数据预取中，对于同一个对象的若干个后继，距离 该对象的访问间隔越短的应该优先被预取，因为紧接下来被优先访问的可能性更 高。 定义abd为对象a，b之间的访问间隔，w为监测窗口值，abdw。改进后 的计算历史访问次序相关性的方法为： 1 ( , )(1)/ n abi a i d f a bn w= = （2 - 3 ） 其中表示每个后继相对前驱对象的访问距离。例如对于访问序列： ,a d a b c a c b d b作为a的后继出现了 2 次，每次出现相对于a的访问距离分别为 0 和 1，假 设监测窗口值设为 10，则1 0.91.9id = +=，而访问概率(|)1.9/30.63f a b =。 对于历史访问次序相关性的分析，还需要注意以下几点考虑。 (1) 基于历史访问次序的相关性分析性具有一定滞后性的，在相关的对象的先 后被访问的情况多次出现并被分析记录之前，这种算法是无法进行有效预 测的。 (2) 监测窗口的大小也会直接影响相关性的精确度，从理论上来说，监测的窗 华 中 科 技 大 学 硕 士 学 位 论 文 11 口越大，得出的结果越准确。但是保留的检测窗口的值越大，耗费的计算 资源和存储资源也越多，需要在计算精度和资源耗费上达到一个平衡。 (3) 访问序列是在不断变化的，因此任意两个对象之间的访问次序相关性是会 随着访问的过程而不断变化，这种计算方法对于非规律性出现的访问序列 抗干扰能力不够强。 (4) 某些访问序列特征是呈马尔科夫链状分布的，即仅仅和当前被访问的对象 有关，和之前的所有访问序列均无关。 因此需要借助其他方面的研究，来补充历史访问次序相关性的不足，利用对象 的语义相似度是一个很好的补充。 2.3 对象的语义的相关性 对象的语义就是用于描述存储单元各种属性和信息的元数据。在对象存储系统 中包含了非常丰富的元数据的描述。例如数据所在的文件扩展名和对象名，路径； 数据内容关键字，数据大小，访问修改时间，属于用户等。 在数据预取的传统研究领域中，仅仅是从历史访问序列中去寻找规律，忽视了 数据本身属性提供的信息，而实际上这些信息是可以被加以利用的。探索语义相关 性的基本方法就是通过对上述提到的各种内容语义进行挖掘，利用数据挖掘和统计 学方法找到更多关于对象之间的联系。通过相关的数据方法研究将语义信息量化并 予以评价。为了理解语义相关性，可以考虑以下场景： (1) 一个用户将自己的许多收藏歌曲放到同一个文件夹中，然后使用播放器顺 序播放这些歌曲文件。同样情形还有很多，说明具有相同或者相似路径下 的文件是具有很强的相关性； (2) 每个用户都有自己的访问领域，使得同一用户访问的对象具有很强的相关 性，这意味着用户与对象的访问具有强相关性； (3) 进程在调用文件时也呈现一些规律，比如一台机器上同时运行着多个进程， 其中包含一个数据库的服务进程，另外一个是 webserver，那么数据库服务 进程主要访问的是数据库文件，而 webserver 主要是访问的是网页文件。同 一个进程访问的文件也是在有一定关联的。 华 中 科 技 大 学 硕 士 学 位 论 文 12 在这些场景下，具有相同语义的文件更容易被先后连续访问，具有相同或者相 似语义属性的数目越多，相关性也越大。分析语义相关的首先需要提取那些对相关 性有所影响的属性。在前面我们已经从定性的角度发现了文件路径，用户名，进程 名的属性对相关性的影响，随着对文件语义方面的研究深入，也会有越来越多的语 义属性被纳入到相关性计算的范畴，对这些一系列的语言属性的相似度的评估，需 要有一套完善的计算方法，而这方面最为成熟的算法是向量空间模型算法 1 3 。 向量空间模型算法的基本思想是，将需要进行相似度匹配的文本进行特征属性 切分， 然后将切分后的属性组成向量， 然后统计相似的属性部分占所有属性的比重， 类似与求余弦。余弦计算的好处是, 正好是一个介于 0 到 1 的数, 如果向量一直就是 1 , 如果正交就是 0 , 符合相似度百分比的特性。 然后可以使用向量来表示文件属性的集合，用向量中的每一项来表示文件的某 个特定属性。向量可以作为矩阵中的列来存储，这样，就可以用向量来计算文件之 间的语义相似度。语义相似度是基于这样的一个计算公式，类似余弦算法。 ( , ) |/|max( , ) |sim a baba b= （2 - 4 ） 在该式中，a和b分别代表文件的语义向量空间，( , )sim a b表示二个语义向量 空间的语义距离。i ， 12 ,., m bb bb=。语义向量a和b之间的交集作为分子，a 和b的最大项数目（即 n 和 m 之间最大数）作为分母。 根据式( 2 - 4 ) ，可以计算文件之间的语义相关性，语义相关性的计算可以理解 为语义相似度的计算。 在所有我们前面讨论过的文件语义属性中，除了文件路径，其他语义属性都可 以简单的用一个单元来表示。文件路径本身是由若干个目录组成，本身也可以看成 一个向量，因此可以先对文件路径本身做一次语义相似度的运算，然后再将所有语 义属性的相似度加入到相关性的计算公式中。换句话说，文件路径这样的属性的相 似度可以使小数， 而其他简单属性的相似度要么为 0 . 要么为 1 。 表 2 - 1 是一个例子， 每个语义向量项(1,2,.) i a i =表示了一个语义属性的相似度。 华 中 科 技 大 学 硕 士 学 位 论 文 13 表 2 - 1 文件路径的语义向量 文件 文件路径 文件路径语义向量 a / h o m e / w o r k / p i c t u r e / a a = h o m e , w o r k , p i c t u r e , a b / h o m e / w o r k / p i c t u r e / b b = h o m e , w o r k , p i c t u r e , b c / h o m e / g u e s t / c c = h o m e , g u e s t , c 图中可以计算文件 a ，b ，c 之间的文件路径相似度 f d : f d ( a , b ) = 3 / 4 = 0 . 7 5 ; f d ( a , c ) = 1 / 4 = 0 . 2 5 ; f d ( b , c ) = 1 / 4 = 0 . 2 5 。 对于简单属性的语义相似度求法：如果 a b 语义属性相同，(,)1sim a b =；否则， (,)0sim a b =。 前述两小节各自从历史访问次序和语义相似的角度给出了量化的方法，最后综 合以上因素提出对象相关性的完整评价公式，对公式（2 - 1 ）进行了细化： ( , )0( , )( , ) 1 n a ba bi i a b i rfs = =+ （2- 2） 在这里实际上使用一个线性方程来描述对象的相关性的量化模型。其中i描述 了第 i 种因素的影响因子。将历史访问次序的计算结果作为一个影响因素，把每一 种语义都作为一项单独的影响因素。 这样就得出了对象相关性的计算公式， 公式 2 - 2 中的各项影响因子是待定的，实际上按照的计算方法，不存在恒定的影响因子，因 这个算法在很大程度上还是和历史访问序列相关的，也就是说对于不同的存储系 统，不同类型的存储应用，影响因子的值是不同的。针对某种特定的情况，根据已 经发生的访问序列，去计算各项影响因子，实际上是一个回归分析的过程，首先需 要去建立一个分析的环境，记录访问序列，得出结果，然后去进行回归分析，这些 将在第三、四章给出详细的介绍。 华 中 科 技 大 学 硕 士 学 位 论 文 14 2.4 本章小结 本章重点提出了对象相关性的评价模型，并进行了深入分析。 首先对比了信息检索和存储系统中的若干场景，给出了对象相关性的形式定 义。然后进一步分析了影响对象相关性的因素，分为了历史访问次序相关性和语义 相关性。 从对象的历史访问次序进行分析，实际上是假设了存储系统的访问是呈现周期 性重复规律的。历史访问次序相关性的计算方法可以简单的使用条件概率形式来计 算，并加入了访问时间间隔的因素。 语义相关性的计算实际上等效与计算语义相似度，这方面可以借鉴了信息检索 领域的语义向量空间算法，给出了语义相似度的计算方法。 最后通过一个包含了若干影响因子的公式来描述对象相关性的评价模型。 华 中 科 技 大 学 硕 士 学 位 论 文 15 3 基于对象相关性的数据预取 对象相关性的信息可以对数据的组织和管理提出更多更好的策略34，其中基于 对象相关性的数据预取是其中一个较为简单的应用，同时这个应用也提供了一个进 一步分析对象相关性的场景，本章介绍了对象存储系统中一个基于对象相关性实现 的缓存模型。 3.1 对象存储系统体系结构 基于对象存储的思路， 实验室设计实现了一个分布式对象存储系统hoss （huge object- based storage system） ，内部使用对象作为存储的单元来组织数据，对外提 供传统文件系统的接口，以满足上层基于文件的应用程序的需要。主要包括了元数 据服务器(mds)、客户端(client)和对象存储设备(osd)，三者通过网络互连，具有 良好的可扩展性。 (1) 客户端主要的作用是提供传统的文件系统结构，并且提供并发访问 osd 的 机制。客户端可以看做将 mds 客户端和 osd 客户端组合并嵌入到传统的 文件系统里，实现基本的文件系统的接口，但是将对文件系统的请求全部 转化为对对象的请求，然后转发给 osd 并从 osd 中返回数据。其他的功 能还包括权限管理，qos 需求配置等。 (2) 元数据服务器的主要作用是维护和管理统一对象的元数据视图。元数据服 务器上保存了完整的文件到对象的映射关系的信息，以及文件的路径、用 户名等元数据信息，提供文件的目录等元数据信息的统一管理。 (3) 对象存储设备（osd）主要作用是提供基于对象的智能数据管理。osd 是 一种智能的设备，具备了某些分布式文件系统的功能，例如数据智能布局， 安全管理机制等。hoss 中的 osd 实际上也是在文件系统上层实现的34， 其底层仍然是传统的文件系统 ext2 和磁盘设备，兼容了 osd 的传输接口。 hoss 的工作流程基本上可以总结为两次转化。一次发生在 mds，一次发生在 osd，如图 3- 1 示。用户在客户端上发起了文件的请求，请求分为元数据请求和 i/o 请求。 华 中 科 技 大 学 硕 士 学 位 论 文 15 3 基于对象相关性的数据预取 对象相关性的信息可以对数据的组织和管理提出更多更好的策略34，其中基于 对象相关性的数据预取是其中一个较为简单的应用，同时这个应用也提供了一个进 一步分析对象相关性的场景，本章介绍了对象存储系统中一个基于对象相关性实现 的缓存模型。 3.1 对象存储系统体系结构 基于对象存储的思路， 实验室设计实现了一个分布式对象存储系统hoss （huge object- based storage system） ，内部使用对象作为存储的单元来组织数据，对外提 供传统文件系统的接口，以满足上层基于文件的应用程序的需要。主要包括了元数 据服务器(mds)、客户端(client)和对象存储设备(osd)，三者通过网络互连，具有 良好的可扩展性。 (1) 客户端主要的作用是提供传统的文件系统结构，并且提供并发访问 osd 的 机制。客户端可以看做将 mds 客户端和 osd 客户端组合并嵌入到传统的 文件系统里，实现基本的文件系统的接口，但是将对文件系统的请求全部 转化为对对象的请求，然后转发给 osd 并从 osd 中返回数据。其他的功 能还包括权限管理，qos 需求配置等。 (2) 元数据服务器的主要作用是维护和管理统一对象的元数据视图。元数据服 务器上保存了完整的文件到对象的映射关系的信息，以及文件的路径、用 户名等元数据信息，提供文件的目录等元数据信息的统一管理。 (3) 对象存储设备（osd）主要作用是提供基于对象的智能数据管理。osd 是 一种智能的设备，具备了某些分布式文件系统的功能，例如数据智能布局， 安全管理机制等。hoss 中的 osd 实际上也是在文件系统上层实现的34， 其底层仍然是传统的文件系统 ext2 和磁盘设备，兼容了 osd 的传输接口。 hoss 的工作流程基本上可以总结为两次转化。一次发生在 mds，一次发生在 osd，如图 3- 1 示。用户在客户端上发起了文件的请求，请求分为元数据请求和 i/o 请求。 华 中 科 技 大 学 硕 士 学 位 论 文 16 (1) 客户端发起到 mds 的查询，获取文件对应的对象 id 和对象所在的位置。 (2) mds 查询数据库，获取信息并返回给客户端。如果是元数据的更改请求， 向 osd 发起对象创建/删除操作。 (3) 如果是 i/o 请求，客户端继续向对象所在的 osd 上发起对象的 i/o 请求。 (4) osd 处理对象的 i/o 请求，根据 osd 自己维护的智能数据布局，根据对象 id 计算出该对象所在存储节点的位置和文件路径，然后发起文件请求操作， 返回处理的结果。 (5) 客户端收到 osd 的返回数据再返回给上层应用程序。 元数据服务器 客户端 文件系统接口 元数据服务客 户端 i s c s i 客户端 对象存储设备 i s c s i 服务器端 对象存储服务 文件元数据服务 对象元数据服务 元数据服务客 户端 文件/ 对象映射 e x t 2 文件系统 对象/ 文件映射 图 3 - 1 h o s s 系统结构图 3.2 数据预取模型 hoss 系统中，元数据服务器端集中管理了所有对象的元数据信息，实现元数 据操作和数据操作的分离。因此在 mds 上实现数据预取能够极大提高整个系统中 元数据请求的性能。 基于 hoss 中客户端和 mds 的交互模型，设计和实现了一套数据数据预取模 型，采用了基于对象相关性的数据预取算法。 华 中 科 技 大 学 硕 士 学 位 论 文 17 这个数据预取模型主要分为四个部分，抽取、挖掘、构建和评估。 (1) 抽取，主要是负责从访问的文件或者对象中提取出丰富的元数据信息，并 以一定的形式保存下来。 (2) 挖掘，动态的生成对象之间的相关性，并依次作为判断是否预取的依据。 (3) 构建，创建一个有向带权图来维护所有被访问过的对象和他们之间的关系。 (4) 评估，最后根据缓存的命中率来评估对象相关性的计算公式是否合理，然 后进行调整。 加入了数据预取模型的系统结构如图 3- 2 示。 对象存储设备 数据预取 客户端 文件系统接口 元数据服务客 户端 i s c s i 客户端 对象存储设备 i s c s i 服务器端 对象存储服务 元数据服务端 文件元数据服务 对象元数据服务 信息抽取 信息挖掘 元数据服务客 户端 图 3- 2 数据预取模型 hoss 系统里需重点关注的是客户度和元数据服务器的交互部分，客户端仍然 会提供文件形式的访问接口，并且向元数据服务器请求该文件对应的元数据信息， 元数据服务器会在这个过程中记录每次客户端的发来的请