memorycache's Introduction

MemoryCache

To the time to life, rather than to life in time.

中文

Description

Minimalist in-memory KV storage, powered by HashMap and Minimal Quad Heap.

Cache Elimination Policy:

Set method cleans up overflowed keys
Active cycle cleans up expired keys

Principle

Storage Data Limit: Limited by maximum capacity
Expiration Time: Supported
Cache Eviction Policy: LRU
Persistent: None
Locking Mechanism: Slicing + Mutual Exclusion Locking
HashMap, Heap and LinkedList (excluding user KVs) implemented in pointerless technology

Advantage

Simple and easy to use
High performance
Low memory usage
Use quadruple heap to maintain the expiration time, effectively reduce the height of the tree, and improve the insertion performance

Methods

Set : Set key-value pair with expiring time. If the key already exists, the value will be updated. Also the expiration time will be updated.
SetWithCallback : Set key-value pair with expiring time and callback function. If the key already exists, the value will be updated. Also the expiration time will be updated.
Get : Get value by key. If the key does not exist, the second return value will be false.
GetWithTTL : Get value by key. If the key does not exist, the second return value will be false. When return value, method will refresh the expiration time.
Delete : Delete key-value pair by key.
GetOrCreate : Get value by key. If the key does not exist, the value will be created.
GetOrCreateWithCallback : Get value by key. If the key does not exist, the value will be created. Also the callback function will be called.

Example

package main

import (
	"fmt"
	"github.com/lxzan/memorycache"
	"time"
)

func main() {
	mc := memorycache.New[string, any](
		// Set the number of storage buckets, y=pow(2,x)
		memorycache.WithBucketNum(128),

		// Set bucket size, initial size and maximum capacity (single bucket)
		memorycache.WithBucketSize(1000, 10000),

		// Set the expiration time check period. 
		// If the number of expired elements is small, take the maximum value, otherwise take the minimum value.
		memorycache.WithInterval(5*time.Second, 30*time.Second),
	)

	mc.SetWithCallback("xxx", 1, time.Second, func(element *memorycache.Element[string, any], reason memorycache.Reason) {
		fmt.Printf("callback: key=%s, reason=%v\n", element.Key, reason)
	})

	val, exist := mc.Get("xxx")
	fmt.Printf("val=%v, exist=%v\n", val, exist)

	time.Sleep(2 * time.Second)

	val, exist = mc.Get("xxx")
	fmt.Printf("val=%v, exist=%v\n", val, exist)
}

Benchmark

1,000,000 elements

goos: linux
goarch: amd64
pkg: github.com/lxzan/memorycache/benchmark
cpu: AMD Ryzen 5 PRO 4650G with Radeon Graphics
BenchmarkMemoryCache_Set-8              16107153                74.85 ns/op           15 B/op          0 allocs/op
BenchmarkMemoryCache_Get-8              28859542                42.34 ns/op            0 B/op          0 allocs/op
BenchmarkMemoryCache_SetAndGet-8        27317874                63.02 ns/op            0 B/op          0 allocs/op
BenchmarkRistretto_Set-8                13343023               272.6 ns/op           120 B/op          2 allocs/op
BenchmarkRistretto_Get-8                19799044                55.06 ns/op           17 B/op          1 allocs/op
BenchmarkRistretto_SetAndGet-8          11212923               119.6 ns/op            30 B/op          1 allocs/op
BenchmarkTheine_Set-8                    3775975               322.5 ns/op            30 B/op          0 allocs/op
BenchmarkTheine_Get-8                   21579301                54.94 ns/op            0 B/op          0 allocs/op
BenchmarkTheine_SetAndGet-8              6265330               224.6 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/lxzan/memorycache/benchmark  53.498s

memorycache's People

Contributors

Stargazers

Watchers

memorycache's Issues

类似思路的一个库

作者你好，我前段时间也处于相同的初衷的编写了一个 lru 库。

实现尽量简单 2. 内存和GC负担尽量小 3. 使用分片而不是 RCU 加速(因为会有 GC 负担)

https://github.com/phuslu/lru

随机的混合写的速度是明显快于其他库的，不过 zipf 分布应该不如 RCU 的实现 (otter 等）

Memorycache benchmarks

I think atomic counter is not needed in benchmarks and something strange happens with capacity, that's why I suggest this code:

package benchmark

import (
	"testing"
	"time"

	"github.com/dgraph-io/ristretto"
	"github.com/lxzan/memorycache"
	"github.com/lxzan/memorycache/internal/utils"
	"github.com/maypok86/otter"
)

const (
	benchcount = 1280000
	capacity   = benchcount / 10
)

var benchkeys = make([]string, 0, benchcount)

func init() {
	for i := 0; i < benchcount; i++ {
		benchkeys = append(benchkeys, string(utils.AlphabetNumeric.Generate(16)))
	}
}

func BenchmarkMemoryCache_Set(b *testing.B) {
	var mc = memorycache.New(
		memorycache.WithBucketNum(128),
		memorycache.WithBucketSize(capacity/1280, capacity/128),
	)
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			mc.Set(benchkeys[index], 1, time.Hour)
		}
	})
}

func BenchmarkMemoryCache_Get(b *testing.B) {
	var mc = memorycache.New(
		memorycache.WithBucketNum(128),
		memorycache.WithBucketSize(capacity/1280, capacity/128),
	)
	for i := 0; i < benchcount; i++ {
		mc.Set(benchkeys[i%benchcount], 1, time.Hour)
	}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			mc.Get(benchkeys[index])
		}
	})
}

func BenchmarkMemoryCache_SetAndGet(b *testing.B) {
	var mc = memorycache.New(
		memorycache.WithBucketNum(128),
		memorycache.WithBucketSize(capacity/1280, capacity/128),
	)
	for i := 0; i < benchcount; i++ {
		mc.Set(benchkeys[i%benchcount], 1, time.Hour)
	}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			if index&7 == 0 {
				mc.Set(benchkeys[index], 1, time.Hour)
			} else {
				mc.Get(benchkeys[index])
			}
		}
	})
}

func BenchmarkRistretto_Set(b *testing.B) {
	var mc, _ = ristretto.NewCache(&ristretto.Config{
		NumCounters: 10 * capacity, // number of keys to track frequency of (10M).
		MaxCost:     capacity,      // maximum cost of cache (1GB).
		BufferItems: 64,            // number of keys per Get buffer.
	})
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			mc.SetWithTTL(benchkeys[index], 1, 1, time.Hour)
		}
	})
}

func BenchmarkRistretto_Get(b *testing.B) {
	var mc, _ = ristretto.NewCache(&ristretto.Config{
		NumCounters: 10 * capacity, // number of keys to track frequency of (10M).
		MaxCost:     capacity,      // maximum cost of cache (1GB).
		BufferItems: 64,            // number of keys per Get buffer.
	})
	for i := 0; i < benchcount; i++ {
		mc.SetWithTTL(benchkeys[i%benchcount], 1, 1, time.Hour)
	}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			mc.Get(benchkeys[index])
		}
	})
}

func BenchmarkRistretto_SetAndGet(b *testing.B) {
	var mc, _ = ristretto.NewCache(&ristretto.Config{
		NumCounters: 10 * capacity, // number of keys to track frequency of (10M).
		MaxCost:     capacity,      // maximum cost of cache (1GB).
		BufferItems: 64,            // number of keys per Get buffer.
	})
	for i := 0; i < benchcount; i++ {
		mc.SetWithTTL(benchkeys[i%benchcount], 1, 1, time.Hour)
	}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			if index&7 == 0 {
				mc.SetWithTTL(benchkeys[index], 1, 1, time.Hour)
			} else {
				mc.Get(benchkeys[index])
			}
		}
	})
}

func BenchmarkOtter_Set(b *testing.B) {
	var mc, _ = otter.MustBuilder[string, int](capacity).Build()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			mc.SetWithTTL(benchkeys[index], 1, time.Hour)
		}
	})
}

func BenchmarkOtter_Get(b *testing.B) {
	mc, _ := otter.MustBuilder[string, int](capacity).Build()
	for i := 0; i < benchcount; i++ {
		mc.SetWithTTL(benchkeys[i%benchcount], 1, time.Hour)
	}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			if index&7 == 0 {
				mc.SetWithTTL(benchkeys[index], 1, time.Hour)
			} else {
				mc.Get(benchkeys[index])
			}
		}
	})
}

func BenchmarkOtter_SetAndGet(b *testing.B) {
	mc, _ := otter.MustBuilder[string, int](capacity).Build()
	for i := 0; i < benchcount; i++ {
		mc.SetWithTTL(benchkeys[i%benchcount], 1, time.Hour)
	}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			index := i % benchcount
			i++
			if index&7 == 0 {
				mc.SetWithTTL(benchkeys[index], 1, time.Hour)
			} else {
				mc.Get(benchkeys[index])
			}
		}
	})
}