Setting & getting data for the Fast Cache

[ValarDragon]

We are conceptualizing the fast cache as this direct key value store for latest state. For simplicity of deployment / migration logic, our plan is to make this a secondary copy of latest state in the database. (We do more egregious space overheads with the cosmos pruning strategy, so this is not that bad)

IAVL is divided into two trees, mutable_tree and immutable_tree. Sets only happen on the mutable tree.

Things that need to change and be investigated for getting and setting, and the fast node:

• mutable tree
  • GetVersioned
    • Change the logic to check the FastNode cache first, then do the GetImmutable logic
  • Set
    • Currently there is a bug right now, where it calls SaveFastNode immediately. Looking at the existing code (which is quite confusing and likely led to the bug), this should only be called during SaveVersion. We should add a new field to MutableTree for unsavedFastNodeChanges, and make that a hash map. Then we have every Set update that. Then in SaveVersion we call SaveFastNode on everything in that map. Preferrably, we iterate over this map in deterministic order. (So by sorting the map keys first)
• immutable_tree
  • Get
    • Currently it checks if value is nil before the version check. This is reversed, it should check if the version is too new. If so do old logic. If its sufficiently old, then value = nil implies that the node is deleted. So it should return whatever t.root.get(t, key) returns on a non-existent key.
    • (Note we don't care about the index return value we can make it whatever we want. To our knowledge, nothing uses this index return value. At the end, we may decide to make a new function just to preserve API's / be sure, but no need for right now)
  • We also need to test that these changes work. We should make a test function somewhere, to ensure that the FastNodeCache matches the live State. Then we test that in several of the existing tests. Probably easiest to do so after every version in testRandomOperations, in tree_random_test.go

Things needed for migration and iteration are relegated to new issues.

[ValarDragon]

Also need to rerun/ potentially update the benchmarks to see if we actually sped up reads and how much we slowed down writes

[ValarDragon]

Notes from call:

• Ensure that Set does not update the FastNodeCache in nodedb
• Ensure that SaveVersion updates everything in the FastNodeCache

[p0mvn]

Is it safe to assume that the index in GetVersioned of the mutable tree is also unused and can be anything? Similar to immutable tree's Get...

[ValarDragon]

Yeah, we can assume that. Let me know if theres some test failures its causing, if so we then may just have to add new functions and do some updates to the SDK. But I believe they're unused

[ValarDragon]

Just double checked, merkle proof code doesn't use this, I have no idea why the index param exists. We should file an issue to delete it later as well

[p0mvn]

No failures from the incorrect index. However, there are problems with the tests that delete a version and then try to get that deleted version. Since there is no functionality for deleting FastNodes, their values get returned when they should not be. I believe I should also implement the functionality of deleting old versions of the FastNodes.

I'll be prototyping that in the next little while

[p0mvn]

On more investigation, I think it might be better to delete all FastNodes from the database when a new version is saved by SaveVersion because FastNodes are designed to represent the live state. So IMO it does not make sense to persist the old fast node state since that goes against the abstraction

[ValarDragon]

Shouldn't the fast node get deleted when calling Set with a value thats nil?

[ValarDragon]

It'd get added to the list of unsaved FastNodes update in mutable tree, and then get persisted when calling SaveVersion?

[p0mvn]

Shouldn't the fast node get deleted when calling Set with a value thats nil?

At the moment, Set panics if we try to set a nil value

[p0mvn]

It'd get added to the list of unsaved FastNodes update in mutable tree, and then get persisted when calling SaveVersion?

Yes, that's correct. However, we need to delete old versions of fast nodes somewhere when there are updates to the tree. There are use cases where we may do the following:

tree.Set("c", "val1")
tree.SaveVersion()

tree.Set("c", "val2")

tree.DeleteVersion(1)

_, val := tree.GetVersioned("c", 2)
// val must be "val2"  since the live version is 2

Therefore, I'm trying to remove the persisted fast nodes from the db when we call SaveVersion so that the old versions are not loaded

[p0mvn]

No failures from the incorrect index. However, there are problems with the tests that delete a version and then try to get that deleted version. Since there is no functionality for deleting FastNodes, their values get returned when they should not be. I believe I should also implement the functionality of deleting old versions of the FastNodes.

I'll be prototyping that in the next little while

UPDATE: the incorrect index did cause some test failures. I will go with Dev's suggestion of introducing new Get methods and filing an issue to remove the old methods later