亚洲午夜久久久久久久久久久_日韩电影免费观看在线观看_六月丁香色婷婷_99re6在线观看_国产成人成网站在线播放青青_精品国产成人在线_91国产丝袜播放在线_亚洲一区三区视频在线观看_欧美xxxx在线观看_亚洲系列第一页

長安鏈交易防重之布谷鳥過濾器

一、背景  

長安鏈在商業(yè)化實施過程中收集了諸多實際場景的需求。其中隨著區(qū)塊鏈系統(tǒng)的長期運行，賬本數(shù)據(jù)規(guī)模持續(xù)增長，帶來如下的技術(shù)挑戰(zhàn)：

1、隨著賬本數(shù)據(jù)容量的持續(xù)增長，基于全量賬本的交易防重處理耗時增加，導(dǎo)致tps越來越低；

2、交易防重都基于賬本庫進行操作，在海量交易場景下，賬本庫的讀寫負擔(dān)更加繁重；

基于以上問題決定推出長安鏈布谷鳥過濾器。

二、什么是布谷鳥過濾器  

2.1 概率過濾器

概率過濾器是一種快速的、節(jié)省空間的數(shù)據(jù)結(jié)構(gòu)，是一種常見的數(shù)據(jù)結(jié)構(gòu)，就是否存在的問題，檢索一個元素是否在一個集合中”稱為“集合隸屬測試”；存在假陽性率的“集合隸屬測試”稱為“近似集合隸屬測試”。而在概率過濾器中比較優(yōu)秀的兩個實現(xiàn)一個是布隆過濾器，另一個是布谷鳥過濾器。

2.2 為什么使用布谷鳥過濾器

從添加、查詢、刪除、空間大小幾個方面闡述為什么基于布谷鳥過濾器實現(xiàn)交易過濾器。

添加

添加操作會在節(jié)點出塊時將交易添加到交易過濾器中；布谷鳥隨著接近負載因子容量，效率會曲線下降，而布隆過濾器效率是恒定的，這點布隆過濾器優(yōu)于布谷鳥過濾器，但是我們在實際使用中使我們要存的項的數(shù)量控制在負載因子以下即可減少假陽性的概率。

查詢

交易防重主要依賴查詢方法來檢查過濾器中項是否存在；布谷鳥過濾器的時間復(fù)雜度是O(1)，而布隆過濾器是O(k)，k = 布隆過濾器的哈希數(shù)量，布谷鳥過濾器查詢方法的時間復(fù)雜度優(yōu)于布隆過濾器。

刪除

布谷鳥過濾器中支持刪除操作，而布隆過濾器不支持。

空間大小

在實際測試中200w的項的數(shù)量實測相比布隆過濾器空間占用減少24%。

三、長安鏈布谷鳥交易過濾器  

3.1 簡介

長安鏈布谷鳥交易過濾器是基于布谷鳥過濾器添加時間規(guī)則、分片、快照等功能完美符合長安鏈的交易防重場景。

3.2 特性

納秒級交易查重

通過時間ID規(guī)則，交易過濾器中只保留了最近一批交易，排除時間范圍之外的交易，范圍內(nèi)的交易也可以通過分組時間區(qū)間快速路由到某個布谷鳥中查重。

優(yōu)化到極致的內(nèi)存占用

基于布谷哈希一億筆交易占用550M空間，如果直接保存一億交易ID約需要6G空間，存儲效率提升89%。

分片加速并行處理能力

每個分片包含多組布谷鳥過濾器，通過分片算法將交易均勻并且快速的分配到每一組，讓每組布谷鳥交易過濾器都可以同時處理交易。

數(shù)據(jù)安全不丟失

根據(jù)區(qū)塊高度間隔或者時間間隔保存當(dāng)前交易過濾器快照功能讓節(jié)點隨停隨起不丟數(shù)據(jù)。

交易過濾器預(yù)熱，如果節(jié)點有歷史數(shù)據(jù)，但是沒有快照，交易過濾器初始化時預(yù)熱節(jié)點區(qū)塊數(shù)據(jù)，保證交易過濾器中的交易和節(jié)點已有數(shù)據(jù)一致。

LRU循環(huán)淘汰策略

交易過濾器中一組交易過濾器內(nèi)部會利用LRU循環(huán)淘汰策略將最舊的布谷鳥過濾器淘汰調(diào)并創(chuàng)建一個新的布谷鳥過濾器，讓交易過濾器中永遠保存最近一批交易。

四、使用效果  

4.1 內(nèi)存占用

在使用容量為一億的交易過濾器的情況下僅用305M內(nèi)存。用戶可以根據(jù)實際情況調(diào)整交易過濾器的參數(shù)。

4.2 如何使用

長安鏈布谷鳥交易過濾器是基于本地內(nèi)存的過濾器，使用長安鏈v2.2.1及以上版本，在`chainamker.yml`中設(shè)置`tx_filter`配置項，即可實現(xiàn)快速的交易防重處理。