go_lru_cache

README

简介

为优化对热点数据的缓存，本项目设计两个LRU队列，一个LRU队列存储数据，另一个LRU队列统计数据键热度变化。

测试

本次测试，针对符合帕累托分布(二八原则)数据进行，生成方法如下：

import numpy as np
np.random.pareto(4, 1000000))*10000 + 1

数据分布如下：

测试结果：

缓存大小100时，KEY命中率

最小热度K值	LRU算法	2Q算法	ARC算法
0(基准)	0.0875463	0.118036	0.1210772
1	0.1283985	0.1350703	0.1397713
2	0.1285002	0.1351739	0.1398301
4	0.1595406	0.1438613	0.1510483
8	-	0.1617143	0.1640282

缓存大小500时，KEY命中率

最小热度K值	LRU算法	2Q算法	ARC算法
0(基准)	0.3960788	0.4558791	0.4760088
1	0.4819089	0.4843694	0.5070587
2	0.4819796	0.4841934	0.5071921
4	0.554208	0.4959567	0.52678
8	0.568441	0.5585039	0.5572612
16		0.5664294	0.5685396

缓存大小1000时，KEY命中率

最小热度K值	LRU算法	2Q算法	ARC算法
0(基准)	0.7231351	0.693408	0.7209555
1	0.7227088	0.7102965	0.7432944
2	0.7691043	0.7101937	0.7432019
4	0.7855555	0.7160656	0.7601185
8	-	0.7740888	0.7720391
16	-	0.7813305	0.7814856

缓存大小2000时，KEY命中率

最小热度K值	LRU算法	2Q算法	ARC算法
0(基准)	0.8959815	0.8899972	0.9080057
1	0.906264	0.8898667	0.9145529
2	0.9063081	0.8897457	0.9143771
4	0.918635	0.8899214	0.9170311
8	0.9227886	0.9190385	0.9192692

算法流程

数据查询流程：

数据更新流程:

BenchMark

BenchmarkBucketLru_Single-4      1000000              1268 ns/op             140 B/op          4 allocs/op
BenchmarkBucketLru_K-4           1000000              1257 ns/op             118 B/op          3 allocs/op
BenchmarkBucket2Q_Single-4       1000000              1971 ns/op             166 B/op          4 allocs/op
BenchmarkBucket2Q_K-4            1000000              1624 ns/op             112 B/op          3 allocs/op
BenchmarkBucketArc_Single-4      1000000              2028 ns/op             167 B/op          4 allocs/op
BenchmarkBucketArc_K-4           1000000              1692 ns/op             113 B/op          3 allocs/op

示例

Documentation

Index

• Constants
• type BucketI
  • func NewBucket(opts *CacheOptions) (BucketI, error)
  • func NewBucketLru(opts *CacheOptions) (BucketI, error)
  • func NewBucketLruArc(opts *CacheOptions) (BucketI, error)
  • func NewBucketLruTwoQueue(opts *CacheOptions) (BucketI, error)
  • func NewBucketSimple(opts *CacheOptions) BucketI
• type BucketLru
  • func (bucket *BucketLru) Add(key string, value interface{}, ttl time.Duration) bool
  • func (bucket *BucketLru) Get(key string) (interface{}, bool, bool)
  • func (bucket *BucketLru) Remove(key string)
• type BucketLruArc
  • func (bucket *BucketLruArc) Add(key string, value interface{}, ttl time.Duration) bool
  • func (bucket *BucketLruArc) Get(key string) (interface{}, bool, bool)
  • func (bucket *BucketLruArc) Remove(key string)
• type BucketLruTwoQueue
  • func (bucket *BucketLruTwoQueue) Add(key string, value interface{}, ttl time.Duration) bool
  • func (bucket *BucketLruTwoQueue) Get(key string) (interface{}, bool, bool)
  • func (bucket *BucketLruTwoQueue) Remove(key string)
• type BucketSimple
  • func (bucket *BucketSimple) Add(key string, value interface{}, ttl time.Duration) bool
  • func (bucket *BucketSimple) Get(key string) (interface{}, bool, bool)
  • func (bucket *BucketSimple) Remove(key string)
• type Cache
  • func (cache *Cache) Add(key string, value interface{}, ttl time.Duration) bool
  • func (cache *Cache) Get(key string) (interface{}, bool, bool)
  • func (cache *Cache) Remove(key string)
• type CacheI
  • func NewCache(options *CacheOptions) (CacheI, error)
• type CacheOptions
• type Item
• type Limiter
  • func (limiter *Limiter) Acquire() bool
  • func (limiter *Limiter) Hit()
  • func (limiter *Limiter) HitRate() float64
  • func (limiter *Limiter) MissedQps() float64
  • func (limiter *Limiter) Qps() float64

Constants

const CacheTypeArc = "arc"

const CacheTypeLru = "lru"

const CacheTypeSimple = "simple"

const CacheTypeTwoQueue = "2q"

const DefaultBucketSize = 32

const DefaultDecreaseRatio = 0.9

const DefaultSize = 10240

const HistorySize = 12

Types

type BucketI

type BucketI interface {
	Add(key string, value interface{}, ttl time.Duration) bool
	Get(key string) (data interface{}, found bool, canAdd bool)
	Remove(key string)
}

func NewBucket

func NewBucket(opts *CacheOptions) (BucketI, error)

func NewBucketLru

func NewBucketLru(opts *CacheOptions) (BucketI, error)

func NewBucketLruArc

func NewBucketLruArc(opts *CacheOptions) (BucketI, error)

func NewBucketLruTwoQueue

func NewBucketLruTwoQueue(opts *CacheOptions) (BucketI, error)

func NewBucketSimple

func NewBucketSimple(opts *CacheOptions) BucketI

type BucketLru

type BucketLru struct {
	BucketI
	// contains filtered or unexported fields
}

func (*BucketLru) Add

func (bucket *BucketLru) Add(key string, value interface{}, ttl time.Duration) bool

func (*BucketLru) Get

func (bucket *BucketLru) Get(key string) (interface{}, bool, bool)

func (*BucketLru) Remove

func (bucket *BucketLru) Remove(key string)

type BucketLruArc

type BucketLruArc struct {
	BucketI
	// contains filtered or unexported fields
}

func (*BucketLruArc) Add

func (bucket *BucketLruArc) Add(key string, value interface{}, ttl time.Duration) bool

func (*BucketLruArc) Get

func (bucket *BucketLruArc) Get(key string) (interface{}, bool, bool)

func (*BucketLruArc) Remove

func (bucket *BucketLruArc) Remove(key string)

type BucketLruTwoQueue

type BucketLruTwoQueue struct {
	BucketI
	// contains filtered or unexported fields
}

func (*BucketLruTwoQueue) Add

func (bucket *BucketLruTwoQueue) Add(key string, value interface{}, ttl time.Duration) bool

func (*BucketLruTwoQueue) Get

func (bucket *BucketLruTwoQueue) Get(key string) (interface{}, bool, bool)

func (*BucketLruTwoQueue) Remove

func (bucket *BucketLruTwoQueue) Remove(key string)

type BucketSimple

type BucketSimple struct {
	BucketI
	// contains filtered or unexported fields
}

func (*BucketSimple) Add

func (bucket *BucketSimple) Add(key string, value interface{}, ttl time.Duration) bool

func (*BucketSimple) Get

func (bucket *BucketSimple) Get(key string) (interface{}, bool, bool)

func (*BucketSimple) Remove

func (bucket *BucketSimple) Remove(key string)

type Cache

type Cache struct {
	CacheI

	Limiter *Limiter
	// contains filtered or unexported fields
}

func (*Cache) Add

func (cache *Cache) Add(key string, value interface{}, ttl time.Duration) bool

func (*Cache) Get

func (cache *Cache) Get(key string) (interface{}, bool, bool)

func (*Cache) Remove

func (cache *Cache) Remove(key string)

type CacheI

type CacheI interface {
	Add(key string, value interface{}, ttl time.Duration) bool
	Get(key string) (data interface{}, found bool, canAdd bool)
	Remove(key string)
}

func NewCache

func NewCache(options *CacheOptions) (CacheI, error)

type CacheOptions

type CacheOptions struct {
	CacheType  string
	Size       int
	BucketSize int

	DefaultTTL             time.Duration
	DefaultCleanUpInterval time.Duration
	LruStoreHitMin         int
	LruStoreHitInterval    time.Duration

	QpsMax         int64
	ReservedQpsMin int64
	MissedQpsMax   int64
}

type Item

type Item struct {
	// contains filtered or unexported fields
}

type Limiter

type Limiter struct {
	// contains filtered or unexported fields
}

func (*Limiter) Acquire

func (limiter *Limiter) Acquire() bool

func (*Limiter) Hit

func (limiter *Limiter) Hit()

func (*Limiter) HitRate

func (limiter *Limiter) HitRate() float64

func (*Limiter) MissedQps

func (limiter *Limiter) MissedQps() float64

func (*Limiter) Qps

func (limiter *Limiter) Qps() float64