search

turbofish-org / merk

High-performance Merkle key/value store
Apache License 2.0
226 stars 36 forks source link

Order of transactions in the tree #8

Closed davebryson closed 5 years ago

davebryson commented 5 years ago

With IAVL I believe it was (is) a best practice to sort transactions before committing them to the tree. Is this true for merk as well? Looking through the code it doesn't appear that it's doing so. Great work by the way...

mappum commented 5 years ago

Interesting, any idea why? That seems unnecessary as long as the operations are produced in a deterministic order.

davebryson commented 5 years ago

I think determinism is the reason: From the IAVL docs:

On the other hand, while IAVL+ trees provide a deterministic merkle root hash, it depends on the order of transactions. In practice this shouldn't be a problem, since you can efficiently encode the tree structure when serializing the tree contents.

I know in the past when I used IAVL I'd sort keys in the cache before committing to the tree.

Appears to be added in with the Cosmos SDK cachekvstore: https://github.com/cosmos/cosmos-sdk/blob/develop/store/cachekvstore.go#L109

mappum commented 5 years ago

Cool well in that case, I think the contract with the consumer of merk should be to make operations in a deterministic order. IMO it shouldn't be the data store's job to enforce that.

Although this should probably be outlined in the README to prevent confusion.

mappum commented 5 years ago

Closing since the Rust rewrite was made to sort the data by default, but also have a method which takes presorted data for higher performance.