在本项目中，很多部分参考了geketutu的实现和groupcache的实现。与tutu的geecache相比，本项目实现了一些全新的功能，分别包括：
- LRU
- ttl
- grpc
- expired cache eviction
后续还会实现
etcd服务注册(这里留一个坑), 填坑！ 本项目主要作为一个教学或者基础项目，所以没有方便的客户端来供使用，本人将从学习的角度来讲解一下项目的思路以及实现流程。
对于缓存来说，其空间不是无限大的，当缓存的值达到一定的阈值后，就要发生缓存驱逐。
常见的驱逐算法有FIFO(First In First Out)、LRU(Least RecentLy Used)和LFU(Least Frequently Used)。但是，由于缓存是“金子一样珍贵”的东西，如果被驱逐的数据是热点数据(即多个请求可能请求的值)，那么当再次发起访问的时候，就会发生cache miss，从而可能增加数据库的压力，有可能导致服务宕机！所以一个合理且高效的缓存驱逐策略是很必要的，下面来分析一下常见的三种算法。
FIFO算法也就是队列的思想，先缓存的值在驱逐的时候优先被驱逐。这个算法的实现思路很简单，只需要根据先后顺序来维护一个队列即可。
假设此时缓存达到上限，要发生缓存驱逐，那么，根据这个原则，优先到来的缓存key1就要被驱逐，此时就可以添加一个新的缓存。
显然，FIFO的缺点就是只是根据先后顺序去进行删除，如果key1是一个热点数据，那么这个cache就会发生miss。所以，我们不采用这种算法。
LRU的数据结构一般来说是Map + DoubleLinkList，Map可以提供O(1)查询， 而DoubleLinkList可以将热点key放到队首来，这样可以保证队首的数据总是热点数据，这样在key驱逐的时候，只需要淘汰队尾数据即可。
LFU在wiki上的描述就是维护一个内部计数器，当cache hit的时候，就把这个引用计数+1，这样，当达到容量后，引用计数最小的那个cache就该被驱逐。
Wiki: The simplest method to employ an LFU algorithm is to assign a counter to every block that is loaded into the cache. Each time a reference is made to that block the counter is increased by one. When the cache reaches capacity and has a new block waiting to be inserted the system will search for the block with the lowest counter and remove it from the cache, in case of a tie (i.e., two or more keys with the same frequency), the Least Recently Used key would be invalidated.
这样的思路很直观，但是请考虑一种情况，当一个key块在某一段时间内被一直访问，之后却不再访问。也就是说，这个key块有着一个次数很多的引用计数，即使它之后没有被访问；当发生key驱逐的时候，这个key块也不会被驱逐，但是在这一段时间内，这个块并不是热点数据，也就是说，LFU并不可以很好的反映热点数据。
所以，我们折中一下，选择比较完美的LRU
LRU-K这个k的含义就是指访问k次之后，这个key才可以变为热点数据，从而实现热点数据追踪。其思路就是维护两个cache块，一个是history cache，另一个就是hot cache。当请求到来时，会先到达history cache，当这个请求的次数大于k次后，就会移动到hot cache中，因此，可以将访问次数封装为一个cache字段。
// Real data that stored in cache
type entry struct {
key string
visit int
value Value
}对于一个cache来说，自动清理过期数据是很有必要的，清理过期数据可以节省大量的空间，从而更少的发生cache eviction，不过，自动清理的时间也不宜设置的过短，否则也会发生cache miss。
在go语言中，可以轻松使用多线程，当我们启动一个cache服务后，就可以使用多线程来清理缓存。
过期策略的思路就是去记录key的过期时间，每次在Get缓存的时候，都要对key进行是否过期的判断。
定时清理也就是一个定时器触发的一个任务，创建定时器可以通过time.NewTicker来创建，这样，当定时器触发时，就可以把“触发的信号”发送到定时器的chan中来作为触发定时器的标志。
func (c *cache) startEvictionLoop(interval time.Duration) {
c.mu.Lock()
defer c.mu.Unlock()
if c.evictionRunning {
return
}
c.evictionRunning = true
c.stopChan = make(chan struct{})
go func() {
ticker := time.NewTicker(interval)
defer ticker.Stop()
for {
select {
case <-ticker.C:
c.mu.Lock()
if c.lru != nil {
c.lru.CleanExpired()
}
c.mu.Unlock()
case <-c.stopChan:
return
}
}
}()
}分布式系统需要特别注意的一点就是数据的获取。假设这样一种情形，这里总共有三台机器A、B、C，在每台机器上都运行了缓存服务。当并发请求时，如果不作任何限制，那么假设并发请求的都是同一个key，此时并不能确定这个key究竟是去请求哪一台机器？所以，当请求被随机转发后，A、B、C三台机器都可能保存同一份key的缓存，造成数据冗余。
而且，由于转发是随机的，当一个请求到来时，例如key1缓存存在于A机器种，但是这个请求却转发给了B服务，导致Cache miss。
所以，我们要思考一下这两个问题：
- 数据冗余
- 同一个
key只会由同一个机器处理
固定结点位置的操作很容易联想到hash算法，我们假设一个hash算法是hash(key) % n，其中，n指服务器的台数。对于上面这个问题，n的数量和hash(key)的值都是固定的，所以每次请求也会将请求发送给固定的机器，似乎解决了问题！
但是结点的宕机并不是人为可以预测的，假设“A"服务宕机，那么原本属于A结点的所有数据不得不去重新计算hash值，即hash(key) % 2。这样就会导致基本上所有数据都要重复计算hash值，导致数据大量迁移。
对于用户来说，结点如何分配是不感知的，但是他们就会发现似乎发现响应时间变长了！差评！
一致性哈希就是解决这个问题的！一致性hash的算法思路是：维护一个 0 ~ 2^32-1范围的一个hash值，对于请求key来说，首先计算其hash值，然后把这个查询key的任务分配给顺时针遇到的第一个结点。
如图所示"key1, key2"会被分向"A"结点， "key3, key4, key5"会被分往"B"种，"key6"则会被分向"C"中，这样即使某个服务宕机，那也是某一个区间内的值发生迁移！
可能你已经想到了，即使这样做也会导致一些问题，假设我们的hash算法很烂，也就是说A, B, C这三台机器在hash环上的分布不够均匀分散，那么也会导致数据大量迁移的问题。
如上图，"A"服务宕机后，大量结点顺时针找到的第一个服务是"B"服务，导致数据大量迁移。
一个合理的办法是给结点添加虚拟结点，我们可以维护一个虚拟地址到真实结点之间的一个hash表，这样当请求到来时，就可以达到负载均衡的效果。
可以看到，即使某个结点宕机，也只会造成一小部分数据需要重新移动！
分组设计的一个好处就是分流。对于不同的请求，例如scores, name等请求，如果没有分组设计，那么这些请求都会去请求总的机器。
在分组之后，不同的group维护一个各自的cache，各个请求之间互补打扰。
其实group可以理解为redis里面的一个db，各个group之间需要实现通信功能。
其实这也是分布式结点最重要的一部分，其调用流程是
先从本地缓存开始查找，如果
cache hit，那么直接返回数据；否则，就去调用其它在线的结点，从其它结点获取。
而结点之间通信的方式我们可以使用rpc。
在缓存中，永远有三个绕不开的话题，即缓存击穿、缓存穿透、缓存雪崩
缓存击穿指的是热点
key过期的时候出现的情况。当很多请求并发请求一个key时，就可以把这个key当作热点数据，当这个key过期后，由于cache miss，请求就会发送到数据库，而数据库往往承受不住大量的请求，造成服务宕机。
缓存穿透指的是请求缓存和数据库中都不存在的数据。当请求一个不存在的
key时，请求最后由数据库返回给缓存(空值,因为key不存在)，导致数据库宕机。
缓存雪崩指的是过期时间的设置造成的数据库宕机。当缓存中的大量数据在某一时刻同时过期，那么这些数据都要去数据库中进行查询，造成数据库宕机。
对于这三种情况，我们来分别讨论一下应对策略。
-
缓存击穿
虽然是很多请求，但是实际上大家请求的东西都是同一个
key，也就是说，只需要让第一个请求去请求即可，其它请求等待返回或者返回一个旧值即可，也就是互斥锁/singleflight方案。 -
缓存穿透
缓存穿透更像是别有用心的攻击。这类解决方法很多，例如可以对请求值加以判断，或者给数据库设置空值(
NullValue)，直接返回空值(可能会污染数据库！)。还可以使用布隆过滤器来判断请求值是否存在于数据库或缓存中。 -
缓存雪崩
缓存雪崩是大量数据过期所导致的，所以，可以将过期时间错开，或者考虑将热点数据设置为永不过期，还可以设置多级缓存，从而减少数据库压力。
使用etcd作为服务发现和服务注册。在启动项目时，可以将在线结点信息写入etcd里面，当进行结点选择时时，通过客户端与etcd建立连接，从etcd中拿到需要的服务地址，然后返回客户端。
这个项目比较重要的部分本人已经讲解完毕，更多细节都藏在代码中，欢迎大家讨论！