I have the JavaScript code below, which is traversing the state trie from geth's leveldb for Ethereum mainnet Block #5200035.

After some time with high cpu usage and having reserved about 6Gb RAM, it crashes with FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory.

It looks like the library is having trouble with the size of the mainnet database (~70Gb after a fast sync). A simple key/value lookup with db.get works fine. If I try to traverse something smaller like the storage trie of a contract (tried with 0xd0a6E6C54DbC68Db5db3A091B171A77407Ff7ccf) it also works fine.

Any idea how to approach this problem?

var Trie = require('merkle-patricia-tree/secure');
var levelup = require('levelup');
var leveldown = require('leveldown');

//Connecting to the leveldb database
var db = levelup(leveldown('../datadir/geth/chaindata'));

//Adding the "stateRoot" value from the block so that we can inspect the state root at that block height.
var root = "0x4d675087a16f13fa5f61af74d79e08c82de7cf200e63d5b225b4a7937705a3e2"; // Block #5200035

//Creating a trie object of the merkle-patricia-tree library
var trie = new Trie(db, root);

//Creating a nodejs stream object so that we can access the data
var stream = trie.createReadStream()

//Turning on the stream (because the node js stream is set to pause by default)
stream.on('data', function (data){

This question is related to How to collect all contract instantiations and count the bytecode redundancies?


Pull request for the fix https://github.com/ethereumjs/merkle-patricia-tree/pull/38

Previous answer

I'm not 100% sure but I think the problem lies in using the async.forEachOf() for traversing the children of a node in baseTrie.js in the processNode function https://github.com/ethereumjs/merkle-patricia-tree/blob/dc436426d717fed408f4d46fed23f6d26d03d39d/baseTrie.js#L447:

 function processNode (nodeRef, node, key, cb) {
    if (!node) return cb()
    if (aborted) return cb()
    var stopped = false
    key = key || []

    var walkController = {
      stop: function () {
        stopped = true
      // end all traversal and return values to the onDone cb
      return: function () {
        aborted = true
        returnValues = arguments
      next: function () {
        if (aborted) {
          return cb()
        if (stopped) {
          return cb()
        var children = node.getChildren()
        async.forEachOf(children, function (childData, index, cb) {
          var keyExtension = childData[0]
          var childRef = childData[1]
          var childKey = key.concat(keyExtension)
          self._lookupNode(childRef, function (childNode) {
            processNode(childRef, childNode, childKey, cb)
        }, cb)
      only: function (childIndex) {
        var childRef = node.getValue(childIndex)
        self._lookupNode(childRef, function (childNode) {
          var childKey = key.slice()
          processNode(childRef, childNode, childKey, cb)
    onNode(nodeRef, node, key, walkController)

If using async here then the trie will be traversed breadth first as opposed to depth first if using synchronous traversal (breadth first basically means that before you get the first key in the stream you load the entire trie into memory, with the current ~30mil accounts in the state it can easily exceed 6GB). I'd try changing it to a simple for loop and see if it fixed the issue (unfortunately can't test it now as I don't have the mainnet chaindata).

Or maybe try using another library for reading the Patricia Merkle Trie.

  • Do you have any suggestions for another trie JavaScript library? – ivicaa Mar 5 '18 at 14:58
  • 1
    Unfortunately, haven't tried other libs yet. Will let you know if I can find a good one :) – medvedev1088 Mar 5 '18 at 15:00
  • 1
    Try this fix github.com/medvedev1088/merkle-patricia-tree/pull/1/files. I create a pool and a priority queue such that nodes with longer keys are looked up first. Fixed OOM for me. I'm not a JavaScript expert so can find some ugly code there. Any comments are welcome. – medvedev1088 Mar 5 '18 at 18:10
  • 1
    Works! Most probably I am underplaying it when I am saying you're a genius! It's a pity I can not push the upvote multiple times. :-) – ivicaa Mar 5 '18 at 18:29
  • 1
    Thanks :). But review my code first. There might be bugs there so don't rely on it blindly. – medvedev1088 Mar 5 '18 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.