Comments (10)
Currently working on this by building on top of loom PR (#150).
Current design
MutableTree has extra fields:
// Pruning fields
keepEvery int64n // Saves version to disk periodically
keepRecent int64 // Saves recent versions in memory
NodeDB has extra fields:
memDb dbm.DB // Memory node storage.
memBatch dbm.Batch // Batched writing buffer for memDB.
On SaveRoot
, the IAVL checks if the version should be persisted to disk (version % keepEvery == 0
)
If version is not going to be persisted to disk, the version is simply saved in memDB
If version is persisted to disk, the version is written to memDB
and levelDB
When version n
is saved, version n - keepRecent
is deleted from memDB. Thus, memDB
always contains keepRecent
versions of the tree.
Orphans:
Save orphan to memDB under o|toVersion|fromVersion
.
If there exists snapshot version snapVersion
s.t. fromVersion < snapVersion < toVersion
, save orphan to disk as well under o|snapVersion|fromVersion
.
NOTE: in unlikely event, that two snapshot versions exist between fromVersion
and toVersion
, we use closest snapshot version that is less than toVersion
Can then simply use the old delete algorithm with some minor simplifications/optimizations
Open Questions:
-
Currently recently persisted versions exist both in
memDB
andlevelDB
. This is so that retreiving a recently persisted version is fast. However, it introduces minor duplication (not a problem in any sane pruning strategy). -
Currently recent versions are saved to
memDB
. Is this better than simply storing in a mapkey => *Node
like loom currently does? I'm not sure what the tradeoffs are.
Decision: Decided to go with usingmemDB
since it already implements DB interface (iterating, etc). Also, could switch out memDB for something else later so long as it respects DB interface. -
Now that
memDB
acts as a recent version "cache" forlevelDB
, need to specify the use (if any) for LRU cache. My thinking is that this will be used to cache old nodes (version < latest - keepRecent
) that are frequently called byGetNode
. But have to make sure that LRU cache's purpose is strictly defined (when does a node get added to cache?) and enforced. -
Currently all
traverse
functions traverse over singlelevelDB
. This will have to be refactored to allow traversing overlevelDB
,memDB
, or both. Should replace all current traversal calls with the appropriate new traversal function.
Currently implementing: -
We can flush any versions in
memDB
to disk in event of graceful shutdown, how do we restart node correctly?
Current thinking: Regardless of whether there is a graceful shutdown or not, on recovery, we reverse-iterate for the latestVersion stored on disk (and refill memDB if necessary).
from conversation with @jackzampolin
from iavl.
If we do not write values to database every block, that will improve throughput dramatically. But we need to replay all blocks from latest saved state when we restart node.
do we have a plan to do this
from iavl.
yeah this would be need.
IF there is a graceful shutdown, we just flush to disk before we shutdown but block replay would be great for recovery in a panic
from iavl.
See #150
from iavl.
Actually, if we do save LastCommit when we do not save IAVL state, then blocks will be replayed automatically for the difference between state height and block height. A graceful shutdown will surely help to save the replay work.
So besides the IAVL change you mentioned, we also need to do some changes on cosmos Commit stage.
from iavl.
For recovery, Tendermint store metadata on the LastCommit
and then replays all past block. Tendermint will need to know how to back up to last save commit and then replay.
Current thinking is that isn't necessarily hard.
from iavl.
Sounds like you should write up an approach for points 3 and 4 above and we can get some feedback on those.
from iavl.
This is closed with PR correct @AdityaSripal
from iavl.
Reopening this as a potential work scope for future iavl work.
from iavl.
closing this as the goal is referenced in #140
from iavl.
Related Issues (20)
- Racing conditions on `UnsavedFastIterator` & `MutableTree` HOT 6
- Change node key of leaf nodes to contain the value's key
- Restoring state-sync snapshot takes a long time HOT 5
- all: use SHA256 with SIMD instructions for higher performance and throughout HOT 14
- export: don't support multiple formats HOT 3
- empty root loading is failed in `GetImmutable`
- upstream deepsubtree work from celestia
- Proposed new repo API
- Implement a `lazy set` for the migration to the new node key format HOT 2
- Consider dropping error result from ImmutableTree.Iterator
- Consider dropping error result from ImmutableTree.Export
- Drop error result from NewMutableTree/NewMutableTreeWithOpts HOT 1
- Drop error result from Node.hashWithCount HOT 1
- leaf separation or versiondb integration HOT 1
- keyformat: (*KeyFormat).KeyBytes presumes that len(kf.layout) will always be non-empty
- internal/rand: RandStr and (*Rand).Str should have limits to their lengths lest cause memory hogs and if used can caused a Denial-of-Service HOT 1
- Consider changing the type of NodeKey.nonce to uint32 HOT 7
- Missing bounds check in deltaEncode HOT 1
- Memory leak during State Sync HOT 4
- iavl export failed with "version does not exist" HOT 2
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.