太阳城娱乐官网 - 在线登录入口

长安链交易防重之布谷鸟过滤器

一、背景

长安链在商业化实施过程中收集了诸多实际场景的需求。其中随着区块链系统的长期运行，账本数据规模持续增长，带来如下的技术挑战：

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`配置项，即可实现快速的交易防重处理。