feat: add adr-001 for node key refactoring#608
Conversation
|
a good question by celestia, how does this effect the commitment structure? Are proofs still the same? |
it doesn't affect, as you can see in #597 it doesn't update any proof part and still passing tests |
#597 still contains Line 364 in 36a150e version will affect all the hashes, and therefore migration will invalidate all existing proofs.
|
@tzdybal , good catch. @tac0turtle how about your thougt? Will we keep the version or refactor the ics23 part? |
what do you mean by refactor ics23? So there are two paths, introduce this in a breaking release of the sdk which a coordinated upgraded is needed or leave it alone. for testing purposes and data collection we probably want to leave it but in the future we could break it. BUT we should check with IBC about this. |
I mean update the validation part in ics23.
Sounds good, then let's keep the version at this time. I will create the issue and we can revisit in the future |
| leftNodeKey int64 // new field, need to store in the storage | ||
| rightNodeKey int64 // new field, need to store in the storage |
There was a problem hiding this comment.
Why do we need these fields, if we already have leftNode and rightNode?
There was a problem hiding this comment.
leftNode and rightNode is only meaningful on memory side, we need these fields to get children from the storage side.
Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>
Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>
aaronc
left a comment
There was a problem hiding this comment.
I'm unclear as to how an integer improves data locality. Can you explain this a bit more? It would seem that it puts nodes that are created at similar times near each other in the B-tree, but this doesn't actually improve things like range scans other than by reducing the size of the node key which is significant.
Reducing key size itself improves data locality. I am not sure if leveldb uses compressed trie or general bTree, but we can reduce the node count and improve the tree density. |
https://github.com/cosmos/iavl/blob/master/export.go#L21 |
| The `Update` operation will require extra DB access because we need to take children to calculate the hash of updated nodes. | ||
| It doesn't require more access in other cases including `Set`, `Remove`, and `Proof`. | ||
|
|
||
| It is impossible to remove the individual version. The new design requires more restrict pruning strategies. |
There was a problem hiding this comment.
can you elaborate on this?
There was a problem hiding this comment.
I think it is enough, it will remove orphans and it will be impossible to remove the intermediate version from storage.
And pruning part explains in more detail the new methods.
There was a problem hiding this comment.
Even if removing orphans, it's certainly possible to delete the individual versions in between.
There was a problem hiding this comment.
lets edit to include this.
|
Another round of review: Keep order of insertion sortedwhen there are multiple stores in the same db, the insertion is not sorted by keys anymore. MigrationYou also need to record the mapping of PruningWe'll need both in-order and pre-order somehow, in-order to keep the key order, pre-order to skip subtree early on. Remove the individual versionIt's still possible to remove individual version with new pruning alrogithm, we just need to be aware of predecessor version and avoid deleting nodes older than that. Export SnapshotCan we clarify that the new node key format don't affect the snapshot export format? so the nonce assignment strategy is not part of consensus, but a node local decision. |
|
|
||
| ### Negative | ||
|
|
||
| The `Update` operation will require extra DB access because we need to take children to calculate the hash of updated nodes. |
There was a problem hiding this comment.
Do you mean to say that it requires extra DB reads? Why is this not needed in Set and Remove?
There was a problem hiding this comment.
because update only needs the re-calc of hash, but Set and Remove requires calcHeightAndSize (re-calculation of height and size) and this needs to splay the children nodes
There was a problem hiding this comment.
so we are getting left and right in Set and Remove but not splay in Update since we have leftHash and rightHash in the original version
There was a problem hiding this comment.
the trade off here is storage saving on per node basis, right? maybe we mention this as a tradeoff
Co-authored-by: Aaron Craelius <aaron@regen.network>
ref: #592, #593, #597