写点什么

基于 Go 的缓存实现

作者:俞凡
  • 2022-12-25
    上海
  • 本文字数:2978 字

    阅读完需:约 10 分钟

缓存是架构设计中的常用概念,本文基于 Go 实现了一个简单的缓存组件,支持最基本的缓存操作。原文: Implementing Cache With Go


客户端-服务器缓存

简介

概念

缓存是计算机科学中的一个重要概念。设想某个组件需要访问外部资源,它向外部源请求资源,接收并使用资源,这些步骤都需要花费时间。当组件再次需要资源时,可以再次请求资源,但这种方式从时间上考虑是比较低效的。相反,组件可以将请求结果保存在本地某处,然后再次使用,使用本地数据总是比请求外部数据要快,这一策略就是缓存的基本概念。我们可以在内存、CPU 缓存和服务器缓存(如 Redis)中找到这些例子。

不同用例

Web 服务中的缓存用于减少数据请求的延迟。Web 服务保存第一次查询的执行结果,然后在需要的时候再次使用,而不用再次访问数据库。取决于数据的特性,缓存有不同情况,可以有相对静态的数据,如统计数据、计算结果,也有可能是经常变化的数据,如评论区或 SNS。


最好的情况是缓存那些很少变化的数据。以月度统计数据为例,上个月的数据将不会变化,如果对它进行缓存,可能就不需要查询数据库获取上个月的数据了。


愚蠢的设计


对于快速变化的数据,在存在多个服务器时最好谨慎些。看看上面的设计,以评论区服务为例,考虑如下场景,用户 A 发表了一些评论,然后 A 决定删除评论,用户 B 尝试回复评论。在某些情况下,A 和 B 向不同的服务器发送请求。A 的删除操作可能不会传播到 B 的服务器缓存。结果会是这样: 缓存 A 和缓存 B 有不同的数据,数据库不知道哪个才是真实的,数据的完整性被破坏了。


更好的方式


在这种情况下,可以使用单一外部缓存(如上图所示),多个服务器只访问统一的缓存。

限制条件

缓存比数据库要快,但在大小上要小得多。这是因为数据库将数据存储在驱动器中,缓存将数据存储在内存中。它们遵循各自相同的特征,同样也有不同的特点,如果主机停止工作,缓存的所有数据都会丢失,但数据库的数据不会丢失。


由于缓存位于内存中,空间是有限的,需要选择缓存哪些数据。在 CS 课上,我们会听到 LRU(Least Recently Used,最近最少使用),LFU(Least Frequently Used,最不常用)和 FIFO(First In First Out,先入先出)这样的词,这些是"选择哪一个"的标准,被称为驱逐策略(eviction policy)。

设计 &实现

需求
  • 键值存储(Key-Value Storage): 缓存既要有输入键、输出值的读功能,也要有输入键、值的写功能。这些函数应该在平均 O(logN)时间内完成,其中 N 是键的数量。

  • LRU 驱逐策略: 由于缓存空间有限,如果缓存满了,一些数据应该被清除,选择用 LRU 算法实现。

  • TTL (Time To Live): 每个键值都有生存时间,如果 TTL 到期,该键值应该被驱逐。

API 设计

键值存储的意思是,如果请求键,缓存会返回那些存在的键的值,类似于 hash-map 抽象数据类型,以提供以下 API 概念的应用程序为例:


func Get(key string) (hit bool, value []byte)func Put(key string, value []byte) (hit bool)
复制代码


  • Get: 通过键读取值的 API。如果所提供的键在缓存中存在,则返回等效值。如果不存在,则返回 hit=false。对于 LRU 策略,键将被标记为最近被使用,从而使该键不会被驱逐。

  • Put: 通过键写入值的 API。如果所提供的键存在,则 value 将被替换为新值。如果不存在,将创建新的键值存储。因为该函数可以添加数据,其执行可能会导致溢出。在这种情况下,根据 LRU 策略,最近最少使用的键值将被清除。新添加/修改的键将被标记为最近使用的键。

数据结构

设计概念


我们使用两种不同的数据结构: hash-map 和双向链表,实现键值读写和 LRU 策略的特性。


  • Hash-map: Hash-map 是使用最广泛的键值数据结构,在 Go 中是现成的数据类型,可以通过map[<type>]<type>定义。

  • 双向链表: LRU 缓存可以通过双向链表实现。


基于这两种数据结构可以同时提供键值特性和 LRU 策略。参考以上设计概念图,hash-map 的键将是字符串键,值是指向链表节点的指针,节点将保存键的值。


如果用户调用Get(),缓存应用程序将在 hash-map 中搜索键,跟随指针到达链表中的一个节点,获取值,完成 LRU 策略,并将值返回给用户。


类似的,如果调用Put(),会在 hash-map 中搜索键,跟踪指针并替换值,完成 LRU 策略,或者向 hash-map 中插入新键,并向链表中插入新节点。

并发控制

由于缓存被设计为支持频繁访问,因此在同一时间会有多个访问,并且总是存在并发问题的可能性。


在该设计中,存在两种不同的数据结构,并且并不总是同步的。在执行过程中,hash-map 的修改和链表的修改之间有一个微小的时间间隔,请看下面的例子。


并发问题案例


  1. 该问题的触发条件为: 当前缓存已满,最近最少使用的键为 1。这意味着,如果添加了新的键,键 1 和等效的值将被清除。

  2. 用户 A 使用新键 101 调用 Put()。hash-map 检查键,发现 101 不存在,决定清除 1 并将 101 添加到缓存中。

  3. 同时,用户 B 使用键 1 调用 Put()。hash-map 确认键 1 存在,并决定修改该值。

  4. A 的调用继续执行,从链表中删除节点 1,从 hash-map 中删除键 1。

  5. 紧接着,B 的调用试图访问节点 1 的地址,并发现该地址已不存在,从而发生 panic 并造成应用失效。


防止这种情况发生的最简单方法是使用互斥(Mutex) ,参考以下代码。


func (s *CStorage) Get(key string) (data []byte, hit bool) {  s.mutex.Lock()  defer s.mutex.Unlock()    n, ok := s.table[key]  if !ok {    return nil, false  }  if n.ttl.Before(time.Now()) {    s.evict(n)    s.size--    return nil, false  }    return n.data, true}
复制代码


这段代码是Get()的函数定义,可以看到在第一行中有互斥锁代码,在第二行中有 defer 的互斥锁解锁代码(defer 是 Go 关键字,将行执行推迟到函数的末尾)。这些代码应用于所有其他数据存储访问功能,如 Put、Delete、Clear 等。


通过使用互斥锁,每次执行都不会受到其他操作的影响,保证了数据访问的安全性。

生存时间(Time To Live)

目前 TTL 是采用被动方式实现的,这意味着如果执行了数据访问函数(Get, Put),它将检查 TTL 是否过期并决定是否删除。这也意味着即使节点已经过期,将仍然存在于数据结构中。


这种方法不需要消耗大量 CPU 时间来定期遍历所有节点,但是缓存很可能会保存过期的值。


大多数情况下,这么做没有问题,因为过期节点很可能是"最近最少使用"状态。但是,如果有函数通过数据结构清除过期节点就更好了,所以我们使用RemoveExpired()函数。


func (s *CStorage) RemoveExpired() int64 {  var count int64 = 0  for key, value := range s.table {    if value.ttl.Before(time.Now()) {      s.Delete(key)      count++    }  }  return count}
复制代码


此函数将被定期调用以清除所有过期节点。

结果
  • github.com: https://github.com/cocm1324/cstorage

  • pkg.go.dev: https://pkg.go.dev/github.com/cocm1324/cstorage


实现的 Go 包可以导入其他 Go 项目。另外,我还做了独立的缓存应用程序,提供 gRPC API,细节可以查看这个存储库



结论

这是个很好的重新审视缓存概念的机会,并且我们用 Go 实现了缓存。缓存是降低组件延迟的好工具,虽然空间受限,但速度更快。


实现实际的缓存模块可以用 hash-map 和双向链表完成。并发问题有点棘手,所以不得不使用互斥锁。此外,我们混合了被动和主动方式来删除过期数据。




你好,我是俞凡,在 Motorola 做过研发,现在在 Mavenir 做技术工作,对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓厚的兴趣,平时喜欢阅读、思考,相信持续学习、终身成长,欢迎一起交流学习。

微信公众号:DeepNoMind

发布于: 2022-12-25阅读数: 21
用户头像

俞凡

关注

公众号:DeepNoMind 2017-10-18 加入

俞凡,Mavenir Systems研发总监,关注高可用架构、高性能服务、5G、人工智能、区块链、DevOps、Agile等。公众号:DeepNoMind

评论

发布
暂无评论
基于Go的缓存实现_架构_俞凡_InfoQ写作社区