JavaScript merkle-patricia-tree/secure - OutOfMemory when traversing large (~70Gb) state tries

Question

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){
  console.log(data)
});

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

Answer 1

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
        cb()
      },
      // end all traversal and return values to the onDone cb
      return: function () {
        aborted = true
        returnValues = arguments
        cb()
      },
      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()
          childKey.push(childIndex)
          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.