分布式计算算法

Ⅰ 分布式计算机系统有什么特点

分布式计算机系统是由多台计算机通过网络连接形成的计算机系统，其主要特点包括：
1. 分布性：分布式计算机系统中的计算资源和数据存储分布在不同的计算节点上，可以是物理上的分布，也可以是逻辑上的分布。这使得系统能够利用多台计算机的处理能力和存储能力，提高整体的计算性能和容量。
2. 并行性：分布式计算机系统中的多个计算节点可以同时执行任务，实现并行计算。通过任务的分发和协调，系统可以将大规模的计算任务划分为多个子任务并行处理，加快计算速度，提高系统的吞吐量。
3. 可扩展性：分布式计算机系统具有良好的可扩展性，可以根据需求增加或减少计算节点。当需要处理更大规模的任务或增加系统的容量时，可以通过添加计算节点来扩展系统。这使得系统能够适应不断变化的计算需求。
4. 高可用性：分布式计算机系统具有较高的可靠性和容错性。由于系统中的计算节点相互独立工作，当其中一个节点发生故障时，其他节点仍然可以继续工作，保证系统的可用性。此外，系统通常采用冗余和备份机制来保障数据的安全性和可恢复性。
5. 数据通信：分布式计算机系统通过网络进行数据通信和协作。节点之间通过消息传递或远程过程调用等方式进行通信，实现数据的共享和协同计算。良好的数据通信机制是分布式系统的关键，对系统的性能和效率有着重要影响。
6. 分布式算法：分布式计算机系统需要采用特定的分布式算法来协调和管理各个计算节点之间的工作。这些算法包括分布式任务调度、数据同步、一致性协议等，保证系统的正常运行和数据的一致性。
总体而言，分布式计算机系统通过将计算资源和数据分布在多个计算节点上，实现高性能、可扩展和高可用的计算能力。它在大规模数据处理、高性能计算、云计算和分布式人工智能等领域具有广泛的应用前景。

Ⅱ 分布式系统常用的一致性算法有哪些

在做服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法. 典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。 常用的算法是对hash结果取余数 (hash() mod N)：对机器编号从0到N-1，按照自定义的hash()算法，对每个请求的hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。那么，如何设计一个负载均衡策略，使得受到影响的请求尽可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以说Consistent Hashing 是分布式系统负载均衡的首选算法。 1、Consistent Hashing算法描述 下面以Memcached中的Consisten Hashing算法为例说明。 由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在[0,232-1]间，如果我们把一个圆环用232 个点来进行均匀切割，首先按照hash(key)函数算出服务器（节点）的哈希值， 并将其分布到0～232的圆上。 用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器（节点）上。 Consistent Hashing原理示意图 新增一个节点的时候，只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候，只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响，因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。 Consistent Hashing添加服务器示意图 虚拟节点（virtual nodes）：之所以要引进虚拟节点是因为在服务器（节点）数较少的情况下（例如只有3台服务器），通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的（稀疏的），仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品（replicas），本质上与实际节点实际上是一样的（key并不相同）。引入虚拟节点后，通过将每个实际的服务器（节点）数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候，落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的州胡氏，因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。 虚拟节点对Consistent Hashing结果的影响 从上图可以看出，在节点数为10个的情况下，每个实际节点的虚拟节点数为实际做团节点的100-200倍的时候，结果还是很均衡的。 第3段中有这些文字：“但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法册散得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；” 为何是 (N-1)/N 呢？解释如下： 比如有 3 台机器，hash值 1-6 在这3台上的分布就是： host 1: 1 4 host 2: 2 5 host 3: 3 6 如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成： host 1: 1 3 5 host 2: 2 4 6 可以看到，还在数据位置不变的只有2个： 1，2，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3这样的话，受影响的数据太多了，势必太多的数据需要重新从 DB 加载到 cache 中，严重影响性能 【consistent hashing 的办法】 上面提到的 hash 取模，模数取的比较小，一般是负载的数量，而 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向了，那个图还是挺直观的。 以下部分为一致性哈希算法的一种PHP实现。点击下载

Ⅲ 分布式计算系统 Maekawa算法 13个进程怎么划分子集

第一个进程子集是（1.2.4.10）；第二个进程子集是（2.3.5.11）；以后每一列数字递增，13以后从1重新开始。

分布式系统的类型，大致可以归为三类：

1、分布式数据，但只有一个总数据库，没有局部数据库。

2、分层式处理，每一层都有自己的数据库。

3、充分分散的分布式网络，没有中央控制部分，各节点之间的联接方式又可以有多种，如松散的联接，紧密的联接，动态的联接，广播通知式联接等。

(3)分布式计算算法扩展阅读

衡量分布式系统的指标

1、性能：系统的吞吐能力，指系统在某一时间可以处理的数据总量，通常可以用系统每秒处理的总的数据量来衡量；系统的响应延迟，指系统完成某一功能需要使用的时间。

系统的并发能力，指系统可以同时完成某一功能的能力，通常也用QPS(query per second)来衡量。上述三个性能指标往往会相互制约，追求高吞吐的系统，往往很难做到低延迟；系统平均响应时间较长时，也很难提高QPS。

2、可用性：系统的可用性(availability)指系统在面对各种异常时可以正确提供服务的能力。

系统的可用性可以用系统停服务的时间与正常服务的时间的比例来衡量，也可以用某功能的失败次数与成功次数的比例来衡量。可用性是分布式的重要指标，衡量了系统的鲁棒性，是系统容错能力的体现。

3、可扩展性：系统的可扩展性(scalability)指分布式系统通过扩展集群机器规模提高系统性能（吞吐、延迟、并发）、存储容量、计算能力的特性。

好的分布式系统总在追求“线性扩展性”，也就是使得系统的某一指标可以随着集群中的机器数量线性增长。

4、一致性：分布式系统为了提高可用性，总是不可避免的使用副本的机制，从而引发副本一致性的问题。越是强的一致的性模型，对于用户使用来说使用起来越简单。