Skip to main content

shard_telemetry/
locality.rs

1//! Model-free compression-locality collation.
2//!
3//! Records receive a cheap integer temperature on ingress, but placement is a
4//! block decision. A full block is scored against stripe-local compression
5//! shards, split with farthest-point seeds when its internal variance is high,
6//! and handed to the nearest shard in bounded owned byte prefixes.
7
8use std::collections::VecDeque;
9use std::mem::size_of;
10use std::ops::Range;
11
12use bytes::{BufMut, Bytes, BytesMut};
13use bytes_handoff::{HandoffBuffer, HandoffBufferConfig, HandoffBufferPolicy};
14
15use crate::{CompressionCohortId, MetadataField, TelemetryError, TelemetryResult};
16
17const MAX_ROUTER_STATE_BYTES: usize = 512 * 1024;
18const MAX_COMPRESSION_SHARDS: usize = 16;
19const MAX_SPLIT_DEPTH: u8 = 2;
20const SPLIT_EXPLORATION_SLOTS: usize = 64;
21const SPLIT_FAILURES_BEFORE_BACKOFF: u8 = 2;
22const SPLIT_BACKOFF_BLOCKS: u8 = 63;
23const INDEX_BYTES: usize = size_of::<u32>();
24const SHAPE_MISMATCH_DISTANCE: u8 = 4;
25const MAX_LOCALITY_DISTANCE: u8 = 16 + SHAPE_MISMATCH_DISTANCE;
26
27const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
28const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
29const BASE_PLACEMENT_DOMAIN: u64 = 0x3a72_3e4b_b78f_19d5;
30const COLLATED_PLACEMENT_DOMAIN: u64 = 0xd6e8_feb8_6659_fd93;
31
32/// Stable identifier for a final compression placement.
33///
34/// Placement IDs select active blocks and immutable compression dictionaries.
35/// They are independent of the producer-derived source cohort.
36#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
37pub struct CompressionPlacementId(u64);
38
39impl CompressionPlacementId {
40    /// Creates a placement identifier from a stable raw value.
41    #[must_use]
42    pub const fn new(value: u64) -> Self {
43        Self(value)
44    }
45
46    /// Returns the raw placement identifier.
47    #[must_use]
48    pub const fn get(self) -> u64 {
49        self.0
50    }
51
52    /// Returns the deterministic fail-open placement for a source cohort.
53    #[must_use]
54    pub fn from_source_cohort(source: CompressionCohortId) -> Self {
55        Self(splitmix64(source.get() ^ BASE_PLACEMENT_DOMAIN))
56    }
57
58    fn from_temperature(
59        source: CompressionCohortId,
60        temperature: CompressionTemperature,
61        shape_hash: u64,
62    ) -> Self {
63        Self(splitmix64(
64            source.get()
65                ^ COLLATED_PLACEMENT_DOMAIN
66                ^ u64::from(temperature.get()).rotate_left(19)
67                ^ shape_hash.rotate_right(11),
68        ))
69    }
70}
71
72/// Integer compression-locality temperature.
73///
74/// The bits are a SimHash locality signature, so distance is measured with XOR
75/// Hamming distance rather than numeric subtraction. It affects placement only
76/// and is not needed to decode a block.
77#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
78pub struct CompressionTemperature(u16);
79
80impl CompressionTemperature {
81    /// Creates a temperature from its integer value.
82    #[must_use]
83    pub const fn new(value: u16) -> Self {
84        Self(value)
85    }
86
87    /// Returns the raw integer temperature.
88    #[must_use]
89    pub const fn get(self) -> u16 {
90        self.0
91    }
92
93    /// Returns the Hamming distance between two compression temperatures.
94    #[must_use]
95    pub const fn distance(self, other: Self) -> u8 {
96        (self.0 ^ other.0).count_ones() as u8
97    }
98}
99
100/// Locality class selected for a block.
101#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
102#[repr(u8)]
103pub enum LocalityGranularity {
104    /// Producer-derived OTLP service/scope cohort.
105    Base = 0,
106    /// Block was assigned to an active stripe-local compression shard.
107    Collated = 1,
108}
109
110/// Final owner-local placement decision for one collated block.
111#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
112pub struct CompressionPlacement {
113    /// Stable block and dictionary placement identifier.
114    pub placement_id: CompressionPlacementId,
115    /// Byte-weighted centroid of record temperatures.
116    pub temperature: CompressionTemperature,
117    /// Whether the block uses the base cohort or a compression shard.
118    pub granularity: LocalityGranularity,
119    /// Locality distance from the block centroid to the selected shard.
120    pub distance_to_shard: u8,
121    /// Byte-weighted mean squared locality deviation, Q8.
122    pub internal_variance_q8: u16,
123}
124
125impl CompressionPlacement {
126    /// Returns the fail-open placement for a producer-derived source cohort.
127    #[must_use]
128    pub fn base(source: CompressionCohortId, temperature: CompressionTemperature) -> Self {
129        Self {
130            placement_id: CompressionPlacementId::from_source_cohort(source),
131            temperature,
132            granularity: LocalityGranularity::Base,
133            distance_to_shard: 0,
134            internal_variance_q8: 0,
135        }
136    }
137}
138
139/// Bounded settings for one stripe-local block collator.
140#[derive(Debug, Clone, PartialEq, Eq)]
141pub struct CompressionLocalityConfig {
142    /// Enables block scoring, splitting, and compression-shard placement.
143    pub enabled: bool,
144    /// Maximum active compression shards owned by one stripe.
145    pub max_compression_shards: usize,
146    /// Maximum recursive farthest-seed split depth.
147    pub max_split_depth: u8,
148    /// Minimum records required in each child of a split.
149    pub min_split_records: usize,
150    /// Minimum source bytes required in each child of a split.
151    pub min_split_bytes: u64,
152    /// Split blocks above this byte-weighted Q8 variance.
153    pub split_variance_q8: u16,
154    /// Do not train a specialized shard with a worse leaf variance.
155    pub max_shard_variance_q8: u16,
156    /// Maximum locality distance for assigning a block to an existing shard.
157    pub max_assignment_distance: u8,
158    /// Minimum leaf bytes needed to create a new compression shard.
159    pub min_admission_bytes: u64,
160    /// Maximum memory reserved for persistent collation profiles.
161    pub state_budget_bytes: usize,
162}
163
164impl Default for CompressionLocalityConfig {
165    fn default() -> Self {
166        Self {
167            enabled: false,
168            max_compression_shards: MAX_COMPRESSION_SHARDS,
169            max_split_depth: MAX_SPLIT_DEPTH,
170            min_split_records: 8,
171            min_split_bytes: 64 * 1024,
172            split_variance_q8: 768,
173            max_shard_variance_q8: 3_072,
174            max_assignment_distance: 6,
175            min_admission_bytes: 4 * 1024 * 1024,
176            state_budget_bytes: MAX_ROUTER_STATE_BYTES,
177        }
178    }
179}
180
181impl CompressionLocalityConfig {
182    pub(crate) fn validate(&self) -> Result<(), &'static str> {
183        if self.max_compression_shards == 0 || self.max_compression_shards > MAX_COMPRESSION_SHARDS
184        {
185            return Err("locality max_compression_shards must be between 1 and 16");
186        }
187        if self.max_split_depth > MAX_SPLIT_DEPTH {
188            return Err("locality max_split_depth must be no larger than 2");
189        }
190        if self.min_split_records < 2 {
191            return Err("locality min_split_records must be at least 2");
192        }
193        if self.min_split_bytes == 0 || self.min_admission_bytes == 0 {
194            return Err("locality byte thresholds must be nonzero");
195        }
196        if self.split_variance_q8 == 0 || self.max_shard_variance_q8 < self.split_variance_q8 {
197            return Err("locality variance thresholds are inconsistent");
198        }
199        if self.max_assignment_distance > MAX_LOCALITY_DISTANCE {
200            return Err("locality max_assignment_distance must be no larger than 20");
201        }
202        if self.state_budget_bytes == 0 || self.state_budget_bytes > MAX_ROUTER_STATE_BYTES {
203            return Err("locality state_budget_bytes must be between 1 and 512 KiB");
204        }
205        if estimated_state_bytes(self) > self.state_budget_bytes {
206            return Err("locality tables exceed locality state_budget_bytes");
207        }
208        Ok(())
209    }
210}
211
212/// Allocation-free message analysis used by routing and term indexing.
213#[derive(Debug, Clone, Copy, PartialEq, Eq)]
214pub struct MessageFingerprint {
215    /// Stable template-shape hash with dynamic values removed.
216    pub shape_hash: u64,
217    /// Integer SimHash over static and type-class features.
218    pub locality_signature: u16,
219}
220
221/// One record presented to block collation.
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223pub struct CompressionLocalityRecord {
224    /// Allocation-free message fingerprint.
225    pub fingerprint: MessageFingerprint,
226    /// Logical source bytes contributed by this record.
227    pub source_bytes: u64,
228}
229
230/// Integer score for a complete block or sub-block.
231#[derive(Debug, Clone, Copy, PartialEq, Eq)]
232pub struct CompressionBlockScore {
233    /// Byte-weighted majority-bit centroid.
234    pub temperature: CompressionTemperature,
235    /// Representative exact template-shape hash.
236    pub shape_hash: u64,
237    /// Byte-weighted mean squared locality distance from the centroid, Q8.
238    pub internal_variance_q8: u16,
239    /// Largest record-to-centroid locality distance.
240    pub max_deviation: u8,
241    /// Logical source bytes represented by the score.
242    pub source_bytes: u64,
243    /// Records represented by the score.
244    pub record_count: usize,
245}
246
247/// Final assignment of one complete sub-block.
248#[derive(Debug, Clone)]
249pub struct CompressionBlockAssignment {
250    /// Selected compression shard and block diagnostics.
251    pub placement: CompressionPlacement,
252    /// Score calculated before assignment.
253    pub score: CompressionBlockScore,
254    membership: BlockMembership,
255}
256
257impl CompressionBlockAssignment {
258    /// Iterates original input indices belonging to this sub-block.
259    pub fn record_indices(&self) -> impl ExactSizeIterator<Item = usize> + '_ {
260        self.membership.indices()
261    }
262}
263
264/// Read-only diagnostics for one active compression shard.
265#[derive(Debug, Clone, Copy, PartialEq, Eq)]
266pub struct CompressionShardProfile {
267    /// Stable placement and dictionary identifier.
268    pub placement_id: CompressionPlacementId,
269    /// Producer-derived source cohort isolated by this shard.
270    pub source_cohort: CompressionCohortId,
271    /// Current byte-weighted shard temperature.
272    pub temperature: CompressionTemperature,
273    /// Current representative exact template-shape hash.
274    pub shape_hash: u64,
275    /// Integer EWMA of assigned block variance, Q8.
276    pub variance_q8: u16,
277    /// Blocks assigned to this shard.
278    pub blocks: u64,
279    /// Source bytes assigned to this shard.
280    pub source_bytes: u64,
281}
282
283/// Cumulative diagnostics for one stripe-local collator.
284#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
285pub struct CompressionLocalityStats {
286    /// Records scored in complete blocks.
287    pub observations: u64,
288    /// Complete blocks and recursive sub-blocks scored.
289    pub blocks_scored: u64,
290    /// Parent blocks divided by farthest-seed partitioning.
291    pub blocks_split: u64,
292    /// Child blocks produced by splitting.
293    pub subblocks_created: u64,
294    /// High-variance blocks kept whole after repeated unproductive splits.
295    pub split_explorations_suppressed: u64,
296    /// Records ultimately kept in the base source cohort.
297    pub base_placements: u64,
298    /// Records assigned to active compression shards.
299    pub collated_placements: u64,
300    /// Records moved away from the block's tentative home shard.
301    pub records_reassigned: u64,
302    /// Source bytes moved away from the tentative home shard.
303    pub bytes_reassigned: u64,
304    /// Current number of active compression shards.
305    pub active_compression_shards: usize,
306    /// Largest scored internal variance, Q8.
307    pub max_internal_variance_q8: u16,
308    /// Packed membership bytes transferred through `bytes-handoff`.
309    pub handoff_membership_bytes: u64,
310    /// Preallocated persistent profile memory in bytes.
311    pub allocated_state_bytes: usize,
312}
313
314#[derive(Debug, Clone)]
315struct CompressionShard {
316    snapshot: CompressionShardProfile,
317    one_weights: [u64; 16],
318    total_weight: u64,
319    shape_vote_weight: u64,
320}
321
322#[derive(Debug)]
323struct WorkBlock {
324    membership: BlockMembership,
325    depth: u8,
326}
327
328#[derive(Debug, Clone)]
329enum BlockMembership {
330    Contiguous(Range<usize>),
331    Packed(Bytes),
332}
333
334impl BlockMembership {
335    fn indices(&self) -> MembershipIndices<'_> {
336        match self {
337            Self::Contiguous(range) => MembershipIndices::Contiguous(range.clone()),
338            Self::Packed(bytes) => MembershipIndices::Packed(bytes.chunks_exact(INDEX_BYTES)),
339        }
340    }
341
342    fn encoded_len(&self) -> usize {
343        match self {
344            Self::Contiguous(_) => 0,
345            Self::Packed(bytes) => bytes.len(),
346        }
347    }
348}
349
350enum MembershipIndices<'a> {
351    Contiguous(Range<usize>),
352    Packed(std::slice::ChunksExact<'a, u8>),
353}
354
355impl Iterator for MembershipIndices<'_> {
356    type Item = usize;
357
358    fn next(&mut self) -> Option<Self::Item> {
359        match self {
360            Self::Contiguous(range) => range.next(),
361            Self::Packed(chunks) => chunks.next().map(|chunk| {
362                usize::try_from(u32::from_le_bytes(
363                    chunk.try_into().expect("membership entry is four bytes"),
364                ))
365                .expect("u32 membership index fits usize")
366            }),
367        }
368    }
369
370    fn size_hint(&self) -> (usize, Option<usize>) {
371        let length = self.len();
372        (length, Some(length))
373    }
374}
375
376impl ExactSizeIterator for MembershipIndices<'_> {
377    fn len(&self) -> usize {
378        match self {
379            Self::Contiguous(range) => range.len(),
380            Self::Packed(chunks) => chunks.len(),
381        }
382    }
383}
384
385#[derive(Debug, Clone, Copy, Default)]
386struct SplitExploration {
387    source_tag: u64,
388    occupied: bool,
389    failed_explorations: u8,
390    blocks_since_exploration: u8,
391}
392
393#[derive(Debug, Clone, Copy)]
394struct ScoredMembership {
395    score: CompressionBlockScore,
396    seed_a: usize,
397    seed_b: usize,
398}
399
400/// Fixed-capacity, owner-local block collator.
401#[derive(Debug)]
402pub struct CompressionBlockCollator {
403    config: CompressionLocalityConfig,
404    target_block_bytes: u64,
405    shards: Vec<CompressionShard>,
406    split_explorations: [SplitExploration; SPLIT_EXPLORATION_SLOTS],
407    stats: CompressionLocalityStats,
408}
409
410impl CompressionBlockCollator {
411    /// Creates preallocated collation state for one stripe.
412    pub fn new(
413        config: CompressionLocalityConfig,
414        target_block_bytes: u64,
415    ) -> TelemetryResult<Self> {
416        config.validate().map_err(TelemetryError::InvalidConfig)?;
417        if target_block_bytes == 0 {
418            return Err(TelemetryError::InvalidConfig(
419                "locality target_block_bytes must be nonzero",
420            ));
421        }
422        let allocated_state_bytes = estimated_state_bytes(&config);
423        let shard_capacity = config.max_compression_shards;
424        Ok(Self {
425            config,
426            target_block_bytes,
427            shards: Vec::with_capacity(shard_capacity),
428            split_explorations: [SplitExploration::default(); SPLIT_EXPLORATION_SLOTS],
429            stats: CompressionLocalityStats {
430                allocated_state_bytes,
431                ..CompressionLocalityStats::default()
432            },
433        })
434    }
435
436    /// Returns whether block collation is enabled.
437    #[must_use]
438    pub const fn is_enabled(&self) -> bool {
439        self.config.enabled
440    }
441
442    /// Returns a snapshot of cumulative collation diagnostics.
443    #[must_use]
444    pub fn stats(&self) -> CompressionLocalityStats {
445        let mut stats = self.stats;
446        stats.active_compression_shards = self.shards.len();
447        stats
448    }
449
450    /// Returns current read-only compression-shard profiles.
451    pub fn compression_shards(
452        &self,
453    ) -> impl ExactSizeIterator<Item = CompressionShardProfile> + '_ {
454        self.shards.iter().map(|shard| shard.snapshot)
455    }
456
457    /// Selects the tentative block collector for one record.
458    ///
459    /// This is only an ingress hint. The final placement is calculated when the
460    /// complete block is scored and may differ after outlier filtering.
461    #[must_use]
462    pub fn tentative_placement(
463        &self,
464        source: CompressionCohortId,
465        fingerprint: MessageFingerprint,
466    ) -> CompressionPlacement {
467        let temperature = CompressionTemperature::new(fingerprint.locality_signature);
468        if !self.config.enabled {
469            return CompressionPlacement::base(source, temperature);
470        }
471        if let Some((index, distance)) =
472            self.nearest_shard(source, temperature, fingerprint.shape_hash)
473            && distance <= self.config.max_assignment_distance
474        {
475            return CompressionPlacement {
476                placement_id: self.shards[index].snapshot.placement_id,
477                temperature,
478                granularity: LocalityGranularity::Collated,
479                distance_to_shard: distance,
480                internal_variance_q8: 0,
481            };
482        }
483        CompressionPlacement::base(source, temperature)
484    }
485
486    /// Scores, recursively splits, and assigns one complete candidate block.
487    ///
488    /// Membership lists are packed as `u32` indices. `bytes-handoff` splits the
489    /// packed left prefix from the right tail without per-record channels or
490    /// cloned log payloads.
491    pub fn collate(
492        &mut self,
493        source: CompressionCohortId,
494        home: CompressionPlacementId,
495        records: &[CompressionLocalityRecord],
496    ) -> Vec<CompressionBlockAssignment> {
497        if records.is_empty() {
498            return Vec::new();
499        }
500        self.stats.observations = self
501            .stats
502            .observations
503            .saturating_add(u64::try_from(records.len()).unwrap_or(u64::MAX));
504        let root = BlockMembership::Contiguous(0..records.len());
505
506        let mut work = VecDeque::from([WorkBlock {
507            membership: root,
508            depth: 0,
509        }]);
510        let explore_splits = self.should_explore_splits(source);
511        let mut split_attempted = false;
512        let mut leaves = Vec::new();
513        while let Some(block) = work.pop_front() {
514            let scored = score_membership(records, &block.membership);
515            let score = scored.score;
516            self.observe_score(score);
517            let nearest = self.nearest_shard(source, score.temperature, score.shape_hash);
518            let closer_to_other_shard = nearest.is_some_and(|(index, distance)| {
519                let nearest_id = self.shards[index].snapshot.placement_id;
520                nearest_id != home
521                    && self
522                        .profile_distance(home, score.temperature, score.shape_hash)
523                        .is_none_or(|home_distance| distance < home_distance)
524            });
525            let should_split = self.config.enabled
526                && explore_splits
527                && block.depth < self.config.max_split_depth
528                && (score.internal_variance_q8 > self.config.split_variance_q8
529                    || closer_to_other_shard);
530
531            if should_split {
532                split_attempted = true;
533                if let Some((left, right)) =
534                    split_membership(records, &block.membership, &self.config, scored)
535                {
536                    self.stats.blocks_split = self.stats.blocks_split.saturating_add(1);
537                    self.stats.subblocks_created = self.stats.subblocks_created.saturating_add(2);
538                    self.stats.handoff_membership_bytes =
539                        self.stats.handoff_membership_bytes.saturating_add(
540                            u64::try_from(left.encoded_len().saturating_add(right.encoded_len()))
541                                .unwrap_or(u64::MAX),
542                        );
543                    work.push_back(WorkBlock {
544                        membership: left,
545                        depth: block.depth.saturating_add(1),
546                    });
547                    work.push_back(WorkBlock {
548                        membership: right,
549                        depth: block.depth.saturating_add(1),
550                    });
551                    continue;
552                }
553            }
554            leaves.push((block.membership, score));
555        }
556
557        let mut assignments = Vec::with_capacity(leaves.len());
558        for (membership, score) in leaves {
559            let placement = self.assign_leaf(source, records, &membership, score);
560            let record_count = u64::try_from(score.record_count).unwrap_or(u64::MAX);
561            if placement.granularity == LocalityGranularity::Base {
562                self.stats.base_placements =
563                    self.stats.base_placements.saturating_add(record_count);
564            } else {
565                self.stats.collated_placements =
566                    self.stats.collated_placements.saturating_add(record_count);
567            }
568            if placement.placement_id != home {
569                self.stats.records_reassigned =
570                    self.stats.records_reassigned.saturating_add(record_count);
571                self.stats.bytes_reassigned = self
572                    .stats
573                    .bytes_reassigned
574                    .saturating_add(score.source_bytes);
575            }
576            assignments.push(CompressionBlockAssignment {
577                placement,
578                score,
579                membership,
580            });
581        }
582        assignments.sort_unstable_by_key(|assignment| {
583            assignment.record_indices().next().unwrap_or(usize::MAX)
584        });
585        let specialized = assignments
586            .iter()
587            .any(|assignment| assignment.placement.granularity == LocalityGranularity::Collated);
588        self.observe_split_exploration(source, split_attempted, specialized);
589        assignments
590    }
591
592    fn should_explore_splits(&mut self, source: CompressionCohortId) -> bool {
593        if !self.config.enabled
594            || self
595                .shards
596                .iter()
597                .any(|shard| shard.snapshot.source_cohort == source)
598        {
599            return true;
600        }
601        let slot = &mut self.split_explorations[usize::try_from(splitmix64(source.get()))
602            .unwrap_or(0)
603            & (SPLIT_EXPLORATION_SLOTS - 1)];
604        if !slot.occupied || slot.source_tag != source.get() {
605            *slot = SplitExploration {
606                source_tag: source.get(),
607                occupied: true,
608                ..SplitExploration::default()
609            };
610        }
611        if slot.failed_explorations < SPLIT_FAILURES_BEFORE_BACKOFF
612            || slot.blocks_since_exploration >= SPLIT_BACKOFF_BLOCKS
613        {
614            slot.blocks_since_exploration = 0;
615            true
616        } else {
617            slot.blocks_since_exploration = slot.blocks_since_exploration.saturating_add(1);
618            self.stats.split_explorations_suppressed =
619                self.stats.split_explorations_suppressed.saturating_add(1);
620            false
621        }
622    }
623
624    fn observe_split_exploration(
625        &mut self,
626        source: CompressionCohortId,
627        attempted: bool,
628        specialized: bool,
629    ) {
630        if !attempted && !specialized {
631            return;
632        }
633        let slot = &mut self.split_explorations[usize::try_from(splitmix64(source.get()))
634            .unwrap_or(0)
635            & (SPLIT_EXPLORATION_SLOTS - 1)];
636        if slot.occupied && slot.source_tag == source.get() {
637            if specialized {
638                slot.failed_explorations = 0;
639                slot.blocks_since_exploration = 0;
640            } else if attempted {
641                slot.failed_explorations = slot.failed_explorations.saturating_add(1);
642            }
643        }
644    }
645
646    fn assign_leaf(
647        &mut self,
648        source: CompressionCohortId,
649        records: &[CompressionLocalityRecord],
650        membership: &BlockMembership,
651        score: CompressionBlockScore,
652    ) -> CompressionPlacement {
653        if !self.config.enabled || score.internal_variance_q8 > self.config.max_shard_variance_q8 {
654            return CompressionPlacement {
655                internal_variance_q8: score.internal_variance_q8,
656                ..CompressionPlacement::base(source, score.temperature)
657            };
658        }
659
660        let selected = self
661            .nearest_shard(source, score.temperature, score.shape_hash)
662            .filter(|(_, distance)| *distance <= self.config.max_assignment_distance)
663            .or_else(|| {
664                (score.source_bytes >= self.config.min_admission_bytes.min(self.target_block_bytes)
665                    && self.shards.len() < self.config.max_compression_shards)
666                    .then(|| {
667                        let index = self.admit_shard(source, score.temperature, score.shape_hash);
668                        (index, 0)
669                    })
670            });
671
672        let Some((index, distance)) = selected else {
673            return CompressionPlacement {
674                internal_variance_q8: score.internal_variance_q8,
675                ..CompressionPlacement::base(source, score.temperature)
676            };
677        };
678        self.observe_shard(index, records, membership, score);
679        CompressionPlacement {
680            placement_id: self.shards[index].snapshot.placement_id,
681            temperature: score.temperature,
682            granularity: LocalityGranularity::Collated,
683            distance_to_shard: distance,
684            internal_variance_q8: score.internal_variance_q8,
685        }
686    }
687
688    fn nearest_shard(
689        &self,
690        source: CompressionCohortId,
691        temperature: CompressionTemperature,
692        shape_hash: u64,
693    ) -> Option<(usize, u8)> {
694        self.shards
695            .iter()
696            .enumerate()
697            .filter(|(_, shard)| shard.snapshot.source_cohort == source)
698            .map(|(index, shard)| {
699                (
700                    index,
701                    locality_distance(
702                        temperature,
703                        shape_hash,
704                        shard.snapshot.temperature,
705                        shard.snapshot.shape_hash,
706                    ),
707                    shard.snapshot.variance_q8,
708                    shard.snapshot.placement_id,
709                )
710            })
711            .min_by_key(|(_, distance, variance, placement)| {
712                (*distance, *variance, placement.get())
713            })
714            .map(|(index, distance, _, _)| (index, distance))
715    }
716
717    fn profile_distance(
718        &self,
719        placement_id: CompressionPlacementId,
720        temperature: CompressionTemperature,
721        shape_hash: u64,
722    ) -> Option<u8> {
723        self.shards
724            .iter()
725            .find(|shard| shard.snapshot.placement_id == placement_id)
726            .map(|shard| {
727                locality_distance(
728                    temperature,
729                    shape_hash,
730                    shard.snapshot.temperature,
731                    shard.snapshot.shape_hash,
732                )
733            })
734    }
735
736    fn admit_shard(
737        &mut self,
738        source: CompressionCohortId,
739        temperature: CompressionTemperature,
740        shape_hash: u64,
741    ) -> usize {
742        let mut placement_id =
743            CompressionPlacementId::from_temperature(source, temperature, shape_hash);
744        if self
745            .shards
746            .iter()
747            .any(|shard| shard.snapshot.placement_id == placement_id)
748        {
749            placement_id = CompressionPlacementId::new(splitmix64(
750                placement_id.get() ^ u64::try_from(self.shards.len()).unwrap_or(u64::MAX),
751            ));
752        }
753        self.shards.push(CompressionShard {
754            snapshot: CompressionShardProfile {
755                placement_id,
756                source_cohort: source,
757                temperature,
758                shape_hash,
759                variance_q8: 0,
760                blocks: 0,
761                source_bytes: 0,
762            },
763            one_weights: [0; 16],
764            total_weight: 0,
765            shape_vote_weight: 0,
766        });
767        self.shards.len() - 1
768    }
769
770    fn observe_shard(
771        &mut self,
772        index: usize,
773        records: &[CompressionLocalityRecord],
774        membership: &BlockMembership,
775        score: CompressionBlockScore,
776    ) {
777        let shard = &mut self.shards[index];
778        if shard.total_weight > u64::MAX / 4 {
779            shard.total_weight >>= 1;
780            shard.shape_vote_weight >>= 1;
781            for weight in &mut shard.one_weights {
782                *weight >>= 1;
783            }
784        }
785        for record_index in membership.indices() {
786            let record = records[record_index];
787            let weight = locality_weight(record.source_bytes);
788            shard.total_weight = shard.total_weight.saturating_add(weight);
789            for bit in 0..16 {
790                if record.fingerprint.locality_signature & (1u16 << bit) != 0 {
791                    shard.one_weights[bit] = shard.one_weights[bit].saturating_add(weight);
792                }
793            }
794        }
795        shard.snapshot.temperature = CompressionTemperature::new(centroid_from_weights(
796            &shard.one_weights,
797            shard.total_weight,
798        ));
799        if shard.snapshot.blocks == 0 || shard.snapshot.shape_hash == score.shape_hash {
800            shard.snapshot.shape_hash = score.shape_hash;
801            shard.shape_vote_weight = shard.shape_vote_weight.saturating_add(score.source_bytes);
802        } else if shard.shape_vote_weight > score.source_bytes {
803            shard.shape_vote_weight = shard.shape_vote_weight.saturating_sub(score.source_bytes);
804        } else {
805            shard.snapshot.shape_hash = score.shape_hash;
806            shard.shape_vote_weight = score.source_bytes.saturating_sub(shard.shape_vote_weight);
807        }
808        shard.snapshot.variance_q8 = if shard.snapshot.blocks == 0 {
809            score.internal_variance_q8
810        } else {
811            u16::try_from(
812                (u32::from(shard.snapshot.variance_q8) * 7 + u32::from(score.internal_variance_q8))
813                    / 8,
814            )
815            .expect("variance EWMA remains u16")
816        };
817        shard.snapshot.blocks = shard.snapshot.blocks.saturating_add(1);
818        shard.snapshot.source_bytes = shard
819            .snapshot
820            .source_bytes
821            .saturating_add(score.source_bytes);
822    }
823
824    fn observe_score(&mut self, score: CompressionBlockScore) {
825        self.stats.blocks_scored = self.stats.blocks_scored.saturating_add(1);
826        self.stats.max_internal_variance_q8 = self
827            .stats
828            .max_internal_variance_q8
829            .max(score.internal_variance_q8);
830    }
831}
832
833/// Scans a message once, calling `on_term` for every Unicode alphanumeric term.
834///
835/// Dynamic structural tokens contribute only type and logarithmic length
836/// classes. Metadata values never enter either fingerprint.
837pub fn analyze_message(
838    message: &str,
839    fields: &[MetadataField],
840    mut on_term: impl FnMut(&str),
841) -> MessageFingerprint {
842    let (mut shape_hash, mut simhash) = if message.is_ascii() {
843        analyze_ascii_body(message, &mut on_term)
844    } else {
845        analyze_unicode_body(message, &mut on_term)
846    };
847
848    for field in fields {
849        shape_hash = fnv_bytes(shape_hash, &[0xf1]);
850        shape_hash = fnv_bytes(shape_hash, field.key.as_bytes());
851        add_simhash_feature(
852            &mut simhash,
853            fnv_bytes(FNV_OFFSET ^ 0x6d65_7461_6b65_7900, field.key.as_bytes()),
854        );
855    }
856
857    let mut locality_signature = 0u16;
858    for (bit, weight) in simhash.into_iter().enumerate() {
859        if weight > 0 {
860            locality_signature |= 1u16 << bit;
861        }
862    }
863    MessageFingerprint {
864        shape_hash,
865        locality_signature,
866    }
867}
868
869/// Scans only case-preserving search terms without calculating compression
870/// fingerprints.
871///
872/// The default production locality policy is disabled. Keeping this path
873/// separate avoids template hashing and 16-lane SimHash work when ingestion
874/// only needs the inverted search index.
875pub fn scan_message_terms(message: &str, mut on_term: impl FnMut(&str)) {
876    if message.is_ascii() {
877        let mut start = None;
878        for (index, byte) in message.bytes().enumerate() {
879            match (start, byte.is_ascii_alphanumeric()) {
880                (None, true) => start = Some(index),
881                (Some(term_start), false) => {
882                    on_term(&message[term_start..index]);
883                    start = None;
884                }
885                _ => {}
886            }
887        }
888        if let Some(term_start) = start {
889            on_term(&message[term_start..]);
890        }
891        return;
892    }
893
894    let mut start = None;
895    for (index, character) in message.char_indices() {
896        match (start, character.is_alphanumeric()) {
897            (None, true) => start = Some(index),
898            (Some(term_start), false) => {
899                on_term(&message[term_start..index]);
900                start = None;
901            }
902            _ => {}
903        }
904    }
905    if let Some(term_start) = start {
906        on_term(&message[term_start..]);
907    }
908}
909
910fn analyze_ascii_body(message: &str, on_term: &mut impl FnMut(&str)) -> (u64, [i16; 16]) {
911    let bytes = message.as_bytes();
912    let mut shape_hash = FNV_OFFSET;
913    let mut simhash = [0i16; 16];
914    let mut structural_start = 0usize;
915    let mut structural_is_token = None;
916    let mut structural_has_digit = false;
917    let mut term_start = None;
918
919    for (index, byte) in bytes.iter().copied().enumerate() {
920        let is_term = byte.is_ascii_alphanumeric();
921        match (term_start, is_term) {
922            (None, true) => term_start = Some(index),
923            (Some(start), false) => {
924                on_term(&message[start..index]);
925                term_start = None;
926            }
927            _ => {}
928        }
929
930        let is_token = is_template_token_byte(byte);
931        match structural_is_token {
932            None => {
933                structural_start = index;
934                structural_is_token = Some(is_token);
935                structural_has_digit = byte.is_ascii_digit();
936            }
937            Some(current) if current == is_token => {
938                structural_has_digit |= byte.is_ascii_digit();
939            }
940            Some(current) => {
941                analyze_structural_run(
942                    &message[structural_start..index],
943                    current,
944                    structural_has_digit,
945                    &mut shape_hash,
946                    &mut simhash,
947                );
948                structural_start = index;
949                structural_is_token = Some(is_token);
950                structural_has_digit = byte.is_ascii_digit();
951            }
952        }
953    }
954    if let Some(start) = term_start {
955        on_term(&message[start..]);
956    }
957    if let Some(is_token) = structural_is_token {
958        analyze_structural_run(
959            &message[structural_start..],
960            is_token,
961            structural_has_digit,
962            &mut shape_hash,
963            &mut simhash,
964        );
965    }
966    (shape_hash, simhash)
967}
968
969fn analyze_unicode_body(message: &str, on_term: &mut impl FnMut(&str)) -> (u64, [i16; 16]) {
970    let mut shape_hash = FNV_OFFSET;
971    let mut simhash = [0i16; 16];
972    let mut structural_start = 0usize;
973    let mut structural_is_token = None;
974    let mut structural_has_digit = false;
975    let mut term_start = None;
976
977    for (index, character) in message.char_indices() {
978        let is_term = character.is_alphanumeric();
979        match (term_start, is_term) {
980            (None, true) => term_start = Some(index),
981            (Some(start), false) => {
982                on_term(&message[start..index]);
983                term_start = None;
984            }
985            _ => {}
986        }
987
988        let is_token = is_template_token_character(character);
989        match structural_is_token {
990            None => {
991                structural_start = index;
992                structural_is_token = Some(is_token);
993                structural_has_digit = character.is_ascii_digit();
994            }
995            Some(current) if current == is_token => {
996                structural_has_digit |= character.is_ascii_digit();
997            }
998            Some(current) => {
999                analyze_structural_run(
1000                    &message[structural_start..index],
1001                    current,
1002                    structural_has_digit,
1003                    &mut shape_hash,
1004                    &mut simhash,
1005                );
1006                structural_start = index;
1007                structural_is_token = Some(is_token);
1008                structural_has_digit = character.is_ascii_digit();
1009            }
1010        }
1011    }
1012    if let Some(start) = term_start {
1013        on_term(&message[start..]);
1014    }
1015    if let Some(is_token) = structural_is_token {
1016        analyze_structural_run(
1017            &message[structural_start..],
1018            is_token,
1019            structural_has_digit,
1020            &mut shape_hash,
1021            &mut simhash,
1022        );
1023    }
1024    (shape_hash, simhash)
1025}
1026
1027/// Returns a fingerprint without observing search terms.
1028#[must_use]
1029pub fn fingerprint_message(message: &str, fields: &[MetadataField]) -> MessageFingerprint {
1030    analyze_message(message, fields, |_| {})
1031}
1032
1033fn analyze_structural_run(
1034    run: &str,
1035    is_token: bool,
1036    has_digit: bool,
1037    shape_hash: &mut u64,
1038    simhash: &mut [i16; 16],
1039) {
1040    if is_token && has_digit {
1041        *shape_hash = fnv_bytes(*shape_hash, &[0xd1]);
1042        let class = dynamic_class(run);
1043        let length_class = length_class(run.len());
1044        add_simhash_feature(
1045            simhash,
1046            splitmix64(0x6479_6e61_6d69_6300 ^ (u64::from(class) << 8) ^ u64::from(length_class)),
1047        );
1048    } else {
1049        *shape_hash = fnv_bytes(*shape_hash, &[0x51]);
1050        *shape_hash = fnv_bytes(*shape_hash, run.as_bytes());
1051        add_simhash_feature(
1052            simhash,
1053            fnv_bytes(FNV_OFFSET ^ 0x6c69_7465_7261_6c00, run.as_bytes()),
1054        );
1055    }
1056}
1057
1058fn is_template_token_character(character: char) -> bool {
1059    character.is_ascii_alphanumeric() || matches!(character, '_' | '-' | '.' | '/' | ':')
1060}
1061
1062fn is_template_token_byte(byte: u8) -> bool {
1063    byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b'-' | b'.' | b'/' | b':')
1064}
1065
1066fn dynamic_class(run: &str) -> u8 {
1067    let bytes = run.as_bytes();
1068    if bytes.iter().all(u8::is_ascii_digit) {
1069        1
1070    } else if bytes.iter().all(u8::is_ascii_hexdigit) {
1071        2
1072    } else if bytes.contains(&b'-') {
1073        3
1074    } else if bytes.contains(&b'.') || bytes.contains(&b':') || bytes.contains(&b'/') {
1075        4
1076    } else {
1077        5
1078    }
1079}
1080
1081fn length_class(length: usize) -> u8 {
1082    let length = u64::try_from(length).unwrap_or(u64::MAX).max(1);
1083    u8::try_from(length.ilog2()).unwrap_or(u8::MAX).min(15)
1084}
1085
1086fn add_simhash_feature(weights: &mut [i16; 16], feature_hash: u64) {
1087    let hash = splitmix64(feature_hash);
1088    for (bit, weight) in weights.iter_mut().enumerate() {
1089        if hash & (1u64 << bit) == 0 {
1090            *weight = weight.saturating_sub(1);
1091        } else {
1092            *weight = weight.saturating_add(1);
1093        }
1094    }
1095}
1096
1097fn fnv_bytes(mut hash: u64, bytes: &[u8]) -> u64 {
1098    for byte in bytes {
1099        hash ^= u64::from(*byte);
1100        hash = hash.wrapping_mul(FNV_PRIME);
1101    }
1102    hash
1103}
1104
1105const fn splitmix64(mut value: u64) -> u64 {
1106    value = value.wrapping_add(0x9e37_79b9_7f4a_7c15);
1107    value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
1108    value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
1109    value ^ (value >> 31)
1110}
1111
1112fn fingerprint_distance(left: MessageFingerprint, right: MessageFingerprint) -> u8 {
1113    locality_distance(
1114        CompressionTemperature::new(left.locality_signature),
1115        left.shape_hash,
1116        CompressionTemperature::new(right.locality_signature),
1117        right.shape_hash,
1118    )
1119}
1120
1121fn locality_distance(
1122    left_temperature: CompressionTemperature,
1123    left_shape_hash: u64,
1124    right_temperature: CompressionTemperature,
1125    right_shape_hash: u64,
1126) -> u8 {
1127    left_temperature
1128        .distance(right_temperature)
1129        .saturating_add(u8::from(left_shape_hash != right_shape_hash) * SHAPE_MISMATCH_DISTANCE)
1130}
1131
1132fn score_membership(
1133    records: &[CompressionLocalityRecord],
1134    membership: &BlockMembership,
1135) -> ScoredMembership {
1136    let seed_a = membership
1137        .indices()
1138        .next()
1139        .expect("scored membership is nonempty");
1140    let mut seed_b = seed_a;
1141    let mut seed_distance = 0u8;
1142    let mut one_weights = [0u64; 16];
1143    let mut total_weight = 0u64;
1144    let mut source_bytes = 0u64;
1145    let mut record_count = 0usize;
1146    let mut shape_hash = records[seed_a].fingerprint.shape_hash;
1147    let mut shape_vote_weight = 0u64;
1148    for index in membership.indices() {
1149        let record = records[index];
1150        let weight = locality_weight(record.source_bytes);
1151        total_weight = total_weight.saturating_add(weight);
1152        source_bytes = source_bytes.saturating_add(record.source_bytes);
1153        record_count = record_count.saturating_add(1);
1154        for (bit, one_weight) in one_weights.iter_mut().enumerate() {
1155            if record.fingerprint.locality_signature & (1u16 << bit) != 0 {
1156                *one_weight = one_weight.saturating_add(weight);
1157            }
1158        }
1159        if record.fingerprint.shape_hash == shape_hash {
1160            shape_vote_weight = shape_vote_weight.saturating_add(weight);
1161        } else if shape_vote_weight > weight {
1162            shape_vote_weight -= weight;
1163        } else {
1164            shape_hash = record.fingerprint.shape_hash;
1165            shape_vote_weight = weight - shape_vote_weight;
1166        }
1167        let distance = fingerprint_distance(records[seed_a].fingerprint, record.fingerprint);
1168        if distance > seed_distance {
1169            seed_b = index;
1170            seed_distance = distance;
1171        }
1172    }
1173    let temperature =
1174        CompressionTemperature::new(centroid_from_weights(&one_weights, total_weight));
1175    let mut squared_distance_weight = 0u128;
1176    let mut max_deviation = 0u8;
1177    for index in membership.indices() {
1178        let record = records[index];
1179        let distance = locality_distance(
1180            temperature,
1181            shape_hash,
1182            CompressionTemperature::new(record.fingerprint.locality_signature),
1183            record.fingerprint.shape_hash,
1184        );
1185        max_deviation = max_deviation.max(distance);
1186        squared_distance_weight = squared_distance_weight.saturating_add(
1187            u128::from(distance)
1188                .saturating_mul(u128::from(distance))
1189                .saturating_mul(u128::from(locality_weight(record.source_bytes))),
1190        );
1191    }
1192    let variance_q8 = squared_distance_weight
1193        .saturating_mul(256)
1194        .checked_div(u128::from(total_weight.max(1)))
1195        .unwrap_or(u128::from(u16::MAX))
1196        .min(u128::from(u16::MAX));
1197    ScoredMembership {
1198        score: CompressionBlockScore {
1199            temperature,
1200            shape_hash,
1201            internal_variance_q8: u16::try_from(variance_q8).expect("variance was bounded to u16"),
1202            max_deviation,
1203            source_bytes,
1204            record_count,
1205        },
1206        seed_a,
1207        seed_b,
1208    }
1209}
1210
1211fn split_membership(
1212    records: &[CompressionLocalityRecord],
1213    membership: &BlockMembership,
1214    config: &CompressionLocalityConfig,
1215    scored: ScoredMembership,
1216) -> Option<(BlockMembership, BlockMembership)> {
1217    let seed_a = scored.seed_a;
1218    let seed_b = scored.seed_b;
1219    if seed_a == seed_b {
1220        return None;
1221    }
1222    let goes_left = |index: usize| {
1223        fingerprint_distance(records[index].fingerprint, records[seed_a].fingerprint)
1224            <= fingerprint_distance(records[index].fingerprint, records[seed_b].fingerprint)
1225    };
1226
1227    let mut left_records = 0usize;
1228    let mut right_records = 0usize;
1229    let mut left_bytes = 0u64;
1230    let mut right_bytes = 0u64;
1231    let packed_capacity = membership.indices().len().saturating_mul(INDEX_BYTES);
1232    let mut left = BytesMut::with_capacity(packed_capacity);
1233    let mut right = BytesMut::with_capacity(packed_capacity / 2);
1234    for index in membership.indices() {
1235        if goes_left(index) {
1236            left_records = left_records.saturating_add(1);
1237            left_bytes = left_bytes.saturating_add(records[index].source_bytes);
1238            left.put_u32_le(
1239                u32::try_from(index).expect("a block cannot contain more than u32 rows"),
1240            );
1241        } else {
1242            right_records = right_records.saturating_add(1);
1243            right_bytes = right_bytes.saturating_add(records[index].source_bytes);
1244            right.put_u32_le(
1245                u32::try_from(index).expect("a block cannot contain more than u32 rows"),
1246            );
1247        }
1248    }
1249    if left_records < config.min_split_records
1250        || right_records < config.min_split_records
1251        || left_bytes < config.min_split_bytes
1252        || right_bytes < config.min_split_bytes
1253    {
1254        return None;
1255    }
1256
1257    let left_len = left.len();
1258    left.unsplit(right);
1259    let packed = left;
1260    let max_len = packed.len().max(1);
1261    let mut handoff = HandoffBuffer::from_tail_with_policy(
1262        packed,
1263        HandoffBufferConfig::new(max_len),
1264        HandoffBufferPolicy::new().with_small_prefix_copy_max(0),
1265    )
1266    .expect("packed sub-block membership fits its exact handoff limit");
1267    let left = handoff
1268        .split_prefix(left_len)
1269        .expect("counted left prefix is present");
1270    let right = handoff.freeze_all();
1271    Some((
1272        BlockMembership::Packed(left),
1273        BlockMembership::Packed(right),
1274    ))
1275}
1276
1277fn locality_weight(source_bytes: u64) -> u64 {
1278    source_bytes.max(1).min(u64::from(u32::MAX))
1279}
1280
1281fn centroid_from_weights(one_weights: &[u64; 16], total_weight: u64) -> u16 {
1282    let mut centroid = 0u16;
1283    for (bit, one_weight) in one_weights.iter().enumerate() {
1284        if one_weight.saturating_mul(2) >= total_weight.max(1) {
1285            centroid |= 1u16 << bit;
1286        }
1287    }
1288    centroid
1289}
1290
1291fn estimated_state_bytes(config: &CompressionLocalityConfig) -> usize {
1292    config
1293        .max_compression_shards
1294        .saturating_mul(size_of::<CompressionShard>())
1295        .saturating_add(size_of::<[SplitExploration; SPLIT_EXPLORATION_SLOTS]>())
1296}
1297
1298#[cfg(test)]
1299mod tests {
1300    use super::*;
1301
1302    fn test_config() -> CompressionLocalityConfig {
1303        CompressionLocalityConfig {
1304            enabled: true,
1305            min_split_records: 2,
1306            min_split_bytes: 1,
1307            split_variance_q8: 64,
1308            max_shard_variance_q8: u16::MAX,
1309            min_admission_bytes: 1,
1310            ..CompressionLocalityConfig::default()
1311        }
1312    }
1313
1314    fn locality_record(signature: u16, source_bytes: u64) -> CompressionLocalityRecord {
1315        CompressionLocalityRecord {
1316            fingerprint: MessageFingerprint {
1317                shape_hash: u64::from(signature),
1318                locality_signature: signature,
1319            },
1320            source_bytes,
1321        }
1322    }
1323
1324    #[test]
1325    fn dynamic_values_preserve_template_shape() {
1326        let first = fingerprint_message("2026-07-29T10:22:31Z request 12345 took 981 ms", &[]);
1327        let second = fingerprint_message("2027-01-03T09:00:02Z request 987654321 took 12 ms", &[]);
1328        assert_eq!(first.shape_hash, second.shape_hash);
1329    }
1330
1331    #[test]
1332    fn static_changes_affect_the_fingerprint() {
1333        let first = fingerprint_message("request 123 failed", &[]);
1334        let second = fingerprint_message("request 123 succeeded", &[]);
1335        assert_ne!(first, second);
1336    }
1337
1338    #[test]
1339    fn exact_shape_mismatch_adds_a_grouping_penalty() {
1340        let first = MessageFingerprint {
1341            shape_hash: 1,
1342            locality_signature: 0x1234,
1343        };
1344        let second = MessageFingerprint {
1345            shape_hash: 2,
1346            locality_signature: 0x1234,
1347        };
1348        assert_eq!(fingerprint_distance(first, second), SHAPE_MISMATCH_DISTANCE);
1349    }
1350
1351    #[test]
1352    fn scanner_reports_unicode_terms_without_allocating_a_collection() {
1353        let mut terms = Vec::new();
1354        let _ = analyze_message("Échec: request-42 東京", &[], |term| {
1355            terms.push(term.to_owned());
1356        });
1357        assert_eq!(terms, ["Échec", "request", "42", "東京"]);
1358    }
1359
1360    #[test]
1361    fn term_only_scanner_matches_full_analysis_for_ascii_and_unicode() {
1362        for message in [
1363            "ERROR request-42 took 981ms",
1364            "Échec: request-42 東京",
1365            "",
1366            "---",
1367        ] {
1368            let mut full = Vec::new();
1369            let _ = analyze_message(message, &[], |term| full.push(term.to_owned()));
1370            let mut terms_only = Vec::new();
1371            scan_message_terms(message, |term| terms_only.push(term.to_owned()));
1372            assert_eq!(terms_only, full, "{message:?}");
1373        }
1374    }
1375
1376    #[test]
1377    fn homogeneous_block_admits_a_compression_shard() {
1378        let mut router =
1379            CompressionBlockCollator::new(test_config(), 1_024).expect("collator validates");
1380        let source = CompressionCohortId::new(9);
1381        let records = vec![locality_record(0x1234, 128); 16];
1382        let home = CompressionPlacementId::from_source_cohort(source);
1383        let assignments = router.collate(source, home, &records);
1384        assert_eq!(assignments.len(), 1);
1385        assert_eq!(
1386            assignments[0].placement.granularity,
1387            LocalityGranularity::Collated
1388        );
1389        assert_eq!(assignments[0].score.internal_variance_q8, 0);
1390        assert_eq!(router.stats().active_compression_shards, 1);
1391        assert_eq!(
1392            router
1393                .tentative_placement(source, records[0].fingerprint)
1394                .placement_id,
1395            assignments[0].placement.placement_id
1396        );
1397    }
1398
1399    #[test]
1400    fn sparse_and_restarted_collators_fail_open_to_base() {
1401        let config = CompressionLocalityConfig {
1402            enabled: true,
1403            min_admission_bytes: 1_024,
1404            ..CompressionLocalityConfig::default()
1405        };
1406        let source = CompressionCohortId::new(4);
1407        let mut first = CompressionBlockCollator::new(config.clone(), 8 * 1024 * 1024)
1408            .expect("collator config validates");
1409        let records = [locality_record(0x1234, 128)];
1410        assert_eq!(
1411            first.collate(
1412                source,
1413                CompressionPlacementId::from_source_cohort(source),
1414                &records
1415            )[0]
1416            .placement
1417            .granularity,
1418            LocalityGranularity::Base
1419        );
1420        let mut restarted = CompressionBlockCollator::new(config, 8 * 1024 * 1024)
1421            .expect("collator config validates");
1422        assert_eq!(
1423            restarted.collate(
1424                source,
1425                CompressionPlacementId::from_source_cohort(source),
1426                &records
1427            )[0]
1428            .placement
1429            .granularity,
1430            LocalityGranularity::Base
1431        );
1432    }
1433
1434    #[test]
1435    fn high_variance_blocks_split_with_farthest_seeds() {
1436        let mut router =
1437            CompressionBlockCollator::new(test_config(), 1_024).expect("collator validates");
1438        let source = CompressionCohortId::new(7);
1439        let records = (0..8)
1440            .map(|_| locality_record(0x0000, 128))
1441            .chain((0..8).map(|_| locality_record(0xffff, 128)))
1442            .collect::<Vec<_>>();
1443        let assignments = router.collate(
1444            source,
1445            CompressionPlacementId::from_source_cohort(source),
1446            &records,
1447        );
1448        assert_eq!(assignments.len(), 2);
1449        assert!(
1450            assignments
1451                .iter()
1452                .all(|assignment| assignment.score.internal_variance_q8 == 0)
1453        );
1454        assert_eq!(router.stats().blocks_split, 1);
1455        assert_eq!(router.stats().subblocks_created, 2);
1456        assert_eq!(router.stats().active_compression_shards, 2);
1457    }
1458
1459    #[test]
1460    fn blocks_closer_to_another_shard_are_reassigned_after_splitting() {
1461        let mut router =
1462            CompressionBlockCollator::new(test_config(), 1_024).expect("collator validates");
1463        let source = CompressionCohortId::new(7);
1464        let first_records = vec![locality_record(0x0000, 128); 8];
1465        let first = router.collate(
1466            source,
1467            CompressionPlacementId::from_source_cohort(source),
1468            &first_records,
1469        );
1470        let first_home = first[0].placement.placement_id;
1471        let second_records = vec![locality_record(0xffff, 128); 8];
1472        let second = router.collate(source, first_home, &second_records);
1473        assert_ne!(second[0].placement.placement_id, first_home);
1474        assert_eq!(router.stats().records_reassigned, 16);
1475    }
1476
1477    #[test]
1478    fn collation_is_deterministic_and_bounded() {
1479        let config = CompressionLocalityConfig {
1480            max_compression_shards: 4,
1481            ..test_config()
1482        };
1483        let mut first =
1484            CompressionBlockCollator::new(config.clone(), 512).expect("collator config validates");
1485        let mut second =
1486            CompressionBlockCollator::new(config, 512).expect("collator config validates");
1487        let source = CompressionCohortId::new(7);
1488        let records = (0..64)
1489            .map(|index| locality_record((index % 4 * 0x1111) as u16, 128))
1490            .collect::<Vec<_>>();
1491        let home = CompressionPlacementId::from_source_cohort(source);
1492        let first_assignments = first.collate(source, home, &records);
1493        let second_assignments = second.collate(source, home, &records);
1494        assert_eq!(
1495            first_assignments
1496                .iter()
1497                .map(|assignment| (
1498                    assignment.placement,
1499                    assignment.record_indices().collect::<Vec<_>>()
1500                ))
1501                .collect::<Vec<_>>(),
1502            second_assignments
1503                .iter()
1504                .map(|assignment| (
1505                    assignment.placement,
1506                    assignment.record_indices().collect::<Vec<_>>()
1507                ))
1508                .collect::<Vec<_>>()
1509        );
1510        assert!(first_assignments.len() <= 1usize << MAX_SPLIT_DEPTH);
1511        assert!(first.stats().active_compression_shards <= 4);
1512        assert!(first.stats().allocated_state_bytes <= MAX_ROUTER_STATE_BYTES);
1513    }
1514
1515    #[test]
1516    fn excess_compression_shards_fall_back_instead_of_exceeding_the_cap() {
1517        let config = CompressionLocalityConfig {
1518            max_compression_shards: 1,
1519            max_assignment_distance: 0,
1520            ..test_config()
1521        };
1522        let mut router =
1523            CompressionBlockCollator::new(config, 512).expect("collator config validates");
1524        let source = CompressionCohortId::new(12);
1525        let home = CompressionPlacementId::from_source_cohort(source);
1526        let first = router.collate(source, home, &[locality_record(0, 128); 4]);
1527        let second = router.collate(source, home, &[locality_record(u16::MAX, 128); 4]);
1528        assert_eq!(router.stats().active_compression_shards, 1);
1529        assert_eq!(
1530            usize::from(first[0].placement.granularity != LocalityGranularity::Base)
1531                + usize::from(second[0].placement.granularity != LocalityGranularity::Base),
1532            1
1533        );
1534    }
1535
1536    #[test]
1537    fn membership_handoff_preserves_every_record_exactly_once() {
1538        let records = (0..32)
1539            .map(|index| locality_record(if index % 2 == 0 { 0 } else { u16::MAX }, 64))
1540            .collect::<Vec<_>>();
1541        let membership = BlockMembership::Contiguous(0..records.len());
1542        let scored = score_membership(&records, &membership);
1543        let (left, right) =
1544            split_membership(&records, &membership, &test_config(), scored).expect("block splits");
1545        let mut observed = left.indices().chain(right.indices()).collect::<Vec<_>>();
1546        observed.sort_unstable();
1547        assert_eq!(observed, (0..records.len()).collect::<Vec<_>>());
1548    }
1549
1550    #[test]
1551    fn repeated_unproductive_splits_enter_bounded_backoff() {
1552        let config = CompressionLocalityConfig {
1553            min_split_bytes: 1024,
1554            max_shard_variance_q8: 64,
1555            ..test_config()
1556        };
1557        let mut collator =
1558            CompressionBlockCollator::new(config, 512).expect("collator config validates");
1559        let source = CompressionCohortId::new(19);
1560        let home = CompressionPlacementId::from_source_cohort(source);
1561        let records = [
1562            locality_record(0, 64),
1563            locality_record(u16::MAX, 64),
1564            locality_record(0, 64),
1565            locality_record(u16::MAX, 64),
1566        ];
1567        for _ in 0..4 {
1568            let assignments = collator.collate(source, home, &records);
1569            assert!(
1570                assignments
1571                    .iter()
1572                    .all(|assignment| assignment.placement.granularity == LocalityGranularity::Base)
1573            );
1574        }
1575        assert!(collator.stats().split_explorations_suppressed >= 1);
1576        assert_eq!(collator.stats().active_compression_shards, 0);
1577    }
1578
1579    #[test]
1580    fn production_defaults_fit_the_collator_memory_budget() {
1581        let config = CompressionLocalityConfig::default();
1582        config.validate().expect("default collator is bounded");
1583        assert!(estimated_state_bytes(&config) <= MAX_ROUTER_STATE_BYTES);
1584    }
1585
1586    #[test]
1587    fn invalid_collator_limits_are_rejected_without_allocating() {
1588        let error = CompressionBlockCollator::new(
1589            CompressionLocalityConfig {
1590                max_compression_shards: 0,
1591                ..CompressionLocalityConfig::default()
1592            },
1593            8 * 1024 * 1024,
1594        )
1595        .expect_err("zero compression shards is invalid");
1596        assert_eq!(
1597            error,
1598            TelemetryError::InvalidConfig(
1599                "locality max_compression_shards must be between 1 and 16"
1600            )
1601        );
1602    }
1603}