作者：Alexey Vanin

任何計(jì)算機(jī)系統(tǒng)都有監(jiān)控操作，可能會(huì)發(fā)送心跳信息、校驗(yàn)和查詢及哈希請(qǐng)求等。這些操作在本文中都被統(tǒng)稱為任務(wù)。在中心化系統(tǒng)中，通常會(huì)有一個(gè)受認(rèn)證的節(jié)點(diǎn)或節(jié)點(diǎn)群組來完成任務(wù)。而去中心化系統(tǒng)可以將任務(wù)下發(fā)給各個(gè)節(jié)點(diǎn)，從而靈活拓展，因此效率也顯然更高，但這也就導(dǎo)致了相應(yīng)的問題——到底如何在所選節(jié)點(diǎn)間分配任務(wù)。我們可以通過以下兩種方式解決這個(gè)問題：

? 節(jié)點(diǎn)隨機(jī)選擇要做的任務(wù)
? 節(jié)點(diǎn)使用dBFT之類的共識(shí)算法分配任務(wù)

本文將探討第二種方法。

拜占庭容錯(cuò)任務(wù)分配

假設(shè)有v個(gè)任務(wù)和n個(gè)可隨時(shí)在系統(tǒng)中工作的節(jié)點(diǎn)。每個(gè)任務(wù)和節(jié)點(diǎn)都有一個(gè)獨(dú)一無二的標(biāo)識(shí)符。因此每個(gè)節(jié)點(diǎn)都可以使用HRW [2]選擇任務(wù)，使用預(yù)先設(shè)定的算法來執(zhí)行任務(wù)。任務(wù)分配共識(shí)實(shí)際上確認(rèn)了所有任務(wù)都是在未發(fā)生技術(shù)故障的前提下完成的。

使用dBFT算法，即使網(wǎng)絡(luò)[1]中高達(dá)1/3的節(jié)點(diǎn)做出妥協(xié)也可以達(dá)成共識(shí)。舉個(gè)例子，若某系統(tǒng)n=v=3:

該系統(tǒng)有3個(gè)任務(wù)和3個(gè)節(jié)點(diǎn)，其中有一個(gè)節(jié)點(diǎn)有欺詐行為。

這些任務(wù)統(tǒng)一在各節(jié)點(diǎn)中進(jìn)行分配：如果每個(gè)節(jié)點(diǎn)承擔(dān)一個(gè)任務(wù)，在最壞的情況下會(huì)有一個(gè)任務(wù)可能無法被執(zhí)行。因此我們使用了冗余來確保所有任務(wù)都能被執(zhí)行。v任務(wù)須被n/3+1個(gè)節(jié)點(diǎn)執(zhí)行。在此情況下，節(jié)點(diǎn)任務(wù)池的大小可通過以下公式算出。

在此案例中，P(3,3) = 2

不管哪個(gè)節(jié)點(diǎn)做出了妥協(xié)，所有任務(wù)都仍能被正確執(zhí)行。

圖1 不同任務(wù)數(shù)前提下任務(wù)池大小的最大值

圖1標(biāo)明，該公式的值趨向于v/3，意味著在任何情況下各節(jié)點(diǎn)任務(wù)池中的任務(wù)都占所有任務(wù)的1/3。在負(fù)載增加的情況下系統(tǒng)可能不能正常拓展。

減小任務(wù)池大小

若系統(tǒng)的n=3 v=4，任務(wù)池大小即為P(3,4) = 2.3 ≈ 3。各節(jié)點(diǎn)的任務(wù)池大小就可減至2：

因此，各任務(wù)被執(zhí)行的幾率就都達(dá)到了66%。因此任務(wù)池大小可以縮減，只要確保一定的精度就可以了。
出于研究的目的，我們建立了一個(gè)模擬模型進(jìn)行實(shí)驗(yàn)，參數(shù)為v=1000。我們嘗試在不同n的情況下找到能使任務(wù)無法執(zhí)行的可能性小于0.00001的任務(wù)池大小。該模型已開源在github[3]。結(jié)果如圖2所示：

圖2 v=1000時(shí)的任務(wù)池容量實(shí)驗(yàn)

上圖顯示，該模型的實(shí)驗(yàn)數(shù)據(jù)實(shí)際上處于任務(wù)池容量的最大和最小值的區(qū)間里。因此當(dāng)n增加時(shí)，任務(wù)池所需容量會(huì)減小。任務(wù)池容量的最大值與實(shí)驗(yàn)值之間的差額可以使用R(x)（位于y1軸上，取0-1之間的任意值）公式求得一個(gè)近似值。然后任務(wù)池容量就可通過以下公式求得。

深入研究

本文并未考慮網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障的可能性，而且所有實(shí)驗(yàn)均在最壞假設(shè)下進(jìn)行，做出妥協(xié)的節(jié)點(diǎn)數(shù)也帶入了最大值。顯然，100個(gè)節(jié)點(diǎn)中出現(xiàn)33個(gè)妥協(xié)節(jié)點(diǎn)的比例也比3個(gè)節(jié)點(diǎn)中出現(xiàn)1個(gè)妥協(xié)節(jié)點(diǎn)的幾率小。因此可以將“妥協(xié)幾率”的方程定義為Q(x)，而后計(jì)算出任務(wù)池的大小為P(n,v)?R(n)?Q(n)。而當(dāng)妥協(xié)節(jié)點(diǎn)的數(shù)量小于n/3時(shí)，R(x)的的行為還需要深入研究。

參考文獻(xiàn)

1.張錚文，區(qū)塊鏈拜占庭容錯(cuò)算法：
https://docs.neo.org/en-us/ba...
2.一致性哈希（最高隨機(jī)權(quán)值）:
https://en.wikipedia.org/wiki...
3.模擬模型庫：
https://github.com/AlexVanin/...

原文翻譯自：https://medium.com/@neospcc/t...

總結(jié)

以上是生活随笔為你收集整理的如何在NEO共识节点间分配任务的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。