基于linux的集群系统
基于linux的集群系统（一）
本文是《基于LINUX的集群系统》系列文章的第一篇。作者就集群系统这一概念进行了概述，介绍了集群系统的发展以及国内外主要的集群系统解决方案。
第一台计算机问世已经半个世纪了，在这期间计算机技术经历了五次更新换代。更新换代的标志主要有两个：一个是计算机的器件，另一个是系统体系结构。从第一代到第五代计算机，器件发生了根本的变化：从电子管、晶体管发展到集成电路，而集成电路又经小规模、中规模、大规模、非常大规模等阶段发展到超大规模阶段。系统体系结构的不断改进，许多重要的概念的不断提出并且得到实现，推动计算机技术向更高的层次发展。从早期的变址寄存器、通用寄存器、程序中断和I/O通道等概念，到虚拟存储器、Cache存储器、微程序设计、系列机、基于总线的多CPU系统、向量处理机等概念，发展到64位RISC处理器、基于MPP、NUMA、集群等体系结构的可伸缩并行处理系统，计算机系统技术也取得了突飞猛进的发展。
将多台同构或异构的计算机连接起来协同完成特定的任务就构成了集群系统。早在二十世纪七八十年代，Digital equipment公司和Tandem计算机公司就开始了集群系统的研究与开发工作。
集群系统主要分为两种：
高可用性集群和高性能集群。
高可用性集群的主要功能就是提供不间断的服务。有许多应用程序都必须一天二十四小时地不停运转，如所有的web服务器、工业控制器、ATM、远程通讯转接器、医学与军事监测仪以及股票处理机等。对这些应用程序而言，暂时的停机都会导致数据的丢失和灾难性的后果。
高性能集群通过将多台机器连接起来同时处理复杂的计算问题。模拟星球附近的磁场、预测龙卷风的出现、定位石油资源的储藏地等情况都需要对大量的数据进行处理。传统的处理方法是使用超级计算机来完成计算工作，但是超级计算机的价格比较昂贵，而且可用性和可扩展性不够强，因此集群成为了高性能计算领域瞩目的焦点。
集群系统采用的操作系统主要有VMS、UNIX、WindowsNT和Linux。
美国DEC公司（Digital Equipment Corporation）开发的VMScluster系统开发最早，技术也很成熟，应用也很广泛，但由于VMS操作系统只能在DEC公司的VAX系列和Alpha系列服务器上运行，VMScluster的应用受到很大限制。
UNIX是服务器或工作站上普遍使用的操作系统，它运行稳定、安全性也比较好，因此许多大的公司都采用了基于UNIX的集群系统解决方案，如DEC、HP、SUN、IBM、NCR和DG等公司，其中在国内影响比较大的主要是DEC、HP、SUN和IBM。其中DEC公司的Trucluster系统提供了由4台Digital Alpha Server组成的集群系统，它集高可靠性、高可用性和易管理性于一身，是关键业务计算机系统的理想解决方案。
基于WindowsNT的集群系统解决方案厂商主要有Mircrosoft和DEC。Microsoft于1995年就开始了集群系统的开发工作。Windows 2000中已经增加了集群功能，该高可用性集群叫做WolfPack，也叫做Microsoft Cluster Server (MCS)。它主要是在企业级对基于Windows NT服务器的应用程序提供可用性和可升级性。WolfPack现在支持两个服务器，一个用来对用户提供服务，另一个作为备份服务器使用。Microsoft下一步的目标是将WolfPack支持的节点数扩展到16个。Wolfpack的缺陷在于：它只提供了两个节点的失败恢复功能，而没有采用复杂的应用程序资源管理功能，因此在一定程度上影响了系统的高可用性、高可靠性和可升级性。Wolfpack不能支持多种操作系统，而只能运行于Windows NT操作系统上。由于WindowsNT操作系统本身在稳定性、大型并行计算上与UNIX系统存在较大差距，目前主要在中小型系统上应用。但是随着WindowsNT系统走向成熟，基于WindowsNT的计算机集群系统将获得更广泛的应用。
九十年代末期，Linux操作系统不断走向成熟，它的健壮性不断增强，并且提供了GNU软件和标准化的PVM、MPI消息传递机制，最重要的是Linux在普通PC机上提供了对高性能网络的支持，这样就大大推动了基于Linux的集群系统的发展。
Turbolinux公司推出了能够显著地提高基于TCP/IP协议的多种网络服务的服务质量的高可用性集群系统Turbocluster。Red Hat也提供了基于Linux Virtual Server思想构建的高可用性集群系统Piranha。由Ericsson软件工程研究中心开发的高可用性集群系统Eddie的主要目的是提供一个商业级的，能提供较好的服务质量的web服务器的解决方案。
Platform公司开发的高可用性集群系统Lsf提供了分布式集群系统的解决方案，通过将物理上分离的多个集群连接在一起使使多个同构或异构的计算机能够通过局域网或广域网共享计算资源，并能够为用户提供对资源的透明访问。
高性能集群系统MOSIX为Linux核心增添了集群计算的功能。在MOSIX集群环境中，用户无需对应用程序进行修改，或将应用程序与库连接起来，或将应用程序分配到不同的节点上运行。MOSIX会自动将这些工作透明地交给别的节点来执行。
日本的F5公司开发出了高可用性集群BIG-IP，它是使用于本地网络站点或数据中心的高可用的、智能化的负载平衡产品，它提供了对网络流量的自动和智能的管理。与前几种集群系统不同的是，BIG-IP向用户提供的是一个即插即用设备，而其它的提供的都是软件方法。
IBM、Microsoft和Intel于2000年7月联合发布了一种高可用性服务器集群软件及硬件包，这种服务器集群的配置包括32台IBM Netfinity 8500R及Intel Pentium Ⅲ Xeon处理器，运行IBM的DB2 Universal Database和Microsoft Windows 2000 Advanced Server操作系统，每分钟可以执行440879次交易。这套系统面向数据密集的应用，特别是B2B、电子商务和企业资源规划领域。
在科学计算领域中，人们开始把注意力投向通过普通PC机或工作站的集群来代替昂贵的超级计算机。比较成功的例子是高性能集群系统Beowulf，它最初是由NASA的Goddard Flight Center进行开发的，主要目的是支持大规模的科学计算问题，如地球和太空科学面临的一些计算问题。
国内也有不少公司进行了集群系统的研究和开发工作。
联想公司在1999年9月推出了用于分布式高性能计算的NS10000高性能集群服务器，该系统是一个四节点的系统，主要基于联想万全4500R服务器，以总体成本相对较低的设备组合，足以替代传统RISC小型机和中型机的工作，而价格仅为市场上同等性能小型机的1/2--1/4。
朗新公司也推出了类似于Turbocluster的高可用性集群系统LongShine Cluster Server。
中国自主开发研制的集群式高性能计算机集群系统"自强2000-SUHPCS"于2000年9月在上海大学问世。这一系统的峰值速度达到每秒3000亿次浮点操作。是当前中国国内集群式高性能计算机系统中速度最快的。
典型集群系统介绍之一
在《基于Linux的集群系统》系列文章的第二部分，作者将向我们介绍几个最典型的集群系统。
1. Lsf
如何管理各种各样的计算资源(如：CPU时间、内存空间、网络带宽、应用程序等)是许多企业当前都很头疼的问题。尤其是对于那些员工遍布全球的公司而言，如何充分利用有限的计算资源是非常关键的问题。由platform公司开发的lsf 多集群系统使多个异构的计算机能够通过局域网或广域网共享计算资源，并能够为用户提供对资源的透明访问。Lsf现在主要支持以下三种大规模资源共享：
一个大企业中的多个部门，每个部门可以有一个或多个集群，这样就使得部门内部和部门之间可以共享资源。
较小部门的数据中心。大的昂贵的计算资源如超级计算机可以透明地与远方较小的部门直接进行共享。
通过松散连接的站点共享资源。
Lsf将多个集群连接在一起，一个集群往往是企业中的一个部门，每个集群中有一个主控机，此主控机负责收集该集群系统中的各台主机的负载信息，并且根据各主机的负载信息情况对作业进行调度。各个集群系统之间根据一定的策略进行资源共享。在每个主控机上定义了该集群能共享哪些集群系统中的资源。当用户发送了一个任务请求时，lsf系统能将此任务发送到对应的资源所在地，并根据调度策略选择负载较轻的机器对此任务进行处理。当多个用户请求同一个资源时，根据用户的请求优先级来确保优先级高的用户的紧急任务能首先得到满足。Lsf还具有以下特点：
提供了增强的计算能力。
通过全局资源共享，用户可以访问各种各样的计算资源，许多闲置的计算机现在都可以充分利用起来进行任务处理，许多机器也可以并行地执行同一个任务，这样就大大增强了用户的计算能力。
lsf提供了用户可配置的安全策略。
通过让用户使用RFC931协议、Kerberos、和DCE认证等策略，系统保证了远方的任务来自授权的用户。
每一个集群都是一个自治的系统。
每个集群中的主控机的配置文件中记录了如下信息：如允许在多个集群系统之间传输的任务的数量与类型，允许在多个集群之间共享资源的用户名。
提供非共享的用户账号和文件系统。
当任务在多个集群之间进行传输时，用户的账号可以根据配置文件进行映射。为了支持异构的系统，lsf通过在任务执行前后将文件在集群系统之间传递来提供对非共享的文件系统的支持。
良好的可扩展性。
在单一的集群系统中通过主控机进行管理，所有的配置信息都在主控机上，多个集群系统之间信息的传递主要是与主控机有关，而与集群中的其它主机无关。因此lsf的集群能非常容易地扩展到成百甚至上千台。
lsf系统支持多种操作系统平台。
如主要的UNIX平台：Sun Solaris、 HP-UX、 IBM AIX、 Digital UNIX/Compaq Tru64 UNIX、SGI IRIX以及 Red hat Linux、 Windows NT、Windows 2000等。
2. TurboCluster
TurboCluster是一个企业级的集群方案，它允许在多个计算机上构建高可用的、可扩展的网络。它支持Intel和Alpha芯片，支持Linux 、Windows NT 和Solaris操作系统平台。使用TurboCluster系统可以显著地提高基于TCP/IP协议的多种网络服务的服务质量，这些服务包括Web、Mail、News和Ftp等。TurboCluster具有良好的可用性、可扩展性和可管理性，集群内部的实际服务器的数量可以扩充到无限台。TurboCluster是一种基于软件的集群系统解决方案，它还能够支持异构的网络环境。它的结构如图2-1所示。
当客户向集群系统发送一个请求时，该请求首先到达高级流量管理器，高级流量管理器通过一定的调度策略将此请求转发到集群中的某一台实际服务器上对此请求进行处理，最终的回应请求将直接发送给客户。由于最终的回应请求没有通过高级浏览管理器而是直接发送给客户，这样大大减轻了高级浏览管理器上的负载，从而降低了瓶颈产生的可能。TurboCluster中采用的调度策略有：轮回(Round Robin)、加权轮回(Weighted Round Robin)、最少连接(Least Connection)。为了减少高级流量管理器产生失效的可能，TurboCluster为高级流量管理器准备了一个备份机。该备份机不断询问管理器来确认它正在正常工作，一旦发现主管理器已经失效，备份机将接替它继续工作。
图2-1 turbocluster结构图
TurboCluster具有如下一些增强的性能。
通过heartbeat在备份机上监测流量管理器的运行状态来提供更高的可用性。
对不可预测的系统或应用程序的失效进行自动管理。
提供动态的负载平衡，它能够消除瓶颈并且处理峰值负载。
高级流量管理器只转发已经授权的请求，通过在实际的应用程序服务器的前端增加虚拟防火墙来提高网络的安全性。
TurboCluster对外只显现出流量管理器的IP，而集群系统中的实际服务器的IP地址对外界而言是不可见的。
当实际服务器正在对外界提供服务时就可以对它进行维护工作。
基于Linux的集群系统（三）
文是《基于Linux的集群系统》系列《典型集群系统分析》的第三篇，作者将继续向我们介绍几个最典型的集群系统。
3. Linux Virtual Server
Linux虚拟服务器（Linux Virtual Server, LVS）建筑于实际的服务器集群之上，用户看不到提供服务的多台实际服务器，而只能看见一台作为负载平衡器的服务器。实际的服务器通过高速局域网或地理上分散的广域网连接。实际服务器的前端是一台负载平衡器，他将用户的请求调度到实际服务器上完成，这样看起来好像所有服务都是通过虚拟服务器来完成的。Linux虚拟服务器能够提供良好的可升级性、可靠性和可用性。用户可以透明地增加或减少一个节点，可以对实际服务器进行监测，如果发现有节点失败就重新配置系统。
Linux Virtual Server的结构如图3-1所示。：
图3-1 Linux虚拟服务器结构图
3.1 调度算法
LVS提供了四种调度算法：轮转调度，加权轮转调度，最少连接调度，加权最少连接调度。
轮转调度（Round Robin Scheduling）
轮转调度不考虑服务器的连接数和响应时间，它将所有的服务器都看作是相同的。当以轮转的形式将连接分发到不同的服务器上。
加权轮转调度(Weighted Round Robin Scheduling)
根据每个机器的处理能力的不同给每个机器分配一个对应的权重，然后根据权重的大小以轮转的方式将请求分发到各台机器。这种调度算法的耗费比其它的动态调度算法小，但是当负载变化很频繁时，它会导致负载失衡，而且那些长请求会发到同一个服务器上。
最少连接调度(Least Connection Scheduling)
最少连接调度将用户请求发送到连接数最少的机器上。最少连接调度是一种动态调度方法，如果集群中各台服务器的处理能力相近，则当负载的变化很大时也不会导致负载失衡，因为它不会把长请求发送到同一台机器上。但是当处理器的处理能力差异较大时，最少连接调度就不能很好的发挥效能了。
加权最小连接调度(Weighted Least Connection Scheduling)
根据服务器的性能不同而给它们分配一个相应的权重，权重越大，获得一个连接的机会就越大。有如下的运算方法：（假设共有n台机器，每一台服务器i的权重为Wi (i=1，..，n)，活跃连接数为Ci (i=1，..，n)， 所有的连接数为Ci (i=1，..，n)的总和，下一个连接会发送给服务器j，服务器j满足以下的要求）：
(Cj/ALL_CONNECTIONS)/Wj = min { (Ci/ALL_CONNECTIONS)/Wi } (i=1，..，n)
由于ALL_CONNECTIONS是一个常数，因此上面的式子可以优化为：
Cj/Wj = min { Ci/Wi } (i=1，..，n)
3.2 负载平衡方法
LVS提供了三种IP级的负载平衡方法：Virtual Server via NAT 、Virtual Server via IP Tunneling、Virtual Server via Direct Routing。
Virtual Server via NAT方法使用了报文双向重写的方法， Virtual Server via IP Tunneling采用的是报文单向重写的策略， Virtual Server via Direct Routing采用的是报文转发策略，这些策略将在以后的文章中详细描述。
4. MOSIX
MOSIX为Linux核心增添了集群计算的功能。它支持的操作系统平台有BSD/OS 和Linux，它允许任意多个基于X86/Pentium的服务器和工作站协同工作。在MOSIX集群环境中，用户无需对应用程序进行修改，或将应用程序与库连接起来，或将应用程序分配到不同的节点上运行。MOSIX会自动将这些工作透明地交给别的节点来执行。
MOSIX的核心是适应性的资源管理算法，它对各节点的负载进行监测并做出相应的回应，从而提高所有进程的整体性能。它使用抢先的进程迁移方法来在各节点中分配和再分配进程，从而充分利用所有的资源。适应性的资源管理算法具体上又包括适应性的负载平衡算法、内存引导算法和文件I/O的优化算法。这些算法都对集群中的资源使用情况的变化做出响应。如：节点上的不平衡的负载分布或由于内存不足而导致的过多的磁盘换入换出。在这种情况下，MOSIX将进程从一个节点迁移到另外一个节点上，从而来均衡负载或将进程迁移到有足够的内存空间的节点上。
由于MOSIX是在Linux的核心中实现的，因此它的操作对应用程序而言是完全透明的。可以用它来定义不同的集群类型，这些集群中的机器可以相同也可以不同。
与Turbocluster、Linux Virtual Server、Lsf等集群系统不同的是，MOSIX集群中的每个节点既是主节点又是服务节点，不存在主控节点。对于那些在本地节点创建的进程而言，该节点就是一个主节点；对于那些从远方节点迁移过来的进程而言，该节点就是服务节点。这意味着可以在任意时刻向集群中增加节点或从集群中删除节点，而不会对正在运行的进程产生不良的影响。MOSIX的另外一个特性就是它的监测算法能够监测每个节点的速度、负载、可用内存、IPC 以及I/O rate 。系统使用这些信息来决定将进程发送到哪个具体的节点上。当在某个节点上创建了一个进程以后，该进程就在这个节点上执行。当该节点的负载超过了一定的阀值以后，就将该进程透明地迁移到别的节点上继续执行。
MOSIX文件系统采用直接文件系统访问的方法，它可以允许迁移到别的节点的进程在本地进行I/O操作。这样就减少了需要进行I/O操作的进程与创建该进程的节点之间的通讯，从而允许这些进程更加自由地在集群中的节点中进行迁移。MOSIX文件系统使所有节点都可以像访问本地文件系统一样透明地访问其它节点上的所有目录和文件。
一个低端的MOSIX配置可以包含通过以太网连接起来的多台PC机。一个较大的配置可以包含通过快速以太网连接起来的多台工作站和服务器。高端的MOSIX配置可以包含通过Gigabit-Ethernet连接起来的多台SMP 或非SMP工作站和服务器。
5 EDDIE
Eddie的主要目的是提供一些供那些进行重要任务处理的网站使用的工具，从而使这些网站能够提供持续的高级服务。Eddie创建了一个真正的分布式web服务器结构，它支持分布于不同的物理地点的web服务器。它的结构如图5-1所示。
图5-1所示的分布式服务器包含两个集群，它们分别是site 1 和site 2。每个集群都包含着一台域名服务器和若干台运行web服务器软件的实际的服务器。当用户敲入一个域名时，首先在Local DNS上对这个域名进行解析，找出与其对应的IP地址。如果Local DNS无法对这个域名进行解析，就将此域名发送到Authoritative DNS上，Authoritative DNS返回应该访问的服务器的IP地址，然后用户就可以访问指定的服务器上的内容了。
图5-1 Eddie集群结构图
Eddie主要包含两个软件包：HTTP网关和增强的DNS服务器。如图5-2所示，在每个站点上增加一个新的服务器（即前端机），在其上运行HTTP网关来接受外界发来的请求并且将请求调度到合适的后端机上执行，DNS服务器上运行增强的DNS服务器软件，通过该软件可以在多个地理上分散的网址上均衡负载。
Eddie主要有以下与众不同的特点：
提高了web服务器的吞吐量。通过提供强大的负载平衡能力，Eddie使用户可以充分利用分布式web服务器中的所有资源。主要在两个地方使用了负载平衡。首先后端机将本机上的负载信息如CPU负载、内存、磁盘延迟、运行队列数据以及页面错等信息发送给前端机，前端机根据负载轻重将外界请求发送到合适的服务器上。另外在增强DNS服务器软件中也提供了负载平衡的功能，前端机和后端机的综合负载信息都发送到Authoritative DNS服务器上，然后Local DNS可以根据各个Authoritative DNS上的负载的轻重来决定将域名解析的任务发送到哪一台Authoritative DNS上。这样就可以充分利用分布式服务器环境中的所有资源，增强了web服务器的吞吐量。
提供很好的服务质量。首先Eddie通过使用静态和动态负载平衡策略提高了web服务器的吞吐量，减少了用户请求的响应时间；其次，当用户发一个请求时，系统就要检查是否来自该用户的连接已经存在，如果存在，就将请求继续发送到上次对该请求提供服务的服务器上，这样就保证了用户对web访问的持续性。如果没有足够的资源，则将用户请求加入等待队列，并且告诉用户它的请求要等待一会儿才会被处理。
基于Linux的集群系统（四）
典型系统小结及评测标准
在本系列的前面几篇文章中，作者为我们介绍了几个最典型的集群系统。在本篇中，作者将就典型的集群系统做一个小节，并提出对集群系统的评测标准。
1. 典型集群系统小结
典型的集群共有的特点是：
集群都是将普通PC 工作站、工作站或服务器通过某种方式连接起来构成的多机系统。连接方式可以采取通过网络适配器和网络集线器，或通过将各个机器的RS-232串口直接连接起来，还可以通过内存通道卡和内存通道集线器的方式连接各台机器。
集群系统都具有良好的可用性。即它们都能够在集群的某部分资源出故障的情况下继续向用户提供持续的服务。几乎所有的典型集群都拥有灾难恢复功能。
集群系统有良好的可扩展性。只需很少的配置工作就可以方便地向集群中加入或删除工作节点。
典型的集群系统提供了良好的可管理性。管理人员通过简单的操作就可以对集群中的工作节点或控制节点进行配置工作。
集群系统一般都提供了负载平衡功能。负载平衡包括静态负载平衡和动态负载平衡，为了最大程度地利用集群中的一切资源，集群需要具有动态负载平衡功能，它能够通过监视集群中的实际节点的负载情况并动态地进行调度的改变。
大部分集群系统都有一个主控机，它能够对集群中的机器的运行状态进行监视，而且能够根据各机器的负载轻重进行任务的调度。
2. 评测标准
检验集群系统的主要指标是可靠性（reliability）、高可用性(availability)、可维护性（serviceablity）和其它相关特点和功能。
可靠性主要指集群中的软件、节点计算机和共享存储设备的可靠和稳定程度。
高可用性(High Availabity，HA)要求当硬件系统发生故障时，运行在该系统上的数据不会丢失，而且在尽可能短的时间内恢复应用系统的正常运行，能够满足上述要求的系统称为高可用性系统。
在美国D.H.Brown Association 公司的集群系统评测报告中，将集群系统的测试项目分为11个大项，即：
1.集群内备份与恢复：考察集群对故障和条件变化的检测和响应能力。
2.集群可配置性：考察集群硬件和软件配置的灵活性。
3.节点内故障恢复：考察独立节点硬件和软件故障条件下的恢复能力。
4.集群并行数据库可存取性：考察集群对并行数据库的支持程度和效率，即集群内各节点同时访问同一数据库的能力和效率。
5.集群内高可用性可管理能力：考察集群系统提供的集群管理工具和界面的易使用性和友好性。
6.集群单一系统映像：考察集群在分布式环境中对客户端提供的单一系统的形象。完美的情况就是为了管理和使用方便，集群提供分布式集群资源就像单机系统一样。
7.灾难恢复能力：考察集群在地理数据镜像、远程数据复制、远程自动故障处理等方面的能力，即集群在火灾、洪水和地震等条件下保持正常运行和自动故障恢复的能力。
8.硬件和软件RAID功能：考察集群对硬件和软件RAID（Redudant Array of Independent Disks）的支持程度，从而保证数据的安全性和可恢复性。
9.节点内故障预防：考察节点对故障的预警能力和节点内故障的易分辨性。
10.节点故障在线维护：考察节点在不停机条件下增加或更换部件的能力以及节点内软件的可管理性（如软件升级）。
11.节点维护特征：考察集群在重启动自动配置（在部分部件失效或增加冗余部件的情况下）、远程操作和远程故障通知等方面的能力
基于Linux的集群系统(五)
关键技术分析之 进程的放置和迁移
通过对本系列前面四篇文章的学习，您对于集群系统应该已经有了一个整体的认识。从本篇开始作者将对集群系统进行更深入的探讨。本篇作为《关键技术分析》的第一篇将向我们讲述进程放置和迁移的一些关键技术。
1. 进程的放置
在集群系统中，进程的到达时间和新到达进程所需的资源量都是不可预测的，因此进程的放置和迁移是非常重要的问题。由于集群系统中的不可预测性，进程有时就会被放置在不合适的机器上，进程迁移就给了系统一个弥补这样的错误的机会。通过较好的算法将新创建的进程放置到合适的节点上执行，并且对某些进程进行迁移可以缩短任务的平均执行时间，因此从整体上提高了系统的性能。
进程的放置问题是非常复杂的，因为集群中的资源是异构的，如：内存、CPU、进程间通讯等等。衡量这些资源耗费的方法也是不同的：内存的单位是字节，CPU的单位是循环、通讯资源的单位是带宽。
进程的放置策略分为静态放置策略和动态放置策略。静态放置策略通过预先定义的规则对新创建的进程进行分配，它不使用运行时的信息。而动态放置策略则根据系统状态的变化将进程重新放置到最适宜的节点上。
常见的静态放置策略由三种：Round Robin（RR）、Best-Fit(BF)、Round Robin Next-Fit (NF)。
Round Robin将新创建的进程以轮转的形式放置到集群中的各节点上。这种方法的缺陷在于如果新创建的进程所需的内存量大于将要分配到其上的节点的可用内存大小，则会导致算法的失败。
一种改进的方法是使用Best-Fit方法，进程将被放置到具有最大可用内存的节点上。
Round Robin Next-fit以Round Robin的方式扫描各节点，并且将进程发送到第一个有足够大内存的节点上。它的缺点就是可能会导致负载不均衡地分配到各个节点。
三种进程放置策略的性能如图1-1所示。（进程的平均大小是16MB）
从该图可以看出，NF算法能够最充分地利用内存资源。当集群中的节点数增加时，BF算法和RR的算法的性能也随之有明显的下降，之所以产生这种情况是因为当节点数增加时，集群中的内存总量也随之成比例地增加，而且新增加的节点也会创建新的进程，这也就意味着大进程的数量也会随之增多，这些大进程对于BF算法和RR算法而言是很难放置的，因此会导致它们的性能的下降。
一种动态的进程放置策略叫做MS（Migrate the Smallest process），它以Round Robin的形式扫描所有的节点，并且将新进程放置到下一个节点上。与Round Robin不同的是，如果要放置的节点的内存不足以提供给新来的进程使用，则MS算法将迁移走一个进程。将要被迁移的进程是该节点上所有进程中最小的一个但是迁移走它刚好能满足新进程所需内存，而且也有其它的节点能够容纳这个将被迁移的节点，这种方法有较小的网络开销，如果不存在这样的节点，如其它的所有节点都没有足够大的内存空间，则算法失败。MS算法和NF算法的比较如下图所示。当进程的平均大小为
以上各种算法都是集中式的进程放置策略，都需要使用全局信息来决定放置策略，不利于可扩展性，不能有效地在拥有多个节点的集群上执行。一种基于MS的分布式进程放置算法(Windowed MS)是这样实现的：它将迁移的进程放置到从信息窗口中选出的具有最大可用内存的节点上。所谓信息窗口指的是一个缓冲区，里面保存着其它节点的可用内存的信息。每隔一定的时间就会将其它各节点的内存信息收集到信息窗口中，并对信息窗口进行更新。
图1-1 进程放置策略性能比较图
图1-2 进程放置策略性能比较图
2. 进程的迁移
早在20世纪80年代，人们就开始了进程迁移的研究。大多数的研究主要着眼于如何用更好的方法在机器之间传送进程的状态。同构的进程迁移指的是进程迁移的原始和目标机器的体系结构相同，而异构的进程迁移指的是不同体系结构的机器之间的进程迁移。同构的进程迁移系统的例子有：V Charllote 、DEMOS/MP、 Sprite、 Condor、 Accent ；异构的进程迁移系统有：Tui、Emerald、HMF(Heterogeneous Migration Facility )等。进程迁移主要用于以下几种情况下。
当失效的机器修复了错误，重新进入集群系统时，需要将某些该机器上原来运行的进程重新迁移回来。
在集群系统中进行负载共享。为了让一个进程使用尽可能多的CPU时间，需要将它迁移到能提供大部分指令和I/O操作的机器上执行。但是有时候负载共享也有缺陷，因为大部分的进程只需一少部分的CPU时间，考虑到进程迁移的开销，如果对那些简单的可以在本地运行的进程进行迁移是得不偿失的，但是对于那些需要大量的处理时间的程序如仿真程序，迁移进程是非常有效的。
提高通讯性能。如果一个进程需要与其它进程频繁地进行通讯，这时将这些进程放置得近一些就会减少通讯的开销。具体的迁移方法就是将一个进程迁移到其它进程所在的CPU上。
可用性。当网络上的某台机器失效时，通过进程迁移可以将进程迁移到其它机器上继续执行，这样就保证了系统在遇到灾难时的可用性。
重新配置。当对集群进行管理时，有时需要将服务从一个节点移到另一个节点，透明的进程迁移可以在不停机的情况下迁移服务。
使用集群中的某些机器的特殊能力。如果某个进程能够从集群中的某台特定机器上受益，它就应该在那台机器上执行。如进行数值计算的程序能够通过使用数学协处理器或超级计算机中的多个处理器来大大缩短程序执行时间。
尽管进程迁移已经在实验环境中成功地实现了，但是它还没有被广泛地接受。一个原因是占主流的平台如MSDOS、 Microsoft Windows以及许多种类的UNIX操作系统都没有对进程迁移的支持。另一个原因是因为进程迁移开销可能比不迁移进程时的开销还要大。但是当前，两种新的计算领域又促进了进程迁移的发展，一个是移动计算，另一个是广域计算。移动计算指的是那些便携式的小型计算机的计算问题。而广域计算是指广域网中的机器的计算问题。
进程迁移将一个正在执行的进程从一个节点迁移到通过网络连接的另一个节点上（也就是说，不使用本地共享内存机制）。进程所在的原始节点上的操作系统应该将进程的所有状态都包装起来，这样目的机就可以继续执行此进程。
要完成进程迁移需要迁移进程的状态，尤其是进程的地址空间，对其它进程的访问（如套接口、管道等），代码（可以组成地址空间的一部分）以及执行状态（寄存器、堆栈等）。除了这些，还需要将那些对原始的进程所有访问都重新链接到新的进程拷贝上，不然迁移就不是无缝的，就会导致错误。整个进程迁移操作必须是原子操作，这样才能避免进程的丢失或者是有两个拷贝。
为了进行进程迁移需要再进行以下的修改：
必须对文件系统进行一定的修改使每个机器看到相同的名字空间。
必须传送足够的状态从而确保正常的核心调用能够在远端机器上正常执行。
一些特殊的核心系统调用如gettimeofday 、getpgrp应该发回到原始节点执行。
下面通过一个异构进程迁移的例子来说明进程迁移的整个过程。图1-3说明了进程是如何在Tui进程迁移系统中从一个机器上迁移到另一个机器上的。
首先是对一个程序进行编译，针对Tui支持的四种体系结构，将程序分别编译四次。
程序在原始机上以普通方式执行。（如命令行方式）
当选定一个迁移的进程时，migrout程序首先为进程设置检查点，然后挂起进程，然后进行内存映像，接着扫描全局变量、堆栈和堆来定位所有的数据。再把所有的这些都转化为一种中介的格式传送给目标机。最后，杀死原始机器上的进程。
在目标机上，migrin程序取得中介值并创建新的进程，由于程序已经根据目标机的体系结构进行了编译，因此正文段的信息和数据报的类型信息都是可用的。然后通过重新创建全局变量、堆和堆栈，程序从检查点处继续执行。
经过统计，选择空闲主机并且开始一个新的进程需要0.1秒的时间，平均迁移时间是330毫秒。通过进程迁移可以将性能提高近5倍。
图1-3 进程迁移过程示意图
基于Linux的集群系统（六）
关键技术分析之 高可用性
本篇是《关键技术分析》的第二篇，将为您讲述集群系统高可用性，主要包括集群管理器和节点的高可用性。
计算机系统的可靠性用平均无故障时间（MTTF）来度量，即计算机系统平均能够正常运行多长时间，才发生一次故障。系统的可靠性越高，平均无故障时间越长。可维护性用平均维修时间（MTTR）来度量，即系统发生故障后维修和重新恢复正常运行平均花费的时间。系统的可维护性越好，平均维修时间越短。计算机系统的可用性定义为：MTTF/(MTTF+MTTR) * 100%。由此可见，计算机系统的可用性定义为系统保持正常运行时间的百分比。
计算机产业界通常用如下表所示的"9"的个数来划分计算机系统可用性的类型。
通过硬件冗余或软件的方法都可以从很大程度上提高系统的可用性。硬件冗余主要是通过在系统中维护多个冗余部件如硬盘、网线等来保证工作部件失效时可以继续使用冗余部件来提供服务；而软件的方法是通过软件对集群中的多台机器的运行状态进行监测，在某台机器失效时启动备用机器接管失效机器的工作来继续提供服务。
一般来说，需要保证集群管理器的高可用性和节点的高可用性。Eddie、Linux Virtual Server、Turbolinux、Piranha和Ultramonkey 都采用了类似于图1的高可用性解决方案。
集群管理器的高可用性
为了屏蔽集群管理器的失效，需要为它建立一个备份机。主管理器和备份管理器上都运行着heartbeat程序，通过传送诸如"我活着"这样的信息来监测对方的运行状况。当备份机不能在一定的时间内收到这样的信息时，它就激活fake程序，让备份管理器接管主管理器继续提供服务；当备份管理器又从主管理器收到"我活着"