1、目录n物联网数据存储现状分析n海量元数据查询需求分析n物联网元数据管理系统设计n面向数据更新的结构设计和分析 n面向预计算的元数据组织结构数据立方体 物联网数据存储现状分析 n大规模存储系统的应用越来越广泛，存储容量也从以前的TB（Terabyte）级上升到PB（Petabyte）级甚至EB（Exabyte）级。n随着存储系统规模不断增大，在大规模文件系统中，文件的数量高达几十亿个，在这种海量数据中查找和管理文件变得异常困难。物联网数据存储现状分析n这与互联网环境形成了鲜明的对比：n由于搜索引擎技术的发展，在互联网的环境下查找信息很方便，n而用户在存储系统中找到想要的信息比在互联网上查找信息更
2、加困难 物联网数据存储现状分析n如今存储系统中的数据量的快速增长使得查找和管理文件异常的困难，n为了能够合理的管理这些不断增多的海量数据，n不管是用户还是管理者都需要能够高效的获得文件的属性。物联网数据存储现状分析n元数据查询包含索引文件元数据，例如索引节点和一些扩展属性，能够帮助回答很多复杂查询问题。n利用文件属性，元数据查询允许点查询、范围查询、top-k查询和聚集查询，n这些使得复杂的、特定的查询变得简单。物联网数据存储现状分析n能够帮助管理者回答n“哪些文件在过去的一周里增长很快？”n或者是“哪些应用程序和用户的文件占用大多数存储空间？”n元数据查询也能够帮助用户找到10个最近访问的报
3、告或最大的虚拟机镜像。n准确地回答这些问题能够极大的提高用户和管理者管理大规模存储系统中的文件。物联网数据存储现状分析n现存的系统一般都采用通用型的数据库管理系统（Database Management System，DBMS）来索引元数据，n由于DBMS不能很好的适用于多维元数据的查询，n查询效率非常低物联网数据存储现状分析n这就限制了在大规模存储系统中元数据查询的性能和可扩展性，n所以在大规模存储系统中要想获得快速、高效的元数据查询是很难实现的。物联网数据存储现状分析n从而使得一些复杂查询非常耗时、效率低下，n不能有效地支持用户或管理者查找到想要的文件，或得到想要的数据。n例如，“我最近修
4、改过的PPT在哪？”n或者“我的目录下这个文件有几个副本？ 物联网数据存储现状分析n为了解决上述问题，必须提供一种高效的多维元数据查询系统，而且必须满足以下特点：n第一，必须能够从存储系统中快速收集到元数据；n第二，查询和更新必须快速而且可扩展；n第三，必须能够快速的返回计算结果，比如用户提交一个复杂查询后并不想长时间在线等待计算结果，有时这个过程非常费时物联网数据存储现状分析n例如n“某公司想统计一个星期内用户产生的数据总量有多少？”n或者“最近一星期内排前五名的热点文件是哪五个？”，n用户或管理者希望系统能够预先计算好这些结果而不用在线等待，当提交查询后能够快速返回结果物联网数据存储现状分
5、析n第四，资源需求必须很低，现存的很多元数据查询工具需要专门的CPU、内存以及硬盘，这就使得它们非常昂贵而且很难集成到存储系统中；n第五，查询的接口必须灵活好用，对于现存的文件系统接口和查询语言，复杂查询非常困难 物联网数据存储现状分析n在海量的数据中，让用户获得想要的信息至关重要，n对存储系统中多维元数据查询的研究将大大提高文件元数据的查询效率，n实现复杂查询，缩短响应时间，n这对于用户或管理者查找和管理文件，以及决策支持都有重要的意义 海量元数据查询需求分析 n现在的存储系统都是采用层次化的目录结构来组织文件的，层次化结构使得文件的访问效率不高。n访问某个文件必须通过层次型的目录树结构到达
6、文件的保存位置，n如果不知道文件保存位置，就必须遍历整个目录或使用操作系统的搜索功能，n而操作系统仅能依靠文件名来检索和查找数据。海量元数据查询需求分析 n在最近的十几年里，新数据类型（多媒体、电子邮件）不断涌现，n这些数据中包含了大量的元数据信息。n认识到现有文件系统的不足，学术界和工业界都做了大量的工作来研究如何利用丰富的元数据信息来提高文件的管理和搜索效率 海量元数据查询需求分析n在大规模存储系统中查找和管理文件显得更加困难，n元数据查询可以很好的解决点查询、范围查询、top-k查询以及聚集查询，n便于进行一些复杂、特殊的查询。n能够快速地实现上述查询能极大地提高用户或管理者对大规模存储
7、系统的管理 海量元数据查询需求分析n在大规模存储系统提供高效的元数据查询是一个很大的挑战，n而现在有一些商业元数据查询系统主要致力于小型的存储系统（最多几千万个文件）n并且常常很慢，耗费的资源多 海量元数据查询需求分析n在大规模存储系统中想要实现高效的元数据查询，需满足以下几点: n最小的资源需求最小的资源需求p元数据查询不应该需要额外的硬件，它应该集成到存储系统中而不降低系统的性能。p现在大多数的元数据查询系统都需要专门的CPU、内存以及磁盘，p使得它们非常昂贵而且很难部署，这就限制它们的扩展性 海量元数据查询需求分析n快速的元数据收集快速的元数据收集n必须从几十亿、几百亿个文件中周期性的收
8、集发生改变的元数据，n而不会给整个存储系统带来额外负载，使得系统变慢。n现在的爬行算法（crawling method）非常慢而且消耗系统资源 海量元数据查询需求分析n快速可扩展的索引查询和更新快速可扩展的索引查询和更新n查询必须快速，甚至随着系统规模的扩大，性能依旧能保持很好，能够快速周期性的对元数据索引进行更新。n但是，现存的系统一般都采用通用型的关系型数据库来索引元数据。nDBMS常常使用重量级的锁和事务，这给系统增加负载 海量元数据查询需求分析n易用的查询接口易用的查询接口n大多数系统输出简单的查询应用程序接口，n但是研究表明专门设计的接口能够很好表达且容易使用，n这会大大提升查询体验
9、。 物联网元数据管理系统设计 n系统设计要求系统设计要求n第一、高性能，能够快速的从文件系统中聚集元数据，解决并发操作、热点数据的管理和访问等问题；n第二、查找和更新速度必须快且可靠。现有的系统一般采用通用的DBMS来索引元数据，但是通用的DBMS的设计并不完全适合各种应用场合，比如元数据查找，特别是支持各种复杂的元数据查询，热点数据查询等；而且在大规模存储系统中会限制其性能和扩展性。物联网元数据管理系统设计n第三、低的资源消耗。保证元数据查询不需要占用太多的存储空间，且不会降低系统的性能。n第四、接口灵活好用。现有的文件系统接口不能很好的支持各种复杂文件查询。n第五、良好的伸缩性及可用性。随
10、着存储系统的规模越来越大，必须保证系统具有良好的伸缩性和可用性 多维元数据组织结构 n传统的索引方法已不能满足多维数据的索引和查询要求，n比如哈希表是数据的精确匹配而不能进行范围查询，n而B树索引一维数据而不能搜索多维空间。n目前存在大量的空间数据索引方法多维元数据组织结构n一般来说，常见的多维空间数据索引有两种数据组织方式：基于规则的分割方法和基于数据的分割方法。n基于规则分割的索引结构按照特定算法对数据空间进行划分，包括KD树、网格等，n这种方法仅适用于数据分布均匀的情况，在数据分布不均匀时会引起索引结构的不平衡。n基于数据的分割方法有R树，Cell树等，按照数据的分布特性逐层划分空间 多
11、维元数据组织结构n如果系统基于每个维度单独建立索引，则需要对每个维度进行查找之后将结果做交集。n如果系统按照多维属性信息建立了空间索引结构，则可以同时在文件大小、创建时间和修改时间这个三个属性维度上做约束，大大减少了查询的数据量和查询的时间代价。n系统耗费一定的存储空间维护空间索引结构，在提供各种复杂查询服务时可以有效的减少查询时间延迟 相关研究工作: R树结构n与B树相似，R树是一种高度平衡的树，它的叶子节点的记录包含数据对象的指针。n如果索引是磁盘驻留的，则每个节点对应一个磁盘页，以节点为单位读取和写入。n该结构设计使得空间搜索只需要访问一小部分的节点，大大提高检索效率。n索引结构是完全动
12、态的；插入、删除和查找操作能同时进行而且不需要定期地对树的结构进行重新组织 相关研究工作相关研究工作:B树、树、B-树、树、B+树、树、B*树树nB树树 即二叉搜索树：1.所有非叶子结点至多拥有两个儿子（Left和Right）；2.所有结点存储一个关键字；3.非叶子结点的左指针指向小 于其关键字的子树，右指针 指向大于其关键字的子树；如：B树树n B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；n如果B树的所有非叶子结点的左右子树
13、的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；B树树是一种多路搜索树（并不是二叉的）：1.定义任意非叶子结点最多只有M个儿子；且M2；2.根结点的儿子数为2, M；3.除根结点以外的非叶子结点的儿子数为M/2, M；4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）5.非叶子结点的关键字个数=指向儿子的指针个数-1；6.非叶子结点的关键字：K1, K2, , KM-1；且Ki Ki+1；7.非叶子结点的指针：P1, P2, , PM；
14、其中P1指向关键字小于K1的子树，PM指向关键字大于KM-1的子树，其它Pi指向关键字属于(Ki-1, Ki)的子树；8.所有叶子结点位于同一层；如：（M=3）B-树树B树树B+树是B-树的变体，也是一种多路搜索树：1.其定义基本与B-树同，除了：2.非叶子结点的子树指针与关键字个数相同；3.非叶子结点的子树指针Pi，指向关键字值属于Ki, Ki+1)的子树（B-树是开区间）；5.为所有叶子结点增加一个链指针；6.所有关键字都在叶子结点出现；如：（M=3）B+树树n是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；nB*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低
15、使用率为2/3（代替B+树的1/2）；B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；所以，B*树分配新结点的概率比B+树要低，空间使用率更高；B*树树nB
16、树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；nB-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；n所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；nB+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；nB*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；相关研究工作相关研究工作:B树、树、B-树、树、B+树、树、B*树树相关研究工作: R树结构nR树是一个高度平衡树，它是B树在k维上的自
17、然扩展，用空间对象的MBR来近似表达空间对象，根据地物的MBR建立R树，可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点都对应着磁盘页D和区域I，如果结点不是叶结点，则该结点的所有子结点的区域都在区域I的范围之内，而且存储在磁盘页D中。如果结点是叶结点，那么磁盘页D中存储的将是区域I范围内的一系列子区域，子区域紧紧围绕空间对象，一般为空间对象的外接矩形。 n一个空间数据库由代表对象的的集合组成。n每个对象元组都有一个唯一的标识符，可通过这些标识符来检索对象元组。nR树的叶节点按以下形式记录索引记录的入口 比较典型的有R+树、R树、压缩R树等。 相关研究工作: R树结构n特点；
18、1根节点若非叶子节点，则至少有两个子节点； 2每个非根叶节点和非叶节点包含的实体个数均介于m和M之间； 3所有叶子节点在同一层次； R树兄弟结点对应的空间区域可以重叠，可以较容易地进行插入和删除操作。但正因为区域之间有重叠，空间索引可能要对多条路径进行搜索后才能得到最后的结果。 R树的空间分布图 Bloom filternBloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false po
19、sitive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。n由一个很长的二进制向量数组和一系列随机映射函数组成，n它只需要哈希表 1/8 到 1/4 的大小就能解决同样规模的集合的查询问题 Bloom filterBloom filter nBloom filter的本质是哈希计算，不同之处在于Bloom filter对同一数据使用多个哈希函数进行多次哈希，将结果保存在同一个向量数组中，n所以Bloom filter在达到相同的功能的情况下比原始的哈希结构更节约存储空间。nBlo
20、om filter算法的一个缺点在于查询一个元素是否在集合S上可能存在失误定位(False Positive) n集合表示和元素查询集合表示和元素查询n下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。Bloom filtern为了表达S=x1, x2,xn这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到1,m的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1ik）。注意，如果一个位置多
21、次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。 Bloom filtern在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1ik），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。 算法算法Bloom filter Bloom filterRBF索引结构 n从B树演变而来的R树结构，能有效地支持多维范围查询。n但是，R树不能有效地支持点查询。因为成员查询只能在叶子节点
22、上进行，相应的操作将导致查询效率很低。n然而，Bloom filter是一种空间利用率高且能有效地支持点查询的结构。RBF索引结构n一种叫做RBF的新的空间存储结构来存储多维元数据，n基本思路是是扩展经典的R树结构，n将Bloom filter插入到每个R树结点上来支持点查询，n维持多维范围信息并实现空间效率 RBF索引结构面向数据更新的结构设计和分析 nR树更新 n基于R树的索引在商业上得到广泛应用和发展，n但是它在频繁更新操作时性能低下。nR树及其变体在空间索引结构中占据主导地位，R树更新 n传统的空间索引的研究主要考虑静态数据，n只关注高效的查询处理，R树的更新性能很差，n不能直接用于频
23、繁更新的应用环境R树更新n存储系统下元数据的更新是很频繁的，n直接对索引的修改会产生大量的磁盘操作并可能引起索引结构的不平衡。n已经存在的各种基于R树索引的更新机制主要采取的是自顶向下模式 减少更新操作的方法 n位置预测位置预测n一种减少对象更新操作次数的策略是采用线性函数来表示移动对象的位置，n保存对象的运动特性，包括当前位置和速度参数等，n通过这些数据可以预测将来一段时间后的位置 减少更新操作的方法n容忍更新容忍更新n减少更新次数的另一种策略是容忍更新。并不是每次更新都需要一个至上而下的删除操作和插入操作。n当一个对象的新位置没有移出原来的MBR，换句话说就是该对象还在同一个叶子节点内时，
24、n只要修改对应叶子节点的数据信息即可，不需要删除后插入，也不可能引起分裂和合并操作 延迟更新 n更新操作包括删除和插入两个步骤，延迟更新也包括延迟删除和延迟插入两个方面。n延迟删除的策略是将更新信息立即插入，而旧的对象信息不会立即删除，n而是使用某种策略将未删除的索引信息缓存起来以便区分新旧数据，直到缓冲区满或者其它情况下才进行删除操作 批量操作nR树的批量插入策略是当前研究的热点之一。n其中STLT (Small-Tree-Large-Tree) 技术，n首先利用输入数据集建立一棵小R（Small tree）树，n然后将小R树插入到原有的大R树（Large tree）中 批量操作nGBI（G
25、eneralized Bulk Insertion）技术利用聚类算法将输入数据集分割为多个空间上接近的数据组，n为每个数据组建立R树结构，n最后将这些R树结构批量插入到目标R树中 多版本文件更新系统 nVersioning文件系统保存被修改的文件之前的版本，来实现用户误操作以及系统错误后的数据恢复。nVersioning文件系统存在的主要问题是不能有效地保存大量的version，version数据消耗大量的存储空间，n对version的删除的策略，恢复系统时version的选择问题等 多版本文件更新系统nCedar采用简单的version策略来帮助客户在误操作后恢复数据。n最近的Elephan
26、t文件系统提供了一系列的version选项，n用来保存对用户最为重要的文件的version。多版本文件更新系统nCVFS提出两种有效节省空间的version元数据结构，n对于inodes和indirect blocks采用Journal-based元数据，n而对于目录采用Multiversion B树，有效地节省了version占用的空间。多版本文件更新系统nCausality-based versioning结合causal relationship和versioning技术，n通过causal connection使得version更具意义，n提出新的在何时创建version的算法；n通过
27、causal relationship定位version，能够更有效的在错误后恢复到正确的version 面向预计算的元数据组织结构数据立方体 n数据立方体（Data Cube）是分析数据仓库数据的基本单位，是联机分析处理（On-Line Analytical Processing, OLAP）中的主要对象，n是一项可对数据仓库中的数据进行快速访问的技术。n数据立方体是一个数据集合，通常由数据仓库的子集构造，并组织和汇总成一个由一组维度和度量值定义的多维结构。n数据立方体提供一种便于使用的查询数据机制，响应时间短 数据立方体n数据立方体是多维数据库的基本结构，n并作为在多维数据库上定义的所有操
28、作符的输入输出基本单位。n将它定义为一个四元组，这四个组件分别表示数据立方体的特征 数据立方体n在典型的OLAP应用中，存在一个中心关系或数据集合，称作事实表。n事实表代表感兴趣的事件或对象。n事实表通常有几个表示维的属性和一个或多个度量属性，n这些度量属性一般是用户想要查询到的一些值 维数据立方体表示 数据立方体的计算 n数据立方体的计算是数据仓库实现的一项基本任务，数据立方体计算也称为数据立方体的物化（Materialization）n简单的说，它是将常用的查询按照各自的属性分组（Group by）提前计算出结果并保存起来，这样在执行查询时直接利用保存的结果来返回查询结果。n数据立方体的全
29、部或部分预计算可以大幅降低响应时间，提高查询效率，提高联机分析处理性能 预先计算任何方体，即完全立方预先计算任何方体，即完全立方体物化（体物化（Full Materialization） n完全物化优点：n可以对提出的任何查询快速响应，快速返回预计算好的结果，n不用在线等待计算结果，提高交互性。n缺点：完全物化时间复杂度是维度的指数，随着维度的增大，将发生困难。预先计算任何方体，即完全立方预先计算任何方体，即完全立方体物化（体物化（Full Materialization）n计算代价非常大，而且消耗大量的存储空间和系统资源，n同时当它的数据源发生改变时，为了保持数据的一致性，需要重新的计算所有
30、的方体。n当立方体的维度比较高时，对完全物化策略的立方体进行更新维护将耗费大量的时间和系统资源。完全物化主要有多路数组聚集方法 不预先计算任何的方体（不物不预先计算任何的方体（不物化，化，No Materialization） n数据立方体中每一个方体都不对聚集度量M进行预计算，n相当于只提供一个多维的索引，这样对于用户提交的查询，n需要在线计算结果，响应时间较长。不预先计算任何的方体（不物不预先计算任何的方体（不物化，化，No Materialization） n当总的数据量很大时，那查询的结果集也会很大，n在线计算将需要很长的时间，从而导致无法忍受的响应时间，n在海量数据情况下，该策略是不可取的 部分物化部分物化n提供了存储空间和响应时间的有效折衷。替代计算完全立方体，n可以计算立方体的一个子集，或计算由各种方体的单元组成的子立方体。n优点是节省了大量的计算时间和存储空间；n缺点是只能命中大部分查询而且结果可能不太精确，对于没命中的查询需要在线计算 部分物化部分物化n在许多情况下，相当多的立方体空间可能被大量具有很低度量值的单元占据。n这是因为立方体单元在多维空间中的分布常常是相当稀疏的。部分物化部分物化n某一类型的文件非常少，这样的事件将产生少量非空单元，n使得其他大部分立方体单元为空。n在这种情况下仅物化其度量值大于某个最小阈值的方体（Group by）单元是很有用的
