基于一种海量数据处理分析系统设计.doc

18中科基于一种海量数据处理分析系统的设计文档1、 海量数据处理的背景分析 在当前这个信息量飞速增长的时代，业的成功已经越来越多地与其海量数据处理能力相关联。高效、迅速地从海量数据中挖掘出潜在价值并转化为决策依据的能力，将成为企业的核心竞争力。数据的重要性毋庸置疑，但随着数据的产生速度越来越快，数据量越来越大，数据处理技术的挑战自然也越来越大。如何从海量数据中挖掘出价值所在，分析出深层含义，进而转化为可操作的信息，已经成为各互联网企业不得不研究的课题。数据量的增长，以及分析需求的越来越复杂，将会对互联网公司的数据处理能力提出越来越高的要求、越来越大的挑战。但每一个场景都有其特点与功能，充分分析其数据特性，将合适的软件用在合适的场景下，才能更好地解决实际问题。2、 海量数据处理分析的特点 （一）、数据量大，情况多变 现在的数据量比以前任何时期更多，生成的速度更快，以前如果说有10条数据，繁琐的操作时每条去逐一检查，人为处理，如果有上百条数据，也可以考虑，如果数据上到千万级别，甚至过亿，那不是手工能解决的了，必须通过工具或者程序进行处理，尤其海量的数据中，情况多变，手工操作是完不成任务的。例如，数据中某处格式出了问题，尤其在程序处理时，前面还能正常处理，突然到了某个地方问题出现了，程序将会终止。海量数据处理系统的诞生是输入层每个神经元的输入是同一个向量的一个分量，产生的输出作为隐藏层的输入，输出层每一个神经元都会产生一个标量结果，所以整个输出层所有神经元的输出构成一个向量，向量的维数等于输出层神经元的数目在人工神经网络模型中，各个神经元通过获取输入和反馈，相对独立地进行训练和参数计算。其拓扑结构的重要特点便是每一层内部的神经元之间相互独立，各个层次间的神经元相互依赖。由于各个层次内部神经元相互独立，使得各个层次内部的神经元的训练可以并行化。但由于不同层之间的神经元具有相互依赖关系，因此各个层次之间仍然是串行处理的。可以将划分出的每一层内部的不同神经元通过map操作分布到不同的计算机上。各个神经元在不同的计算终端上进行训练，在统一的调度和精度控制下进行多个层次的神经元的训练，这样神经网络算法的训练就可以实现并行化。训练结束后，同样可以通过每层内节点的并行化处理快速地得到输出结果。在神经网络算法中，每层内的节点都可以进行并行化处理，并行化程度非常高。（2） 、软硬件要求高，系统资源占用率高 各种应用对存储系统提出了更多的需求，数据访问需要更高的带宽，不仅要保证数据的高可用性，还要保证服务的高可用性；可扩展性：应用在不断变化，系统规模也在不断变化，这就要求系统提供很好的扩展性，并在容量、性能、管理等方面都能适应应用的变化；对海量的数据进行处理，除了好的方法，最重要的 就是合理使用工具，合理分配系统资源。一般情况，如果处理的数据过TB级，小型机是要考虑的，普通的机子如果有好的方法可以考虑，不过也必须加大CPU和 内存，对电脑的内存、显卡、硬盘及网络都要求相对较高！其中对网络要求高的原因是因为其引入目前最前沿的“云端计算”好多东西都要从网络上调用；对硬盘要求是最高的，用SATA6.0的固态硬盘，对整机性能限制比较大的就是高速系统总线对低速硬盘传输，32位的系统，最大只能认到3.5G内存，就是说，不论你装几根内存条，装多大容量的内存条，你装8G的，它也只能用到3.5G，64位的系统就可以突破了这个限制。如果你的电脑配置不是特别高的话，XP是比较好的选择。32位的XP是最低要求。基于23G互操作测试生成23G互操作测试报告测试起始点时间、测试终止点时间、3G网络驻留时间（秒）、2G网络驻留时间（秒）、3G覆盖总采样点、3G覆盖总采样点不同区间数量统计、3G覆盖总采样点不同门限范围内数量统计、2G覆盖总采样点、2G覆盖总采样点不同区间数量统计、2G覆盖总采样点不同门限范围内数量统计、3G到2G重选成功次数、2G到3G重选成功次数、3G到2G切换尝试次数、3G到2G切换成功次数、切换掉话次数和其它掉话次数。（3） 、过高的处理方法和技巧 随着数据量的飞速增长，存储的规模越来越庞大，存储系统本身也越来越复杂，这给系统的管理、运行带来了很高的维护成本；能够按照应用需求的不同提供不同的服务，如不同的应用、不同的客户端环境、不同的性能等。处于这个阶段的系统都在研究中，但从中也可以看出一些发展趋势：体系结构的研究逐渐成熟，表现在不同文件系统的体系结构趋于一致；系统设计的策略基本一致，如采用专用服务器方式等；每个系统在设计的细节上各自采用了很多特有的先进技术，也都取得了很好的性能和扩展性。通常没有通用的处理方法，但有通用的原理和规则。1、选用优秀的数据库工具 现在的数据库工具厂家比较多，对海量数据的处理对所使用的数据库工具要求比较高，一般 使用Oracle或者DB2。另外在BI领域：数据库，数据仓库，多维数据库，数据挖掘等相关工具也要进行选择，好的ETL工具和好的OLAP工具都十分必要， 例如Informatic，Eassbase等。2、编写优良的程序代码 处理数据离不开优秀的程序代码，尤其在进行复杂数据处理时，必须使用程序。好的程序代码对数据的处理至关重要，这不仅仅是数据处理准确度的问题，更是数据处理效率的问题。良好的程序代码应该包含好的算法，包含好的处理流程，包含好的效率，包含好的异常处理机制等。3、建立广泛的索引 对海量的数据处理，对大表建立索引是必行的，建立索引要考虑到具体情况，例如针对大表的分组、排序等字段，都要建立相应索引，一般还可以建立复合索引，对经常插入的表则建立索引时要小心，在处理数据时，曾经在一个ETL流程中，当插入表时，首先删除索引，然后插入完毕，建立索引，并实施聚合操作，聚合完成后，再次插入前还是删除索引，所以索引要用到好的时机，索引的填充因子和聚集、非聚集索引都要考虑。4、建立缓存机制 当数据量增加时，一般的处理工具都要考虑到缓存问题。缓存大小设置的好差也关系到数据处理的成败。例如，在处理2亿条数据聚合操作时，缓存设置为100000条/Buffer，这对于这个级别的数据量是可行的。5、加大虚拟内存 如果系统资源有限，内存提示不足，则可以靠增加虚拟内存来解决。在实际项目中可能遇到针对18亿条的这样的数据进行处理，内存为1GB，1个P4 2.4G的CPU，对这么大的数据量进行聚合操作是有问题的，提示内存不足，那么采用了加大虚拟内存的方法来解决，在6块磁盘分区上分别建立了6个4096M的磁盘分区，用于虚拟内存，这样虚拟的内存则增加为 4096*6 + 1024 = 25600 M，解决了数据处理中的内存不足问题。6、使用临时表和中间表数据量增加时，处理中要考虑提前汇总。这样做的目的是化整为零，大表变小表，分块处理完成后，再利用一定的规则进行合并，处理过程中的临时表的使用和中间结果的保存都非常重要，如果对于超海量的数据，大表处理不了，只能拆分为多个小表。如果处理过程中需要多步汇总操作，可按汇总步骤一步步来，不能一条语句完成。7、优化查询 SQL语句 在对海量数据进行查询处理过程中，查询的SQL语句的性能对查询效率的影响是非常大的，编写高效优良的SQL脚本和存储过程是数据库工作人员的职责，也是检验数据库工作人员水平的一个标准，在对SQL语句的编写过程中，例如减少关联，少用或不用游标，设计好高效的数据库表结构等都十分必要。笔者在工作中试着对1亿行的数据使用游标，运行3个小时没有出结果，这是一定要改用程序处理了。8、使用文本格式进行处理 对一般的数据处理可以使用数据库，如果对复杂的数据处理，必须借助程序，那么在程序操作数据库和程序操作文本之间选择，是一定要选择程序操作文本的，原因为：程序操作文本速度快；对文本进行处理不容易出错；文本的存储不受限制等。例如一般的海量的网络日志都是文本格式或者csv格式（文本格式），对它进行处理牵扯到数据清洗，是要利用程序进行处理的，而不建议导入数据库再做清洗。9、建立视图或者物化视图 视图中的数据来源于基表，对海量数据的处理，可以将数据按一定的规则分散到各个基表 中，查询或处理过程中可以基于视图进行，这样分散了磁盘I/O，正如10根绳子吊着一根柱子和一根吊着一根柱子的区别。10、避免使用32位机子 目前的计算机很多都是32位的，那么编写的程序对内存的需要便受限制，而很多的海量数 据处理是必须大量消耗内存的，这便要求更好性能的机子，其中对位数的限制也十分重要。11、考虑操作系统问题海量数据处理过程中，除了对数据库，处理程序等要求比较高以外，对操作系统的要求也放到了重要的位置，一般是必须使用服务器的，而且对系统的安全性和稳定性等要求也比较高。尤其对操作系统自身的缓存机制，临时空间的处理等问题都需要综合考虑。系统操作流程图如下：12、 对海量数据进行分区操作对海量数据进行分区操作十分必要，例如针对按年份存取的数据，可以按年进行分区， 不同的数据库有不同的分区方式，不过处理机制大体相同。例如SQL Server的数据库分区是将不同的数据存于不同的文件组下，而不同的文件组存于不同的磁盘分区下，这样将数据分散开，减小磁盘I/O，减小了系统负荷， 而且还可以将日志，索引等放于不同的分区下。13、定制强大的清洗规则和出错处理机制 海量数据中存在着不一致性，极有可能出现某处的瑕疵。例如，同样的数据中的时间字段，有的可能为非标准的时间，出现的原因可能为应用程序的错误，系统的错误等，这是在进行数据处理时，必须制定强大的数据清洗规则和出错处理机制。14、使用数据仓库和多维数据库存储 数据量加大是一定要考虑OLAP的，传统的报表可能5、6个小时出来结果，而基于 Cube的查询可能只需要几分钟，因此处理海量数据的利器是OLAP多维分析，即建立数据仓库，建立多维数据集，基于多维数据集进行报表展现和数据挖掘等15、定制强大的清洗规则和出错处理机制 海量数据中存在着不一致性，极有可能出现某处的瑕疵。例如，同样的数据中的时间字段， 有的可能为非标准的时间，出现的原因可能为应用程序的错误，系统的错误等，这是在进行数据处理时，必须制定强大的数据清洗规则和出错处理机制。16、使用采样数据，进行数据挖掘 基于海量数据的数据挖掘正在逐步兴起，面对着超海量的数据，一般的挖掘软件或算法往往 采用数据抽样的方式进行处理，这样的误差不会很高，大大提高了处理效率和处理的成功率。一般采样时要注意数据的完整性和，防止过大的偏差。笔者曾经对1亿 2千万行的表数据进行采样，抽取出400万行，经测试软件测试处理的误差为千分之五，客户可以接受。 还有一些方法，需要在不同的情况和场合下运用，例如使用代理键等操作，这样的好处是加快了聚合时间，因为对数值型的聚合比对字符型的聚合快得多。类似的情况需要针对不同的需求进行处理。海量数据是发展趋势，对数据分析和挖掘也越来越重要，从海量数据中提取有用信息重要而紧迫，这便要求处理要准确，精度要高，而且处理时间要短，在最短的时间内得到有价值信息。三、海量数据分析的功能阐述 海量数据处理分析系统可以使数据分散到不同的存储设备上，这样存在着很多好处，加入数据来源于世界各地，数据可以存放到数据来源地的镜像上，使用者在连接自己本地的数据时会享受到较好的速度； 针对每一台存储设备，可对其进行单独的建立索引，从而减轻主服务器的负担。但是分布式进行数据的存储仍然还是存在很多问题需要解决的，例如我们如何去分配数据，使他们存储在不同的分布式文件存储系统上。如何解决动态的添加或减少文件存储系统时服务器对已存储数据的影响。（一）、 系统需求分析 由于本文件系统运行在普通的机器上，而普通机器通常容易发生故障，比如操作系统缺陷，人为错误或者磁盘，内存，连接器，网络，电源失效造成的问题。某些机器在某些时间是不工作的，而某些机器发生故障后则不能恢复。因此，对系统的监视，错误的检测和容忍以及自动恢复必须集成在系统中，这是本系统最核心的架构目标。 由于系统的主要应用是分析和处理海量的数据，而这类应用很少对反应时间有要求，因此持续的高吞吐量比低延迟更加重要。系统必须能够在不同的软硬件的平台运行。系统能够通过加入新的机器获得性能的提升。用户不需要了解文件的分布性。用户只需通过同样的文件操作来访问本地文件或者远程文件。其次，使用单一的文件命名空间，在不改变路径名的前提下，文件或者文件集合可以被重定位。第三，当文件被在文件系统内部移动时，不能改变文件对外的属性功能需求就是要实现文件的基本操作。文件系统基本操作：对外要提供对文件的通用操作。这些操作包括:文件创建，文件拷贝，文件删除，文件读取，文件写入，目录创建，目录删除。（二）、系统架构分析与设计2.1 逻辑结构分析和设计图2-1 单服务器的主从模式 分布式文件系统的服务端的设计存在两种设计模式11。一种是主从模式，一种是对等模式。在主从模式中，系统中有一个或一组服务器用来存储文件的元数据并提供对元数据访问的服务，元数据是指某个文件的相关属性信息包括文件位置，文件副本数量，文件标识符，文件访问权限等等，而其它服务器则存储用户数据提供对用户数据访问的服务。主从模式中又可以分为单服务器模式和多服务器模式，单服务器模式(图2-1)中系统中只存在一个元数据服务器而多服务器模式(图2-2)所示中，有一组服务器存储元数据。多个元数据服务器模式的优点在于可扩展较好，但是很容易造成元数据的不一致性而且非常复杂。单服务器模式下元数据服务器容易造成系统性能瓶颈。图2-2 多服务器的主从模式 对等模式(图2-3)所示是所有服务器既存储系统元数据又存储数据既给客户提供数据访问服务又给系统内其它服务器提供元数据访问服务。比如p2p 分布式文件系统就属于这一类。对等模式下很难对系统进行管理，数据更加难以保持一致，系统复杂度大大增加。图2-3 对等模式 主从模式使得文件系统内数据一致性问题得到很好的解决但可伸缩性和扩展性没有对等模式好。而对等模式下实现和管理元数据比较复杂不容易实现数据一致性。我们选择了单服务器的主从模式。原因如下:由于在本系统中数据存储的独特设计和数据访问方式的设计使得在实际应用中元数据服务器不太可能出现瓶颈，所以当我们增加数据服务器时，每个服务器存储文件的副本的平均值会减少，这样就减少了单个数据服务器的通信量，进而提升性能，我们提高元数据服务器的配置时使得元数据服务器能够存储更多的元信息，并且能够更快的查询元信息进而提升性能，这符合系统的可伸缩性的设计目标。2.2、 客户访问数据方式分析和设计 在采用单服务器的主从模式后，我们要解决的一个问题是避免元数据服务器成为系统性能瓶颈。所以我们必须最小化元数据服务器在客户端进行写入和读取数据时候的代价。目前有两种方式数据访问方式12。一种(图2-4)是客户向元数据服务器请求数据，元数据服务器查询元数据确定客户所需数据所在的数据服务器的位置然后通过元数据服务器把数据从数据服务器传递给客户端。这种方式有个很大的缺点就是操作数据和元数据都有经过元数据服务器，元数据服务器会受到自身IO 能力和网络限制，容易造成元数据服务成为系统性能瓶颈。还有第二种方式(图2-5)，在这种方式下，客户端向元数据服务器请求数据，主服务器返回数据的元数据，然后客户端依据数据元信息和数据服务器交互获得数据。在这个过程中客户端还可以缓存元数据，在缓存过期之前再次访问该数据可以绕开元数据服务器，这样大大减少了元数据服务器的通信数量，进而提高了性能。本系统中采用第二种方式。图2-4 经过元数据服务器转发数据流程图2-5 数据不经过元数据服务器流程（三）、 数据存储方式分析和设计（1）文件数据的存储设计 在KiddenFS 中每个文件都被分为了大小相同的块，一个文件可能包含一个或者多个块。每个文件以块的形式在数据服务器中存放。每个块都有一个全局唯一的标识符，如图2-6 所示。图2-6 数据节点中的数据块 在图2-6 中，数据块1 有两个副本分别存储在不同的数据节点之中。把数据分块存储有好几个好处。首先，如果一个文件比单个机器的存储容量大也能够在本系统中存储。因为不需要将一个大文件的所有块放在同一个机器上，这样可以充分利用整个系统的数据服务器。一个大文件的块很可能分布在集群的所有机器上。其次，将文件分块存储极大的简化了存储系统，因为每个块大小都固定，系统很容易计算出每个节点能够存储多少个块，并且消除了对元数据的依赖。最后，让每个数据块拥有多个副本用来给系统提供存取效率和容错性。为了保证当某个块损坏或者某台机器发生故障时系统能够运行，每个块都存在一定数量的副本，这些副本分散在不同的机器上。一个数据块不可用时，客户端可以从其它的机器上获取此块的副本，系统会定时扫描，如果某个块的副本数量不够，则系统会将此块副本复制到其它机器以便块的副本数量达到正常水平。拥有多个副本使得访问某个数据块时能够选择负荷最小的机器从而提高了访问效率。 数据块大小是关键的设计参数，本系统中默认块大小为64M 字节，这比一般的文件系统大得多。大的块大小提供如下优点。首先，它减少了客户端和元数据服务的通信量，因为同一个客户端在读写一个块只需要查询一次元数据服务器块的信息然后客户端可以将元数据缓存下来。其次，减少了客户端和数据服务器的通信量，因为块很大，客户端很有可能在一个块上执行许多操作，通过保持和块服务器持久的tcp 连接，它能够减少网络流量。第三，这减少了主服务器上元数据的大小，块越大每个文件分的块越少所以每个文件的元信息越少，这允许我们保持元数据在内存中。但是大块也有缺点，一个小文件由少量的块组成，甚至可能是一块。如果有许多的客户端访问同一个小文件，那么存储这些块的块服务器就会变成热点。解决这个热点的方式是为小文件设置较高的副本参数，使得小文件块的副本更加分散。（2）元数据的存储设计 在KiddenFS 中元数据服务器用于保存文件的元数据。元数据服务器保存三种主要类型的元数据：文件和数据块命名空间，文件到文件的数据块的映射集合，以及每个数据块的位置信息。元数据服务器会持久化存储文件和数据块的命名空间和文件到数据块的映射集合，这两种信息存储在FSImage 的文件之中，这个文件存储在元数据服务器的本地系统之中。对这两种元数据的修改都会写入文件名为EditLog的日志文件之中。元数据服务器在启动时会读取FSImage 和EditLog 到内存中，然后将EditLog 中的操作应用到内存的FSImage 上以便反映文件系统的修改，然后把内存中的FSImage 保存到本地文件系统中。元数据服务器不会持久化保存每个数据块的位置信息。元数据服务器在自己启动时和数据服务器加入集群的时候，元数据服务器会询问数据服务器它所包含的数据块的信息。之所以这样设计，因为元数据保存在内存中，所以元数据服务器操作的速度很快。而且，元数据服务器可以在后台简单而高效的周期扫猫自己的整个状态。这种周期性的扫描可以用来在数据服务器间实现块的垃圾收集的功能，用来实现数据服务器失效的时复制新副本的功能，用来实现负载均衡的块移动的功能，以及用来实现统计硬盘使用情况的功能等。 这种纯内存的机制一种可能的问题是，数据块的数量和整个系统的容量都受限于元数据服务器拥有的内存尺寸。不过实际上这不是一个严重的限制。对于每个64MB的数据块，元数据服务器只需管理不到64 字节的元数据。大多数的数据块是满的，因为每个文件只有最后一块是部分填充的。类似的，每个文件的命名空间通常在64字节以下，因为保存的文件名是用前缀压缩算法压缩过的。如果需要支持更大的文件系统，为元数据服务器增加额外内存的花费是很少的，而把元数据保存在内存之中带来了系统的简洁性，可靠性，高性能和灵活性。 元数据服务器启动后会进入一个称为安全模式的特殊状态。处于安全模式的系统是不会进行数据块的复制的。元数据服务器从所有的数据服务器接收心跳信号和数据块状态报告。数据块状态报告包括了某个数据服务器所有的数据块列表。每个数据块都有一个指定的最小副本数。当元数据服务器检测确认某个数据块的副本数目达到这个最小值，那么该数据块就会被认为是副本安全的；在一定百分比(这个参数可配置)的数据块被元数据服务器检测确认是安全之后(加上一个额外的30 秒等待时间)，系统将退出安全模式状态。接下来它会确定还有哪些数据块的副本没有达到指定数目，并将这些数据块复制到其他数据服务器上。这种在元数据服务器启动的时候查询数据服务器块位置然后周期查询的方式，简化了在数据服务器在加入和离开集群，重命名，失效，重启等等情况下，数据服务器和元数据服务器的同步问题。（3）日志的存储设计 对元数据的操作都会记录在日志之中，日志包含核心元数据变化的历史记录。这对系统十分重要。这不仅是因为它是元数据唯一的持久化存储记录，而且因为它起到了定义同步操作顺序的逻辑时间线的作用。文件和数据块以及他们的版本，都是唯一和持久地由它们创建时的逻辑时间标识的。因为元数据操作日志很重要，我们必须持久的保存它，并保证只有在元数据的变化被持久化保存后，这种变化才对客户端可见。否则，即使数据块没有发生任何问题，我们仍有可能丢失整个文件系统，或者丢失近期的客户端操作。所以，把操作日志复制到多台机器做备份，而且仅在把最近的日志记录写入本地以及远程机器的硬盘后，才会对客户端操作进行响应。写入之前元数据服务器批量处理数个日志记录，减少写入和复制的负载。（四）、 数据缓存方式分析和设计 缓存在分布式文件系统设计中对性能有着重要的影响。每个分布式文件系统设计过程中需要权衡各种方式的优缺点，找出最适合的缓存方式。一般来讲，缓存有四种位置:服务器端的内存，服务器端的磁盘，客户端的内存和客户端的磁盘。如果文件缓存位于服务器端内存，则客户在读取文件时，服务器端看看内存缓存是否存在文件，这样速度比较快。如果多个客户访问同一个缓存，服务器只需在设计时考虑并发处理就可以避免缓存一致性的问题。服务器端内存缓存实现起来也很方便。但是有个缺点，服务器端内存缓存对服务器的内存容量有很高的要求。如果文件缓存位于服务器端磁盘，则客户在读取文件时，服务器端从磁盘把缓存读到内存之中，然后再查看缓存是否存在文件，这样速度比较慢。同样，如果多个客户访问同一个缓存，服务器只需在设计时考虑并发处理就可以避免缓存一致性的问题。服务器端磁盘缓存实现起来也很方便比内存缓存稍微复杂。但是有个缺点，服务器端磁盘缓存的性能不够好，如果大量的请求访问，则需要多次访问磁盘。 如果文件缓存位于客户端内存，则客户在读取文件时，查看本地内存之中是否存在文件，这样速度很快。但是，这样会造成缓存的不一致，比如多个客户端缓存了同一个文件，并且同时写这样会造成缓存的不一致。如果文件缓存位于客户端磁盘和位于客户端内存一样，只是性能稍差。综合起来，位于服务器端的缓存不需要考虑一致性问题，但是对服务器要求很高。位于客户端的缓存要考虑数据一致性问题。由于KiddenFS 系统对服务器要求不能很高，并且Kidden 的文件模型是一次写入，多次读取，数据不一致的可能性很低，这样通过客户端缓存就可以达到所需要求。只需选择合适的不一致性策略即可。目前，有几种策略来针对数据不一致性。直写策略。当客户端写文件时会必须等待其它写操作完成。向缓冲区写后立即发送到服务器来更新文件。对于大规模写的文件系统，直写策略性能很低。写回策略。客户端现将数据写入本地缓存。一定时间之后，再将缓存写入服务器。这样会提高写操作性能，缺点是可能会造成数据丢失。由于本系统应用特点，大规模读的可能性不大。所以采用直写策略。（五）、负载均衡策略分析和设计对于分布式系统，负载均衡策略非常重要。好的负载均衡策略对提高服务器的性能有很大的帮助。目前存在以下负载均衡算法。轮询调度算法：轮询调度算法是所有调度算法中最简单也最容易实现的一种方法。在一个任务队列里，队列的每个成员（节点）都具有相同的地位，轮转法简单的在这组成员中顺序轮转选择。在负载平衡环境中，均衡器将新的请求轮流发给节点队列中的下一节点，如此连续、周而复始，每个集群的节点都在相等的地位下被轮流选择。这个算法在 DNS 域名轮询中被广泛使用。轮询法的活动是可预知的，每个节点被选择的机会是1/N，因此很容易计算出节点的负载分布。轮询法典型的适用于集群中所有节点的处理能力和性能均相同的情况，在实际应用中，一般将它与其他简单方法联合使用时比较有效。散列法：散列法也叫哈希法（HASH），通过单射不可逆的HASH 函数，按照某种规则将网络请求发往集群节点。哈希法在其他几类平衡算法不是很有效时会显示出特别的威力。例如，在前面提到的UDP 会话的情况下，由于轮询法和其他几类基于连接信息的算法，无法识别出会话的起止标记，会引起应用混乱。 而采取基于数据包源地址的哈希映射可以在一定程度上解决这个问题：将具有相同源地址的数据包发给同一服务器节点，这使得基于高层会话的事务可以以适当的方式运行。相对称的是，基于目的地址的哈希调度算法可以用在Web Cache 集群中，指向同一个目标站点的访问请求都被负载平衡器发送到同一个Cache 服务节点上，以避免页面缺失而带来的更新Cache 问题。最少连接法：在最少连接法中，平衡器纪录目前所有活跃连接，把下一个新的请求发给当前含有最少连接数的节点。这种算法针对TCP 连接进行，但由于不同应用对系统资源的消耗可能差异很大，而连接数无法反映出真实的应用负载，因此在使用重型Web服务器作为集群节点服务时（例如Apache 服务器），该算法在平衡负载的效果上要打个折扣。为了减少这个不利的影响，可以对每个节点设置最大的连接数上限（通过阈值设定体现）。最低缺失法：在最低缺失法中，平衡器长期纪录到各节点的请求情况，把下个请求发给历史上处理请求最少的节点。与最少连接法不同的是，最低缺失记录过去的连接数而不是当前的连接数。最快响应法：平衡器记录自身到每一个集群节点的网络响应时间，并将下一个到达的连接请求分配给响应时间最短的节点，这种方法要求使用ICMP 包或基于UDP 包的专用技术来主动探测各节点。在大多数基于LAN 的集群中，最快响应算法工作的并不是很好，因为LAN 中的ICMP 包基本上都在10ms 内完成回应，体现不出节点之间的差异；如果在WAN 上进行平衡的话，响应时间对于用户就近选择服务器而言还是具有现实意义的；而且集群的拓扑越分散这种方法越能体现出效果来。这种方法是高级平衡基于 拓扑结构重定向用到的主要方法。加权法：加权方法只能与其他方法合用，是它们的一个很好的补充。加权算法根据节点的优先级或当前的负载状况（即权值）来构成负载平衡的多优先级队列，队列中的每个等待处理的连接都具有相同处理等级，这样在同一个队列里可以按照前面的轮转法或者最少连接法进行均衡，而队列之间按照优先级的先后顺序进行均衡处理。在这里权值是基于各节点能力的一个估计值。本系统采用动态的负载均衡策略。数据服务器定期向元数据服务器发送本机状态信息。元数据服务器依据当前的各个数据服务器状态，针对不同的请求计算出最合适的服务器来处理这些请求。这些状态包含内存大小，处理器计算能力以及磁盘容量和网络延迟等等。具体每个状态所占的权值可以通过不断调整来设定。（六）、 系统架构分析KiddenFS 分布式文件系统采用主从单服务器结构。从物理上看由两个部分组成:元数据服务器和数据服务器。一个KiddenFS 集群是由一个元数据服务器节点和一定数目的数据服务器节点组成。元数据服务器是一个中心服务器，负责管理文件系统的名字空间以及客户端对文件的访问。集群中的数据服务器节点负责管理它所在节点上的数据的存储。系统暴露了文件系统的名字空间，用户能够以文件的形式在上面存储数据。从内部看，一个文件其实被分成一个或多个数据块，这些块存储在一组数据节点上。元数据服务器执行文件系统的名字空间操作，比如打开、关闭、重命名文件或目录。它也负责确定数据块到具体数据节点的映射。数据节点负责处理文件系统客户端的读写请求。在元数据节点的统一调度下进行数据块的创建、删除和复制。图2-7 KiddenFS 体系结构图（1） 文件的创建和写入 客户端首先向元数据服务器请求创建一个文件。元数据服务器对请求参数做一些检查，比如文件是否存在等等。客户端创建文件的请求其实并没有立即发送给元数据服务器，事实上，在刚开始阶段客户端会先将文件数据缓存到本地的一个临时文件。应用程序的写操作被透明地重定向到这个临时文件。当这个临时文件累积的数据量超过一个数据块的大小，客户端才会联系元数据服务器。元数据服务器将文件名插入文件系统的层次结构中，并且分配一个数据块给它。然后返回数据服务器的标识符和目标数据块给客户端。接着客户端将这块数据从本地临时文件上传到指定的数据服务器上。当文件关闭时，在临时文件中剩余的没有上传的数据也会传输到指定的数据服务器上。然后客户端告诉元数据服务器文件已经关闭。此时元数据服务器才将文件创建操作提交到日志里进行存储。如果元数据服务器在文件关闭前宕机了，则该文件将丢失。如果不采用客户端缓存，由于网络速度和网络堵塞会对吞估量造成比较大的影响。 当客户端向系统文件写入数据的时候，一开始是写到本地临时文件中。假设该文件的副本系数设置为3，当本地临时文件累积到一个数据块的大小时，客户端会从元数据服务器获取一个数据服务器列表用于存放副本。然后客户端开始向第一个数据服务器传输数据，第一个数据服务器一小部分一小部分地接收数据，将每一部分写入本地仓库，并同时传输该部分到列表中第二个数据服务器节点。第二个数据服务器也是这样，一小部分一小部分地接收数据，写入本地磁盘