海量数据分布式存储方案的分析与设计

中国科技论文在线海量数据分布式存储方案的分析与设计乔宇*作者简介：北京邮电大学08级研究生，主修数据仓库和数据挖掘专业.E-mail:[e-mail]（北京邮电大学信息与通信工程学院，北京100876）摘要：随着网络用户的不断扩大，企业内部网络数据、Internet上的数据、电子邮件,无数个不同的商用软件和数据库数据使数据量爆炸性增长，人们对网络的传输速度、数据的安全及可靠性有了新的认识。用户的数据，广泛地分布在很多地方，工作效率正在被数据传输的效率所限制。本文将研究一种海量数据的解决方案，用于对各种海量信息进行处理，从而使用户可以方便快捷的取得自己需要的信息。关键词：web2.0；海量数据处理；海量数据存储；海量数据索引中图分类号：TP311TheresearchanddesignofGreatCapabilityDataQiaoYu(BejingUniversityofPostsandTelecommunications,Beijing100876)Abstract:Asthedevelopmentoftheweb，allkindsofdatacomingfromallkindsofdomainssuchasusers,enterprise,interneteandE-mailmakethedatablastup.Thedataofusers,spreadedaroundthewholeworld,serverlyrestrictthetransferspeedoftherate.Inthispaper,wewilldiscussanewkindofwaytostoremessageandhelppeoplegettheirmessagewithhighspeed.Keywords:web2.0;massdataprocess;massdatastorage;massdataindexing0引言近些年来，博客（blog）、维基百科（wiki）、共享空间（spaces）等新型应用的兴起导致互联网内容的提供方式出现转变，催生了用户创造内容的web2.0时代到来，带动着视频应用、网络游戏、搜索引擎等互联网衍生业务迅速发展[1]。互联网正处于一个信息爆炸的时代。面对信息爆炸的互联网，如何去存储和处理所产生的海量数据，对诸如Facebook、YouTube等大规模互联网企业提出了巨大的技术挑战，同时也开启了广阔的研究空间[2]。互联网应用种类繁多，包括Facebook、MySpace为代表的社会关系网络、Flickr为代表的图片共享应用、Youtube为代表的视频共享应用以及以谷歌（Google）、雅虎（Yahoo）为代表的搜索引擎应用等[3]。这些互联网应用因为自己的应用特性不同，面对不断增长的互联网用户带来的不断增长的数据(视频、图片、博客等)所采用的技术路线不尽相同。但是，这些技术路线从本质上可以分为两个方面：海量数据的存储管理技术以及针对海量数据的处理技术[4]。本文将根据海量数据设计出一种数据存储方案，并且数据处理的解决方案。这种方案在笔者所完成的北京市中小企业分析系统中得到了应用。数据存储方案分析当遇到海量数据时，将所有数据存储到一台服务器上变成了一个较难完成的事情，随着数据的增加，要求服务提供厂商提供更大的存储设备来满足这种要求，但是由于科技的限制，这种可以无限扩张的设备并不存在[5]。退而言之，就算存在这么一台设备可以存储所有的信息，那么用户在一台服务器上进行数据的索引查询也会是处理器变的不堪重负。分布式[6]成为了解决这种问题的一个很好的解决方案。使用分布式的解决方案存在着一系列的优点：1）可以使数据分散到不同的存储设备上，这样存在着很多好处，加入数据来源于世界各地，数据可以存放到数据来源地的镜像上，这么使用者在连接自己本地的数据时会享受到较好的速度；2）针对每一台存储设备，可对其进行单独的建立索引，从而减轻主服务器的负担。但是分布式进行数据的存储仍然还是存在很多问题需要解决的，例如我们如何去分配数据，使他们存储在不同的分布式文件存储系统上。如何解决动态的添加或减少文件存储系统时服务器对已存储数据的影响。1.2数据存储方案的初步设计如何将海量数据分配处理，哈希化[7]是一个很好的解决方案，因此，数据存储的方案被初步设计为使用将数据哈希处理后根据哈希结果选择对应的存储服务器进行存储的方案。假设有N台服务器，将服务器进行编号，其中M(i)表示编号为i的服务器。则将数据存储的初步设计方案设计成为：1)根据数据来源的IP:m，将其转换为16进制整数m(16),然后根据相应的方法，转化成为十进制整数m(10)；2)对于m(10)进行取模运算，即m(10)%N,将结果记录为t;3)将来自于IP：m的数据存储到服务器M(t+1)的中。这是数据存储方案的最初设计，但是这种设计的存储方案存在着很多问题：1)数据的存储并非是按照IP进行的，这样，同一地区上传的内容有可能被存储在不同存储器，如果数据来源和服务器分布是世界范围的，则可能导致a地区的数据被分配到b地区的文件存储系统，这对于数据的获得速度有着很大的影响[8]，下图1为IBMRational在进行用户调查时统计的中国用户对来自各地信息需求，其中U标示us，E标示Europe，而O则表示世界其他各地的信息。由此可见，将数据进行合理的分配对用户获得较好的用户体验有很大帮助。图1中国用户对世界各地信息获取量Fig.1Thetableofinfomationaroundworldgetbychineseusers2)如果服务器的数量增加或者减少时，之前已经存储的信息将如何处理。这是一个急需解决的问题，随着信息的不断膨胀，我们不能保证现有的存储系统会满足用户的使用，所以，我们的文件存储系统必须具备动态的添加或者减少存储系统的功能[9]。根据以上问题，我们提出了对现有存储方案的解决计划。1.3数据存储方案的优化策略针对初步设计中不能解决文件存储系统不可以动态的添加或者较少的问题，提出了一个一种优化策略。假设原有N台文件存储服务器而现在需要添加n台文件存储服务器。如果将所有数据重新取出进行哈希化运算，必然可以得出结果，但是会进行大量的运算，下面这种方案对运算量进行分析：假设当前每台文件服务器的信息存储量是m份，则我们需要N*m取出操作，同时有需要将N*m进行哈希化算法同时分别存入(N+n)台服务器中；由此看出，进行挂载新的服务器时，需要各进行N*m次存、取、运算操作，这对服务器的要求是相当高的。所以动态调整哈希值[10]是我们的解决方案之一：1)在主处理服务器中建立一个栈型结构，每次动态的添加节点后，我们就会将添加点后的文件存储系统数量入栈；2)当有新的节点入栈时，根据当前栈顶的值进行哈希化数据分配，然后建立数据索引。这是数据分配的优化方案，也许有人会质疑这个主服务器中栈结构存在的意义，其实栈结构存在是为了在数据查询和操作时方便服务器能够在正确的存储系统中进行获取，本文将在之后的章节讨论文件的存储。尽管优化方案解决了动态添加服务器的问题，但是始终有一个问题没有解决，就是如何能保证数据可以按照自己所属的IP区域进行存储[11]，所以这个方案仍需要进行优化，根据这种问题，我们将进一步提出优化方案。1.4数据存储最终解决方案如何让我们的数据可以存储到最近的文件存储器上，是本方案需要解决的问题之一。同时，是否存在对动态添加数据存储服务器[12]更好的方法也是我们在此方案要解决的问题。从第一个问题出发，如何使文件存储服务器和IP地址取得关联是解决此问题的关键。从计算机网络的知识可知，计算机网络的IP地址可以转换成一个有限的整数区域(假设长度)，可以从这个角度出发来解决相应的问题。1)将数据转换成一个环形结构，其中有N个节点，其中每个节点代表一个IP地址。2)将服务器的IP地址在环形结构上标示出来；3)当有新的数据出现的时候，在环形节点上将数据节点m表示出来，同时顺时针旋转，当遇到第一个服务器节点的时候，记录为存储服务器n,则将所有来自于m的数据全部放入服务器n进行存储。下图为这种存储方案的一个示例。当来自左侧的键值IP的节点有数据需要存储时，主控制服务器就会顺时针查找，当找到node3时，服务器停止查找，然后将数据存储入node3。以此论推，我们可以完成对所有数据的存储，并且保证数据存储到距离自己IP地址较近的位置，这在一定程度上解决了数据不能存储到距离自己物理位置较近的文件存储服务器的问题[13]。图2改进型文件存储方案示意图Fig.2Theschematicofimproveddata-storingscheme这种解决方案在动态添加服务器上也更加科学和合理：1）通过图2可以发现节点2和节点4之间有较多的数据存储，我们可以在两个节点的中间位置新加一个文件存储服务器；2）将节点4的数据进行重新非配，将属于新节点的数据取出并存入并放入到新节点中，这样就动态的添加了新的数据存储服务器。3)通过这么添加数据存储服务器，可以发现，这种解决方案不仅可以动态的添加文件存储节点，更重要的是，主控服务器可以根据各个文件当前存储的状态和各个节点上传新数据的频度，选择合适的节点进行新的文件存储服务器的存储，这样可以最大限度的减少服务器的负担，实现文件资源的平均分配；同时主控服务器还可以根据当前的状况，关闭不活跃的文件存储器，在一定程度上可以减少企业的运营成本。我们可以分析下这么操作的复杂度，假设节点4存有x条数据，其中y条属于新节点，则我们的主服务器再添加时需要检测节点4的所有数据记录，同时去除属于新节点的y条记录并将其放入新的节点中，这样的主服务器的操作次数为x比较操作以及y条读写操作。通过上面的分析可以知道，这种文件存储的解决方案可以科学的解决动态添加减少节点的问题，节点可以被添加到数据出来最多的节点之前，减小文件存储服务器的负担[14]；另一方面这种文件存储方案还可以解决了如何让数据存储到距离自己物理位置较近的区域的中国科技论文在线方案，这在很大程度上帮助了用户在以后去获得自己的数据以及自己周围人员上传共享的资料数据。由上可知，这种解决方案可以作为最优的文件存储解决方案进行文件的存储，我们可以建立这样的一个数据存储模型[15]。图3最优方案下的文档存储模型Fig.3TheStoragemodeloftheoptimalstrategy2基于数据存储方案的数据操作分析在提出的最佳文件存储解决方案后，同样需要证明该方案适合服务器快速的对其进行查找同时取得正确的数据。我们将对方案的三个阶段进行分析，得出一个比较好的解决方案，同时进行权衡分析，得到最佳的存储和处理的解决方案。假设文件存储服务器的数量为N,数据存储记录为M,同时需要新增的服务器数量为n，为了简化分析过程假设所有来自客户端的请求都由一个主控服务器进行处理。2.1数据存储初步解决方案数据操作性能分析在初步解决方案，假设主控服务器收到一个服务器查询请求，主控服务器会先将数据进行哈希化处理，同时做取模运算，根据取模值去相应的服务器进行处理，故可以得到这种方案下数据查找的时间复杂度为o(1)。在此方案中，当需要添加新的服务器时，主控服务器需要将所有的数据从原有节点中取出，然后进行哈希化计算，然后将他们重新放入新的数据存储器中，故操作次数问3*（n+m），所以这种方案下数据添加数据服务器的时间复杂多为o(n+m)。2.2数据存储优化解决方案数据操作性能分析在优化解决方案中，假设主服务中栈结构的深度为t，则当主控服务器