FilterMaps：geth中eip-7745的实现

newlife
发布于 2天前
阅读 252

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  |

```go 
func addressValue(address common.Address) common.Hash
func topicValue(topic common.Hash) common.Hash
```

同时还定义了函数**addressValue**和**topicValue**，返回值统称**logValue**，这个值是address和topic经过固定哈希函数的值（可能是为了统一长度？）

## filterMap

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

```go
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，计算方法如下：
>
> ```go
> 	mapIndex := uint32(lvIndex >> f.logValuesPerMap)
> ```
>
> 即对logValue进行分组，每65536个logValue为一组。mapIndex是单个组的索引。
>
> mapIndex可以看做一个和lvIndex正相关但范围更模糊的顺序值。

### filterMap中数据的填充过程

```go
///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

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

分析**columnIndex**函数可以得出

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

### rowIndex

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

```go
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得出标记限制。
>
> 默认参数下每层可以标记的值：
>
> ```go
> 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

是一个实例：

```go
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是一组包含**mapIndex**key，存储的内容是block number，可以理解为mapindex和block number的对应表

### 3. filterMapBlockLVKey

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

filterMapBlockLVKey是一组包含**block number**key，存储的内容是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://eips.ethereum.org/EIPS/eip-7745)

[https://learnblockchain.cn/docs/eips/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://ethereum-magicians.org/t/eip-7745-two-dimensional-log-filter-data-structure/20580)

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

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

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

同时还定义了函数addressValue和topicValue，返回值统称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的值，由lvIndex和logValue计算得出，虽然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

原创
学分: 9
分类: EIP/ERC
标签: Geth RPC API 日志处理

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。