一个集群实例

基于Linux集群系统的资源共享方案

这是高二暑假为了参加上海市Intel杯创新大赛而做的课题，原本是为了建立一个简单的集群模型然后研究一下负载均衡算法的，结果由于课业的压力，没能完成，结果就成了这副德性。这是初稿，不是最终的参赛论文，这样的文章当然也没法去参加那样的大赛。在这里也想说句，20届intel杯创新大赛参赛项目也真的没什么好看头，除了第一名的人脸识别，其它都没什么特色，要不我这个课题也得不了CS组第三名。

其中有些图无法显示，懒得弄了，如果大家想要我再加上。


基于Linux集群系统的资源共享方案

作者：
上海市大同中学 Andy Jing
指导教师：Laura Wang



摘要：　作者设计CSLIS（Clustering Searching of Library Information System，集群图书信息检索系统）把几个图书馆的资料联合在一起，在不使用大型数据库的情况下巧妙地解决了资源共享的问题。作者重点研究如何提高检索速度。使用集中式负载均衡算法并行地执行接收到的客户请求，这要比使用单一的数据库系统效率高得多，主进程事先创建好一个线程池，各自对应一个远程节点。任务到达时，主进程动态地将任务分配空闲的远程从进程从而减轻负载，同时收集节点及网络负载并图形化地显示，作者使用proc等多种手段减少由于性能收集而带来的效率降低．而且通过监视客户端的信息发送间隔来不断地对集群算法进行优化。同时CSLIS使用NFS等手段增加用户操作及系统管理的透明性。
关键字： SMP（对称多处理器） 负载均衡 线程 主从进程 发送时间间隔（IAT）


一、引言

为了使读者最快地找到想要的图书，一个检索系统是必要的。当然这个问题已经得到解决。但是如果为了方便读者检索图书，将很多的图书馆的内容连成一个大的网络，读者使用一个单一的接口就可检索所有这些图书馆的图书，就有点问题了。数据不能通过简单的方式共享。建立一个统一格式的数据库开销很大。所以作者想到了使用集群来解决这一问题。各个图书馆可能使用不同的操作系统，不同的数据库系统，使用集群不但可以忽略掉这些因素，还可以大大提高信息检索的效率。
顾名思义，“集群”是“群”，它将各种不同性能的计算机联结起来，使它们按照一定的方式工作，来处理那些用超级计算机来处理的事务或科学计算，不但达到了任务目的，同时相对于那些大型的超级计算机，大大节约了成本。因此对于像大型图书馆的图书检索系统来说，集群性价比更高。
集群是一种由互相连接的计算机组成的并行或分布式系统，可以作为单独、统一的计算资源来使用。系统中的计算机和互连网络通常都是商用的非定制系统，这是集群系统与传统的MPP系统的主要区别。简言之，就是由多台同构或异构的计算机连接起来协同完成特定的任务就构成了集群系统。
一般计算机任务都是串行方式处理的，也就是说以堆栈或队列的方式来安排任务的执行。一个任务执行完以后下一个任务才能执行。采用集群技术以后，任务的分配及完成就成了并行化的方式。也就是说任务同时被执行，不用再等待其它任务的完成，对于现代高速发展的计算机来说，这一点非常重要，充分利用了资源。而价格则比同等功能的SMP（对称多处理器）机器便宜得多。
集群按照应用类型可分为以下几类：高性能集群（High Performance，HP）、负载均衡集群 (Load Balance, LB)、高可用性集群（High Availability，HA）。
作者设计的集群通过并发线程处理任务的方式使任务的完成更加高效，同时为了进一步提高性能，使用了负载均衡算法。在高效完成任务的同时，可以实时地根据集群当前的负载来决定被分配任务的节点。一个优秀的系统，在碰到错误的时候应该可以做出积极的响应并自动处理错误使工作恢复正常，因此作者又在集群中实现了一些容错机制。

CSLIS特点
CSLIS是作者为实现一个高效图书检索系统而设计的一个针对性的简化模型。对于一个真正投入应用的检索系统，它是非常复杂的。为了更加方便地研究集群这个核心内容，作者使用了简化的模型，即简单的文本提取。
CSLIS是作者根据已有集群模型，加入了自己的特色实现而成。其突出特点有以下几点：
（1） 使用主从结构
（2） 主任务生成一系列子任务来处理请求，减轻了主任务的负担，使服务器的响应能力大幅度提高。
（3） 用线程来处理子任务，相对于传统的进程池方式，既提高了初始化速度，又使子任务切换速度大大增加，提高了整体性能。
（4） 除了主任务对客户的请求连接之外，其它连接均使用UDP套接口进行通信，经过一些处理，它完全可以安全工作，并且速度比TCP快得多。
（5） 实时的性能监视，包括各节点的处理器及内存的使用情况，各个节点以及整体的网络负载。
（6） 使用Proc（一个用户级的内核接口，用户可以通过它获得系统内核的工作信息）内核接口获得内核信息，系统资源信息的获得更加快速高效。


二、开发及测试环境

硬件环境：
CSLIS集群的开发工作在三星P20笔记本上进行。测试使用4点节的集群环境，P20作为主节点，三台赛扬PC机为子节点。它们的基本配置如下表：

主节点 子节点1 子节点2 子节点3
处理器 P4 2.4GHz 赛扬II700 赛扬II700 赛扬II700
内存 256M 128 128 128

软件环境：
四个节点均以Redhat 9.0为平台，使用2.4.8版本内核。在CSLIS开发的过程中，采用GCC3.3（GNU C Complier）编译器，使用GDB（GNU Debugger）调试器完成部分调试工作，由于gdb不能对线程及子进程进行调试监控，所以很多的程序调试工作只能通过其运行情况来评估。
另外，要设计一个集群并让它在Linux系统上正常运行，需要考虑它的运行环境。如，节点如何启动，节点之间怎样互相访问效率最高等。所以这里需要对Linux系统的几个部分进行调整，以使它更好地支持集群的运行。相关的配置主要分三个步骤进行（如图1）：hosts主机名文件、NFS文件系统及xinetd超级服务器（xinetd是用来在系统中监听接入请求并启动相应服务的工具，它可以有效地节约系统资源，不必启动很多的服务来监听各自的端口）的配置。


1、 为了使节点之间的访问更加方便，作者CSLIS中选择使用主机名来访问集群中的各个节点，这要比直接使用IP地址来得直观。因此这里需要修改/etc/hosts文件来在集群中直接使用主机名来访问其它节点。以下是/etc/hosts的内容：

192.168.1.119 windlamf windlamf.cluster.org windlamf
127.0.0.1 windlamf localhost.localdomain localhost
192.168.1.118 andy andy.cluster.org andy

2．为了减轻在节点之间拷贝文件的麻烦，作者只在主节点上保留了一份集群程序的拷贝，并使用NFS文件系统使所有节点来共享这份拷贝。从而使系统对于管理员来说更加透明．这里需要修改/etc/fstab和/etc/exports文件来实现NFS服务。相关配置如下：
本例中/etc/exports文件配置如下：
/home/andy (rw)
/home/andy是使网络上的其他计算机可以访问的目录。对于这一项目，必须使用绝对路径名。在同一行中，还列出了能够访问这一目录的计算机及其访问权限，这里是可读写如果这一行中的内容超过了行的长度限度，可以使用标准的连续符(反斜杠\ )使它继续到下一行。
实际配置过程中，/etc/fstab文件为如下内容，读者可以依据需要修改。

windlamf:/home/andy /home/andy nfs rw 0 0

3、在集群初始化阶段使用UDP广播包来启动各个子节点，所以在每个子节点上需要配置xinetd超级服务器来监听UDP广播。这样的好处是，不用一直运行从进程来监听集群启动信息，而是用超级服务器监听相应端口，在UDP广播包真正到达的时候才启动从进程，从而节省了系统资源，牺牲的仅仅是少量的进程启动时间。
首先需要在/etc/inetd.d/目录下建立一个slave脚本文件，其内容如下：
service slave
{
disable = no
port = 5000
socket_type = dgram
protocol = udp
wait = yes
user = andy
server = /home/andy/cluster/bin/slave
}
然后还要修改/etc/service文件将这个slave服务注册为系统服务。在这个文件末尾加上：
slave 5000/udp
两个字段分别表示：服务名、监听端口号/协议。


三、设计实现

1、概述

CSLIS旨在通过集群来实现高速、高负载量的信息检索系统。限于各方面的条件，作者实现一个完整的系统实在困难。所以使用了简化的模型来构造集群。主要任务是从文本文件中提取文本并使负载均衡化。
CSLIS系统采用主从接口的方法进行设计。即集群中的一个节点作为主节点，上面运行主进程。其它节点上运行从进程。主从进程之间通过主进程下的一系列子任务进程通信。这里作者进行了一些大胆的尝试。一般传统上的并行处理方式均使用并发子进程的方式，而作者认为线程显然是个更好的选择。因为总体来说线程与进程相比有两大优点，一是它启动速度比进程快三个数量级；二是它的切换不需要完整的上下文切换，因为线程之间共享很多资源，所以切换速度比进程又快上很多。因此这些子任务作者均使用线程处理，代替传统的进程池处理方式。使集群启动阶段和子任务的切换方面速度得到大的提升。
下面分别对主进程和客户进程的主要实现过程进行分析。因为采取的是主从结构，所以主要从主进程、从进程及客户进程三方面进行分析。在此之前，先要配置某些系统文件来实现所需要的功能。

2、主从接口结构的具体实现
主进程
主进程是整个主从进程结构中的支柱，它是集群系统的中枢。对于主进程先分析它的启动与终止和子任务安排，最后将详细分析集群的主要算法——负载均衡以及作者自己的一点尝试。
主进程有两个阶段：初始化和处理移交。在初始化阶段中，从集群中的任意一个节点被启动，然后它向本网段的所有节点的特定端口发送UDP数据包来激活所有能够激活的从进程。所有节点均使用超级服务器xinetd来监听此UDP广播。远程从进程被激活并注册。结果产生一个利用率表，每个注册过的从进程在其中都有一个条目。每个条目包括计算机名称、IP地址和预计利用率索引。在处理移交阶段，主进程接收每个请求并传送给利用率表中最不忙碌的计算机上的从进程。

(1) 初始化与终止
为了使主从进程之间有比较透明的初始化过程，作者采用让主进程启动时发送UDP广播数据包的方式来启动其它节点的所有可能的从进程。每一个成功启动的从进程会向主进程发送回自己的主机信息。其中包括从进程自己的主机名。主进程会在主节点上将从进程注册信息输出。以下是执行的主要步骤（参看图2）：
（1）初始化，读取配置文件net.conf的信息来提取广播地址
（2）得到本机（主节点）地址以便加入广播包
（3）向整个网段发送广播包以启动其它节点
（4）监听注册信息并从标准输出输出



对于集群系统的终止，主进程使用了一个信号处理器和一个全局标识变量来解决终止问题。主进程使用共享变量来标示工作状态，并将它初始化为“TRUE”，一旦主进程的信号处理器捕捉到“ctrl+c”按键组合，就会将标识符设为“FALSE”，当主进程检测到标识符的改变时（如图3），就会停止接收外部请求，并等待子线程处理完各自的任务。当所有子任务完成工作时，主进程执行一切收尾工作，关闭使用过的共享存储区，关闭信号处理器，关闭使用过的套接口等
以下是主要执行步骤：
（1）初妈化。包括全局变量的设置及信号处理器的初始化
(2) 处理任务阶段
（3）检查标识符以判断是否结束主进程
（4）满足条件主进程做退出处理，否则继续处理任务。



(2) 子任务安排及请求处理——负载均衡

负载均衡是CSLIS的核心算法，它包括两种，一种是静态负载均衡，一种是动态负载均衡。只是利用系统负载的平均信息，而忽视系统当前的负载状况的方法被称为静态负载均衡。根据系统当前的负载状况来调整任务划分的方法被称为动态负载均衡。
动态负载均衡中，任务是在程序运行期间被分配到处理器的。动态负载均衡可以被分为集中式和分散式两类。
在集中式动态负载均衡中，任务是从一个中心位置分发的，存在清晰的主从结构（就像作者设计的集群）。其中主进程直接控制一组从进程中的每个进程。相反，在分散式动态负载均衡中，任务是在任意进程间传送的，一组工作者进程对问题进行操作，它们之间互相交互，最后向一个单独进程报告。一个工作者进程可以从其他工作进程处接收任务，也可以向其他工作者进程发送任务。
CSLIS中采用集中式动态负载均衡算法，
在集中式动态负载均衡中(图4)，主进程（主处理器）持有要执行的任务集（实际中，是由客户进程把任务发送给主进程），任务由主进程发送给从进程，从进程完成一个任务后，会向主进程请求另一个任务。这种机制是工作池方法的本质。
工作池技术可容易地用于简单的分治问题，也可用于那些任务很不相同，大小不同的问题。一般最好先分配较大或最复杂的任务，如果在计算中分配大任务较晚，完成小任务的从进程会闲呆着，以等待大任务的完成。
当在执行期间任务数会发生变化时，也较适合应用工作池技术。在一些应用，特别是搜索算法中，一个任务的执行会产生一些新的任务，尽管最终的任务数必会减为零以指示计算的完成。可用一个队列存放当前等待的任务。如果所有任务大小相同且同等重要，则可使用简单的先进先出队列，如果某些任务比其他任务更重要（如期望更快地到到解），就要首先把这些任务送到从进程。其他的一些信息，如当前的最佳解等，可由主进程加以保存。
集中式动态负载均衡的一个突出优点是，主进程很容易识别计算会何时终止。对一个计算，如果其中的任务是从任务队列中获取的，那么当以下条件满足时计算就终止：
任务队列为空
每个进程已经请求了另一任务，而又没有任务新的任务产生。

另外一种负载均衡的实现方式是分散式负载均衡。由于分散式动态负载均衡算法实现起来比较复杂，以及它的适用范围，这部分内容不再详细论述，读者可以参看其它参考资料以获得相关信息。

通过了解以上内容，读者清楚地了解了集中式负载均衡的原理。 在CSLIS中，主进程采用并行方式处理接收到的请求。它在初始化阶段产生与注册子节点个数相等的线程来处理输入请求，如下：


作者在主进程中初始化一个TCP套接口来监听外部请求，一旦接收到请求。线程便从所有的子线程中选出空闲的一个来处理请求，因为每一个本地子任务都对应一个远程从进程，所以只要用一个标识符来标识子线程的状态（活动或者是空闲），主线程使用一个循环对所有子线程的标识符进行检查，将外部请求转交给空闲的子任务（整体结构请参看图5）。



这里之所以使用事先建立好的线程而不是接收到请求的时候再创建，是因为这样可以减少因为启动线程而浪费的CPU时间（尽管线程创建只需要极短的时间）。值得一提的是作者这里用线程池来代替进程池，线程的优点便是生成的时候时间上比进程要快好几个数量级，而且线程的切换不需要完整上下文切换，比进程之间切换要快得多。所以这样的做法不仅使集群系统初始化的过程大大加快，同时提高了处理请求的速度。



从进程
从进程在子节点上启动，它与主节点上的某一个子线程对应。它接收并处理由主节点传送来的任务，处理完成后发送回结果。

(1) 初始化
在每个节点上用超级服务器程序xinetd监听5000（预先定义的广播端口）端口的UDP广播（广播包中带有主节点的地址信息），一旦接收到广播信息xinetd便启动从进程。从进程读取广播包中主进程的信息并将自己的地址信息通过UDP信息包发送回主节点注册。
主要有两个步骤：
（1）得到主节点的地址信息
（2）向主节点注册

(2) 处理请求

从进程建立一个UDP套接口来接收来自主节点的请求，处理以后把结果发送回去。
相关代码如下：

客户进程
客户程序请求一个位于服务器硬盘的苦干行文本。它向服务器程序发送包含文件名和行号的请求。服务器程序打开文件，取得文本行并将它作为响应发送回客户程序。客户端在向服务器发送请求的时候，在每个数据包之间有一定的时间间隔，简称IAT。如果IAT值偏小，服务器可能无法响应极其快速的客户请求（当然这取决于服务器的性能，使用集群正是提高这一响应能力），如里IAT值偏大，又不能快速的完成任务。所以这里使用三种不同的时间间隔分布，以便在不同环境下找到合适的时间间隔而达到软为理想的性能。同时为集群系统的优化提供一个检测标准。

时间间隔分布

客户程序每隔一定的时间间隔向主节点发送文本请求。这个时间间隔使用了三种时间分布，为的是用不同的请求间隔时间来判断整个集群的性能以及依此进行优化。这三种时间分布分别是：扫描分布、脉冲分布、指数分布。
扫描分布是从某个高的发送时间间隔开始，逐渐减少到事先指定的某个低的发送时间间隔为止（通俗来说就是逐渐提高发送请求的频率）。图7很好地说明了这种时间分布方式。


在脉冲分布(如图中，流是相等间隔的，高时间间隔请求后面跟随着突发性的低的时间间隔请求。空发之后，流回复到高时间间隔值，直到发送最后一个请求。



指数分布（如图9）。顾名思义，是间隔时间按照指数方式分布的一种方案。为了实现它，可以先产生一定范围内均匀分布的随机数random，然后套用公式：
Random = -1 * log(random)
进行计算，这样可以获得从无穷大迅速减少到0的时间间隔值。




数据检验

主进程在处理完客户请求并发回结果时，在数据包中附带结果的出处，当客户端接收到主节点发送给它的处理结果后，可以据此核实是否是它开始请求的文件及相应的行数。使处理结果准确无误。

以上是系统的核心部分。用户可参看源代码来了解它的具体工作步骤。
四、实时性能

为了监视每个节点的运行情况，包括它们的系统资源使用率及网络负载等。一个集群性能监视程序是必须的。它既可以使用户清楚地了解集群的工作状况，又可以为作者提供优化集群的依据。
性能监视程序分为两部分：性能收集和性能显示。性能收集进程运行在各个节点上。每个节点启动的时候都会自动去行它。它持续不断地收集本地的性能数据，并在一定的时间间隔以后将数据发送给主节点，然后性能显示部分就会处理这些数据并交由一个GUI前端以图形化的方式显示出来。
性能收集：
系统CPU和内存的使用率可以在Linux的命令行键入top来获得。因此在主程序中使用system()系统调用来调用命令是个不错的想法。但Linux给用户提供了一种高效的解决方案。那就是proc文件系统。
proc是一个内核接口，用户可以通过查看它里面的一些文本文件来获得系统内核的当前工作信息，而不需要直接访问内核，使用proc文件系统有两个好处：一，因为直接访问内核的数据结构来检索系统信息还要掌握内核的内部知识，而使用proc文件系统只不过是读取几个文本文件,操作相对简易；二，从文本文件中提取数据要比执得system()系统调用快得多。所以这里选用proc文件系统作为各项数据的来源。
这个收集实时统计信息的程序运行在集群的每个节点上，作者将它作为主进程（或从进程）的子进程来启动，即使用fork-execl的方法。这种方法是先生成一个子进程，然后将子进程的镜像换成想要运行的程序，这里是性能收集进程。性能显示进程运行在主节点上。这些进程每秒阅读并处理文本一次，所以它们对节点的资源只产生很小的影响。甚至在没有显示进程时，它们也可以运行，只是发送给显示进程的UDP信息包会被忽略。
CSLIS的性能收集进程主要提取每个节点的如下数据：
（1） 处理器使用率
（2） 内存使用率
（3） 流入流出数据包
（4） 整体网络负载
这些数据分别要从/proc/stat、/proc/net/dev、/proc/meminfo三个文件中提取。当然，因为proc是一个内核接口，从它里面得到的数据并不能直接显示给用户，因为它们深奥难懂。还要进行一系列的运算得到用户想要的结果。以下将分别介绍上述四个性能数据的获得及计算方法。如里有问题或对要提取的数据不太清楚，可以使用man proc来查看proc文件系统的联机手册。
（1） 处理器使用率
这里要从/proc/stat中提取四个数据：用户模式（user）、低优先级的用户模式（nice）、内核模式（system）以及空闲的处理器时间（idle）。它们均位于/proc/stat文件的第一行。CPU的利用率使用如下公式来计算。
CPU利用率 = 100 *（user + nice + system）/（user + nice + system + idle）
为了得到集群的实时性能，性能数据的收集是持续不断的。当第二次得到以上四个数据的时候，将它们分别与前一次的数据相减，然后再按照上面的公式进行计算。
（2） 内存使用率
这里需要从/proc/meminfo文件中提取两个数据，当前内存的使用量(cmem)以及内存总量(amem)。
内存使用百分比 = 100 * (cmem / umem)
（3）网络利用率
为了得到网络利用率的相关数据，需要从/proc/net/dev文件中获得两个数据：从本机输出的数据包数，流入本机的数据包数。它们都位于这个文件的第四行。
性能收集程序开始记录下这两个数据的初始值，以后每次获得这个值后均减去这个初始值即为从集群启动开始从本节点通过的数据包。
另外作者还利用上述数据计算出网络的平均负载，方法如下：
平均网络负载 = (输出的数据包+流入的数据包) / 2

性能显示：
CSLIS的性能显示模块，其功能是将性能收集进程收集到的主要数据以图形化的方式展现。程序因考虑到跨平台性和移植性，从而采用Java语言编写。程序挂接在主节点上，由主节点启动并运行。
性能显示模块的工作原理非常简单：当性能收集进程将运算好的进程数据发送给主进程后，主进程将这些数据通过一定的格式写入本地的一些文本文件中，然后性能显示模块以一秒为单位时间片，周期性读取文本文件中的数据，并将其图形化。





五、结束语

全文介绍了CSLIS的特色功能以及其具体实现方法，并同时阐述了集群的一些基本知识。这个简化的模型已经体现出了核心内容——集群技术，包括负载分散以及负载均衡等。作者认为在这个基础上，如果能对高性能、高有效性、容错性几方面再多做些深入的工作。势必会更好地提高集群的性能。
作者个人认为集群系统的性能还可以从以下几个方面进行加强。首先，实现子节点以无盘工作站的方式工作，就可以减少集群的配置工作量，同时增加了增减节点的自由度；其次，关于容错性，子进程或主进程如果因错终止，需要能够自动重启并恢复丢失的工作。集群技术不仅仅可用来做信息检索，对于科学计算，服务器等它都是很好的选择。希望作者对CSLIS的研究能够使各位能够对集群技术加以重视，使它能够更好地为人们服务。

参考文献：
（美）Alex Vrenios 《Linux集群体系结构》 机械工业出版社
（美）Kert Wall 《GNU/Linux编程指南 第二版》 清华大学出版社
（美）Barry Wilkinson Michael Allen 《并行程序设计》 机械工业出版社
（英）Neil Matthew Richard Stone 《Linux程序设计 第二版》 机械工业出版社