分布集群范文（精选5篇）
分布集群 第1篇
随着Inernet数据规模的急剧增加、应用类型的丰富, 海量数据的存储和分析处理给传统的系统框架带来巨大挑战, 在这种潮流和趋势的推动下, 云计算应运而生。Hadoop是Apache组织的一个开源分布式系统架构, 广泛地运行于多种平台上, 是云计算的实现。它为应用程序提供了一组稳定可靠的接口, 有着低成本、可扩展性、可伸缩性、高效性、高容错性等优点。
2 Hadoop平台搭建及容错验证
2.1 集群搭建及运行
机器说明:sc706-26、27、28、29共4台机器, IP地址分别为:192.168.153.89、90、91、92, 操作系统是fedora12, jdk版本为jdk-6u19-Linux-i586, hadoop的版本是hadoop-0.20.2, 其中sc706-26作为NameNode、JobTracker, 其余三台作为DataNode、TaskTracker。
(1) 机器间的Ping通及新建hadoop用户:
配置NameNode上的/etc/hosts文件, 加入四台机器的IP地址和机器名, 保证相互之间可以Ping通。同时, Hadoop要求所有机器上hadoop的部署目录结构要相同, 并且有一个相同用户名的账户, 设定默认路径为:/home/hadoop。
(2) ssh设置及关闭防火墙。
Linux系统安装后, 默认会启动sshd服务。建立ssh无密码登录时先执行命令[hadoop@sc706-26 ～]$ ssh-keygen-t dsa-P ''-f ～/.ssh/id_dsa, 在～/.ssh/下生成两个成对出现的文件:id_dsa和id_dsa.pub, 然后将id_dsa.pub文件追加到DataNode上的authorized_keys, 命令如:cat id_dsa.pub >> ～/.ssh/authorized_keys, 注意:NameNode上也要追加, 完成后必须修改NameNode和DataNode上的.ssh和authorized_keys的权限。
Root身份service iptables stop关闭NameNode和DataNode的防火墙, 注意重新开机启动hadoop前都必须确保防火墙处于关闭状态。
2.2 高容错性验证
Hadoop将硬件的故障作为常态, 通过块的冗余存储机制保证数据的高可靠性。在大多数情况下, 块的副本系数 (replication) 为3, HDFS的存放策略是将一个副本存放在本地机架的节点上, 一个副本放在同一机架的另一个节点上, 最后一个副本存放在不同机架的节点上。
验证实验是基于副本系数分别设置为1和3时对产生的2000000条数据运行排序, 在其过程中人为的关闭一个节点, 使之失效, 对比验证job是否可以成功完成。数据生成命令:hadoop jar/home/hadoop/hadoop-0.20.2/hadoop-0.20.2-examples.jar teragen 2000000 terasort/input-1, 运行排序命令:hadoop jar hadoop-0.20.2-examples.jar terasort terasort/input-1 terasort/output-1。
(1) dfs.replication=1验证。
副本系数设为1, 说明存放在HDFS中的文件每个块只存储了一次, 当块损坏时程序将无法正常读取数据, job失败。
正常情况下, job运行完毕如图1:
通过Web接口查看运行过程无失效节点和异常, 如图2示:
某一节点失效情况下, 即将一个节点关机, 抛出异常, job失败如图3:
通过Web接口查看失败job, 截图如图4:
(2) dfs.replication=3验证。
设置副本系数为3, 即每个文件的分块都有三个复制备份, 当某些数据块因硬件故障出错时, HDFS将通过复制完整的副本来产生一个新的数据块进行治愈, 并且使数据块的副本数恢复到预期设定的数量, 保证了数据的高可靠性, 使job仍可以成功运行。
仍采用dfs.replication=1时的job实验, 运行时关闭一个节点, job仍然正常运行, 并成功完成排序任务, 如图5所示。
从图3和图5可以看出, 当副本系数设置为1时, Hadoop集群的数据没有进行冗余备份, 假设某个节点失效, 抛出异常, 导致提交的作业无法正常完成。然而, 当副本系数设置为3时, HDFS利用其冗余机制对数据块进行了备份, 无论硬件何时出现故障, 数据的可靠性得到了保障, 有着高容错性, 保证了job的成功运行。
3 结论
通过实验, 我们验证了Hadoop的冗余机制, 这种机制保证了存放在HDFS中的数据的高可靠性和数据的完整一致性, 说明了集群具有高容错性, 为job的正常运行提供了保障。
参考文献
[1]White T.Hadoop, the definitive guide[M].O'Reilly Media, Inc, 2009.
[2]Apache Hadoop[EB/OL]. (2009-09-12) .http://ha-doop.apache.org/.
[3]Taiwan Hadoop Forum[EB/OL].http://forum.hadoop.tw/2009.
分布集群 第2篇
1 分布式相关技术
1.1 分布式存储和计算
分布式存储和分布式计算是分布式系统中重要的两个方面。分布式存储就是将数据分散存储在多台独立的设备上。传统的网络存储系统采用集中的存储服务器存放所有数据,存储服务器成为系统性能的瓶颈,也是可靠性和安全性的焦点,不能满足大规模存储应用的需要。分布式存储采用可扩展的系统结构,利用多台存储服务器分担存储负荷,利用位置服务器定位存储信息,它不但提高了系统的可靠性、可用性和存取效率,还易于扩展。分布式计算是研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后把这些部分分配给许多计算机进行处理,最后把这些计算结果综合起来得到最终的结果。
Hadoop是一个分布式系统基础架构,由Apache基金会开发。用户可以在不了解分布式底层细节的情况下,开发分布式程序。利用集群来实现高速存储和运算。Hadoop作为一个开源项目,受到Google FS很大启发。Hadoop包括两个部分:Hadoop分布式文件系统(Hadoop Distributed File System,HDFS)和Map Reduce编程模型,其中HDFS能为应用程序提供高吞吐率的数据访问,能对文件系统数据进行流式访问,从而适用于批量数据的处理。HDFS为文件采用一种"一次写多次读"的访问模型,从而简化了数据一致性问题,使高吞吐率数据访问成为可能。Map/Reduce是一种编程模型,主要用于大规模数据集的并行运算,Map Reduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性;每个节点会周期性的把完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔,主节点记录下这个节点状态为死亡,并把分配给这个节点的数据发到别的节点。每个操作使用命名文件的不可分割操作以确保不会发生并行线程间的冲突;当文件被改名的时候,系统可能会把他们复制到任务名以外的另一个名字上去,从而避免副作用。
1.2 分布式哈希表算法
分布式哈希表(Distributed Hash Table)简称DHT,是一种分散式存储方法。这种网络不需要中心节点服务器,而是每个用户端负责一个小范围的路由,并负责存储一小部分资料,从而实现整个DHT网络的定址和存储。和中心节点伺服器不同,DHT网络中的各节点并不需要维护整个网络的资讯,而是只在节点中存储其临近的后继节点资讯,大幅减少了带宽的占用和资源的消耗。DHT网络还在与关键字最接近的节点上复制备份冗余资讯,避免了单一节点失效问题。
1.2.1 DHT的主要思想
DHT的主要思想是:首先每条文件索引被表示成一个(K,V)对,K称为关键字,可以是文件名(或文件的其他描述信息)的哈希值,V是实际存储文件的节点的描述信息。所有的文件索引条目(即所有的(K,V)对)组成一张大的文件索引哈希表,只要输入目标文件的K值,就可以从这张表中查出所有存储该文件的节点地址。然后,再将上面的大文件哈希表分割成很多局部小块,按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上,使得每个节点负责维护其中的一块。这样节点查询文件时,只要把查询报文路由到相应的节点即可(该节点维护的哈希表分块中含有要查找的(K,V)对)。这里面有个很重要的问题,就是节点要按照一定的规则来分割整体的哈希表,进而也就决定了节点要维护特定的邻居节点,以便路由能顺利进行。这个规则因具体系统的不同而不同。基于分布式哈希表(DHT)的分布式检索和路由算法所面临的一个问题是DHT仅支持精确关键词匹配查询,无法支持内容/语义等复杂查询。
2 分布式索引集群的设计
在分布式系统中,数据是按分块的形式存储在集群的各个节点上,传统的数据文件都是以文件目录树来组织和管理。如Windows和Linux系统等都是用文件目录来管理数据,但是当数据以海量形式呈现时,传统的方法已经失效。使用HDFS可以分散存储超大规模数据,作为存储数据的基础。分布式索引首先需要解决的问题就是如何组织索引,目前研究较多的索引组织策略有局部索引策略、全局索引策略以及混合索引策略。局部索引组织策略是将所有数据以块进行划分,然后将得到的数据块分发给集群的不同节点,服务器为各自维护的数据建立局部索引表。在查询时需要把用户的请求转发给索引集群中的所有的节点。局部索引具有良好的查询性能和负载均衡水平,并且索引表的维护很简单。缺点是需要所有集群中的节点都参与查询处理,资源浪费较多且缺乏可扩展性。全局索引将数据按行分块,并把数据块分给的集群的不同节点。在查询时可将用户查询直接转发到维护相应索引片的集群节点。全局索引无需将请求转发给所有的集群节点,查询处理耗费资源较少,但负载均衡水平相对较低,而且由于全局索引往往分布在不同的服务器上,查询结果合并操作困难。混合索引希望能结合局部索引和全局索引。为查询比较频繁的数据创建全局索引,全局索引可以看作是局部索引的缓存,以提高整体查询效率。但局部索引或全局索引均存在查询效率不高的问题,随着分布式技术的发展,如何组织混合索引来提高检索速度是非常重要的。
2.1 索引集群框架
索引集群的任务是并行构建混合索引机制,可分为数据分块、局部索引集群、全局索引集群三部分,其架构如图1所示。
数据的分块由HDFS负责,HDFS自动地将数据划分为数据块,默认分块大小是64M,这个用户可以自己设置。在数据分块时通过Map Reduce将数据块处理作业拆分成若干个可独立运行的Map任务,分配到不同的集群节点上去执行,生成某种格式的中间文件,再由若干个Reduce任务合并这些中间文件来创建索引。当用户查询时全局索引集群将查询请求转发到能满足的数据块来实现路由查找功能,从而减小局部索引集群的压力,提高查询速度。通过数据块摘要、局部索引摘要的方式实现全局索引块。在系统中我们采用局部索引块的方式构建全局索引并根据关键值哈希编码分布到全局索引集群上。通过DHT技术搭建全局索引集群。局部索引集群的节点通过对各个数据块建立“键值—数据块摘要”的局部索引表,然后全局索引集群节点再建立“键值—数据块”的全局索引表。这样就减少了每个索引项的路由列表的长度,对全局索引项再通过一致性哈希进行组织。客户查询的时候先将查询键值哈希,然后通过一致性协议找到维护该键值的数据块全局索引表,然后再将请求转发给数据块对应的局部索引表,最后得到查询结果。
3 结论
本文给出了Hadoop相关分布式技术的介绍,并介绍了分布式哈希表算法。然后分析了分布式索引策略。最后通过Hadoop的HDFS存储索引分块数据,Map Reduce并行计算框架并行构建索引,设计了全局索引集群和局部索引集群相结合的混合式索引集群的分布式索引集群的框架模式。在分布式索引集群中当数据块文件改动时还涉及到索引的更新维护等操作,以及索引集群间的协同工作,这也是我们今后进行更一步的方向。
参考文献
[1]White T.Hadoop权威指南(中文版)[M].曾大聃,译.北京:清华出版社,2010.
[2]Hadoop Distributed File Syste[EB/OL].(2011).http://hadoop.apache.org/hdfs/.
[3]Hadoop MapReduce[EB/OL].(2011).http://hadoop.apache.org/mapreduce/.
[4]王峰,雷葆何.Hadoop分布式文件系统的模型[J].电信科学,2010(12):95-97.
[5]黄晓云.HDFS的云存储服务系统研究[D].大连:大连海事大学,2010.
[6]张路.大规模数据集的分布式索引机制研究[J].微电子学与计算机,2008,25(10):122-123.
分布集群 第3篇
关键词：集群系统,分布式任务,高可用,故障冗余
0引言
随着计算机技术的不断进步,各类业务对系统处理能力、服务能力以及可扩展性要求的不断增加,采用集群的计算机业务系统得到越来越广泛地应用。 但是,随着集群系统节点数量和计算任务规模的不断增长,集群系统中因设备故障、进程问题等异常情况导致的任务故障难以避免,为避免任务故障带来的损失,亟需研究集群系统分布式任务故障冗余管理机制,提高集群系统可靠性,保障关键业务的连续稳定运行。
国内已有学者就如何提高集群系统可靠性作了大量研究。卢毕玮研究了提高集群系统可靠性的方法,该文献表明故障容忍即在故障发生的情况下如何避免服务失效,是目前工业界和学术界研究和实践最多的一种方法。杜云飞分析了使用硬件冗余和软件冗余方式来保证系统可靠性的优缺点。该文献表明在大规模系统内使用硬件冗余代价很高,研究软件冗余对解决大规模系统的可靠性问题具有十分重要的意义。魏勇等提出了一种主动容错方法,该方法主要通过在线方式的状态监控、故障分析及故障快速恢复方式实现。郝丽蕊等指出了集群系统中设计冗余服务管理的两类常用模式:全局集中管理模式、分散管理模式,并分析了这两类模式的优缺点。该文献表明在集群系统中可采用全局集中管理模式来获得高可靠性的服务。徐江红等提出了一种采用双机热备份的方法解决单点故障问题。张新洲等分析了发生在集群中的故障情况,包括计算任务自身故障和设备故障导致的任务故障。顾文杰等提出了一种高效的任务守护机制。可以对运行在节点内任务的退出、停滞等异常情况进行有效的检测及恢复。
在上述背景下,本文专注于集群系统以及运行在集群系统环境中的分布式任务,设计和实现了集群系统分布式任务故障冗余机制。该机制有效解决了传统任务故障冗余机制中无法跨节点对故障任务进行恢复的问题,通过多机热备方式有效解决了集群系统中单点故障问题,并解决了主备切换导致的故障任务信息丢失问题。该机制在很大程度上提高了集群系统可靠性,具有很强的实用性。
1体系架构与工作原理
集群系统分布式任务故障冗余体系架构如图1所示。该系统运行的守护模块包括:节点任务故障冗余模块、主集群任务故障冗余模块及备集群任务故障冗余模块,节点分为集群中心节点和计算节点两类。
图1中123为数据通信。12为实线,表示该数据通信一直存在;3为虚线,表示只有当某一事件发生时,该数据通信才会存在。节点任务故障冗余模块运行在集群中的每个节点上,该模块主要负责对运行在该节点上的任务进行状态检测,在任务故障时在本节点进行恢复,与主集群任务故障冗余模块之间进行数据通信(见图1中1)。备集群任务故障冗余模块运行在集群中的部分节点上,该模块主要是作为主集群任务故障冗余模块的热备份(见图1中2), 在主集群任务故障冗余模块失效时通过选举算法重新选举出一个主集群任务故障冗余模块对外提供服务(见图1中3)。主集群任务故障冗余模块主要负责对全集群任务进行状态检测,在任务故障时负责跨节点对任务进行恢复,与节点任务故障冗余模块、备集群任务故障冗余模块之间进行数据通信。集群中心节点是运行主集群任务故障冗余模块所在节点,其他节点均为计算节点。本系统通过跨节点信息同步以及集中式管理方式使集群系统实现了分布式任务故障冗余功能,并通过多机热备有效解决了集中式管理所产生的单点故障问题。
2关键技术
2.1任务故障检测及恢复
能及时、准确地检测任务故障,是提高本系统可靠性的关键。本系统采用两级任务故障检测及恢复机制(见图2)。
第一级为节点任务故障冗余模块的任务故障检测及恢复。节点任务故障冗余模块通过被动监视检测任务异常退出,通过主动汇报检测任务停滞等方式检测任务是否故障。当检测某任务为故障时(见图2中1),节点任务故障冗余模块首先会将该故障任务在本节点内进行恢复(见图2中2)。如果该故障任务恢复失败,节点任务故障冗余模块将故障任务信息发送至第二级进行任务故障检测及恢复(见图2中3)并等待恢复结果(见图2中9)。
第二级为集群任务故障冗余模块的任务故障检测及恢复。集群任务故障冗余模块通过接收来自节点任务故障冗余模块的任务故障报文(见图2中3)、 检测整个节点的所有任务超时未刷新(见图2中4) 等方式检测任务是否故障。当检测某任务为故障时, 主集群任务故障冗余模块首先会将该故障任务信息同步冗余到备集群任务故障冗余模块(见图2中5), 然后会在集群中选择一个节点对该故障任务进行恢复(图2中67)并等待结果(见图2中8),最后主集群任务故障冗余模块会将对该故障任务恢复结果发送至备集群任务故障冗余模块、原故障任务运行节点上的节点任务故障冗余模块(见图2中910)。
2.2集群中心节点选举
由于集群任务故障冗余管理模块采用了集中管理方式,因此必须考虑单点故障情况。当发生单点故障时,必须能够及时地选举出一台可用的主集群任务故障冗余管理模块来对外提供服务,以达到自身冗余。
集群中任意节点上的集群任务故障冗余模块启动后,该节点为SLAVE节点(备集群任务故障冗余模块运行节点),其会一直接收MASTER节点(主集群任务故障冗余模块运行节点)心跳报文。如果在4T(1T为MASTER节点心跳报文周期)时间内未收到心跳报文,则该节点升为MASTER节点并且该节点需要在4T时间内稳定后才能对外提供服务。在4T稳定时间内,如果该MASTER节点收到其他MASTER节点的心跳报文,则该MASTER节点根据一定的策略判定自身是否要降为SLAVE节点。当该MASTER节点在4T时间内收不到其他MASTER节点的心跳报文,则该节点为选举出的MASTER节点。
2.3任务状态同步
任务状态能够及时同步是各个节点协调合作的关键。在本系统中,采用周期性报文同步和紧急报文同步相结合方式保证任务状态在集群系统内同步。
在节点任务故障冗余模块端,对于运行正常任务,通过任务周期性汇总报文同步至主集群任务故障冗余模块;对于任务故障或者正常退出时,通过任务紧急报文方式同步至主集群任务故障冗余模块,并需等待应答报文。在主集群任务故障冗余模块端,对于从节点任务故障冗余模块周期性接收的正常状态任务,通过周期性同步报文同步至备集群任务故障冗余模块;对于接收的任务状态为故障或退出时,需要将该任务状态通过任务紧急报文同步至备集群任务故障冗余模块,并确认所有备集群任务故障冗余同步更新了该任务状态后,主集群任务故障冗余模块再进行相关操作。
3系统测试
系统测试主要包含对该机制正确性测试以及效率测试。整体上验证了该机制正确、高效和可靠。
为了验证该机制正确、可靠以及效率,采取以下方法进行测试。
(1)通过终止任务模拟任务故障,验证节点任务故障冗余模块检测任务故障功能以及恢复故障任务功能的正确性。(2)通过移除可执行文件和终止任务模拟任务故障,验证节点任务故障冗余模块检测任务故障功能,节点任务故障冗余模块恢复故障任务失败后,主集群任务故障冗余模块检测任务故障功能以及恢复故障任务功能的正确性。
通过上述模拟任务故障方法,计算从终止任务开始,节点任务故障冗余模块检测到任务故障的时间(T1), 节点任务故障冗余模块恢复故障任务成功(T2)或者失败(T3)时间,集群任务故障冗余模块检测到任务故障的时间(T4),集群任务故障冗余模块恢复故障任务成功(T5)或者失败(T6)时间(见表1)。
从实验结果来看,从任务故障发生时到恢复最长只需要经过大约2秒时间,最短时间在1秒内,且测试中各功能正确,这些都充分证明本文设计和实现的集群系统分布式任务故障冗余管理机制判断处理正确、 高效和可靠。
4结语
分布集群 第4篇
网络交互体系变得越来越复杂, 将其建模成图模型是其必然的趋势[1]。在这种图模型里面, 各结点主要用来描述对象实体, 而各边主要是描述对象实体的关系。例如社交网络体系即属于无向图模型结构的范畴, 各结点所指代的内容为社交个体或群体, 各边指代社交个体或者群体间的关联, 主要包括朋友、同事等[2]。现阶段,伴随信息技术和网络的日益发展, 尤其是Web3.0 网络的问世, 各种虚拟网络应用产品在实践中得到普及, 例如微博等, 其图数据信息的处理量不断增加, 形成了海量图数据信息, 从而使图数据挖掘与分析应用能力面临一系列非常严峻的挑战[3,4,5]。
作为图数据挖掘与分析应用的重要作用之一, 图聚类主要根据聚簇对图模型中的各结点实施分类操作, 同时增加同类聚簇图结点对象实体的关联性, 减小异类的关联性。现阶段, 图聚类在实践中已经普及, 如交通运输规划分析等。因此, 伴随各种超大规模图数据信息与处理机制的问世, 怎样科学合理的进行图聚类分析与处理, 在此基础上, 对其中潜在的有效数据进行挖掘, 已经发展成为该领域的一个重要课题[6]。数据抽样[7]属于其中非常有效的一个方式。其大致步骤为: 抽取整体数据集合里面的局部样本, 利用这种方式实施数据挖掘处理与分析, 旨在实现时间和挖掘处理结果的高性能比。在分析过程中, 应当先依次对图模型里面包含的各结点和边实施数据抽样操作, 通常情况下, 这个步骤叫做图稀疏化处理;然后对上一步得出的结果实施图聚类分析,这样就可以使图聚类分析与处理的有效性有所提升。图稀疏化处理机制[8]已经在诸多领域中得到应用。针对小区域范围、小规模的图模型数据信息, 当前业界形成的图稀疏化处理机制大体上涉及到k- 最近邻图、L-Spar等技术。但是, 当前的技术均无法满足较大区域与规模图模型数据信息的需要, 除此之外, 还无法在分布式集群计算环境中有效应用。
传统的最小哈希算法[9](Minhash) 基本上是用来求解若干数据集合间的相似程度, 目前为止, 该种方法在诸多热门课题中得到应用[10]。引入Map Reduce并行计算理论已成为目前一个明显趋势, 其能够关联操作大规模服务终端, 可以充分解决大规模数据分析与处理的需要。鉴于这个方面的原因, 为实现分布式集群环境下图聚类信息高效处理, 本文利用基于并行计算的高效图稀疏化处理算法(Minhash算法和并行计算Map Reduce架构理论) 实现分布式集群计算环境下超大规模、超大区域范围图数据信息的稀疏化分析与处理。
2 问题描述
Minhash算法是参考Jaccard相似度, 通过K个Hash函数分别对2 个数据集A、B实施Hash操作, 两者分别得到K个Minhash参数值。这样, 两者的相似值即Minhash参数值一样的元素数和总体元素数之比。已有的研究成果对图聚类的性质多有讨论, 它们得到一种启发式图聚类规则集合, 叫做同一聚簇条件下的各结点相似的邻居结点集合。因此, 邻居结点集合内的相似结点非常有可能处在同个聚簇之中。在稀疏化处理机制中, 该种规则集合即2 个关联结点存在的边能够被存储。不同的是, 要是2 个结点的邻居结点集合具有相对偏低的相似程度, 在这种情况下, 则2 个关联结点的边将被删除。这与Minhash算法大致相似。考虑到当前图模型应用产品的日益更新, 其应用规模同样逐渐增加, 数据信息逐渐增大, 单一的计算环境无法充分适用数据分析与处理, 同时导致图稀疏化处理机制不能发挥作用。分布式框架理论体系是在超大规模、超大区域范围的数据集合分析与处理机制中应用。作为并行计算的一个重要架构,Map Reduce能够使相关人员在并行编程过程中,仅仅需要侧重其应用体系内的分析与处理机制就可以,根本不必考虑那些冗余、繁琐的分布式事务。这为大规模数据并行计算提供了解决渠道。
基于以上基本原理, 我们主要讨论在分布式集群计算环境下对超大规模、超大区域范围图数据信息的稀疏化分析与处理机制的改进[11]。本文主要是基于Map Reduce理论, 对Minhash算法实施并行化分析,通过研究, 阐明了以并行计算为基础的高效图稀疏化处理方案。
自技术层面入手, 该方案通过并行计算Map Reduce框架结构[12], 对诸多任务的推算进行研究:
(1)Minhash算法签名推演;
(2)邻居结点数据集合推算;
(3)各结点相互间的签名哈希存储;
(4)稀疏化处理计算。
除此之外, 本文在Hadoop计算环境下, 对方案的性能实施相应的实验, 通过研究发现, 在图聚类稀疏化分析与处理机制中, 引入该方案为机制的高效性能提供了坚实的保障。
L-Spar算法的原理如下所示: 就图模型的边v(i,j)来说, 根据i和j两个结点间的Jaccard参数值来选择相应的删除或存储方法。按照Jaccard相似度实施的推算:
其能够求解出i和j两个结点的Jaccard参数值, 因而相似度值则有:
上式中,Adj(i)表示和i结点的邻居数据集合, 与之相同,Adj(j)则表示和j结点的邻居数据集合。Sim(i,j)输出数值的高效计算应用了最小哈希函数在数据集合相似程度求解过程中的优势。其具体求解过程见图1。
对于L-Spar算法来说, 其基本上是基于小规模环境中的图聚类稀疏化分析与处理机制。当其处于超大规模分布式集群计算条件下时, 在这种情况下, 它的算法优势将不能得到充分发挥。所以, 为妥善解决超大区域范围、超大规模的分布式集群计算问题, 本文在这里主要利用并行计算Map Reduce架构理论体系优化L-Spar算法,然后把它引入到图聚类的稀疏化分析与处理机制,最终得到以并行计算为基础的高效图稀疏化处理方案。本文在后文会细致深入的对该方案进行阐述。
3 稀疏化分析处理机制
3.1 Minhash相似度计算
Minhash算法是快速估算两个集合的相似度, 为大规模数据信息的聚类提供支持。Jaccard相似度实施的推算。Jaccard为相似参数值, 主要是在检测若干数据集合相互间相似度的过程中应用。利用其对A、B数据集合实施相应的操作, 就能够得出两个集合的相似度。上面的式里面,Jaccard参数值为A、B的对比数值。通过上面的式子看出,2 个数据集合相似度越高与Jaccard参数值呈正比例关系。但是, 当数据集合相对较大时,Jaccard参数值将为交并集合的规模所限制, 它的效率就不能增加。
Minhash算法主要参考Jaccard参数值有关理论,首先, 通过Hash函数求解两个数据集合的总元素数量, 其次, 得到相关结果信息, 也就是Minhash(A) 和Minhash(B), 因此:
这样, 在这一个算法里面, 相似度问题就转变为若干数据集合的等值概率数学问题, 最终在很大程度上优化了计算效率。
3.2 Map Reduce并行计算
Map Reduce并行计算的操作步骤见下图。
通过图2 得知, 一般情况下,Map Reduce分布式任务往往都离不开有关分析与处理过程, 大致步骤如下:
(1) Mapping环节: 利用这一个步骤, 任一Map函数操作若干Split数据集合, 在此基础上, 将有关参数值输出, 也就是若干<key,value> 键值对数据信息;
(2) Combine环节: 对第一步中若干<key,value>键值对数据信息实施排列、分类组合操作;
(3) Reducing环节: 这一个步骤主要是对上文中经过有关处理的若干<key,value> 键值对数据信息实施遍历操作, 把唯一性键值操作有关Reduce函数, 得到有关输出结果。
Hadoop为并行计算工具, 目前已经得到普及推广。本文在这里主要通过Hadoop实现本文所设计方案的模拟实验处理过程。模拟实验操作于Hadoop平台下的Map Reduce应用程序, 其大体上包括Mapping类(1 个)、Reducer类、新建的Job Conf驱动方法及关联Combiner类。
4 高效处理方案
针对超大规模、超大区域范围的分布式集群计算条件提出的方案, 其具体操作步骤大体上涉及到4 方面内容, 分别为:
(1)Minhash算法签名推演;
(2)邻居结点数据集合推算;
(3) 各结点相互间的签名哈希存储;
(4) 稀疏化处理计算。接下来我们将分别进行阐述。
4.1 邻居结点数据集合推算
本文所设计方案的首个环节是对一组Map任务得出图模型中任一边结点的邻居结点数据集合,具体来说,其操作步骤见图3。
通过图3 得知,Map任务获取一组键值对数据信息,结点信息为vi和vj。经由求解发现, 输出键值对数据信息为<key=vi,value=list[Ni]>, 在这里vi的邻居结点数据集合为list[Ni], 在HDFS平台中引入输出参数值。其Map任务可以通过下面的方式进行表示:
4.2 Minhash算法签名推演
本文所设计方案的第二个环节是对图模型中任意结点的Minhash算法签名数据信息进行推算。鉴于此, 本文所设计方案可结合Map和Reduce任务, 在此基础上,推算Minhash算法签名数据信息, 具体来说, 其操作步骤见下图4。
在这里,Map任务的输入参数值为首个环节得到的输出结果。通过上面的图形,Map任务主要是将若干Minhash函数(k个) 当做其输入参数值, 在此基础上,利用Hash推算, 就能够得到其键值对数据信息<key=vi,value=Hm(Ni)>(m=1,2,...,k), 在这里,Hm(Ni)代表最小哈希函数的列表信息。该部分输出结果为Reduce任务的输入参数值, 利用Reduce推算得到键值对数据信息<key=vi,value=Sig[i][m]>, 在这里,Sig[i][m] 为二元形式化数组, 描述vi的算法签名序列。从而把Sig[i][m] 引入到HDFS平台里面。具体可以通过下面方式进行描述:
此部分的操作步骤包括若干子环节, 接下来我们将进行阐述:
(1) Map任务处理描述
(2) Reduce任务处理描述:
4.3 结点签名之间的哈希存储
本文所设计方案处理操作的这一个部分旨在判断图模型里面每一结点关联邻接边是否为图聚类稀疏化结构。实质而言, 其主要是通过结合Map和Reduce的方式推算任一个结点, 其具体描述步骤见下图。
通过上面的图形得知, 这个环节的Map任务环节输入为该方案的首个环节中获取的键值对数据信息<key=vi,value=list[Ni]> 和算法签名二元数组集合Sig[i][m], 获取有关中间参数值, 其当做Reduce任务步骤的输入, 并且哈希函数同样属于一个输入参数值, 这样的获取输出为<key=vi,value=list[Sort Cij]>。这一个环节的形式化表达见下文所示:
这一个部分与该方案的第二环节一样, 其处理步骤同样包括若干子环节, 见下文所示:
(1) Map阶段处理描述:
(2) Reduce阶段处理描述:
4.4 图聚类过程中的稀疏化处理计算
本文所设计方案的第四个环节是根据和vi所有邻接边相互匹配的Sort Cij, 通过Map操作存储其前die条结点邻接边数据信息。在这里,di为vi度数参数,e<1 表示图聚类过程中稀疏化处理指数, 利用e对图数据信息的稀疏化进行控制。通过有关步骤发现,e和图模型的稀疏化两者之间成反比。具体来说, 其步骤见下图。
这一个环节中,Map阶段对该方案的第三环节输出参数值实施有关处理, 同时把die归到输入的范畴, 使得整个过程中保留结点, 从而在HDFS平台中对其进行应用。其具体的形式化阐述见下文:
这一个部分的处理步骤见下文所示:
在该方案的最后一个环节实施以后, 图模型里面的各结点都对e大于1 的边的数量进行存储, 这样就为图模型处于连通状态提供了保障。
5 模拟实验
现简要的模拟本文所设计方案, 并通过对比检验其效率。
Hadoop平台主要是由最基础最重要的两种组成元素组成, 底层为用于存储集群中所有存储节点文件的文件系统HDFS(Hadoop Distributed File System), 上层由用来执行Map Reduce程序的Map Reduce引擎[13]。HDFS是一个分布式文件系统, 具有高容错性的特点, 能够完整展现出分布式集群环境中集群的特点[14]; 按照计算机分布式思想, 分布式计算是指将巨量的计算任务分配成许多小任务并由众多的计算机进行处理,Hadoop平台上的Map Reduce编程架构[15]可以实现任务的分配,并把分配后任务的运算结果汇总, 完全可以实现对分布式集群环境运算模式的仿真, 因此本文选择Hadoop平台正是基于以上目的, 有效体现分布式集群环境的特点, 并对其可能存在影响因素通过在Hadoop仿真平台进行实践。
5.1 实验配置
我们在这里采用Map Reduce, 将其引入到Hadoop分布式集群计算条件中。主要包括若干服务器和终端等方面, 其中包括主机1 台, 别的均为附属机, 计算环境下的每一结点CPU处理器工作频率始终处于3.20GHz,因特尔双核处理芯片, 内存必须≥ 1GB。Hadoop分布式计算环境版本为1.0.5,OS,JAVA语言。数据信息源为新浪微博社交虚拟网络的关联图模型。
模拟过程中主要通过Speedup参数值描述本文所设计方案的性能指标参数变化。其具体可以通过下面的公式进行描述:
上面的式子里面,Ti指第i个分布式集群计算条件下结点对图模型稀疏化分析与处理所用时间,T1指单机条件下对图模型稀疏化分析与处理所用时间。
5.2 操作和分析
模拟过程中选择不同的图模型稀疏化处理机制, 得到的图模型稀疏化比率参数值e同样存在着一定的差异,为解决各种数据信息量和分类的图模型数据信息, 对应的最合理的e值同样存在一定的差异。本文在这里取e为0.15, 在此基础上实施有关操作。
为体现本文设计方案在超大规模、超大区域范围的分布式集群计算环境下的高效性能, 模拟过程中本文主要使用不同并行计算条件下的执行算法。该方案第一步是对Map和Reduce任务阶段实施过程处理, 接着分析了图模型数据信息, 完成稀疏化分析与处理机制。模拟过程中涉及到的数据信息见下图。
通过上面的图形发现, 对于超大规模、超大区域范围的分布式集群计算环境下, 引入Hadoopp并行计算平台可以明显减少时间损失, 最终可以显著提高Speedup。按照Map Reduce理论, 图模型数据信息规模与图聚类过程稀疏化比率参数值两者存在正相性; 但是伴随分布式集群计算条件下每一结点的通信过于频繁,同样能够消耗或多或少的数据信息性能, 当图模型数据信息交互规模相对偏小时, 在这种情况下, 图聚类过程稀疏化分析与处理机制效率将有所下降, 对应的e参数值同比降低。另一方面, 当Speedup和分布式集群计算环境不断提高时, 其图聚类过程稀疏化分析与处理机制同样不断增加, 其e参数值同比提高。
5.3 算法聚类能力准确度分析
为了体现本文算法在分布式集群环境中准确度的优势, 下面在Hadoop平台上, 将本文所设计方案与基于Map Reduce的K-means聚类算法做对比( 这种算法的实现见参考文献[16])。在准确度评价体系上, 这里引入F度量值来衡量算法的聚类准确度效果, 具体涉及查准率与查全率[17], 其中:
查准率=( 第i类的正确文本数/ 第i类的实际文本数)*100%
查全率=( 第i类的正确文本数/ 第i类的应有文本数)*100%
F度量值综合查准率和查全率, 将两者等同考虑,以此来衡量算法的聚类准确度,
第i类:
,其中Pi是第i类的应有文本数,P是文本数。
在本对比实验中, 原始数据来自于国家超级计算机中心的数据库的相应的数据类别中随机调取的部分数据[18], 原始数据表见表1
结果见表2, 从表2 可以看出本文所设计方案的F度量值要优于基于Map Reduce的K-maens聚类算法,即其聚类质量占优, 同时其分类准确率也相应提高。
5.4 方案运行时间分析
为了进一步检验本文所设计的算法的效率, 下面将本文所设计稀疏化方案与基于k-medoids聚类算法局部图稀疏化方案[19], 在运行时间上做对比。k-medoids聚类算法具有收敛快、运行简单的特点, 在业内时间复杂度上有较为明显的优势。运行平台与4.3 节相同, 实验素材采用DBLP数据集[20], 运行时间对比数值见表3。
表3 中e代表稀疏化比例参数, 从表3 可知, 本文设计的方案, 在与k-medoids聚类算法相比仍具有一定的时间优势, 并且在不同的稀疏化比例条件下, 其性能表现较为稳定。
经由模拟实验我们发现, 本文所设计的方案更适合超大区域范围、超大规模的分布式集群计算环境下的图数据信息, 因在该方案里面增设排序组合机制, 正是这一个方面的原因, 导致结点和邻接结点间的通信消耗有所减小, 也就是图数据信息规模与算法效率性价比两者呈正比例关系。
6 结束语
针对超大规模、超大区域范围的分布式集群计算环境, 本文主要是基于Map Reduce理论, 对Minhash算法实施并行化分析, 当图模型稀疏化比率参数值e=0.15 时,本算法F度量值要优于基于Map Reduce的K-maens聚类算法, 同时在聚类个数为5,10,15 的情况下比较,本方案运行时间在稀疏化比例为e=0.4,0.8 时要少于k-medoids聚类算法, 差别最大时为0.34s。研究, 证明以并行计算为基础的高效图稀疏化处理方案可以对图聚类数据信息进行高效处理。该算法具有较高的可操作性, 同时可以快速稀疏化处理图聚类数据信息, 简单高效。
摘要：针对人工智能领域图聚类数据分析与处理能力无法适应于日益复杂的分布式集群环境等问题,提出一种基于并行计算的高效率图聚类信息处理方案。在分布式集群计算环境下对超大规模、超大区域范围图数据信息的稀疏化分析与处理机制上,通过对Minhash算法以Map Reduce架构理论进行改进,使其实现对数据的并行化分析处理,确保能够在日益复杂的分布式集群计算环境下高效处理图聚类数据信息。实验表明,改进方案不仅可行,而且能够对图聚类数据信息进行快速稀疏化处理,具有一定的高效性。
分布集群 第5篇
一广电的发展和变化
如今的广电正步入全台网络化、IP化、云化时代。伴随着移动媒体(手机、iPad)、互联网媒体、各种LED屏等新视频媒体的层出不穷,以及各种新兴应用,微博、微信、手机视频、手机电视、互联网视频,互联网电视、iPad应用、户外视频等,逐渐形成了新媒体形态。
就目前互联网视频用户数量已经与传统电视媒体的用户数量相当,足以说明,如今广电面临的是新媒体与传统媒体并存的时代。而媒体融合与整合是基础,面临的就是如何通过新技术,来满足新业务,并构建未来的发展。
如今广电的另一个特点就是数据量的大爆发。从标清时代进入高清时代,而4K技术又接踵而至,面临的数据量是呈几何级数的增长。真人秀季播节目在电视台比比皆是,几十个机位同时记录现场画面,多种拍摄手法并用,每天采集的数据量都是空前的。面对如此庞大的数据量,迫切需要更新换代新兴存储体来满足业务的增长和需求。
无论是面临IP化、新媒体,还是大数据爆发的时代,构建一套可以融合、共享,并具有对未来弹性增长而按需匹配的基础存储体,无疑是件再基础不过的事情了。
二广电领域正在升级换代新兴存储体
在与多家电视台的走访和合作中发现,电视台已经清楚地认识到了今后发展的变化与成长性。在电视台里运行了多年的FC/SAN架构的存储体,无论在运维、还是后续业务突飞猛进的发展中,已经越来越不能满足新型业务形态的发展和需要。所以各电视台纷纷了解和采纳新兴的存储体——分布式大规模集群存储。
该架构的存储体,最早应用于互联网行业,本身就是面对海量数据、大量客户并发访问等应用特性应运而生。并在互联网领域、高性能计算等领域应用多年,取得了非常优异的应用效果。
广电领域在面对融合媒体平台建设,智慧媒体平台建设以及云平台建设中,纷纷采用了该架构的新兴存储体。同时在全台网或者非编网改造中,也采用这种架构的存储体。可见,在广电领域正在进行着新兴存储体的更新换代,来应对和面向电视台业务发展的新方向。
三新兴存储体的变化和优势
那么电视台为什么会选用分布式大规模集群存储这种新兴的存储体作为更新换代的产品呢?我们就要从存储的演变和发展进行了解。
1.第一代存储体——DAS
DAS (Direct Attached Storage)是直接连接存储。从图3中,我们可以清楚地看到,我们的存储就是硬盘,与主机直接相连。后来发现存储空间不够了,就通过SCSI线,在服务器外面连接磁盘柜来扩容。后来又发现空间还是不够(受SCSI外接设备限制),在服务器和磁盘柜中都增加了控制器,以扩大连接外设数量来扩容。这样,在DAS年代,磁盘柜最终被广泛应用。但是,依然可以清楚地看出服务器与磁盘柜之间仍然采用的是SCSI线来连接,也就意味着,无论怎样扩容,都是单台服务器连接存储设备。也就是说,其他计算机设备只能通过与存储设备相连的服务器来共享存储空间。这样的解决方案,到了网络时代显然是落后了。
2.第二代存储体——SAN
存储区域网SAN (Storage Area Network)是颠覆性的发展,以前是服务器通过SCSI连接磁盘阵列,如今的变化是,存储设备通过网络与服务器连接。如图4,这样的好处是,所有的服务器都可以接入这个网络,做到了存储设备共享,实现了存储区域网(SAN)。这个存储区域网是后续所有存储网络接入的基础。但到目前为止,存储设备仅增加了网络接入接口,还是不够智能,没有发挥存储设备本身的能力,所以后续有了NAS的出现。
3.第三代存储体——NAS
网络附加存储NAS (Network Attached Storage),如图5。与SAN架构图突出的区别是,存储设备不再是单纯的存储空间加网络接口,而是一台存储服务器来实现存储功能(NAS服务器)。它里面有操作系统,有文件系统,有许多服务器自身的功能。好处是,减轻了应用服务器的工作压力。应用服务器仅需在目录层与其文件系统建立连接即可。至于后续存储的负责均衡、数据备份、数据安全种种关于存储应该做的事由NAS服务器完成。这样,就把应用服务器解放出来,去做其应该做的任务(应用服务器本身应该处理的各种业务程序,而非存储应完成的工作)。
网络附加存储(NAS),就是智能存储体增加网络功能,而不是一个单纯可以连接存储体的网络(SAN)。NAS存储设备与SAN存储设备在实际使用中,NAS是带文件系统的存储体,与其连接,通过软件直接挂载就可以使用了。而SAN存储设备(块设备),要服务器挂载存储体后,再格式化,并独享已挂载空间。而NAS设备可以共多个服务热点透器同时挂载并共享存储空间。
4.第四代存储体——分布式大规模集群存储
NAS是单机设备,但随着数据量爆炸式增长,存储性能需要线性增加的时候,单机版的NAS已经很难应付业务的成长性。更加弹性、性能更加优越、布置更加灵活、性价比更好的分布式大规模集群存储应运而生,是海量数据时代的最佳解决方案。
分布式大规模集群存储(也称集群NAS),就是将存储任务分配给许多相同的智能存储设备(NAS服务器),并由众多存储设备协同工作,来提供海量数据时代的存储空间及性能要求。更加具象的就是,所有应用服务器可以通过网络直接连接到一个存储设备的集群,而存储设备集群对外表象是一个统一命名存储空间。而具体存储工作无需应用服务器关注,它们会自己协同工作,统一管理,统一对外服务。
这种架构的好处是在分布式大规模集群存储系统中,你可以非常弹性地增加存储设备扩容空间并提高存储性能。每个存储设备都提供空间和性能的对外服务,这样所有使用这个存储集群的应用服务器可以共享到所有存储设备的空间和性能。这样就可以实现空间无限扩容,性能无限增加的理想应用。
面对众多的专用存储设备,分布式大规模集群存储系统架构在性能更优、架构更开放的X86服务器之上。这样,存储设备在价格和性能上达到了空前的性价比优势,在后续维护上更廉价更简单。同时伴随着X86服务器性能的日新月异的更新,存储系统的性能也随之不断提高。
四带外架构的分布式大规模集群存储可以给广电应用带来什么
在分布式大规模集群存储系统中,还有两种架构,全对称式架构和非对称式架构(带外架构),“龙存”就是属于后一种。
1.全对称式架构
每个存储设备对等对外提供服务,每个存储设备既提供数据的存储空间又完成数据的管理任务。就是一台X86服务器的存储设备,既要提供数据的读/写操作“体力活”,又要提供数据的切片、分发、整合等“脑力活”,等于一台X86的存储设备既干“脑力活”又干“体力活”,一“人”多职。
2.非对称式架构(带外架构)
把每个存储设备的“脑力活”提取出来,让专职设备“元数据服务器集群“去完成,这样就解放了存储设备。存储设备可以全力以赴对外提供数据的读/写操作“体力活”,大大提高了存储设备对外提供读/写服务时的性能。同时因增加了新的“大脑”功能,可以实现使用者在“横向”和“纵向”两个方向上的性能线性扩容增长,实现无限扩展使用空间和存储整体性能的理想应用状态。这就是“龙存”最初的设想。
所谓“横向”X轴——存储空间的增长和存储系统整体对外提供读/写混合带宽的增加。
所谓“纵向”Y轴——在存储空间和读/写带宽满足使用者的前提下,随着使用者人数的增加和文件数据量的增加,而实现大用户数并发性能和海量文件检索性能的“纵向”性能提高,而非扩容存储容量。
“带外架构”可以实现在“横向”上增加存储服务器数量来扩容,扩容同时,可以得到读/写混合带宽的线性增长。在“纵向”上增加元数据服务器数量,来提升大用户数并发访问的能力和海量文件检索的能力。
以“龙存”存储系统为例,目前可以支持1000PB级存储容量,2000亿个文件管理,40000个节点并发访问,数百GB的聚合带宽,其规模目前在中国无人企及。
是不是“大脑”元数据服务器集群会成为瓶颈和热点呢?答案:不会!因为“大脑”元数据服务器本身已经集群化,可以有多个“大脑”并发运行。另外,运行中,使用者仅在开始与存储服务器集群建立连接时会通过“大脑”来确认,我的数据“放到哪”,“从哪取”,而“大脑”会发出指令,告诉使用者“去哪放”,“从哪拿”。然后,使用者就会和存储服务器集群直接打交道了,这样“大脑”并不会在后续读/写过程中形成瓶颈和热点,如图9所示。
相反,因为使用者与存储服务器集群直接打交道,反而形成了“多对多”的并行运行模式。多个使用者对多台存储服务器。摒弃了全对称架构中,使用者需与指定的存储服务器打交道。如果数据不在指定存储服务器上,要通过指定存储服务器与其他存储服务器打交道,这样会在指定存储服务器上形成热点。而非对称架构的使用者没有指定存储服务器的这种运行方式,实现了与存储服务器间无热点、无瓶颈、大并发的使用效果。也就是说“使用者越多,则速度越快”,这就是“带外架构”的优势和特点。与常理般的用户数量越多速度越慢恰恰相反。用户越多,越能体现其性能,越能突显性能优越。
因为“带外架构”的分布式大规模集群存储系统,在“横向”X轴和“纵向”Y轴上都可以非常灵活的扩容。使用者则可以非常灵活和有弹性地增加自己所需要的性能,满足业务的飞速发展。应对业务的创新与变化,实现随机应变,按需所配的理想应用。
在广电领域里,IP化已经是大势所趋。面对数据量爆炸式增长,可以在“横向”上增加存储服务器数量来实现无限扩容。在新媒体平台、融合媒体平台、智慧媒体平台、云平台、全台网等诸多平台的建设中,在面对新媒体海量文件的增长,面临更多的人共享和使用平台,可以在“纵向”上增加元数据服务器数量,来满足对大用户数并发访问和海量文件检索性能的需求,而实现为广电IP系统中数据共享基础建设奠定坚实的基础。
五未来软件定义存储,如今已成现实
伴随存储的发展,存储硬件设备已经开始采用通用设备了(X86存储服务器),这样,我们其实可以把存储硬件和软件剥离开来。存储软件,可以通过先进的算法,起到组织和协调所有存储硬件设备,并让这些硬件设备发挥出最佳效率的作用。同时将SAN存储设备(块设备)与NAS分布式存储系统(文件存储设备)整合在一套存储系统中,把以往老旧存储设备与新存储设备整合,这些都可以通过存储软件实现。
所谓的未来“软件定义存储”,其实目前在“龙存”架构中已经实现。以后买存储,就可以哪家硬件便宜,哪家硬件性能好,就采用哪家硬件设备。而存储软件统一管理多品牌硬件设备,实现多模式的应用状态,并发挥出分布式集群存储系统的最高性能,最大效率。
六互联网+、广电IP化,未来的广电生机无限,用新技术焕发青春,将获得巨大发展