DxChain中文博客

链结构(二):存储优化


前言

上一章介绍了链结构的数据存储格式,以太坊所设计的MPT树存在一定的优势,可以在尽量压缩数据的情况下,具有默克尔树特性,并保持较高的读写性能。但随着以太坊应用规模的不断扩大,暴露出的问题越来越多。本次我将介绍两个主要问题查询和写入对磁盘访问次数较频繁,以及十六进制前缀树造成的一系列困扰,并根据该问题,介绍具有代表性的解决方案Merkelized LSM树。

本章提纲

  • 现存问题
  • 优化方案
  • 总结

现存问题

首先回顾一下以太坊的存储结构,在以太坊内分为两类类节点,摘自[1]:

  • 全节点(Branch Node):为图中的分支节点,负责记录前缀树key值,key值为十六进制,加上最后value对应的falg位,一共17个槽位。
  • 子节点(Short Node):为图中的扩展节点和叶子节点,两类节点在代码中的定义一致,通过value值的指向不同进行区分,扩展节点的Val变量指向子节点,而叶子节点Val变量指向key所对应的value值。
enter image description here

该结构仍然存在一些问题:

  1. 当我们读取以太坊中账户的键值金额,需要从LevelDB中查询64次,才能读取到。单个键值的写入将产生同样数量级的LevelDB操作。LevelDB在读写存在额外的操作,进一步降低了存储设备的寿命。较为常用的数据存储设备如SSD,进行频繁的写入,造成磨损,其性能和寿命将会受到严重的影响。需要进一步减少以太坊的读写次数,提升数据的吞吐量,减少硬件更换成本。同时攻击者可利用读写对LevelDB查询频繁的问题对以太坊进行DoS攻击,造成以太坊服务瘫痪。
  2. 以太坊trie采用的十六进制前缀树,会带来一定复杂的变化以及混乱。问题较多出在分支节点上,在上一章我们提到以太坊将byte[]进一步转换为半字节nibble,在取键值的时候,可能会在半字节处终止,因此又需要额外添加一个奇偶校验位。还有,当一个数据过小,为节省存储空间,该数据不会进行哈希运算,而是直接存入原始数据的值。此类等等问题,给开发者带来许多麻烦和痛苦。

优化方案

目前已经有较多团队提出新的解决方案,本文介绍一种其中较具为代表性的数据存储优化方式,采用二进制树代替十六进制树,并将Merkle树分级缓存,减少操作写入对Merkle节点的改动。分以下两步进行优化:

  1. Binary Trees
  2. Merkelized LSM

Binary Trees

将十六进制树转换为二进制树,简化了分支节点,保证一个分支节点最多有两个子节点。二进制树的节点具有以下字段:

  • left,right:树结构上左右节点的哈希值作为指针;
  • value(可空):通过该键可以获取到该子节点;
  • prefix(可空):该字段目的是将十六进制分支树替换为二进制树。

如图,父节点的前缀为0xcafe和一个数字,其中数字表示该节点的前缀占用7bit。父节点的两个指针指向左右子节点,父节点的value字段为空,左子节点的键值对为(0xcafe, 0x00),右子节点的键值对为(0xcaff, 0x01),前缀均为0x0,由于子节点value字段不为空,没有子节点。

Image for post

客户端可以用仅占两字节的 header 实现对数据的编码。采用Binary Trees需要额外占用两个字节,而同样数据进行格式编码RLP至少需要 5 个字节。

由于1byte=8bit,通过定义每一位bit来表示整个树:

  • 如果第7位bit不为空,表示存在左子节点,value字段的32 个字节哈希值指向左子节点。如果该位为空,表示不存在左子节点;
  • 如果第6位bit不为空,表示存在右子节点,value字段的32 个字节哈希值指向右子节点。如果该位为空,表示不存在右子节点;
  • 如果 第5位bit不为空,value字段表示为该节点的值;
  • 如果第4位bit不为空,表示header
  • 则该 header 会有一个额外的字节来给出前缀比特中的数字;前缀比特则跟着 左/右 子节点哈希值放置。
Image for post

Merkelized LSM

Merkelized LSM(mLSM)的新型数据结构,通过结合Merkle树和日志结构树(The log-structured merge-tree ,LSM-tree),该方案通过维护多个Trie结构,对以太坊的查询和验证功能进行解耦,针对性优化了数据的写入,并减小了读取的查询次数。LSM-tree具有多个缓存等级,每个级别具有一定数量级的Merkle,级别越高,Merkle树规模越大。

mLSM采用二进制代替十六进制Merkle树,因为二进制更好的平衡了数据。在LevelDB数据库的中间添加一层缓存,缓存中可对mLSM树进行批量处理,并将需要进行更新和写入的数据写入L0级缓存。当树的规模达到该级别的阀值,会将该级内的所有Merkle树压缩成一棵Merkle树,然后加载至下一级别缓存。

该方案通过避免更新数据,导致以太坊的根节点哈希值发生改变,减少数据更新的节点。写入操作仅需要O(H)的复杂度,H为mLSM树的高度,相对于以太坊降低了大量的写入操作。

总结

此类方案对MPT的优化需要一段时间的过渡期,在这段时间内,以太坊要同时维护两种树结构。需要保证转换树结构的过程不会影响链的运行,而且必须确定使所有的账户都被转换成了相应的存储格式。因此升级的代价仍然较高,但以太坊的运行,随时间推移,其设计的复杂性带来代价越来越昂贵,需要从升级方案和以太坊目前的弊端作出一个权衡。

[1]https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture

[2]https://medium.com/@gballet/structure-of-a-binary-state-tree-part-1-48c587836d2f

[3]Zhang W. Constructing blockchain world state merkle patricia trie subtree: U.S. Patent Application 16/908,502[P]. 2020-10-8.

Author image

About Kang Gao

Blockchain Developer & Researcher