7 files changed, 141 insertions, 40 deletions

diff --git a/internal/mru/keys.go b/internal/mru/keys.go
deleted file mode 100644
index 0cd9a319..00000000
--- a/internal/mru/keys.go
+++ /dev/null
@@ -1,17 +0,0 @@
-package mru
-
-// Keys returns the keys in most-recently-used order,
-// front first.
-//
-// The result is the immutable snapshot current at the call:
-// a concurrent Touch or Sync does not affect it.
-//
-// Labels: Mut-No.
-func (order *Order[K]) Keys() []K {
-	keys := order.snapshot.Load()
-	if keys == nil {
-		return nil
-	}
-
-	return *keys
-}
diff --git a/internal/mru/len.go b/internal/mru/len.go
deleted file mode 100644
index 38863c66..00000000
--- a/internal/mru/len.go
+++ /dev/null
@@ -1,6 +0,0 @@
-package mru
-
-// Len returns the number of keys in the order.
-func (order *Order[K]) Len() int {
-	return len(order.Keys())
-}
diff --git a/internal/mru/new.go b/internal/mru/new.go
deleted file mode 100644
index 221b650b..00000000
--- a/internal/mru/new.go
+++ /dev/null
@@ -1,6 +0,0 @@
-package mru
-
-// New returns a new, empty order.
-func New[K comparable]() *Order[K] {
-	return &Order[K]{} //nolint:exhaustruct
-}
diff --git a/internal/mru/order.go b/internal/mru/order.go
index 9721d852..1ea1ac09 100644
--- a/internal/mru/order.go
+++ b/internal/mru/order.go
@@ -22,4 +22,52 @@ 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 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.
+func (order *Order[K]) Len() int {
+	return len(order.Keys())
+}
+
+// Keys returns the keys in most-recently-used order,
+// front first.
+//
+// The result is the immutable snapshot current at the call:
+// a concurrent Touch or Sync does not affect it.
+//
+// Labels: Mut-No.
+func (order *Order[K]) Keys() []K {
+	keys := order.snapshot.Load()
+	if keys == nil {
+		return nil
+	}
+
+	return *keys
 }
diff --git a/internal/mru/order_test.go b/internal/mru/order_test.go
index 8b667e77..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.
@@ -58,10 +108,26 @@ func TestSyncDropsAbsentAndKeepsSurvivorOrder(t *testing.T) {
 	}
 }
 
+func TestSyncPlacesNewKeysFirst(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string](mru.Options{Interval: 1})
+	order.Sync(set("a", "b"))
+
+	order.Touch("a")
+	order.Touch("b")
+
+	order.Sync(set("a", "b", "z"))
+
+	if got, want := order.Keys(), []string{"z", "b", "a"}; !slices.Equal(got, want) {
+		t.Fatalf("after Sync, order = %v, want %v", got, want)
+	}
+}
+
 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")
@@ -74,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()
@@ -95,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/sync.go b/internal/mru/sync.go
index 69fc3446..f10da5f4 100644
--- a/internal/mru/sync.go
+++ b/internal/mru/sync.go
@@ -4,25 +4,32 @@ package mru
 //
 // Surviving keys keep their relative recency order,
 // absent keys are dropped,
-// and newly present keys are appended after the survivors.
+// and newly present keys are placed before the survivors,
+// since new members are presumed recently used.
 func (order *Order[K]) Sync(present map[K]struct{}) {
 	order.mu.Lock()
 	defer order.mu.Unlock()
 
 	keys := order.Keys()
 
-	next := make([]K, 0, len(present))
-	seen := make(map[K]struct{}, len(present))
+	survivors := make(map[K]struct{}, len(present))
 
 	for _, key := range keys {
 		if _, ok := present[key]; ok {
-			next = append(next, key)
-			seen[key] = struct{}{}
+			survivors[key] = struct{}{}
 		}
 	}
 
+	next := make([]K, 0, len(present))
+
 	for key := range present {
-		if _, ok := seen[key]; !ok {
+		if _, ok := survivors[key]; !ok {
+			next = append(next, key)
+		}
+	}
+
+	for _, key := range keys {
+		if _, ok := survivors[key]; ok {
 			next = append(next, key)
 		}
 	}
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
 	}