Blockchain-based hierarchical data storage

Patent metadata

Field	Value
Publication number	US-11042518-B2
Application number	US-202017033340-A
Country	US
Kind code	B2
Filing date	Sep 25, 2020
Priority date	Jun 28, 2019
Publication date	Jun 22, 2021
Grant date	Jun 22, 2021

Abstract

Disclosed herein are methods, systems, and apparatus, including computer programs encoded on computer storage media, for blockchain-based hierarchical data storage. One of the methods 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 to be migrated to a lower level of storage in response to the data nodes meeting a data migration condition, wherein each of the data nodes is included in a state Merkle tree and is associated with a block number of a block of the blockchain where the corresponding data node was last updated, and the lower level of storage corresponds to a storage media with lower storage cost.

First claim

What is claimed:

1. A blockchain-based hierarchical data storage method comprising:
determining a storage amount of a first storage level of a database satisfies a storage threshold, wherein the database includes multiple levels of storage;
in response to determining the storage amount of the first storage level of the database satisfies the storage threshold, determining, based on a blockchain stored in the database, a block number interval that includes one or more block numbers associated with data nodes to be migrated to a lower level of storage, wherein:
each of the data nodes is included in a state Merkle tree and is associated with a block number of a block of the blockchain where a corresponding data node was last updated, and
the lower level of storage corresponds to a storage media with lower storage cost; determining a migration threshold, comprising:
determining a right endpoint of the block number interval as the migration threshold when the block number interval is right-open; and
determining a sum of the right endpoint and a step size of the one or more block numbers in the block number interval as the migration threshold when the block number interval is right-closed;

traversing a state Merkle tree corresponding to a target block to identify first one or more target data nodes associated with block numbers smaller than the migration threshold; changing the block numbers associated with the first one or more target data nodes to the migration threshold;
traversing one or more state Merkle trees corresponding to one or more blocks of the blockchain with the one or more block numbers in the block number interval to identify second one or more target data nodes associated with block numbers smaller than the migration threshold; and
migrating the second one or more target data nodes to the lower level of storage.

2. The method according to claim 1 , wherein the database is a key-value database, the data nodes included in the state Merkle tree are stored as key-value pairs (KVPs), keys of the KVPs are hash values of corresponding values of the KVPs, and values of the KVPs are data content of corresponding data nodes.

3. The method according to claim 1 , further comprising:
determining one or more data nodes updated in a state Merkle tree corresponding to a latest block of the blockchain; and
associating a block number of the latest block with the one or more data nodes.

4. The method according to claim 1 , wherein each of the one or more block numbers is stored in a block number field that is preserved in a corresponding data node.

5. The method according to claim 4 , wherein the block number field is preserved to identify a storage location of a value of the corresponding data node included in the state Merkle tree.

6. The method according to claim 1 , wherein the state Merkle tree has a tree structure constructed based on a Merkle tree and a prefix tree.

7. The method according to claim 1 , wherein the state Merkle tree is a Merkle Patricia Tree (MPT).

8. The method according to claim 1 , wherein the database is a LevelDB database or a RocksDB database.

9. The method according to claim 1 , wherein determining the storage amount of the first storage level of the database satisfies the storage threshold comprises determining the first storage level of the database has reached a maximum storage amount corresponding to a storage capacity of the first storage level.

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

11. 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 a storage amount of a first storage level of a database satisfies a storage threshold, wherein the database includes multiple levels of storage;
in response to determining the storage amount of the first storage level of the database satisfies the storage threshold, determining, based on a blockchain stored in the database, a block number interval that includes one or more block numbers associated with data nodes to be migrated to a lower level of storage, wherein:
each of the data nodes is included in a state Merkle tree and is associated with a block number of a block of the blockchain where a corresponding data node was last updated, and
the lower level of storage corresponds to a storage media with lower storage cost;

determining a migration threshold, comprising:
determining a right endpoint of the block number interval as the migration threshold when the block number interval is right-open; and
determining a sum of the right endpoint and a step size of the one or more block numbers in the block number interval as the migration threshold when the block number interval is right-closed;
traversing a state Merkle tree corresponding to a target block to identify first one or more target data nodes associated with block numbers smaller than the migration threshold; changing the block numbers associated with the first one or more target data nodes to the migration threshold;
traversing one or more state Merkle trees corresponding to one or more blocks of the blockchain with the one or more block numbers in the block number interval to identify second one or more target data nodes associated with block numbers smaller than the migration threshold; and
migrating the second one or more target data nodes to the lower level of storage.

12. The computer-implemented system according to claim 11 , wherein the database is a key-value database, the data nodes included in the state Merkle tree are stored as key-value pairs (KVPs), keys of the KVPs are hash values of corresponding values of the KVPs, and values of the KVPs are data content of corresponding data nodes.

13. The computer-implemented system according to claim 11 , further comprising:
determining one or more data nodes updated in a state Merkle tree corresponding to a latest block of the blockchain; and
associating a block number of the latest block with the one or more data nodes.

14. The computer-implemented system according to claim 11 , wherein each of the one or more block numbers is stored in a block number field that is preserved in a corresponding data node.

15. The computer-implemented system according to claim 14 , wherein the block number field is preserved to identify a storage location of a value of the corresponding data node included in the state Merkle tree.

16. The computer-implemented system according to claim 11 , wherein the state Merkle tree has a tree structure constructed based on a Merkle tree and a prefix tree.

17. The computer-implemented system according to claim 11 , wherein determining the storage amount of the first storage level of the database satisfies the storage threshold comprises determining the first storage level of the database has reached a maximum storage amount corresponding to a storage capacity of the first storage level.

18. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
determining a storage amount of a first storage level of a database satisfies a storage threshold, wherein the database includes multiple levels of storage;
in response to determining the storage amount of the first storage level of the database sat

Assignees

• Advanced New Technologies Co Ltd

Inventors

• Lu Zhonghao
• Yu Benquan
• Zhuo Haizhen

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• G06F16/137

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title

• H04L9/0637

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• G06F16/214 Primary

  Database migration support · CPC title

• G06F16/1824

  implemented using Network-attached Storage [NAS] architecture (distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097) · CPC title