delta-stream 0.32.0

State-aware delta synchronization and recovery for realtime Rust applications
Documentation
use std::collections::VecDeque;

use crate::smart_delta::SmartDeltaKind;

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct ChangeProfile {
    pub previous_len: usize,
    pub current_len: usize,
    pub changed_bytes: usize,
    pub changed_runs: usize,
    pub common_prefix: usize,
    pub common_suffix: usize,
}

impl ChangeProfile {
    pub fn analyze(previous: &[u8], current: &[u8]) -> Self {
        let common = previous.len().min(current.len());
        let mut changed_bytes = previous.len().abs_diff(current.len());
        let mut changed_runs = 0usize;
        let mut in_run = false;
        for i in 0..common {
            let changed = previous[i] != current[i];
            if changed {
                changed_bytes += 1;
                if !in_run {
                    changed_runs += 1;
                }
            }
            in_run = changed;
        }
        let mut prefix = 0usize;
        while prefix < common && previous[prefix] == current[prefix] {
            prefix += 1;
        }
        let mut suffix = 0usize;
        let suffix_limit = common.saturating_sub(prefix);
        while suffix < suffix_limit
            && previous[previous.len() - 1 - suffix] == current[current.len() - 1 - suffix]
        {
            suffix += 1;
        }
        Self {
            previous_len: previous.len(),
            current_len: current.len(),
            changed_bytes,
            changed_runs,
            common_prefix: prefix,
            common_suffix: suffix,
        }
    }

    pub fn change_ratio(&self) -> f64 {
        let denom = self.previous_len.max(self.current_len).max(1);
        self.changed_bytes as f64 / denom as f64
    }

    pub fn resized(&self) -> bool {
        self.previous_len != self.current_len
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SelectorPolicy {
    pub sparse_ratio: u8,
    pub range_run_limit: usize,
    pub explore_every: u64,
    pub winner_window: usize,
}

impl Default for SelectorPolicy {
    fn default() -> Self {
        Self {
            sparse_ratio: 8,
            range_run_limit: 64,
            explore_every: 64,
            winner_window: 64,
        }
    }
}

#[derive(Debug, Clone)]
pub struct StrategyAdvisor {
    policy: SelectorPolicy,
    recent_winners: VecDeque<SmartDeltaKind>,
    updates: u64,
    compression_attempts: u64,
    compression_wins: u64,
}

impl StrategyAdvisor {
    pub fn new(policy: SelectorPolicy) -> Self {
        Self {
            policy,
            recent_winners: VecDeque::with_capacity(policy.winner_window.max(1)),
            updates: 0,
            compression_attempts: 0,
            compression_wins: 0,
        }
    }

    pub fn shortlist(&self, profile: ChangeProfile) -> Vec<SmartDeltaKind> {
        if profile.resized() {
            return vec![SmartDeltaKind::Splice, SmartDeltaKind::Chunks];
        }
        if let Some(winner) = self.dominant_winner() {
            if !self.should_explore() {
                return vec![winner];
            }
        }
        let pct = profile.change_ratio() * 100.0;
        if pct <= self.policy.sparse_ratio as f64 {
            vec![SmartDeltaKind::Sparse, SmartDeltaKind::Ranges]
        } else if profile.changed_runs <= self.policy.range_run_limit {
            vec![SmartDeltaKind::Ranges, SmartDeltaKind::Sparse]
        } else if pct >= 45.0 {
            vec![SmartDeltaKind::Xor, SmartDeltaKind::Ranges]
        } else {
            vec![SmartDeltaKind::Ranges, SmartDeltaKind::Sparse]
        }
    }

    pub fn observe_winner(&mut self, kind: SmartDeltaKind) {
        self.updates = self.updates.saturating_add(1);
        if self.recent_winners.len() == self.policy.winner_window.max(1) {
            self.recent_winners.pop_front();
        }
        self.recent_winners.push_back(kind);
    }

    pub fn observe_no_delta(&mut self) {
        self.updates = self.updates.saturating_add(1);
    }

    pub fn observe_compression(&mut self, won: bool) {
        self.compression_attempts = self.compression_attempts.saturating_add(1);
        if won {
            self.compression_wins = self.compression_wins.saturating_add(1);
        }
    }

    pub fn compression_win_rate(&self) -> f64 {
        if self.compression_attempts == 0 {
            0.0
        } else {
            self.compression_wins as f64 / self.compression_attempts as f64
        }
    }

    pub fn should_compress(&self, payload_len: usize, min_payload: usize) -> bool {
        if payload_len < min_payload {
            return false;
        }
        self.compression_attempts < 16
            || self.compression_win_rate() >= 0.15
            || self.should_explore()
    }

    fn dominant_winner(&self) -> Option<SmartDeltaKind> {
        if self.recent_winners.len() < 8 {
            return None;
        }
        let mut counts = [0usize; 5];
        for k in &self.recent_winners {
            counts[index(*k)] += 1;
        }
        let (idx, count) = counts.into_iter().enumerate().max_by_key(|(_, c)| *c)?;
        if count * 4 < self.recent_winners.len() * 3 {
            return None;
        }
        Some(from_index(idx))
    }

    fn should_explore(&self) -> bool {
        self.policy.explore_every > 0
            && self.updates > 0
            && self.updates.is_multiple_of(self.policy.explore_every)
    }
}

impl Default for StrategyAdvisor {
    fn default() -> Self {
        Self::new(SelectorPolicy::default())
    }
}

fn index(k: SmartDeltaKind) -> usize {
    match k {
        SmartDeltaKind::Sparse => 0,
        SmartDeltaKind::Ranges => 1,
        SmartDeltaKind::Xor => 2,
        SmartDeltaKind::Splice => 3,
        SmartDeltaKind::Chunks => 4,
    }
}
fn from_index(i: usize) -> SmartDeltaKind {
    match i {
        0 => SmartDeltaKind::Sparse,
        1 => SmartDeltaKind::Ranges,
        2 => SmartDeltaKind::Xor,
        3 => SmartDeltaKind::Splice,
        _ => SmartDeltaKind::Chunks,
    }
}