用Go实现一个分布式缓存—GoCache

[!NOTE]

原项目链接：https://geektutu.com/post/geecache.html

什么是分布式缓存

分布式缓存：指将应用系统和缓存组件进行分离的缓存机制，这样多个应用系统就可以共享一套缓存数据了，它的特点是共享缓存服务和可集群部署，为缓存系统提供了高可用的运行环境，以及缓存共享的程序运行机制。

分布式缓存系统是一个独立的缓存服务，与本地应用隔离，这使得多个应用系统之间可直接的共享缓存数据。目前分布式缓存系统已经成为微服务架构的重要组成部分。

分布式缓存的特性

相对于本地应用缓存，分布式缓存具有如下特性:

高性能：当传统数据库面临大规模数据访问时，磁盘I/O 往往成为性能瓶颈，从而导致过高的响应延迟。分布式缓存将高速内存作为数据对象的存储介质，数据以key/value 形式存储。

动态扩展性：支持弹性扩展，通过动态增加或减少节点应对变化的数据访问负载，提供可预测的性能与扩展性；同时，最大限度地提高资源利用率；

高可用性：高可用性包含数据可用性与服务可用性两方面，故障的自动发现，自动转义。确保不会因服务器故障而导致缓存服务中断或数据丢失。

易用性：提供单一的数据与管理视图；API 接口简单,且与拓扑结构无关；动态扩展或失效恢复时无需人工配置;自动选取备份节点；多数缓存系统提供了图形化的管理控制台，便于统一维护；

通过在应用服务与DB中间引入缓存层，我们可以得到如下三个好处：
（1）读取速度得到提升。
（2）系统扩展能力得到大幅增强。我们可以通过加缓存，来让系统的承载能力提升。
（3）总成本下降，单台缓存即可承担原来的多台DB的请求量，大大节省了机器成本。

使用缓存的目的

缓存的目的是为了在高并发系统中有效降低DB的压力，高效的数据缓存可以极大地提高系统的访问速度和并发性能。系统会自动根据调用的方法缓存请求的数据。当再次调用该方法时，系统会首先从缓存中查找是否有相应的数据，如果命中缓存，则从缓存中读取数据并返回；如果没有命中，则请求数据库查询相应的数据并再次缓存。每一个用户请求都会先查询缓存中的数据，如果缓存命中，则会返回缓存中的数据。这样能减少数据库查询，提高系统的响应速度。

分布式缓存的应用场景

分布式缓存的典型应用场景可分为以下几类：

页面缓存：用来缓存Web 页面的内容片段，包括HTML、CSS 和图片等，多应用于社交网站等；
应用对象缓存：缓存系统作为ORM 框架的二级缓存对外提供服务，目的是减轻数据库的负载压力，加速应用访问；
状态缓存：缓存包括Session 会话状态及应用横向扩展时的状态数据等，这类数据一般是难以恢复的，对可用性要求较高，多应用于高可用集群；
并行处理：通常涉及大量中间计算结果需要共享；
事件处理：分布式缓存提供了针对事件流的连续查询(continuous query)处理技术，满足实时性需求；
极限事务处理：分布式缓存为事务型应用提供高吞吐率、低延时的解决方案，支持高并发事务请求处理，多应用于铁路、金融服务和电信等领域；

Redis

Redis是一种基于内存的，支持网络、分布式、可选持久性的键值对(Key-Value)存储数据库。可用作数据库，缓存，消息中间件，事件发布或订阅，高速队列等场景。支持网络，提供字符串，哈希，列表，队列，集合结构直接存取，基于内存，可持久化。同时性能强劲，具有复制特性以及解决问题而生的独一无二的数据模型。它可以存储键值对与5种不同类型的值之间的映射，可以将存储在内存的键值对数据持久化到硬盘，可以使用复制特性来扩展读性能，还可以使用客户端分片来扩展写性能。

GoCache实现流程

                         是
接收 key --> 检查是否被缓存 -----> 返回缓存值 (1)
                |  否                         
                |-----> 使用一致性哈希选择节点        是                                    是
														|-----> 是否是远程节点 -----> HTTP 客户端访问远程节点 --> 成功？-----> 服务端返回返回缓存值(2)
															         |  否                                    ↓  否
										                   |----------------------------> 回退到本地节点处理。
																							                            |-----> 调用`回调函数`，获取值并添加到缓存 --> 返回缓存值 (3)

使用LRU(Least Recently Used)算法实现Cache

LRU 算法最核心的 2 个数据结构

蓝色的是字典(map)，存储键和值的映射关系。这样根据某个键(key)查找对应的值(value)的复杂是O(1)，在字典中插入一条记录的复杂度也是O(1)。
红色的是双向链表(double linked list)实现的队列。将所有的值放到双向链表中，这样，当访问到某个值时，将其移动到队尾的复杂度是O(1)，在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。

type Cache struct {
	maxBytes  int64                         //最大可使用的内存
	nbytes    int64                         //当前已使用的内存
	ll        *list.List                    //双向链表
	cache     map[string]*list.Element      //与双向链表的节点做映射
	OnEvicted func(key string, value Value) //某条记录被移除后执行的回调函数，可以为nil
}

go的标准库中有一个 container包 ，其中包含了 list（双向链表）、 heap（堆）、 ring（圈） .

这里简单介绍一下双向链表

双向链表一般用于经常对头部和尾部进行增删的场景，同时它不需要在一开始初始化它的容量，它的容量随着使用动态变化（扩大or缩小）。

go标准库中实现的list主要包含以下两个核心数据结构：

// 链表的一个元素
type Element struct {
   next, prev *Element // 前后指针
   list *List // 所属链表
   Value any // 值
}
// 链表
type List struct {
   root Element // 哨兵元素
   len  int     // 链表元素个数
}

List支持延迟初始化，因此不管你使用list.New()创建一个已经初始化的list，或者直接使用list.List{}创建一个未初始化的list，都可以正常运行。

在调用PushFront()、PushBack()、PushFrontList()、PushBackList()时会调用 lazyInit() 检查是否已经初始化，如果没有初始化则调用 Init() 进行初始化。

List包含以下方法：

PushFront()、PushBack()、PushFrontList()、PushBackList()、Front()、Back()、Len()、InsertBefore()、InsertAfter()、MoveBefore()、MoveAfter()、MoveToFront()、MoveToBack()、Remove()

一致性哈希

如何分配请求？

现在的网站通常都由多台服务器组成的集群对外提供服务，那么对于一个集群而言，如何分配用户发起的请求？

这个问题其实就是 负载均衡 。解决负载均衡问题的算法很多，不同的负载均衡算法，对应的就是不同的分配策略，适应的业务场景也不同。

最简单的方式，引入一个中间的负载均衡层，让它将外界的请求轮流的转发给内部的集群。比如集群有 3 个节点，外界请求有 3 个，那么每个节点都会处理 1 个请求，达到了分配请求的目的。

考虑到每个节点的硬件配置有所区别，我们可以引入权重值，将硬件配置更好的节点的权重值设高，然后根据各个节点的权重值，按照一定比重分配在不同的节点上，让硬件配置更好的节点承担更多的请求，这种算法叫做 加权轮询。

加权轮询算法使用场景是建立在每个节点存储的数据都是相同的前提。所以，每次读数据的请求，访问任意一个节点都能得到结果。

而在数据分片的分布式缓存系统中，由于每个节点中存储的数据都是不一致的，任意访问一个节点不一定能够命中缓存，因此采用轮询分配请求的方法并不适用。

一般的哈希算法

对于一个分布式缓存系统，一个key对应的节点应该是确定的，因此可以使用哈希算法将key和节点进行映射，如： hash(key)%n=1，对key做一次哈希运算后再对节点数量取余得到1，这就能将key映射到节点1，如果要查找key就直接请求节点1。

但这样做又一个很致命的问题：如果有一个节点宕机或者有新的节点加入，都会导致基数n的变化，那么对于一个key而言，与它映射的节点就会发生变化，因此对于所有现存的key都需要重新计算与节点之间的映射关系，否则就会导致数据查询不到，即大多数的缓存都会失效。但是这个做法数据迁移的成本太高了，而且同一时间过多的缓存同时失效，容易引起 缓存雪崩 。