Research on Distributed Index Cluster Based on the Hadoop
　　WANG Wei
　　(College of Information Science & Technology, Chengdu University of Technology , Chendu 610059, China;)
　　Abstract：Distributed system is a good solution for deal with the mass data, index is necessary for mass-level data query and retrieval. According to the traditional index to create and maintain efficiency is not high, design of a distributed indexing of cluster solution based on Hadoop. Use of the Hadoop distributed storage and computing capacity, and based on DHT (Distributed Hash Table) Distributed index algorithm, to make data inqury and retrival more efficient, by parallel processing separately on each node of the distributed index cluster.
　　Key words：mass data; hadoop; distributed index; DHT; cluster
　　1 引 言
　　随着信息化技术的发展，数据规模变得越来越庞大，以Internet上产生的数据为例， 在Facebook公司，每天处理的新数据量超过20TB，随着Facebook用户的不断增加以后要处理的数据会变的更加庞大。面对着如此的海量数据传统的单机存储数据变的不可行，分布式存储正是为了解决这些问题。Google在这方面的研究处于领先地位，在Google的发展过程中，用户的搜索需求是与日俱增的，Google不是靠购买大量昂贵的服务器资源来满足大量的搜索需求，而是根据需求慢慢的添加。Google使用自己的分布式存储文件系统GFS（Google File System）、MapReduce以及BigTable分布式数据库，只需使用廉价的Linux PC机组成集群就能处理各种用户需求。在分布式存储的环境下，传统的索引如顺序索引、树索引（B+树等）以及HASH索引等都会产生不同程度的问题。众多学者对此进行了长期的研究，提出了很多分布式索引理论，分布式哈希表算法为分布式存储提供了有效的理论方法。文中从海量数据的特点出发，通过分析常用索引算法，运用开源的hadoop技术设计了分布式索引集群系统。
　　2 分布式相关技术
　　2.1 分布式存储和计算
　　分布式存储和分布式计算是分布式系统中重要的两个方面。分布式存储就是将数据分散存储在多台独立的设备上。传统的网络存储系统采用集中的存储服务器存放所有数据，存储服务器成为系统性能的瓶颈，也是可靠性和安全性的焦点，不能满足大规模存储应用的需要。分布式存储采用可扩展的系统结构，利用多台存储服务器分担存储负荷，利用位置服务器定位存储信息，它不但提高了系统的可靠性、可用性和存取效率，还易于扩展。分布式计算是研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。
　　Hadoop是一个分布式系统基础架构，由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。利用集群来实现高速存储和运算。Hadoop作为一个开源项目，受到GoogleFS很大启发。Hadoop包括两个部分：Hadoop分布式文件系统（Hadoop Distributed File System，HDFS）和MapReduce编程模型，其中HDFS能为应用程序提供高吞吐率的数据访问，能对文件系统数据进行流式访问，从而适用于批量数据的处理。HDFS为文件采用一种"一次写多次读"的访问模型，从而简化了数据一致性问题，使高吞吐率数据访问成为可能。Map/Reduce是一种编程模型，主要用于大规模数据集的并行运算，MapReduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性；每个节点会周期性的把完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔，主节点记录下这个节点状态为死亡，并把分配给这个节点的数据发到别的节点。每个操作使用命名文件的不可分割操作以确保不会发生并行线程间的冲突；当文件被改名的时候，系统可能会把他们复制到任务名以外的另一个名字上去，从而避免副作用。
　　2.2 分布式哈希表算法
　　分布式哈希表(Distributed Hash Table)简称DHT，是一种分散式存储方法。这种网络不需要中心节点服务器，而是每个用户端负责一个小范围的路由，并负责存储一小部分资料，从而实现整个DHT网络的定址和存储。和中心节点伺服器不同，DHT网络中的各节点并不需要维护整个网络的资讯，而是只在节点中存储其临近的后继节点资讯，大幅减少了带宽的占用和资源的消耗。DHT网络还在与关键字最接近的节点上复制备份冗余资讯，避免了单一节点失效问题。
　　2.2.1 DHT的主要思想
　　DHT的主要思想是：首先每条文件索引被表示成一个(K, V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的描述信息。所有的文件索引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。这样节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节点要维护特定的邻居节点，以便路由能顺利进行。这个规则因具体系统的不同而不同。基于分布式哈希表（DHT）的分布式检索和路由算法所面临的一个问题是DHT仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。
　3 分布式索引集群的设计
　　在分布式系统中，数据是按分块的形式存储在集群的各个节点上，传统的数据文件都是以文件目录树来组织和管理。如Windows和Linux系统等都是用文件目录来管理数据，但是当数据以海量形式呈现时，传统的方法已经失效。使用HDFS可以分散存储超大规模数据，作为存储数据的基础。分布式索引首先需要解决的问题就是如何组织索引，目前研究较多的索引组织策略有局部索引策略、全局索引策略以及混合索引策略。局部索引组织策略是将所有数据以块进行划分，然后将得到的数据块分发给集群的不同节点，服务器为各自维护的数据建立局部索引表。在查询时需要把用户的请求转发给索引集群中的所有的节点。局部索引具有良好的查询性能和负载均衡水平，并且索引表的维护很简单。缺点是需要所有集群中的节点都参与查询处理，资源浪费较多且缺乏可扩展性。全局索引将数据按行分块，并把数据块分给的集群的不同节点。在查询时可将用户查询直接转发到维护相应索引片的集群节点。全局索引无需将请求转发给所有的集群节点，查询处理耗费资源较少，但负载均衡水平相对较低，而且由于全局索引往往分布在不同的服务器上，查询结果合并操作困难。混合索引希望能结合局部索引和全局索引。为查询比较频繁的数据创建全局索引，全局索引可以看作是局部索引的缓存，以提高整体查询效率。但局部索引或全局索引均存在查询效率不高的问题，随着分布式技术的发展，如何组织混合索引来提高检索速度是非常重要的。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）