Cuckoo filter for Chang'an chain transaction

We will use three articles to explain the work of Chang'an chain in improving the anti duplication ability of transactions , This is the first one .

All three chapters mainly include the following contents ：

1. Chang'an chain trading pool and anti duplication trading optimization ;

2. The cuckoo filter of Chang'an chain transaction ;

3. bigfilter Introduction and application of global transaction anti duplication component .

   One 、 background

Chang'an chain has collected the needs of many actual scenarios in the process of commercialization . With the long-term operation of the blockchain system , The scale of ledger data continues to grow , Bring the following technical challenges ：

1、 With the continuous growth of ledger data capacity , The anti duplication processing of transactions based on the full ledger takes more time , Lead to tps Lower and lower ;

2、 Transaction duplication prevention is based on the ledger base , In a massive trading scenario , The reading and writing burden of the ledger library is even heavier ;

Based on the above problems, we decided to launch Changan chain cuckoo filter .

  Two 、 What is? Cuckoo filter   

 2.1 Probability filter

Probability filter is a fast 、 Space saving data structures , Is a common data structure , On whether there is a problem , Retrieve whether an element is in a collection ” be called “ Set membership test ”; There is a false positive rate “ Set membership test ” be called “ Approximate set membership test ”.

One of the two outstanding implementations of the probability filter is the bloom filter , The other is the cuckoo filter .

2.2 Why use cuckoo filters

Add from 、 Inquire about 、 Delete 、 This paper expounds why the transaction filter is implemented based on cuckoo filter in terms of space size .

add to

The add operation will add the transaction to the transaction filter when the node is out of the block ; Cuckoo capacity as approaching load factor , Efficiency will curve down , And the efficiency of the bloom filter is constant , This is better than the cuckoo filter , But we can reduce the probability of false positives by controlling the number of items we want to save below the load factor in practical use .

Inquire about

Transaction anti duplication mainly relies on the query method to check whether items in the filter exist ; The time complexity of the cuckoo filter is O(1), And the bloom filter is O(k),k = The number of hashes for the bloom filter , The time complexity of cuckoo filter is better than that of Bloom filter .

Delete

Cuckoo filter supports deletion , The bloom filter does not support .

The size

In the actual test 200w Compared with the measured number of items, the bulon filter takes up less space 24%.

summary

Compare... Based on the following table , Chang'an chain team selected cuckoo filter as the basic implementation of the anti weight component of the transaction .

	Cuckoo Filter	Standard Bloom Filter
add to	The addition efficiency is O(1) As load factor capacity approaches , Efficiency will continue to decline	Fixed efficiency O(k)
Inquire about	O(1) Fixed check two drums	O(k)
Delete	O(1) Check up to two barrels	I won't support it
The size	The paper mentions that the space size is reduced compared with the bloom filter 40%, Actually measured 24% about	1

  3、 ... and 、 Changan chain cuckoo transaction filter   

3.1 brief introduction

Changan chain cuckoo transaction filter is based on cuckoo filter to add time rules 、 Fragmentation 、 Snapshot and other functions perfectly conform to the transaction anti duplication scenario of Chang'an chain .

 3.2 characteristic

Nanosecond transaction duplication check

Through time ID The rules , Only the latest batch of transactions are retained in the transaction filter , Transactions excluded from the time frame , Transactions within the range can also be quickly routed to a cuckoo for duplicate checking through the grouping time interval .

Optimized to the extreme memory footprint

Based on cuckoo hashes, 100 million transactions occupy 550M Space , If you save 100 million transactions directly ID About need 6G Space , Improved storage efficiency 89%.

Sharding accelerated parallel processing capability

Each segment contains multiple sets of cuckoo filters , The transaction is distributed to each group evenly and quickly through the partition algorithm , Let each set of cuckoo transaction filters process transactions at the same time .

Data security without loss

Save the current transaction filter snapshot function according to the block height interval or time interval, so that the node can stop and start without losing data .

The transaction filter warms up , If the node has historical data , But no snapshots , Warm up node block data when the transaction filter is initialized , Ensure that the transactions in the transaction filter are consistent with the existing data in the node .

LRU Circular elimination strategy

A set of transaction filters in the transaction filter will internally utilize LRU The circular elimination strategy eliminates the oldest cuckoo filter and creates a new cuckoo filter , Let the transaction filter always save the latest batch of transactions .

  Four 、 Use effect   

4.1 Performance improvement

We choose the block height 26w+, The size of the deal 13 Billion + Performance comparison test under the environment of .

- chart 1 It shows the cuckoo's TPS Chart , Whole TPS unstable , Take the red line as the reference line , It is obvious that TPS The curve of gradually inclines downward .

- chart 2 It shows that after opening cuckoo TPS Chart , In such a large trading volume TPS It is still in a stable state , There will be no downward curve .

chart 1： Before opening

chart 2： After opening

4.2 Memory footprint

In the case of using a transaction filter with a capacity of 100million, only 305M Memory . The user can adjust the parameters of the transaction filter according to the actual situation .

4.3 How to use

Changan chain cuckoo transaction filter is a filter based on local memory , Use Changan chain v2.2.1 And above , stay `chainamker.yml` Set in `tx_filter` Configuration item , It can realize fast transaction anti duplication processing .

For specific configuration, please refer to 《 Transaction filters - Configuration Guide 》https://docs.chainmaker.org.cn/operation/%E4%BA%A4%E6%98%93%E8%BF%87%E6%BB%A4%E5%99%A8-%E9%85%8D%E7%BD%AE%E6%8C%87%E5%8D%97.html

RECOMMEND

Recommended reading

One 、 Changan chain ChainMaker Anti duplication optimization of trading pool transactions

Tips

More Chang'an chain open source projects QA, You can log in to the open source community 、 Technical document library view .

Download the source code

https://git.chainmaker.org.cn/chainmaker/chainmaker-go

Consult the documentation

https://docs.chainmaker.org.cn/

Changan chain ChainMaker Case collection

http://www.wenjuan.com/s/UZBZJvhFGte/

“ Changan chain ChainMaker” It is the first independent and controllable blockchain software and hardware technology system in China , It is jointly developed by microchip Research Institute, enterprises and universities , With full autonomy 、 High performance 、 Strong privacy 、 The outstanding characteristics of wide cooperation . Chang'an chain is oriented to large-scale node networking 、 High transaction processing performance 、 Strong data security, privacy and other next-generation blockchain technology requirements , Integrate the special acceleration chip hardware of blockchain and the bottom software platform that can be assembled , To build high performance 、 High credibility 、 High security digital infrastructure provides new solutions , Provide strong blockchain technical support for Chang'an chain ecological alliance . The name “ Changan chain ”, Metaphorical meaning “ lasting political stability 、 Create brilliance again 、 Link to the world “.