Skip to main content

shard_telemetry/
correlation.rs

1//! Bounded stripe-local links between logs, traces, and metrics.
2
3use std::hash::{BuildHasher, Hash};
4use std::sync::Arc;
5
6use foldhash::{HashMap, HashMapExt, HashSet, HashSetExt};
7use serde::{Deserialize, Serialize};
8
9use crate::{
10    AttributeFingerprint, DurableLog, DurableMetricPoint, DurableSpan, ResourceContext,
11    ResourceContextId, ScopeContext, ScopeContextId, TelemetryAttribute, TelemetryRecordRef,
12    TelemetrySignal, TraceId,
13};
14
15const CONTEXT_ID_CACHE_ENTRIES: usize = 64;
16const ATTRIBUTE_ID_CACHE_ENTRIES: usize = 1_024;
17
18/// Hard bounds for one owner stripe's cross-signal postings.
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub struct CorrelationConfig {
21    /// Maximum distinct trace, resource, scope, and attribute keys combined.
22    pub max_keys: usize,
23    /// Maximum record references retained for one correlation key.
24    pub max_refs_per_key: usize,
25    /// Maximum references retained across all postings.
26    pub max_total_refs: usize,
27}
28
29impl Default for CorrelationConfig {
30    fn default() -> Self {
31        Self {
32            max_keys: 65_536,
33            max_refs_per_key: 4_096,
34            max_total_refs: 1_048_576,
35        }
36    }
37}
38
39/// Snapshot of bounded correlation-index state.
40#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
41pub struct CorrelationStats {
42    /// Distinct admitted correlation keys.
43    pub keys: usize,
44    /// Record references retained across all postings.
45    pub refs: usize,
46    /// Postings omitted because a configured bound was reached.
47    pub dropped_postings: u64,
48}
49
50/// Cross-signal lookup constraints combined with AND semantics.
51#[derive(Debug, Clone, PartialEq, Eq)]
52pub struct CorrelationQuery {
53    /// Authenticated tenant.
54    pub tenant: Arc<str>,
55    /// Optional trace link shared by spans, logs, and metric exemplars.
56    pub trace_id: Option<TraceId>,
57    /// Optional exact resource context.
58    pub resource_id: Option<ResourceContextId>,
59    /// Optional exact instrumentation scope.
60    pub scope_id: Option<ScopeContextId>,
61    /// Exact typed metadata key/value identities.
62    pub attributes: Arc<Vec<AttributeFingerprint>>,
63    /// String labels rendered by compatibility APIs and matched across signal scopes.
64    pub labels: Arc<Vec<(Arc<str>, Arc<str>)>>,
65    /// Optional signal restriction.
66    pub signal: Option<TelemetrySignal>,
67    /// Inclusive lower event-time bound.
68    pub start_time_unix_nanos: Option<u64>,
69    /// Inclusive upper event-time bound.
70    pub end_time_unix_nanos: Option<u64>,
71    /// Exclusive stable continuation point.
72    pub after: Option<TelemetryRecordRef>,
73    /// Maximum record references returned.
74    pub limit: usize,
75}
76
77impl CorrelationQuery {
78    /// Creates an unconstrained, bounded query for one tenant.
79    #[must_use]
80    pub fn new(tenant: impl Into<Arc<str>>) -> Self {
81        Self {
82            tenant: tenant.into(),
83            trace_id: None,
84            resource_id: None,
85            scope_id: None,
86            attributes: Arc::new(Vec::new()),
87            labels: Arc::new(Vec::new()),
88            signal: None,
89            start_time_unix_nanos: None,
90            end_time_unix_nanos: None,
91            after: None,
92            limit: 1_000,
93        }
94    }
95
96    /// Requires an exact trace link.
97    #[must_use]
98    pub const fn with_trace_id(mut self, trace_id: TraceId) -> Self {
99        self.trace_id = Some(trace_id);
100        self
101    }
102
103    /// Requires an exact resource context.
104    #[must_use]
105    pub const fn with_resource_id(mut self, resource_id: ResourceContextId) -> Self {
106        self.resource_id = Some(resource_id);
107        self
108    }
109
110    /// Requires an exact instrumentation scope.
111    #[must_use]
112    pub const fn with_scope_id(mut self, scope_id: ScopeContextId) -> Self {
113        self.scope_id = Some(scope_id);
114        self
115    }
116
117    /// Requires one exact typed metadata key/value.
118    #[must_use]
119    pub fn with_attribute(mut self, attribute: &TelemetryAttribute) -> Self {
120        Arc::make_mut(&mut self.attributes).push(attribute.fingerprint());
121        self
122    }
123
124    /// Requires one exact string label wherever that key/value is attached.
125    #[must_use]
126    pub fn with_label(mut self, key: impl Into<Arc<str>>, value: impl Into<Arc<str>>) -> Self {
127        let key = key.into();
128        let value = value.into();
129        Arc::make_mut(&mut self.attributes).push(
130            TelemetryAttribute::new(
131                Arc::clone(&key),
132                crate::TelemetryValue::String(Arc::clone(&value)),
133            )
134            .fingerprint(),
135        );
136        Arc::make_mut(&mut self.labels).push((key, value));
137        self
138    }
139
140    /// Restricts results to one signal.
141    #[must_use]
142    pub const fn for_signal(mut self, signal: TelemetrySignal) -> Self {
143        self.signal = Some(signal);
144        self
145    }
146
147    /// Continues strictly after a record reference returned by a prior page.
148    #[must_use]
149    pub const fn after(mut self, record_ref: TelemetryRecordRef) -> Self {
150        self.after = Some(record_ref);
151        self
152    }
153
154    /// Sets the bounded result count.
155    #[must_use]
156    pub const fn with_limit(mut self, limit: usize) -> Self {
157        self.limit = limit;
158        self
159    }
160}
161
162#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
163enum CorrelationKey {
164    Trace(TraceId),
165    Resource(ResourceContextId),
166    Scope(ScopeContextId),
167    Attribute(AttributeFingerprint),
168}
169
170const CORRELATION_FILTER_WORDS: usize = 16;
171const CORRELATION_FILTER_HASHES: usize = 4;
172
173/// Compact immutable filter used to prune cold signal blocks by shared
174/// telemetry identity. False positives are possible; false negatives are not.
175#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
176pub struct CorrelationBlockFilter {
177    bits: [u64; CORRELATION_FILTER_WORDS],
178}
179
180impl Default for CorrelationBlockFilter {
181    fn default() -> Self {
182        Self {
183            bits: [0; CORRELATION_FILTER_WORDS],
184        }
185    }
186}
187
188impl CorrelationBlockFilter {
189    #[cfg(test)]
190    pub(crate) fn from_query(query: &CorrelationQuery) -> Self {
191        let mut filter = Self::default();
192        for key in query_keys(query) {
193            filter.insert(&query.tenant, key);
194        }
195        filter
196    }
197
198    /// Merges another immutable filter into this one without introducing
199    /// false negatives. Used to summarize blocks into catalog groups/pages.
200    pub(crate) fn union_assign(&mut self, other: &Self) {
201        for (target, source) in self.bits.iter_mut().zip(other.bits) {
202            *target |= source;
203        }
204    }
205
206    /// Builds a filter for one immutable trace block.
207    #[must_use]
208    pub fn for_spans(spans: &[DurableSpan]) -> Self {
209        let mut filter = Self::default();
210        let mut last_resource = None;
211        let mut last_scope = None;
212        let mut last_attributes = None;
213        for span in spans {
214            let tenant = Arc::clone(&span.tenant);
215            let resource_key = (Arc::clone(&tenant), Arc::as_ptr(&span.resource));
216            if last_resource.as_ref() != Some(&resource_key) {
217                filter.insert(&tenant, CorrelationKey::Resource(span.resource_id()));
218                filter.insert_attributes(&tenant, &span.resource.attributes);
219                last_resource = Some(resource_key);
220            }
221            let scope_key = (Arc::clone(&tenant), Arc::as_ptr(&span.scope));
222            if last_scope.as_ref() != Some(&scope_key) {
223                filter.insert(&tenant, CorrelationKey::Scope(span.scope_id()));
224                filter.insert_attributes(&tenant, &span.scope.attributes);
225                last_scope = Some(scope_key);
226            }
227            let attribute_key = (Arc::clone(&tenant), Arc::as_ptr(&span.attributes));
228            if last_attributes.as_ref() != Some(&attribute_key) {
229                filter.insert_attributes(&tenant, &span.attributes);
230                last_attributes = Some(attribute_key);
231            }
232            for event in span.events.iter() {
233                filter.insert_attributes(&tenant, &event.attributes);
234            }
235            for link in span.links.iter() {
236                filter.insert(&tenant, CorrelationKey::Trace(link.trace_id));
237                filter.insert_attributes(&tenant, &link.attributes);
238            }
239        }
240        filter
241    }
242
243    /// Builds a filter for one immutable metric chunk.
244    #[must_use]
245    pub fn for_metrics(points: &[DurableMetricPoint]) -> Self {
246        let mut filter = Self::default();
247        let mut traces = HashSet::new();
248        let mut attribute_sets = HashSet::new();
249        if let Some(point) = points.first() {
250            let tenant = point.identity.tenant.as_ref();
251            filter.insert(
252                tenant,
253                CorrelationKey::Resource(point.identity.resource_id()),
254            );
255            filter.insert(tenant, CorrelationKey::Scope(point.identity.scope_id()));
256            filter.insert_attributes(tenant, &point.identity.resource.attributes);
257            filter.insert_attributes(tenant, &point.identity.scope.attributes);
258            filter.insert_attributes(tenant, &point.identity.point_attributes);
259        }
260        for point in points {
261            let tenant = Arc::clone(&point.identity.tenant);
262            if !point.metadata.is_empty() {
263                filter.insert_attribute_set_once(&tenant, &point.metadata, &mut attribute_sets);
264            }
265            for exemplar in point.exemplars.iter() {
266                if let Some(trace_id) = exemplar.trace_id
267                    && traces.insert((Arc::clone(&tenant), trace_id))
268                {
269                    filter.insert(&tenant, CorrelationKey::Trace(trace_id));
270                }
271                filter.insert_attribute_set_once(
272                    &tenant,
273                    &exemplar.filtered_attributes,
274                    &mut attribute_sets,
275                );
276            }
277        }
278        filter
279    }
280
281    /// Returns whether this block can satisfy all exact identities in a query.
282    #[must_use]
283    pub fn may_match(&self, query: &CorrelationQuery) -> bool {
284        query_keys(query).all(|key| self.contains(&query.tenant, key))
285    }
286
287    /// Tests a trace block whose primary trace IDs are represented exactly by
288    /// the catalog range. The Bloom filter only needs linked trace IDs.
289    #[must_use]
290    pub fn may_match_trace_block(
291        &self,
292        query: &CorrelationQuery,
293        min_trace_id: u128,
294        max_trace_id: u128,
295    ) -> bool {
296        query_keys(query).all(|key| match key {
297            CorrelationKey::Trace(trace_id) => {
298                let value = u128::from_be_bytes(*trace_id.as_bytes());
299                (value >= min_trace_id && value <= max_trace_id)
300                    || self.contains(&query.tenant, key)
301            }
302            _ => self.contains(&query.tenant, key),
303        })
304    }
305
306    fn insert(&mut self, tenant: &str, key: CorrelationKey) {
307        for bit in correlation_filter_bits(tenant, key) {
308            self.bits[bit / 64] |= 1_u64 << (bit % 64);
309        }
310    }
311
312    fn contains(&self, tenant: &str, key: CorrelationKey) -> bool {
313        correlation_filter_bits(tenant, key)
314            .into_iter()
315            .all(|bit| self.bits[bit / 64] & (1_u64 << (bit % 64)) != 0)
316    }
317
318    fn insert_attributes(&mut self, tenant: &str, attributes: &[TelemetryAttribute]) {
319        for attribute in attributes {
320            self.insert(tenant, CorrelationKey::Attribute(attribute.fingerprint()));
321        }
322    }
323
324    fn insert_attribute_set_once(
325        &mut self,
326        tenant: &Arc<str>,
327        attributes: &Arc<Vec<TelemetryAttribute>>,
328        seen: &mut HashSet<(Arc<str>, *const Vec<TelemetryAttribute>)>,
329    ) {
330        if seen.insert((Arc::clone(tenant), Arc::as_ptr(attributes))) {
331            self.insert_attributes(tenant, attributes);
332        }
333    }
334}
335
336fn query_keys(query: &CorrelationQuery) -> impl Iterator<Item = CorrelationKey> + '_ {
337    query
338        .trace_id
339        .map(CorrelationKey::Trace)
340        .into_iter()
341        .chain(query.resource_id.map(CorrelationKey::Resource))
342        .chain(query.scope_id.map(CorrelationKey::Scope))
343        .chain(
344            query
345                .attributes
346                .iter()
347                .copied()
348                .map(CorrelationKey::Attribute),
349        )
350}
351
352fn correlation_filter_bits(tenant: &str, key: CorrelationKey) -> [usize; 4] {
353    let (tag, value) = match key {
354        CorrelationKey::Trace(value) => (0_u64, u128::from_be_bytes(*value.as_bytes())),
355        CorrelationKey::Resource(value) => (1, value.get()),
356        CorrelationKey::Scope(value) => (2, value.get()),
357        CorrelationKey::Attribute(value) => (3, value.get()),
358    };
359    let tenant_hash = tenant
360        .as_bytes()
361        .iter()
362        .fold(0xcbf2_9ce4_8422_2325, |hash, byte| {
363            (hash ^ u64::from(*byte)).wrapping_mul(0x100_0000_01b3)
364        });
365    let low = value as u64;
366    let high = (value >> 64) as u64;
367    let first = mix_filter_hash(low ^ tenant_hash ^ tag.wrapping_mul(0x9e37_79b9_7f4a_7c15));
368    let stride = mix_filter_hash(
369        high ^ tenant_hash.rotate_left(29) ^ tag.wrapping_mul(0xd6e8_feb8_6659_fd93),
370    ) | 1;
371    let bit_count = CORRELATION_FILTER_WORDS * 64;
372    let mut bits = [0; CORRELATION_FILTER_HASHES];
373    for (index, bit) in bits.iter_mut().enumerate() {
374        *bit = first.wrapping_add((index as u64).wrapping_mul(stride)) as usize % bit_count;
375    }
376    bits
377}
378
379const fn mix_filter_hash(mut value: u64) -> u64 {
380    value ^= value >> 30;
381    value = value.wrapping_mul(0xbf58_476d_1ce4_e5b9);
382    value ^= value >> 27;
383    value = value.wrapping_mul(0x94d0_49bb_1331_11eb);
384    value ^ (value >> 31)
385}
386
387pub(crate) fn span_matches_correlation(query: &CorrelationQuery, span: &DurableSpan) -> bool {
388    if span.tenant != query.tenant {
389        return false;
390    }
391    let mut observed = Vec::new();
392    visit_span_keys(span, |_, key| observed.push(key));
393    query_keys(query).all(|key| observed.contains(&key))
394}
395
396pub(crate) fn metric_matches_correlation(
397    query: &CorrelationQuery,
398    point: &DurableMetricPoint,
399) -> bool {
400    if point.identity.tenant != query.tenant {
401        return false;
402    }
403    let mut observed = Vec::new();
404    visit_metric_keys(point, |_, key| observed.push(key));
405    query_keys(query).all(|key| observed.contains(&key))
406}
407
408fn visit_span_keys(span: &DurableSpan, mut visit: impl FnMut(&str, CorrelationKey)) {
409    let tenant = span.tenant.as_ref();
410    visit(tenant, CorrelationKey::Trace(span.trace_id));
411    visit(tenant, CorrelationKey::Resource(span.resource_id()));
412    visit(tenant, CorrelationKey::Scope(span.scope_id()));
413    visit_attributes(tenant, span.resource.attributes.iter(), &mut visit);
414    visit_attributes(tenant, span.scope.attributes.iter(), &mut visit);
415    visit_attributes(tenant, span.attributes.iter(), &mut visit);
416    for event in span.events.iter() {
417        visit_attributes(tenant, event.attributes.iter(), &mut visit);
418    }
419    for link in span.links.iter() {
420        visit(tenant, CorrelationKey::Trace(link.trace_id));
421        visit_attributes(tenant, link.attributes.iter(), &mut visit);
422    }
423}
424
425fn visit_metric_keys(point: &DurableMetricPoint, mut visit: impl FnMut(&str, CorrelationKey)) {
426    let tenant = point.identity.tenant.as_ref();
427    visit(
428        tenant,
429        CorrelationKey::Resource(point.identity.resource_id()),
430    );
431    visit(tenant, CorrelationKey::Scope(point.identity.scope_id()));
432    visit_attributes(
433        tenant,
434        point.identity.resource.attributes.iter(),
435        &mut visit,
436    );
437    visit_attributes(tenant, point.identity.scope.attributes.iter(), &mut visit);
438    visit_attributes(tenant, point.identity.point_attributes.iter(), &mut visit);
439    visit_attributes(tenant, point.metadata.iter(), &mut visit);
440    for exemplar in point.exemplars.iter() {
441        if let Some(trace_id) = exemplar.trace_id {
442            visit(tenant, CorrelationKey::Trace(trace_id));
443        }
444        visit_attributes(tenant, exemplar.filtered_attributes.iter(), &mut visit);
445    }
446}
447
448fn visit_attributes<'a>(
449    tenant: &str,
450    attributes: impl Iterator<Item = &'a TelemetryAttribute>,
451    visit: &mut impl FnMut(&str, CorrelationKey),
452) {
453    for attribute in attributes {
454        visit(tenant, CorrelationKey::Attribute(attribute.fingerprint()));
455    }
456}
457
458/// Preallocated, single-writer correlation postings owned by one stripe.
459///
460/// Reaching a bound drops only an optional navigation posting; durable signal
461/// storage and each signal's exact native indexes remain authoritative.
462#[derive(Debug)]
463pub struct CorrelationIndex {
464    config: CorrelationConfig,
465    tenants: HashMap<Arc<str>, u32>,
466    postings: HashMap<(u32, CorrelationKey), Vec<CorrelationPosting>>,
467    resource_pointer_ids: Vec<Option<CachedResourceId>>,
468    resource_ids: Vec<Option<CachedResourceId>>,
469    scope_pointer_ids: Vec<Option<CachedScopeId>>,
470    scope_ids: Vec<Option<CachedScopeId>>,
471    attribute_pointer_ids: Vec<Option<CachedAttributeIds>>,
472    attribute_ids: Vec<Option<CachedAttributeIds>>,
473    refs: usize,
474    dropped_postings: u64,
475}
476
477#[derive(Debug, Clone, Copy, PartialEq, Eq)]
478struct CorrelationPosting {
479    record_ref: TelemetryRecordRef,
480    timestamp_unix_nanos: u64,
481}
482
483#[derive(Debug)]
484struct CachedResourceId {
485    hash: u64,
486    context: Arc<ResourceContext>,
487    id: ResourceContextId,
488}
489
490#[derive(Debug)]
491struct CachedScopeId {
492    hash: u64,
493    context: Arc<ScopeContext>,
494    id: ScopeContextId,
495}
496
497#[derive(Debug)]
498struct CachedAttributeIds {
499    hash: u64,
500    attributes: Arc<Vec<TelemetryAttribute>>,
501    ids: Arc<[AttributeFingerprint]>,
502}
503
504impl CorrelationIndex {
505    /// Creates a bounded stripe-local index.
506    #[must_use]
507    pub fn new(config: CorrelationConfig) -> Self {
508        Self {
509            config,
510            tenants: HashMap::new(),
511            postings: HashMap::with_capacity(config.max_keys.min(4_096)),
512            resource_pointer_ids: std::iter::repeat_with(|| None)
513                .take(CONTEXT_ID_CACHE_ENTRIES)
514                .collect(),
515            resource_ids: std::iter::repeat_with(|| None)
516                .take(CONTEXT_ID_CACHE_ENTRIES)
517                .collect(),
518            scope_pointer_ids: std::iter::repeat_with(|| None)
519                .take(CONTEXT_ID_CACHE_ENTRIES)
520                .collect(),
521            scope_ids: std::iter::repeat_with(|| None)
522                .take(CONTEXT_ID_CACHE_ENTRIES)
523                .collect(),
524            attribute_pointer_ids: std::iter::repeat_with(|| None)
525                .take(ATTRIBUTE_ID_CACHE_ENTRIES)
526                .collect(),
527            attribute_ids: std::iter::repeat_with(|| None)
528                .take(ATTRIBUTE_ID_CACHE_ENTRIES)
529                .collect(),
530            refs: 0,
531            dropped_postings: 0,
532        }
533    }
534
535    /// Indexes one durable log without retaining its body or metadata values.
536    pub fn index_log(&mut self, tenant: &str, log: &DurableLog) {
537        let Some(tenant_id) = self.tenant_id(tenant) else {
538            return;
539        };
540        if let Some(trace_id) = log.trace_id {
541            self.insert(
542                tenant_id,
543                CorrelationKey::Trace(trace_id),
544                log.record_ref,
545                log.timestamp_unix_nanos,
546            );
547        }
548        self.index_contexts(
549            tenant_id,
550            log.record_ref,
551            log.timestamp_unix_nanos,
552            &log.resource,
553            &log.scope,
554        );
555        self.index_attribute_set(
556            tenant_id,
557            log.record_ref,
558            log.timestamp_unix_nanos,
559            &log.attributes,
560        );
561    }
562
563    /// Indexes one durable span, including event and link metadata.
564    pub fn index_span(&mut self, span: &DurableSpan) {
565        let tenant = span.tenant.as_ref();
566        let Some(tenant_id) = self.tenant_id(tenant) else {
567            return;
568        };
569        self.insert(
570            tenant_id,
571            CorrelationKey::Trace(span.trace_id),
572            span.record_ref,
573            span.start_time_unix_nanos,
574        );
575        for link in span.links.iter() {
576            self.insert(
577                tenant_id,
578                CorrelationKey::Trace(link.trace_id),
579                span.record_ref,
580                span.start_time_unix_nanos,
581            );
582            self.index_attribute_set(
583                tenant_id,
584                span.record_ref,
585                span.start_time_unix_nanos,
586                &link.attributes,
587            );
588        }
589        self.index_contexts(
590            tenant_id,
591            span.record_ref,
592            span.start_time_unix_nanos,
593            &span.resource,
594            &span.scope,
595        );
596        self.index_attribute_set(
597            tenant_id,
598            span.record_ref,
599            span.start_time_unix_nanos,
600            &span.attributes,
601        );
602        for event in span.events.iter() {
603            self.index_attribute_set(
604                tenant_id,
605                span.record_ref,
606                span.start_time_unix_nanos,
607                &event.attributes,
608            );
609        }
610    }
611
612    /// Indexes one metric point and connects exemplar trace IDs directly.
613    pub fn index_metric(&mut self, point: &DurableMetricPoint) {
614        let tenant = point.identity.tenant.as_ref();
615        let Some(tenant_id) = self.tenant_id(tenant) else {
616            return;
617        };
618        for exemplar in point.exemplars.iter() {
619            if let Some(trace_id) = exemplar.trace_id {
620                self.insert(
621                    tenant_id,
622                    CorrelationKey::Trace(trace_id),
623                    point.record_ref,
624                    point.timestamp_unix_nanos,
625                );
626            }
627            self.index_attribute_set(
628                tenant_id,
629                point.record_ref,
630                point.timestamp_unix_nanos,
631                &exemplar.filtered_attributes,
632            );
633        }
634        self.index_contexts(
635            tenant_id,
636            point.record_ref,
637            point.timestamp_unix_nanos,
638            &point.identity.resource,
639            &point.identity.scope,
640        );
641        self.index_attribute_set(
642            tenant_id,
643            point.record_ref,
644            point.timestamp_unix_nanos,
645            &point.identity.point_attributes,
646        );
647        self.index_attribute_set(
648            tenant_id,
649            point.record_ref,
650            point.timestamp_unix_nanos,
651            &point.metadata,
652        );
653    }
654
655    /// Returns the deterministic intersection of every requested posting.
656    #[must_use]
657    pub fn query(&self, query: &CorrelationQuery) -> Vec<TelemetryRecordRef> {
658        let mut keys = Vec::with_capacity(3 + query.attributes.len());
659        if let Some(trace_id) = query.trace_id {
660            keys.push(CorrelationKey::Trace(trace_id));
661        }
662        if let Some(resource_id) = query.resource_id {
663            keys.push(CorrelationKey::Resource(resource_id));
664        }
665        if let Some(scope_id) = query.scope_id {
666            keys.push(CorrelationKey::Scope(scope_id));
667        }
668        keys.extend(
669            query
670                .attributes
671                .iter()
672                .copied()
673                .map(CorrelationKey::Attribute),
674        );
675        if keys.is_empty() || query.limit == 0 {
676            return Vec::new();
677        }
678        let Some(tenant_id) = self.tenants.get(query.tenant.as_ref()).copied() else {
679            return Vec::new();
680        };
681        let mut lists = keys
682            .into_iter()
683            .map(|key| {
684                self.postings
685                    .get(&(tenant_id, key))
686                    .map(Vec::as_slice)
687                    .unwrap_or_default()
688            })
689            .collect::<Vec<_>>();
690        lists.sort_unstable_by_key(|list| list.len());
691        let Some(first) = lists.first() else {
692            return Vec::new();
693        };
694        let start = query.after.map_or(0, |after| {
695            first.partition_point(|posting| posting.record_ref <= after)
696        });
697        let mut selected = Vec::with_capacity(query.limit.min(first.len().saturating_sub(start)));
698        let mut cursors = lists[1..]
699            .iter()
700            .map(|incoming| {
701                query.after.map_or(0, |after| {
702                    incoming.partition_point(|posting| posting.record_ref <= after)
703                })
704            })
705            .collect::<Vec<_>>();
706        'candidate: for posting in &first[start..] {
707            let record = posting.record_ref;
708            if query.signal.is_some_and(|signal| record.signal != signal) {
709                continue;
710            }
711            if query
712                .start_time_unix_nanos
713                .is_some_and(|start| posting.timestamp_unix_nanos < start)
714                || query
715                    .end_time_unix_nanos
716                    .is_some_and(|end| posting.timestamp_unix_nanos > end)
717            {
718                continue;
719            }
720            for (incoming, cursor) in lists[1..].iter().zip(&mut cursors) {
721                while incoming
722                    .get(*cursor)
723                    .is_some_and(|current| current.record_ref < record)
724                {
725                    *cursor += 1;
726                }
727                let Some(current) = incoming.get(*cursor) else {
728                    return selected;
729                };
730                if current.record_ref != record {
731                    continue 'candidate;
732                }
733            }
734            selected.push(record);
735            if selected.len() == query.limit {
736                break;
737            }
738        }
739        selected
740    }
741
742    /// Drops expired bounded navigation postings without touching durable data.
743    pub fn retain_since_timestamp(&mut self, cutoff_timestamp_unix_nanos: u64) {
744        let mut retained = 0usize;
745        self.postings.retain(|_, postings| {
746            postings.retain(|posting| posting.timestamp_unix_nanos >= cutoff_timestamp_unix_nanos);
747            retained = retained.saturating_add(postings.len());
748            !postings.is_empty()
749        });
750        self.refs = retained;
751    }
752
753    /// Returns current bounds and drop diagnostics.
754    #[must_use]
755    pub fn stats(&self) -> CorrelationStats {
756        CorrelationStats {
757            keys: self.postings.len(),
758            refs: self.refs,
759            dropped_postings: self.dropped_postings,
760        }
761    }
762
763    fn index_contexts(
764        &mut self,
765        tenant_id: u32,
766        record_ref: TelemetryRecordRef,
767        timestamp_unix_nanos: u64,
768        resource: &Arc<ResourceContext>,
769        scope: &Arc<ScopeContext>,
770    ) {
771        let resource_id = self.resource_id(resource);
772        let scope_id = self.scope_id(scope);
773        self.insert(
774            tenant_id,
775            CorrelationKey::Resource(resource_id),
776            record_ref,
777            timestamp_unix_nanos,
778        );
779        self.insert(
780            tenant_id,
781            CorrelationKey::Scope(scope_id),
782            record_ref,
783            timestamp_unix_nanos,
784        );
785        self.index_attribute_set(
786            tenant_id,
787            record_ref,
788            timestamp_unix_nanos,
789            &resource.attributes,
790        );
791        self.index_attribute_set(
792            tenant_id,
793            record_ref,
794            timestamp_unix_nanos,
795            &scope.attributes,
796        );
797    }
798
799    fn index_attribute_set(
800        &mut self,
801        tenant_id: u32,
802        record_ref: TelemetryRecordRef,
803        timestamp_unix_nanos: u64,
804        attributes: &Arc<Vec<TelemetryAttribute>>,
805    ) {
806        for id in self.attribute_ids(attributes).iter().copied() {
807            self.insert(
808                tenant_id,
809                CorrelationKey::Attribute(id),
810                record_ref,
811                timestamp_unix_nanos,
812            );
813        }
814    }
815
816    fn resource_id(&mut self, context: &Arc<ResourceContext>) -> ResourceContextId {
817        let pointer_slot = pointer_cache_slot(Arc::as_ptr(context), CONTEXT_ID_CACHE_ENTRIES);
818        if let Some(cached) = &self.resource_pointer_ids[pointer_slot]
819            && Arc::ptr_eq(&cached.context, context)
820        {
821            return cached.id;
822        }
823        let hash = identity_hash(context.as_ref());
824        let slot = hash as usize & (CONTEXT_ID_CACHE_ENTRIES - 1);
825        if let Some(cached) = &self.resource_ids[slot]
826            && cached.hash == hash
827            && (Arc::ptr_eq(&cached.context, context)
828                || cached.context.as_ref() == context.as_ref())
829        {
830            self.resource_pointer_ids[pointer_slot] = Some(CachedResourceId {
831                hash,
832                context: Arc::clone(context),
833                id: cached.id,
834            });
835            return cached.id;
836        }
837        let id = context.id();
838        self.resource_pointer_ids[pointer_slot] = Some(CachedResourceId {
839            hash,
840            context: Arc::clone(context),
841            id,
842        });
843        self.resource_ids[slot] = Some(CachedResourceId {
844            hash,
845            context: Arc::clone(context),
846            id,
847        });
848        id
849    }
850
851    fn scope_id(&mut self, context: &Arc<ScopeContext>) -> ScopeContextId {
852        let pointer_slot = pointer_cache_slot(Arc::as_ptr(context), CONTEXT_ID_CACHE_ENTRIES);
853        if let Some(cached) = &self.scope_pointer_ids[pointer_slot]
854            && Arc::ptr_eq(&cached.context, context)
855        {
856            return cached.id;
857        }
858        let hash = identity_hash(context.as_ref());
859        let slot = hash as usize & (CONTEXT_ID_CACHE_ENTRIES - 1);
860        if let Some(cached) = &self.scope_ids[slot]
861            && cached.hash == hash
862            && (Arc::ptr_eq(&cached.context, context)
863                || cached.context.as_ref() == context.as_ref())
864        {
865            self.scope_pointer_ids[pointer_slot] = Some(CachedScopeId {
866                hash,
867                context: Arc::clone(context),
868                id: cached.id,
869            });
870            return cached.id;
871        }
872        let id = context.id();
873        self.scope_pointer_ids[pointer_slot] = Some(CachedScopeId {
874            hash,
875            context: Arc::clone(context),
876            id,
877        });
878        self.scope_ids[slot] = Some(CachedScopeId {
879            hash,
880            context: Arc::clone(context),
881            id,
882        });
883        id
884    }
885
886    fn attribute_ids(
887        &mut self,
888        attributes: &Arc<Vec<TelemetryAttribute>>,
889    ) -> Arc<[AttributeFingerprint]> {
890        let pointer_slot = pointer_cache_slot(Arc::as_ptr(attributes), ATTRIBUTE_ID_CACHE_ENTRIES);
891        if let Some(cached) = &self.attribute_pointer_ids[pointer_slot]
892            && Arc::ptr_eq(&cached.attributes, attributes)
893        {
894            return Arc::clone(&cached.ids);
895        }
896        let hash = identity_hash(attributes.as_ref());
897        let slot = hash as usize & (ATTRIBUTE_ID_CACHE_ENTRIES - 1);
898        if let Some(cached) = &self.attribute_ids[slot]
899            && cached.hash == hash
900            && (Arc::ptr_eq(&cached.attributes, attributes)
901                || cached.attributes.as_ref() == attributes.as_ref())
902        {
903            self.attribute_pointer_ids[pointer_slot] = Some(CachedAttributeIds {
904                hash,
905                attributes: Arc::clone(attributes),
906                ids: Arc::clone(&cached.ids),
907            });
908            return Arc::clone(&cached.ids);
909        }
910        let ids = attributes
911            .iter()
912            .map(TelemetryAttribute::fingerprint)
913            .collect::<Arc<[_]>>();
914        self.attribute_pointer_ids[pointer_slot] = Some(CachedAttributeIds {
915            hash,
916            attributes: Arc::clone(attributes),
917            ids: Arc::clone(&ids),
918        });
919        self.attribute_ids[slot] = Some(CachedAttributeIds {
920            hash,
921            attributes: Arc::clone(attributes),
922            ids: Arc::clone(&ids),
923        });
924        ids
925    }
926
927    fn tenant_id(&mut self, tenant: &str) -> Option<u32> {
928        if let Some(tenant_id) = self.tenants.get(tenant).copied() {
929            return Some(tenant_id);
930        }
931        if self.postings.len() >= self.config.max_keys {
932            self.dropped_postings = self.dropped_postings.saturating_add(1);
933            return None;
934        }
935        let tenant_id = u32::try_from(self.tenants.len()).ok()?;
936        self.tenants.insert(Arc::from(tenant), tenant_id);
937        Some(tenant_id)
938    }
939
940    fn insert(
941        &mut self,
942        tenant_id: u32,
943        key: CorrelationKey,
944        record_ref: TelemetryRecordRef,
945        timestamp_unix_nanos: u64,
946    ) {
947        let lookup = (tenant_id, key);
948        let refs = if self.postings.len() < self.config.max_keys {
949            self.postings.entry(lookup).or_default()
950        } else if let Some(refs) = self.postings.get_mut(&lookup) {
951            refs
952        } else {
953            self.dropped_postings = self.dropped_postings.saturating_add(1);
954            return;
955        };
956        if refs
957            .last()
958            .is_some_and(|posting| posting.record_ref == record_ref)
959        {
960            return;
961        }
962        if refs.len() >= self.config.max_refs_per_key || self.refs >= self.config.max_total_refs {
963            self.dropped_postings = self.dropped_postings.saturating_add(1);
964            return;
965        }
966        let posting = CorrelationPosting {
967            record_ref,
968            timestamp_unix_nanos,
969        };
970        if refs.last().is_none_or(|last| last.record_ref < record_ref) {
971            refs.push(posting);
972        } else {
973            match refs.binary_search_by_key(&record_ref, |posting| posting.record_ref) {
974                Ok(_) => return,
975                Err(position) => refs.insert(position, posting),
976            }
977        }
978        self.refs += 1;
979    }
980}
981
982#[inline]
983fn pointer_cache_slot<T>(pointer: *const T, entries: usize) -> usize {
984    let address = pointer as usize;
985    (address ^ (address >> 12) ^ (address >> 24)) & (entries - 1)
986}
987
988fn identity_hash(value: &impl Hash) -> u64 {
989    foldhash::fast::FixedState::with_seed(0x5348_4152_4443_4f52).hash_one(value)
990}
991
992#[cfg(test)]
993mod tests {
994    use shard_stream_core::{LogicalOffset, LogicalPartitionId, ShardId, TopicPartition};
995
996    use super::*;
997    use crate::{
998        CompressionCohortId, DurableLog, LOGS_TOPIC_ID, ResourceContext, ScopeContext,
999        TelemetryValue,
1000    };
1001
1002    #[test]
1003    fn shared_typed_metadata_connects_signals_without_retaining_values() {
1004        let service = TelemetryAttribute::new(
1005            "service.name",
1006            TelemetryValue::String(Arc::from("checkout")),
1007        );
1008        let resource = Arc::new(ResourceContext {
1009            attributes: Arc::new(vec![service.clone()]),
1010            ..ResourceContext::default()
1011        });
1012        let scope = Arc::new(ScopeContext::default());
1013        let partition = TopicPartition::new(LOGS_TOPIC_ID, LogicalPartitionId::new(1));
1014        let mut log = DurableLog::new(
1015            ShardId::new(0),
1016            partition,
1017            LogicalOffset::new(7),
1018            42,
1019            "request complete",
1020            CompressionCohortId::new(1),
1021        );
1022        log.resource = resource;
1023        log.scope = scope;
1024        let mut index = CorrelationIndex::new(CorrelationConfig::default());
1025        index.index_log("tenant-a", &log);
1026
1027        let refs = index.query(
1028            &CorrelationQuery::new("tenant-a")
1029                .with_resource_id(log.resource_id())
1030                .with_attribute(&service),
1031        );
1032        assert_eq!(refs, vec![log.record_ref]);
1033        assert_eq!(index.stats().refs, 3);
1034    }
1035
1036    #[test]
1037    fn bounds_drop_only_optional_postings() {
1038        let mut index = CorrelationIndex::new(CorrelationConfig {
1039            max_keys: 1,
1040            max_refs_per_key: 1,
1041            max_total_refs: 1,
1042        });
1043        let partition = TopicPartition::new(LOGS_TOPIC_ID, LogicalPartitionId::new(1));
1044        for offset in 0..2 {
1045            let log = DurableLog::new(
1046                ShardId::new(0),
1047                partition,
1048                LogicalOffset::new(offset),
1049                offset,
1050                "message",
1051                CompressionCohortId::new(1),
1052            );
1053            index.index_log("tenant-a", &log);
1054        }
1055        assert_eq!(index.stats().refs, 1);
1056        assert!(index.stats().dropped_postings > 0);
1057    }
1058
1059    #[test]
1060    fn bounded_intersection_preserves_order_filters_and_pagination() {
1061        let first = TelemetryAttribute::new("shared", TelemetryValue::String(Arc::from("yes")));
1062        let second = TelemetryAttribute::new("region", TelemetryValue::String(Arc::from("east")));
1063        let partition = TopicPartition::new(LOGS_TOPIC_ID, LogicalPartitionId::new(1));
1064        let mut index = CorrelationIndex::new(CorrelationConfig {
1065            max_keys: 2,
1066            max_refs_per_key: 20_000,
1067            max_total_refs: 40_000,
1068        });
1069        let tenant_id = index.tenant_id("tenant-a").expect("tenant is admitted");
1070        for offset in 0..10_000 {
1071            let record = TelemetryRecordRef::for_signal(
1072                TelemetrySignal::Logs,
1073                partition,
1074                LogicalOffset::new(offset),
1075            );
1076            index.insert(
1077                tenant_id,
1078                CorrelationKey::Attribute(first.fingerprint()),
1079                record,
1080                offset,
1081            );
1082            if offset % 2 == 0 {
1083                index.insert(
1084                    tenant_id,
1085                    CorrelationKey::Attribute(second.fingerprint()),
1086                    record,
1087                    offset,
1088                );
1089            }
1090        }
1091        let after = TelemetryRecordRef::for_signal(
1092            TelemetrySignal::Logs,
1093            partition,
1094            LogicalOffset::new(4_990),
1095        );
1096        let result = index.query(
1097            &CorrelationQuery::new("tenant-a")
1098                .with_attribute(&first)
1099                .with_attribute(&second)
1100                .for_signal(TelemetrySignal::Logs)
1101                .after(after)
1102                .with_limit(3),
1103        );
1104        assert_eq!(
1105            result
1106                .iter()
1107                .map(|record| record.offset.get())
1108                .collect::<Vec<_>>(),
1109            vec![4_992, 4_994, 4_996]
1110        );
1111    }
1112
1113    #[test]
1114    fn time_bounds_and_retention_remove_expired_navigation_postings() {
1115        let resource = Arc::new(ResourceContext {
1116            attributes: Arc::new(vec![TelemetryAttribute::new(
1117                "service.name",
1118                TelemetryValue::String(Arc::from("checkout")),
1119            )]),
1120            ..ResourceContext::default()
1121        });
1122        let partition = TopicPartition::new(LOGS_TOPIC_ID, LogicalPartitionId::new(1));
1123        let mut index = CorrelationIndex::new(CorrelationConfig::default());
1124        for (offset, timestamp) in [(0, 10), (1, 20)] {
1125            let mut log = DurableLog::new(
1126                ShardId::new(0),
1127                partition,
1128                LogicalOffset::new(offset),
1129                timestamp,
1130                "message",
1131                CompressionCohortId::new(1),
1132            );
1133            log.resource = Arc::clone(&resource);
1134            index.index_log("tenant-a", &log);
1135        }
1136        let query = CorrelationQuery {
1137            start_time_unix_nanos: Some(15),
1138            ..CorrelationQuery::new("tenant-a").with_resource_id(resource.id())
1139        };
1140        assert_eq!(
1141            index
1142                .query(&query)
1143                .into_iter()
1144                .map(|record| record.offset.get())
1145                .collect::<Vec<_>>(),
1146            vec![1]
1147        );
1148
1149        index.retain_since_timestamp(15);
1150        assert_eq!(index.query(&query).len(), 1);
1151        assert!(index.stats().refs > 0);
1152        let expired = CorrelationQuery {
1153            end_time_unix_nanos: Some(14),
1154            ..CorrelationQuery::new("tenant-a").with_resource_id(resource.id())
1155        };
1156        assert!(index.query(&expired).is_empty());
1157    }
1158}