Comments (7)
I wonder if it'd be worthwhile to explore an approach for iavl similar to what they're doing on the handshake project - creating a flat file database designed around the tree:
We devise an authenticated data structure, which unlike the Ethereum Trie or
Sparse Merkle Tree, is intended for storage in flat files. This removes the
overhead of database lookups entirely by making the data structure its own
database implementation.
By storing a merkelized data structure in a series of append-only files, we are
able to provide traditional database features such as snapshotting, atomicity,
and crash consistency. Given our requirements, a trie is the obvious choice as
a backing data structure.
from iavl.
Snapshotting - yes
Simple small proofs - yes
Range queries/proofs - would need to be implemented
Additionally, you'll also need compaction. Essentially you're creating a custom database for the tree. Not a trivial thing to get right. But I bet the Tendermint team has the "chops" to do it 😃
I don't know about a drop-in replacement if Tendermint prefers AVL. There's primarily 2 versions of the Urkel tree: simple base 2, and radix like.
from iavl.
One of the first issues, is the underlying persistence area is quite dumb and has little knowledge of what its storing, so you can't even optimize the storage much cause it just uses a https://github.com/tendermint/tendermint/blob/master/libs/db/types.go#L4 tendermint/db interface. It would be nice to know about the tree and info when doing persistence. Maybe nodedb should be pluggable or something even more higher level
See https://github.com/tendermint/iavl/blob/master/nodedb.go#L37
from iavl.
According to Jae, IAVL tree already has Copy on Write semantics
from iavl.
Assuming Urkle supports snapshotting, range queries/proofs and prefix iteration, can't it be used as a drop-in replacement for IAVL?
from iavl.
#144 has a few ideas related to this, when this work is picked up please check that pr
from iavl.
Had a quick glance over Urkle implementation, it seems the storage format is similar to our new node key format, index the nodes by order, we can also do a similar flat file storage like this.
from iavl.
Related Issues (20)
- Memory leak during State Sync HOT 4
- iavl export failed with "version does not exist" HOT 2
- Async Commit HOT 1
- nodeDb.DeleteVersionsFrom can leave mutex locked indefinitely hence a deadlock
- [Epic]: IAVL v2 implementation HOT 1
- Post-order snapshot HOT 4
- Tree diff (IAVL v1 design)
- Historical proofs & changelog replay
- Refactor the pruning logic in V1 HOT 1
- Add a metric to track state size HOT 3
- Why got error: orphan expires before it comes alive. 41 > 40. HOT 3
- [Question] About leaf and inner nodes and how they change
- Lazy Pruning HOT 3
- Change IAVL node.writeBytes to take in bytes.Buffer HOT 3
- meaningless cache adding in the pruning
- CacheMultiStoreWithVersion -> store.(*iavl.Store).GetImmutable(version) error: "version does not exist"
- PANIC: in node.go func (node *Node) String() string
- `UnsetCommitting` is not idemptont
- Root hash breaking change in v1.x.x HOT 4
- Stop pruning Go routine on close
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from iavl.