1use 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#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
37pub struct CompressionPlacementId(u64);
38
39impl CompressionPlacementId {
40 #[must_use]
42 pub const fn new(value: u64) -> Self {
43 Self(value)
44 }
45
46 #[must_use]
48 pub const fn get(self) -> u64 {
49 self.0
50 }
51
52 #[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#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
78pub struct CompressionTemperature(u16);
79
80impl CompressionTemperature {
81 #[must_use]
83 pub const fn new(value: u16) -> Self {
84 Self(value)
85 }
86
87 #[must_use]
89 pub const fn get(self) -> u16 {
90 self.0
91 }
92
93 #[must_use]
95 pub const fn distance(self, other: Self) -> u8 {
96 (self.0 ^ other.0).count_ones() as u8
97 }
98}
99
100#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
102#[repr(u8)]
103pub enum LocalityGranularity {
104 Base = 0,
106 Collated = 1,
108}
109
110#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
112pub struct CompressionPlacement {
113 pub placement_id: CompressionPlacementId,
115 pub temperature: CompressionTemperature,
117 pub granularity: LocalityGranularity,
119 pub distance_to_shard: u8,
121 pub internal_variance_q8: u16,
123}
124
125impl CompressionPlacement {
126 #[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#[derive(Debug, Clone, PartialEq, Eq)]
141pub struct CompressionLocalityConfig {
142 pub enabled: bool,
144 pub max_compression_shards: usize,
146 pub max_split_depth: u8,
148 pub min_split_records: usize,
150 pub min_split_bytes: u64,
152 pub split_variance_q8: u16,
154 pub max_shard_variance_q8: u16,
156 pub max_assignment_distance: u8,
158 pub min_admission_bytes: u64,
160 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
214pub struct MessageFingerprint {
215 pub shape_hash: u64,
217 pub locality_signature: u16,
219}
220
221#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223pub struct CompressionLocalityRecord {
224 pub fingerprint: MessageFingerprint,
226 pub source_bytes: u64,
228}
229
230#[derive(Debug, Clone, Copy, PartialEq, Eq)]
232pub struct CompressionBlockScore {
233 pub temperature: CompressionTemperature,
235 pub shape_hash: u64,
237 pub internal_variance_q8: u16,
239 pub max_deviation: u8,
241 pub source_bytes: u64,
243 pub record_count: usize,
245}
246
247#[derive(Debug, Clone)]
249pub struct CompressionBlockAssignment {
250 pub placement: CompressionPlacement,
252 pub score: CompressionBlockScore,
254 membership: BlockMembership,
255}
256
257impl CompressionBlockAssignment {
258 pub fn record_indices(&self) -> impl ExactSizeIterator<Item = usize> + '_ {
260 self.membership.indices()
261 }
262}
263
264#[derive(Debug, Clone, Copy, PartialEq, Eq)]
266pub struct CompressionShardProfile {
267 pub placement_id: CompressionPlacementId,
269 pub source_cohort: CompressionCohortId,
271 pub temperature: CompressionTemperature,
273 pub shape_hash: u64,
275 pub variance_q8: u16,
277 pub blocks: u64,
279 pub source_bytes: u64,
281}
282
283#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
285pub struct CompressionLocalityStats {
286 pub observations: u64,
288 pub blocks_scored: u64,
290 pub blocks_split: u64,
292 pub subblocks_created: u64,
294 pub split_explorations_suppressed: u64,
296 pub base_placements: u64,
298 pub collated_placements: u64,
300 pub records_reassigned: u64,
302 pub bytes_reassigned: u64,
304 pub active_compression_shards: usize,
306 pub max_internal_variance_q8: u16,
308 pub handoff_membership_bytes: u64,
310 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#[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 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 #[must_use]
438 pub const fn is_enabled(&self) -> bool {
439 self.config.enabled
440 }
441
442 #[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 pub fn compression_shards(
452 &self,
453 ) -> impl ExactSizeIterator<Item = CompressionShardProfile> + '_ {
454 self.shards.iter().map(|shard| shard.snapshot)
455 }
456
457 #[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 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
833pub 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
869pub 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#[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}