← SIEVE Cache cachingmedium ready

Problem

SIEVE Cache (Go)

Topics: cache eviction, doubly-linked list, SIEVE

Problem

Implement the SIEVE eviction algorithm (Zhang et al., NSDI 2024) — simpler than LRU, with a better hit rate, and now used in production caches. It's a single FIFO-ordered doubly-linked list where each entry has a visited bit, plus a hand that scans for a victim.

func New[K comparable, V any](capacity int) *Sieve[K, V]
func (c *Sieve[K, V]) Get(key K) (V, bool)
func (c *Sieve[K, V]) Put(key K, value V)
func (c *Sieve[K, V]) Len() int

New entries are inserted at the head (newest) with their visited bit clear.
Get (a hit) sets the entry's visited bit — its "second chance" — and does not move it.
On a full Put, evict: start at the hand (or the tail/oldest on the first eviction) and scan toward the head. Clear the visited bit of any entry you pass that has it set; evict the first entry whose bit is already clear. The hand then points at the next candidate (toward the head) and keeps that position for the next eviction.
Updating an existing key refreshes its value and marks it visited.

put 1,2,3 (cap 3); get(1); put(4)   → evicts 2, not 1 (1 had its bit set)

The node, insertAtHead, and unlink plumbing is provided; you implement Get, Put, and evict.

Run

go test -v -race ./challenges/sieve-cache/go/

Sign in to submit your solution.

Leaderboard score: lower is better, 1.0 ≈ reference

#	Name	score	ns/op	allocs

Output

No submission yet.

// Package sieve implements the SIEVE eviction algorithm (Zhang et al., NSDI '24):
// a FIFO-ordered doubly-linked list where each entry carries a visited bit, plus
// a hand that scans old→new for an unvisited victim. A hit just sets the bit; the
// hand clears bits as it passes and evicts the first entry whose bit is already
// clear, keeping its position between evictions. Simpler than LRU, better hit rate.
//
// The list scaffolding (node, insertAtHead, unlink) is provided; implement Get,
// Put, and the evict policy.
package sieve

import "sync"

type node[K comparable, V any] struct {
	key     K
	val     V
	visited bool
	// older points toward the tail (oldest), newer toward the head (newest).
	older, newer *node[K, V]
}

type Sieve[K comparable, V any] struct {
	mu    sync.Mutex
	cap   int
	items map[K]*node[K, V]
	head  *node[K, V] // newest
	tail  *node[K, V] // oldest
	hand  *node[K, V] // eviction cursor, retained between evictions
}

func New[K comparable, V any](capacity int) *Sieve[K, V] {
	return &Sieve[K, V]{cap: capacity, items: make(map[K]*node[K, V])}
}

// Get returns the value and sets the entry's visited bit (its "second chance").
func (c *Sieve[K, V]) Get(key K) (V, bool) {
	panic("not implemented")
}

// Put updates an existing key (refreshing its value and marking it visited) or
// inserts a new key at the head, evicting first if the cache is full.
func (c *Sieve[K, V]) Put(key K, value V) {
	panic("not implemented")
}

func (c *Sieve[K, V]) insertAtHead(n *node[K, V]) {
	n.older = c.head
	n.newer = nil
	if c.head != nil {
		c.head.newer = n
	}
	c.head = n
	if c.tail == nil {
		c.tail = n
	}
}

func (c *Sieve[K, V]) unlink(n *node[K, V]) {
	if n.older != nil {
		n.older.newer = n.newer
	} else {
		c.tail = n.newer
	}
	if n.newer != nil {
		n.newer.older = n.older
	} else {
		c.head = n.older
	}
}

// evict removes one entry per the SIEVE policy: scan from the hand (or the tail on
// the first eviction) toward the head, clearing visited bits, and drop the first
// entry whose bit is already clear.
func (c *Sieve[K, V]) evict() {
	panic("not implemented")
}

func (c *Sieve[K, V]) Len() int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return len(c.items)
}