1use 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub struct CorrelationConfig {
21 pub max_keys: usize,
23 pub max_refs_per_key: usize,
25 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#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
41pub struct CorrelationStats {
42 pub keys: usize,
44 pub refs: usize,
46 pub dropped_postings: u64,
48}
49
50#[derive(Debug, Clone, PartialEq, Eq)]
52pub struct CorrelationQuery {
53 pub tenant: Arc<str>,
55 pub trace_id: Option<TraceId>,
57 pub resource_id: Option<ResourceContextId>,
59 pub scope_id: Option<ScopeContextId>,
61 pub attributes: Arc<Vec<AttributeFingerprint>>,
63 pub labels: Arc<Vec<(Arc<str>, Arc<str>)>>,
65 pub signal: Option<TelemetrySignal>,
67 pub start_time_unix_nanos: Option<u64>,
69 pub end_time_unix_nanos: Option<u64>,
71 pub after: Option<TelemetryRecordRef>,
73 pub limit: usize,
75}
76
77impl CorrelationQuery {
78 #[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 #[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 #[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 #[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 #[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 #[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 #[must_use]
142 pub const fn for_signal(mut self, signal: TelemetrySignal) -> Self {
143 self.signal = Some(signal);
144 self
145 }
146
147 #[must_use]
149 pub const fn after(mut self, record_ref: TelemetryRecordRef) -> Self {
150 self.after = Some(record_ref);
151 self
152 }
153
154 #[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#[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 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 #[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 #[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 #[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 #[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#[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 #[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 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 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 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 #[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 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 #[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}