Question

1 缓存为王

页表(page table)和内存管理单元(MMU)负责将虚拟地址转化为页的物理地址。 页表负责记录哪些是物理页，哪些是虚拟页，以及这些页的页表条目(PTE)。 MMU是一个物理硬件，负责进行虚拟地址到物理地址的翻译，翻译过程中需要从页表获取页的 PTE，MMU也会使用翻译后备缓存(TLB)的缓存页号。

系统性能指标：响应时间、延迟时间、吞吐量，并发用户数和资源利用率等

浏览器缓存

Cache-Control/Exires 优先级高于 Last-Modified/ETag，当本地副本根据 Cache-Control/Expires 发现还在有效期， 就不会再次发送请求服务器询问修改时间(Last-Modified)或实体标识(e-tag)了。

主流的缓存算法：

• LRU(Least-Recently-Used): 替换掉最近请求最少的对象，实际中使用最广。cpu缓存淘汰和虚拟内存效果好，web应用欠佳
• LFU(Least-Frequently-Used): 缓存污染问题(一个先前流行的缓存对象会在缓存中驻留很长时间)
• LRU2
• 2Q(two queues)。多级缓存
• SIZE：替换占用空间最大的。也会有缓存污染
• LRU-Threashold：不超过某一个size 的，其他与 LRU 相同
• Log(Size) + LRU: 替换 size 最大的对象，当size相同按 LRU 替换
• Hyper-G: LFU 改进版，同时考虑上次访问时间和对象 size
• Pitkow/Recker: 替换最近最少使用对象，除非所有对象都是今天访问过的。如果是，替换调最大的对象
• Lowest-Latency-First: 替换下载时间最少的，最小化平均延迟
• Hybrid Hybrid: 保留效用最低的会被替换掉
• Lowest Relative Value(LRV): 替换保留效用最低的
• Adaptive Replacement Cache(ARC)
• Most Recently Used(MRU)
• First in First out(FIFO)
• Random Cache

2 分布式系统理论

2.3 分布式系统理论

CAP：一致性、可用性、分区容忍性

Paxos: 解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。 《从Paxos到ZooKeper》 paper: paxos-make-simple.pdf github.com/papers-we-love

2PC: 2阶段提交协议。阻塞型协议，如果事务协调器宕机，某些参与者无法解决他们的事务。

3PC：增加了 preCommit

Raft：选举过程，然后在选举出来的领导人带领进行正常操作。

Lease机制：Lease 是由授权者授予分布式环境一段时间内的承诺

脑裂问题：双主脑裂。设置仲裁（第三方检测服务器monitor）

5 Memcached 集中式缓存

特性：

• 协议简单：基本文本或者二进制协议
• libevent 事件处理
• 内存存储空间
• 客户端分布式。客户端实现，服务端并不支持分布式

不足：

• 无法备份（易失）。只能通过持久化解决
• 不支持条件查询
• 没有内置安全机制
• 单点故障 failover。可以通过主从解决

内存管理: Slab Allocation。按照预先规定大小，将分配的内存分割成各种尺寸的块(chunk)，并把尺寸相同的块分成组(chunk集合)， 分配的块可以重复利用，不释放到内存

• Page: 分配给 Slab 的内存空间，默认 1 MB
• Chunk： 用于缓存记录的内存空间
• Slab class： 特定大小的 chunk 组

典型问题： - 容量问题 - 服务高可用(HA) - 扩展问题

两种过期机制：

• lazy expiration: get时候查看是否过期，不直接监视
• LRU

哈希算法：任意长度的输入，通过散列算法，变换成固定长度的输出。 使用一致性哈希很好解决动态环境下的使用 Memcached 扩缩容带来的大量数据失效的问题。

热点问题： 如果是超高访问的热点数据 - 通用解决思路就是 client 端做本地的 LocalCache（放到进程缓存里），省去了缓存服务器IO。 - 通过多个 key_index 分散到多个机器上，减少针对一个server 的超高访问。

缓存与数据库的更新问题： 更新数据库成功，删除cache失败。别把缓存当存储，分布式架构一切都可能fail。

命名空间：通过前缀等来模拟

CAS(Check and Set): 解决原子操作问题。比如用户操作一个key对应的value，需要保证操作当中，value不允许被其他访问操作， 如果被操作过，则操作失败。 首先用 gets 指令获取 key-value 及 key 对应 value 的版本号version，然后操作产生新的value；最后使用 CAS 指令重新提交key-value，并附带之前的版本号version。服务端判断CAS操作中的version不是最新，认为key被改，本次CAS操作失败。

客户端：协议封装，连接池，sharding，故障转移，序列化

周边工具： - The innoDB memcached Plugin - Twemcache - Twemproxy: 快速的单线程代理程序 - MemcacheDB/MemcacheQ/Mcrouter - Tokyo Cabinet: DBM 数据库

6 Memcached 周边

可扩展、高可用、可维护性

Twemcache

Twemproxy

单线程代理程序，支持memcached ASCII 协议和Redis 协议。c语言编写，通过引入一个代理层，将应用程序后端多个redis或者membcached 实例进行统一管理。应用程序只需要在Wwemproxy上进行操作即可。

• 支持失败节点自动删除
• 支持设置Hash Tag
• 保持与缓存服务器长连接，减少直接连接数
• 支持多种hash 算法
• 支持状态监控
• 连接复用和内存复用

LVS(keepalived,双节点热备保证LVS高可用) -> Twemproxy -> cache(缓存自身高可用)

7 Redis 探秘

数据类型

Redis(REmote DIictionary Server): string/list/set/hash/sorted set

String: 能表达字节串、整数、浮点数。redis 自动识别精度、值域范围。实现为 int/sds

List :存储string序列。内部实现为 linkedlist/ziplist。 linkedlist 双链表实现。 ziplist 列表结构，连续内存。移动复杂度较高

Hash: 不能嵌套。智能是string 能表达的内容：整型、浮点型、字节串。实现 hashtable/ziplist

Set: intset(只包含整形元素时)/hashtable。intset 使用二分查找(logn)

Sorted Set: ziplist/ skiplist+hashtable skip查找O(n)

客户端

交互协议：

• 网络模型(TCP)
• 序列化协议: inline command/simple string/bulk string/error/integer/array

请求响应模式：

• 串行化
• pipeline实现

事务模式：原子化。不同事务的命令之间不会交叉。一次执行一个队列里所有请求，不会执行其他客户端命令。 非一致性：如果EXEC 中有一条执行请求失败，后续继续执行。只在返回客户端的array型 响应中标记这一条出错结果。 事务只读：每个请求的参数取值不能依赖上一个结果 乐观锁的可串行化事务隔离：通过watch机制实现乐观锁解决一致性问题。

为了实现可串行化隔离级别：Redis 使用者需要做到三点约束

• 事务只读操作需要先于写操作（批量操作中执行度操作没意义）
• 所有写操作的执行不依赖其他写操作的执行结果
• 乐观锁避免一致性问题，对相同key 的并发访问频繁时候事务成功率低

脚本交互模式：

• 每个提交给服务器的端的 lua_script_string 都会在服务端的 lua_script_map 中常驻，除非显示 FLUSH 命令清理
• script实例的主备间可通过script重放和cmd重放两种方式实现复制
• 之前执行过的script后续可以直接通过它的sha指定而不用再向服务器发送一边script内容

持久化：

• 全量: SAVE/BGSAVE
• 增量: AOF

分布式 Redis

单实例节点：数据量伸缩、访问量伸缩、单点故障

分布式方案：

• 水平拆分：每个分组处理业务数据的一个子集。原则上没交集
• 主备复制： W+R>N
• 故障转移：需要保持多副本，位于不同节点上

水平拆分(sharding)

常用映射：

• hash
• 范围映射。key值域不确定、不可控
• hash 范围结合

请求路由

• 只读的跨实例请求
• 跨实例原子读写

主备复制

保证单点间数据一致性。有些是客户端双写，有些是存储层复制。 redis master slave. PSYNC 支持断点续传

故障转移（failover）

master故障时，slave可以成为新的 master，对外提供读写服务，这种机制称为 failover。 一种方式是使用daemon 监视redis多节点，但是没法保证daemon本身带点可用性没法保证。 如果引入多个 daemon虽然解决了其单点问题，但是不同daemon观察到master 可用状态不一样，如何决策此时master是否需要failover？ redis用多个 daemon 组成一个 集群称为 sentinel 集群，这些节点之间互相通信、选举、协商，在master故障发现、failover决策上表现出一致性。

过程：

sentinel 节点通过定期向maser 发送心跳包判断其存活状态，成为PING。 如果一个sentinel一旦发现master 没有正确响应，将master设置为『主观不可用』，随后将『主观不可用』发送给其他所有的 sentinel节点确认，如果确认的sentinel节点数>=quorum(可配置)，判断master为『客户端不可用』，随后进入failover流程。

进入failover后，最后只能有一个sentinel 节点作为failover 发起者，此时需要一个leader选举过程，选择谁发起failover。 redis sentinel 机制采用类似 Raft 协议实现选举算法。

Redis Cluster

集群拓扑结构

slotId = crc16(key) % 16384 (2**14)

9 Tair 探秘

TaoBao Pair。

一个Tair 集群主要包括 Client, Config Server 和 DataServer

10 EVCache 探秘

分布式缓存，基于 Memcached 内存存储和Spymem-cached 客户端实现

Ephemeral: 数据存储是短暂的，有自己的存活时间 Volatile: 数据可以在任何时候消失 Cache: 一个内存型键值对存储系统

12 社交场景架构进化：从数据库到缓存

社交业务示例

post, follow, timeline

16 新的旅程

缓存使用模式

• Cache-Aside: 业务代码中管理缓存。需要利用数据库比较成熟的高可用机制
• Cache-As-SoR :SOR 是记录系统，就是实际存储原始数据的系统。把 cache 当做 sor，业务代码只对 cache 操作
• Read-Through: 业务代码获取数据先从缓存获取，没有再从数据库加载，然后放入缓存
• Refresh-Ahead: 仅调用 cache 的 get 操作，通过设定数据的过期时间在数据过期时，自动从数据库重新加载数据的模式。
• Write-Through: 穿透写模式，业务代码首先调用 cache 写，实际由 cache 更新缓存数据和存储数据
• Write-Behind: 业务代码只更新到缓存数据，什么时候更新到数据库，由缓存到数据库同步策略决定

管理缓存

缓存穿透

查询不存在的 key 导致大量回源。

• 预先设定一个值，发怒 i 的时候应用可以判断出来并且决定是否回源
• key 不存在，加锁，回源，存入缓存，解锁

缓存失效

大量缓存同时过期

• 失效时间随机值，避免同时失效

淘汰算法

LRU, LFU, FIFO

• LRU 周期性批量操作导致命中率急剧下降，缓存污染比较严重。LRU-k，访问次数达到 k 次的时候才将数据放入缓存

缓存可用性

• 主备：一致性问题
• cluster 方案

数据一致性

• 最终一致性。对于时间敏感数据可以设置很短的过期时间（失效时间）
• 强一致性：InnoDB memcached 插件结合 mysql 结局缓存和数据库一致性问题

热点数据处理

• 数据预热。
  • 是否有监控机制确保预热数据都写入成功
  • 数据预热配备回滚方案
  • 评估数据量
  • 注意是否会引发数据库批量操作和慢查询问题

• 非预期热点：nginx+lua 应用内缓存（热点发现系统）
• 多级缓存：localCache
• 数据复制模式：通过多个 key_index 解决热点读问题。所有热点 key 发布到所有的 web 服务器

注意事项

• 慎用缓存当存储
• 就近原则：cpu 缓存、客户端缓存、cdn 缓存
• 并发控制手段：乐观锁、Latch、mutex、CAS 等。