hotring

package module
v0.5.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 6, 2026 License: Apache-2.0 Imports: 7 Imported by: 0

README

HotRing

CI Go Reference

A lightweight, concurrent hot-key tracker extracted from NoKV.

HotRing is designed to be a system-level hotness signal rather than a cache policy: it tracks read/write frequencies at high throughput, surfaces Top-N hotspots, and supports short-term bursts via sliding windows and long-term decay via periodic aging.

Highlights

  • Lock-free bucket lists with atomic counters
  • Sliding window for burst detection
  • Periodic decay for long-term cooling
  • Top-N snapshots for diagnostics and scheduling
  • Touch-and-clamp for throttling hot keys
  • Node cap + stable sampling for high-cardinality control
  • Optional ring rotation for bounded memory + recent hotness

Install

go get github.com/feichai0017/hotring

Quick Start

package main

import (
    "fmt"
    "time"

    "github.com/feichai0017/hotring"
)

func main() {
    ring := hotring.NewHotRing(12, nil) // 4096 buckets
    ring.EnableSlidingWindow(8, 250*time.Millisecond)
    ring.EnableDecay(time.Second, 1)
    ring.EnableNodeSampling(1_000_000, 4) // optional cap + sampling

    ring.Touch("user:1")
    ring.Touch("user:1")
    ring.Touch("user:2")

    fmt.Println("user:1", ring.Frequency("user:1"))
    fmt.Println("top", ring.TopN(2))
}

Rotation (Optional, Dual Ring)

For long-running systems that only need recent hotness, use dual-ring rotation to bound memory and naturally forget old keys while avoiding sudden drops.

Rotation keeps two rings:

  • active: current writes
  • warm: previous generation (read-only)

Default merge semantics:

  • Frequency / TouchAndClamp: max(active, warm)
  • Touch: returns max(active, warm) after incrementing active
  • TopN / KeysAbove: sum(active, warm)
ring := hotring.NewRotatingHotRing(12, nil)
ring.EnableNodeSampling(1_000_000, 0)  // strict cap per ring
ring.EnableRotation(10 * time.Minute) // rotate periodically

ring.Touch("user:1")
fmt.Println(ring.TopN(10))

Memory note: dual ring means ~2 × cap upper bound. If total budget is fixed, halve the per-ring cap.

API Overview

Method Purpose
Touch(key) Insert or increment key counter
Frequency(key) Read-only counter lookup
TouchAndClamp(key, limit) Increment unless limit reached; for throttling
TopN(k) Snapshot of hottest keys
KeysAbove(threshold) Keys with counters >= threshold
Stats() Lightweight counters + config snapshot
SnapshotTopN(k) Timestamped Top-N snapshot
EnableSlidingWindow(slots, dur) Short-term hotness
EnableDecay(interval, shift) Long-term cooling
EnableNodeSampling(cap, sampleBits) Cap node growth with stable sampling
SetObserver(obs) Optional hooks for observability

Rotating ring helpers:

Method Purpose
NewRotatingHotRing(bits, fn) Ring wrapper with rotation support
EnableRotation(interval) Periodic rotation (<=0 disables)
Rotate() Manual rotation
RotationStats() Rotation counters + config
ActiveStats() Stats for active ring
WarmStats() Stats for warm ring
TopNMax(k) Top-N with max merge
KeysAboveMax(threshold) KeysAbove with max merge

Design Notes

  • Data structure: buckets of sorted lock-free linked lists, with a per-node spin lock for sliding-window updates.
  • Hashing: xxhash by default; custom hash function supported.
  • Hotness semantics: sliding window reflects recent access; decay prevents old hotspots from dominating.

Benchmarks

go test -bench . ./...

License

Apache 2.0. See LICENSE.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type HashFn 

type HashFn func(string) uint32

type HotRing 

type HotRing struct {
	// contains filtered or unexported fields
}

HotRing keeps track of frequently accessed keys using lock-free bucketed lists.

func NewHotRing 

func NewHotRing(bits uint8, fn HashFn) *HotRing

NewHotRing builds a ring with 2^bits buckets. When fn is nil a fast xxhash-based hash is used.

func (*HotRing) Close 

func (h *HotRing) Close()

Close releases background resources attached to the ring.

func (*HotRing) EnableDecay 

func (h *HotRing) EnableDecay(interval time.Duration, shift uint32)

EnableDecay applies periodic right-shift decay to the raw counters. interval <= 0 or shift == 0 disables background decay.

func (*HotRing) EnableNodeSampling added in v0.4.0 

func (h *HotRing) EnableNodeSampling(cap uint64, sampleBits uint8)

EnableNodeSampling caps node growth and applies stable sampling once the cap is reached. cap <= 0 disables the cap. sampleBits controls the sampling rate (1/2^sampleBits). sampleBits == 0 means no sampling when the cap is exceeded (strict cap).

func (*HotRing) EnableSlidingWindow 

func (h *HotRing) EnableSlidingWindow(slots int, slotDuration time.Duration)

EnableSlidingWindow configures the ring to maintain a time-based sliding window. slots specifies how many buckets to retain, while slotDuration controls how long each bucket remains active. Passing non-positive values disables the window.

func (*HotRing) Frequency 

func (h *HotRing) Frequency(key string) int32

Frequency returns the current access counter for key without mutating state.

func (*HotRing) KeysAbove 

func (h *HotRing) KeysAbove(threshold int32) []Item

KeysAbove returns all keys whose counters are at least threshold.

func (*HotRing) Remove 

func (h *HotRing) Remove(key string)

func (*HotRing) SetObserver added in v0.2.0 

func (h *HotRing) SetObserver(obs Observer)

SetObserver registers an optional observer hook.

func (*HotRing) SnapshotKeysAbove added in v0.2.0 

func (h *HotRing) SnapshotKeysAbove(threshold int32) Snapshot

SnapshotKeysAbove captures a threshold snapshot with a timestamp.

func (*HotRing) SnapshotTopN added in v0.2.0 

func (h *HotRing) SnapshotTopN(n int) Snapshot

SnapshotTopN captures a Top-N snapshot with a timestamp.

func (*HotRing) Stats added in v0.2.0 

func (h *HotRing) Stats() Stats

Stats returns a lightweight view of ring configuration and counters.

func (*HotRing) TopN 

func (h *HotRing) TopN(n int) []Item

TopN returns at most n hot keys ordered by access count (descending).

func (*HotRing) Touch 

func (h *HotRing) Touch(key string) int32

Touch records a key access and returns the updated counter.

func (*HotRing) TouchAndClamp 

func (h *HotRing) TouchAndClamp(key string, limit int32) (count int32, limited bool)

TouchAndClamp increments the counter if below the provided limit and reports whether the key should be considered throttled.

type Item 

type Item struct {
	Key   string
	Count int32
}

Item captures a hot key and its access counter.

type Node 

type Node struct {
	// contains filtered or unexported fields
}

func NewNode 

func NewNode(key string, tag uint32) *Node

func (*Node) CompareAndSwapNext 

func (n *Node) CompareAndSwapNext(old, next *Node) bool

func (*Node) Equal 

func (n *Node) Equal(c *Node) bool

func (*Node) GetCounter 

func (n *Node) GetCounter() int32

func (*Node) Increment 

func (n *Node) Increment() int32

func (*Node) Less 

func (n *Node) Less(c *Node) bool

Less compares by tag first, then by key when tags are equal.

func (*Node) Next 

func (n *Node) Next() *Node

func (*Node) ResetCounter 

func (n *Node) ResetCounter()

func (*Node) ResetCounterWithWindow 

func (n *Node) ResetCounterWithWindow(slots int, slotID int64)

func (*Node) SetNext 

func (n *Node) SetNext(next *Node)

type Observer added in v0.2.0 

type Observer interface {
	OnTouch(key string, count int32)
	OnClamp(key string, limit int32, count int32)
	OnDecay(shift uint32)
}

Observer receives optional notifications for observability hooks.

type RotatingHotRing added in v0.5.0 

type RotatingHotRing struct {
	// contains filtered or unexported fields
}

RotatingHotRing wraps HotRing with dual-ring time-based rotation. Rotation swaps in a fresh active ring and keeps the previous generation warm.

func NewRotatingHotRing added in v0.5.0 

func NewRotatingHotRing(bits uint8, fn HashFn) *RotatingHotRing

NewRotatingHotRing builds a rotating ring with 2^bits buckets.

func (*RotatingHotRing) ActiveStats added in v0.5.0 

func (r *RotatingHotRing) ActiveStats() Stats

ActiveStats returns stats for the active ring.

func (*RotatingHotRing) Close added in v0.5.0 

func (r *RotatingHotRing) Close()

Close releases background resources attached to the rotating ring.

func (*RotatingHotRing) EnableDecay added in v0.5.0 

func (r *RotatingHotRing) EnableDecay(interval time.Duration, shift uint32)

EnableDecay applies periodic right-shift decay to the raw counters.

func (*RotatingHotRing) EnableNodeSampling added in v0.5.0 

func (r *RotatingHotRing) EnableNodeSampling(cap uint64, sampleBits uint8)

EnableNodeSampling caps node growth and applies stable sampling once the cap is reached.

func (*RotatingHotRing) EnableRotation added in v0.5.0 

func (r *RotatingHotRing) EnableRotation(interval time.Duration)

EnableRotation starts or stops time-based rotation. interval <= 0 disables rotation.

func (*RotatingHotRing) EnableSlidingWindow added in v0.5.0 

func (r *RotatingHotRing) EnableSlidingWindow(slots int, slotDuration time.Duration)

EnableSlidingWindow configures the ring to maintain a time-based sliding window.

func (*RotatingHotRing) Frequency added in v0.5.0 

func (r *RotatingHotRing) Frequency(key string) int32

Frequency returns the current access counter for key without mutating state.

func (*RotatingHotRing) KeysAbove added in v0.5.0 

func (r *RotatingHotRing) KeysAbove(threshold int32) []Item

KeysAbove returns all keys whose counters are at least threshold.

func (*RotatingHotRing) KeysAboveMax added in v0.5.0 

func (r *RotatingHotRing) KeysAboveMax(threshold int32) []Item

KeysAboveMax returns all keys whose counters are at least threshold using max merge.

func (*RotatingHotRing) Remove added in v0.5.0 

func (r *RotatingHotRing) Remove(key string)

Remove deletes a key from the active ring.

func (*RotatingHotRing) Rotate added in v0.5.0 

func (r *RotatingHotRing) Rotate()

Rotate swaps in a fresh ring and releases background resources of the old ring.

func (*RotatingHotRing) RotationStats added in v0.5.0 

func (r *RotatingHotRing) RotationStats() RotationStats

RotationStats returns rotation counters and configuration.

func (*RotatingHotRing) SetObserver added in v0.5.0 

func (r *RotatingHotRing) SetObserver(obs Observer)

SetObserver registers an optional observer hook.

func (*RotatingHotRing) SnapshotKeysAbove added in v0.5.0 

func (r *RotatingHotRing) SnapshotKeysAbove(threshold int32) Snapshot

SnapshotKeysAbove captures a threshold snapshot with a timestamp.

func (*RotatingHotRing) SnapshotKeysAboveMax added in v0.5.0 

func (r *RotatingHotRing) SnapshotKeysAboveMax(threshold int32) Snapshot

SnapshotKeysAboveMax captures a threshold snapshot using max merge semantics.

func (*RotatingHotRing) SnapshotTopN added in v0.5.0 

func (r *RotatingHotRing) SnapshotTopN(n int) Snapshot

SnapshotTopN captures a Top-N snapshot with a timestamp.

func (*RotatingHotRing) SnapshotTopNMax added in v0.5.0 

func (r *RotatingHotRing) SnapshotTopNMax(n int) Snapshot

SnapshotTopNMax captures a Top-N snapshot using max merge semantics.

func (*RotatingHotRing) Stats added in v0.5.0 

func (r *RotatingHotRing) Stats() Stats

Stats returns a lightweight view of ring configuration and counters.

func (*RotatingHotRing) TopN added in v0.5.0 

func (r *RotatingHotRing) TopN(n int) []Item

TopN returns at most n hot keys ordered by access count (descending).

func (*RotatingHotRing) TopNMax added in v0.5.0 

func (r *RotatingHotRing) TopNMax(n int) []Item

TopNMax returns at most n hot keys ordered by access count (descending) using max merge.

func (*RotatingHotRing) Touch added in v0.5.0 

func (r *RotatingHotRing) Touch(key string) int32

Touch records a key access and returns the updated counter.

func (*RotatingHotRing) TouchAndClamp added in v0.5.0 

func (r *RotatingHotRing) TouchAndClamp(key string, limit int32) (int32, bool)

TouchAndClamp increments the counter if below the provided limit.

func (*RotatingHotRing) WarmStats added in v0.5.0 

func (r *RotatingHotRing) WarmStats() Stats

WarmStats returns stats for the warm ring.

type RotationStats added in v0.5.0 

type RotationStats struct {
	Interval       time.Duration `json:"interval"`
	Rotations      uint64        `json:"rotations"`
	LastRotateUnix int64         `json:"last_rotate_unix"`
}

RotationStats reports rotation activity for a RotatingHotRing.

type Snapshot added in v0.2.0 

type Snapshot struct {
	TakenAt time.Time `json:"taken_at"`
	Items   []Item    `json:"items"`
}

Snapshot captures a point-in-time view of hot keys.

type Stats added in v0.2.0 

type Stats struct {
	Buckets            int           `json:"buckets"`
	Nodes              uint64        `json:"nodes"`
	LoadFactor         float64       `json:"load_factor"`
	WindowSlots        int           `json:"window_slots"`
	WindowSlotDuration time.Duration `json:"window_slot_duration"`
	DecayInterval      time.Duration `json:"decay_interval"`
	DecayShift         uint32        `json:"decay_shift"`
	NodeCap            uint64        `json:"node_cap"`
	SampleMask         uint32        `json:"sample_mask"`
	Touches            uint64        `json:"touches"`
	Inserts            uint64        `json:"inserts"`
	Removes            uint64        `json:"removes"`
	Clamps             uint64        `json:"clamps"`
	SampleDrops        uint64        `json:"sample_drops"`
	DecayRuns          uint64        `json:"decay_runs"`
	LastDecayUnix      int64         `json:"last_decay_unix"`
}

Stats exposes lightweight observability data for a HotRing instance.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.