Trie doesn't remove obsolete nodes from cache and database about ethereumj HOT 8 CLOSED

I had to remove that part to workaround a bug where old values were still referenced in an external class (See pull request #81) I might have a solution and will try to put it back for Poc6, but for now it's not a problem until the cache runs out of memory.

Come to think of it, the nodes also need to be removed from the database.

from ethereumj.

It's a garbage data that disturbs the
dump and your ability for clear
compare .

It's not connected in any way to
eviction policy.

from ethereumj.

Apparently this 'garbage data' has some use for rolling back to old states. Garbage collection might still be usefull. To save diskspace, it might be nice to have it pruned at one point.

[22:12:51] Vitalik Buterin: py is full storage right now
[22:12:58] Vitalik Buterin: plan is to store 30000 probably

from ethereumj.

The optimal strategy that Gav, Heiko and I were discussing is to have a
concept of a "death row", where as soon as a trie updates nodes that are no
longer referenced by the main root go on death row, and are scheduled to be
removed after 30000 blocks. If a revert happens, then the death row gets
reverted.

It's a bit complicated, and I'm still trying to figure out the best way to
do it without introducing inefficiency, but it should work.

An alternative strategy is to copy the entire current trie over to a new DB
every 30000 blocks, and then delete DBs older than the current and previous
one. This might be simpler to write, and it really depends on the level of
usage which one is better.

On Sun, Sep 14, 2014 at 2:24 PM, romanman [email protected] wrote:

Closed #102 #102.

—
Reply to this email directly or view it on GitHub
#102 (comment).

from ethereumj.

The first strategy is not so simple ,
because on the #30001 block you have to
remove garbage of block #1 but you have no
way to find out what exact data it is.

@vbuterin

from ethereumj.

The idea is that when you do a trie update during block B, and that ends up
removing nodes [n1 ... nk], you create a separate data structure, where you
store (B, n1), (B, n2) ... (B, nk). Then, at block B + 30000, you go
through the deletion list left to right destroying everything of the form
(B, x). If you're at B + 20000 and you want to revert to B + 10000, you
remove all pairs of the form (x, i) for B - 20000 < x < B - 10000 from the
deletion list (don't remove the actual nodes). This should be doable with a
database that has next/prev operators.

On Sun, Sep 14, 2014 at 2:38 PM, romanman [email protected] wrote:

The first strategy is not so simple ,
because on the #30001 block you have to
remove garbage of block #1 #1
but you have no
way to find out what exact data it is.

@vbuterin https://github.com/vbuterin

—
Reply to this email directly or view it on GitHub
#102 (comment).

from ethereumj.

This should be doable with a database that has next/prev operators.

The Java implementation of Level DB currently doesn't have reverse iteration/seeking. dain/leveldb#8

from ethereumj.

kk, next iterators only will suffice.

On Sun, Sep 14, 2014 at 3:21 PM, Nick Savers [email protected]
wrote:

This should be doable with a database that has next/prev operators.

The Java implementation of Level DB currently doesn't have reverse
iteration/seeking.
dain/leveldb#8 dain/leveldb#8

—
Reply to this email directly or view it on GitHub
#102 (comment).

from ethereumj.