garnet/go/src/thinfs/cache/arc.go

// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Package cache provides an object cache that uses an adaptive replacement policy
// described by Mediddo & Modha in "Outperforming LRU with an Adaptive Replacement
// Cache Algorithm".
package cache

import (
	"container/list"
)

// Key represents a key to an object in the cache.
type Key interface{}

// Value represents a value associated with a key in the cache.
type Value interface{}

// sigh...
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Entry represents a single entry in the cache.
type Entry struct {
	// The list.Element corresponding to this entry.
	elem *list.Element

	// The list.List to which this entry belongs.
	list *list.List

	// The key for this entry.
	key Key

	// The value associated with the key for this entry.
	Value Value

	// Indicates whether this entry has been modified.  Callers must set this field
	// to true when they modify Value.  The cache will only commit this Entry to the BackingStore
	// if IsDirty is true.
	IsDirty bool
}

// BackingStore defines the interface that the cache expects from the storage medium for which
// it is acting as a cache.
type BackingStore interface {
	// Get is called by the cache when a requested key is not found in the cache and needs
	// to be read in from the BackingStore.
	Get(Key) Value

	// Put is called by the cache when a dirty entry is flushed and should be committed to
	// the BackingStore.
	Put(Key, Value)
}

// C represents an object cache.
type C struct {
	lru     *list.List // Least recently used.
	lruhist *list.List // Least recently used history.
	lfu     *list.List // Least frequently used.
	lfuhist *list.List // Least frequently used history.

	p       int            // The adaptive parameter.
	size    int            // Size of the cache.
	bs      BackingStore   // Backing store for the cache.
	entries map[Key]*Entry // The actual cache entries.
}

// New returns a new, initialized Adaptive Replacement Cache.
func New(size int, bs BackingStore) *C {
	return &C{
		lru:     list.New(),
		lruhist: list.New(),
		lfu:     list.New(),
		lfuhist: list.New(),
		p:       0,
		size:    size,
		entries: make(map[Key]*Entry),
		bs:      bs,
	}
}

// evict moves the last Entry from top to the front of bottom, clearing the value associated with the
// Entry and committing it to the BackingStore, if necessary.
func (c *C) evict(top, bottom *list.List) {
	victim := top.Back().Value.(*Entry)

	// Flush the entry.
	if victim.IsDirty {
		c.bs.Put(victim.key, victim.Value)
		victim.IsDirty = false
	}
	victim.Value = nil

	// Move onto bottom.
	top.Remove(victim.elem)
	victim.elem = bottom.PushFront(victim)
	victim.list = bottom
}

// replace implements the REPLACE subroutine from the paper.
func (c *C) replace(e *Entry) {
	lrulen := c.lru.Len()
	if lrulen >= 1 && ((e.list == c.lfuhist && lrulen == c.p) || lrulen > c.p) {
		c.evict(c.lru, c.lruhist)
	} else {
		c.evict(c.lfu, c.lfuhist)
	}
}

// remove deletes an Entry from the cache, committing its value to the BackingStore, if necessary.
func (c *C) remove(e *Entry) {
	if e.IsDirty {
		c.bs.Put(e.key, e.Value)
		e.IsDirty = false
	}
	e.Value = nil

	e.list.Remove(e.elem)
	e.list = nil
	e.elem = nil
	delete(c.entries, e.key)
}

// handleMiss implements Case IV from the paper.
func (c *C) handleMiss(e *Entry) {
	if l1len := c.lru.Len() + c.lruhist.Len(); c.size == l1len {
		if c.lru.Len() < c.size {
			c.remove(c.lruhist.Back().Value.(*Entry))
			c.replace(e)
		} else {
			c.remove(c.lru.Back().Value.(*Entry))
		}
	} else if l2len := c.lfu.Len() + c.lfuhist.Len(); l1len < c.size && l1len+l2len >= c.size {
		if l1len+l2len == 2*c.size {
			c.remove(c.lfuhist.Back().Value.(*Entry))
		}
		c.replace(e)
	}
	e.elem = c.lru.PushFront(e)
}

// handleHit implements Case I from the paper.
func (c *C) handleHit(e *Entry) {
	e.list.Remove(e.elem)
	e.elem = c.lfu.PushFront(e)
	e.list = c.lfu
}

// handleFakeHit implements Case II and Case III from the paper.
func (c *C) handleFakeHit(e *Entry) {
	// Adapt p.
	if e.list == c.lruhist {
		c.p = min(c.size, c.p+max(c.lfuhist.Len()/c.lruhist.Len(), 1))
	} else {
		c.p = max(0, c.p-max(c.lruhist.Len()/c.lfuhist.Len(), 1))
	}
	c.replace(e)

	c.handleHit(e)
}

// Get returns the Entry containing the Value for the Key k, fetching it from the BackingStore
// if necessary.  Callers _must_ set the IsDirty field for the returned Entry if they change the
// Value in the Entry to ensure that the change is propagated to the BackingStore.  Callers must
// also not retain the returned Entry.
func (c *C) Get(k Key) *Entry {
	e, ok := c.entries[k]
	if !ok {
		e = &Entry{
			list:    c.lru,
			key:     k,
			Value:   c.bs.Get(k),
			IsDirty: false,
		}
		c.entries[k] = e

		c.handleMiss(e)
	} else if e.list == c.lruhist || e.list == c.lfuhist {
		e.Value = c.bs.Get(k)

		c.handleFakeHit(e)
	} else {
		c.handleHit(e)
	}

	return e
}

// Put associates the Value v with the Key k and stores it in the cache.  It additionally marks the
// Entry dirty so that the new Value will be propagated to the BackingStore.  Callers may wish to
// use Put when they want to completely replace the Value associated with some Key and want to avoid
// a potentially expensive lookup for the Key in the BackingStore.
func (c *C) Put(k Key, v Value) {
	e, ok := c.entries[k]
	if !ok {
		e = &Entry{
			list:    c.lru,
			key:     k,
			Value:   v,
			IsDirty: true,
		}
		c.entries[k] = e

		c.handleMiss(e)
	} else if e.list == c.lruhist || e.list == c.lfuhist {
		e.Value = v
		e.IsDirty = true

		c.handleFakeHit(e)
	} else {
		e.Value = v
		e.IsDirty = true

		c.handleHit(e)
	}
}

// Flush commits all dirty Entries in the cache to the BackingStore.
func (c *C) Flush() {
	for _, e := range c.entries {
		if !e.IsDirty {
			continue
		}

		c.bs.Put(e.key, e.Value)
		e.IsDirty = false
	}
}