Performing map iterations in a blockchain-based system
View Patent ↗Computer-implemented methods, systems, and apparatus are described for storing keys of multiple key-value pairs by a network node of a blockchain network. One method includes maintaining data representing a forest that stores multiple keys of the multiple key-value pairs that are stored in a map. The forest includes multiple trees, each tree includes respective storage nodes, and each storage node stores a subset of the multiple keys. The network node receives a request to add a key of a key-value pair into the forest. A first hash value of the key is computed using a first hash function. One of the multiple trees to store the key is determined based on the first hash value. The network node determines a target storage node of the one of the multiple trees to store the key, and stores the key in the target storage node.
1. A computer-implemented method comprising:
maintaining, by one or more processing devices, data representing a forest that stores a plurality of keys of a plurality of key-value pairs that are stored in a map, the map being stored in a consensus node of a blockchain network, the forest comprising a plurality of trees, each tree comprising a respective plurality of storage nodes, each storage node storing a subset of the plurality of keys;
receiving, by the one or more processing devices, a request to add a key of a key-value pair into the forest, the key-value pair stored in the map;
computing, by the one or more processing devices, a first hash value of the key using a first hash function;
determining, by the one or more processing devices, one of the plurality of trees to store the key based on the first hash value, wherein determining the one of the plurality of trees to store the key based on the first hash value comprises:
performing a modulo operation on the first hash value to generate a first modulo value; and
determining the one of the plurality of trees to store the key based on the first modulo value;
determining, by the one or more processing devices, a target storage node of the one of the plurality of trees to store the key; and
storing, by the one or more processing devices, the key in the target storage node.
2. The computer-implemented method of claim 1 , wherein each of the plurality of trees comprises a respective number of levels, each level corresponding to a respective hash function.
3. The computer-implemented method of claim 1 , wherein the one of the plurality of trees comprises a first level that comprises a root node, and determining the target storage node of the one of the plurality of trees to store the key comprises:
determining whether the root node has available space for storing the key; and
in response to determining that the root node in the first level has available space for storing the key, storing the key in the root node in the first level, wherein the root node is the target storage node.
4. The computer-implemented method of claim 1 , wherein the one of the plurality of trees comprises a first level that comprises a root node, and determining the target storage node of the one of the plurality of trees to store the key comprises:
determining whether the root node has available space for storing the key; and
in response to determining that the root node in the first level does not have available space for storing the key,
computing a second hash value of the key using a second hash function, the second hash function corresponding to a second level of the one of the plurality of trees, the second hash function being different from the first hash function; and
determining the target storage node in the second level of the one of the plurality of trees to store the key based on the second hash value.
5. The computer-implemented method of claim 4 , wherein determining the target storage node in the second level of the one of the plurality of trees to store the key based on the second hash value comprises:
performing a modulo operation on the second hash value to generate a second modulo value;
determining a second storage node in the second level of the one of the plurality of trees to store the key based on the second modulo value;
determining whether the second storage node has available space for storing the key; and
in response to determining that the second storage node in the second level has available space for storing the key, storing the key in the second storage node in the second level, wherein the second storage node is the target storage node.
6. The computer-implemented method of claim 1 , wherein:
each tree of the plurality of trees comprises a plurality of leaf storage nodes and one or more non-leaf storage nodes, each of the one or more non-leaf storage nodes corresponding to a configurable number of child nodes, and
each storage node of the forest stores a configurable number of keys.
7. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
maintaining data representing a forest that stores a plurality of keys of a plurality of key-value pairs that are stored in a map, the map being stored in a consensus node of a blockchain network, the forest comprising a plurality of trees, each tree comprising a respective plurality of storage nodes, each storage node storing a subset of the plurality of keys;
receiving a request to add a key of a key-value pair into the forest, the key-value pair stored in the map;
computing a first hash value of the key using a first hash function;
determining one of the plurality of trees to store the key based on the first hash value, wherein determining the one of the plurality of trees to store the key based on the first hash value comprises:
performing a modulo operation on the first hash value to generate a first modulo value; and
determining the one of the plurality of trees to store the key based on the first modulo value;
determining a target storage node of the one of the plurality of trees to store the key; and
storing the key in the target storage node.
8. The non-transitory, computer-readable medium of claim 7 , wherein each of the plurality of trees comprises a respective number of levels, each level corresponding to a respective hash function.
9. The non-transitory, computer-readable medium of claim 7 , wherein the one of the plurality of trees comprises a first level that comprises a root node, and determining the target storage node of the one of the plurality of trees to store the key comprises:
determining whether the root node has available space for storing the key; and
in response to determining that the root node in the first level has available space for storing the key, storing the key in the root node in the first level, wherein the root node is the target storage node.
10. The non-transitory, computer-readable medium of claim 7 , wherein the one of the plurality of trees comprises a first level that comprises a root node, and determining the target storage node of the one of the plurality of trees to store the key comprises:
determining whether the root node has available space for storing the key; and
in response to determining that the root node in the first level does not have available space for storing the key,
computing a second hash value of the key using a second hash function, the second hash function corresponding to a second level of the one of the plurality of trees, the second hash function being different from the first hash function; and
determining the target storage node in the second level of the one of the plurality of trees to store the key based on the second hash value.
11. The non-transitory, computer-readable medium of claim 10 , wherein determining the target storage node in the second level of the one of the plurality of trees to store the key based on the second hash value comprises:
performing a modulo operation on the second hash value to generate a second modulo value;
determining a second storage node in the second level of the one of the plurality of trees to store the key based on the second modulo value;
determining whether the second storage node has available space for storing the key; and
in response to determining that the second storage node in the second level has available space for storing the key, storing the key in the second storage node in the second level, wherein the second storage node is the target storage node.
12. The non-transitory, computer-readable medium of claim 7 , wherein:
each tree of the plurality of trees comprises a plurality of leaf storage nodes and one or more non-leaf storage nodes, each of the one or more non-leaf storage nodes corresponding to a configurable number of child nodes, and
each storage node of the forest stores a configurable number of keys.
13. 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 one or more operations comprising:
maintaining data representing a forest that stores a plurality of keys of a plurality of key-value pairs that are stored in a map, the map being stored in a consensus node of a blockchain network, the forest comprising a plurality of trees, each tree comprising a respective plurality of storage nodes, each storage node storing a subset of the plurality of keys;
receiving a request to add a key of a key-value pair into the forest, the key-value pair stored in the map;
computing a first hash value of the key using a first hash function;
determining one of the plurality of trees to store the key based on the first hash value, wherein determining the one of the plurality of trees to store the key based on the first hash value comprises:
performing a modulo operation on the first hash value to generate a first modulo value; and
determining the one of the plurality of trees to store the key based on the first modulo value;
determining a target storage node of the one of the plurality of trees to store the key; and
storing the key in the target storage node.
14. The computer-implemented system of claim 13 , wherein each of the plurality of trees comprises a respective number of levels, each level corresponding to a respective hash function.
15. The computer-implemented system of claim 13 , wherein the one of the plurality of trees comprises a first level that comprises a root node, and determining the target storage node of the one of the plurality of trees to store the key comprises:
determining whether the root node has available space for storing the key; and
in response to determining that the root node in the first level has available space for storing the key, storing the key in the root node in the first level, wherein the root node is the target storage node.
16. The computer-implemented system of claim 13 , wherein the one of the plurality of trees comprises a first level that comprises a root node, and determining the target storage node of the one of the plurality of trees to store the key comprises:
determining whether the root node has available space for storing the key; and
in response to determining that the root node in the first level does not have available space for storing the key,
computing a second hash value of the key using a second hash function, the second hash function corresponding to a second level of the one of the plurality of trees, the second hash function being different from the first hash function; and
determining the target storage node in the second level of the one of the plurality of trees to store the key based on the second hash value.
17. The computer-implemented system of claim 16 , wherein determining the target storage node in the second level of the one of the plurality of trees to store the key based on the second hash value comprises:
performing a modulo operation on the second hash value to generate a second modulo value;
determining a second storage node in the second level of the one of the plurality of trees to store the key based on the second modulo value;
determining whether the second storage node has available space for storing the key; and
in response to determining that the second storage node in the second level has available space for storing the key, storing the key in the second storage node in the second level, wherein the second storage node is the target storage node.