安徽京準 NTP授時服務器（北斗授時設備）在分布式系統(tǒng)中的重要性

安徽京準 NTP授時服務器（北斗授時設備）在分布式系統(tǒng)中的重要性

安徽京準 NTP授時服務器（北斗授時設備）在分布式系統(tǒng)中的重要性

分布式系統(tǒng)由Tanenbaum定義，“分布式系統(tǒng)是一組獨立的計算機，在”分布式系統(tǒng)?—?原理和范例“中作為用戶的單一，連貫的系統(tǒng)出現(xiàn)”。

區(qū)塊鏈通過構建全球分布式系統(tǒng)，嘗試實現(xiàn)分散的新數(shù)據(jù)存儲和組織結構。

首先，定位到分布式系統(tǒng)的原因主要是可擴展性，位置和可用性。區(qū)塊鏈也不例外。地理可擴展性，形成全球價值存儲網(wǎng)絡/信息保護區(qū)域，包括非集中式結構下的防篡改/零停機時間的可用性。這些未來都是使用分布式系統(tǒng)在block中實現(xiàn)的。

0.目錄

X.區(qū)塊鏈和分布式系統(tǒng)

1.簡介（同步和整體流程概述）

2.時鐘同步

2–1。物理時鐘（時鐘和時鐘偏移）

2–2。 時鐘同步算法（網(wǎng)絡時間協(xié)議（NTP）/伯克利算法）

3.邏輯時鐘

3–1。 Lamport的邏輯時鐘（完全有序的多播）

3–2。 矢量時鐘（因果訂單組播）

4.獨家控制

4–1。 集中算法

4–2。 分散算法

4–3。 分布式算法

5.選舉算法

5–1。 欺負算法

5–2。 環(huán)算法

6.阻止鏈和同步作為分布式系統(tǒng)

6–1。 塊鏈和時鐘同步（塊鏈和物理/邏輯時鐘）

6–2。 塊鏈和獨占控制算法（PoW·PoS·BFT中的獨占控制算法）

6–3。 塊鏈和領導者選舉算法（PoW·PoS·BFT中的領導者選擇算法）

1.簡介（同步和整體流程概述）

與集中式系統(tǒng)不同，在分布式系統(tǒng)中就時間達成一致并不容易。

在前一種情況下，可以基于全局共享時鐘確定絕對順序關系，但是在后一種情況下，由于存在時鐘值錯誤和對應時間，因此難以共享絕對時間。

但是，絕對時間的順序并不是絕對必要的，如果相對順序是固定的，通常就足夠了。

在本文中，將按以下順序解釋節(jié)點之間的同步。

時鐘同步是如何發(fā)生的？

使用邏輯時鐘和矢量時鐘的相對排序方法

關于分布式系統(tǒng)一致性的排除控制算法

關于分布式系統(tǒng)中的領導選舉算法

2.時鐘同步

2–1.物理時鐘

時鐘和時鐘歪斜

大多數(shù)計算機都有保持時間的電路，這種設備稱為“時鐘”。這是基于頻率的振動，該振動可以通過晶體類型，切割方法和向精確加工的石英增加張力時的壓力大小明確定義。

雖然這個頻率相當穩(wěn)定，但不能保證不同計算機的所有晶體都能以完全相同的頻率運行。由此引起的同步時間的差異稱為時鐘偏差。

在這種情況下，特別是在實時系統(tǒng)中，如何使多個時鐘與現(xiàn)實時鐘同步以及如何同步時鐘是一個問題。

現(xiàn)實世界中的時間最初基于平均太陽秒，但現(xiàn)在銫133過渡9，192，631，770次的時間定義為1秒，并且定義了國際原子時間和通用協(xié)調時間（UTC）。為了向需要準確時間的人提供UTC，使用WWV并且時間以±10毫秒的精度提供。

2–2.時鐘同步算法

但是，大多數(shù)機器沒有WWV接收器。因此，每臺機器都需要時間跟蹤和管理算法，以便所有機器都可以同步時間。

順便提及，用于確定是否需要重新同步的錯誤，即時鐘偏移，如下測量。

將H定義為每臺機器計數(shù)的晶體振動引起的每秒中斷次數(shù)（刻度數(shù)），并將C表示為該時鐘的值。設Cp（t）表示機器的時鐘值，當UTC時間為t時。

如果將p定義為定義允許的時鐘偏差量的最大漂移率，則假定它在以下范圍內運行。

1-p《= dC/dt《= 1+p

也就是說，在從先前同步開始經(jīng)過At秒之后，兩個時鐘最多分開2pΔt。

當保證在操作執(zhí)行時沒有大于＆的偏差時，必須至少每＆/2p重新同步軟件。

網(wǎng)絡時間協(xié)議（NTP）

在許多協(xié)議中很常見，［Cristian，1989］首先提出的方法是一種與客戶服務器通信的方法。由于時間服務器具有WWV接收器或具有準確的時鐘，因此它可以提供當前時間。在與服務器通信時，重要的是延遲報告消息傳播延遲的時間，但是通過估計延遲，這里可以最小化錯誤。目前，已知NTP能夠在1至50毫秒的范圍內實現(xiàn)精度。

伯克利算法

在諸如NTP的許多算法中，時間服務器是被動的并且僅回答查詢。另一方面，在Berkeley算法中，時間服務器接收每個參與節(jié)點所持有的時間，并且還基于平均值改變其自己的時間。當時間值不必與現(xiàn)實世界有關系時，很容易在同一當前時間達成一致，并且它對此算法有效。

3.邏輯時鐘

到目前為止，雖然我們描述了一種根據(jù)實際時鐘將時鐘與絕對時間同步作為參考的方法，但通常只執(zhí)行相對同步。這里，邏輯時鐘的概念用于確定相對順序。

3–1. Lamport的邏輯時鐘

為了同步邏輯時鐘，Lamport定義了一個名為happen-before的關系。表達式a→b表示“a發(fā)生在b之前”，這意味著事件首先發(fā)生，然后所有進程都同意事件b將發(fā)生。發(fā)生之前?—?可以在以下兩種情況下直接觀察到關系。

如果a和b是同一過程中的事件且a出現(xiàn)在b之前，則a→b為真。

2.如果a是由一個進程發(fā)送的消息的事件，并且b是由另一個進程接收的該消息的事件，那么a→b也是如此。在發(fā)送消息之前無法接收消息，即使消息同時也需要有限的非零時間。

因為發(fā)生前關系處于過渡關系中，如果a→b和b→c，則可以證明a→c。如果事件x，y出現(xiàn)在不交換消息的不同進程中，則x→y和y→x都不為真，并且這些事件被認為是并發(fā)的。 （之前發(fā)生的關系未知。）

利用邏輯時鐘，通過分配所有進程對每個事件a一致的時間C（a）來測量相對時間。如果這些時間值是a→b，則通過向時間添加正值來校正它們，使得C（a）《C（b）。通過分配如下圖所示的時間值，可以掌握之前發(fā)生的關系。

在Lamport的邏輯時鐘中，如果a→b，則可以證明C（a）《C（b），但如果C（a）《C（b）則a→b不一定成立。換句話說，a→b是C（a）《C（b）的必要條件，并且不是充分條件。 Lamport的邏輯時鐘增加了改進，它是一個矢量時鐘，可以滿足這種必要和充足的條件。

完全有序的多播

有關詳細信息，請參閱“分布式系統(tǒng)一致性”一文中的內容

在許多情況下，有必要在重復的副本之間執(zhí)行完全有序的多播。換句話說，所有消息都需要以相同的順序傳遞給每個收件人。 Lamport的邏輯時鐘可用于在完全分布式系統(tǒng)下實現(xiàn)完全有序的多播。

當進程收到某個消息時，它會根據(jù)時間戳按順序放入本地隊列。收件人向另一個進程多播確認。如果您按照Lamport的算法調整本地時鐘，則所有進程實際上都具有本地隊列的相同副本。只有當消息位于隊列的頭部并且被所有其他進程確認時，才有一個進程可以將隊列中的消息傳遞給正在運行的應用程序，因此，所有消息都以相同的順序傳遞到各處。換句話說，已經(jīng)建立了完全有序的多播。

3–2.矢量時鐘

使用矢量時鐘，可以掌握Lamport邏輯時鐘無法掌握的因果關系。 假設事件a的向量時鐘是VC（a），則執(zhí)行以下步驟，使得a→b成為VC（a）《VC（b）的必要和充分條件。

在通過網(wǎng)絡發(fā)送消息之前，節(jié)點Pi向矢量時鐘VCi［i］添加1，或者操作一些內部事件。

2.如果處理Pi將消息m發(fā)送到Pj，則Pi在執(zhí)行前一步驟之后將m的向量時間戳ts（m）設置為等于VCi。

3.當接收到消息m時，進程Pj執(zhí)行步驟1，將消息分發(fā)給應用程序，然后更新其自己的向量時鐘的每個k，如下所示：VCj［k］←max {VCj［k］，ts（m）［k］}。

因果關系多播

通過使用向量時鐘，可以實現(xiàn)稍微弱于上述完全有序多播的因果有序多播。

通過比較矢量時鐘的值并掌握發(fā)生在之前的關系，對于特定事件x，其他事件可以被分類為過去事件，并發(fā)事件和未來事件。例如，在上圖中，當事件d用作參考點時，過去事件是a，b，c，i，并發(fā)事件是j，l，m，未來事件是f，g，h。

此時，假設因果有序多播是過去事件和因果事件的序列，其中發(fā)生所有因果關系，以便在所有過程中保持一致，但是關于并發(fā)事件的順序是無關緊要的。通過這種方式，與Lamport的邏輯時鐘不同，可以用向量時鐘來掌握因果關系。

4.獨家控制

多個進程之間的并發(fā)操作和協(xié)作操作是分布式系統(tǒng)的基本，但是為了保證對資源的獨占訪問，以便通過多個進程同時訪問相同資源時不處于不一致狀態(tài)時，需要分布式排他算法。

分布式獨占控制算法可以分為以下兩種類型。

基于Token的解決方案

基于權限的方法

在基于Token的方案中，很容易避免StarvaTIon（很長時間內不允許訪問資源）和死鎖（多個進程等待彼此的進展）。一個代表性的例子是Token環(huán)算法。但是，當持有Token的過程異常停止并且Token丟失，有必要只生成一個新Token，這種復雜性是一個嚴重的缺點。

許多其他分散的獨占控制算法采用基于權限的方法，并有許多不同的獲取權限的方法，我們將分別具體解釋。

4–1.集中算法

通過模擬單處理器系統(tǒng)的功能，可以輕松實現(xiàn)分布式系統(tǒng)中獨占控制的單一訪問。在集中式算法中，一個進程被指定為協(xié)調器，并且當進程訪問共享資源時，請求消息被發(fā)送到協(xié)調器以獲得許可。如果其他進程未訪問共享資源，則協(xié)調器返回權限響應，并且在接收到回復之后，所請求的進程執(zhí)行該進程。

很容易看出，該算法保證了對資源的獨占訪問，但它具有單點故障的嚴重缺點。雖然這可能是大型系統(tǒng)中的性能瓶頸，但這種簡單性帶來的優(yōu)勢仍然可以彌補這些缺點。

4–2.分散算法

假設各項都會重復n次。在分散算法中，當進程訪問資源時，需要批準大多數(shù)m》 n / 2。如果獲得大多數(shù)批準，則該過程獲得許可并可以進行處理。

雖然該方案解決了集中式算法的單點故障問題，但是如果有太多的節(jié)點試圖訪問，則存在另一個問題，即沒有節(jié)點可以獲得足夠的投票而無法獲得充分的性能。

4–3.分布式算法

在該算法中，假設系統(tǒng)上所有事件的順序可以定義為完全有序的關系。作為這個基礎，使用了前一章中描述的Lamport的邏輯時鐘，并且假設沒有消息會丟失。

當進程嘗試訪問共享資源時，它會創(chuàng)建一條消息，其中包含資源名稱，自己的進程號和當前邏輯時鐘，并將其發(fā)送給所有其他進程。當接收到該請求消息時，根據(jù)其自身狀態(tài)執(zhí)行以下操作。

1.如果收件人未訪問該資源且未嘗試訪問該資源，則收件人會向發(fā)件人返回“確定”消息。

2.如果收件人已在訪問資源，請不要回復并執(zhí)行排隊請求。

3.如果收件人正在嘗試訪問資源但尚未完成，請將輸入消息中的時間戳與發(fā)送給其他進程的消息中的時間戳進行比較，并將較低的一個作為獲勝者。如果收到的消息具有小的時間戳，則收件人返回OK消息。如果自己的消息具有較小的時間戳，則接收方將不會將輸入消息排隊。

顯然，如果它不像process1或2那樣沖突，這個算法就能正常工作。即使在沖突的情況下，也只建立了唯一一個進程可以訪問的條件。

與集中式算法一樣，該算法可以保證獨占控制，不會出現(xiàn)死鎖或饑餓。 此外，沒有單點故障。 盡管如此，單點故障被故障n位置特征所取代。 它可以通過回復權限或拒絕權限并引入超時來解決，但也會出現(xiàn)其他問題，例如需要多播通信原語。 不幸的是，目前尚未設計出超越集中式算法的分布式算法，并且仍在研究中。

當比較各個算法時，變?yōu)槿缦隆?/p>

5.領導者選舉算法

許多分布式算法需要一個特殊的過程，它具有領導者作為協(xié)調者或發(fā)起者的角色。哪個過程是領導者，唯一過程是否可以成為領導者是一個重要問題，研究人員在過去幾十年中一直在努力。

5–1.欺負算法

當協(xié)調員失敗并且任何進程P注意到該情況時，P根據(jù)以下過程激活選舉。

· P向所有具有比其自身更高數(shù)值的進程發(fā)送ELECTION消息。

·如果沒有人回復，P將贏得選舉并成為協(xié)調員。

·如果來自具有高于P的數(shù)值的過程的答案，則將替換它。 P的工作結束了。

使用該算法，可以唯一地確定協(xié)調器。但是，該算法需要大量的消息和數(shù)據(jù)流量，可以說是冗余的。作為替代方案，存在環(huán)算法。

5–2.環(huán)算法

與一般環(huán)算法不同，該算法不使用Token。發(fā)現(xiàn)協(xié)調器不工作的任何進程構造一個包含其自己的進程號的ELECTION消息，并將該消息發(fā)送給其后繼者（環(huán)網(wǎng)中的下一個節(jié)點）。如果繼任者失敗，請?zhí)^。如果沒有比您更高的數(shù)值的節(jié)點，您的消息將仍然返回給您自己的進程號，因此它將被指定為協(xié)調員。

在該算法中，執(zhí)行具有減少數(shù)量的消息的領導者選舉，但是還可以通過將消息的目的地設置到兩個相鄰節(jié)點來實現(xiàn)具有較少量數(shù)據(jù)流量的算法。

6.阻止鏈和同步作為分布式系統(tǒng)

因此，在作為分布式系統(tǒng)之一的塊鏈中，進程之間的同步如何發(fā)生？

6–1.區(qū)塊鏈和時鐘同步

塊鏈和邏輯時鐘

首先，考慮是否可以使用區(qū)塊鏈中的物理時鐘來掌握絕對時間關系。如第2章所述，參與網(wǎng)絡的每個節(jié)點并不總是保持正確的物理時鐘，并且應該存在時鐘偏差。由于比特幣區(qū)塊鏈的平均生成時間是10分鐘，因此認為即使一定程度的大時鐘偏差也是可接受的。然而，當節(jié)點散布在世界各地時難以同步各個物理時鐘，并且還可能存在偽裝時鐘的節(jié)點。通過引入網(wǎng)絡時間協(xié)議（NTP）來重新同步節(jié)點之間的正確時間是一項困難的技術。

區(qū)塊鏈和邏輯時鐘

因此，準備邏輯時鐘而不是物理時鐘是切合實際的。實際上，通過在塊中加入時間標記，可以制備出與Lamport邏輯時鐘非常相似的機制。

如［比特幣：點對點電子現(xiàn)金系統(tǒng)Satoshi Nakamoto］中所述，對作為礦工的區(qū)塊執(zhí)行寫操作的每個節(jié)點本身具有作為時間戳服務器的角色。每個時間戳通過在其哈希中包含前一個時間戳來形成鏈。但是，無法保證這些節(jié)點保持正確的物理時鐘。時間戳的數(shù)值，即每個事務的順序和時間相對模糊。

由于時鐘的這種模糊性，有可能會進行雙重付款。但是，在比特幣區(qū)塊鏈中，只有最長的鏈是合法的，在次要驗證后丟棄不正確的交易。因此，區(qū)塊的順序隨著時間的流逝唯一確定。隨著每個時間戳的增加，前一個時間戳被加強。

總之，在區(qū)塊鏈中的模糊時間戳下，事務的順序一致性是不準確的。然而，利用鏈式連接的簡單機制，每個交易的發(fā)生前關系隨著時間的推移而建立。此外，還有一種激勵結構，以便礦工轉移到良好，交易不一致的順序不會發(fā)生。

可以說，實現(xiàn)類似于Lamport的邏輯時鐘的時鐘同步方法，因為事務之間的相對順序關系，即發(fā)生在之前的關系變得更清楚。

對于大多數(shù)交易，沒有因果關系，因此如果您引入向量時鐘并采用因果關系排序的概念，則可以極大地放松訂單關系的約束。然而，在區(qū)塊鏈中，由于結構本身默認共享所有塊的順序關系，所以保持總排序（相對于在一段時間之后的塊）。

6–2.區(qū)塊鏈和獨占控制算法

即使在作為分布式系統(tǒng)的區(qū)塊鏈中，也需要排除控制。在區(qū)塊鏈網(wǎng)絡中，每個節(jié)點并行地異步操作。此時，要共享的區(qū)塊鏈本身的信息不應該不一致。

PoW·PoS中的獨占控制算法

如第4章所述，分布式排他控制算法可分為以下兩種類型。

·基于Token的解決方案

·基于權限的解決方案

PoW和PoS是基于權限的，其中，可以說它是類似于分布式算法的機制。那么，您什么時候獲得訪問資源的權限？是的，就在你找到一個隨機數(shù)時。

在PoW中，只有當找到在哈希值后跟0后跟n為0的隨機數(shù)時，才可以執(zhí)行有效的新塊寫操作。執(zhí)行操作的礦工將其廣播給所有礦工并分享。

通常，當節(jié)點找到一個nonce并創(chuàng)建一個比他自己更早的塊時，minor會同步該信息并移動以搜索下一個nonce值。這是因為如果您使用最長鏈被認為合法的規(guī)則搜索下一個nonce值，它們可以獲得更多利潤。盡管PoS優(yōu)先為具有較大硬幣持有量的人提供資源訪問，但基本排除控制算法結構也類似于分布式算法。

但是，嚴格來說，不執(zhí)行排除控制。這是為了在公共時間內同步并形成共識10分鐘，直到下一個區(qū)塊為止。當兩個或更多個節(jié)點同時找到隨機數(shù)值時，寫入操作以非獨占狀態(tài)執(zhí)行。此時，由于只有最長的鏈被認為是合法的，因此區(qū)塊鏈網(wǎng)絡中的信息與時間的流逝保持一致。叉子發(fā)生的一個問題是因為沒有執(zhí)行嚴格的排他控制而且沒有確認最終結果。

BFT類型的獨占控制算法

另一方面，通過BFT類型，基于許可的分散算法執(zhí)行排他控制。該算法解決了分叉和終結問題，這是PoW中與分布式算法類似的問題。

在BFT類型中，只有一個名為Proposer，Orderer等的節(jié)點有權生成新區(qū)塊。創(chuàng)建區(qū)塊時，您可以從所有參與節(jié)點收集投票，獲得超過2/3的同意，您才有權創(chuàng)建新塊。此時，有必要同意超過2/3而不是多數(shù)的原因是處理拜占庭故障，有關此問題的詳細信息在“分布式系統(tǒng)中的容錯”一文中有所描述。

在BFT類型算法中，與PoW等不同，只有一個節(jié)點可以獲得對區(qū)塊鏈的獨占訪問權限，因此不會立即確定fork和finality。但是，任何人都可以作為礦工參與網(wǎng)絡的財產往往會丟失。

6–3.區(qū)塊鏈和領導者選擇算法

PoW，PoS和領導者選擇算法

區(qū)塊鏈上的領導者選擇算法類似于獨占控制算法的機制。在比特幣中，用于選舉領導者的算法，即，新創(chuàng)建塊的節(jié)點是PoW。

PoW允許添加一個塊作為一個好的領導者，為比特幣網(wǎng)絡提供有計算復雜性和發(fā)現(xiàn)nonce的節(jié)點。每個成為領導者的礦工都會嘗試為比特幣網(wǎng)絡做出貢獻，因為更容易早期同步到首先發(fā)現(xiàn)現(xiàn)時的節(jié)點并開始搜索下一個塊的現(xiàn)時值更有可能獲得獎勵。盡管存在鏈條完全由硬叉分支的問題，但是通過基于博弈論準備非常簡單的激勵結構，在塊鏈網(wǎng)絡中實現(xiàn)作為分布式系統(tǒng)的同步。

在以太坊的情況下，由于塊生成的時間很短，因此傾向于發(fā)生更多的分叉。關于這一點，通過采用unkle塊的概念，我們實現(xiàn)了一種結構，即使產生不合法的鏈條也會給予一定的獎勵。

將來引入未來的PoS允許優(yōu)先生成具有大硬幣保持量的節(jié)點的塊作為引導者。這是一種解決/改善PoW中必要電量變得巨大且易受51％攻擊的問題的算法。這是一種基于博弈論的選舉算法，如果一個節(jié)點持有大量硬幣，就不會采取破壞網(wǎng)絡等惡意行為。

BFT和領導者選擇算法

BFT類型算法的問題在于如何選擇將投票給塊生成的領導者作為Proposer或Orderer。

在PBFT采取的HyperLedger當中，原為可信賴的機構才會注冊為Orderer。 但這是集中式的領導者選擇方法，與分布式系統(tǒng)存在著明顯的區(qū)別。

在Tendermint協(xié)議當中，領導者以循環(huán)方式被選出，以通過與不同驗證者的輪換交替來提出建議。 此時，領導候選者是基于PoS，并且可以說是可以在分布式系統(tǒng)中實現(xiàn)領導者選擇的算法之一。

審核編輯 黃宇