一、集群和负载均衡的概念

（一）集群的概念
　　集群（Cluster）是由两台或多台节点机（服务器）构成的一种松散耦合的计算节点集合，为用户提供网络服务或应用程序(包括数据库、Web服务和文件服务等)的单一客户视图，同时提供接近容错机的故障恢复能力。集群系统一般通过两台或多台节点服务器系统通过相应的硬件及软件互连，每个群集节点都是运行其自己进程的独立服务器。这些进程可以彼此通信，对网络客户机来说就像是形成了一个单一系统，协同起来向用户提供应用程序、系统资源和数据。除了作为单一系统提供服务，集群系统还具有恢复服务器级故障的能力。集群系统还可通过在集群中继续增加服务器的方式，从内部增加服务器的处理能力，并通过系统级的冗余提供固有的可靠性和可用性。
（二）集群的分类
1、高性能计算科学集群：
　　以解决复杂的科学计算问题为目的的IA集群系统。是并行计算的基础，它可以不使用专门的由十至上万个独立处理器组成的并行超级计算机，而是采用通过高速连接来链接的一组1/2/4 CPU的IA服务器，并且在公共消息传递层上进行通信以运行并行应用程序。这样的计算集群，其处理能力与真正超级并行机相等，并且具有优良的性价比。
2、负载均衡集群：
　　负载均衡集群为企业需求提供更实用的系统。该系统使各节点的负载流量可以在服务器集群中尽可能平均合理地分摊处理。该负载需要均衡计算的应用程序处理端口负载或网络流量负载。这样的系统非常适合于运行同一组应用程序的大量用户。每个节点都可以处理一部分负载，并且可以在节点之间动态分配负载，以实现平衡。对于网络流量也如此。通常，网络服务器应用程序接受了大量入网流量，无法迅速处理，这就需要将流量发送给在其它节点。负载均衡算法还可以根据每个节点不同的可用资源或网络的特殊环境来进行优化。
3、高可用性集群：
　　为保证集群整体服务的高可用，考虑计算硬件和软件的容错性。如果高可用性群集中的某个节点发生了故障，那么将由另外的节点代替它。整个系统环境对于用户是一致的。
　　实际应用的集群系统中，这三种基本类型经常会发生混合与交杂。
（三）典型集群
科学计算集群：
1、Beowulf
当谈到 Linux 集群时，许多人的第一反映是 Beowulf。那是最著名的 Linux科学软件集群系统。实际上，它是一组适用于在 Linux 内核上运行的公共软件包的通称。其中包括流行的软件消息传递 API，如“消息传送接口”(MPI) 或“并行虚拟机”(PVM)，对 Linux 内核的修改，以允许结合几个以太网接口、高性能网络驱动器，对虚拟内存管理器的更改，以及分布式进程间通信 (DIPC) 服务。公共全局进程标识空间允许使用 DIPC 机制从任何节点访问任何进程。
2、MOSIX
Beowulf类似于给系统安装的一个支持集群的外挂软件，提供了应用级的集群能力。而MOSIX是彻底修改Linux的内核，从系统级提供了集群能力，它对应用而言是完全透明的，原有的应用程序，可以不经改动，就能正常运行在MOSIX系统之上。集群中的任何节点都可以自由地加入和移除，来接替其它节点的工作，或是扩充系统。MOSIX 使用自适应进程负载均衡和内存引导算法使整体性能最大化。应用程序进程可以在节点之间实现迁移，以利用最好的资源，这类似于对称多处理器系统可以在各个处理器之间切换应用程序。由于MOSIX通过修改内核来实现集群功能，所以存在兼容性问题，部分系统级应用程序将无法正常运行。
负载均衡/高可用性集群
3、LVS（Linux Virtual Server）
这是一个由国人主持的项目。
它是一个负载均衡/高可用性集群，主要针对大业务量的网络应用（如新闻服务、网上银行、电子商务等）。
LVS是建立在一个主控服务器(通常为双机)（director）及若干真实服务器（real-server）所组成的集群之上。real-server负责实际提供服务，主控服务器根据指定的调度算法对real-server进行控制。而集群的结构对于用户来说是透明的，客户端只与单个的IP（集群系统的虚拟IP）进行通信，也就是说从客户端的视角来看，这里只存在单个服务器。
N54537Real-server可以提供众多服务，如ftp, http, dns, telnet, nntp, smtp 等。主控服务器负责对Real-Server进行控制。客户端在向LVS发出服务请求时，Director会通过特定的调度算法来指定由某个Real-Server来应答请求，而客户端只与Load Balancer的IP（即虚拟IP，VIP）进行通信。
其他集群：
现在集群系统可谓五花八门，绝大部分的OS开发商，服务器开发商都提供了系统级的集群产品，最典型的是各类双机系统，还有各类科研院校提供的集群系统。以及各类软件开发商提供的应用级别的集群系统，如数据库集群，Application Server 集群，Web Server集群，邮件集群等等。
（四）负载均衡
1、概念
由于目前现有网络的各个核心部分随着业务量的提高，访问量和数据流量的快速增长，其处理能力和计算强度也相应地增大，使得单一的服务器设备根本无法承担。在此情况下，如果扔掉现有设备去做大量的硬件升级，这样将造成现有资源的浪费，而且如果再面临下一次业务量的提升时，这又将导致再一次硬件升级的高额成本投入，甚至性能再卓越的设备也不能满足当前业务量增长的需求。

针对此情况而衍生出来的一种廉价有效透明的方法以扩展现有网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性的技术就是负载均衡（Load Balance）。
2、特点和分类
负载均衡(Server Load Balance)一般用于提高服务器的整体处理能力，并提高可靠性，可用性，可维护性，最终目的是加快服务器的响应速度，从而提高用户的体验度。　　

负载均衡从结构上分为本地负载均衡(Local Server Load Balance)和地域负载均衡(Global Server Load Balance)(全局负载均衡)，一是指对本地的服务器群做负载均衡，另一是指对分别放置在不同的地理位置、有不同的网络及服务器群之间作负载均衡。　　

地域负载均衡有以下的特点：

（1）解决网络拥塞问题，服务就近提供，实现地理位置无关性

（2）对用户提供更好的访问质量

（3）提高服务器响应速度

（4）提高服务器及其他资源的利用效率

（5）避免了数据中心单点失效
3、负载均衡技术主要应用

（1）DNS负载均衡 最早的负载均衡技术是通过DNS来实现的，在DNS中为多个地址配置同一个名字，因而查询这个名字的客户机将得到其中一个地址，从而使得不同的客户访问不同的服务器，达到负载均衡的目的。DNS负载均衡是一种简单而有效的方法，但是它不能区分服务器的差异，也不能反映服务器的当前运行状态。

（2）代理服务器负载均衡 使用代理服务器，可以将请求转发给内部的服务器，使用这种加速模式显然可以提升静态网页的访问速度。然而，也可以考虑这样一种技术，使用代理服务器将请求均匀转发给多台服务器，从而达到负载均衡的目的。

（3）地址转换网关负载均衡 支持负载均衡的地址转换网关，可以将一个外部IP地址映射为多个内部IP地址，对每次TCP连接请求动态使用其中一个内部地址，达到负载均衡的目的。

（4）协议内部支持负载均衡 除了这三种负载均衡方式之外，有的协议内部支持与负载均衡相关的功能，例如HTTP协议中的重定向能力等，HTTP运行于TCP连接的最高层。

（5）NAT负载均衡 NAT（Network Address Translation 网络地址转换）简单地说就是将一个IP地址转换为另一个IP地址，一般用于未经注册的内部地址与合法的、已获注册的Internet IP地址间进行转换。适用于解决Internet IP地址紧张、不想让网络外部知道内部网络结构等的场合下。

（6）反向代理负载均衡 普通代理方式是代理内部网络用户访问internet上服务器的连接请求，客户端必须指定代理服务器,并将本来要直接发送到internet上服务器的连接请求发送给代理服务器处理。反向代理（Reverse Proxy）方式是指以代理服务器来接受internet上的连接请求，然后将请求转发给内部网络上的服务器，并将从服务器上得到的结果返回给internet上请求连接的客户端，此时代理服务器对外就表现为一个服务器。反向代理负载均衡技术是把将来自internet上的连接请求以反向代理的方式动态地转发给内部网络上的多台服务器进行处理，从而达到负载均衡的目的。

（7）混合型负载均衡 在有些大型网络，由于多个服务器群内硬件设备、各自的规模、提供的服务等的差异，我们可以考虑给每个服务器群采用最合适的负载均衡方式，然后又在这多个

1.有三个布尔操作：

not, and, or

2.  优先级

例子：

1. 在console输入：

not not True or False and not True

输出是：True

2. 在console输入：

(not not True or False) and not True

输出是：False

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n = 0;
int InsSort(int a[], int s, int h) {
    int x = 0, j = 0;
    for (int i = s; i < n; i += h) {
        x = a[i];
        for (j = i-h; j>=s && x<a[j]; j -= h) {
            a[j+h] = a[j];
        }
        a[j+h] = x;
    }
    return 0;
}

int ShellSort(int a[]) {
    int inrc = n;
    do {
        inrc = inrc/3+1;
        for (int i = 0; i < inrc; i++) {
            InsSort(a, i, inrc);
        }
    } while (inrc > 1);
    return 0;
}

int main()
{
    int a[] = {503, 87, 512, 61, 908, 170, 897, 275, 653, 426,
                154, 509, 612, 677, 765, 703};
    n = 16;
    ShellSort(a);

    for (int i = 0; i < n; i++) {
        if (a[i] < 10) {
            printf("00");
        } else if (a[i] < 100) {
            printf("0");
        }
        printf("%d ", a[i]);
    }
    printf("\n");
        return 0;
}