快速构建Go语言KVCache

　　缓存是几乎所有程序或产品的必需品，我们在每个角落都能看到它，比如网页、数据库、应用程序等。
　　它的意义在于它所带来的效率。 这就像在你忙于燃烧卡路里的问题时，把你最喜欢的零食放在桌子上，让你快速拿一下。
　　熟悉和可快速构建一个本地kv缓存对日常开发很重要，所以我将从头开始实现一个健全且可用的本地 kv 缓存。KV-Cache 的基本元素
　　首先是实现键值缓存时应考虑的因素：贮存
　　一般最常用的数据结构是map[string]Element{}，其中string为key，其中element包含value信息。元素
　　最简单的元素至少应该包含值和过期时间。并且值类型通常是interface{}，可以根据场景换成string、int或者其他特定类型。并发
　　缓存必须考虑并发访问，除非它是特定于线程的映射。和其他高级语言一样，Go 也提供了一个线程安全的映射（sync.map）。
　　当然，将 map 与 sync.RWMutex 组合起来可以实现相同的功能，提供更大的灵活性并帮助更好地理解 Go。容量
　　如果要在 Kubernetes Pod 中运行，则需要提前设置缓存大小。
　　否则，它可能会消耗过多的内存，并导致整个 pod 因内存限制而被淘汰。删除过期的
　　及时释放过期的key可以提高缓存利用率，节省开销，提升性能。GC 调优
　　它与 Go 相关，减少了 GC 对缓存的影响。而sync.Pool可以用来进一步优化。API 设计
　　Cache有Put、Get、Remove和Flush 4个基本功能，并且开放给更多的方法以获得更好的支持。缓存实现
　　考虑到这些元素，我们现在要设计缓存。
　　首先是两个简单的步骤。1）定义所有类型和功能。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 使用也是改进缓存的方法。结束
　　互联网世界有很多的开源缓存，这使得我们免于自己编写，而且效率更高。但是，当你更了解其中实现原理的时候，开发起来会更加的高效。