HDiff in the hot DB #39

dapplion · 2024-10-31T14:44:22Z

Partial implementation of https://hackmd.io/6WI3idBfR2q2AQyMUfYMyg

beacon_node/beacon_chain/src/migrate.rs

michaelsproul · 2024-12-12T02:55:37Z

beacon_node/store/src/hot_cold_store.rs

+                        state_root,
+                        state_slot: Some(summary.slot),
+                        // Delete the diff as descendants of this state will never be used.
+                        prune_hot_diff: true,


We need to change this to not delete the diff ancestors of the finalized state (use closest_layer_slots somewhere here).

We need to know the ancestor diffs of the new finalized state, so one approach would be:

Reorder migrate_database (hot to freezer migration) prior to pruning heads

Keep hot states which are either after the split, or before the split and descended from it according to the diff hierarchy.

We may want to rewrite the prune_abandoned_forks code, but if we don't want to do that now, we can take the approach above

michaelsproul · 2024-12-12T03:31:52Z

Regarding state summaries stored during state advance (infamous beacon_node/beacon_chain/src/block_verification.rs:1487):

Option 1 (current strategy) is to commit eagerly:

Means storing more on disk in the hot-path of state advance (potentially annoying due to latency from disk I/O and diff computation). However this is mitigated by the state advance routine usually doing this work prior to block import.
Saves memory because we don't need to hold potentially thousands of states in memory until the block is verified and we decide to commit it.

Option 2 (old strategy from ages ago) is to commit on import:

Uses a lot more memory because we need to keep the states around in memory. Naively for 1000 epoch boundary states this could be like 1000 x 0.1 GB = 100 GB = death by OOM.
The advantage of this approach is that we could avoid computing the diffs for the intermediate states until after the block has been imported & added to fork choice. However this is probably not worth it.

Option 3 (don't store intermediate states at all):

Would need to recompute them (and re-do the epoch transition).

beacon_node/beacon_chain/src/block_verification.rs

beacon_node/store/src/impls/beacon_state.rs

michaelsproul · 2024-12-19T01:10:32Z

beacon_node/beacon_chain/src/beacon_chain.rs

+            .viable_heads::<T::EthSpec>(head_slot)
+            .iter()
+            .map(|node| (node.root, node.slot))
+            .collect()


Could use to implement the DB downgrade (recreate the headtracker after it has been deleted)

michaelsproul · 2024-12-19T01:21:48Z

beacon_node/beacon_chain/src/block_verification.rs

+                    // TODO(hdiff): Is it necessary to do this read tx now? Also why is it necessary to
+                    // check that the summary exists at all? Are double writes common? Can this txn
+                    // lock deadlock with the `do_atomically` call?
+                    let txn_lock = chain.store.hot_db.begin_rw_transaction();


The reason for this lock is a race with the write in BeaconChain::import_block:

If we were to write a non-temporary state in import_block in between setting state_already_exists (false) and the write of the temporary state in this function, we can corrupt the DB:

There is a state that is not temporary (required by some fully-imported block),

But it is marked temporary due to the race condition here

Temporary states risk being deleted by pruning -> invalid DB due to deletion of canonical state.

The lock prevents this case by preventing the interleaving of the read in this function with the write in the import function. However this is a bad abstraction forced upon us by LevelDB which lacks proper ACID transactions. If we move away from LevelDB eventually we can maybe have proper transactions, see:

Modularize beacon node backend sigp/lighthouse#4718

beacon_node/beacon_chain/src/builder.rs

michaelsproul · 2024-12-19T01:36:08Z

beacon_node/beacon_chain/src/migrate.rs


        // Persist the new finalized checkpoint as the pruning checkpoint.
        batch.push(StoreOp::KeyValueOp(
            store.pruning_checkpoint_store_op(new_finalized_checkpoint),


Lets delete the pruning_checkpoint while we're here.

https://github.com/sigp/lighthouse/blob/b5f27610ca675d649bbff755b970cea74ba144ad/beacon_node/store/src/hot_cold_store.rs#L2389-L2400

Done in c8d82f0

michaelsproul · 2024-12-19T01:37:28Z

beacon_node/beacon_chain/src/migrate.rs

+            StateSummariesDAG::new(state_summaries, parent_block_roots)
+        };
+
+        // From the DAG compute the list of roots that ascend from finalized root up to the split


Suggested change

// From the DAG compute the list of roots that ascend from finalized root up to the split

// From the DAG compute the list of roots that descend from finalized root up to the split

Fixed with 4fa32cc

michaelsproul · 2024-12-19T01:37:56Z

beacon_node/beacon_chain/src/migrate.rs

+        };
+
+        // From the DAG compute the list of roots that ascend from finalized root up to the split
+        // slot. And run `migrate_database` with it


Suggested change

// slot. And run `migrate_database` with it

// slot.

Fixed with 4fa32cc

michaelsproul · 2024-12-19T01:41:14Z

beacon_node/beacon_chain/src/migrate.rs

+                    // keep those on the finalized canonical chain. Note that there may be lingering
+                    // forks.


Suggested change

// keep those on the finalized canonical chain. Note that there may be lingering

// forks.

// keep those on the finalized canonical chain. Checking the state root ensures we avoid lingering forks.

Fixed with 4fa32cc

michaelsproul · 2024-12-19T01:44:41Z

beacon_node/beacon_chain/src/migrate.rs

-                    // Abandoned forks will never be used, so we can safely delete the diffs
-                    prune_hot_diff: true,
-                }]
+                // Abandoned forks will never be used, so we can safely delete the diffs


Noting this now includes:

Abandoned forks (not descended from finalized)

Old stuff that wasn't pruned previously but is getting pruned now (older than previous finalization)

Finalized states from the canonical chain which are not required by the HDiff mechanism.

Updated the comments

michaelsproul · 2024-12-19T01:45:29Z

beacon_node/beacon_chain/src/migrate.rs


        // Persist the head in case the process is killed or crashes here. This prevents
        // the head tracker reverting after our mutation above.
        let persisted_head = PersistedBeaconChain {


We could remove this write, and probably delete the PersistedBeaconChain altogether.

Fixed with 9ce4b33, but to fully remove PersistedBeaconChain we need to have a way to compute the genesis state root and genesis block root when booting from an existing DB. The issue is that while the state is in the DB it is keyed by root which we don't know.

michaelsproul · 2024-12-19T02:03:30Z

beacon_node/store/src/hot_cold_store.rs

+
+    pub fn hot_hdiff_start_slot(&self) -> Slot {
+        // TODO(hdiff): read the start slot from somewhere
+        todo!();


I was thinking maybe we could recycle the anchor_slot for use here, as it is fairly useless and not used for much. The only load-bearing use of the anchor_slot that I can find is in try_prune_execution_payloads where it is used to halt the pruning process. However, this is not necessary as we could either:

Keep iterating back to Bellatrix, or

Stop iterating back once we find a payload that is missing, or

Use the oldest_block_slot to determine when to stop iterating back. This is my preferred option, as it is also compatible with storing execution payloads older than the anchor_slot, i.e. Store execution payloads during backfill if --prune-payloads false sigp/lighthouse#6510

Conclusion: we can recycle the anchor_slot field and set it to the epoch-aligned slot of the snapshot state (not the slot of the checkpoint block, which might be older due to skipped slots).

Fixed on 5ecf9db

dapplion · 2024-12-24T19:42:10Z

Branch with commit history https://github.com/dapplion/lighthouse/pull/new/tree-states-hot-backup

squashed and rebase on top of sigp/unstable

dapplion · 2024-12-25T12:39:45Z

I have done manual testing and this branch works on mainnet:

starting the node from genesis
starting the node with fresh DB and checkpoint sync (not aligned epoch to hdiff snapshot)
starting the node from an existing DB with at least 100 slots of history

All of them were broken originally, there's a lot of commits https://github.com/dapplion/lighthouse/pull/new/tree-states-hot-backup to make them work. I have also rebased to unstable, it was quite easy.

For 3. I had to add a new column to store the new hot state summaries. Otherwise when diffing it will try to read a V22 summary and break.

dapplion · 2024-12-26T14:17:04Z

@michaelsproul If we stop updating the head_tracker in the persisted head, how can we downgrade safely? If you run an old version of Lighthouse it will read the persisted head which contains an empty head tracker.

dapplion · 2025-01-09T01:19:13Z

beacon_node/store/src/lib.rs

+    ///
+    /// This column is populated after DB schema version 23 superseding `BeaconStateSummary`. The
+    /// new column is necessary to have a safe migration without data loss.
+    #[strum(serialize = "bs3")]


Suggested change

#[strum(serialize = "bs3")]

#[strum(serialize = "hss")]

dapplion · 2025-01-09T01:53:05Z

RE pruning routine:

Iterate summaries from finalized state jumping by diff base root, and keep only those. required_finalized_diff_state_slots = to the diff path of the finalized state

dapplion · 2025-01-09T01:59:28Z

delete this line https://github.com/dapplion/lighthouse/pull/39/files#diff-3ae67ec6dc8a5c3f1bed97ea1d5d397762c2c8ec4783a8509aeda6312a40d65eR646

dapplion · 2025-01-09T02:04:46Z

loop on each block and state to prune and log on separate lines so there's not a single giant dump of potentially megabytes

lighthouse/beacon_node/beacon_chain/src/migrate.rs

Line 680 in ee13a1f

"states_to_prune" => ?states_to_prune,

dapplion · 2025-01-09T02:05:22Z

change to "not copying state to freezer DB"

lighthouse/beacon_node/store/src/hot_cold_store.rs

Line 3252 in ee13a1f

debug!(store.log, "Pruning finalized state"; "slot" => slot);

pruning not happening here

dapplion · 2025-03-06T17:53:16Z

Closing for Hierarchical state diffs in hot DB sigp/lighthouse#6750

The head tracker is a persisted piece of state that must be kept in sync with the fork-choice. It has been a source of pruning issues in the past, so we want to remove it - see #1785 When implementing tree-states in the hot DB we have to change the pruning routine (more details below) so we want to do those changes first in isolation. - see #6580 - If you want to see the full feature of tree-states hot dapplion#39 Closes #1785 **Current DB migration routine** - Locate abandoned heads with head tracker - Use a roots iterator to collect the ancestors of those heads can be pruned - Delete those abandoned blocks / states - Migrate the newly finalized chain to the freezer In summary, it computes what it has to delete and keeps the rest. Then it migrates data to the freezer. If the abandoned forks routine has a bug it can break the freezer migration. **Proposed migration routine (this PR)** - Migrate the newly finalized chain to the freezer - Load all state summaries from disk - From those, just knowing the head and finalized block compute two sets: (1) descendants of finalized (2) newly finalized chain - Iterate all summaries, if a summary does not belong to set (1) or (2), delete This strategy is more sound as it just checks what's there in the hot DB, computes what it has to keep and deletes the rest. Because it does not rely and 3rd pieces of data we can drop the head tracker and pruning checkpoint. Since the DB migration happens **first** now, as long as the computation of the sets to keep is correct we won't have pruning issues.

michaelsproul assigned michaelsproul and dapplion Nov 21, 2024

dapplion force-pushed the tree-states-hot branch from 3025158 to 8eaee8d Compare December 10, 2024 12:23

michaelsproul reviewed Dec 12, 2024

View reviewed changes

beacon_node/beacon_chain/src/migrate.rs Outdated Show resolved Hide resolved

michaelsproul reviewed Dec 12, 2024

View reviewed changes

beacon_node/beacon_chain/src/block_verification.rs Outdated Show resolved Hide resolved

michaelsproul reviewed Dec 12, 2024

View reviewed changes

beacon_node/store/src/impls/beacon_state.rs Outdated Show resolved Hide resolved

dapplion force-pushed the tree-states-hot branch from dcce765 to 0a230ec Compare December 18, 2024 11:32

michaelsproul reviewed Dec 19, 2024

View reviewed changes

beacon_node/beacon_chain/src/builder.rs Outdated Show resolved Hide resolved

michaelsproul reviewed Dec 19, 2024

View reviewed changes

dapplion force-pushed the tree-states-hot branch 7 times, most recently from 06f6177 to f4d44e4 Compare December 24, 2024 18:44

dapplion changed the base branch from tree-states-archive to unstable December 24, 2024 19:23

HDiff in the hot DB - squashed

fbc62f2

dapplion force-pushed the tree-states-hot branch from 1860064 to fbc62f2 Compare December 24, 2024 19:42

dapplion added 3 commits December 25, 2024 12:04

lint

f21c4b8

Attribute store ssz errors

f460b59

Debug db opening issue

ff69ee0

dapplion force-pushed the tree-states-hot branch from 007727e to ff69ee0 Compare December 25, 2024 04:45

dapplion added 4 commits December 25, 2024 12:50

Load partial split first

926330e

More logs in migration

0a33dcc

More logs on migration

889a968

Write new hot state summaries in different column

ee13a1f

dapplion force-pushed the tree-states-hot branch from e033b3b to ee13a1f Compare December 25, 2024 09:04

This was referenced Dec 28, 2024

Drop head tracker for summaries DAG sigp/lighthouse#6744

Merged

Use oldest_block_slot to break off pruning payloads sigp/lighthouse#6745

Merged

Hierarchical state diffs in hot DB sigp/lighthouse#6750

Merged

dapplion commented Jan 9, 2025

View reviewed changes

dapplion closed this Mar 6, 2025

	// From the DAG compute the list of roots that ascend from finalized root up to the split
	// From the DAG compute the list of roots that descend from finalized root up to the split

		// keep those on the finalized canonical chain. Note that there may be lingering
		// forks.

HDiff in the hot DB #39

HDiff in the hot DB #39

Uh oh!

Conversation

dapplion commented Oct 31, 2024

Uh oh!

Uh oh!

michaelsproul Dec 12, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

michaelsproul commented Dec 12, 2024

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

michaelsproul Dec 19, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dapplion commented Dec 24, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dapplion commented Dec 25, 2024

Uh oh!

dapplion commented Dec 26, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dapplion commented Jan 9, 2025

Uh oh!

dapplion commented Jan 9, 2025

Uh oh!

dapplion commented Jan 9, 2025

Uh oh!

dapplion commented Jan 9, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dapplion commented Mar 6, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

michaelsproul Dec 12, 2024 •

edited

Loading

michaelsproul Dec 19, 2024 •

edited

Loading

dapplion commented Dec 24, 2024 •

edited

Loading

dapplion commented Jan 9, 2025 •

edited

Loading