[Performance] Linear scan for deduplication candidates — O(n) complexity kills performance on large vaults

[anshul23102]

Executive Summary

Finding deduplication candidates requires scanning all blocks linearly. On vaults with millions of blocks, this becomes prohibitively slow.

Proposed Solution

use std::collections::HashMap;

pub struct ContentIndex {
  // Hash of first 8KB chunk -> list of block IDs with this hash
  chunk_index: HashMap<[u8; 32], Vec<u64>>,
}

impl ContentIndex {
  pub fn find_similar_blocks(&self, new_block: &[u8]) -> Vec<u64> {
    let chunk_hash = self.hash_first_chunk(new_block);
    self.chunk_index
      .get(&chunk_hash)
      .cloned()
      .unwrap_or_default()
  }
  
  fn hash_first_chunk(&self, data: &[u8]) -> [u8; 32] {
    let chunk_size = 8192;
    let chunk = if data.len() > chunk_size {
      &data[0..chunk_size]
    } else {
      data
    };
    hash_sha256(chunk)
  }
}

Checklist

• I have searched existing issues and confirmed this is not a duplicate
• I have read the CONTRIBUTING.md guidelines
• I have provided clear steps to reproduce the issue
• I have described expected vs. actual behavior clearly
• This issue title is clear and specific
• This repository has been verified as NSOC on https://www.nsoc.in/projects

@Rakshat28 Could you please /assign this issue to me? I would like to implement block indexing under NSOC '26.

/assign