CN119520066A 一种读取状态数据时提供完整性保障的方法、实现恢复状态索引的方法和计算机设备 （蚂蚁区块链科技(上海)有限公司）

一种读取状态数据时提供完整性保障的方一种读取状态数据时提供完整性保障的方从持久化存储介质读取状态数据至内存的过程本结束元信息包含区块的版本号和对应区块的状态数据写入持久化存储介质的操作标示的范2从持久化存储介质读取状态数据至内存的过程中，读取版本号对应基于所述版本结束元信息中的版本号和操作标示范围过滤所述读取版本号对应的状2.如权利要求1所述的方法，所述基于所述版本结束元信息中的版本号和操作标示范将操作标示在所述版本结束元信息中操作标示范围内的所述读取的版本号对应的状根据树结构的构建规则，基于过滤的所述读取版本号对应的状态数据生成所述状态根据树结构的构建规则，基于过滤的所述读取版本号对应的状态数量页对应一个或多个内存页，包含相对于之前相邻的基础页/增量页发生变化的一个或多基于所述版本结束元信息中包含的对应版本树结构的根hash验证所述恢复的树结构34[0006]基于所述版本结束元信息中的版本号和操作标示范围过滤所述读取版本号对应[0007]一种基于所述读取状态数据时提供完整性保障的方法实56[0055]区块链一般被划分为三种类型：公有链(PublicBlockchain)，私有链(Private7[0061]以Solidity语言为例，用其编写的合约与面向对象编程语言中的类(Class)很相[0068]functionget到以太坊网络后，节点1的EVM可以执行这个交易并生成对应的合约实例。图中2中交易的8尔树算法对每个交易都计算一个Hash值，然后两两连接再次计算Hash，一直到最顶层的[0083]以太坊MPT树的数据结构包括状态树(statetrie)。状态树中包含以太坊网络中境中以代码形式定义的能够自动执行条款的合storagetrie根节点的hash值即存储于上述storageroot中，从而将该合约的所有状态通值的key_value映射。从storagetrie树的根节点到叶子节点中的部分信息顺序排布后用区块哈希previous_Hash(图中的PrevHash)，随机数Nonce(在一些区块链系统中这个区块号BlockNum，状态根哈希State_Root，交易根哈希Transaction_Root，收据根哈希[0086]图4是一个区块链数据存储的结构示意图。仍以以太坊为state_root是当前区块中所有账户的状态组成的MPT树的根的哈希值，即指向state_root的为一颗MPT形式的状态树statetrie。这个MPT树的根节点一般为一个扩展节点(ExtensionNode)或一个分支节点(BranchNode)，state_root中存储的一般为这个根节9节点中的一部分值按照顺序串联起来可以构成账户地址并作为key，叶子节点中存储的账户信息为这个账户地址对应的value，这样，构成了key_value键值对。这个key也可以是sha3(Address)后取一部分,户信息一般都位于一个单独的叶子节点(LeafNode)中。从根节点的ExtensionNode/BranchNode。对于BranchNode，其最多可以有16个孩子节点，其中可能包括ExtensionMPT形式的树，其中存储了合约执行涉及的状态变量(statevariable)的数据。这个可以是合约中的状态变量声明的位置(从0开始计数的值)经过一定规则处理后得到的结果，例如是sha3(状态变量声明的位置)，或者是sha3(合约名称+状态变量声明的位置)。的路径上存储的一部分数据连起来构成key，叶子节点中存储value。前面提到，这个[0090]例如图4中的stateTrie的LeafNodeAccountP，该账户是一个合约账户，其StorageRoot锁定了该合约存储中的所有状态。这些状态组织为MPT树，树形结构如该StorageRoot链接的Storagetrie。这个链接的Storagetrie中，以LeafNodeStateVariableN为例，例如为前述合约代码示例的storedData的值，则其key为sha3则LeafNodeStateVariableC这个叶子节点中即存储nonce＝20，balance＝4550。而[0093]如图5的示例中所示，上一级的MPT结构中，对于叶子节点A1，通过根节点A8(ExtensionNode)中sharednibble的a7—中间节点A7(BranchNode)的槽位1—叶子节点sharednibble的a7—中间节点A7(BranchNode)的槽位7—节点A6(ExtensionNode)中sharednibbles的d3—中间节点A5(BranchNode)中的槽位3_叶子节点A2中key_end的7，顺序组合起来构成该叶子节点的key，即为a77d337，在该叶子节点中存储Balance=的a7—中间节点A7(BranchNode)的槽位f—叶子节点A3中key_end的9365，顺序组合起来对于叶子节点A4，通过根节点A8(ExtensionNode)中sharednibble的a7—中间节点A7(BranchNode)的槽位7—节点A6(ExtensionNode)中sharednibbles的d3—中间节点A5(BranchNode)中的槽位9_叶子节点A4中key_end的7，顺序组合起来构成该叶子节点的[0094]如图5的示例中所示，下一级的MPT结构中，对于叶子节点A11，通过根节点A10 根节点A10(BranchNode)中的槽位7—叶子节点A12中key_end的c25988，顺序组合起来构定义的B类型数字资产归属于李四的份额为50，即李四的B类资产的余额为50。对于叶子节点A15，通过根节点A10(BranchNode)中的槽位f—中间节点A13(ExtensionNode)中sharednibble的a—中间节点A14(BranchNode)的槽位6—叶子节点A15中key_end的be33，顺序组合起来构成该叶子节点的key，即为fa6be33，在该叶子节点中存储A13(ExtensionNode)中sharednibble的a—中间节点A14(BranchNode)的槽位9—叶子sharednibbles(共享的半字节)的ExtensionNode，用1表示包含奇数个sharednibble(s)的ExtensionNode，用2表示包含偶数个nibbles的LeafNode，用3表示包含奇数个为多中心化)的分布式账本。这样的区块链系统需POS)、委任权益证明(DelegatedProofofStake，DPOS)、实用拜占庭容错(Practical涉及合约的交易，执行模块可以引入虚拟机来执行智能合约的代码，如以太坊虚拟机而将共识结果的一个确定性的交易集合输出至执行模块。执行模块通过执行普通转账交共识模块和执行模块的功能实现一般需要CPU、内存的参与。存储模块可以包括构建树模树模块用于基于执行模块传入的状态k_v构建树(例如是MPT树)，如前述的statetrie和模块生成的树的叶子节点k_v写入状态数据库模块的过程中由于断电等情形造成的数据丢子节点实现对状态key的字典序索引。这些树节点按某种规则编码为Key、其内容编码为建树模块生成的树节点k_v写入状态数据库模块的过程中由于断电等情形造成的数据丢数据可以写入(flush)到磁盘中。为了避免写MemTable的操作对flush造成堵塞，这个生成一个新的MemTable来接收新传入的树节点k_v。这个新的MemTable可以提供并发读写能会达到256MB。进而，这个MemTable转化为ImmutableMemTable，并可以将ImmutableMemTable中的数据写入(flush，这里指内存中的数据写入到磁盘的操作)到磁盘中。具体SST11的k的最小值＜左边SST11的k的最大值＜中间SST12的k的最小值＜中间SST12的k的最大[0109]Level0中的1个SST内的k_v可以按照k的大小关系排序，多个SST之间k可以没有效的和可行的；当然，也可以不按照k值大小来排序，这里并不排斥。以排序为例，当MemTable的容量达到256MB时，可能其内存储的是包括多个区块对应多个k_v，这个0中同一SST中由不同ImmutableMemTable写入的k_v集合之间一般是没有大小排序的，不围可能有交叉/重合。同样的，由于Level0中的一个SST中所写入的k_v可以是多次因此Level0中的每个SST中存储的多个k_v之间一般也没有特定顺序，Level0中各SST之的各SST中的k_v和Level1内部分或所有SST的k_v可以先转入到内存中，在内存中完成排个SST，左边SST的k的最小值＜左边SST的k的最大值＜右边SST的k的最小值＜右边SST的k[0111]在compaction的过程中Level0内的各SST中的k_v和Level1内部分SST的k_v可述例子中，Level1中包括3个SST，SST11中key的范围是10b43c032a46～2018df9326a7，SST12中key的范围是21a514c0a7e1～284a5df3fca7，SST13中key的范围是3a5e55ac3fe1~400a51ef1405。例如Level0内的各SST中key的范围为18c49a405e32～24d35f39ab56。可新的数据存储于Level0，...最旧的数据存储于最底层Level内的SST中。此外，通过的后半部分查找(若第一次比较就发现两值相等则直接返回当前值所在的位置)。以此类字段指明调用的函数和输入的参数。假设合约D中被调用的函数的逻辑包括判断合约中的开始匹配后，从匹配的位置读取下一层树节点(可以是InternalNode或LeafNode，以模块的文件中查找。具体的，可以优先Level0中的SST内查找，如果还找不到就继续在的状态地址key值剩余的部分字段，匹配处的hash值作为下一次查找中间节点或叶子节点此，可能需要从状态数据库模块中读取至内存中操作。可以首先在状态数据库模块的码(反序列化)得到其中的内容。具体的，例如首先在level0的sst文件逐个查找，如果步在Level1内根据中间节点/叶子节点的hash值做二分查找，如果没有找到则在Level2的访问(大于M是因为最坏情况下对Level脏数据(dirtydata)。脏数据通常是指已经被写入MemTable但尚未被写入持久性存储(如SSTable)的数据。脏数据可以在前述flush过程中写入磁盘。状态数据库模块进而将MemTable中包括所述树节点k‑v在内的一些k‑v写入到磁盘的SST文件中。一旦MemTable被子节点中可以包括所述状态数据的内容或所述状态数据在持久化存储介质中数据文件内[0128]存储模块中包括构建树模块。构建树模块在内存中构建有世界状态的树形结启动加载的情况与此类似。由于内存的容量一般是有限的，因此一般采用LRU(Least[0129]对于要查找的状态key，如果构建树模块的内存中具有该状态key对应的叶子节利用其包括的location字段，其内容例如为图10中A11这个叶子节点中的location为<2，hash锁定到了区块头的stateroot字段中。假设该表中的k_v对存储于底层的状态数据库sharednibble(s)字段(对于ExtensionNode)或槽位(对于BranchNode)从头开始匹配后，从匹配的位置读取下一层树节点的hash，进而，优先在构建树模块的内存中查找该读取的状态地址key值剩余的部分字段，匹配处的hash值作为下一次查找中间节点或叶子1内根据中间节点/叶子节点的hash值做二分查找，如果没有找到则在Level2内做二分查[0137]S930：将所述位置索引指向的持久化存储介质中所述数据文件位置的value值加value值加载到内存并读取其中的状态数据，即将数据文件中的文件2中从起始位置第据文件的位置例如表2中H(11)对应内容中的location(2,750,210)，H(12)对应内容中的[0142]上述结合图10说明了图9方法实施例的具体过程。图10中仍然是两级MPT树的结仍然可以采用两级树的结构，上一级树中的叶子节点可以直接将定位到底数据文件中对应位置的内容加载进内存，这样也避免了在多个Level的SST中读取大量的文件并加载进内存所带来的读放大问题。同样作为上一级树的叶子节可能存在于一层树结构底层的不同叶子节点中，而不会再聚集于其所属的合约账户之下。据库中key是0x9的树节点(key为0x9的树节点的value中的h(C5D9)可以用于与父节点中槽可以根据状态key的最后一位6匹配到数据库中key是0x6的树节点(key为0x6的树节点的到数据库中匹配到key是0x52d的树节点，且其value中的H(C5)与根节点中槽位5上的hash读取大量的文件并加载进内存所带来的读放大问题。这也避免了叶子节点的k_v一并存储StateRoot下的两级Merkle树的根节点、中间节点对N号块中没有发生改变的状态变量的点以及与之相关的中间节点和中间节点之外，其它并未发生改变的叶子节点及中间节点，于之前区块中并未发生改变的叶子节点及中间节点，在N+1号块中均引用上一次更新为该[0176]这里仍以N+1号版本中同一合约存储中的状态相对于N号版本发生改变来做简便设该合约状态中的其它状态在前后两个版本中并未发生改变，则发生改变的45在N+1号版版本)中的叶子节点和/或中间节点，从而在N+1号版本中构造一棵该合约存储的新MPT树，除了创建一条从45到Storageroot的新路径外，N+1号版本的Storageroot通过hash索引[0184]其中，所述叶子节点中可以是采用前述数据文件的形式，也可以是采用前述的久化存储介质中数据文件内的位置索引以及状态value内容的述内存页用于表示所述逻辑页中对应的全部树逻辑页维护的树节点的内容，根据连续的版本更新，按生成/修改行为生成基础页和增量DeltaPage也可以作为树的磁盘持久化的最[0188]需要说明的是，这里的BasePage是对整个LogicalPage内容的检查点(checkpoint)，其可以包含LogicalPage的当时的全量内容，如所有包含的树节点信息。假设修改达到预定次数5，则可以将N+5号版本中的值a＝20以及b＝8和c＝3作为这个当BasePage和DeltaPage占用内存达到预定量时将BasePage和DeltaPage批量做磁盘持久化，从而避免每次修改都持久化所有脏数据，持续占用内存和CPU资源。所述BasePage和LRU)策略。这样，MemoryPage如果被淘汰，读取对应BasePage和DeltaPage，重放出版本可以直接根据通过内存页获得，对于历史版本读时可以读取BasePage和关联的若干前所述，可以是按照树结构的节点关联关系，将上、下相邻的若干个树节点聚合为一个hash值。而且，所述状态的key还需要设计，特别是针对所述LogicalPage和与之对应的MemoryPage/BasePage/DeltaP[0199]其中，所述叶子节点中可以是采用前述数据文件的形式，也可以是采用前述的久化存储介质中数据文件内的位置索引以及状态value内容的样，每个区块不仅包含了交易信息，还通过状态根保存了执行这些交易后的全局状态的所述页标识包括所述逻辑页中上层树节点的字典序[0207]所述叶子节点中还可以包括状态value内容的hash值(valuehash)和key_end字叶子节点中的内容计算叶子节点的hash值，包括根据叶子节点中状态value内容的hash值和所述key_full字段计算，但不包括所述状态value在持久化存储介质中数据文件内的位该LogicalPage的PageID可以设置为上层的树节点的NodeID。这些页ID是从根节点到该LogicalPage(也即内存页)中上层树节点的字典序内容，即从根对于之前相邻的基础页/增量页/版本发生变化的一个或多个连续版本内存页中的树节点，对应一个或多个内存页，包含相对于之前相邻的基础页/增量页发生变化的一个或多个连因此一个增量页的版本可以是与其对应的一个或多个内存页中[0216]上述方案，一种Merkle状态数据字典树的多版本Page切分方案，将树切换为LogicalPage，树和LogicalPage都维护version(如区块号)，内部管理MemoryPage/BasePage/DeltaPage，BasePage/DeltaPage按version维护内存结构和文件持久化，通过page聚合减少整体的写放大的同时，利用version有序特性，避免page落盘后的久化存储介质的数据文件中，所述叶子节点中包括所述状态value在持久化存储介质中数[0220]对于接收到的状态key和版本，可以按照字典序顺序匹配内存页的页标识中的版收到的状态key在内存页中进一步匹配下层间节点共同构成一个LogicalPage构成的内存页可以匹配到(0xd2345167890ab前5位，即[0223]具体的，例如在内存中没有查找到版本相同且匹配剩余则可以在持久化存储介质中根据所述页标识查找匹配剩余的字典序内容的对应基础页和本为18的DeltaPage1中可以包括版本为18的树节点和版本为19的树节点，版本为20的DeltaPage2中可以包括版本为20的树节点和版本为21的树节点，则可以加载版本不大于在版本为17的BasePage1、版本为18的DeltaPage1、版本为20的DeltaPage2和版本为22的合条件的基础页的版本是17，并加载所述BasePage1的版本17之后至不小于所述读取的版本20的最小版本20、页ID一致且页类型为增量页的版本为18的DeltaPage1和版本为20的版本为17的BasePage1的基础上，按照版本为18的DeltaPage1→版本为20的DeltaPage2这[0232]之所以需要从基础页回放到增量页从而得到内存页，是由于区块链的去信任特介绍增量页的版本是与其对应的多个内存页中最之后至不小于所述读取的版本的最小版本、页ID一致且页类型为增量页的增量页至内存，本为19的DeltaPage1中可以包括版本为18的树节点和版本为19的树节点，版本为21的DeltaPage2中可以包括版本为20的树节点和版本为21的树节点，则可以加载版本不大于的基础页的版本是17，并加载所述BasePage1的版本17之后至不小于所述读取的版本20的最小版本21、页ID一致且页类型为增量页的版本为19的DeltaPage1和版本为21的版本为17的BasePage1的基础上，按照版本为19的DeltaPage1→版本为21的DeltaPage2这增量页，即回放到加载的版本为19的DeltaPage1后，在按序回放到加载的最大版本21的子节点中包含的位置索引，所述位置索引指向所述持久化存储介质中数据文件内的位置，进而可以将所述位置索引指向的持久化存储介质中所述数据文件位置的value值加载到内[0238]前述提到，区块链的本质是一系列通过哈希关联的数据块(区块)组成的链式结的某个区块中更新的，且一直延续到当前区块没有改变。这与以太坊类似，这也称为增加了系统的复杂性。通常的操作流程是先更新currentDB，然后生成二进制日志[0240]另一方面，某些区块链实现采用了只保留currentDB而不维护historyDB的方括所述状态value在持久化存储介质中数据文件内的位所述数据库中加载所述基础页的版本之后至不小于所述恢复版本的最小版本且页类型为申请的方案，从持久化存储介质中加载当前最新版本区块对应的基础页和增量页至内存，达到目标状态的方案外，还可以是从指定的历史版本的状态根所锁定的MPT树的根节点开文件位置的value值加载到内存并读取其[0262]如前所述的一个例子中，所述叶子节点中可以包括状态value内容的hash值[0263]所述将加载的基础页和增量页按照页类型和版本顺序回放得到所述恢复版本的这里这个符合条件的基础页的版本是17，并加载所述BasePage1的版本17之后至不小于所是将加载的基础页和增量页按照页类型和版本顺序回放得到内存页。仍然按照上述例子，加载的基础页是版本为17的BasePage1，加载的增量页包括版本为19的DeltaPage1和版本版本为19的DeltaPage1→版本为21的DeltaPage2这样的顺序回放所述增量页，得到内存序回放所述页至小于所述读取的版本的最大版本的增量页，即回放到加载的版本为19的节点在左侧LogicalPage中位于版本号为17的DeltaPage中，而在右侧LogicalPage中则位[0266]此外，本申请提供的实施例中，LogicalPage的具体设计可以采用如下方式：将作为这个逻辑页中的根的中间节点和多个作为这个根的孩子节点的中间节点。例如，1个InternalPage中包含1个作为这个LogicalPage中的根的InternalNode和至多16个作为这及至少1个中间节点以构成的一颗子树。在构成一颗完整树结构的前提下，上述任一InternalNode的至少一个slot不为空。典型的例如附图18中C5这1个InternalNode和其下C5D14构成一颗子树,这时C5这个InternalNode的3个slot不为空，即slot1存储C5D1这个具体有几个slot不为空以及哪个slot不为空取决于其所连接的下层InternalNode的数量ID。该方案在数据库中可以根据要查找的状态key和版本在磁盘中根据页标识匹配基础页淘汰，读取对应BasePage和DeltaPage，可以重放出MemoryPage。读取对应BasePage和的位置，如磁盘块号、起始位置以及持续长度，从而可以实现在磁盘中定位该BasePage/[0270]磁盘上存储的索引文件与BasePage和DeltaPage如图21中所示。特别的是，一个即该BasePage的PageID。而一个DeltaPage可以是将多次连续对MemoryPage的修改聚合为[0271]在接收到读取的状态key和版本后，例如存储模块接收到读取的状态key和版本的版本分别为25和27，即存在25，假设PageID也匹配，这样，本次查找命中，且命中的全部具备一个MemoryPage的全量树节点内容，因此可以以该版本为24、PageID匹配的配的BaseType以及该版本为25、PageID匹配的DeltaType，按版本顺序回放该版本为24、照版本+页类型+PageID进行遍历或进行二分查找。如果找到匹配版本27的若干相邻条目，配的BaseType以及该版本为25、27的PageID匹配的DeltaType，按版本顺序回放该版本为所述版本和页标识在基础页/增量页的索引文件中查找到匹配的增量页，则递归的执行以找过程体现出，如果根据所述版本和页标识在基础页/增量页的索引文件中没有查找到匹[0277]上述查找过程中，如果相符的条目中PageType为DeltaPage，说明恢复该MemoryPage的部分增量的树节点内容在该DeltaPage已经具备，但还需要可能存在的之前[0289]如果根据所述版本和页标识在基础页/增量页的索引文件中查找到匹配的增量[0290]如果根据所述版本和页标识在基础页/增量页的索引文件中没有查找到匹配的增的前驱的基础页/增量页条目，而是在首先查找到的增量页条目中读取其存储的前驱基础[0295]如图22中所示，例如查找的是指向B5(PageID的细节这里忽略)的版本为28的在磁盘中找到DeltaPage27。同样的，由于DeltaPage25存储了它的前驱DeltaPage，即如前所述，找到该BaseType类型的文件后，由于该BasePage文件已经全部具备一个进而，可以加载该版本为24PageID匹配的BaseType以及该版本为25、27的PageID匹配的DeltaType，按版本顺序回放该版本为24、PageID匹配的BaseType以及该版本为25、27的[0297]为了避免对于每个要查找的版本和PageID都在索引中按照版本和PageID进行匹[0303]S238：根据查找到的基础页/增量页的版本联合页ID在索引中确定对应数据文件其存储的前驱基础页/增量页的版本并按照查找到的版本和页ID在索引文件中查找，直至[0307]如图23中所示，例如查找的是指向B5(PageID的细节这里忽略)的版本为27的其存储的前驱基础页/增量页的版本并按照查找到的版本和页ID在索引文件中查找，直至[0310]如图23中所示，例如查找的是指向B5(PageID的细节这里忽略)的版本为28的里递减版本后为28，根据递减后的版本28和页ID在所述索引文件中查找对应的增量页条设置有前一前驱基础页/增量页的版本，即DeltaPage27这个条目中存储了它的前驱的条目中设置其中包含的树节点的子节点所在这样，可以在索引中设置该页中的版本为26、27的树节点对应的子节点所在下一层B5层中的BasePage24和DeltaPag位于下层MemoryPageB5层中的Base的版本26和页ID在所述索引文件中查找MemoryPageB4层对应的增量页，可以找到述索引文件的增量页条目中可以设置有前一前驱增[0331]S266：一方面根据查找到的增量页条目中树节点记录的子节点所在基础页/增量页的版本在索引文件中查找下层基础页/增量页条目，另一方面递归的在查找到的下层增量页条目中读取其前驱基础页/增量页的版本并按照查找到的版本和页ID在索引文件中查系，可能涉及先在MemoryPageB4的BasePage和DeltaPage中查找，进而在下层的基础页/增量页条目。这里对于MemoryPageB4这一层中版本为27的树节点，其存在于以根据该版本26和页ID在所述索引文件中查找对应的增量页条目。如前所述，DeltaPage目中树节点记录的子节点所在基础页/增量页的版本，这里是MemoryPageB5这一层中的可以递归的在查找到的下层增量页条目中读取其前驱基础页/增量页的版本并按照查找到的版本和页ID在索引文件中查找，从而找到DeltaPage27和BasePage24查找到匹配的增量页。由于索引文件的增量页条目中设置树节点的子节点所在基础页/增在所述索引文件的增量页条目中设置有前一前驱基础页/增量页的版本，因此可以在索引取其前驱基础页/增量页的版本并按照查找到的版本和页ID在索引文件中查找，从而找到不同点在于所述基础页/增量页的数据文件中设置有树节点的子节点所在基础页/增量页其存储的树节点的子节点所在基础页/增量页的版本，并基于所述查找到的版本和页ID在的版本26和页ID在所述索引文件中查找MemoryPageB4层对应的增量页，可以找到录的树节点的子节点所在基础页/增量页的版本在索引文件中查找下层基础页/增量页条目，另一方面递归的在查找到的下层增量页条目中读取其前驱基础页/增量页的版本并按系，可能涉及先在MemoryPageB4的BasePage和DeltaPage中查找，进而在下层的基础页/增量页条目。这里对于MemoryPageB4这一层中版本为27的树节点，其存在于以根据该版本26和页ID在所述索引文件中查找对应的增量页条目。如前所述，DeltaPage础页/增量页条目对应基础页/增量页数据文件中记录的树节点的子节点所在基础页/增量页的版本在索引文件中查找下层基础页/增量页条目，这里基础页/增量页条目对应基础页/增量页数据文件中包括版本为26的树节点和版本27的树节点，数据文件中记录了版本节点对应下层基础页的版本为24。这样，找到了下层MemoryPageB5这一层中的BasePage的在查找到的下层增量页条目中读取其前驱基础页/增量页的版本并按照查找到的版本和查找到匹配的增量页。由于基础页/增量页的数据文件中设置有树节点的子节点所在基础件中记录的树节点的子节点所在基础页/增量页的版本在索引文件中查找下层基础页/增在所述索引文件的增量页条目中设置有前一前驱基础页/增量页的版本，因此可以在索引取其前驱基础页/增量页的版本并按照查找到的版本和页ID在索引文件中查找，从而找到增量页的数据文件位置。基于此，本申请还提供一种查找基础页/增量页的方法实施例包其存储的树节点的子节点所在基础页/增量页的数据文件位置，并基于所述读取到的数据增量页的数据文件位置，在所述索引文件的增量页条目中可以设置有前一前驱基础页/增取的数据文件中获得所述树节点的子节点所在基础页/增量页的数据文件位置，从而查找坊社区一直在寻找平衡存储效率和功能完整会保留最近的128个版本写入数据产生的snapshot，遍历RocksDB(前述LevelDB的变种)中据划分的LogicalPage结构对应MemoryPage。具体的，LogicalPage内部可以维护一个虑裁剪后能够恢复所述裁剪版本之后的特定版本，因此需要确定不同LogicalPage实际裁类似前述，不再赘述。特别的，前述本申请为了加速查找，提供的方案包括对BasePage、裁剪掉指定版本之前的多少部分，需要考虑裁剪后能够恢复所述裁剪版本之后的特定版[0382]S312的具体实现可以是根据所述版本在索引文件中查找每一逻辑页中不大于所页，则可以递归的在查找到的增量页中读取其存储的前驱的基础页/增量页的数据文件位[0384]另外，也可以在索引的增量页条目中设置有前一前驱基础页/增量页的版本。这以递归的在查找到的增量页条目中读取其存储的前驱基础页/增量页的版本并按照查找到后的版本在所述索引文件中查找对应的基础页/增量页条目，直至查找到版本匹配的基础页/增量页条目。如果递归的执行上述操作的过程中，首先查找到的是增量页而不是基础页，则可以递归的在查找到的增量页条目中读取其存储的前驱基础页/增量页的版本并按[0393]这样，可以由S314，将每一LogicalPage中确定的最大版本基础页作为安全裁剪[0396]对于LeafPageB6，裁剪掉版本25之前的BasePage和DeltaPage，而25及之后的[0399]对于LeafPageB9，裁剪掉版本23之前的BasePage和DeltaPage，而23及之后的[0405]S324：根据查找到的基础页/增量页条目中树节点记录的子节点所在基础页的版[0407]从树结构中的根节点(也即根节点所在的LogicalPage)自顶向下的查找每一子LogicalPage，从而可以查找到每一子LogicalPage对应在持久化存储介质上的BasePage。具体到这里的实施例，可以是在索引文件中从树结构中的根节点(也即根节点所在的LogicalPage)索引文件自顶向下的查找每一子LogicalPage在索引条目中的版本，从而可以在索引文件中进一步查找到每一子LogicalPage的索引文件，进而查找到对应在持久化[0418]上述S310～S314以及S320～S326和S330～S336的过程，是以LogicalPage为单位类型+页ID)顺序排列的BasePage和DeltaPage数据文件，可能会在连续的数据文件中进行角形表示，且该图中画出了上下两层LogicalPage之间的连线以表示上一层基础页对应的件的基础页/增量页的条目中设置有树节点的子节点所在下层基础页的版本,所述方法包逻辑页中任一版本的基础页/增量页，即保留的数据文件中仍然存在指定版本到安全裁剪所述安全裁剪点之前的该逻辑页中任一版本的基础页/增量页数[0441]例如图29所示。图左侧为剪裁前的世界状态，图右侧为经S372和S374处理后的版本分别为101和150。版本为101的DeltaPage中包含的版本包括101～149，版本为150的包含版本为106～149的Internal[0443]类似的，InternalPageC2中，包含的BasePage的版本为80，其后连续的两个本105。当指定的剪裁版本为105时，图29右侧的经S372和S374处理后的InternalPageC2版本为106～149的Internal[0444]类似的，InternalPageC3中，包含的BasePage的版本为90，其后连续的两个裁前版本为90的BasePage和版本为91的DeltaPage中版本为91～99的InternalNode以及版的版本分别为51和90。版本为51的DeltaPage中包含的版本包括51～89，版本为90的50的BasePage和版本为51的DeltaPage中版本为51～89的LeafNode(或还包括InternalNode)以及版本为90的DeltaPage中版本为90～105的LeafNode(或还包括版本号为106的DeltaPage，其中包含版本为106～119的LeafNode(或还包括的版本分别为61和100。版本为61的DeltaPage中包含的版本包括61～99，版本为100的60的BasePage和版本为61的DeltaPage中版本为61～99的LeafNode(或还包括InternalNode)以及版本为100的DeltaPage中版本为100～105的LeafNode(或还包括版本号为106的DeltaPage，其中包含版本为106～119的LeafNode(或还包括的版本分别为61和90。版本为61的DeltaPage中包含的版本包括61～89，版本为90的60的BasePage和版本为61的DeltaPage中版本为61～89的LeafNode(或还包括InternalNode)以及版本为90的DeltaPage中版本为90～105的LeafNode(或还包括版本号为106的DeltaPage，其中包含版本为106～109的LeafNode(或还包括于剪裁后已经不存在对应的数据文件，而是如上重新生成的版本为105的BasePage数据文101的DeltaPage更新为106的D[0452]可以在索引文件的基础页/增量页的条目中设置树节点的子节点所在下层基础页的版本,则所述根据所述指定版本查找该逻辑页中不大于所述指定版本的最大版本第一基页条目中树节点记录的子节点所在下层基础页的版本在索引文件中查找所述下层基础页[0454]可以在基础页/增量页的数据文件中设置树节点的子节点所在下层基础页的版本,则所述根据所述指定版本查找该逻辑页中不大于所述指定版本的最大版本第一基础页后，在查找到的基础页/增量页数据文件中读取其存储的树节点的子节点所在下层基础页[0457]对于任一版本的增量页在其数据文件中设置有前一前驱版本的数据文件存储位量页中读取其存储的前驱的基础页/增量页的数据文件位置，直至查找到基础页的数据文[0459]对于在索引的增量页条目中设置有前一前驱基础页/增量页的版本，则根据所述[0460]递归的在查找到的增量页条目中读取其存储的前驱基础页/增量页的版本并按照第二基础页作为安全裁剪点并删除该安全裁剪点之前的该逻辑页中任一版本的基础页/增文件中的key查找索引文件，如果在索引文件没有查找到该key，说明索引对该key已经失存储在状态数据文件中。具体的，可以在索引中MemoryPageB6这个LeafPage的DeltaPage26中记录版本为26的LeafNode的NodeID及对应的数据所存储在数据文件中的位10左下角的数据文件所示，假设每个文件的大小为1024MB，索引的逻辑地址范围为0KB~+NodeID对应的Location1的数据，索引中LeafPageC4的版本为31的DeltaPage中49+NodeID对应的Location7的数据，索引中LeafPageC4的版本为50的BasePage中50+NodeID对应的Location7的数据，索引中LeafPageC4的版本为50的BasePage中50+NodeID对应的分包含LeafPageC4的数据文件，省略的数据文件中可能并不包含LeafPageC4的数据文[0465]在状态索引文件(IndexFile)中，对于LeafPageC4，在不同版本的BasePage/DeltaPage中可以包含不同版本+树节点对应的数据文件位置(Location)。如图30中所示，DeltaPage可以包含若干版本+树节点与Location其中，一个InternalPage中包含至少两层InternalNode；一个LeafPage中包含至少一个LeafNode，或还包括至少一层InternalNode。InternalPage、LeafPage中，可以包含[0469]对应于图30左侧简化的31版本的这个LeafPageC4的DeltaPage，右侧IndexFile中包含的版本+树节点与Location的对应关系，版本的范围是31～49，即小于其后的树节点与Location的对应关系，版本的范围是51～89。对于90版本的这个LeafPageC4的中表示所述逻辑页当前版本的内存页中对应的全部树节点的内容，也包含对树节点按生在之前版本发生生成/修改行为产生的对应关系，即之前的内存页中即存在。如图30右侧成/修改行为产生的对应关系，即之前的DeltaPage中即已不存在，因此，31版本的这个在当前版本的内存页中由于发生生成/修改行为而产生[0474]这里，可以对BasePage中由当前版本内存页中发生生成/修改行为产生的对应关系记录文件使用量。例如上述50版本的这个LeafPageC4的BasePage中也包含对应关系2，应关系中的Location也可以是指向DataFile中的其它数据文件中的效数据量在所在数据文件中的占比与1的差值设置为该如图所示的LogicalPageC4的31+DeltaPage+PageID的索引文件、50+BasePage+PageID的设LogicalPageC4的31+DeltaPage+PageID的索引文件中Location1和Location7对应的是数据文件1；并假设LogicalPageC4的50+BasePage+PageID的索引文件的FileUsage中Location12对应的是数据文件1，而不考虑不在FileUsage中的Location7，因为这个Location7并不是50+BasePage+PageID这个内存页中发生生成/修改行为产生的文件使用[0480]这里是以数据文件来统计，例如为了统计DataFile1，这里统计的Location1、[0494]上述对应关系3中，FileID与垃圾比达到阈值的数据文件为DataFile_target一[0495]上述对应关系4中，FileID与垃圾比达到阈值的数据文件为DataFile_target一[0503]将索引文件中对DataFile_target的Location引用更新成对新数据文件的[0505]对应于图31左侧简化的31版本的这个LeafPageC4的DeltaPage，右侧IndexFile中包含的版本+树节点与Location的对应关系，版本的范围是31～50，即包含其后的DeltaPage中49+NodeID对应的Location7的数据，索引中LeafPageC4的版本为50的DeltaPage中50+NodeID对应的Location12的数据，索引中LeafPageC4的版本为50的BasePage中50+NodeID对应的Location7的数据，索引中LeafPageC4的版本为50的BasePage中50+NodeID对应的Location前版本的DeltaPage中发生生成/修改行为产生的新的对应关系。如图31右侧IndexFile中[0510]其中，对应关系6是之前版本DeltaPage中发生生成/修改行为产生的新的对应关中L12对应的DF位置(L12表示Location12，DF表示DataFile)。而对应关系7也是前一将所述有效数据量在所在数据文件中的占比与1的差值设置为该数据文件的垃圾比；所述叶子页包含的叶子节点中包括所述状态数据在持久化存储介质中数据文件内的所述逻辑页当前版本的内存页中对应的全部树节点的内容，但不包含对树节点按生成/修一个索引文件中，即遍历到的一个叶子页的增量页中，包含前述提到的版本+NodeID→是说，叶子节点中可以记录完整的状态key。这样，叶子页的增量页中，包含状态key到[0530]上述对应关系3中，FileID与垃圾比达到阈值的数据文件为DataFile_target一[0531]上述对应关系4中，FileID与垃圾比达到阈值的数据文件为DataFile_target一[0539]将索引文件中对DataFile_target的Location引用更新成对新数据文件的以删除所述安全裁剪点之前的所述逻辑页中任一版本的基础页/增量页数据文件，即完成涉及对索引文件的裁剪和对数据文件的垃圾回收。前述提供的进行垃圾回收的方法实施[0549]S380～S382中或SS390～S392中，包括对索引文件的遍历和对Location中将对应的key加入到重写集合，这也意味着上述所说的垃圾回收后所述有效数据的的遍历和对Location中DataFile的引用信息与垃圾比达到阈值的数据文件的FileID是否32中所示LeafPageC4的31+DeltaPage+PageID这个索引文件中，记录包括如下的映射关[0553]例如对如图32中所示LeafPageC4的50+BasePage+PageID这个索引文件中，记录[0555]上述两个映射关系仅仅作为示例加以说明本申请方法实施例的实现过程。实际用信息与垃圾比达到阈值的数据文件的FileID也是一致，例如对LeafPageC4的31+DeltaPage+PageID这个索引文件中记录的映射关系还包括：31+NodeID→Location1和50+NodeID→Location12，以及对LeafPageC4的50+BasePage+PageID这个索引文件中记录的[0556]上述这些映射关系中，由于Location指向的DataFile1在垃圾回收过程中确定为垃圾比达到阈值的数据文件，因此需要将这些Location重新映射到新数据文件中的位置。[0557]仍然以图32中LeafPageC4的31+DeltaPage+PageID这个索引文件中记录的映射关系49+NodeID→Location7和LeafPageC4的50+BasePage+PageID这个索引文件中记录的[0559]这里的NodeID即上述49+NodeID→Location7和50+BasePage+Page是新生成的数据文件及其中的位置，如图32中所示为新数据文件350中的位置，例如是[0560]如图32中所示，对于垃圾回收前的蓝色箭头划线的源头映射数据和所指向的用RewritePage的容量，可以将NodeID也即状态key通过hash分桶的方式设置所在的是版本+NodeID→新数据文件位置的形式。由于可能存在多个不同版本的NodeID都重新映射到同一新数据文件位置的情形，因此这里的版本可以选择对应的原NodeID的最大版本，从而在RewritePage中指示该条重映射数据中的版本是重映射的原始NodeID的最大版本。例如，图32中LeafPageC4的31+DeltaPage+PageID这个索引文件中记录的映射关系49+NodeID→Location7和LeafPageC4的50+BasePage+PageID这个索引文件中记录的映射关系50+NodeID→Location7为例，RewritePage中是50+NodeID→Location5，则可以表示可以对RewritePage也设置版本，这样才能保持索引文件的版本有序性。例如，可以将RewritePage的版本设置为所包含的NodeID所对应的最大版本或最小版本。这样，[0569]经过上述S400和S420，在索引文件中建立了RewritePage与新数据文件之间的映以在MetaData中记录该失效的FileID——1和对应的重写页的I据清单(DatabaseMetadataManifest)。这个manifest不同于单个BasePage或DeltaPage[0588]S414：基于所述数据文件位置中的数据文件ID在所述基础页/增量页的元数据中据的版本+状态key时，对于RewritePage的ID中包含版本的情形，由于该版本指示了该RewritePage中的重映射关系所使用的最大版本，因此可以便于在索引文件中BasePage、前若干个bits相同的分在同一个分桶中，从而将该分桶中的重映射数据聚合在同一基于待查找的状态key查找RewritePage中的重映射关系。如果查找到对应的重映射关系，则可以进一步在查找到的重映射关系指向的新数据文件位置找到对应的状例如，在某些基于PoW(工作量证明)的区块链中，整个网络的安全性与算力的分布紧密相供的索引、数据分离架构下状态数据和状态索引的持续增长。对于持久化存储来说，创建的RewritePage包含版本的情形下，在索引文件中，RewritePage与BasePage、于前述BasePage、DeltaPage和数据文件持续增长的原因，可能在索引文件中生成或安装RewritePage的过程中，生成版本大于RewritePage的BasePage、DeltaPage及对应数据文移的结果。而生成新数据文件之外还可以通过另一独立线程在后台进行索引重建等工作，号大于(或还包括等于，这取决于索引文件中的排序规则)Rew效数据文件内的内容而需要由RewritePage来实现跳转的情形，从某一时机开始统一指向[0608]本申请提供一种收敛失效文件位置的方法实施例，过新数据文件的来源来获取对应的BasePage或DeltaPage的版本，从而获取对应的[0611]具体的，可以是在垃圾回收过程中记录生成新数据文件所基于的BasePage或DeltaPage版本信息，如在前述进行垃圾回收的过程中对索引文件的遍历从而加入到重写述获取的新数据文件中的状态key与其所在新数据文件位置的对应关系对于所述获取的最针对S430中获取的最大版本之前版本的基础页/增量页重建索引，而不包括所述最大版本据文件中的状态key与其所在新数据文件位置的对应关系生成最大版本之后版本的基础使得RewritePage之后版本的BasePage/DeltaPage中(如LeafPageC4中版本号为120的BasePage，其位于RewritePage的版本之后)，而相关的NodeID与Location的对应关系中Location指向的都是新数据文件(如图36中新数据文件350)或之后生成的数据文件(通过新数据文件的版本来指示)，而不存在指向失效数据文件的情况。而在收敛点之前，即RewritePage之前版本的BasePage/DeltaPage中，如果发生重映射，则都将重映射至该通过该RewritePage重映射的情况，通过Location或通过重映射之后的Location所指向的[0617]重写页可以实现在垃圾回收后对指向失效数据文件的索引文件中的映射关系进索引文件中查找基础页/增量页中相同状态[0622]由于重写页中包含了由原本指向oldLocation的状态key到newLocation的映射关[0623]在索引文件中查找重写页后，可以基于其中的重映射关系中的状态key在所述索[0626]如前所述的例子中，DeltaPage中可以包含对树节点按生成/修改行为产生的增应数据文件内容而产生位置并记录后，后续在没有发生数据变化的情况下，后续的止，因为再之前的BasePage/DeltaPage中即使相同的状态key所对应的位置也都与该[0627]S442：采用所述重写页中的新数据文件位置修正查找到的所述基础页/增量页中而是会将该治理任务挂在后台，待前台的数据查询/修改之类的流量降低到一定门限以下Log不断追加(而不是修改)的特点，核心思想是充分利用磁盘批量的顺序写远比随机写高[0633]具体的，底层存储例如可以写入k_v数据，写入内存中的MemTable文件中。写MemTable的操作对flush造成堵塞，这个MemTable转化为内存中不可更改的Immutablek_v。这个新的MemTable可以提供并发读写操作(如图中的NewMemTable)。存储引擎将转化为ImmutableMemTable的过程中,会对MemTable中的键值对数据按照键(key)进行排BasePage/DeltaPage可以作为磁盘持久化的最小单元，根据大小，可以是单个BasePage/且实现了在BasePage/DeltaPage内按照key的顺序排列。[0635]由于LS中的SST文件不要求分层，因此Compaction的过程是对整个数据集进行重写入Level1中，这个过程中涉及将Level0中的SST和Leve的过程来将Level1的数据写入Level2中，这个过程中涉及将Level1中的部分SST和[0636]需要说明的是，上述图37示出了LS架构中的SST和其中的BasePage/DeltaPage的DeltaPage以及索引文件的索引(即图37中磁盘内部左侧的索引)。后续主要以图38为例加以说明，本申请的改进方案大部分内容(除了分层和M[0637]所述LS或LSM架构中的sst可以设置连续的分段。每个分段中可以包括若干取决于生成BasePage/DeltaPage的版本情况。如果某个版本号下在某一LogicalPage并未些BasePage/DeltaPage可以按照版本排序。在BasePage/DeltaPage采用版本+PageType+的按照版本排序。在排序中，对于同版本的BasePage和DeltaPage，可以设定规则为所述状态value在持久化存储介质中数据文件内的位置Location，而这个Location是状态存中生成。后续，在当BasePage和DeltaPage占用内存达到预定量时将BasePage和DeltaPage批量做磁盘持久化，从而避免每次修改都持久化所有脏数据，持续占用内存和账交易或一个涉及合约的交易在执行后可能涉及多个状态的变化，即对应多个key_value将该合约执行产生的状态key_value发送至存储层。存储层可以基于这些状态生成Merkle中，树节点的叶子节点中可以不包含状态key_value，而是包含指向专门的数据文件位置状态key_value是同一区块中的交易所生成的，即对应相同的版本号，这里例如版本号版本号的版本结束元信息。所述版本结束元信息如图40中包括key42_value42之后的蓝色以作为状态value的索引，并将树结构的世界状态按照Page切分的方案，将树结构划分为可以在按照版本号将状态key_value批量写入磁盘的过程中，生成当前所写入区块对应版个request_sequence，其后紧跟的成功写入的状态key_value对应的request_sequence是其之前紧跟的request_sequence+1。如图40中所示，版本号data_version＝10的key10_key_value，且每个数据文件中还包含request_sequence，后一紧跟的状态数据文件中的递增的。这样，key10_value10所在的状态数据文件中的request_sequence＝39，key11_[0648]相应的，版本结束元信息中除了包含版本号，可以包含对应版本号的写入状态key_value中的request_sequence范围，例如用最小request_sequence(即图中min_request_sequence)和最大request_sequence(即图中max_request_sequence)来表示文件中的request_sequence＝39，key11_value11所在的状态数据文件中的request_sequence＝40，key12_value12所在的状态数据文件中的request_sequence＝41，...，request_sequence＝71来标写入持久化存储介质后，可以在key42_value42的状态数据文件之后写入对应版本号的版信息写入到所述持久化存储介质中紧随所述区块对应的状态数据之后，如图40中包含[0651]写入的版本结束元信息，可以表明写入到持久化存储介质中的状态key_value对可以以前次版本对应的完整状态数据整体再次写入，其中再次写入状态数据中的第一个，