README
¶
clockpro
A cache implementation that utilizes the CLOCK‑Pro+ cache replacement algorithm in Go.
Example:
import (
"fmt"
clockpro "github.com/djdv/go-clockpro"
)
func GetSet() {
const (
capacity = 1024 // TODO(Anyone): Use contextual capacity.
key = "name"
value = 1
)
cache, err := clockpro.New[string, int](capacity)
if err != nil {
panic(err) // TODO(Anyone): Handle error.
}
cache.Set(key, value)
if got, ok := cache.Get(key); ok {
fmt.Printf("%s: %d\n", key, got)
}
// Output:
// name: 1
}
func LoadValue() {
const (
capacity = 1024 // TODO(Anyone): Use contextual capacity.
key = "load"
value = 1
)
cache, err := clockpro.New[string, int](capacity)
if err != nil {
panic(err) // TODO(Anyone): Handle error.
}
got, err := cache.Load(key, makeValue)
if err != nil {
panic(err) // TODO(Anyone): Handle error.
}
fmt.Printf("%s: %d\n", key, got)
if got, err = cache.Load(key, makeValue); err != nil {
panic(err) // TODO(Anyone): Handle error.
}
fmt.Printf("cached: %d\n", got)
// Output:
// initialized value: 1
// load: 1
// cached: 1
}
func makeValue() (int, error) {
const (
someValue = 1
initError = false
)
if initError {
return 0, fmt.Errorf(
"could not initialize...",
)
}
fmt.Println("initialized value:", someValue)
return someValue, nil
}
Papers:
2005 USENIX CLOCK-Pro
CLOCK-PRO+
Contributing:
Please see CONTRIBUTING.md for the terms that apply to all contributions.
Documentation
¶
Overview ¶
Package clockpro implements a Cache using the CLOCK‑Pro+ replacement algorithm.
CLOCK‑Pro+ is an adaptive, scan‑resistant policy that balances recency and frequency to improve hit rates over traditional CLOCK and LRU by utilizing adaptive hot/cold targets and a bounded metadata "test" set.
The following is a summary (intended for maintainers) of several papers, which are recursively cited by the CLOCK-Pro+ paper. Most of the clock behaviour+documentation is derived from the 2005 USENIX CLOCK-Pro paper and then adapted via the CLOCK-PRO+ paper.
Glossary and invariants:
Page contains metadata along with a potentially valid/"resident" value.
LIR: Low Inter-reference Recency (hot) page.
Resident and protected from eviction.
HIR: High Inter-reference Recency (cold) page.
May be resident or nonresident.
Test page
Nonresident HIR page retained only as metadata to guide adaptation.
Stacked
Whether the page currently exists in the stack `S` (metadata ring).
Resident
Whether the page's value is in cache (as opposed to metadata-only).
Referenced
Set on access; cleared when a hand processes the page.
Demoted
Set when an LIR is demoted to HIR until it is later referenced/processed.
Operations:
Eviction
When a resident HIR (cold) page is removed its value is discarded, but its metadata may remain as a nonresident “test page” to inform future hot/cold target adaption/adjustment.
Demotion
When an LIR (hot) page is converted into an HIR (cold) page and moves to the LRU, because the hot set exceeds its target size.
Hands:
hot
Scans until it finds an LIR with Referenced == false. Clears references and updates LRU; removes nonresident HIR page it encounters.
cold
Scans until it finds an unreferenced resident HIR to evict. On referenced HIRs: clears reference and either promotes (if stacked) or restacks.
test
Points to a nonresident, non-LIR HIR (a "test page") when testCount > 0.
lru
The tail of the ring/"recency stack"; new/updated pages are moved to lru.
Counts and targets:
hotCount + coldCount == resident capacity.
The abstract "length" of the cache / usable page count.
testCount == number of metadata-only pages.
Some pages are kept around to make adaption decisions.
coldTarget ∈ [1, capacit/2], hotTarget = capacity - coldTarget.
This is some point within the range that the hot and cold page sizes can be adapted to.
Metadata is bounded to: hotCount + coldCount + testCount ≤ 2 * size.
"So totally there are at most `2m` metadata pages for keeping track of page access history in the list."
This bound ensures adaptation history without unbounded growth.
Index ¶
Examples ¶
Constants ¶
const ErrInvalidCapacity = constError("invalid capacity")
ErrInvalidCapacity may be returned from New.
const MinimumCapacity = 2
MinimumCapacity defines the lowest value supported by New.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache[Key comparable, Value any] struct { // contains filtered or unexported fields }
Cache utilizes the Cache-Pro+ replacement algorithm. Concurrent access must be guarded by the caller. Constructed by New.
Example ¶
package main
import (
"fmt"
clockpro "github.com/djdv/go-clockpro"
)
func main() {
const (
capacity = 1024 // TODO(Anyone): Use contextual capacity.
key = "name"
value = 1
)
cache, err := clockpro.New[string, int](capacity)
if err != nil {
panic(err) // TODO(Anyone): Handle error.
}
cache.Set(key, value)
if got, ok := cache.Get(key); ok {
fmt.Printf("%s: %d\n", key, got)
}
}
Output: name: 1
func New ¶
func New[Key comparable, Value any](capacity int) (*Cache[Key, Value], error)
New creates a Cache with the given capacity. Capacity must be at least MinimumCapacity to allow both hot and cold cache pages.
func (*Cache[Key, Value]) Get ¶
func (c *Cache[Key, Value]) Get(key Key) (Value, bool)
Get returns the Value for key if it is resident in the cache, and marks it as referenced; otherwise it returns the zero value and false.
func (*Cache[Key, Value]) Load ¶
Load returns the cached value for key (if resident). Otherwise, it calls fetch, inserts and returns the value on success. If fetch returns an error, the value is not cached.
Example ¶
package main
import (
"fmt"
clockpro "github.com/djdv/go-clockpro"
)
func makeValue() (int, error) {
const (
someValue = 1
initError = false
)
if initError {
return 0, fmt.Errorf(
"could not initialize...",
)
}
fmt.Println("initialized value:", someValue)
return someValue, nil
}
func main() {
const (
capacity = 1024 // TODO(Anyone): Use contextual capacity.
key = "load"
value = 1
)
cache, err := clockpro.New[string, int](capacity)
if err != nil {
panic(err) // TODO(Anyone): Handle error.
}
got, err := cache.Load(key, makeValue)
if err != nil {
panic(err) // TODO(Anyone): Handle error.
}
fmt.Printf("%s: %d\n", key, got)
if got, err = cache.Load(key, makeValue); err != nil {
panic(err) // TODO(Anyone): Handle error.
}
fmt.Printf("cached: %d\n", got)
}
Output: initialized value: 1 load: 1 cached: 1
Source Files
Directories