Blockchain-based hierarchical data storage

Patent metadata

Field	Value
Publication number	US-11036720-B2
Application number	US-202016790605-A
Country	US
Kind code	B2
Filing date	Feb 13, 2020
Priority date	Jun 28, 2019
Publication date	Jun 15, 2021
Grant date	Jun 15, 2021

Abstract

Methods, systems, and apparatuses are disclosed for blockchain-based hierarchical data storage. One method includes determining, based on a blockchain stored in a database that includes multiple levels of storage, a block number interval that includes one or more block numbers associated with data nodes included in a state Merkle tree stored in a target data storage and to be migrated to a lower level of storage with lower storage cost in response to the data nodes meeting a data migration condition, each of the data nodes is associated with a block number of a block of the blockchain where the corresponding data node is last updated, and the data nodes in the state Merkle tree are in the form of key-value pairs (KVPs), each key of the KVPs comprises a node identifier (ID) and a block number associated with the corresponding data node.

First claim

What is claimed:

1. A blockchain-based hierarchical storage method comprising:
determining target data storage of a storage level in a database satisfies a data migration condition, wherein the database comprises multi-level storage, wherein the database is a Merkle tree that stores account state data of a blockchain in key-value pairs, and wherein each key of the key-value pairs comprises a node identifier (ID) of a data node and a block number;
responsive to determining the target data storage in the database satisfies the data migration condition, determining a block number interval, wherein the block number interval comprises two or more numbers representing two or more blocks of the blockchain that are to be migrated;
determining a migration threshold based on an endpoint of the block number interval, wherein the migration threshold is a block number of the blockchain;
traversing one or more key-value pairs of the target data storage to identify a target data node associated with a block number smaller than the migration threshold;
traversing the target data storage to determine that the target data storage comprises a second data node having the same node ID as that of the target data node, wherein the second data node comprises a block number greater than a block number of the target data node and smaller than the migration threshold; and
in response to determining that the target data storage comprises the second data node, migrating the target data node to a lower level of storage.

2. The method according to claim 1 , wherein determining the migration threshold comprises:
determining a right endpoint of the block number interval as the migration threshold if the block number interval is right-open; and
determining a sum of the right endpoint and a step size of one or more block numbers in the block number interval as the migration threshold if the block number interval is right-closed.

3. The method according to claim 1 , wherein determining whether the target data storage comprises the second data node further comprises:
identifying a plurality of data nodes that comprise a node ID equal to the node ID of the target data node and block numbers smaller than the migration threshold;
identifying, a data node of the plurality of data nodes that comprises a largest block number; and
determining whether the data node of the plurality of data nodes comprises a block number greater than the block number associated with the target data node.

4. The method according to claim 1 , further comprising:
determining a plurality of data nodes that are updated in a state Merkle tree associated with a latest block appended to the blockchain;
generating KVPs corresponding to the plurality of data nodes; and
storing the KVPs to a highest-level of data storage with highest storage cost in the database, wherein values of the KVPs are data content of corresponding data nodes.

5. The method according to claim 4 , wherein the state Merkle tree has a tree structure constructed based on a Merkle tree and a prefix tree, and wherein a node ID of a data node of the state Merkle tree is a prefix character corresponding to a path from a root node to the data node of the state Merkle tree.

6. The method according to claim 5 , wherein the state Merkle tree is a Merkle Patricia tree (MPT).

7. The method according to claim 1 , wherein the database is a LevelDB database.

8. The method according to claim 7 , wherein the database is a RocksDB database.

9. The method according to claim 1 , wherein storage with lower storage cost has lower read-write performance.

10. A computer-implemented system, comprising one or more computers, and one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform operations comprising:
determining target data storage of a storage level in a database satisfies a data migration condition, wherein the database comprises multi-level storage, wherein the database is a Merkle tree that stores account state data of a blockchain in key-value pairs, and wherein each key of the key-value pairs comprises a node identifier (ID) of a data node and a block number;
responsive to determining the target data storage in the database satisfies the data migration condition, determining a block number interval, wherein the block number interval comprises two or more numbers representing two or more blocks of the blockchain that are to be migrated;
determining a migration threshold based on an endpoint of the block number interval, wherein the migration threshold is a block number of the blockchain;
traversing one or more key-value pairs of the target data storage to identify a target data node associated with a block number smaller than the migration threshold;
traversing the target data storage to determine that the target data storage comprises a second data node having the same node ID as that of the target data node, wherein the second data node comprises a block number greater than a block number of the target data node and smaller than the migration threshold; and
in response to determining that the target data storage comprises the second data node, migrating the target data node to a lower level of storage.

11. The computer-implemented system according to claim 10 , wherein determining the migration threshold comprises:
determining a right endpoint of the block number interval as the migration threshold if the block number interval is right-open; and
determining a sum of the right endpoint and a step size of one or more block numbers in the block number interval as the migration threshold if the block number interval is right-closed.

12. The computer-implemented system according to claim 10 , wherein determining whether the target data storage comprises the second data node further comprises:
identifying a plurality of data nodes that comprise a node ID equal to the node ID of the target data node and block numbers smaller than the migration threshold;
identifying, a data node of the plurality of data nodes that comprises a largest block number; and
determining whether the data node of the plurality of data nodes comprises a block number greater than the block number associated with the target data node.

13. The computer-implemented system according to claim 10 , further comprising:
determining a plurality of data nodes that are updated in a state Merkle tree associated with a latest block appended to the blockchain;
generating KVPs corresponding to the plurality of data nodes; and
storing the KVPs to a highest-level of data storage with highest storage cost in the database, wherein values of the KVPs are data content of corresponding data nodes.

14. The computer-implemented system according to claim 13 , wherein the state Merkle tree has a tree structure constructed based on a Merkle tree and a prefix tree, and wherein a node ID of a data node of the state Merkle tree is a prefix character corresponding to a path from a root node to the data node of the state Merkle tree.

15. The computer-implemented system according to claim 14 , wherein the state Merkle tree is a Merkle Patricia tree (MPT).

16. The computer-implemented system according to claim 10 , wherein the database is a LevelDB database.

17. The computer-implemented system according to claim 16 , wherein the database is a RocksDB database.

18. The computer-implemented system according to claim 10 , whe

Assignees

• Advanced New Technologies Co Ltd

Inventors

• Lu Zhonghao
• Zhuo Haizhen
• Yu Benquan

Classifications

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title