Tweak hdiff buffer sizes

[michaelsproul]

In this PR we noticed some improvements to xdelta buffers that could be made:

• Fix xdelta3 output buffer issue #7174

They are tagged with TODO(hdiff), see that PR for details.

This will probably require a DB migration to address (adding the output buffer size to the HDiff on disk).

[hopinheimer]

is this up for grabs? @michaelsproul

[michaelsproul]

Yes, it is!

Here's a bit more detail:

We want to add a field to BytesDiff which is the output_length, i.e. the size of the output data (state bytes) after applying the BytesDiff to its intended input (pre state).

lighthouse/beacon_node/store/src/hdiff.rs

Lines 153 to 156 in fcbec47

	#[derive(Debug, PartialEq, Encode, Decode)]
	pub struct BytesDiff {
	bytes: Vec<u8>,
	}

This will require adding a new V1 variant to HDiff, which will have either a BytesDiffV0 (for HDiffV0) or a BytesDiffV1 (for HDiffV1) as a field.

lighthouse/beacon_node/store/src/hdiff.rs

Lines 108 to 151 in fcbec47

	/// Hierarchical state diff.
	///
	/// Splits the diff into two data sections:
	///
	/// - **balances**: The balance of each active validator is almost certain to change every epoch.
	/// So this is the field in the state with most entropy. However the balance changes are small.
	/// We can optimize the diff significantly by computing the balance difference first and then
	/// compressing the result to squash those leading zero bytes.
	///
	/// - **everything else**: Instead of trying to apply heuristics and be clever on each field,
	/// running a generic binary diff algorithm on the rest of fields yields very good results. With
	/// this strategy the HDiff code is easily mantainable across forks, as new fields are covered
	/// automatically. xdelta3 algorithm showed diff compute and apply times of ~200 ms on a mainnet
	/// state from Apr 2023 (570k indexes), and a 92kB diff size.
	#[superstruct(
	variants(V0),
	variant_attributes(derive(Debug, PartialEq, Encode, Decode))
	)]
	#[derive(Debug, PartialEq, Encode, Decode)]
	#[ssz(enum_behaviour = "union")]
	pub struct HDiff {
	state_diff: BytesDiff,
	balances_diff: CompressedU64Diff,
	/// inactivity_scores are small integers that change slowly epoch to epoch. And are 0 for all
	/// participants unless there's non-finality. Computing the diff and compressing the result is
	/// much faster than running them through a binary patch algorithm. In the default case where
	/// all values are 0 it should also result in a tiny output.
	inactivity_scores_diff: CompressedU64Diff,
	/// The validators array represents the vast majority of data in a BeaconState. Due to its big
	/// size we have seen the performance of xdelta3 degrade. Comparing each entry of the
	/// validators array manually significantly speeds up the computation of the diff (+10x faster)
	/// and result in the same minimal diff. As the `Validator` record is unlikely to change,
	/// maintaining this extra complexity should be okay.
	validators_diff: ValidatorsDiff,
	/// `historical_roots` is an unbounded forever growing (after Capella it's
	/// historical_summaries) list of unique roots. This data is pure entropy so there's no point
	/// in compressing it. As it's an append only list, the optimal diff + compression is just the
	/// list of new entries. The size of `historical_roots` and `historical_summaries` in
	/// non-trivial ~10 MB so throwing it to xdelta3 adds CPU cycles. With a bit of extra complexity
	/// we can save those completely.
	historical_roots: AppendOnlyDiff<Hash256>,
	/// See historical_roots
	historical_summaries: AppendOnlyDiff<HistoricalSummary>,
	}

For backwards-compatibility, we should support both types of diffs throughout the whole diff process. E.g. when loading from disk, we should read the enum tag and use it to decode the correct variant (this should be handled automatically by

lighthouse/beacon_node/store/src/hdiff.rs

Line 127 in fcbec47

#[ssz(enum_behaviour = "union")]

, but we should have a test that confirms this).

When applying the diff, we should use the output_length when available, here:

lighthouse/beacon_node/store/src/hdiff.rs

Lines 348 to 350 in fcbec47

	// TODO(hdiff): Dynamic buffer allocation. This is a stopgap until we implement a schema
	// change to store the output buffer size inside the `BytesDiff`.
	let mut output_length = ((source.len() + self.bytes.len()) * 3) / 2;

And when computing new diffs for storage, we should default to V1:

lighthouse/beacon_node/store/src/hdiff.rs

Line 255 in fcbec47

let state_diff = BytesDiff::compute(&source.state, &target.state)?;

Finally, we'll also need a schema update implemented here:

https://github.com/sigp/lighthouse/blob/tree-states-hot-rebase/beacon_node/beacon_chain/src/schema_change.rs

The guide to writing schema migrations has some details:

https://github.com/sigp/lighthouse/tree/tree-states-hot-rebase/beacon_node/beacon_chain/src/schema_change

For simplicity, I think we should base this change off tree-states-hot-rebase (schema V24) as schema V25. The schema downgrade would convert all HDiffV1s in the DB to HDiffV0s.