Database pruning for Gossamer

[dutterbutter]

Database pruning for Gossamer

Overview

This presents two possible state trie pruning algorithms to be included in Gossamer. These are the current production algorithms for Geth and Substrate.

To describe both algorithms the following terminology will be used

• $N$ - The current highest block head
• $X$ - The number of states prior to the head that should be kept and not pruned
• State Window = [N-X : N] - The range of block heights for which the state should be stored. This shifts with each new block that is added.

Bloom Filtering (Geth)

A Bloom filter is a data structure for efficiently testing set inclusion. Elements can be added to the filter in $O(1)$ and elements can be tested for inclusion in $O(1)$. It operates probabilistically so it can determine if an element is defintely not in the set or if it probably is in the set with some fixed error probability for false positives.

A Bloom filter is constructed by traversing the state trie for each block in the state window. Each node in each state trie is added to the bloom filter.

The algorithm works as follows:

• For each block in the state window, traverse its state trie and add all nodes to the Bloom filter
• Test every node in the database for inclusion
  • Nodes that are definitely not used inside the window are deleted.
  • Others are kept

Some small percentage if nodes that should be deleted will be kept due to the error rate of the bloom filter but this can be very small (<0.01%). The algorithm scales linearly in the number of trie nodes in the db and the size of the state tries. A Bloom filter has constant memory requirements.

This main disadvantage of this approach is its need to be run offline. The node must be stopped and the pruning process run on the database for a fixed window. Despite this it is a solution that is simple to understand and implement and can be implemented externally to the main block processing loop. This would be a good short term solution.

This solution is discounted in a Geth PR but is later implemented and is the current pruning solution.

Initial development work can be found here: feat(cmd): Add offline pruning of state trie

In-memory Deathlists (Substrate)

Substrate uses an online algorithm to remove trie nodes for blocks when they leave the state window.

For a state look back window of size $X$, it maintains $X$ deathlists in-memory indexed by block hash. Each of these stores the list of hashes of nodes to be deleted when the block leaves the look back window.

The main consideration for this algorithm is that a block can be deleted (added to a deathlist) and then re-added to a trie later. When adding a new node all existing deathlists must be checked to make sure it isn't already marked for deletion.

This works as follows:

• For each new block added, compute the set of incoming (added to the trie, not from the previous state) and outgoing (removed from the trie) nodes. (check - can this be done cheaply without reference counting?)
• The outgoing nodes are added to the new deathlist for this block that is stored in-memory
• All deathlists in the current window are checked for nodes in the incoming list. If any are found they are removed from the deathlists
• For the block that just left the window all nodes that still remain in its deathlist are deleted from the db and the deathlist itself is deleted

This solves the pruning issue assuming blocks cannot be applied and then rolled back. Supporting this requires an additional journaling step that allows the modifications to the deathlists to be rolled back as well.

Let $I$ and $O$ be the average number of incoming and outgoing nodes respectively. The resource requirements for this approach are:

• Storing $X * O$ hashes in memory
• $XOI$ in-memory comparisons
• $O$ database deletions

per block.

This approach is simple to understand and works online, however, it requires modifications to the block creation cycle and adds constant memory and work overhead.

The Substrate implementation is available here

Proposed Implementation | In-memory Deathlists (Substrate)

Gossamer Online State Trie Pruning

Step 1: State Trie Diff

Get the diff(inserted and deleted keys) of state trie of current finalized block and previously finalized block, that will be used as deleted keys in JournalRecord

Step 2:

Initialize Journal Record

Initialized journal record by using state trie diff, and store the record in DB using pruning_journal key

Journal Record

When block is finalized, create a journal record with the state trie diff and persist that record as the meta data for the block

type JournalRecord struct {
    blockHash,
    // Hash of keys that are inserted into state trie of the block

    inserted keys []keyHash, 
    // Hash of keys that are deleted from state trie of the block
    deleted keys []keyHash,
}

Journal Key

We need to persist the JournalRecord to recover it in case of crash.
It is persisted in DB with journal key as the entry key.
journalKey = pruning_journal (prefix) + block number

Step 3:

Window

• It tracks a list of blocks identified by header hash.
• The in-memory DeathList is a queue of DeathRow.
• DeathRow contains keys that got deleted for each block in the pruning window.
• DeathIndex stores all the keys store in the entire DeathList. This serves as an inverted index to check if a key is already in a DeathRow of a block.

Death Row

type DeathRow struct{
    blockHash,
    journalkey,
    deleted: map[keyHash]nil // keys hash that will be deleted from DB
}

Initialize Death Row

1. Remove the key from DeathList and from DeathRow using DeathIndex if that key is re-inserted into state trie of finalized block.
2. Store the keys that is deleted from state trie into DeathIndex.
3. Create a DeathRow and add it to DeathList.

Step 4: (Background Pruning)

Pruning

Pruner will have maxBlock which is the total blocks from head after which all block will be pruned.

1. Get the first element(DeathRow) from DeathList , remove all the deleted field keys of DeathRow from DB and DeathIndex
2. Store the last pruned index with last_pruned key prefix in DB

[dutterbutter]

Implementations of above discussed pruning solutions can be viewed here:

• feat(cmd): Add offline pruning of state trie
• feat(dot/state): Implement online pruning of state tries

Great work! @arijitAD