NTP網路授時,分布式系統時鐘同步重要性-京準電子科技
NTP網路授時,分布式系統時鐘同步重要性-京準電子科技
京準電子科技網址 ahjzsz.com 官微 ahjzsz
分布式系統由Tanenbaum定義，“分布式系統是一組獨立的計算機，在”分布式系統?—?原理和范例“中作為用戶的單一，連貫的系統出現”，
區塊鏈通過構建全球分布式系統，嘗試實作分散的新資料存盤和組織結構，
首先，定位到分布式系統的原因主要是可擴展性，位置和可用性，區塊鏈也不例外，地理可擴展性，形成全球價值存盤網路/資訊保護區域，包括非集中式結構下的防篡改/零停機時間的可用性，這些未來都是使用分布式系統在block中實作的，
0.目錄
X.區塊鏈和分布式系統
1.簡介（同步和整體流程概述）
2.時鐘同步
2–1，物理時鐘（時鐘和時鐘偏移）
2–2， 時鐘同步演算法（網路時間協議（NTP）/伯克利演算法）
3.邏輯時鐘
3–1， Lamport的邏輯時鐘（完全有序的多播）
3–2， 矢量時鐘（因果訂單組播）
4.獨家控制
4–1， 集中演算法
4–2， 分散演算法
4–3， 分布式演算法
5.選舉演算法
5–1， 欺負演算法
5–2， 環演算法
6.阻止鏈和同步作為分布式系統
6–1， 塊鏈和時鐘同步（塊鏈和物理/邏輯時鐘）
6–2， 塊鏈和獨占控制演算法（PoW·PoS·BFT中的獨占控制演算法）
6–3， 塊鏈和領導者選舉演算法（PoW·PoS·BFT中的領導者選擇演算法）
1.簡介（同步和整體流程概述）
與集中式系統不同，在分布式系統中就時間達成一致并不容易，
在前一種情況下，可以基于全域共享時鐘確定絕對順序關系，但是在后一種情況下，由于存在時鐘值錯誤和對應時間，因此難以共享絕對時間，
但是，絕對時間的順序并不是絕對必要的，如果相對順序是固定的，通常就足夠了，
在本文中，將按以下順序解釋節點之間的同步，
時鐘同步是如何發生的？
使用邏輯時鐘和矢量時鐘的相對排序方法
關于分布式系統一致性的排除控制演算法
關于分布式系統中的領導選舉演算法
2.時鐘同步
2–1. 物理時鐘
時鐘和時鐘歪斜
大多數計算機都有保持時間的電路，這種設備稱為“時鐘”，這是基于頻率的振動，該振動可以通過晶體型別，切割方法和向精確加工的石英增加張力時的壓力大小明確定義，
雖然這個頻率相當穩定，但不能保證不同計算機的所有晶體都能以完全相同的頻率運行，由此引起的同步時間的差異稱為時鐘偏差，
在這種情況下，特別是在實時系統中，如何使多個時鐘與現實時鐘同步以及如何同步時鐘是一個問題，
現實世界中的時間最扯訓于平均太陽秒，但現在銫133過渡9，192，631，770次的時間定義為1秒，并且定義了國際原子時間和通用協調時間（UTC），為了向需要準確時間的人提供UTC，使用WWV并且時間以±10毫秒的精度提供，
2–2. 時鐘同步演算法
但是，大多數機器沒有WWV接收器，因此，每臺機器都需要時間跟蹤和管理演算法，以便所有機器都可以同步時間，
順便提及，用于確定是否需要重新同步的錯誤，即時鐘偏移，如下測量，
將H定義為每臺機器計數的晶體振動引起的每秒中斷次數（刻度數），并將C表示為該時鐘的值，設Cp（t）表示機器的時鐘值，當UTC時間為t時，
如果將p定義為定義允許的時鐘偏差量的最大漂移率，則假定它在以下范圍內運行，
1-p 《= dC/dt 《= 1+p
也就是說，在從先前同步開始經過At秒之后，兩個時鐘最多分開2pΔt，
當保證在操作執行時沒有大于＆的偏差時，必須至少每＆/2p重新同步軟體，
網路時間協議（NTP）
在許多協議中很常見，［Cristian，1989］首先提出的方法是一種與客戶服務器通信的方法，由于時間服務器具有WWV接收器或具有準確的時鐘，因此它可以提供當前時間，在與服務器通信時，重要的是延遲報告訊息傳播延遲的時間，但是通過估計延遲，這里可以最小化錯誤，目前，已知NTP能夠在1至50毫秒的范圍內實作精度，
伯克利演算法
在諸如NTP的許多演算法中，時間服務器是被動的并且僅回答查詢，另一方面，在Berkeley演算法中，時間服務器接收每個參與節點所持有的時間，并且還基于平均值改變其自己的時間，當時間值不必與現實世界有關系時，很容易在同一當前時間達成一致，并且它對此演算法有效，
3.邏輯時鐘
到目前為止，雖然我們描述了一種根據實際時鐘將時鐘與絕對時間同步作為參考的方法，但通常只執行相對同步，這里，邏輯時鐘的概念用于確定相對順序，
3–1. Lamport的邏輯時鐘
為了同步邏輯時鐘，Lamport定義了一個名為happen-before的關系，運算式a→b表示“a發生在b之前”，這意味著事件首先發生，然后所有行程都同意事件b將發生，發生之前?—?可以在以下兩種情況下直接觀察到關系，
如果a和b是同一程序中的事件且a出現在b之前，則a→b為真，
2. 如果a是由一個行程發送的訊息的事件，并且b是由另一個行程接收的該訊息的事件，那么a→b也是如此，在發送訊息之前無法接收訊息，即使訊息同時也需要有限的非零時間，
因為發生前關系處于過渡關系中，如果a→b和b→c，則可以證明a→c，如果事件x，y出現在不交換訊息的不同行程中，則x→y和y→x都不為真，并且這些事件被認為是并發的， （之前發生的關系未知，）
利用邏輯時鐘，通過分配所有行程對每個事件a一致的時間C（a）來測量相對時間，如果這些時間值是a→b，則通過向時間添加正值來校正它們，使得C（a）《C（b），通過分配如下圖所示的時間值，可以掌握之前發生的關系，
在Lamport的邏輯時鐘中，如果a→b，則可以證明C（a）《C（b），但如果C（a）《C（b）則a→b不一定成立，換句話說，a→b是C（a）《C（b）的必要條件，并且不是充分條件， Lamport的邏輯時鐘增加了改進，它是一個矢量時鐘，可以滿足這種必要和充足的條件，
完全有序的多播
有關詳細資訊，請參閱“分布式系統一致性”一文中的內容
在許多情況下，有必要在重復的副本之間執行完全有序的多播，換句話說，所有訊息都需要以相同的順序傳遞給每個收件人， Lamport的邏輯時鐘可用于在完全分布式系統下實作完全有序的多播，
當行程收到某個訊息時，它會根據時間戳按順序放入本地佇列，收件人向另一個行程多播確認，如果您按照Lamport的演算法調整本地時鐘，則所有行程實際上都具有本地佇列的相同副本，只有當訊息位于佇列的頭部并且被所有其他行程確認時，才有一個行程可以將佇列中的訊息傳遞給正在運行的應用程式，因此，所有訊息都以相同的順序傳遞到各處，換句話說，已經建立了完全有序的多播，
3–2. 矢量時鐘
使用矢量時鐘，可以掌握Lamport邏輯時鐘無法掌握的因果關系， 假設事件a的向量時鐘是VC（a），則執行以下步驟，使得a→b成為VC（a）《VC（b）的必要和充分條件，
在通過網路發送訊息之前，節點Pi向矢量時鐘VCi ［i］添加1，或者操作一些內部事件，
2. 如果處理Pi將訊息m發送到Pj，則Pi在執行前一步驟之后將m的向量時間戳ts（m）設定為等于VCi，
3. 當接收到訊息m時，行程Pj執行步驟1，將訊息分發給應用程式，然后更新其自己的向量時鐘的每個k，如下所示：VCj ［k］←max {VCj ［k］，ts（m）［k］}，
因果關系多播
通過使用向量時鐘，可以實作稍微弱于上述完全有序多播的因果有序多播，
通過比較矢量時鐘的值并掌握發生在之前的關系，對于特定事件x，其他事件可以被分類為過去事件，并發事件和未來事件，例如，在上圖中，當事件d用作參考點時，過去事件是a，b，c，i，并發事件是j，l，m，未來事件是f，g，h，
此時，假設因果有序多播是過去事件和因果事件的序列，其中發生所有因果關系，以便在所有程序中保持一致，但是關于并發事件的順序是無關緊要的，通過這種方式，與Lamport的邏輯時鐘不同，可以用向量時鐘來掌握因果關系，
4.獨家控制
多個行程之間的并發操作和協作操作是分布式系統的基本，但是為了保證對資源的獨占訪問，以便通過多個行程同時訪問相同資源時不處于不一致狀態時，需要分布式排他演算法，
分布式獨占控制演算法可以分為以下兩種型別，
基于Token的解決方案
基于權限的方法
在基于Token的方案中，很容易避免StarvaTIon（很長時間內不允許訪問資源）和死鎖（多個行程等待彼此的進展），一個代表性的例子是Token環演算法，但是，當持有Token的程序例外停止并且Token丟失，有必要只生成一個新Token，這種復雜性是一個嚴重的缺點，
許多其他分散的獨占控制演算法采用基于權限的方法，并有許多不同的獲取權限的方法，我們將分別具體解釋，
4–1. 集中演算法
通過模擬單處理器系統的功能，可以輕松實作分布式系統中獨占控制的單一訪問，在集中式演算法中，一個行程被指定為協調器，并且當行程訪問共享資源時，請求訊息被發送到協調器以獲得許可，如果其他行程未訪問共享資源，則協調器回傳權限回應，并且在接收到回復之后，所請求的行程執行該行程，
很容易看出，該演算法保證了對資源的獨占訪問，但它具有單點故障的嚴重缺點，雖然這可能是大型系統中的性能瓶頸，但這種簡單性帶來的優勢仍然可以彌補這些缺點，
4–2. 分散演算法
假設各項都會重復n次，在分散演算法中，當行程訪問資源時，需要批準大多數m》 n / 2，如果獲得大多數批準，則該程序獲得許可并可以進行處理，
雖然該方案解決了集中式演算法的單點故障問題，但是如果有太多的節點試圖訪問，則存在另一個問題，即沒有節點可以獲得足夠的投票而無法獲得充分的性能，
4–3. 分布式演算法
在該演算法中，假設系統上所有事件的順序可以定義為完全有序的關系，作為這個基礎，使用了前一章中描述的Lamport的邏輯時鐘，并且假設沒有訊息會丟失，
當行程嘗試訪問共享資源時，它會創建一條訊息，其中包含資源名稱，自己的行程號和當前邏輯時鐘，并將其發送給所有其他行程，當接收到該請求訊息時，根據其自身狀態執行以下操作，
1. 如果收件人未訪問該資源且未嘗試訪問該資源，則收件人會向發件人回傳“確定”訊息，
2. 如果收件人已在訪問資源，請不要回復并執行排隊請求，
3. 如果收件人正在嘗試訪問資源但尚未完成，請將輸入訊息中的時間戳與發送給其他行程的訊息中的時間戳進行比較，并將較低的一個作為獲勝者，如果收到的訊息具有小的時間戳，則收件人回傳OK訊息，如果自己的訊息具有較小的時間戳，則接收方將不會將輸入訊息排隊，
顯然，如果它不像process1或2那樣沖突，這個演算法就能正常作業，即使在沖突的情況下，也只建立了唯一一個行程可以訪問的條件，
與集中式演算法一樣，該演算法可以保證獨占控制，不會出現死鎖或饑餓， 此外，沒有單點故障， 盡管如此，單點故障被故障n位置特征所取代， 它可以通過回復權限或拒絕權限并引入超時來解決，但也會出現其他問題，例如需要多播通信原語， 不幸的是，目前尚未設計出超越集中式演算法的分布式演算法，并且仍在研究中，
當比較各個演算法時，變為如下，
5.領導者選舉演算法
許多分布式演算法需要一個特殊的程序，它具有領導者作為協調者或發起者的角色，哪個程序是領導者，唯一程序是否可以成為領導者是一個重要問題，研究人員在過去幾十年中一直在努力，
5–1. 欺負演算法
當協調員失敗并且任何行程P注意到該情況時，P根據以下程序激活選舉，
· P向所有具有比其自身更高數值的行程發送ELECTION訊息，
· 如果沒有人回復，P將贏得選舉并成為協調員，
· 如果來自具有高于P的數值的程序的答案，則將替換它， P的作業結束了，
使用該演算法，可以唯一地確定協調器，但是，該演算法需要大量的訊息和資料流量，可以說是冗余的，作為替代方案，存在環演算法，
5–2. 環演算法
與一般環演算法不同，該演算法不使用Token，發現協調器不作業的任何行程構造一個包含其自己的行程號的ELECTION訊息，并將該訊息發送給其后繼者（環網中的下一個節點），如果繼任者失敗，請跳過，如果沒有比您更高的數值的節點，您的訊息將仍然回傳給您自己的行程號，因此它將被指定為協調員，
在該演算法中，執行具有減少數量的訊息的領導者選舉，但是還可以通過將訊息的目的地設定到兩個相鄰節點來實作具有較少量資料流量的演算法，
6.阻止鏈和同步作為分布式系統
因此，在作為分布式系統之一的塊鏈中，行程之間的同步如何發生？
6–1. 區塊鏈和時鐘同步
塊鏈和邏輯時鐘
首先，考慮是否可以使用區塊鏈中的物理時鐘來掌握絕對時間關系，如第2章所述，參與網路的每個節點并不總是保持正確的物理時鐘，并且應該存在時鐘偏差，由于位元幣區塊鏈的平均生成時間是10分鐘，因此認為即使一定程度的大時鐘偏差也是可接受的，然而，當節點散布在世界各地時難以同步各個物理時鐘，并且還可能存在偽裝時鐘的節點，通過引入網路時間協議（NTP）來重新同步節點之間的正確時間是一項困難的技術，
區塊鏈和邏輯時鐘
因此，準備邏輯時鐘而不是物理時鐘是切合實際的，實際上，通過在塊中加入時間標記，可以制備出與Lamport邏輯時鐘非常相似的機制，
如［位元幣：點對點電子現金系統Satoshi Nakamoto］中所述，對作為礦工的區塊執行寫操作的每個節點本身具有作為時間戳服務器的角色，每個時間戳通過在其哈希中包含前一個時間戳來形成鏈，但是，無法保證這些節點保持正確的物理時鐘，時間戳的數值，即每個事務的順序和時間相對模糊，
由于時鐘的這種模糊性，有可能會進行雙重付款，但是，在位元幣區塊鏈中，只有最長的鏈是合法的，在次要驗證后丟棄不正確的交易，因此，區塊的順序隨著時間的流逝唯一確定，隨著每個時間戳的增加，前一個時間戳被加強，
總之，在區塊鏈中的模糊時間戳下，事務的順序一致性是不準確的，然而，利用鏈式連接的簡單機制，每個交易的發生前關系隨著時間的推移而建立，此外，還有一種激勵結構，以便礦工轉移到良好，交易不一致的順序不會發生，
可以說，實作類似于Lamport的邏輯時鐘的時鐘同步方法，因為事務之間的相對順序關系，即發生在之前的關系變得更清楚，
對于大多數交易，沒有因果關系，因此如果您引入向量時鐘并采用因果關系排序的概念，則可以極大地放松訂單關系的約束，然而，在區塊鏈中，由于結構本身默認共享所有塊的順序關系，所以保持總排序（相對于在一段時間之后的塊），
6–2. 區塊鏈和獨占控制演算法
即使在作為分布式系統的區塊鏈中，也需要排除控制，在區塊鏈網路中，每個節點并行地異步操作，此時，要共享的區塊鏈本身的資訊不應該不一致，
PoW·PoS中的獨占控制演算法
如第4章所述，分布式排他控制演算法可分為以下兩種型別，
· 基于Token的解決方案
· 基于權限的解決方案
PoW和PoS是基于權限的，其中，可以說它是類似于分布式演算法的機制，那么，您什么時候獲得訪問資源的權限？是的，就在你找到一個亂數時，
在PoW中，只有當找到在哈希值后跟0后跟n為0的亂數時，才可以執行有效的新塊寫操作，執行操作的礦工將其廣播給所有礦工并分享，
通常，當節點找到一個nonce并創建一個比他自己更早的塊時，minor會同步該資訊并移動以搜索下一個nonce值，這是因為如果您使用最長鏈被認為合法的規則搜索下一個nonce值，它們可以獲得更多利潤，盡管PoS優先為具有較大硬幣持有量的人提供資源訪問，但基本排除控制演算法結構也類似于分布式演算法，
但是，嚴格來說，不執行排除控制，這是為了在公共時間內同步并形成共識10分鐘，直到下一個區塊為止，當兩個或更多個節點同時找到亂數值時，寫入操作以非獨占狀態執行，此時，由于只有最長的鏈被認為是合法的，因此區塊鏈網路中的資訊與時間的流逝保持一致，叉子發生的一個問題是因為沒有執行嚴格的排他控制而且沒有確認最終結果，
BFT型別的獨占控制演算法
另一方面，通過BFT型別，基于許可的分散演算法執行排他控制，該演算法解決了分叉和終結問題，這是PoW中與分布式演算法類似的問題，
在BFT型別中，只有一個名為Proposer，Orderer等的節點有權生成新區塊，創建區塊時，您可以從所有參與節點收集投票，獲得超過2/3的同意，您才有權創建新塊，此時，有必要同意超過2/3而不是多數的原因是處理拜占庭故障，有關此問題的詳細資訊在“分布式系統中的容錯”一文中有所描述，
在BFT型別演算法中，與PoW等不同，只有一個節點可以獲得對區塊鏈的獨占訪問權限，因此不會立即確定fork和finality，但是，任何人都可以作為礦工參與網路的財產往往會丟失，
6–3. 區塊鏈和領導者選擇演算法
PoW，PoS和領導者選擇演算法
區塊鏈上的領導者選擇演算法類似于獨占控制演算法的機制，在位元幣中，用于選舉領導者的演算法，即，新創建塊的節點是PoW，
PoW允許添加一個塊作為一個好的領導者，為位元幣網路提供有計算復雜性和發現nonce的節點，每個成為領導者的礦工都會嘗試為位元幣網路做出貢獻，因為更容易早期同步到首先發現現時的節點并開始搜索下一個塊的現時值更有可能獲得獎勵，盡管存在鏈條完全由硬叉分支的問題，但是通過基于博弈論準備非常簡單的激勵結構，在塊鏈網路中實作作為分布式系統的同步，
在以太坊的情況下，由于塊生成的時間很短，因此傾向于發生更多的分叉，關于這一點，通過采用unkle塊的概念，我們實作了一種結構，即使產生不合法的鏈條也會給予一定的獎勵，
將來引入未來的PoS允許優先生成具有大硬幣保持量的節點的塊作為引導者，這是一種解決/改善PoW中必要電量變得巨大且易受51％攻擊的問題的演算法，這是一種基于博弈論的選舉演算法，如果一個節點持有大量硬幣，就不會采取破壞網路等惡意行為，
BFT和領導者選擇演算法
BFT型別演算法的問題在于如何選擇將投票給塊生成的領導者作為Proposer或Orderer，
在PBFT采取的HyperLedger當中，原為可信賴的機構才會注冊為Orderer， 但這是集中式的領導者選擇方法，與分布式系統存在著明顯的區別，
在Tendermint協議當中，領導者以回圈方式被選出，以通過與不同驗證者的輪換交替來提出建議， 此時，領導候選者是基于PoS，并且可以說是可以在分布式系統中實作領導者選擇的演算法之一，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24538.html
標籤：其他
上一篇：Wireshark使用記錄