Frequency Tracking at Scale: Fitting Recency, Counts, and First-Sightings into 64 Bits

#go #algorithms #architecture #webdev

A look at interpreted decay, 64-bit word packing, and how to track frequency in nanoseconds with zero background cleanup.

The Real-World Dilemma: The Coffee Shop Barista

Imagine a busy coffee shop in a tech hub.

The barista doesn't need a massive ledger tracking every single customer who bought coffee over the past five years. To manage the line effectively, they only need answers to a few immediate questions:

Has this customer come in multiple times in the last hour? (Frequency)
Was their last visit just now, or 4 hours ago? (Recency)
Is this their very first visit during this rush window? (First sighting)

In software engineering, backend services face this exact challenge every second. Whether you are building an API rate-limiter, a proxy gateway, an anomaly detector, or an LLM prompt cache, you need to answer: “How often has this IP or user key occurred **lately?”

Doing this for millions of unique keys in high-throughput services turns out to be surprisingly tricky.

Understanding the Trade-Offs of Traditional Approaches

When engineers design frequency tracking at scale, they choose different tools depending on their primary constraints. Here is how common approaches compare:

┌─────────────────────────────────────────────────────────────────────────┐
│ 1. In-Memory Hash Map  │ map[string]int                                 │
│    → Unlimited RAM growth under scrapers or randomized IP floods.       │
├─────────────────────────────────────────────────────────────────────────┤
│ 2. Count-Min Sketch    │ Fixed memory probabilistic counters            │
│    → No recency. Old traffic looks forever hot unless wiped completely. │
├─────────────────────────────────────────────────────────────────────────┤
│ 3. Background Decay    │ Periodic threads halving counters in memory    │
│    → Stop-the-world locks, thread contention, and GC pauses.            │
└─────────────────────────────────────────────────────────────────────────┘

A Plain Hash Map (map[key]int): Exact, but dangerous. An attacker cycling through millions of spoofed IP addresses or random API keys will bloat your heap until the process hits Out-Of-Memory (OOM).
Count-Min Sketch: Uses fixed memory, but has no concept of time. A key that was spammed 100,000 times yesterday looks just as active today as a key spammed right now—unless you flush the entire structure and lose all history.
Background Cleanup / Sweeping Threads: Structures like TinyLFU introduce decay by periodically looping through memory to halve all counter values. But running a background mutator thread across millions of entries introduces lock contention, CPU cache invalidation, and garbage collection (GC) spikes right when your traffic is highest.

Can we get fixed memory, instant recency decay, and lock-free speed without relying on a background thread?

The Core Idea: Interpreted Decay

Instead of spawning a background thread to update stored counts when time moves forward, what if we never mutate stored counts to decay them at all?

What if decay is calculated on-the-fly when reading the data?

We call this Interpreted Decay.

How it works in simple terms:

Time is divided into discrete windows called epochs (for instance, 1 tick = 1 second).

When a key is recorded, we store two numbers together:

The raw count accumulated so far.
The epoch timestamp of when that count was last updated.

When a query reads the entry later, it compares the current_epoch with the stored_epoch:

age = current_epoch - stored_epoch

Instead of running a costly division or float math, the decayed estimate is calculated using a simple bit-shift:

effective_count = stored_count >> age

Time: Epoch 10                        Time: Epoch 12 (2 seconds later)
┌──────────────────────────────┐      ┌──────────────────────────────┐
│ Stored Count: 16             │      │ Stored Count: 16 (Unchanged!)│
│ Stored Epoch: 10             │      │ Stored Epoch: 10             │
└──────────────────────────────┘      └──────────────────────────────┘
                                                    │
                                                    ▼ Read-time Interpretation:
                                             age = 12 - 10 = 2
                                             effective_count = 16 >> 2 = 4

Notice what happened here: No background worker touched memory during those 2 seconds. The data structure stayed completely passive. The moment a thread reads the slot, bitwise math naturally decays the value.

Three Questions in One 64-Bit Word

To make this execution blazing fast in modern hardware, every single entry in EpochSketch is packed into a single 64-bit integer (uint64).

Why 64 bits? Because 64 bits fit perfectly in a single CPU register and can be read or modified using a single atomic operation (Compare-And-Swap / CAS) on any 64-bit processor.

Here is how the bits are laid out:

 63                    48 47                    24 23                     0
┌────────────────────────┬────────────────────────┬────────────────────────┐
│      Tag (16 bits)     │     Epoch (24 bits)    │     Count (24 bits)    │
└────────────────────────┴────────────────────────┴────────────────────────┘

Packed inside this 64-bit word, we get answers to three crucial questions in nanoseconds:

Tag (16 bits): A shortened hash signature of the key. “Is this slot tracking my key, or a hash collision?”
Epoch (24 bits): The timestamp of the last write. “How old is this frequency counter?”
Count (24 bits): The raw count (saturates up to $16,777,215$). Combined with the epoch, this yields the decayed frequency.

Furthermore, if the slot was empty, stale, or evicted on this write, the operation returns first = true. This provides an immediate first-sighting signal—perfect for triggering anomaly alerts the very first time an IP appears in a time window.

Seeing it in Code (Go)

Using EpochSketch in Go takes just a few lines:

package main

import (
    "fmt"
    "time"

    "github.com/shyam-s00/epochsketch"
)

func main() {
    // Initialize a fixed table (65,536 buckets) with a 1-second tick
    sk := epochsketch.New(epochsketch.Config{
        NumBuckets:   1 << 16,
        TickDuration: time.Second,
    })

    // Observe a client key multiple times
    for i := 0; i < 3; i++ {
        est, first := sk.Observe("api_client:192.168.1.50")
        fmt.Printf("Observe #%d -> Estimate: %d, First Sight: %v\n", i+1, est, first)
    }

    // A brand new key arriving in the same window
    est, first := sk.Observe("api_client:10.0.0.1")
    fmt.Printf("New Key     -> Estimate: %d, First Sight: %v\n", est, first)
}

Output:

Observe #1 -> Estimate: 1, First Sight: true
Observe #2 -> Estimate: 2, First Sight: false
Observe #3 -> Estimate: 3, First Sight: false
New Key     -> Estimate: 1, First Sight: true

Zero heap allocations per Observe call. Single-digit nanosecond execution times. Fixed memory overhead that never grows, regardless of how many million requests hit your system.

In summary, by shifting decay from a background mutation to a read-time bitwise interpretation, we get predictable fixed memory, zero background thread overhead, and lock-free execution speed.

This post is Part 1 of an ongoing series on high-performance data structures and zero-infrastructure proxy patterns. In Part 2, we will take a quick look under the hood at atomic CAS concurrency and slot eviction mechanics under multi-threaded traffic.

💡 Try it interactively: You can watch raw 64-bit slots flip, decay, and evict live in your browser using the zero-dependency interactive simulator at epochsketch.dev (or view simulator/epochsketch-simulator.html).