FilterMaps:geth中eip-7745的实现

  • newlife
  • 发布于 1天前
  • 阅读 171

eip-7745的主要作用是取代之前的core/bloombits包中提供的功能,用来实现跨block的日志查询。新的设计完全抛弃了bloomfilter的使用,使用了全新的设计思路来解决问题

日志和事件是以太坊生态中重要的组成部分,可以用来跟踪并记录智能合约在区块链上的特定操作或数据。

geth日志的存储是是和block绑定的。

db中存储的key包含固定前缀,block number 和 block hash,value则是这个block中的Receipt,我们熟悉的Logs则是Receipt的一个字段。Log中才有用于查询的address和topic。 所以完整的存储顺序是block--Receipt--Log--address/topics

从这里我们可以看到日志是依附于block存在的,新的设计把日志视为第一主体,给所有的日志进行排序,每个日志都有自己独立的索引(LvIndex)。

逻辑定义

从逻辑上,对每个log event中包含的address和topic进行排序。

下面这个表是一个简单的例子,展示了log event中address和topic是如何进行排序的,注意其中block delimiter也参与了排序。

Block number Transaction index Log index Log event log value indices
0 block delimiter 0
1 0 0 Addr, Topic1, Topic2, Topic3 1, 2, 3, 4
1 0 1 Addr, Topic1, Topic2, Topic3 5, 6, 7, 8
1 1 0 Addr, Topic1, Topic2 9, 10, 11
1 1 1 Addr, Topic1 12, 13
1 1 2 Addr, Topic1, Topic2 14, 15, 16
1 block delimiter 17
2 0 0 Addr, Topic1, Topic2, Topic3, Topic4 18, 19, 20, 21, 22
func addressValue(address common.Address) common.Hash
func topicValue(topic common.Hash) common.Hash

同时还定义了函数addressValuetopicValue,返回值统称logValue,这个值是address和topic经过固定哈希函数的值(可能是为了统一长度?)

filterMap

filterMap是这个实现中最重要的数据结构。

type filterMap []FilterRow
// emptyFilterMap returns an empty filter map.
func (f *FilterMaps) emptyFilterMap() filterMap {
    return make(filterMap, f.mapHeight)
}
type FilterRow []uint32

从类型定义可以看出filterMap是一个长度是mapHeight(65536)的数组,数组的元素是FilterRow

FilterRow是一个uint32的数组,filterMap是一个二位数组。

mapIndex,一个新的概念。

参数valuesPerMap(默认65536)

每个filterMap都有固定的mapIndex,计算方法如下:

  mapIndex := uint32(lvIndex >> f.logValuesPerMap)

即对logValue进行分组,每65536个logValue为一组。mapIndex是单个组的索引。

mapIndex可以看做一个和lvIndex正相关但范围更模糊的顺序值。

filterMap中数据的填充过程

///from map_render.go       
if logValue := r.iterator.getValueHash(); logValue != (common.Hash{}) {
            lvp, cached := rowMappingCache.Get(logValue)
            if !cached {
                lvp = lvPos{rowIndex: r.f.rowIndex(r.currentMap.mapIndex, 0, logValue)}
            }
            for uint32(len(r.currentMap.filterMap[lvp.rowIndex])) >= r.f.maxRowLength(lvp.layerIndex) {
                lvp.layerIndex++
                lvp.rowIndex = r.f.rowIndex(r.currentMap.mapIndex, lvp.layerIndex, logValue)
                cached = false
            }
            r.currentMap.filterMap[lvp.rowIndex] = append(r.currentMap.filterMap[lvp.rowIndex], r.f.columnIndex(r.iterator.lvIndex, &logValue))
            if !cached {
                rowMappingCache.Add(logValue, lvp)
            }
        }

分析上面的代码可以看出,

  • 通过计算logValue的rowIndex来确定将当前logvalue的对应值放到哪一行,
  • 通过计算logValue的columnIndex,按照lvIndex,将这个值放到对应行的末尾

columnIndex

func (p *Params) columnIndex(lvIndex uint64, logValue *common.Hash) uint32

分析columnIndex函数可以得出

  • logValue是address和topic的hash值
  • lvIndex即上面的提到的index值
  • 该函数的返回值是一个uint32的值,由lvIndexlogValue计算得出,虽然logValue可能重复,lvIndex一定不会重复。因此,返回值大概率是唯一的(小概率冲突)。

rowIndex

这个函数确定数据添加到filterMap哪一行

func (p *Params) rowIndex(mapIndex, layerIndex uint32, logValue common.Hash) uint32

columnIndex函数不同,函数rowIndex还多了一个layerIndex的参数。

在不考虑layerIndex的情况下,同一个map中,相同的logValue会得出相同的返回值,即相同的logValue会被放到同一行。这样会导致某一行的数据了不可控。

layerIndex的出现就是为了解决某一行出现太多logValue需要标记的情况。

layerIndex

理想情况下,每个filterMap中有65536行数据,标记65536个logvalue,平均而言,每行可以标记一个logValue。

但是,实际情况是,其中的address和topic都会出现重复的情况,比如

  • 某个高频交易的合约地址
  • 某个常用的事件 topic0(transfer,etc),
  • 某个高频交易的外部地址被index的情况(topic1,topic2)

解决的方法就是限制每一行可以标记的logValue的上限。函数maxRowLength(layerIndex uint32) uint32 就是实现这个功能的。

这个函数是一个纯函数,给定layer得出标记限制。

默认参数下每层可以标记的值:

layer: 0 lenght: 8
layer: 1 lenght: 128
layer: 2 lenght: 2048
layer: 3 lenght: 8192
layer: 4 lenght: 8192

filterMap和其他类型的层次关系

  • epoch,每1024个filterMap组成一个epoch,定义为params中的mapsPerEpoch
  • 每个filterMap中含有65536个FilterRow,定义为params中的mapHeight
  • 每个filterMap中标记65536个logValues,定义为params中的valuesPerMap
  • 每个filterMap都有固定的mapIndex ,通过lvIndex计算可知,定义为lvIndex//valuesPerMap,即lvIndex >>16
  • 同理,每个epoch也有固定的index,通过lvIndex计算可知mapIndex,mapIndex>>10

DB中的存储

1. filterMapsRangeKey

是一个实例:

type FilterMapsRange struct {
    Version                      uint32
    HeadIndexed                  bool
    HeadDelimiter                uint64
    BlocksFirst, BlocksAfterLast uint64
    MapsFirst, MapsAfterLast     uint32
    TailPartialEpoch             uint32
}

用来表示当前FilterMaps(内存中的唯一实例)的indexedRange字段,表示当前日志索引的状态

2. filterMapLastBlockKey

filterMapLastBlockPrefix + mapIndex (uint32 big endian) -> block number (uint64 big endian)

filterMapLastBlockKey是一组包含mapIndexkey,存储的内容是block number,可以理解为mapindex和block number的对应表

3. filterMapBlockLVKey

filterMapBlockLVPrefix + num (uint64 big endian) -> log value pointer (uint64 big endian)

filterMapBlockLVKey是一组包含block numberkey,存储的内容是log value pointer,可以理解为block number和lvp的对应表

4. filterMapRowKey

filterMapRowPrefix + mapRowIndex (uint64 big endian) -> filter row

filterMapRowKey是一组key,存储的内容是filter row,即index data。这个部分的实现较为复杂,复杂的原因还是要处理logValue的分布不均匀这种情况,参考前面layerIndex的处理,变量baseRowLength参与了计算

mapRowIndex的计算:这里要注意的是,不能望文生义,

不是每个map的每个row都有一个key

而是baseRowGroupSize(默认32)参与了key的生成,即32个map的row聚集在一起算一个value。

我们可以计算下一个epoch中大约含有多少filterMapRowKey,

1024*65536/32,这个是最多的情况

参考文献

https://eips.ethereum.org/EIPS/eip-7745

https://learnblockchain.cn/docs/eips/EIPS/eip-7745/ https://ethereum-magicians.org/t/eip-7745-two-dimensional-log-filter-data-structure/20580

https://gist.github.com/zsfelfoldi ,四篇文档 https://github.com/ethereum/go-ethereum

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
newlife
newlife
0x2664...3FF4
江湖只有他的大名,没有他的介绍。