Performance Issue When Saving Trie Node

[ajlopez]

In TrieStoreImpl the save of a node trie is implemented with this code:

    /**
     * @param forceSaveRoot allows saving the root node even if it's embeddable
     */
    private void save(Trie trie, boolean forceSaveRoot, int level) {
        logger.trace("Start saving trie, level : {}", level);
        if (savedTries.contains(trie)) {
            // it is guaranteed that the children of a saved node are also saved
            return;
        }

        byte[] trieKeyBytes = trie.getHash().getBytes();

        if (forceSaveRoot && this.store.get(trieKeyBytes) != null) {
            // the full trie is already saved
            logger.trace("End saving trie, level : {}, already saved.", level);
            return;
        }

        logger.trace("Start left trie. Level: {}", level);
        trie.getLeft().getNode().ifPresent(t -> save(t, false, level + 1));
        logger.trace("Start right trie. Level: {}", level);
        trie.getRight().getNode().ifPresent(t -> save(t, false, level + 1));

        if (trie.hasLongValue()) {
            // Note that there is no distinction in keys between node data and value data. This could bring problems in
            // the future when trying to garbage-collect the data. We could split the key spaces bit a single
            // overwritten MSB of the hash. Also note that when storing a node that has long value it could be the case
            // that the save the value here, but the value is already present in the database because other node shares
            // the value. This is suboptimal, we could check existence here but maybe the database already has
            // provisions to reduce the load in these cases where a key/value is set equal to the previous value.
            // In particular our levelDB driver has not method to test for the existence of a key without retrieving the
            // value also, so manually checking pre-existence here seems it will add overhead on the average case,
            // instead of reducing it.
            logger.trace("Putting in store, hasLongValue. Level: {}", level);
            this.store.put(trie.getValueHash().getBytes(), trie.getValue());
            logger.trace("End Putting in store, hasLongValue. Level: {}", level);
        }

        if (trie.isEmbeddable() && !forceSaveRoot) {
            logger.trace("End Saving. Level: {}", level);
            return;
        }

        logger.trace("Putting in store trie root.");
        this.store.put(trieKeyBytes, trie.toMessage());
        logger.trace("End putting in store trie root.");
        savedTries.add(trie);
        logger.trace("End Saving trie, level: {}.", level);
    }

We could discuss some refactor (ie detecting the trie is embedded earlier), but the main issue is in the lines:

        logger.trace("Start left trie. Level: {}", level);
        trie.getLeft().getNode().ifPresent(t -> save(t, false, level + 1));
        logger.trace("Start right trie. Level: {}", level);
        trie.getRight().getNode().ifPresent(t -> save(t, false, level + 1));

If the trie node to be saved is new and not contained in the savedTries set, THEN the above logic LOAD in memory and save the children EVEN when the children were not changed (ie, the new trie node changed its value, and their children were not read nor modified).

Proposal

Replace the above lines with this code:

        NodeReference leftNodeReference = trie.getLeft();

        if (leftNodeReference.wasLoaded()) {
            logger.trace("Start left trie. Level: {}", level);
            leftNodeReference.getNode().ifPresent(t -> save(t, false, level + 1));
        }

        NodeReference rightNodeReference = trie.getRight();

        if (rightNodeReference.wasLoaded()) {
            logger.trace("Start right trie. Level: {}", level);
            rightNodeReference.getNode().ifPresent(t -> save(t, false, level + 1));
        }

There is WIP (Work In Progress) code in https://github.com/ajlopez/rskj/tree/triefix