README
¶
2q
Thread safe GoLang 2Q cache.
Maintained fork of the archived floatdrop/2q.
Its former dependencies (floatdrop/lru, floatdrop/fifo, both also archived)
have been folded in as internal packages, and their bahlo/generic-list-go
based linked list was replaced by a slice-backed ring (internal/ring) — so
this module has zero dependencies outside the standard library. Public API is
unchanged. See NOTICE.md for attribution.
Example
import (
"fmt"
twoqueue "github.com/d1n-go/2q"
)
func main() {
cache := twoqueue.New[string, int](256)
cache.Set("Hello", 5)
if e := cache.Get("Hello"); e != nil {
fmt.Println(*e)
// Output: 5
}
}
TTL
You can wrap values into an Expiring[T any] struct to release memory on a timer (or manually, in a Valid method).
Example implementation
import (
"fmt"
"time"
twoqueue "github.com/d1n-go/2q"
)
type Expiring[T any] struct {
value *T
}
func (E *Expiring[T]) Valid() *T {
if E == nil {
return nil
}
return E.value
}
func WithTTL[T any](value T, ttl time.Duration) Expiring[T] {
e := Expiring[T]{
value: &value,
}
time.AfterFunc(ttl, func() {
e.value = nil // Release memory
})
return e
}
func main() {
cache := twoqueue.New[string, Expiring[string]](256)
cache.Set("Hello", WithTTL("Bye", time.Hour))
if e := cache.Get("Hello").Valid(); e != nil {
fmt.Println(*e)
}
}
Note: although this short implementation frees memory after the TTL duration, it does not erase the entry for the key in the cache. It can be a problem if you do not check nilness after getting an element from the cache and call Set afterwards.
Benchmarks
Measured against the original floatdrop/2q + floatdrop/lru + floatdrop/fifo (last released versions, before archiving) with benchstat, same machine, -count=10:
name old time/op new time/op delta
2Q_Rand-8 288ns ± 4% 301ns ± 3% +4.37% (p=0.001)
2Q_Freq-8 273ns ± 1% 264ns ± 1% -3.55% (p=0.000)
geomean 281ns 282ns +0.33% (statistically indistinguishable overall)
name old alloc/op new alloc/op delta
2Q_Rand-8 46.0B ± 2% 46.0B ± 2% ~ (p=1.000)
2Q_Freq-8 44.0B ± 0% 44.0B ± 0% ~ (p=1.000)
name old allocs/op new allocs/op delta
2Q_Rand-8 3.00 ± 0% 3.00 ± 0% ~ (p=1.000)
2Q_Freq-8 3.00 ± 0% 3.00 ± 0% ~ (p=1.000)
At the public TwoQueue API level, performance is on par with the original (one workload slightly faster, one slightly slower, both within single-digit noise), with identical memory/allocation profile. The internal/ring rewrite also fixes a latent bug present in the original lru/fifo: their eviction path deleted a cache entry keyed by a preallocated-but-never-used node's zero value, which could silently drop an unrelated real entry whose key equalled that zero value (e.g. key 0 for int keys). internal/ring only clears an index entry for a slot that was actually occupied.
Documentation
¶
Index ¶
Examples ¶
Constants ¶
const ( // Default2QRecentRatio is the ratio of the 2Q cache dedicated // to recently added entries that have only been accessed once. Default2QRecentRatio = 0.25 // Default2QGhostEntries is the default ratio of ghost // entries kept to track entries recently evicted Default2QGhostEntries = 0.50 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Evicted ¶
type Evicted[K comparable, V any] struct { Key K Value V }
Evicted holds key/value pair that was evicted from cache.
type TwoQueue ¶
type TwoQueue[K comparable, V any] struct { // contains filtered or unexported fields }
TwoQueue is a thread-safe fixed size 2Q cache. 2Q is an enhancement over the standard LRU cache in that it tracks both frequently and recently used entries separately. This avoids a burst in access to new entries from evicting frequently used entries. It adds some additional tracking overhead to the standard LRU cache, and is computationally about 2x the cost, and adds some metadata over head.
Example ¶
package main
import (
"fmt"
twoqueue "github.com/d1n-go/2q"
)
func main() {
cache := twoqueue.New[string, int](256)
cache.Set("Hello", 5)
if e := cache.Get("Hello"); e != nil {
fmt.Println(*e)
}
}
Output: 5
func New ¶
func New[K comparable, V any](size int) *TwoQueue[K, V]
New creates 2Q cache with predefined size splits. 25% of size goes to Kin, 50% to KOut and rest to Am size.
func NewParams ¶
New creates 2Q cache with specified capacities:
- Kin defines A1in FIFO size for key/value pairs - Kout defines A1out FIFO size for keys - size defines frequent LRU size for key/value pairs
It's recommended to hold 25% of available memory in Kin. Kout size should correspond to 50% memory for values. And size should consume rest of memory. You can refer to original paper (http://www.vldb.org/conf/1994/P439.PDF) for computing sizes.
For example, if you can store around 10000 items in cache: - Kin should hold around 2500 items. - Kout should hold 5000 items. - And size should take the rest 7500 items.
Cache will preallocate size count of internal structures to avoid allocation in process.
func (*TwoQueue[K, V]) Get ¶
func (L *TwoQueue[K, V]) Get(key K) *V
Get probes frequent and recent cached items and returns pointer to value (or nil if it was not found).
func (*TwoQueue[K, V]) Peek ¶
func (L *TwoQueue[K, V]) Peek(key K) *V
Peek returns value for key (if key was in cache), but does not modify its recency.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
internal
|
|
|
fifo
Package fifo implements a thread-safe fixed size FIFO with O(1) Get.
|
Package fifo implements a thread-safe fixed size FIFO with O(1) Get. |
|
lru
Package lru implements cache with least recent used eviction policy.
|
Package lru implements cache with least recent used eviction policy. |
|
ring
Package ring implements a fixed-capacity intrusive ring of key/value slots backed by a single slice, combined with a key index.
|
Package ring implements a fixed-capacity intrusive ring of key/value slots backed by a single slice, combined with a key index. |