分散運算

**分散式運算**，又叫**分佈式運算**，係電腦科學子領域，專門研究**分散式系統**嘅設計。分散式系統有多部位於唔同電腦－呢啲電腦彼此間有網絡－呢啲電腦會互相通訊，靠呢啲通訊協調彼此嘅行動，用嚟達到某啲共同目的，由用家嘅角度睇望落好似係一部單一嘅電腦噉。

總括嚟講，分散式系統有幾個有用嘅特徵：
#**共用資源**：例如 5 部電腦組成一分散式系統，共用一部打印機，其中一部電腦唔使用打印機嗰陣可以讓俾第部電腦用，更有效率噉使用打印資源；
#**相異**：例如 5 部電腦各有唔同硬件，當中有部嘅顯示卡零舍勁，所以呢部就喺個系統入面專門處理圖像輸出嘅工作；
#**同時**：幾部電腦同一時間各自做自己嘅工作，喺實際應用上，噉做可以減少好多系統工作上嘅延誤（睇埋平行運算）；
#**可縮放**：如果個系統嘅用家數量變多，需要做嘅多數都只係增加電腦嘅數量，而一部單一電腦就算硬件再勁都會有個上限；
#容錯：10 部電腦入面就算有 1 部壞咗，只要有機制教啲電腦點樣重新分配工作，其餘嗰 9 部都可以繼續正常噉運作。

分散式系統嘅呢啲特性喺實用上好有價值。其中一個例子係大型多人網上遊戲（MMOG）嘅伺服器，一隻 MMOG 嘅一個玩家會用佢部電腦－遊戲機或者個人電腦等－行佢個遊戲程式，然後部電腦將個玩家俾嘅訊號（撳咗邊個掣或者俾咗乜指令呀噉）傳去伺服器嗰度，伺服器喺每一個時間點都要接收成千上萬嘅玩家俾嘅輸入，進行運算，計出遊戲世界嘅狀態應該要點樣改變，再將個輸出傳返去玩家嘅電腦嗰度，所以隻遊戲嘅玩家數量愈多，個伺服器要處理嘅數據量就愈大。喺呢個情況下，分散式系統嘅可縮放性特質就好有用：如果遊戲伺服器係一個分散式系統，噉每當玩家數量增加嘅時候，隻遊戲嘅開發者只係需要增加個系統嘅電腦總數量就得。

## 概論

### 定義
:多個獨立節點
定義上，一個分散式系統有多個**節點**（node）：一個分散式系統嘅每個節點可以係一部超級電腦，又可以係一啲細啲簡單啲嘅運算機械，節點之間喺空間上可以相距好遠，而每個節點唔一定會知嗮成個系統嘅狀態；重點係每一個節點都有能力獨立於第啲節點做運算；<code>foreach</code> 節點 N_i，個節點有既定嘅輸入（input）同輸出（output）。每一個節點都有獨立嘅記憶體；個系統嘅設計者想要用呢柞節點合作一齊做某啲特定嘅運算，所以將呢啲節點編寫成會彼此之間互傳訊號，一個節點會將自己嘅運算結果傳俾另一個，等後者去做進一步嘅處理。

舉個好簡單嘅例子說明，一個設計師可能想要個系統曉幫一個伺服器做日誌，記住個伺服器做過啲乜，一個簡單嘅做法係整一個兩個節點嘅系統，第一個節點 N_1 係個伺服器，第二個節點 N_2 係個日誌紀錄器，設計師做好程式編寫嘅工作，教 N_1 做親乜都傳個訊號去 N_2 嗰度（傳嘅訊號），個訊號帶有「做咗啲乜」同「何年何月何日幾點幾分幾秒做」等嘅訊息，例：
:`task 00248 date 01Feb2020 time 0548pm` 表示
:「喺 2020 年 2 月 1 號下晝 5 點 48 分做咗工作 248」，
然後 N_2 內部有個程式，令 N_2 將 N_1 傳嗰啲訊號冚唪唥記低（「記低」就係 N_2 所做嘅進一步處理）－形成一個簡單嘅雙節點系統。

:望落單一
另一方面，有唔少分散式系統嘅設計師認為，分散式系統由用家嘅角度睇要似一個單一嘅系統。呢一點就噉睇落好似好簡單，但查實可以好撈絞：首先，一個分散式系統有陣時可能會有其中一部機出現故障，於是個系統由嗰部機負責嘅工序就會撠咗喺度唔郁，同時系統第啲部份負責嘅工序會繼續行，打破個系統嘅運行以及「成個系統係一體」嘅觀感。「系統嘅一部份壞咗」係所有複雜系統都要面對嘅問題，但喺分散式系統當中，呢種情況零舍難以掩飾，例如美國電腦科學家萊斯利·藍波特係噉描述分散式系統嘅：

### 中介軟體

中介軟體（middleware）係指提供超越作業系統所提供嘅服務嘅軟件，用途在於確保個分散式系統嘅唔同節點之間能夠有效噉通訊同管理數據。中介軟體邏輯上一般會置喺每部個別電腦嘅作業系統之上，由個系統嘅唔同節點嗰度攞輸入，並且做「由一個節點接收訊號，再將個訊號翻譯俾第個節點知」等嘅工作：簡單嘅例子可以想像一個分散式系統，個中介軟體會由各個節點攞輸入，將輸入變成目標節點睇得明嘅程式語言；再先進啲嘅中介軟體仲會有「俾一個節點執行第個節點嘅子程序」同「確保幾個一開始唔係設計嚟做一個系統嘅應用程式順利噉一齊行」等嘅功能。

## 對比平行運算

分散式運算同平行運算好有關係。平行運算喺最廣義上係指有多個計算過程喺同一時間執行（t_i 當做個系統入面第 i 個過程嘅發生時間，個系統入面有多個過程 t_1 = t_2 = t_3...）。分散式運算同平行運算有相當嘅重疊：當個系統有好多個節點（N_1, N_2, N_3...）嗰時，理論上可以喺一個節點做完計算先到下個節點做；不過喺實際應用上，比較慳時間資源嘅做法係俾至少其中一啲節點同時做計算－分散式運算多數時間都係喺度做平行運算嘅。一般認為，分散式運算同平行運算兩者最大嘅差別在於記憶體嘅分散性：
*喺一般嘅平行運算當中，所有處理器都能夠使用同一柞記憶體，允許處理器之間直接分享訊息（睇附圖嘅 (c)）；
*喺分散式運算當中，每個處理器（節點 N_i）都有獨立、第啲處理器唔能夠直接使用嘅記憶體，只可以透過處理器之間嘅訊號傳遞嚟分享訊息。

想像以下呢幾個過程嘅日誌（`Ty` 代表件事喺時間點 `y` 發生）：

  **P1**
    **T1**：Read input a from memory
    **T1**：Read input b from memory
    **T2**：Compute function_01 using a as input
    **T2**：Compute function_02 using b as input

  **P2**
    **T1**：Node 1 reads input a from Node 1's memory
    **T2**：Node 1 reads input b from Node 1's memory
    **T3**：Node 1 computes function_01 using a as input
    **T4**：Node 1 sends b to Node 2
    **T5**：Node 2 reads function_02 using b as input

`P1` 反映咗一個平行運算，`function_01` 同 `function_02` 呢兩個運算過程可以直接使用同一柞記憶；而 `P2` 反映咗一個分散式運算，`Node 2` 呢個節點唔可以直接用 `Node 1` 呢個節點嘅記憶，而係要 `Node 1` 將件記憶用訊號傳俾佢先可以用。喺某啲情況下，平行運算可以搞到個系統出一啲齋用非平行分散式運算唔會出嘅錯。

## 睇埋
*分散式演算法
*平行運算
*雲端運算
*共識機制
*分散式阻斷服務攻擊

## 文獻

*Arora, Sanjeev; Barak, Boaz (2009), *Computational Complexity – A Modern Approach*, Cambridge, ISBN 978-0-521-42426-4.
*Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), *Introduction to Reliable and Secure Distributed Programming* (2. ed.), Springer, ISBN 978-3-642-15259-7
*Ghosh, Sukumar (2007), *Distributed Systems – An Algorithmic Approach*, Chapman & Hall/CRC, ISBN 978-1-58488-564-1.
*Lynch, Nancy A. (1996), *Distributed Algorithms*, Morgan Kaufmann, ISBN 978-1-55860-348-6.
*Herlihy, Maurice P.; Shavit, Nir N. (2008), *The Art of Multiprocessor Programming*, Morgan Kaufmann, ISBN 978-0-12-370591-4.
*Peleg, David (2000), *Distributed Computing: A Locality-Sensitive Approach*, SIAM, ISBN 978-0-89871-464-7,

## 引咗

## 拎

* Distributed Computing，講分散式運算嘅學術期刊。
* Journal of Parallel and Distributed Computing，又一本講分散式運算嘅期刊。