分布式計算演算法

Ⅰ 分布式計算機系統有什麼特點

分布式計算機系統是由多台計算機通過網路連接形成的計算機系統，其主要特點包括：
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、一致性：分布式系統為了提高可用性，總是不可避免的使用副本的機制，從而引發副本一致性的問題。越是強的一致的性模型，對於用戶使用來說使用起來越簡單。