system design 俄罗斯大叔系列
分布缓存
client ——> web service ——> database
有一些问题：
调用db可能花很长时间，或者占用大量系统资源
→ 需要存在内存
Requirement：
Functional：
- put （key, value）
- get （key）
Non-Functional：
- scalable
- highly available（survives hardware/network failures）
- highly performance（fast）
（如果persistence很重要还要考虑持久性）
如果引入CAP， availability 被 consistency取代
local cache：
在单个服务器中实现一个容量优先的基本内存数据存储。
——> 它是个算法问题。
什么数据结构？hash
达到饱和之后，怎么移除旧数据？有很多策略like LRU
但是单hash表无法实现，意味着我们需要另一种数据结构来跟踪何时使用过什么。
用常量时间复杂度增删的队列：双向链表
distributed world
有多台主机，每个的cache只存一部分，called shard 分片
分布式缓存集群
隔离cache环境，cache和service不share memory和CPU
可以自行scale
可以被多个services利用
选硬件灵活
协同定位缓存
不需要单独集群，节省成本
service和cache同时scale
调用cache进程用TCP 或 UDP
如何决定调用哪个shard：
简单方法：hash 求mod —> 无法扩展
进一步：用一致性哈希
👆 知道了怎么put和get，但是谁负责？：
cache client
小型轻量级库，与服务代码集成，负责缓存主机选择.
- 知道所有缓存服务器,
- 所有 client都应该有相同的列表
- 按序存储缓存主机列表（用于快速主机查找）
- 二分搜索binary search找到server
- 使用 TCP 或 UDP 协议与server通信
- 如果缓存主机不可用，客户端会继续进行，就像缓存未命中一样。
client端最重要【cache server list】
如何创建维护和共享cache server list
第一种：
把host存到一个file里，然后通过一些持续部署管道deployment pipeline把它们部署到主机，像chef、puppet等。
pros cons：简单，但不灵活。列表更改的时候就要全重新部署
第二种：
保留这个file，但是把它放到共享storage里like S3，并让service定期轮询文件.
要引入一个守护进程，在每个servers上运行并几分钟轮询一次这个storage
pros cons：仍然需要手动维护文件，有更新时就更改并update到storage里
第三种：
使用单独的配置中心configuration service，来发现cache hosts并监控它们的健康
每个server在configuration service上自己注册，并给它定期发送心跳。periodically。
心跳一来就注册。心跳停了就注销。
每个client都从这个配置中心获取server list
pros cons：难，运营成本高operational cost，但自动维护
总结：
为了在内存存更多数据：分片，并将每个分片放在自己的服务器上。
每个缓存客户端都知道所有缓存分片。
缓存客户端使用一致的哈希算法来选择一个分片来存储和检索特定的缓存键。
高性能否？yes：
LRU：常数时间淘汰。binary search：logN查找。connect：TCPUDP
总之就是快
可扩展性？yes:
可以轻松创建更多分片
（分片常见问题：hot）
高可用？无
如果shard挂了，这个分片所有的data就没了
使用：replication
replication:
两类复制协议：
① gossip, epidemic broadcast trees, bimodal multicast. 支持最终一致性
② 2 or 3 phase commit, paxos, raft, chain replication. 支持强一致性
keep it simple：使用主从复制
一主两从
每次 主master和从replica断连时，从都会尝试重连
从位于不同的数据中心，防止一个中心故障
主可以读写，从只读
因为对缓存分片的调用分布在不同的node，所以处理热分片要容易的多
可以通过添加更多的只读副本来扩展
leader如何产生：
两种选择：
① 用一个单独组件 就叫configuration service
它负责监控主和从，以及故障转移，如果leader不work就重选一个
它本质就是个分布式服务，通常由奇数个节点组成，为了更容易实现仲裁quorum。节点位于独立机器上，高可用。相互之间使用TCP通信。
可以用zookeeper 👆 or Redis Sentinel
② 在cache集群中选举
但是还不够高可用。复制数据时数据还有可能丢失。但是可接受，主要是要快。
other thing：
consistency：
①异步复制时
②client有个不一样的service list
可用同步解决，但是会增加延迟
data expiration：
LRU：但是当不满时，有些items可能待很久。——>引入存储时间属性。
两种方式清除：
① 被动，访问时如果发现过期就丢掉
② 主动，创建一个定期运行的维护栈维护
如果数据量很大，无法遍历，就使用一些随机算法。
local and remote cache：
两个都用，本地cache没找到，就启用分布式cache
不用两个都处理，可用在client内部实现对local cache的支持。
so在创建缓存客户端实例时，我们还构建了一个本地缓存。
可以用LRU缓存或者知名第三方缓存like guava实现
security：
一般不将缓存服务器直接暴露给 Internet
so应该使用防火墙来限制对缓存服务器端口的访问，并确保只有经过批准的客户端才能访问缓存。
client还可以在将数据存储在缓存中之前对其进行加密，并在输出时对其进行解密。但是要考虑性能
Monitoring and logging:
对分布式cache很重要
monitor指标：number of faults while calling the cache, latency, number of hits and misses, CPU and memory utilization on cache hosts, network I/O.
cache client：
职责很多：维护缓存服务器列表、选择一个分片以将请求路由到、处理远程调用和任何潜在的故障、发出指标。
可以简化：
①引入代理，位于client和service之间，负责选shard
②由service负责选shard：client向随机service发请求，service用一致hash（or其它）重定向该请求到目的分片。Redis cluster就这样
一致哈希：
两个flaws:
①domino effect
一个service挂掉导致后面压力很大，超载，也挂掉。loop
② ⚪不能均分
虚拟节点
真总结：
单机 & LRU （本地容量有限无法扩展）→ LRU cache作为独立进程在它的主机上运行
→ 引入一致性hash分配service → 引入cache client负责将每个请求路由到特定shard
→ 为了高可用和扩展，引入主从复制 → 为了监控主从和故障转移，引入配置服务