internal/lru: Add sharded CLOCK

12 files changed, 953 insertions, 0 deletions

diff --git a/internal/clock/bench_test.go b/internal/clock/bench_test.go
new file mode 100644
index 00000000..49d85cde
--- /dev/null
+++ b/internal/clock/bench_test.go
@@ -0,0 +1,109 @@
+package clock //nolint:testpackage
+
+import (
+	"sync/atomic"
+	"testing"
+)
+
+func benchWeight(_, _ int) uint64 { return 1 }
+
+// goroutineSeq hands each parallel worker a distinct starting offset
+// so workers don't go in lockstep over identical keys.
+var goroutineSeq atomic.Uint64
+
+func workerOffset() int {
+	return int(goroutineSeq.Add(1) * 0x9E3779B1)
+}
+
+func BenchmarkReadHeavy(b *testing.B) {
+	// ≈95% Get hits, ≈5% Add, and fits budget.
+
+	const n = 100_000
+
+	cache := New(n, benchWeight)
+	for k := range n {
+		cache.Add(k, k)
+	}
+
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		i := workerOffset()
+		for pb.Next() {
+			i++
+			key := i % n
+			if i%20 == 0 {
+				cache.Add(key, key)
+			} else {
+				_, _ = cache.Get(key)
+			}
+		}
+	})
+}
+
+func BenchmarkHotKey(b *testing.B) {
+	// Every worker does Get over a relatively small hot set.
+
+	const (
+		hot       = 64
+		maxWeight = 4096
+	)
+
+	cache := New(maxWeight, benchWeight)
+	for k := range hot {
+		cache.Add(k, k)
+	}
+
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		i := workerOffset()
+		for pb.Next() {
+			i++
+			_, _ = cache.Get(i % hot)
+		}
+	})
+}
+
+func BenchmarkMixed(b *testing.B) {
+	// Even split of Get and Add over a working set that fits.
+
+	const n = 100_000
+
+	cache := New(n, benchWeight)
+	for k := range n {
+		cache.Add(k, k)
+	}
+
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		i := workerOffset()
+		for pb.Next() {
+			i++
+			key := i % n
+			if i%2 == 0 {
+				cache.Add(key, key)
+			} else {
+				_, _ = cache.Get(key)
+			}
+		}
+	})
+}
+
+func BenchmarkChurn(b *testing.B) {
+	// Every op inserts a fresh key into a small budget.
+	// I don't think this is likely to happen for git delta caches,
+	// but this may matter if we use this for other workloads later.
+
+	const maxWeight = 4096
+
+	cache := New(maxWeight, benchWeight)
+
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		base := workerOffset()
+		i := 0
+		for pb.Next() {
+			i++
+			cache.Add(base+i, i)
+		}
+	})
+}
diff --git a/internal/clock/cache.go b/internal/clock/cache.go
new file mode 100644
index 00000000..31d97082
--- /dev/null
+++ b/internal/clock/cache.go
@@ -0,0 +1,86 @@
+package clock
+
+import (
+	"hash/maphash"
+	"runtime"
+
+	"lindenii.org/go/lgo/intconv"
+)
+
+// maxShards bounds the shard count.
+//
+// Keep it relatively modest
+// so the per-shard budget
+// stays large enough to admit sizable values.
+const maxShards = 16
+
+// WeightFunc reports one entry's weight, used for eviction budgeting.
+type WeightFunc[K comparable, V any] func(key K, value V) uint64
+
+// Cache is a concurrent, weight-bounded cache
+// with CLOCK eviction.
+//
+// Reads are lock-free;
+// writes lock only the shard that owns the key.
+//
+// Labels: MT-Safe.
+type Cache[K comparable, V any] struct {
+	shards   []*shard[K, V]
+	seed     maphash.Seed
+	mask     uint64
+	weightFn WeightFunc[K, V]
+}
+
+// New returns a cache bounded to maxWeight total weight,
+// weighing entries with weightFn.
+//
+// New panics if weightFn is nil.
+func New[K comparable, V any](maxWeight uint64, weightFn WeightFunc[K, V]) *Cache[K, V] {
+	if weightFn == nil {
+		panic("internal/clock: nil weight function")
+	}
+
+	count, mask := shardLayout(maxWeight)
+	perShard := maxWeight / (mask + 1)
+
+	shards := make([]*shard[K, V], count)
+	for i := range shards {
+		shards[i] = newShard[K, V](perShard)
+	}
+
+	return &Cache[K, V]{
+		shards:   shards,
+		seed:     maphash.MakeSeed(),
+		mask:     mask,
+		weightFn: weightFn,
+	}
+}
+
+// shardLayout picks a power-of-two shard count and its address mask.
+//
+// Tracks GOMAXPROCS, capped at maxShards,
+// and is shrunk so the per-shard budget
+// stays at least one while maxWeight is nonzero.
+func shardLayout(maxWeight uint64) (int, uint64) {
+	count := 1
+	for count < runtime.GOMAXPROCS(0) && count < maxShards {
+		count *= 2
+	}
+
+	countU, err := intconv.IntToUint64(count)
+	if err != nil {
+		return 1, 0
+	}
+
+	for countU > maxWeight && countU > 1 {
+		count /= 2
+		countU /= 2
+	}
+
+	return count, countU - 1
+}
+
+// shardFor returns the shard that owns key.
+func (cache *Cache[K, V]) shardFor(key K) *shard[K, V] {
+	return cache.shards[maphash.Comparable(cache.seed, key)&cache.mask]
+}
diff --git a/internal/clock/cache_ops.go b/internal/clock/cache_ops.go
new file mode 100644
index 00000000..18958202
--- /dev/null
+++ b/internal/clock/cache_ops.go
@@ -0,0 +1,51 @@
+package clock
+
+// Add inserts or replaces key, marking it recently used.
+//
+// It reports whether the entry was admitted;
+// an entry heavier than the per-shard budget is rejected
+// and leaves the cache unchanged.
+func (cache *Cache[K, V]) Add(key K, value V) bool {
+	return cache.shardFor(key).add(key, value, cache.weightFn(key, value))
+}
+
+// Get returns the value for key and marks it recently used.
+//
+//nolint:ireturn
+func (cache *Cache[K, V]) Get(key K) (V, bool) {
+	return cache.shardFor(key).get(key)
+}
+
+// Peek returns the value for key without changing its recency.
+//
+//nolint:ireturn
+func (cache *Cache[K, V]) Peek(key K) (V, bool) {
+	return cache.shardFor(key).peek(key)
+}
+
+// Len returns the number of cached entries.
+func (cache *Cache[K, V]) Len() int {
+	total := 0
+	for _, shard := range cache.shards {
+		total += shard.len()
+	}
+
+	return total
+}
+
+// Weight returns the current total weight across all shards.
+func (cache *Cache[K, V]) Weight() uint64 {
+	var total uint64
+	for _, shard := range cache.shards {
+		total += shard.loadWeight()
+	}
+
+	return total
+}
+
+// Clear removes all entries.
+func (cache *Cache[K, V]) Clear() {
+	for _, shard := range cache.shards {
+		shard.clear()
+	}
+}
diff --git a/internal/clock/cache_test.go b/internal/clock/cache_test.go
new file mode 100644
index 00000000..116efdd3
--- /dev/null
+++ b/internal/clock/cache_test.go
@@ -0,0 +1,100 @@
+package clock_test
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+
+	"lindenii.org/go/furgit/internal/clock"
+	"lindenii.org/go/lgo/intconv"
+)
+
+func byteWeight(_ string, value string) uint64 {
+	weight, err := intconv.IntToUint64(len(value))
+	if err != nil {
+		return 0
+	}
+
+	return weight
+}
+
+func TestCacheAddGetPeek(t *testing.T) {
+	t.Parallel()
+
+	cache := clock.New(1<<20, byteWeight)
+
+	if !cache.Add("a", "alpha") {
+		t.Fatalf("Add(a) should succeed")
+	}
+
+	if got, ok := cache.Get("a"); !ok || got != "alpha" {
+		t.Fatalf("Get(a) = (%q, %v), want (alpha, true)", got, ok)
+	}
+
+	if got, ok := cache.Peek("a"); !ok || got != "alpha" {
+		t.Fatalf("Peek(a) = (%q, %v), want (alpha, true)", got, ok)
+	}
+
+	if _, ok := cache.Get("missing"); ok {
+		t.Fatalf("Get(missing) should miss")
+	}
+}
+
+func TestCacheWeightStaysBounded(t *testing.T) {
+	t.Parallel()
+
+	const maxWeight = 4096
+
+	cache := clock.New(maxWeight, byteWeight)
+	value := strings.Repeat("x", 64)
+
+	for i := range 1000 {
+		cache.Add(fmt.Sprintf("key-%d", i), value)
+	}
+
+	if got := cache.Weight(); got > maxWeight {
+		t.Fatalf("weight = %d, exceeds max %d", got, maxWeight)
+	}
+}
+
+func TestCacheLenAndClear(t *testing.T) {
+	t.Parallel()
+
+	cache := clock.New(1<<20, byteWeight)
+
+	for i := range 10 {
+		cache.Add(fmt.Sprintf("key-%d", i), "v")
+	}
+
+	if got := cache.Len(); got != 10 {
+		t.Fatalf("Len = %d, want 10", got)
+	}
+
+	cache.Clear()
+
+	if got := cache.Len(); got != 0 {
+		t.Fatalf("Len after Clear = %d, want 0", got)
+	}
+
+	if got := cache.Weight(); got != 0 {
+		t.Fatalf("Weight after Clear = %d, want 0", got)
+	}
+}
+
+func TestCacheRejectsOversized(t *testing.T) {
+	t.Parallel()
+
+	cache := clock.New(4, byteWeight)
+
+	if cache.Add("a", "xxxxx") {
+		t.Fatalf("oversized Add should report false")
+	}
+
+	if _, ok := cache.Get("a"); ok {
+		t.Fatalf("oversized entry must not be cached")
+	}
+
+	if got := cache.Weight(); got != 0 {
+		t.Fatalf("weight = %d, want 0", got)
+	}
+}
diff --git a/internal/clock/concurrent_test.go b/internal/clock/concurrent_test.go
new file mode 100644
index 00000000..86283a9b
--- /dev/null
+++ b/internal/clock/concurrent_test.go
@@ -0,0 +1,103 @@
+package clock //nolint:testpackage
+
+import (
+	"sync"
+	"testing"
+)
+
+func keyValue(key int) int {
+	return key*1000003 + 7
+}
+
+func TestConcurrentStress(t *testing.T) {
+	t.Parallel()
+
+	const (
+		maxWeight = 512
+		keys      = 400
+		workers   = 8
+		rounds    = 5000
+	)
+
+	cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 })
+
+	var wg sync.WaitGroup
+
+	for worker := range workers {
+		wg.Go(func() {
+			for i := range rounds {
+				key := (worker*7 + i) % keys
+
+				switch i % 4 {
+				case 0, 1:
+					cache.Add(key, keyValue(key))
+				case 2:
+					if got, ok := cache.Get(key); ok && got != keyValue(key) {
+						t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key))
+					}
+				case 3:
+					if got, ok := cache.Peek(key); ok && got != keyValue(key) {
+						t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key))
+					}
+				}
+			}
+		})
+	}
+
+	wg.Wait()
+
+	checkCache(t, cache)
+
+	if got := cache.Weight(); got > maxWeight {
+		t.Fatalf("weight %d exceeds max %d", got, maxWeight)
+	}
+}
+
+func TestReadDuringEviction(t *testing.T) {
+	t.Parallel()
+
+	const (
+		maxWeight = 8
+		hot       = 64
+		writers   = 2
+		readers   = 6
+		rounds    = 20000
+	)
+
+	cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 })
+
+	var wg sync.WaitGroup
+
+	for range writers {
+		wg.Go(func() {
+			for i := range rounds {
+				key := i % hot
+				cache.Add(key, keyValue(key))
+			}
+		})
+	}
+
+	for range readers {
+		wg.Go(func() {
+			for i := range rounds {
+				key := i % hot
+
+				if got, ok := cache.Get(key); ok && got != keyValue(key) {
+					t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key))
+				}
+
+				if got, ok := cache.Peek(key); ok && got != keyValue(key) {
+					t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key))
+				}
+			}
+		})
+	}
+
+	wg.Wait()
+
+	checkCache(t, cache)
+
+	if got := cache.Weight(); got > maxWeight {
+		t.Fatalf("weight %d exceeds max %d", got, maxWeight)
+	}
+}
diff --git a/internal/clock/doc.go b/internal/clock/doc.go
new file mode 100644
index 00000000..6f28805b
--- /dev/null
+++ b/internal/clock/doc.go
@@ -0,0 +1,9 @@
+// Package clock provides a concurrent, weight-bounded object cache.
+//
+// The cache is sharded by key,
+// and each shard owns an independent fraction of the total budget.
+// An entry heavier than that per-shard fraction is never admitted,
+// so callers should keep the total budget well above the largest value.
+//
+// Labels: MT-Safe.
+package clock
diff --git a/internal/clock/fuzz_test.go b/internal/clock/fuzz_test.go
new file mode 100644
index 00000000..af0d4024
--- /dev/null
+++ b/internal/clock/fuzz_test.go
@@ -0,0 +1,53 @@
+package clock //nolint:testpackage
+
+import "testing"
+
+// FuzzShard replays a decoded op stream against one shard,
+// checking the value oracle and invariants after every op.
+func FuzzShard(f *testing.F) {
+	f.Add([]byte{})
+	f.Add([]byte{0, 1, 10, 0, 2, 10, 0, 3, 10, 0, 4, 10, 1, 1, 0, 0, 5, 10})
+	f.Add([]byte{0, 7, 200, 0, 7, 5, 2, 7, 0, 3, 0, 0, 0, 8, 8})
+
+	f.Fuzz(func(t *testing.T, program []byte) {
+		const maxWeight = 32
+
+		shard := newShard[uint8, uint64](maxWeight)
+		shadow := make(map[uint8]uint64)
+
+		var nonce uint64
+
+		for i := 0; i+2 < len(program); i += 3 {
+			key := program[i+1]
+			weight := uint64(program[i+2])
+
+			switch program[i] % 4 {
+			case 0: // add
+				nonce++
+				value := nonce
+
+				admitted := shard.add(key, value, weight)
+				if admitted != (weight <= maxWeight) {
+					t.Fatalf("add(%d, w=%d) admitted=%v, want %v", key, weight, admitted, weight <= maxWeight)
+				}
+
+				if admitted {
+					shadow[key] = value
+				}
+			case 1: // get
+				if got, ok := shard.get(key); ok && got != shadow[key] {
+					t.Fatalf("get(%d) = %d, want %d", key, got, shadow[key])
+				}
+			case 2: // peek
+				if got, ok := shard.peek(key); ok && got != shadow[key] {
+					t.Fatalf("peek(%d) = %d, want %d", key, got, shadow[key])
+				}
+			case 3: // clear
+				shard.clear()
+				clear(shadow)
+			}
+
+			checkShard(t, shard)
+		}
+	})
+}
diff --git a/internal/clock/invariant_test.go b/internal/clock/invariant_test.go
new file mode 100644
index 00000000..2efd7ff9
--- /dev/null
+++ b/internal/clock/invariant_test.go
@@ -0,0 +1,88 @@
+package clock //nolint:testpackage
+
+import "testing"
+
+// checkShard verifies a shard's structural invariants at a quiescent point.
+//
+// It must be called with no concurrent operations in flight.
+func checkShard[K comparable, V any](t *testing.T, shard *shard[K, V]) {
+	t.Helper()
+
+	shard.mu.Lock()
+	defer shard.mu.Unlock()
+
+	ringLen := 0
+
+	var ringWeight uint64
+
+	seen := make(map[*entry[K, V]]struct{})
+
+	if shard.hand != nil { //nolint:nestif
+		for e := shard.hand; ; e = e.next {
+			if e.prev == nil || e.next == nil {
+				t.Fatalf("nil ring link at key %v", e.key)
+			}
+
+			if e.next.prev != e || e.prev.next != e {
+				t.Fatalf("ring links not reciprocal at key %v", e.key)
+			}
+
+			if _, dup := seen[e]; dup {
+				t.Fatalf("ring revisits a node before returning to the hand")
+			}
+
+			seen[e] = struct{}{}
+			ringLen++
+			ringWeight += e.weight
+
+			if got, ok := shard.items.Load(e.key); !ok || got != e {
+				t.Fatalf("ring node %v is not mapped to itself", e.key)
+			}
+
+			if e.next == shard.hand {
+				break
+			}
+		}
+	}
+
+	if ringLen != shard.count {
+		t.Fatalf("ring length %d != count %d", ringLen, shard.count)
+	}
+
+	if ringWeight != shard.weight {
+		t.Fatalf("ring weight %d != shard weight %d", ringWeight, shard.weight)
+	}
+
+	if shard.weight > shard.maxWeight {
+		t.Fatalf("weight %d exceeds budget %d", shard.weight, shard.maxWeight)
+	}
+
+	if (shard.hand == nil) != (shard.count == 0) {
+		t.Fatalf("hand/count disagree: hand=%v count=%d", shard.hand, shard.count)
+	}
+
+	mapLen := 0
+
+	shard.items.Range(func(_ K, e *entry[K, V]) bool {
+		mapLen++
+
+		if _, ok := seen[e]; !ok {
+			t.Fatalf("mapped entry %v missing from ring", e.key)
+		}
+
+		return true
+	})
+
+	if mapLen != shard.count {
+		t.Fatalf("map size %d != count %d", mapLen, shard.count)
+	}
+}
+
+// checkCache verifies every shard's invariants.
+func checkCache[K comparable, V any](t *testing.T, cache *Cache[K, V]) {
+	t.Helper()
+
+	for _, shard := range cache.shards {
+		checkShard(t, shard)
+	}
+}
diff --git a/internal/clock/shard.go b/internal/clock/shard.go
new file mode 100644
index 00000000..22e58b2f
--- /dev/null
+++ b/internal/clock/shard.go
@@ -0,0 +1,67 @@
+package clock
+
+import (
+	"sync"
+	"sync/atomic"
+
+	lsync "lindenii.org/go/lgo/sync"
+)
+
+// entry is one cached key/value with CLOCK.
+type entry[K comparable, V any] struct {
+	key        K
+	value      V
+	weight     uint64
+	prev, next *entry[K, V]
+
+	// referenced is set on access and cleared by the eviction sweep;
+	// prev and next link the entry into its shard's ring.
+	referenced atomic.Bool
+}
+
+// shard is an independently locked CLOCK cache.
+type shard[K comparable, V any] struct {
+	items lsync.Map[K, *entry[K, V]]
+
+	hand      *entry[K, V]
+	weight    uint64
+	count     int
+	maxWeight uint64
+
+	// mu protects the ring, hand, totals, and writes.
+	mu sync.Mutex
+}
+
+// newShard returns an empty shard with the given weight budget.
+func newShard[K comparable, V any](maxWeight uint64) *shard[K, V] {
+	return &shard[K, V]{ //nolint:exhaustruct
+		maxWeight: maxWeight,
+	}
+}
+
+// len returns the shard's entry count.
+func (shard *shard[K, V]) len() int {
+	shard.mu.Lock()
+	defer shard.mu.Unlock()
+
+	return shard.count
+}
+
+// loadWeight returns the shard's current total weight.
+func (shard *shard[K, V]) loadWeight() uint64 {
+	shard.mu.Lock()
+	defer shard.mu.Unlock()
+
+	return shard.weight
+}
+
+// clear removes every entry.
+func (shard *shard[K, V]) clear() {
+	shard.mu.Lock()
+	defer shard.mu.Unlock()
+
+	shard.items.Clear()
+	shard.hand = nil
+	shard.weight = 0
+	shard.count = 0
+}
diff --git a/internal/clock/shard_read.go b/internal/clock/shard_read.go
new file mode 100644
index 00000000..624e3409
--- /dev/null
+++ b/internal/clock/shard_read.go
@@ -0,0 +1,33 @@
+package clock
+
+// get returns the value for key and marks it referenced.
+//
+//nolint:ireturn
+func (shard *shard[K, V]) get(key K) (V, bool) {
+	e, ok := shard.items.Load(key)
+	if !ok {
+		var zero V
+
+		return zero, false
+	}
+
+	if !e.referenced.Load() {
+		e.referenced.Store(true)
+	}
+
+	return e.value, true
+}
+
+// peek returns the value for key without affecting eviction.
+//
+//nolint:ireturn
+func (shard *shard[K, V]) peek(key K) (V, bool) {
+	e, ok := shard.items.Load(key)
+	if !ok {
+		var zero V
+
+		return zero, false
+	}
+
+	return e.value, true
+}
diff --git a/internal/clock/shard_test.go b/internal/clock/shard_test.go
new file mode 100644
index 00000000..d974a30e
--- /dev/null
+++ b/internal/clock/shard_test.go
@@ -0,0 +1,149 @@
+package clock //nolint:testpackage
+
+import "testing"
+
+func TestShardEvictsOldest(t *testing.T) {
+	t.Parallel()
+
+	shard := newShard[string, string](8)
+	shard.add("a", "a", 4)
+	shard.add("b", "b", 4)
+	shard.add("c", "c", 4) // overflows, evicts
+
+	if _, ok := shard.peek("a"); ok {
+		t.Fatalf("a should have been evicted")
+	}
+
+	for _, key := range []string{"b", "c"} {
+		if _, ok := shard.peek(key); !ok {
+			t.Fatalf("%s should remain present", key)
+		}
+	}
+
+	if got := shard.loadWeight(); got != 8 {
+		t.Fatalf("weight = %d, want 8", got)
+	}
+
+	if got := shard.len(); got != 2 {
+		t.Fatalf("len = %d, want 2", got)
+	}
+}
+
+func TestShardGetGivesSecondChance(t *testing.T) {
+	t.Parallel()
+
+	shard := newShard[string, string](8)
+	shard.add("a", "a", 4)
+	shard.add("b", "b", 4)
+	shard.add("c", "c", 4) // a evicted; b and c survive
+
+	if _, ok := shard.get("b"); !ok {
+		t.Fatalf("get(b) should hit")
+	}
+
+	shard.add("d", "d", 4) // b was just touched, so c is evicted instead
+
+	if _, ok := shard.peek("c"); ok {
+		t.Fatalf("c should have been evicted after b was touched")
+	}
+
+	for _, key := range []string{"b", "d"} {
+		if _, ok := shard.peek(key); !ok {
+			t.Fatalf("%s should remain present", key)
+		}
+	}
+}
+
+func TestShardPeekGivesNoSecondChance(t *testing.T) {
+	t.Parallel()
+
+	shard := newShard[string, string](8)
+	shard.add("a", "a", 4)
+	shard.add("b", "b", 4)
+	shard.add("c", "c", 4) // a is evicted; b and c survive with cleared bits
+
+	if _, ok := shard.peek("b"); !ok {
+		t.Fatalf("peek(b) should hit")
+	}
+
+	shard.add("d", "d", 4) // peek did not refresh b, so b is evicted
+
+	if _, ok := shard.peek("b"); ok {
+		t.Fatalf("b should have been evicted; peek must not grant a second chance")
+	}
+
+	for _, key := range []string{"c", "d"} {
+		if _, ok := shard.peek(key); !ok {
+			t.Fatalf("%s should remain present", key)
+		}
+	}
+}
+
+func TestShardReplaceUpdatesWeight(t *testing.T) {
+	t.Parallel()
+
+	shard := newShard[string, string](100)
+	shard.add("a", "old", 4)
+	shard.add("a", "new", 6)
+
+	if got, ok := shard.peek("a"); !ok || got != "new" {
+		t.Fatalf("peek(a) = (%q, %v), want (new, true)", got, ok)
+	}
+
+	if got := shard.loadWeight(); got != 6 {
+		t.Fatalf("weight = %d, want 6", got)
+	}
+
+	if got := shard.len(); got != 1 {
+		t.Fatalf("len = %d, want 1", got)
+	}
+}
+
+func TestShardRejectsOversized(t *testing.T) {
+	t.Parallel()
+
+	shard := newShard[string, string](5)
+	shard.add("a", "x", 3)
+
+	if shard.add("b", "big", 6) {
+		t.Fatalf("oversized add should report false")
+	}
+
+	if shard.add("a", "huge", 6) {
+		t.Fatalf("oversized replace should report false")
+	}
+
+	if got, ok := shard.peek("a"); !ok || got != "x" {
+		t.Fatalf("peek(a) = (%q, %v), want (x, true); cache must be unchanged", got, ok)
+	}
+
+	if _, ok := shard.peek("b"); ok {
+		t.Fatalf("b must not have been admitted")
+	}
+
+	if got := shard.loadWeight(); got != 3 {
+		t.Fatalf("weight = %d, want 3", got)
+	}
+}
+
+func TestShardClear(t *testing.T) {
+	t.Parallel()
+
+	shard := newShard[string, string](100)
+	shard.add("a", "a", 4)
+	shard.add("b", "b", 4)
+
+	shard.clear()
+
+	if got := shard.loadWeight(); got != 0 {
+		t.Fatalf("weight = %d, want 0", got)
+	}
+
+	if got := shard.len(); got != 0 {
+		t.Fatalf("len = %d, want 0", got)
+	}
+
+	if _, ok := shard.peek("a"); ok {
+		t.Fatalf("a should be gone after clear")
+	}
+}
diff --git a/internal/clock/shard_write.go b/internal/clock/shard_write.go
new file mode 100644
index 00000000..40ddabd0
--- /dev/null
+++ b/internal/clock/shard_write.go
@@ -0,0 +1,105 @@
+package clock
+
+// add inserts or replaces key, then evicts down to budget.
+//
+// It reports whether the entry was admitted;
+// an entry heavier than the shard budget is rejected
+// and leaves the shard unchanged.
+func (shard *shard[K, V]) add(key K, value V, weight uint64) bool {
+	if weight > shard.maxWeight {
+		return false
+	}
+
+	shard.mu.Lock()
+	defer shard.mu.Unlock()
+
+	if old, ok := shard.items.Load(key); ok {
+		shard.unlink(old)
+		shard.items.Delete(key)
+		shard.weight -= old.weight
+		shard.count--
+	}
+
+	e := &entry[K, V]{ //nolint:exhaustruct
+		key:    key,
+		value:  value,
+		weight: weight,
+	}
+	e.referenced.Store(true)
+
+	shard.linkBeforeHand(e)
+	shard.items.Store(key, e)
+	shard.weight += weight
+	shard.count++
+
+	shard.evict()
+
+	return true
+}
+
+// evict advances the clock hand until the shard is within budget.
+//
+// A referenced entry is spared once, its bit cleared;
+// after a full rotation of spared entries the next is evicted regardless,
+// so a flood of concurrent reads cannot stall progress.
+func (shard *shard[K, V]) evict() {
+	skips := 0
+
+	for shard.weight > shard.maxWeight && shard.hand != nil {
+		victim := shard.hand
+
+		if victim.referenced.Load() && skips < shard.count {
+			victim.referenced.Store(false)
+			shard.hand = victim.next
+			skips++
+
+			continue
+		}
+
+		shard.unlink(victim)
+		shard.items.Delete(victim.key)
+		shard.weight -= victim.weight
+		shard.count--
+		skips = 0
+	}
+}
+
+// linkBeforeHand inserts e just behind the hand,
+// so a full rotation passes before the sweep examines it.
+func (shard *shard[K, V]) linkBeforeHand(e *entry[K, V]) {
+	if shard.hand == nil {
+		e.prev = e
+		e.next = e
+		shard.hand = e
+
+		return
+	}
+
+	tail := shard.hand.prev
+	tail.next = e
+	e.prev = tail
+	e.next = shard.hand
+	shard.hand.prev = e
+}
+
+// unlink removes e from the ring,
+// moving the hand off e when it points at it.
+func (shard *shard[K, V]) unlink(e *entry[K, V]) {
+	if e.next == e {
+		shard.hand = nil
+		e.prev = nil
+		e.next = nil
+
+		return
+	}
+
+	e.prev.next = e.next
+	e.next.prev = e.prev
+
+	if shard.hand == e {
+		shard.hand = e.next
+	}
+
+	e.prev = nil
+	e.next = nil
+}