📜 [專欄新文章] 區塊鏈管線化的效能增進與瓶頸
✍️ Ping Chen
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
使用管線化(Pipeline)技術可以提升區塊鏈的處理效能,但也可能會產生相應的代價。
Photo by tian kuan on Unsplash
區塊鏈的擴容方案
說到區塊鏈的效能問題,目前討論度最高的應該是分片(sharding)技術,藉由將驗證者分成多組的方式,可以同時分別處理鏈上的交易需求,即使單分片效能不變,總交易量可以隨著分片/驗證者集的數量線性增加。
除了分片,另一個常用來提升程式效能的方案是將計算步驟拆解,以流水線的方式將複雜的運算攤平,降低系統的閒置時間,並大幅提升工作效率。為了達到管線化預期的目的,會需要先知道系統的瓶頸在哪。
區塊鏈的效能瓶頸
熟悉工作量證明設計哲學的人應該會知道,區塊鏈之所以需要挖礦,並不是為了驗證交易的正確性,而是要決定交易的先後順序,從而避免雙花和帳本分裂的發生。可以說,區塊鏈使用低效率的單線程設計,並付給礦工高額的成本,都只為了一件事,就是對交易的全局排序產生共識。
在這樣的基礎之上,區塊鏈在一段時間內可以處理的交易數量是有限的,這之中包含許多方面的限制,包括 CPU 效能、硬碟空間、網路速度等。其中,關於 TPS(每秒交易數) 提升和對硬體的要求大致上是線性增加的,但在設計共識演算法時,通訊複雜度常是平方甚至三次方的關係。
以現在的目標 TPS 來說,處理交易和生成一個合法的區塊並不困難,只是因為區塊鏈的特性,新區塊需要透過洪水法的方式擴散到全網路,每個節點在收到更新請求的時候都要先執行/驗證過區塊內的交易,等於整個廣播的延時會是「驗證區塊時間×經過的 hop 數量」這麼多。似乎網路越分散、節點越多,我們反而會需要降低計算量,以免讓共識不穩定。
管線化的共識機制
使用權益證明取代工作量證明算是行業發展的趨勢,除了環保或安全這些比較顯然的好處之外,權益證明對產生共識的穩定性也很有幫助。首先,權益證明在同一時間參與共識的節點數是已知的,比較容易控制數量級的邊界;其次,權益證明的出塊時間相較工作量證明固定很多,可以降低計算資源不足或閒置的機率。
相較於工作量證明是單一節點出塊,其餘節點驗證,權益證明的出塊本身就需要很多節點共同參與,瓶頸很像是從驗證轉移到通訊上。
以 PBFT 為例,每次產新區塊都需要經過 pre-prepare, prepare, commit 三個階段,你要對同意驗證的區塊簽名,還要對「你有收到某人的簽名」這件事簽名,再對「你有收到 A 說他有收到 B 的簽名」這件事簽名,過程中會有很多簽名飛來飛去,最後才能把一個區塊敲定。
為了降低每兩個區塊間都需要三輪簽名造成的延遲,後來的共識演算法包括 HotStuff 和 Casper FFG 採用了管線化的區塊驗證過程。也就是對區塊 T 的 pre-prepare 同時是對 T-1 的 prepare 和對 T-2 的 commit。再加上簽名聚合技術,出塊的開銷在複雜度等級和係數等級都降低許多。
然而,要保持管線化的區塊生產順利,需要驗證者集合固定不變,且網路通訊狀況良好。如果會經常更動驗證者集合或變換出塊的領導者,前後區塊間的相依性會是個大問題,也就是 T 的驗證者集合取決於 T-1 裡有沒有會導致刪除或新增驗證者的交易,T-1 的合法性又相依於 T-2,以此類推。
當激烈的分叉出現的時候,出塊跟共識的流水線式耦合就從優雅變成災難了。為了避免這種災難,更新的共識演算法會限制驗證者變更的時機,有些叫 epoch 有些叫 checkpoint,每隔一段時間會把前面的區塊徹底敲定,才統一讓驗證者加入或退出。到這些檢查點的時候,出塊的作業流程就會退化成原本的三階段驗證,但在大部分時候還是有加速的效果。
管線化的狀態更新
另一個可以用管線化加速的是區塊鏈的狀態更新。如前所述,現在公鏈的瓶頸在於提高 TPS 會讓區塊廣播變慢,進而導致共識不穩定,這點在區塊時間短的以太坊上尤其明顯。可是如果單看執行一個區塊內的交易所花的時間的話,實際上是遠遠低於區塊間隔的。
只有在收到新區塊的時候,節點才會執行狀態轉移函數,並根據執行結果是否合法來決定要不要把區塊資訊再廣播出去。不過其實只要給定了交易集合,新的狀態 s’ = STF(s, tx) 應該是確定性的。
於是我們有了一個大膽的想法:何不乾脆將交易執行結果移出共識外呢?反正只要大家有對這個區塊要打包哪些交易有共識,計算的結果完全可以當作業留給大家自己算吧。如果真的不放心,我們也可以晚點再一起對個答案,也就是把這個區塊執行後的新狀態根包在下個區塊頭裡面。
這就是對狀態更新的管線化,在區塊 T 中敲定交易順序但暫不執行,區塊 T+1 的時候才更新狀態(以及下一批交易)。這麼做的好處十分顯而易見,就是將原本最緊繃的狀態計算時間攤平了,從原本毫秒必爭的廣播期移出來,變成只要在下個塊出來之前算完就好,有好幾秒的時間可以慢慢來。新區塊在廣播的每個 hop 之間只要驗證交易格式合法(簽名正確,有足夠的錢付手續費)就可以放行了,甚至有些更激進的方案連驗簽名都省略了,如果真的有不合法交易混進去就在下個區塊處罰礦工/提案者便是。
把負擔最重的交易執行移出共識,光用想的就覺得效能要飛天,那代價呢?代價是區塊的使用程度會變得不穩定。因為我們省略了執行,所以對於一筆交易實際用掉多少 gas 是未知的。本來礦工會完整的執行所有交易,並盡可能的塞滿區塊空間,然而在沒有執行的情況下,只能以使用者設定的 gas limit 當作它的用量,能打包的交易會比實際的上限少。
緊接著,下一個問題是退費困難。如果我們仍然將沒用完的手續費退還給使用者,惡意的攻擊者可以透過發送 gas limit 超大,實際用量很小的交易,以接近零的成本「霸佔」區塊空間。所以像已故區塊鏈 DEXON 就直接取消 gas refund,杜絕濫用的可能。但顯然這在使用者體驗和區塊空間效率上都是次優的。
而最近推出的 smartBCH 嘗試擬了一套複雜的退款規則:交易執行後剩餘的 gas 如果小於 gas limit 的一半(代表不是故意的)就退款;如果剩餘量介於 50%-75% 可以退一半;超過 75% 推斷為惡意,不退款。乍看是個合理的方案,仔細一想會發現製造的問題似乎比解決的還多。無論如何,沒用掉的空間終究是浪費了,而根據殘氣比例決定是否退款也不會是個好政策,對於有條件判斷的程式,可能要實際執行才知道走哪條路,gas limit 一定是以高的情況去設定,萬一進到 gas 用量少的分支,反而會噴更多錢,怎麼想都不太合理。
安全考量,退費大概是沒希望了。不過呢,最近以太坊剛上線的 EIP1559 似乎給了一點方向,如果區塊的使用程度能以某種回授控制的方式調節,即使偶爾挖出比較空的區塊似乎也無傷大雅,也許能研究看怎麼把兩者融合吧。
管線化方案的發展性
考慮到以太坊已經堅定地選擇了分片的路線,比較激進的單鏈高 TPS 管線化改造方案應該不太有機會出線,不過管線化畢竟是種歷史悠久的軟體最佳化技巧,還是很有機會被使用在其他地方的,也許是 VDF 之於信標鏈,也許是 rollup 的狀態轉換證明,可以坐等開發者們表演。
倒是那些比較中心化的 EVM fork/sidechain,尤其是專門只 for DeFi 的鏈,管線化加速可以在不破壞交易原子性的前提下擴容,確實是有一些比分片優秀的地方可以說嘴,值得研究研究,但這就要看那些機房鏈們有沒有上進心,願不願意在分叉之餘也投資發展自己的新技術了。
給我錢
ping.eth
區塊鏈管線化的效能增進與瓶頸 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
「時間複雜度排序」的推薦目錄:
- 關於時間複雜度排序 在 Taipei Ethereum Meetup Facebook 的最佳解答
- 關於時間複雜度排序 在 小手老師x語言治療星球 Facebook 的最讚貼文
- 關於時間複雜度排序 在 Whiscript 威事記 Facebook 的最讚貼文
- 關於時間複雜度排序 在 [其他] 關於時間複雜度(big O)的排序- 看板Math - 批踢踢實業坊 的評價
- 關於時間複雜度排序 在 排序Sorting - 演算法的分析與證明 的評價
- 關於時間複雜度排序 在 第二章演算法的複雜度和題度難度的下限 - GitHub 的評價
- 關於時間複雜度排序 在 [軟體工程師雜談] 輕鬆搞懂演算法:快速排序(quick sort) |IT鐵人賽 的評價
- 關於時間複雜度排序 在 新手關於插入排序的時間複雜度有疑問想請教- 軟體工程師 - Dcard 的評價
- 關於時間複雜度排序 在 最新趨勢觀測站- 氣泡排序法時間複雜度的推薦與評價,GITHUB 的評價
時間複雜度排序 在 小手老師x語言治療星球 Facebook 的最讚貼文
3~6歲發展階段的孩子,開始發展出簡單的敘事
一開始可能是跳躍性的描述書中的人事物
慢慢的會依照時間順序性描述
進而使用連結詞
或是到了5歲開始有因果概念
一直到最後能呈現一個完整的故事
-----------------------------------------
📍而這個語言階段的孩子,可以用哪些繪本引導呢?
本次精選15本書單也一樣附上推薦的理由、特色,
並大致按照語言複雜度排序
🔔歡迎留言並tag兩位好友:
『@____ @____ ,一起來看看3~6歲讀什麼吧!』
我就會把精選書單私訊給你~
共讀時大家可以參考上次跟各位分享的
CROWD提問技巧 https://reurl.cc/0oO6zl
喜歡的話也別忘了
🌐分享出去~讓更多需要的人也能夠看見!
👍按讚粉專~追蹤第一手消息!
-----------------------------------------
延伸閱讀 :
0~1歲推薦書單 https://reurl.cc/qd8Zdn
0~1歲共讀技巧 https://stxplanet.blogspot.com/2020/02/01_19.html
1~3歲推薦書單 https://reurl.cc/WdLqdD
1歲以上語言誘發技巧 https://reurl.cc/GVrXrx
時間複雜度排序 在 Whiscript 威事記 Facebook 的最讚貼文
再重複一次,我愛波本桶,我也幾乎只愛波本桶。對於南投酒廠的波本桶一直充滿了好奇心,其實當初K牌剛剛建廠時我對台灣的威士忌充滿了不信任以及各種質疑,我一直不相信台灣可以做出拿得上檯面的東西。但是我錯了,K牌開始不斷的得獎,後來南投酒廠的Omar也起來了,也掃了許多國際獎項,我開始認知到了,我們做的威士忌無庸置疑是世界級的。
運氣很好的參加到第二批次的南投酒廠波本桶8年原酒全品項的品酒會,第一批次一共出了七隻,第二批次出了六隻。Omar 8年波本桶原酒有一些共同特性。因為我希望可以好好檢視這六隻酒,故在品酒會把Sample用分享瓶方式帶回家紀錄。畢竟在一個半小時內喝完6隻平均abv在55%以上的酒款對味蕾是相當大的負擔,在人多的環境也會造成嗅覺的混亂,加上我身邊的人擦了濃香,旁邊的人在吃味道相當重的食物,我希望日後品飲會一律禁止香水古龍水以及進食,尊重酒款也尊重想要專心品飲的品飲者。
1. 全都是Natural Color,沒有添加食用焦糖調色。但出奇的六隻一字排開幾乎看不出色差。
2. 全部使用None Chill Filter,保留酯類酚類及醇類增加酒體架構。
3. 天使稅每年幾乎是 6~7%,遠高於蘇格蘭的”稅率”,最終裝瓶瓶數幾乎都落在150到160瓶。政彥也提到最貴的成本就在這裡,也解釋了為什麼NAS的單價相對高昂。
4. 全部使用First Fill Bourbon Cask。
5. 桶源並不來自單一酒廠,Omar每年購入約1500個波本桶,所以要從各個酒廠收購。
比較有趣的是選桶的模式,我當天晚上若沒聽錯,選桶是以隨機決定,剩下沒被抽中的會被拿去做調和,理由是因為不可能每一桶都試。不禁讓我想到也許有許多超級出色的單桶就這樣消失在酒海中了,這就是機率與運氣的問題了。
品完這六隻之後,我發現嗅覺上的通處是鹹香以及柑橘調,味覺上的差異性相對懸殊。品酒會上品飲的順序是由政彥排的,應該是有由從淡漸濃(甜)。我則是由桶號的數字大小排序。品酒會使用的是GlenCairn杯,我則是使用ISO杯。品飲時間從品酒會的一個半小時拉長到三天,一天兩隻,一隻酒平均花半個小時,為了觀察香氣變化。
桶號各是 11100135、11100144、11100158、11100170、11100181、11100188。酒精度各為54.8%、56.8%、54.8%、57.3%、57.9%、54.8%。因為色差皆在一兩個色階內,就統一稱為橘銅色。統一使用透明ISO也統一在午夜12點進行品飲(最後一餐皆為六點半結束,皆為清淡食物以確保味蕾敏銳度)。以下開始品飲文。
11100135:
鼻腔:
香氣強度: 中上
香氣分子: 果酸、白糖霜粉、 梅子、鹹氣、太空氣球 (乙酸乙酯)、焦糖、調酒用苦精、乾燥花、陳皮梅。
味蕾:
酒體: 中上
油脂: 中上
單寧: 中
複雜度: 中
味蕾表現: 鹹、胡椒鹽、香草、乾燥花 (薰衣草)、辣薄荷、黃水梨、人蔘、小熊軟糖、檸檬夾心餅乾、木屑、Pizza餅皮、香港撈麵。
11100144:
鼻腔:
香氣強度: 中
香氣分子: 花生、奶油車輪餅、柑橘、鹹氣、鳳梨、方塊酥、木質精油、牛奶巧克力、萬精油、情人果。
味蕾:
酒體: 中
油脂: 中上
單寧: 弱
複雜度: 中
味蕾表現: 果乾、杏桃、餅乾麵糰、淡煙燻、柳橙汁、麥芽糖。整體平衡感良好、單寧、油脂、酒體、甜鹹各自表現鮮明且不碰撞。
11100158:
鼻腔:
香氣強度: 中上
香氣分子: 麥芽糖、新波本桶、太空氣球、蠟質、煙燻、奶油、辣薄荷、芭樂、青草、根莖植物。
味蕾:
酒體: 強
油脂: 低
單寧: 中上
複雜度: 中
味蕾表現: 大地氣息、塵土感、鹹蛋、松木精油、芭樂、薄荷、奶油糖、萊姆酒暗示、櫻桃可樂、櫻桃軟糖。單寧些許過強,些許欠缺平衡性。但整體架構仍算舒適。
11100170:
鼻腔:
香氣強度: 強
香氣分子: 強烈花生、塵土、蠟質、芹菜、青草、白胡椒、蜂蜜、紅茶葉、奶茶、血橙、橙汁、鳳梨罐頭。
味蕾:
酒體: 強
油脂: 中
單寧: 中
複雜度: 高
味蕾表現: 新鮮花香、玉米糖漿、玉米榖片、小米粥、生萵苣葉、菠蘿油、果汁感、香草、楊桃、藍莓、收尾是淡淡的中藥。
11100181:
鼻腔:
香氣強度: 中
香氣分子: 紅茶葉、鹹氣、焦糖布丁、夜來香、風乾柑橘、煙燻、薑片、萊姆酒暗示、太空氣球。
味蕾:
酒體: 強
油脂: 弱
單寧: 弱
複雜度: 中
味蕾表現: 熟水果、橘子果醬、薄荷、楓糖漿、糖炒栗子、溫泉饅頭、蠟質、黑糖薑片。
甜度非常高,但欠缺複雜度及層次感導致有些失衡。
11100188:
鼻腔:
香氣強度: 中上
香氣分子: 奶油、太空氣球、鮮割青草、白荳蔻、新鮮白桃、白巧克力。
味蕾:
酒體: 強
油脂: 弱
單寧: 中
複雜度: 中下
味蕾表現: 薰衣草、蠟質、楓糖漿、肉桂、芭樂。
整體來說快速熟成的弱點就是層次感以及尾韻相對欠缺,但是在一年6~7%的天使稅之下存酒的確不適合放太久,全部酒款當中只有一隻單寧相對強烈,但是其餘酒款皆屬平衡。個人認定也許可以考慮放十年的單寧應該會適中,但是失酒太過嚴重成本上應該無法負荷。非常好奇為什麼只用First Fill 而不用 Refill Bourbon Cask,相信應該會相當不錯。
因為全部都是用First Fill導致全部酒款都有強烈的美波影子,而許多台灣人剛好就懼怕美波的強烈辛香、乙酸乙酯以及蠟質溶劑感,故好奇為什麼目前沒有做Refill的桶陳。
這次最喜歡的桶號是11100144以及11100170,144以鼻腔取勝,奶油車輪餅、鳳梨、萬精油以及濃濃的情人果非常有趣,聽起來雖然強烈,但是在鼻腔上非常具有記憶點。170以味蕾取勝,強烈乾燥花香、玉米片、菠蘿油、強烈楊桃以及藍莓讓我印象非常深刻。
台灣的酒款似乎都以強烈爆炸性香氣取勝,在鼻腔上實在令人難忘,味蕾上雖然稍嫌層次感不足及韻尾偏短,但這也是高氣溫陳年環境所造成的,也許考慮把酒丟到八八坑道裡去陳年呢? 台灣的威士忌無比精彩,若你還沒試過,請看看南投酒廠這幾隻精采的8年波本桶,若你也跟我一樣喜歡波本桶,你也會被它所驚豔的。
-Whiscript
時間複雜度排序 在 排序Sorting - 演算法的分析與證明 的推薦與評價
排序 是整理資料中一種最直接的方式。 基於比較的排序Comparison Based Sorting. 演算法, 時間複雜度, 空間複雜度. 泡沫排序法 ... ... <看更多>
時間複雜度排序 在 第二章演算法的複雜度和題度難度的下限 - GitHub 的推薦與評價
上面的定義通常是指worst-case time complexity,即使average-case time complexity 也可採用。本書若無特地說明,則一概都指worst-case lower bound。 對於排序演算法Ω(n ... ... <看更多>
時間複雜度排序 在 [其他] 關於時間複雜度(big O)的排序- 看板Math - 批踢踢實業坊 的推薦與評價
大家好,想請教大家一題關於執行程式時,各函數的時間複雜度的排序。
題目將以下所有函數依照時間複雜度O排序,由大到小:
・N^2 + logN
・2^(2^N)
・NlogN
・lnN
・(n+1)!
・lg(lgN)
・n^3
・n!
・(3/2)^N
・2^(logN)
以下是我的排序,時間複雜度最大排到最小的
1. N! , (N+1)! ----這兩個相等 都是O(N)
2. 2^(2^N) ----比O(C^N)又更大
3. (3/2)^N ----O(C^N) (Exponential)
4. 2^(logN) ----比O(C^N)小因為是指數是放logN
5. n^3 ----O(N^3)
6. N^2 + logN ----O(N^2)
7. NlogN ----O(NlogN)
8. lnN ----O(logN)
9. lg(lgN) ----O(loglogN)
想問大家以上的排序正不正確?
我最主要的疑惑是 2^(2^N) , (3/2)^N , 2^(logN) 這三個,
他們都是Exponential的成長速度,但因為指數部分又有包含N在內變數,
所以應該是要照我的排序,還是其實他們三個的時間複雜度都一樣呢?
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 103.232.136.184 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1639204484.A.AC6.html
... <看更多>