第25個冬天

時間、時脈與事件排序 分散式系統中時間的重要性-歷史重大事件 2012 年 6 月 30 日至 7 月 1 日（英國時間），全球許多線上服務和系統曾同時崩潰 (crashed simultaneously)，伺服器鎖定並停止回應。航空公司數小時無法處理預訂或登機手續。 時間測量的應用 (Clocks and time in distributed systems) ► Schedulers, timeouts, failure detectors, retry timers ► 效能量測、統計、效能剖析 Performance measurements, statistics, profiling ► Log files & databases: record when an eventoccurred ► Data with time-limited validity (e.g. cache entries) ► 跨多個節點判定事件的先後順序 Determining order of events across several nodes 時脈的區分，兩種時脈： • 實體時脈 (physical clocks)：計算經過的秒數 (count number of seconds elapsed)。 • 邏輯時脈 (logical clocks)：計算事件數，例如發送的訊息數。(count events, e.g. messages sent) 注意：數位電子產品中的時脈（振盪器 (oscillator)） 並不等同於分散式系統中的時脈(時間戳記的來源 (source of timestamps)) 1.石英時脈 (Quartz clocks) ->日常使用時鐘(手機、手錶、掛鐘、數位顯示器內建) 基於石英(二氧化矽)晶體經雷射修剪 (laser-trimmed)，以特定頻率機械共振 (mechanically resonate) 利用壓電效應 (Piezoelectric effect) : 一塊石英若用槌子敲打或稍微彎曲，會發出微小電脈衝。若施加一些電流，也類似讓其被彎曲或敲打般。 振盪器電路 (Oscillator circuit) 在共振頻率 (resonant frequency) 產生訊號，計算循環次數來測量經過時間。 就好比如手錶的心臟會跳...

Logical vs. physical clocks Physical clock: count number of seconds elapsed Logical clock: count number of events occurred , 沒有與Physical time有直接關係 被設計用來捕抓因果關係，常用到的是採用 Lamport clocks 跟Vector clocks 做個課堂筆記紀錄，因為坐在教室後面會照到前面同學後腦杓。歹勢.... 分散式系統中的 Lamport Clock 與 Vector Clock Lamport Clock（Lamport 時鐘） 用途： 用來在分散式系統中決定事件（Event）的先後順序，避免物理時鐘不同步所造成的混亂。 結構與運作： 每個節點都維護一個整數計數器（Lamport Clock）。 當本地有事件發生時，計數器加一。 發送訊息時，附加目前的 Lamport Clock 值。 接收訊息時，將本地計數器設為收到時鐘值與本地時鐘的最大值後再加一。 Vector Clock（向量時鐘） 用途： 用來追蹤每個節點彼此之間的事件先後關係，比 Lamport Clock 更進一步，可以判斷事件是否真正平行（concurrent）。 結構與運作： 每個節點都維護一個長度為 N（節點數）的向量，每個元素分別表示此節點對自己和其他節點事件次數的看法。 本地事件發生時，將自己對應的一格加一。 發送訊息時，附上自己的 Vector Clock（整個向量）。 接收訊息時，將收到的 Vector Clock 與本地 Vector Clock 逐格比較，大者為新值，再把自己格加一。 總結 Lamport clock 只能粗略判斷時間順序（數字比大小），但無法區分平行事件或真實先後。 Vector clock 若 v1 < v2（全小於），就可以明確判定 v1 happens-before v2；若無法比較，就是平行事件。 第10題.一起修課的班代幫忙上台作答-Lamport Clock 給出四個節點 (A、B、C、D) 之間的訊息交換（m1 ~ m9），要求在每個訊息送出或接收事件標記 Lamport 時間戳（timestamp）。 初始值：每個節點的 Lamport Clock 都是 0。 送出訊息：本地 Lamport ...

Chord 演算法 提出單位：麻省理工學院 (MIT)  核心概念：The Chord protocol supports just one operation: given a key, it maps the key onto a node. 採用 雜湊法 (Hashing) 將資料分配到對應的節點 透過這種方式，可以快速定位並搜尋資源所在位置 屬於結構化的P2P查詢 (Structured Peer-to-Peer Lookup) 演算法 用環狀架構 (Ring Topology) 來組織節點 Chord選擇SHA-1作為雜湊函數，SHA-1會產生一個2^160 的空間 每項為一個16位元組(160bit)的大整數。 特色 效能表現：查詢資源時，節點在空間與時間複雜度上皆為 O(log N) 具有完全分散式、負載平衡、可用性及可擴展性好、命名方式靈活等特點。 分散式雜湊表(Distributed Hashing Table, DHT) 拓樸建立方式 每個新加入的節點，會將其 IP 位址 經由 雜湊函數 (Hashing function) 轉換為一個 節點代碼 (Node ID)，這些節點代碼會映射到一個 邏輯代碼環 (Identifier Circle) 上。 透過此環狀結構，節點之間能夠進行高效率的查詢與資源定位。 缺點與面臨的挑戰 當鄰近節點發生變動時，需要進行大量通訊來更新與維護鄰近節點資訊。 在 Grid Computing 環境中，節點變動頻繁，這會造成額外的網路負擔。 Ref: Distributed Hash Tables https://courses.cs.washington.edu/courses/cse550/17au/notes/lect14.pdf https://www.cs.princeton.edu/courses/archive/fall22/cos418/docs/L9-dht-chord.pdf Distributed Hash Tables:An Overview http://www.cs.cmu.edu/~ashu/talks/DHT.pdf Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications https...

https://physics.stackexchange.com/questions/402591/quantum-solution-to-the-two-army-problem 兩軍問題(Two Generals' Problem) https://www.youtube.com/watch?v=IP-rGJKSZ3s 兩支軍隊由不同將軍領導，準備進攻一座堅固的城市。軍隊在城市附近的兩個山谷紮營。由於有另一個山谷將兩山隔開，兩名將軍只能透過派信使穿越山谷通信，但這山谷由城市護衛佔領，有可能俘虜途徑山谷傳遞消息的任何信使。 雖然兩軍已約定同時進攻，但尚未約定進攻時間。要順利攻擊，兩軍必須同時進攻。如果同一時間只有一支軍隊進攻就會戰敗，因此兩名將軍須約定攻擊時間，並確保對手知道自己同意了進攻計畫。 拜占庭將軍問題(The Byzantine generals problem) 由矽谷科學家Robert Shostak於1978年提出的情境難題。 古代某個大城市「拜占庭」正經歷一場戰爭，四位將軍散落在城內各處，必須在短時間內決定進攻還是撤退。條件在於，不論進攻或撤退，都必須四位將軍一致同意，才能保證最後勝利。 四位將軍決定各自寫信予其他三人，告知相關決定。當每位將軍都寄出信息，又同時收到其他三名將軍的來信後，就會知道決定是否一致，到底是進攻還是撤退。 https://www.youtube.com/watch?v=-D8aXZvzzww https://www.youtube.com/watch?v=gJqmOf4mFEU 背後探討的延伸問題 如何防止其中一位將軍叛變？ 又可能其中一位將軍已被暗殺，寄信的其實是間諜？ 此外，寄出信件後也可能被敵方截取並篡改扭曲事實的內容，從而阻止四位將軍達成共識？ 拜占庭容錯 第一種解套方式.Oral Messages 安排一個Leader發送進攻/撤退信號給另外三位將軍 情境1.三位將軍中剛好有一個判將，試圖分別給另外兩位將軍不同錯誤訊息。 然而引入了指揮官，因此將軍A、B各自所收到的進攻比撤退比例均為2:1，兩人皆發起進攻。 進攻就成功。 情境2.引入的指揮官是叛徒，其中一位傳入進攻訊息。 然而三位將軍都相互傳遞沒被竄改過的指令訊息，因此三人收到的撤退比進攻比例都是2:1。 撤退就成功。 第二種解套方式.消息簽名Sign...

軟體架構 (Software architectures) : 說明各種軟體元件是如何組織的，以及它們應該如何互動。 分散式系統中軟體架構目標 ：  透過提供中介層 (middleware layer)，將應用程式與底層平台分離。 系統架構（System Architecture） ： 決定軟體元件、它們之間互動方式，以及它們的部署位置，最終形成一具體的軟體架構實例。 Architectural styles (replaceable) components with well-defined interfaces 可替換的元件之間透過明確定義的介面彼此互動 the way that components are connected to each other 元件之間的連接方式 the data exchanged between components 元件間交換的資料 how these components and connectors are jointly configured into a system. 系統的整體配置，元件與 連接器 如何組合成一個完整的系統。 連接器 (Connector): 是一種機制，用來調節元件之間的通訊 (communication)、協調 (coordination)、合作 (cooperation)。 例如:用於遠端程序呼叫(RPC)、訊息傳遞(messaging)或資料串流(streaming)的機制。 Layered architecture Pure layered org : Only downcalls to the next lower layer are made. mixed layered org : take layer n-1. There’s an app called A. this will invoke an OS library that’s available in layer n-3. AS WELL as n-3, A will call layer n-2,wihich holds a maths library . maths library itself relies on OS library in layer n-3! So n-2 has to call n-...

Three types of distributed systems High performance distributed computing systems(高效能分散式計算系統) Ex:Parallel computing Distributed information systems(分散式資訊系統) Distributed systems for pervasive computing(普及運算的分散式系統) Parallel computing Multiprocessor（多處理器系統） 在同一台電腦中，安裝多個處理器（CPU），共享同一個記憶體與 I/O 系統。 Multicore（多核心處理器） 屬於「Private memory架構」，單一處理器晶片內含多個運算核心，每個核心能獨立執行指令。 Multicomputer（多電腦系統） 屬於「分散式記憶體架構」，多台獨立電腦（節點）透過網路連接，協同完成任務。 Grid Computing（網格運算）架構 為了促進協作，運算通常使用虛擬組織(virtual organizations)。可理解為是一組使用者ID的集合，用來進行資源分配的授權。 特徵 異質性（Heterogeneous）：節點來自不同硬體、軟體平台。 跨組織（Dispersed across several organizations）：資源分布於多個管理領域。 廣域網路（Wide-area network）：容易跨越 WAN 進行協作。 Grid Computing 的4層架構各自組成(由下Laryer1至上Layer4) L1.Fabric:Provides interfaces to local resources 提供本地資源的介面 L2.Connectivity:Communication/transaction protocols 通訊與交易協定 L2.Resource: Manages a single resource 管理單一資源 L3.Collective:Handles access to multiple resources or protocols 提供資源發現(discovery)、排程(scheduling)、複製(replication)等功能 L4.Application: Contains...

就Policies(政策) 或 Mechanisms(技術機制) 各自實施作法比較 就Policies(政策)  我們需要對客戶端快取(client-cached)資料維持何種一致性層級？(What level of consistency) 我們允許下載的程式碼執行哪些操作？(Which operations do we allow downloaded code) 在面對不同頻寬時，我們會調整哪些服務品質（QoS）需求？(Which QoS requirements) 我們要求通訊具備何種等級的保密性？(What level of secrecy) 就Mechanisms(技術機制) Allow (dynamic) setting of caching policies 允許（動態）設定快取政策 Support different levels of trust for mobile code Provide adjustable Quality of Service (QoS) parameters per data stream 針對每個資料流提供可調整的服務品質（QoS）參數 Offer different encryption algorithms 策略與機制越嚴格的話，我們就越需要確保適當的機制，也因此會進而導致管理上與配置上的參數會更複雜。硬編碼(Hard coding)策略通常以降低靈活性的代價來簡化管理並降低複雜性。 Scale in distributed systems (怎麼定義系統具有可擴展性?) 至少有三個面向的可擴展性需要考慮： 使用者數量與／或程序數量（Size scalability） 系統能否隨著使用者或程序數量的增加而持續有效運作。 節點之間的最大距離（Geographical scalability） 系統能否在節點分布於更廣泛的地理範圍時，仍維持合理的效能與一致性。 管理領域的數量（Administrative scalability） 系統能否跨越多個獨立的管理領域（如不同組織或機構）而仍能協同運作。 需要明確說明系統在 規模、地理分布、管理領域 三個層面上如何應對挑戰。 絕大部分系統僅在「規模可擴展性（size scalability）」上有所考量，也就是隨著使用者或程序數量的增加，系統能否持續運作。...

Distributed System A distributed system is a collection of autonomous (自主性) computing elements that appears to its users as a single coherent system . Distributed Systems: Principles and Paradigms 一書中的定義 A distributed system is a collection of independent computers that appears to its users as a single coherent system. 由多個彼此獨立運作的節點（可能是硬體裝置或軟體程序）所組成的整體。這些節點透過協作來對外呈現為一個單一、一致的系統。 自主節點的集合且彼此要能相互協作才能組成分散式系統，讓User 用起來 或其他應用程式存取、就像是單體。 補充: 自主運算元素（Autonomous computing elements），也稱為節點（nodes），可以是硬體裝置或軟體程序。 單一一致的系統(Single coherent system)：使用者或應用程式將其視為一個整體的單一系統。因此，節點之間必須進行協作；若缺乏協作，則無法構成分散式系統。 分散式系統中常見問題(Collection of autonomous nodes) Problem1.同步與協調問題(synchronization and coordination problems) 由於每個節點皆為自主運作，因此各自維持獨立的時間觀(own notion of time)，系統中並不存在統一的全域時鐘(global clock)。這種特性引發了分散式系統中最根本的同步與協調問題。 Problem2.如何管理群組成員資格、如何確認你確實正在與一位已授權的（非）成員進行通訊？ 開放式群組（Open group）：任何人都可以加入並向其他人傳送訊息。 封閉式群組（Closed group）：只有群組成員之間才能互相通訊，並且需要透過特定的加入與退出流程。 覆疊網路（Overlay network） 集合中的每個節點 僅與系統內的其他節點（即其鄰居）進行通訊 。鄰居的集合可能是動態變化的，甚至...