statement-store: Unbounded expired HashMap causes ~9GB+ memory bloat during high throughput

[DenzelPenzel]

Is there an existing issue?

• I have searched the existing issues

Experiencing problems? Have you tried our Stack Exchange first?

• This is not a support question.

Request

The statement store maintains an in-memory expired:

polkadot-sdk/substrate/client/statement-store/src/lib.rs

Line 235 in ae772b4

expired: HashMap<Hash, u64>, // Value is expiration timestamp.

that tracks hashes of removed/evicted statements to prevent peers from re-gossiping them.

1. Unbounded growth, unlike entries (capped at 4M statements / 2GiB), the expired map has no capacity limit
2. Inefficient purge

   polkadot-sdk/substrate/client/statement-store/src/lib.rs

   Line 456 in ae772b4

   self.expired.retain(|hash, timestamp| {

During high-throughput scenarios the expired map grows to ~100M entries, consuming an estimated ~9GB of RAM (100M entries × 104 bytes: 32-byte hash + 8-byte timestamp + ~64 bytes HashMap overhead)

Solution

Replace the flat HashMap<Hash, u64> with a time-bucketed ExpiredIndex:

struct ExpiredIndex {
      /// O(1) dedup lookup (hash -> bucket_id)
      lookup: HashMap<Hash, u64>,                                                                                                      
      /// Time buckets ordered by age (bucket_id -> set of hashes)
      buckets: BTreeMap<u64, HashSet<Hash>>,                                                                                           
  }                  

Are you willing to help with this request?

Yes!

[alexggh]

that tracks hashes of removed/evicted statements to prevent peers from re-gossiping them.

I think we can optimise this further, only evicted statements hashes need to make it to the Expired. The ones that we removed because their expiry time is past current time we don't need to store them in the ExpiryIndex at all, because they will be quickly rejected here:

[		if self.timestamp() >= statement.get_expiration_timestamp_secs().into() {](https://github.com/paritytech/polkadot-sdk/blob/ae772b4edb58afa4499e46d97245e303605170bb/substrate/client/statement-store/src/lib.rs#L1306)