[閱讀筆記] Algorithms to Live By - 網路 (Networking)

 網路 (Networking) — 我們如何互通聲息

1. 人類互通訊息的基礎是通訊協定 (protocol)，也就是程序和預期的共通慣例，例如，握手、打招呼和禮儀、禮貌、以及各種社會規範，機器間的聯繫也不例外。從電報到簡訊，通訊科技雖然提供人與人之間溝通的新管道，但人與人之間仍有溝通障礙。Internet 問世後，電腦不僅是溝通管道，也是負責交談的聯絡點，因此它們必須負責解決本身的溝通問題。機器間的這類問題 (以及解決方案)，跟人與人之間的問題相仿，很快變成我們借鏡的對象。

2. 拜占庭將軍 (Byzantine Generals Problem) 問題

問題描述

一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向，他們只能通過信使互相聯絡。在投票過程中每位將軍都將自己投票給進攻還是撤退的資訊通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的資訊就可以知道共同的投票結果而決定行動策略。

解決方案

Lamport 用數學證明，叛徒數必須少於總數的1/3，才能達成共識。 各節點（將軍）送訊給所有節點（將軍），各節點（將軍）根據收到的所有消息決策，如何避免惡意節點（叛徒）影響共識的達成？在過程中，若節點故意拒絕合作（惡意節點）或根本沒有說任何事情（錯誤節點），就是叛徒。在比特幣的區塊鏈網路設計中 ， 中本聰藉由密碼學與工作量證明機制 （Proof of Work，PoW）等方法來制約這些叛徒。透過 PoW，節點必須付出大量的工作量（算力）去證明自己的忠誠，之後才能打包交易，送訊給其他節點。最長鏈機制則是各節點都沿著已知的最長鏈進行。所以即使惡意節點試圖破壞，也會付出很大的代價（付出超過整體系統一半的算力）， 只要每個節點都足夠理性、想讓自己利益最大化的情況下 ，工作量證明機制 PoW 的確有效抑制了叛徒作惡的動機，進而解決了拜占庭問題。。(Ref: https://reurl.cc/0Dd5Vx, https://reurl.cc/OXrl2D )

3. 工作量證明 PoW (Proof of Work)：(Ref: https://reurl.cc/e9yqoW, https://reurl.cc/nnvkMd )

PoW (Proof of Work, 工作量證明) 說明

網路上的節點可以簡單地透過工作量證明，快速驗證彼此是否擁有記帳權。就像是我們求學時期，大學四年熬夜苦讀就是為了獲得那張畢業證書，求職時，面試官透過那張畢業證書，快速驗證你大學的成果。畢業證書就是你的 PoW。

以比特幣為例介紹 PoW

每 10~15 分鐘比特幣網路上全體礦工會互相競爭，運用大量的運算能力去解一道複雜的數學題的答案，這個答案是一個隨機數，可以想像題目大概長這樣：Hash｛（前一個區塊的 Hash 值）,（當前區塊的交易資訊）,（隨機數）｝＝當前區塊的 Hash 值。 礦工必須找出一串數字，代入上述公式，讓當前區塊的 Hash 值開頭為 18 個 0 ，例如：0000000000000000001583447dd74c13c09280a9218827244089adadaba8c8c9 解答的過程沒有軌跡可循，礦工只能不斷代入隨機數，透過暴力法找出答案。

挖礦難度

最先解開的人就能獲得下一個區塊的記帳權並獲得比特幣作為獎勵。比特幣固定 10~15 分鐘出塊一次，但是如果節點越來越多、全網算力增加，會縮短算出答案的時間。因此，比特幣協議每 2016 個區塊會調整一次挖礦難度，大約兩個禮拜調整一次。挖礦難度提高時，就必須找出有更多個 0 的當前區塊 Hash 值，例如從原先的 18 個 0 增加到 19 個 0，難度降低時則相反。 挖礦的過程其實像是擲一顆 20 面的骰子，誰先骰到 < 2 的數字誰就能獲得計帳權，換句話說，礦機的硬體運算能力再強大，也只能提高獲得計帳權的機率（骰骰子手速比較快），算力差的礦工不代表沒有機會。

比特幣經濟與獎勵

中本聰所開發的比特幣為了避免貨幣發行太多或太快，有設計出一套抑制通貨膨脹的機制並最終只會發行 2,100 萬個比特幣。為鼓勵節點幫忙驗證營運，設計了挖掘新區塊的獎勵，區塊獎勵從 2009 年開始每個區塊可獲得 50 個比特幣的獎勵，但此一獎勵區塊回報每產出 21 萬個區塊減半一次，即每 4 年減半，2013 年到 2016 年 6 月則是 25 個比特幣，2016 年 7 月 9 日區塊獎勵再度折半到 12.5 個比特幣，估計到 2021 年時會再度折半到 6.25 個，在 2022 年中就會挖出超過 90％，因為比特幣最小單位是 0.00000001，所以 2140 年之後區塊獎勵就會小於最小單位，即不會再生成比特幣產生。

優缺點

優點 容易實現，節點可自由進入，去中心化程度高。 破壞系統需要投入極大的成本，安全性極高。 缺點 為了保證去中心化程度，區塊的確認時間難以縮短。 透過礦工的計算能力以及硬體成本確保礦工立意良善，挖礦過程中過多的能源消耗，使得此機制非常不環保。

4. TCP 三向交握 (Three-way Handshake) (Ref: https://reurl.cc/WENprD )

Three-way Handshake 說明

傳輸控制協定 (Transmission Control Protocol, TCP) 不像 UDP， TCP 是一種 連接導向 (connection-oriented) 的通訊協定，三向交握 (Three-way Handshake)， 是其建立虛擬連線 (virtual connection) 的方式。  又稱為 三向式握手、三路交握 …，其實就是 三次訊息的交換。

Three-way Handshake 圖示

5. 網路傳輸並不保證送達，面對不可靠的人或電腦，我們所面臨的問題

不可靠傳輸的問題	說明
中斷多久被視為真的中斷	📞若是電話，中斷幾秒鐘，我們就會擔心是不是斷話了； 📧 若是 e-mail，過了好幾天收件者沒回信，就會擔心對方是否沒收到。 訊息在發送者與收件者間往返時間越長，沒消沒息的時間也要越長才會引人注意。
中斷後如何因應 (間隔多久做 retry)	指數退讓法 (Exponential backoff) 是處理各種網路失敗或不可靠性的預設方法。 Using exponential backoff - Geocasts 當我們的電腦試圖連線一台顯然已停機的網站，就會使用指數退讓法 (Exponential backoff)，起先是一秒鐘後 retry，接著是幾秒鐘後 retry，如此不斷拉長，對 client 或 server 端都有好處，不僅可防止停機的伺服器重新上線時因 HTTP Requests 太多而停擺，也可防止 client 端浪費太多時間白做工，而且此法也不會迫使我們的電腦完全放棄。

6. 指數退讓法 (Exponential backoff) 在網路安全也扮演要角，有人藉著連續輸入密碼試圖 login 失敗時，它會以指數方式延長鎖定時間，防止 hacker 利用「字典式攻擊」入侵帳號，不斷輸入可能的密碼，直到成功為止。

7. TCP 壅塞控制 (congestion control) 的核心，稱為加法遞增乘法遞減演算法 (AIMD, additive-increase/multiplicative-decrease)。在 AIMD 中，一批封包完整接收後，不會讓傳送封包數加倍，而只會 +1，而發生封包遺失時，則會使傳輸率降一半。實質上， AIMD 的策略就是：「多一點、多一點、多一點、阿太多趕快減少、多一點、多一點 …。」它產生的頻寬變化圖形稱為 TCP 鋸齒圖 (TCP sawtooth)，先逐步緩升，穿插幾次陡然下降。保守主義在此非常重要，所有使用者的速度都不能超過網路過載的速度，如此才能維持網路穩定。同樣地，加法遞增有助於穩定整體狀況，防止出現劇烈過載和復原循環。

(Ref: https://reurl.cc/qmnDxR )

8. 許多動物的覓食行為類似 TCP 流量控制與特殊的鋸齒曲線。追逐人類食物碎屑的松鼠與鴿子，每次都會往前走一步，偶爾退後好幾步，然後再往前走一步。

9. TCP 鋸齒圖 (TCP sawtooth) 告訴我們，在無法預料與不斷變化的環境中，要充分運用全部資源，最好與唯一的方法，就是把狀況推出到出現錯誤。最重要是確定錯誤、反應迅速，而且很快就能恢復。在 AIMD 演算法中，沒有中斷的連線會加速到中斷為止，接著減速一半，又立刻加速。在 TCP 中，沒有單向傳輸，一旦沒有持續的回饋，發送者會立刻減緩發送速度。

10. 彼得理論 (Peter Principal) 提到「所有員工通常都會升到無法勝任的職」，套用 AIMD 演算法，假設有間公司的員工不是每年晉升一級，就是降階若干級，如此就不會有人抱怨一直沒獲得升遷，也不會有人憂心長期負擔過重。

11. buffer / queue 的概念：當你與另一位客戶幾乎同時走進一間甜甜圈店，收銀員由於一時忙不過來，於是請你們其中一個人排隊稍後。如此一來，可以確保收銀員不會過勞，請客戶排隊可確保店裡的平均處理量可達最大處理量，這是好事。但這種優秀的資源運用方式，必須付出「延遲代價」。當排隊人數越多，隊伍越長，等待時間就越久；若店家在目前隊伍末端，立個標示牌表示本日 sold out，這對顧客與店家可謂皆大歡喜，店家表示已達本日最大產量，顧客也不用浪費時間排隊，可以去買其他東西。出於策略刻意讓球落地，是在負擔過大時完成工作的重要方法。

12. 當緩衝區已滿，通常會出現 tail drop 現象，代表在此之後到達的封包都會直接拒絕並刪除。隨著科技進步，記憶體價格下跌，處處充滿了大型緩衝區的網路設備，這對基於遺失  (lost-based) 的壅塞控制演算法造成巨大的問題。大型的緩衝區，使封包不易被丟棄，而是在佇列中緩慢地等待，TCP 傳送端 並不知道 壅塞的發生，仍持續成長傳輸速率，使網路產生高延遲、吞吐量下降的惡性循環，這就是惡名昭彰的 — 緩衝區膨脹 (bufferbloat)。(Ref: https://reurl.cc/v5paRL, https://reurl.cc/xgpa7V )

13. 運用「Tail drop 概念」於 e-mail 自動回覆功能

14. 許多公司強調的「高速網際網路」，指的是高頻寬，而非低延遲；網路工程師早該將「低延遲」視為最優先的問題。我們需要更多協和式客機 (Concorde)，而非更大台的波音。例如，對線上遊戲玩家而言，即使 50ms 的延遲，都可能影響到他幹掉別人，還是別人幹掉他。