[Execution state] complete ledger - using maxDepthTouched instead of maxDepth metric

[ramtinms]

Currently, each node holds a uint64 for the regCount and a uint16 for a maxDepth. The first one captures the number of registers s and the second one captures the maximum depth under that subtree. the maxDepth can be replaced with an update level metric that captures the maximum depth that was reached during the update without the nodes keeping the information about the maxDepth.

by removing that value from the intermediate nodes we can save a good amount of memory

[Ullaakut]

This should save about 640MB over a 30GB checkpoint, which is indeed non-negligible. I can get started on this task whenever you give me the green light.

One caveat though is that this change would mean that the MaxDepth attribute in the old checkpoints and in the encoding format would now be discarded, and new checkpoints/the new encoding format should not include that data anymore. Because of this, we would effectively have to increment the encoding version, and of course still support the previous version to be able to read older checkpoints.

Since other tasks within this epic will also likely impact the encoding format however, I think this is a non-issue, but please let me know if I am making any wrong assumptions there.

[Ullaakut]

The current situation is that:

• The Forest structure is what holds the ledger metrics component
• It effectively reads forest.trie.root.MaxDepth() to output the MaxDepth metric

Ideally I think we want to change this so that the mtrie.Trie structure contains a maxDepth attribute which would be exposed through a public method, like before. However, currently the update function is not attached to the mtrie.Trie itself. It simply takes arbitrary node pointers, paths and payloads, and updates the nodes accordingly.

This means we have a few options to set the trie's attribute when we update, none of which seem ideal to me:

1. Attach update to the mtrie.Trie structure. This would mean that it would no longer be possible to call update without having an mtrie.Trie. This is never the case at the moment, AFAIK, so that might be an okay solution, but it breaks consistency, and it feels like a huge change with large implications, for such a small need (to set an attribute in the trie)
2. Make update return the depth at which the leaves are created. Because currently update can insert multiple nodes at once, we would need to have some kind of logic so that if two paths created leaves, their interim node's update call returns the highest value of its two children's maxDepth returns. This would reduce the clarity of the update function, which is already quite difficult enough to follow as it is IMO.
3. Add a callback argument to the update function which would be able to contain this logic to pick only the highest max depth and set it on the trie only if it is higher than the current one. This is also not great because it adds yet another argument to the update function.

There are probably other solutions I'm missing, so feel free to suggest them if you have ideas, or to tell me which one is the most convenient of the aforementioned three.

In our implementation in the Flow DPS, we went with the first approach, and have a trie.Insert method to insert ledger key/values into the trie, which would allow us to easily make this change on our side, but here with the recursion and the way the code is currently designed, it's not an easy task. If you think the first approach is fine, we could go a bit further and also replace the recursive approach with an iterative one, to improve code clarity. Our Insert implementation might seem quite complex, but it is mostly due to the extension nodes. Without extensions, it would be about 30 lines of code.

[fxamacker]

Hi @Ullaakut

Ideally I think we want to change this so that the mtrie.Trie structure contains a maxDepth attribute which would be exposed through a public method, like before.

I agree.

Out of the three options, I like option 3 (using callback) even though it adds another argument to the update function. Maybe we can use the same callback function to keep track of regCount (issue #1748). So instead of 2 additional return values, we can have 1 additional argument. In the future, we can track additional metadata (if needed) by only modifying the callback function. Also this approach separates update node logic from update metadata logic.

Maybe to keep it simple, callback function only needs to be called when creating new (compact) leaf. Instead of updating maxDepth, we can keep track of lowest new leaf node height and compute maxDepth afterwards.

[Ullaakut]

Hi @fxamacker,

I am fine with going this way then sure, but I'm curious about your thoughts on the solution #1 here? It seems to me like while it is overkill for this specific task, having the update logic be a method attached to the trie rather than an independent function could have further positive effects. It's what we did in the DPS and I think it works quite well, so I'd love to know your opinion on it.

[fxamacker]

Hi @Ullaakut, I have two concerns about option #1.

• I agree with you that it is overkill for this specific task. It's a big change.
• The trie in optakt/flow-dps appears to be mutable. However, mtrie in Flow is currently immutable.

In DPS, the Trie.Insert() can modify existing nodes while inserting a path and payload. And it makes sense the same trie is updated during batch updates using a for-loop.

In Flow, mtrie being immutable allows us to create mtrieB from mtrieA, and still have mtrieA available. I think this and maybe other aspects might be difficult to achieve by attaching update function to the trie.

Please let me know what you think. Maybe I misunderstood or missed something.

[Ullaakut]

Hi @fxamacker, thanks for your detailed answer!

Are there lots of cases where the trie needs to be immutable in Flow? We got around this on our side by, in the only case where we want to create an trieB from an trieA without modifying it, defining a new trie: trieB := trie.NewTrie(trieA.RootNode(), ...) followed by the insertions on trieB. Since for us there's a single place where we have this use case, it made sense for us.

Either way, I am fine with the callback, so we can most definitely go for that :)

[fxamacker]

Hi @Ullaakut,

We got around this on our side by, in the only case where we want to create an trieB from an trieA without modifying it, defining a new trie: trieB := trie.NewTrie(trieA.RootNode(), ...) followed by the insertions on trieB. Since for us there's a single place where we have this use case, it made sense for us.

Unless I'm mistaken, it seems changes to trieB modifies triaA because trieB is a wrapper for trieA's root node and trieB.insert() modifies the wrapped node (marking it as dirty for hash recomputation) as it traverses down the trie.

In the following code blocks from DPS trie, trie.NewTrie returns a new trie that wraps the original root node.

https://github.com/optakt/flow-dps/blob/trie-improvements/service/mapper/transitions.go#L374-L377

// We then apply the update to the relevant tree, as retrieved from the
	// forest, and save the updated tree in the forest. If the tree is not new,
	// we should error, as that should not happen.
	paths, payloads := pathsPayloads(update)
	newTree := trie.NewTrie(t.log, tree.RootNode(), tree.Store())
	for i := range paths {
		newTree.Insert(paths[i], payloads[i])
	}

https://github.com/optakt/flow-dps/blob/01ed08bc3dbf241e790c0800bc92882367e395a0/ledger/trie/trie.go#L50

// NewTrie creates a new trie using the given root node and payload store.
func NewTrie(log zerolog.Logger, root Node, store dps.Store) *Trie {
	t := Trie{
		log:   log.With().Str("subcomponent", "trie").Logger(),
		root:  root,
		store: store,
	}

	return &t
}

[Ullaakut]

Hi @fxamacker! Thanks for your quick and thoughtful answers :)

As shown in this test where we compare the FlowGo approach and the FlowDPS approach, both result in not mutating the original trie.

Unless I made a mistake in my methodology? But it seems to me like the way FlowGo updates a trie is essentially the same, it basically creates a new trie (effectively a wrapper around the root node) from the same root node. Or did I miss something there?

I'm curious because I didn't spend much time thinking about it and I am not sure why it actually works and does not mutate the original trie, in both cases. To me it seems like since we're dealing only with pointers, as long as we reuse the pointer of the root node of one trie to made modifications to the trie, both tries should be changed, but effectively it seems not to be the case since calling trieA.RootHash() and trieB.RootHash() yield different results, which match with FlowGo's results.

[fxamacker]

Hi @Ullaakut, thanks for the followup and extra details. Your link to DPS forest_integration_test.go was very helpful.

I added extra comparison checks to forest_integration_test.go in DPS.

Running the updated test indicates mutability.

    forest_integration_test.go:84: 
        	Error Trace:	forest_integration_test.go:84
        	Error:      	Not equal: 
        	            	expected: ledger.RootHash{0x9c, 0x76, 0x2e, 0x9e, 0x4c, 0xbc, 0xb, 0xb7, 0x7b, 0x74, 0x8b, 0x9b, 0x84, 0xab, 0xd4, 0xcb, 0xba, 0x94, 0xae, 0xda, 0xd2, 0xd1, 0x99, 0x98, 0x0, 0xa2, 0x7e, 0xd9, 0xa0, 0xa5, 0x2c, 0x3e}
        	            	actual  : ledger.RootHash{0xb8, 0xa3, 0xe8, 0x86, 0x43, 0x36, 0x1a, 0xbe, 0xb7, 0xa9, 0x23, 0x35, 0x4f, 0x58, 0x2b, 0xec, 0xf3, 0x4c, 0x6e, 0x88, 0xa1, 0x71, 0xe3, 0x9, 0x3b, 0x3c, 0xa0, 0x33, 0x2, 0x1b, 0x73, 0xef}

Changes to DPS forest_integration_test.go are at https://github.com/fxamacker/flow-dps/pull/1/files and this diff includes line 84 shown in the test error trace.

[Ullaakut]

@fxamacker Indeed, my methodology was completely wrong 😄 It makes total sense then. That might be the reason behind a mismatch I failed to identify, so I'll look into fixing it to make the mechanism preserve immutability. Thanks for the clear explanations, it really helps :)