Skip to content

Commit c5b4293

Browse files
dappliondapplion
committed
Prune descendants of finalized checkpoint not finalized block
1 parent 28d7b74 commit c5b4293

File tree

2 files changed

+71
-30
lines changed

2 files changed

+71
-30
lines changed

‎beacon_node/beacon_chain/src/migrate.rs‎

Lines changed: 67 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -557,18 +557,38 @@ impl<E: EthSpec, Hot: ItemStore<E>, Cold: ItemStore<E>> BackgroundMigrator<E, Ho
557557
);
558558
}
559559

560-
// From the DAG compute the list of roots that descend from finalized root up to the
561-
// split slot.
562-
563-
let finalized_and_descendant_block_roots = HashSet::<Hash256>::from_iter(
564-
std::iter::once(new_finalized_checkpoint.root).chain(
565-
// Note: The sanity check above for existance of at least one summary with
566-
// new_finalized_checkpoint.root should ensure that this call never errors
567-
block_summaries_dag
568-
.descendant_block_roots_of(&new_finalized_checkpoint.root)
569-
.map_err(PruningError::SummariesDagError)?,
570-
),
571-
);
560+
// `new_finalized_state_hash` is the *state at the slot of the finalized epoch*,
561+
// rather than the state of the latest finalized block. These two values will only
562+
// differ when the first slot of the finalized epoch is a skip slot.
563+
let finalized_and_descendant_state_roots_of_finalized_checkpoint =
564+
HashSet::<Hash256>::from_iter(
565+
std::iter::once(new_finalized_state_hash).chain(
566+
state_summaries_dag
567+
.descendants_of(&new_finalized_state_hash)
568+
.map_err(PruningError::SummariesDagError)?,
569+
),
570+
);
571+
572+
// Collect all `latest_block_roots` of the
573+
// finalized_and_descendant_state_roots_of_finalized_checkpoint set. Includes the finalized
574+
// block as `new_finalized_state_hash` always has a latest block root the finalized block.
575+
let finalized_and_descendant_block_roots_of_finalized_checkpoint =
576+
HashSet::<Hash256>::from_iter(
577+
finalized_and_descendant_state_roots_of_finalized_checkpoint
578+
.iter()
579+
.map(|state_root| {
580+
// `.get()` should never error, we just constructed
581+
// finalized_and_descendant_state_roots_of_finalized_checkpoint from the
582+
// state_summaries_dag
583+
let summary = state_summaries_dag.get(state_root).ok_or(
584+
PruningError::SummariesDagError(
585+
SummariesDagError::MissingStateSummary(*state_root),
586+
),
587+
)?;
588+
Ok(summary.latest_block_root)
589+
})
590+
.collect::<Result<Vec<_>, PruningError>>()?,
591+
);
572592

573593
// Note: ancestors_of includes the finalized state root
574594
let newly_finalized_state_summaries = state_summaries_dag
@@ -603,34 +623,49 @@ impl<E: EthSpec, Hot: ItemStore<E>, Cold: ItemStore<E>> BackgroundMigrator<E, Ho
603623
let mut blocks_to_prune: HashSet<Hash256> = HashSet::new();
604624
let mut states_to_prune: HashSet<(Slot, Hash256)> = HashSet::new();
605625

606-
for (slot, summaries) in state_summaries_dag.summaries_by_slot_ascending() {
626+
// Consider the following block tree where we finalize block `[0]` at the checkpoint `(f)`.
627+
// There's a block `[3]` that descendends from the finalized block but NOT from the
628+
// finalized checkpoint. The block tree rooted in `[3]` conflicts with finality and must be
629+
// pruned. Therefore we collect all state summaries descendant of `(f)`.
630+
//
631+
// finalize epoch boundary
632+
// | /-------[2]-----
633+
// [0]-------|--(f)--[1]----------
634+
// \---[3]--|-----------------[4]
635+
// |
636+
637+
for (_, summaries) in state_summaries_dag.summaries_by_slot_ascending() {
607638
for (state_root, summary) in summaries {
608-
let should_prune =
609-
if finalized_and_descendant_block_roots.contains(&summary.latest_block_root) {
610-
// Keep this state is the post state of a viable head, or a state advance from a
611-
// viable head.
612-
false
613-
} else {
614-
// Everything else, prune
615-
true
616-
};
639+
let should_prune = if finalized_and_descendant_state_roots_of_finalized_checkpoint
640+
.contains(&state_root)
641+
{
642+
// This state is a viable descendant of the finalized checkpoint, so does not
643+
// conflict with finality and can be built on or become a head
644+
false
645+
} else {
646+
// Everything else, prune
647+
true
648+
};
617649

618650
if should_prune {
619651
// States are migrated into the cold DB in the migrate step. All hot states
620652
// prior to finalized can be pruned from the hot DB columns
621-
states_to_prune.insert((slot, state_root));
653+
states_to_prune.insert((summary.slot, state_root));
622654
}
623655
}
624656
}
625657

626658
for (block_root, slot) in block_summaries_dag.iter() {
627659
// Blocks both finalized and unfinalized are in the same DB column. We must only
628-
// prune blocks from abandoned forks. Deriving block pruning from state
629-
// summaries is tricky since now we keep some hot state summaries beyond
630-
// finalization. We will only prune blocks that still have an associated hot
631-
// state summary, are above prior finalization and not in the canonical chain.
632-
let should_prune = if finalized_and_descendant_block_roots.contains(&block_root) {
633-
// Keep unfinalized blocks descendant of finalized + finalized block itself
660+
// prune blocks from abandoned forks. Note that block pruning and state pruning differ.
661+
// The blocks DB column is shared for hot and cold data, while the states have different
662+
// columns. Thus, we only prune unviable blocks or from abandoned forks.
663+
let should_prune = if finalized_and_descendant_block_roots_of_finalized_checkpoint
664+
.contains(&block_root)
665+
{
666+
// Keep unfinalized blocks descendant of finalized checkpoint + finalized block itself
667+
// Note that we anchor this set on the finalied checkpoint instead of the finalized
668+
// block. A diagram above shows a relevant example.
634669
false
635670
} else if newly_finalized_block_roots.contains(&block_root) {
636671
// Keep recently finalized blocks
@@ -664,7 +699,9 @@ impl<E: EthSpec, Hot: ItemStore<E>, Cold: ItemStore<E>> BackgroundMigrator<E, Ho
664699
"newly_finalized_state_roots" => newly_finalized_state_roots.len(),
665700
"newly_finalized_states_min_slot" => newly_finalized_states_min_slot,
666701
"state_summaries_count" => state_summaries_dag.summaries_count(),
667-
"finalized_and_descendant_block_roots" => finalized_and_descendant_block_roots.len(),
702+
"state_summaries_dag_roots" => ?state_summaries_dag_roots,
703+
"finalized_and_descendant_state_roots_of_finalized_checkpoint" => finalized_and_descendant_state_roots_of_finalized_checkpoint.len(),
704+
"finalized_and_descendant_state_roots_of_finalized_checkpoint" => finalized_and_descendant_state_roots_of_finalized_checkpoint.len(),
668705
"blocks_to_prune_count" => blocks_to_prune.len(),
669706
"states_to_prune_count" => states_to_prune.len(),
670707
"blocks_to_prune" => ?blocks_to_prune,

‎beacon_node/beacon_chain/src/summaries_dag.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -153,6 +153,10 @@ impl StateSummariesDAG {
153153
Ok(Self::new(state_summaries))
154154
}
155155

156+
pub fn get(&self, state_root: &Hash256) -> Option<&DAGStateSummary> {
157+
self.state_summaries_by_state_root.get(state_root)
158+
}
159+
156160
/// Returns a vec of state summaries that have an unknown parent when forming the DAG tree
157161
pub fn tree_roots(&self) -> Vec<(Hash256, DAGStateSummary)> {
158162
self.state_summaries_by_state_root

0 commit comments

Comments
 (0)