[發明專利]大規模可擴展、低延遲、高并發性和高吞吐量的去中心化共識方法

有效

• 申請號: 201780052000.8
• 申請日: 2017-08-25
• 公開（公告）號: CN109952740B
• 公開（公告）日: 2023-04-14
• 發明（設計）人: 張建鋼
• 申請（專利權）人: 張建鋼
• 主分類號: H04L67/1042
• 分類號: H04L67/1042;G06F11/20;G06F11/07;G06F11/14
• 代理公司: 北京綏正律師事務所 11776
• 代理人: 龐愛武

大規模可擴展、低延遲、高并發性和高吞吐量的去中心化共識方法，具有自適應性、可大規模擴展、具有低延遲、高并發性和高吞吐量，通過并行處理和位置感知形成拓撲以及O(n)消息達成共識協議。

相關申請的交叉引用

本申請要求2016年8月25日提交的題為“大規模可擴展、低延遲、高并發性和高吞吐量、去中心化共識算法”的第62/379,468號美國專利申請的優先權，其公開內容通過引用整體合并于此。

技術領域

本發明屬于參與實體之間的去中心化和/或分布式共識的技術領域。更具體地，本發明屬于軟件應用和/或設備或由這些應用和設備表示的人員和機構之間的分布式或去中心化共識的技術領域。

背景技術

傳統的共識算法要么針對大規模優化，要么針對低延遲，或者高并發性，或者它們中的一些的組合優化，而不是針對全部優化。在需要大規模、低延遲、高并發性和高吞吐量的用例中很難利用這些共識算法。

發明內容

本發明是一種大規模可擴展、低延遲、高并發性和高吞吐量的去中心化共識方法，其具有低延遲、高并發性和高吞吐量的大規模可擴展性。

本發明通過技術的組合實現了這一點。首先，它基于自動學習和自動調整的位置接近度并受制于可配置的最優成員多少的上限(表示為s)，將共識參與實體(也稱為節點，以下稱為n的總大小)劃分為許多小的共識域。

然后，來自每個共識域的自動選舉的自動調整的代表性節點(表示為命令節點)形成命令域，并且作為命令域與其歸屬共識域之間的橋接。命令域中的命令節點選舉并自動調整其主節點(表示為主節點)。主節點的選舉可以是位置偏置的，因此它具有對其他命令節點的最低總體低延遲。命令域和所有共識域在本發明中形成所謂的共識拓撲。可能存在多層共識域和命令域，但是為了簡潔起見，本發明僅描述了“一個命令域，多個平坦共識域”范例。

命令域負責接受來自邏輯上的外部客戶端的共識請求，與所有共識域協調以實現共識并將結果返回給調用客戶端。所有命令節點可以同時接受客戶端請求以獲得高吞吐量和高并發性，當他們這樣做時，它們被稱為接受節點。主節點本身是命令節點，因此除了向接受節點接收的請求發放簽名序列號之外，它可以是接受節點。

在從客戶端接收到REQUEST消息時，接受節點聯系主節點以獲得為該請求分配的序列號。它組成一個PREPARE消息，并將其并行多播到所有其他命令節點。PREPARE消息由接受節點簽名，并且包括原始REQUEST請求、時間戳、當前主節點、當前拓撲ID以及由主節點分配和簽名的序列號等。

共識域的命令節點通過同域命令節點協調機制進行協調，以將PREPARE消息轉發到共識域中的所有其他節點。可以發送PREPARE消息的“流”或“批處理”。

在接收到PREPARE消息時，共識域中的每個節點試運行該請求，向命令節點返回DRYRUN消息。DRYRUN消息由每個初始共識節點簽名，并且由共識的當前提交狀態的加密散列以及當提交試運行效果時的預期狀態等組成。取決于本發明的用途，如果是在框架層面使用，例如在區塊鏈中，DRYRUN可以(并且應該)是超級輕量級的，它只是斷言請求是在所有先前的請求或檢查點上確定性地接收/存儲的。如果要觸發一系列確定性執行，它不一定是最后一個。

用于特定PREPARE消息的每個域的命令節點聚合所有DRYRUN消息(包括自身的DRYRUN消息)并將它們以批處理方式多播到命令域中的所有其他命令節點。

每個命令節點以并行和非阻塞模式觀察，直到拓撲中的所有共識節點的三分之二對狀態達成一致或三分之一+1達成共識失敗。當發生這種情況時，它會向其本地共識域的所有其他節點發送commit-global(如果至少有三分之二達成共識)或fail-global(如果三分之一+1未達成共識)。接受節點同時將結果發送回客戶端。