缓存是几乎所有程序或产品的必需品,我们在每个角落都能看到它,比如网页、数据库、应用程序等。
它的意义在于它所带来的效率。 这就像在你忙于燃烧卡路里的问题时,把你最喜欢的零食放在桌子上,让你快速拿一下。
熟悉和可快速构建一个本地kv缓存对日常开发很重要,所以我将从头开始实现一个健全且可用的本地 kv 缓存。
首先是实现键值缓存时应考虑的因素:
一般最常用的数据结构是map[string]Element{},其中string为key,其中element包含value信息。
最简单的元素至少应该包含值和过期时间。并且值类型通常是interface{},可以根据场景换成string、int或者其他特定类型。
缓存必须考虑并发访问,除非它是特定于线程的映射。和其他高级语言一样,Go 也提供了一个线程安全的映射(sync.map)。
当然,将 map 与 sync.RWMutex 组合起来可以实现相同的功能,提供更大的灵活性并帮助更好地理解 Go。
如果要在 Kubernetes Pod 中运行,则需要提前设置缓存大小。
否则,它可能会消耗过多的内存,并导致整个 pod 因内存限制而被淘汰。
及时释放过期的key可以提高缓存利用率,节省开销,提升性能。
它与 Go 相关,减少了 GC 对缓存的影响。而sync.Pool可以用来进一步优化。
Cache有Put、Get、Remove和Flush 4个基本功能,并且开放给更多的方法以获得更好的支持。
考虑到这些元素,我们现在要设计缓存。
首先是两个简单的步骤。
type Cache struct {
defaultExpiration time.Duration
elements map[string]Elem
capacity int64
size int64
lock *sync.RWMutex
pool *sync.Pool
cleaner *cleaner
}
type Elem struct {
K string // Needed for the sync.Pool
V interface{}
Expiration int64
LastHit int64
}
type cleaner struct {
Interval time.Duration
stop chan bool
}
func (c *Cache) Get(k string) (v interface{}, err error) {
return nil, nil
}
func (c *Cache) Put(k string, v interface{}) error {
return nil, nil
}
func (c *Cache) Remove(k string) (isFound bool, err error) {
return false, nil
}
func (c *Cache) Flush() error {
return nil
}
// Used in cleaning job
func (c *Cache) RemoveExpired() {}
// Run cleaning job
func (cl *cleaner) Run(c *Cache) {}
在 New 函数中使用它们。
const (
DEFAULT_EXPIRATION = 10 * time.Minute
DEFAULT_CLEAN_DURATION = 10 * time.Minute
DEFAULT_CAP = 1024
)
func NewCache() (*Cache, error) {
return newCache(DEFAULT_CAP, DEFAULT_EXPIRATION, DEFAULT_CLEAN_DURATION)
}
func newCache(cap int64, expiration time.Duration, clean_duration time.Duration) (*Cache, error) {
return &Cache{
defaultExpiration: expiration,
elements: make(map[string]Elem, cap),
capacity: cap,
lock: new(sync.RWMutex),
cleaner: &cleaner{
Interval: clean_duration,
stop: make(chan bool),
},
pool: &sync.Pool{
New: func() interface{} {
return &Entry{}
},
},
}, nil
}
然后是 put 方法。 在为map设置key和val之前,需要做一些额外的工作。
在缓存已满,但无法删除过期key为新key腾出空间的场景下,我们需要引入一些额外的淘汰策略。
LRU,最近最少用户,就是我们在这种情况下应用的:最近没有被访问过的键将被淘汰。 但是,需要注意的是,它对历史数据并不友好。
还有一些其他的淘汰政策,例如,
LFU,最不常用的,淘汰了低频率访问的键。 潜在的问题是,如果密钥在短时间内被频繁访问,它们将在缓存中保留很长时间,尽管以后不会访问。
FIFO,先进先出,最新的保留。 其缺点与 LFU 相同。
ARC,自适应替换缓存。 作为 LRU 的高级版本,它通过与 LFU 和 LRU 集成,4 个队列,消耗更多内存来实现更高性能的缓存。
此外,还有其他算法,如双队列、MRU 等。
最后,我们来看看sync.Pool。 只有在立即使用存储的对象时才需要选择加入功能。 否则,池中的对象将在 Get 中起作用之前被频繁替换。 但这是我们未来需要改进缓存的功能。
一步一步,Put方法就搞定了。
func (c *Cache) Put(k string, v interface{}) error {
expire := time.Now().Add(DEFAULT_EXPIRATION).UnixNano()
lastHit := time.Now().UnixNano()
if c.size+1 > c.capacity {
// LRU kicks in
if err := c.removeLeastVisited(); err != nil {
return err
}
}
c.lock.Lock()
defer c.lock.Unlock()
if ele, ok := c.elements[k]; ok {
ele.V = v
ele.Expiration = expire
ele.LastHit = lastHit
return nil
}
ele := Elem{
V: v,
Expiration: expire,
LastHit: lastHit,
}
c.pool.Put(ele)
c.elements[k] = ele
c.size = c.size + 1
return nil
}
然后你会发现Get the function已经在你的口袋里了:只需从pool和map中获取结果,并更新最后访问时间和过期时间。
func (c *Cache) Get(k string) (v interface{}, err error) {
ele := c.pool.Get()
if item, ok := ele.(Elem); ok {
if item.K == k {
return item.V, nil
}
}
expire := time.Now().Add(DEFAULT_EXPIRATION).UnixNano()
lastHit := time.Now().UnixNano()
c.lock.RLock()
defer c.lock.RUnlock()
if ele, ok := c.elements[k]; ok {
ele.Expiration = expire
ele.LastHit = lastHit
return ele.V, nil
}
return nil, nil
}
接下来要做的就是构建一个自动清理器,通过启动一个 goroutine 定期清理过期时间小于当前时间的键。
// Used in cleaning job
func (c *Cache) RemoveExpired() {
now := time.Now().UnixNano()
c.lock.Lock()
defer c.lock.Unlock()
for k, v := range c.elements {
if v.Expiration > 0 && now > v.Expiration {
_, _ = c.Remove(k)
}
}
}
// Run cleaning job
func (cl *cleaner) Run(c *Cache) {
ticker := time.NewTicker(cl.Interval)
for {
select {
case <-ticker.C:
c.RemoveExpired()
case <-cl.stop:
ticker.Stop()
return
}
}
}
func stopJanitor(c *Cache) {
c.cleaner.stop <- true
}
同时,将以下两行添加到前面的 New 方法中。
go c.cleaner.Run(c)
runtime.SetFinalizer(c, stopCleaner)
至此,缓存功能基本完成,下面我们测试下性能。
迫不及待的想把我们自己搭建的缓存和Github上那些完美的缓存做个性能对比,我以go-cache和hashicorp-lrucache为例,写了一个benchmark测试,对比一下访问效率。
package golang_localcache
import (
"fmt"
"testing"
"time"
hashicorp "github.com/hashicorp/golang-lru"
gocache "github.com/patrickmn/go-cache"
)
func BenchmarkGoCache(b *testing.B) {
c := gocache.New(1*time.Minute, 5*time.Minute)
b.Run("Put", func(b *testing.B) {
for i := 0; i < b.N; i++ {
c.Add(toKey(i), toKey(i), gocache.DefaultExpiration)
}
})
b.Run("Get", func(b *testing.B) {
for i := 0; i < b.N; i++ {
value, found := c.Get(toKey(i))
if found {
_ = value
}
}
})
}
func BenchmarkCache(b *testing.B) {
c, _ := NewCache()
b.Run("Put", func(b *testing.B) {
for i := 0; i < b.N; i++ {
c.Put(toKey(i), toKey(i))
}
})
b.Run("Get", func(b *testing.B) {
for i := 0; i < b.N; i++ {
value, _ := c.Get(toKey(i))
if value != nil {
_ = value
}
}
})
}
func BenchmarkHashicorpLRU(b *testing.B) {
// c := cache2go.Cache("test")
c, _ := hashicorp.New(1024)
b.Run("Put", func(b *testing.B) {
for i := 0; i < b.N; i++ {
c.Add(toKey(i), toKey(i))
}
})
b.Run("Get", func(b *testing.B) {
for i := 0; i < b.N; i++ {
value, err := c.Get(toKey(i))
if err == true {
_ = value
}
}
})
}
func toKey(i int) string {
return fmt.Sprintf("item:%d", i)
}
结果符合我的预期。 我们的缓存比那些成熟的开源缓存慢。 但是,当它只花费我们 20 分钟时,我们还能期待什么。
结果给了我一个提示,hashicorp-cache 这么快一定是有原因的,以后我们可以在单独讲一下!
我们的缓存速度较慢,但 我们可以做一些事情来加快速度。那怎么办?
最重要的因素是并发和缓存大小,两者相互影响:并发越大,元素越多,内存占用越大,缓存越慢。因此,减少并发是第一要务。
这里我们需要一种着色方法,将一个缓存映射拆分为多个,以降低并发可能性并缩小每个缓存的大小。毫无疑问,散列最常用于阴影,因为哈希结果具有高离散率,即高随机性。
Hash避免产生过多的内存分配,缓解垃圾回收带来的压力。哈希算法非常高效。
可以很容易地得出结论,哈希方法的速度决定了着色算法的效率,因为密钥是通过 hash(key) 分配给不同的缓存的。
那么问题就在于选择哪种算法。 MD5 和 SHA-256 是最常见的哈希算法,FNV 和 DJB2 各有优势。如果您在这些选项上苦苦挣扎,请进行基准比较。
此外,添加更多方法,如直接访问字符串和直接存储 int,或优化 sync.Pool 使用也是改进缓存的方法。
互联网世界有很多的开源缓存,这使得我们免于自己编写,而且效率更高。但是,当你更了解其中实现原理的时候,开发起来会更加的高效。
页面更新:2024-05-04
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号