HotRing – Hot Key Tracking

hotring is NoKV’s built-in hot-key tracker. It samples read/write access frequency per key and exposes the hottest entries to the stats subsystem and CLI. The implementation resides in hotring/.

1. Motivation

• Cache hints – DB.prefetchLoop (see db.go) consumes hot keys to schedule asynchronous reads into the block cache.
• Operational insight – StatsSnapshot.HotKeys and nokv stats --json surface the hottest keys, aiding debugging of traffic hotspots.
• Throttling – HotRing.TouchAndClamp enables simple rate caps: once a key crosses a threshold, callers can back off or log alerts.

Compared with RocksDB (which exposes block access stats via perf_context) and Badger (which lacks built-in hot-key reporting), NoKV offers a lightweight but concurrent-friendly tracker out of the box.

2. Data Structure

HotRing
  buckets[] -> per-bucket lock-free linked list (Node)
  hashFn   -> hash(key) -> uint32
  hashMask -> selects bucket (power of two size)

• Each bucket stores a sorted linked list of Node ordered by (tag, key), where tag is derived from the upper bits of the hash. Head pointers are atomic.Pointer[Node], so readers walk the list without taking locks; writers use CAS to splice nodes while preserving order.
• defaultTableBits = 12 → 4096 buckets by default (NewHotRing). The mask ensures cheap modulo operations.
• Nodes keep a count (int32) updated atomically and a next pointer stored via unsafe.Pointer. Sliding-window state is guarded by a tiny per-node spin lock instead of a process-wide mutex.

flowchart LR
  Key(key) -->|hash| Bucket["buckets[index] (atomic head)"]
  Bucket --> Node1
  Node1 --> Node2
  Node2 --> Node3
  Node3 --> Nil[(nil)]

3. Core Operations

Bucket ordering is preserved by findOrInsert, which CASes either the bucket head or the predecessor’s next pointer to splice new nodes. Reads never take locks; only per-node sliding-window updates spin briefly to avoid data races.

4. Integration Points

• DB reads – Txn.Get and iterators call db.recordRead, which in turn invokes HotRing.Touch for every successful lookup. Writes touch the ring only when Options.WriteHotKeyLimit is set, so throttling can clamp abusive keys.
• Stats – StatsSnapshot copies hot.TopN into HotKeys. expvar publishes the same view under NoKV.Stats.HotKeys for automation.
• Caching – lsm/cache can promote blocks referenced by frequently touched keys, keeping the hot tier warm.

5. Comparisons

The HotRing emphasises simplicity: lock-free bucket lists with atomic counters (plus optional per-node window tracking), avoiding sketches while staying light enough for hundreds of thousands of hot keys.

6. Operational Tips

• Options.HotRingTopK controls how many keys show up in stats; default 16. Increase it when investigating workloads with broad hot sets.
• Combine TouchAndClamp with request middleware to detect abusive tenants: when limited is true, log the key and latency impact.
• Resetting the ring is as simple as instantiating a new HotRing—useful for benchmarks that require clean counters between phases.

For end-to-end examples see docs/stats.md and the CLI walkthrough in docs/cli.md.

7. Write-Path Throttling

Options.WriteHotKeyLimit wires HotRing into the write path. When set to a positive integer, every call to DB.Set* or transactional Txn.Set* invokes HotRing.TouchAndClamp with the limit. Once a key (optionally scoped by column family via cfHotKey) reaches the limit, the write is rejected with utils.ErrHotKeyWriteThrottle. This keeps pathological tenants or hot shards from overwhelming a single Raft group without adding heavyweight rate-limiters to the client stack.

Operational hints:

• StatsSnapshot.HotWriteLimited and the CLI line Write.HotKeyThrottled expose how many writes were rejected since the process started.
• Applications should surface utils.ErrHotKeyWriteThrottle to callers (e.g. HTTP 429) so clients can back off.
• Prefetching continues to run independently—only writes are rejected; reads still register hotness so the cache layer knows what to prefetch.
• Set the limit conservatively (e.g. a few dozen) and pair it with richer HotRing analytics (top-K stats, expvar export) to identify outliers before tuning.

8. Time-Based Decay & Sliding Window

HotRing now exposes two complementary controls so “old” hotspots fade away automatically:

1. Periodic decay (Options.HotRingDecayInterval + HotRingDecayShift)
   Every interval the global counters are right-shifted (count >>= shift). This keeps TopN and stats output focused on recent traffic even if writes stop abruptly.
2. Sliding window (Options.HotRingWindowSlots + HotRingWindowSlotDuration)
   Per-key windows split time into slots, each lasting slotDuration. Touch only accumulates inside the current slot; once the window slides past, the stale contribution is dropped. TouchAndClamp and Frequency use the sliding-window total, so write throttling reflects short-term pressure instead of lifetime counts.

Disable either mechanism by setting the interval/durations to zero. Typical starting points:

With both enabled, the decay loop keeps background stats tidy while the sliding window powers precise, short-term throttling logic.