快速构建Go语言KV Cache
|
10,405
|
0
|
大数据,物联网

1722 字
|
7 分钟

缓存是几乎所有程序或产品的必需品，我们在每个角落都能看到它，比如网页、数据库、应用程序等。

它的意义在于它所带来的效率。 这就像在你忙于燃烧卡路里的问题时，把你最喜欢的零食放在桌子上，让你快速拿一下。  

熟悉和可快速构建一个本地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 使用也是改进缓存的方法。

结束


互联网世界有很多的开源缓存，这使得我们免于自己编写，而且效率更高。但是，当你更了解其中实现原理的时候，开发起来会更加的高效。

暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
						

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇