云计算环境下的数据索引方法.doc
《云计算环境下的数据索引方法.doc》由会员分享,可在线阅读,更多相关《云计算环境下的数据索引方法.doc(12页珍藏版)》请在咨信网上搜索。
1、云计算环境下的数据索引方法1.摘要云计算和大数据时代的到来使得计算机产生和处理的数据量急剧增加。为了方便云环境下的数据存储和检索,必须为数据建立索引。传统的索引方法,如B+树等,在传统的数据库系统中已经得到了深入的研究和广泛的应用。但是云环境下,由于数据模型发生了根本改变,传统的索引技术已经无法直接应用在云计算环境中,找到一种适合特定云应用下的索引结构变得越来越重要。为了适应索引结构的新需求,前人已经进行了很多研究,探索出了适应于云应用环境下的数据索引技术。本文综述云计算环境下的索引技术,对比各种索引技术的优缺点,并指出各种索引技术的应用范围,为针对特定的应用环境选择合适的索引技术指出方向。关
2、键字:云计算; 索引结构; 分布式索引AbstractThe era of cloud computing and big data have witnessed the sharp increase in the amount of data generated and processed. In order to facilitate data storage and the retrieval of cloud environment, an efficient index must be created. Traditional indexing methods, such as B+
3、 trees, which are commonly used in existing database management system, have already been extensively studied. But in cloud environment, data model changes fundamentally, the traditional indexing technology cant be applied directly to applications in the cloud computing environment. To find a suitab
4、le index structure under specific cloud applications is becoming increasingly important. In order to meet the new demands of the cloud environment, our predecessors have conducted a lot of research, many indexing technologies that can be applied in cloud computing environment have been invented. Thi
5、s paper conducts a comprehensive survey on the formerly studied indexing technology of this kind and gives some guidance on how to choose appropriate indexing schema for specific application.Keywords: cloud computing; index schema; distributed index;2.概述云计算是一种利用互联网实现随时随地、按需、便捷地访问共享资源池(如计算设施、存储设备、应用程
6、等)的计算模式计算机资源服务化是云计算重要的表现形式,它为用户屏蔽了数据中心管理、大规模数据处理、应用程序部署等问题通过云计算,用户可以根据其业务负载快速申请或释放资源,并以按需支付的方式对所使用的资源付费,在提高服务质量的同时降低运维成本。目前许多大型公司都构建了自己的数据中心,一些IT公司如百度等,还提供了针对中小企业的企业级的云存储解决方案以及针对终端用户的个人云存储解决方案,收到了很好的效果。索引技术是数据统一访问的基础,索引构建的优劣将直接影响到数据的统一访问。索引最早出现在文献系统中,它是将文献系统中的内容,按照可检索的顺序排列成条目表达出来。由于索引可以大大加快查询速度,因此被广
7、泛的应用于于书籍、文献资料的查询。随着计算机技术的出现,索引技术也有了进一步的发展,特别是数据库系统中的索引技术。传统数据库的索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可以大大提高数据库中数据的查询和处理速度。在云计算环境下的,索引往往采用二级索引结构即全局索引以及局部索引。全局索引的使用,体现了分治策略的思想。全局索引由整个集群的节点共同维护,全局索引是整个应用数据的一个概要描述,主要用于将数据的查询修改等操作定位到集群中的特定节点,减轻集群中传递查询消息的网络传输量,并减轻集群中不包含查询信息的节点的处理工作量。局部索引是由单个集群中的节点维护的,针对本地数据的索引,局部
8、索引可以采用与传统数据库索引类似的解决方案。云环存储环境中的数据最终都保存在单个节点上,局部索引的使用,方便了集群中的节点管理自己的本地数据,减少相应查询和修改的IO和计算时间消耗。根据全局索引管理方式的不同,目前云计算环境下分布式存储系统的数据索引主要分为两类:集中式索引和分布式索引,集中式索引一般采用单个节点管理全局索引,目前流行的分布式存储系统如Google文件系统1(GFS)和Hadoop分布式文件系统2(HDFS)都是使用集中式索引结构。在集中式下,数据索引将占用管理节点极大的内存空间,与此同时,单一的管理节点存在单点失效的问题,且容易成为系统性能瓶颈。分布式索引机制3-6将全局索引
9、分布在集群中的多个节点上,由集群中所有包含了全局索引数据的节点共同协调完成处理请求时的节点定位工作,有效避免了负载过重和单点失效的问题。目前使用分布式索引方式的存储系统有Amazon公司的Dynamo3和Yahoo!的PNUTS等。另外,针对索引的维度数的不同,索引又可以分为一维索引和高维索引。一维索引针对记录中的某一个属性或合成一个属性的属性组建立索引。针对一维索引的查询只支持针对索引属性的单点查询或区间查询。多维索引可以针对记录的多个属性建立索引,支持针对多个属性的点查询、区间查询、K近邻等操作。接下来的章节安排如下:第3章、第4章和第5章分别对集中式索引方式和分布式索引方式以及复合式索引
10、方式中的各个有代表性的实现做详细的介绍,介绍各自的工作机制,找出他们优点和存在的问题,并给出适用范围。第6章总结全文,提出需要根据特定分布式应用环境寻找合适的索引方案的观点,并对在具体应用环境下选择索引方案时的注意事项做简要的介绍。3.集中式索引机制3.1 Hadoop File System文件目录Hadoop File System文件目录2是一种典型的集中式索引方式。HDFS集群由名称节点和数据节点两类节点组成。名称节点管理着文件系统中的所有元数据信息,这些元数据包括文件名、访问控制信息、副本个数、块与其副本块的映射信息等等。数据节点存储着文件的数据块,维护着本数据节点中的数据块的索引信
11、息列表,并定期以心跳形式向名称节点发送数据块的信息列表。 图1.Hadoop文件系统结构HDFS 文件系统架构是采用管理者-工作者(Master-Slave)的结构,也就是一个名称节点(Master)和多个的数据节点(Slave)。名称节点其实就是一个主服务器,负责管理和维护集群中文件系统的全局索引信息,主要向客户端提供创建、打开、删除和重命名文件或目录的功能。数据节点是文件系统的工作者,主要是存储文件,管理分布式文件系统存储在本地的文件块索引信息,并负责处理对数据块的读写请求。一般是一台计算机作为一个数据节点。实际上一个大文件存储在 HDFS 文件系统中时,被分成一个或者多个数据块(默认为
12、64MB),这些块受名称节点的调度被分布存储在指定的数据节点上,数据节点在名称节点调度下对块进行创建、复制及删除操作(修改操作在 HDFS 中不支持)。数据节点也要定期向名称节点上报心跳,名称节点响应心跳来控制数据节点。心跳是指数据节点向名称节点传递索引信息。在HDFS这种方式下,名称节点存储了整个文件系统的索引信息,所有的外部访问请求都要先通过名称节点才能定位到数据节点,而后由数据节点在本地文件索引中找到响应的数据块,服务外部请求。为了提高文件访问的速度,名称节点不仅需要有足够的内存将文件目录信息保留在内存中,而且还要有足够的带宽和处理能力响应所有的文件请求。当文件系统存储信息量上升,或者文
13、件访问请求量增加时,名称节点容易成为整个系统的性能瓶颈,而且整个系统对名称节点的故障敏感,存在单点失效的问题。这种方式的优势在于存在一个节点拥有被索引对象的全局信息,可以有效避免不必要的查询开销。4.分布式索引机制4.1 分布式Hash表(HDT)分布式散列表3(简称DHT)是分布式计索引中的一类,以键值对的形式组织资源的索引,其中K键为资源的Hash码,值就是资源的存储位置索引。每个存储在索引系统中的资源位置标识都被映射到一个唯一的Key值上。分布式Hash表用来将一个关键值(key)的集合分散到所有在分布式系统中的节点,以选择索引的存储节点。并且可以有效地将消息转送到唯一一个拥有查询者提供
14、的关键字的节点(Peers)。这里的节点类似散列表中的存储位置。分布式散列表以键值对的形式组织索引,定位资源。在收到资源查询请求后,系统先用分布式Hash函数确定资源的key。然后使用分布式Hash表全局索引定位存储了资源索引信息的节点,返回节点编号。随后请求的发出者再到相应的节点查询局部索引,确定资源的位置。一致性Hash是MIT提出的对分布式散列表的算法实现,它的提出使得DHT在P2P环境中真正得以应用。目前一致性Hash有多种实现算法,其中最具有代表性的包括Chord、CAN、Tapestry和Pastry。本文以Chord为例来描述构建数据中心存储节点间覆盖网络的一致性Hash算法。C
15、hord采用环作为其静态拓扑图,系统中每个节点和关键字的标识符都是一个m位的二进制串,分别通过对节点IP地址和关键字散列运算获得,所有节点根据标识符大小顺时针构成一个环形的拓扑结构。Chord环上所有节点都维护以下邻居信息:前驱节点predecessor(n)、后继节点successor(n)和finger表。Chord实现了两种对关键字是的重要操作:关键字插Insert(k)和关键字查询Lookup(k)。Insert(k)实现以下过程:对k进行散列运算,设idHash(k),Chord将是插入到其在Chord环上的后继节点s=successor(id)(环中沿顺时针方向第1个不小于id的节
16、点)上。Lookup(k)实现以下过程:资源查询时每个节点都通过查询指针表,将查询请求转发到离k最近的节点上图1是优一4的Chord网络,网络中有5个节点:0,1,5,8和1Hash(k)=10的后继节点是11,因此Insert(k)=11图l给出了节点1和节点5的指针表,虚线给出了从节点1开始对k的查询过程,消息最终停止于节点11,即Lookup(k)一11。图2.Chord示意图分布式散列表(DHT)数据索引通常是为了拥有极大节点数量的系统,而且在系统的节点常常会加入或离开(例如网络断线)而设计的。在一个结构性的延展网络(overlay network)中,参加的节点需要与系统中一小部份的
17、节点沟通,这也需要使用分布式散列表。分布式散列表索引技术可以用于创建更复杂的服务,例如分布式文件系统、点对点技术文件分享系统、合作的网页高速缓存、多播、任播、域名系统以及实时通信等。分布式散列构建的两级索引中,所有的资源都可以用一个唯一的主键来标示,这种索引往往只支持单点查询,即通过资源的键定位资源所在的位置。然而云端用户提交的数据查询请求往往包含更加复杂的查询模式,如多维查询(multidimensional query)和区间查询(range query)例如在YouTube等在线视频应用中,一个视频数据往往需要用挖维向量(,点z,也一:)表示,每一维向量分别表示视频的维属性,如主题、作者
18、、创建日期、清晰度等查询请求Q=(20110101Date20110120,480Definition720)表示用户需要获取日期和清晰度两维元数据属于上述区间内的所有视频。由于分布式Hash表中的主键只包含一维元数据,因此其分布式索引机箭无法支持多维查询;与此同时,分布式Hash表为了保证数据分布的负载均衡在散列过程中会破坏数据的主键顺序,查询区间内的两个数值相邻的主键在散列运算后可能产生两个差值很大的标识符,进而被分配到两个存储节点上,因此DHT的分布式索引机制无法支持区间查询。4.2 M-Index索引针对云计算环境下分布式存储系统的数据索引不支持复杂查询的问题,朱夏4等人提出了一种多维
19、数据索引机制M-Index,采用金字塔技术(pyramid-technique)将数据的多维元数据描述成一维索引,在此基础上首次提出前缀二叉树(prefix binary tree,PBT)的概念,通过提取一维索引PBT有效节点的前缀作为数据在存储系统中的主键。数据根据主键和一致性Hash机制发布到存储节点组成的覆盖网络。设计了基于M-Index的数据查询算法,将复杂查询请求转换成一维查询键值,支持多维查询和区间查询等复杂查询模式。4.2.1索引降维云端用户提交的数据在存储系统中一般具有多维元数据属性。在一致性Hash过程中数据的主键只能包含某一维元数据,这导致了诸如DHT等分布式存储索引结构
20、无法支持多维查询其解决思路是利用金字塔技术构建多维数据索引M-Index,将表示元数据的d维向量M(v0,v1,vd-1)降维成一维索引id。M-Index能够保证多维元数据在降维过程中不丢失各维信息,从而保证数据查询结果的完备性.M-Index以点P(0.5,0.5)为中心点,将d维空间0,1d等分成2d个子空间,同时将子空间命名为金字塔,将点P命名为金字塔的顶点,将d-1维空间命名为金字塔的底面。MIndex对金字塔的编号规则如下:在d维空间中任意一维向量D。(Omd)都会与2个金字塔底面垂直,如果金字塔内任意一点的第m维坐标u0d)维的坐标差值hv=0.5-vi,再计算V的一维索引idv
21、=i+hv。4.2.2处理区间查询由于一致性Hash可能会破坏一维索引值域区间idmin,idmax内的数值顺序,因此以一维索引id。为主键的存储系统仍然无法实现对区间查询的支持然而我们观察发现,数值临近的二进制数具有共同前缀的概率往往较高,考虑将区间idmin,idmax划分成n+1个子区间0,11,2,n,n+1,属于区间i,i+1内的一维索引选择区间上下界的二进制值i2和i+12的共同前缀prefixi=PREFIX(i2,i+12)作为主键。据查询过程根据查询区间与子区间的交集将区间查询转化成关于prefixi的单值查询与此同时,为了保证数据发布的负载均衡,作者选择共同前缀作为主键的数
22、据量动态调整子区问大小,并采用树形结构管理子区间的共同前缀。4.2.3复杂查询请求转换根据查询请求的维数和区间,将查询请求分为4类:一维单值查询(Q1)一维区间查询(Q2)、多维单值查询(Q3)和多维区间查询(Q4),其中Q1Q3。均可看作Q4的特例。d维区间查询请求的形式化定义为:Q4=q0min,q0max,qjmin,qjmax,qd-1min,qd-1maz基于主键的存储系统显然无法直接识别诸如Q4的复杂查询请求,因此和数据的索引过程类似,需要根据M-Index将查询请求转换成存储系统可以识别的一维单值查询首先引将Q4转换成一维区间查询请求Q2在此基础上根据PBT将Q2转换成一维单值查
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 环境 数据 索引 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。