Approach: Maintain up to N active traces in memory. Deterministically keep any trace whose observed latency (max span end - min span start) exceeds threshold T; other traces are sampled with probability p. Use an LRU-style eviction that first discards non-deterministic (probabilistic) traces, oldest-first; never evict a deterministic trace. Handle out-of-order spans by updating trace window on span arrival and promoting to deterministic if threshold crossed. Use lightweight metadata only until a trace is closed/evicted.Pseudocode (Python-style):python
# Data structures
# TraceEntry: {trace_id, first_start, last_end, spans_count, deterministic_flag, sampled_flag, last_seen_ts}
# active: dict trace_id -> TraceEntry
# lru_queue: deque of trace_ids for non-deterministic traces ordered by last_seen_ts
# N: memory limit, T: latency threshold, p: sampling probability
def on_span(span):
tid = span.trace_id
now = span.timestamp
e = active.get(tid)
if not e:
# create metadata lightweight
e = TraceEntry(tid, span.start, span.end, 1, False, False, now)
active[tid] = e
# decide probabilistic sample immediately
e.sampled_flag = (random() < p)
if not e.sampled_flag:
# not sampled; still track because may cross threshold
lru_queue.append(tid)
else:
# update window for out-of-order spans
e.first_start = min(e.first_start, span.start)
e.last_end = max(e.last_end, span.end)
e.spans_count += 1
e.last_seen_ts = now
if not e.sampled_flag:
# move to back of LRU if present
if tid in lru_queue:
lru_queue.remove(tid)
lru_queue.append(tid)
# check deterministic promotion
latency = e.last_end - e.first_start
if latency >= T and not e.deterministic_flag:
e.deterministic_flag = True
e.sampled_flag = True
# remove from lru if present
if tid in lru_queue: lru_queue.remove(tid)
enforce_memory_bound()
def enforce_memory_bound():
while len(active) > N:
# evict oldest non-deterministic trace first
if lru_queue:
victim = lru_queue.popleft()
del active[victim]
else:
# all active are deterministic -> must increase N or force best-effort drop:
# drop the non-deterministic trace with oldest last_seen (none exist), so break
break
