999精品色在线播放_亚洲成av人在线播放无码_五月天精品在线_国产一级爱_国产精品久久人妻无码网站蜜臀_天天操夜夜做_18禁无码无遮挡在线播放_午夜免费福利在线观看_久久精品第九区免费观看_丰满少妇被猛烈进入高清app_亚洲日日爽_日本少妇网_欧美在线aa_天堂少妇_日韩精品xx_风流老熟女一区二区三区_小泽玛利亚一区二区免费_久久久久偷看国产亚洲87_婷婷色在线_www.ccyy.com日本

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

一、背景  

長安鏈在商業化實施過程中收集了諸多實際場景的需求。其中隨著區塊鏈系統的長期運行，賬本數據規模持續增長，帶來如下的技術挑戰：

1、隨著賬本數據容量的持續增長，基于全量賬本的交易防重處理耗時增加，導致tps越來越低；

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

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

二、什么是布谷鳥過濾器  

2.1 概率過濾器

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

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

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

添加

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

查詢

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

刪除

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

空間大小

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

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

3.1 簡介

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

3.2 特性

納秒級交易查重

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

優化到極致的內存占用

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

分片加速并行處理能力

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

數據安全不丟失

根據區塊高度間隔或者時間間隔保存當前交易過濾器快照功能讓節點隨停隨起不丟數據。

交易過濾器預熱，如果節點有歷史數據，但是沒有快照，交易過濾器初始化時預熱節點區塊數據，保證交易過濾器中的交易和節點已有數據一致。

LRU循環淘汰策略

交易過濾器中一組交易過濾器內部會利用LRU循環淘汰策略將最舊的布谷鳥過濾器淘汰調并創建一個新的布谷鳥過濾器，讓交易過濾器中永遠保存最近一批交易。

四、使用效果  

4.1 內存占用

在使用容量為一億的交易過濾器的情況下僅用305M內存。用戶可以根據實際情況調整交易過濾器的參數。

4.2 如何使用

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