internal-mru: Add interval

3 files changed, 90 insertions, 9 deletions

diff --git a/internal/mru/order.go b/internal/mru/order.go
index 76b58497..1ea1ac09 100644
--- a/internal/mru/order.go
+++ b/internal/mru/order.go
@@ -22,11 +22,33 @@ import (
 type Order[K comparable] struct {
 	snapshot atomic.Pointer[[]K]
 	mu       sync.Mutex
+
+	interval uint64
+	pending  atomic.Uint64
+}
+
+// Options configures a new Order.
+type Options struct {
+	// Interval applies a reorder at most once per Interval
+	// eligible (non-front, member) Touch calls.
+	//
+	// A larger Interval decreases recency precision
+	// but uses fewer allocations.
+	// Each applied reorder allocates one snapshot,
+	// so throttling decreases the snapshot-allocation rate
+	// by roughly Interval.
+	//
+	// An Interval of 1 reorders on every eligible Touch.
+	Interval uint64
 }
 
-// New returns a new, empty order.
-func New[K comparable]() *Order[K] {
-	return &Order[K]{} //nolint:exhaustruct
+// New returns a new, empty order configured by opts.
+func New[K comparable](opts Options) *Order[K] {
+	if opts.Interval == 0 {
+		panic("internal/mru: Options.Interval must be at least 1")
+	}
+
+	return &Order[K]{interval: opts.Interval} //nolint:exhaustruct
 }
 
 // Len returns the number of keys in the order.
diff --git a/internal/mru/order_test.go b/internal/mru/order_test.go
index bf0d4f2e..2f16eac3 100644
--- a/internal/mru/order_test.go
+++ b/internal/mru/order_test.go
@@ -20,7 +20,7 @@ func set(keys ...string) map[string]struct{} {
 func TestTouchMovesToFront(t *testing.T) {
 	t.Parallel()
 
-	order := mru.New[string]()
+	order := mru.New[string](mru.Options{Interval: 1})
 	order.Sync(set("a", "b", "c"))
 
 	order.Touch("a")
@@ -36,10 +36,60 @@ func TestTouchMovesToFront(t *testing.T) {
 	}
 }
 
+func TestIntervalThrottlesReorder(t *testing.T) {
+	t.Parallel()
+
+	const interval = 4
+
+	order := mru.New[string](mru.Options{Interval: interval})
+	order.Sync(set("a", "b", "c"))
+
+	front := order.Keys()[0]
+
+	other := "a"
+	if other == front {
+		other = "b"
+	}
+
+	for range interval - 1 {
+		order.Touch(other)
+
+		if got := order.Keys()[0]; got != front {
+			t.Fatalf("reordered early: front = %q, want %q", got, front)
+		}
+	}
+
+	order.Touch(other)
+
+	if got := order.Keys()[0]; got != other {
+		t.Fatalf("after interval touches, front = %q, want %q", got, other)
+	}
+}
+
+func TestIntervalKeepsMembershipUnderReorder(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string](mru.Options{Interval: 8})
+	order.Sync(set("a", "b", "c", "d"))
+
+	for range 100 {
+		for _, key := range []string{"a", "b", "c", "d"} {
+			order.Touch(key)
+		}
+	}
+
+	got := slices.Clone(order.Keys())
+	slices.Sort(got)
+
+	if want := []string{"a", "b", "c", "d"}; !slices.Equal(got, want) {
+		t.Fatalf("membership corrupted: %v", got)
+	}
+}
+
 func TestSyncDropsAbsentAndKeepsSurvivorOrder(t *testing.T) {
 	t.Parallel()
 
-	order := mru.New[string]()
+	order := mru.New[string](mru.Options{Interval: 1})
 	order.Sync(set("a", "b", "c"))
 
 	// Establish a deterministic recency order: c, b, a.
@@ -61,7 +111,7 @@ func TestSyncDropsAbsentAndKeepsSurvivorOrder(t *testing.T) {
 func TestSyncPlacesNewKeysFirst(t *testing.T) {
 	t.Parallel()
 
-	order := mru.New[string]()
+	order := mru.New[string](mru.Options{Interval: 1})
 	order.Sync(set("a", "b"))
 
 	order.Touch("a")
@@ -77,7 +127,7 @@ func TestSyncPlacesNewKeysFirst(t *testing.T) {
 func TestTouchAbsentIsNoOp(t *testing.T) {
 	t.Parallel()
 
-	order := mru.New[string]()
+	order := mru.New[string](mru.Options{Interval: 1})
 	order.Sync(set("a", "b"))
 	order.Touch("a")
 	order.Touch("z")
@@ -90,7 +140,7 @@ func TestTouchAbsentIsNoOp(t *testing.T) {
 func TestKeysIsConsistentSnapshot(t *testing.T) {
 	t.Parallel()
 
-	order := mru.New[string]()
+	order := mru.New[string](mru.Options{Interval: 1})
 	order.Sync(set("a", "b"))
 
 	snapshot := order.Keys()
@@ -111,7 +161,7 @@ func TestKeysIsConsistentSnapshot(t *testing.T) {
 func TestConcurrentTouchAndKeys(t *testing.T) {
 	t.Parallel()
 
-	order := mru.New[string]()
+	order := mru.New[string](mru.Options{Interval: 1})
 	order.Sync(set("a", "b", "c", "d"))
 
 	var wg sync.WaitGroup
diff --git a/internal/mru/touch.go b/internal/mru/touch.go
index 67ac6706..420bbc4a 100644
--- a/internal/mru/touch.go
+++ b/internal/mru/touch.go
@@ -10,12 +10,21 @@ package mru
 // A contended attempt,
 // or a key that is not a member,
 // leaves the order unchanged.
+//
+// When the order has a reorder interval above 1,
+// an eligible (non-front) Touch records its recency
+// but applies the reorder only once per interval such calls;
+// the recording itself is lock-free and allocation-free.
 func (order *Order[K]) Touch(key K) {
 	keys := order.Keys()
 	if len(keys) == 0 || keys[0] == key {
 		return
 	}
 
+	if order.interval > 1 && order.pending.Add(1)%order.interval != 0 {
+		return
+	}
+
 	if !order.mu.TryLock() {
 		return
 	}