search

celestiaorg / smt

A Go library that implements a Sparse Merkle tree for a key-value map.
https://godoc.org/github.com/celestiaorg/smt
MIT License
138 stars 53 forks source link

Tree sharding to process updates in parallel #62

Open musalbas opened 3 years ago

musalbas commented 3 years ago

At the moment, the tree can only safely handle one update at a time. It would be desirable to shard the tree into multiple subtrees and allow parallel updates to the subtrees.

tac0turtle commented 3 years ago

Does this get rid of atomic writes?

Does this have overlap with https://github.com/cosmos/cosmos-sdk/issues/6370

musalbas commented 3 years ago

It shouldn't do if implemented correctly! See https://github.com/google/trillian/blob/v1.4.0/merkle/smt/writer.go#L37 for a sharded SMT implementation (but without the efficiency improvements of the Libra SMT).

liamsi commented 3 years ago

The SDK is about to remove / reduce (?) the multistore because it is not easy to implement this correctly I think. See specifically this comment: https://github.com/cosmos/cosmos-sdk/issues/6370#issuecomment-643226398 (the problem is that the sub-trees are treated somewhat too independently and the abstractions did not make it easy that the writes were actually atomic).

IIUC, the code @musalbas posted is not about sharding into subtrees alá logical subtrees (like in the multistore) but rather about sharding into equal sized shards independent of any logical sub-trees (e.g. accounts, delegations, valsets etc would be logical sub-trees).

Either way, it is probably safe to say that this does not have the highest priority right now?

musalbas commented 3 years ago

It's not high priority, but it would be important for execution environments like Solana that support parallel transaction execution.

universe2439 commented 2 years ago

Agree not high priority