GeeCache

golang 分布式缓存

1. 缓存之中可能存在的问题：
   1. 内存不够时怎么办？需要设置一个合理的淘汰策略
   2. 并发写入冲突怎么办？map内是没有并发保护的，对于并发的场景，比如新增，更新，删除等修改操作需要加上Go锁
   3. 单机性能不够时怎么办？单台计算机的性能是有限的，随着业务量增加，单台机器容易遇到瓶颈。
      • 水平扩展：利用多台计算机的资源，并行处理就需要能支持分布式
      • 垂直扩展：增加单台计算机的资源，从而提高系统的性能，但是硬件的成本和性能不一定是成线性变化的。
2. GeeCache是什么？它是一个模仿groupcache的分布式缓存系统

1：淘汰策略：

1. FIFO，LFU，LRU：

   1. FIFO：先进先出，实现方法是创建一个队列，新增记录就添加到队尾，内存不够时，淘汰队首。但是一些比较早加进来，但是又访问得比较频繁的记录就会被频繁地加进去缓存内，导致缓存命中率低
   2. LFU：最少使用：淘汰掉缓存中访问次数最少的记录，但是它需要维护一个按照访问次数排序的队列，它受历史数据的影响很大。（如果一个数据以前访问很多次，现在不再被访问，就很难被淘汰）
   3. LRU：最近最少被使用：它认为，一个数据最近被使用了，那么未来也更容易被使用。它维护一个队列，一旦有数据被访问了，就会被调到队尾，然后淘汰队首。

2. LRU核心数据结构：

   ​

   1. 绿色的是map，查找和插入的复杂度都是O(1)
   2. 红色的是双向链表实现的队列，移动，插入和删除的复杂度都是O(1)
   3. 字典的定义是map[string]*list.Element，key是字符串,value则是链表中对应的元素指针，maxBytes是最大内存值，nbytes是目前使用的内存，链表中保留了每个值对应的key值。

3. 查找功能：首先找到对应的双向链表的节点，然后再将节点移动到队尾。

4. 删除功能：就是LRU，首先移出最近最少访问的节点（队尾）

5. 插入功能/更新功能：如果键存在，就更新对应节点的值，并且移到队尾，不存在则在队尾添加新节点，然后在字典中添加key和节点的映射关系，更新内存大小。

2：互斥锁

多个协程同时读写一个变量时，在并发度很高时就会发生冲突，synv.Mutex就是Go提供的一个互斥锁，当一个goroutine获取一个锁时，其他协程就会阻塞在Lock方法上，一直到调用UnLock为止。使用了互斥锁封装get和add方法

回调函数：如果缓存不存在的话，就应该使用一个回调函数来获取数据，如何从源头获取数据，是用户决定的事情。

回调函数是一个接口型函数，调用时就能够传入函数作为参数。实现的接口就是调用自己获得结果

Group：如何和用户之间进行数据交流？Group内封装了一个cache，和回调函数，Group只用r锁，因为不涉及其他的写操作。Group主要的操作是，从cache之中查询缓存，有的话就放回缓存值，没有的话就调用load方法，也就是回调函数获取源数据，并且要把源数据添加到缓存中。

3：HTTP

1. 创建server调用ServeHTTP方法来启动HTTP服务，服务端HTTPPool有两个参数，一个是用来记录IP和端口，一个则是用来记录网址的前缀，比如API接口的前缀。
2. 实现逻辑比较简单，首先判断前缀是否是basename，然后就是groupname和key值， 从而返回value.

4: 一致性哈希

如果有分布式缓存的话，当一个节点收到请求时，它上面并没有存储缓存值，那么应该去哪里获取数据？那么，我们需要的就是把相应的Key值和对应的节点绑定起来。

缓存雪崩：一瞬间缓存值全部失效，需要重新在数据源获取数据，造成数据库请求量变大，压力变大，造成雪崩。这经常是因为缓存服务器坏了，或者是缓存设置了相同的过期时间导致的。

一致性哈希就是将key映射到2^32的空间里，把所有的数字组成一个环，首先计算机器的哈希值放到环上，然后再计算key的哈希值，也放到环上，从key值开始，顺时针找到的第一个节点，就是应该选取的机器。因此，新增或删除结点时，就只需要重新定位该节点附近的一小部分数据，而不需要重新定位所有节点。

数据倾斜问题：如果服务器节点过少，就会导致数据分布不均匀，因此引入了虚拟节点，一个真实节点会对应多个虚拟节点，可以扩充节点的数量。

实现，传入真实节点的值，对应创建多个虚拟节点，map 虚拟节点对应真实节点，然后放到环上排序，再计算key的哈希值，找到大于它的第一个哈希值，通过map表得到真实节点的值，就完成了。

6：防止缓存击穿

1. 缓存雪崩：同一时间缓存全部失效
2. 缓存击穿：一个缓存的Key值，在缓存过期的那一刻，有大量的请求对它进行，就会瞬时造成DB请求量大，压力增加的情况。
3. 缓存穿透：查找一个不存在的数据，就会每次都去数据库找，又找不到，导致DB穿透。

怎么样令并发情况下多个对同一个Key发出的请求，只发出一次呢？

sync.waitgroup

实现一个singleflight的包，会记录下相应的Key的请求(call)，发起请求时会先加锁，如果key内有对应的请求了，就会一直等待c.wg.Wait()等待到查询的函数结束为止，然后再返回结果。当请求结束，就删除掉map内的记录。

也就是一堆人等一个人干完活。

// Overall flow char										     requsets					        local
// gee := createGroup() --------> /api Service : 9999 ------------------------------> gee.Get(key) ------> g.mainCache.Get(key)
// 						|											^					|
// 						|											|					|remote
// 						v											|					v
// 				cache Service : 800x								|			g.peers.PickPeer(key)
// 						|create hash ring & init peerGetter			|					|
// 						|registry peers write in g.peer				|					|p.httpGetters[p.hashRing(key)]
// 						v											|					|
//			httpPool.Set(otherAddrs...)								|					v
// 		g.peers = gee.RegisterPeers(httpPool)						|			g.getFromPeer(peerGetter, key)
// 						|											|					|
// 						|											|					|
// 						v											|					v
// 		http.ListenAndServe("localhost:800x", httpPool)<------------+--------------peerGetter.Get(key)
// 						|											|
// 						|requsets									|
// 						v											|
// 					p.ServeHttp(w, r)								|
// 						|											|
// 						|url.parse()								|
// 						|--------------------------------------------