平衡的背景

利用冗余(replicas)来降低尾延迟(tail latency), 以及它和 Paxos 共识, load / sharding 之间的关系;
核心是: 复制本来是为了容错/可用性, 但你也可以把它当成"多条独立路径/多台机器"的并行机会, 用来对抗偶发慢请求;

一个 key 有多个副本(N replicas);
- 正常读: 只读一个副本
- 好处: 负载低, 便宜
- 风险: 这一次刚好遇到这个副本慢(GC, 排队, 抖动), 尾延迟就被拖垮

First idea: read from all in parallel(最直接: 全部并行读, 取最快)

做法: 同时向所有副本发 GET, 拿到第一个返回就用(其他请求丢掉/忽略);

  • 优点: 尾延迟会显著下降(你拿的是 min(response times))
  • 问题(slide 点出的): 系统负载和成本暴涨
  • 每次读都变成 N 倍 RPC
  • 平均延迟可能更好, 但整体排队更严重, 反而把系统推到更拥塞, 导致更差的 tail

所以"全并行"通常太贵, 只能在极少数场景用;

Second Idea: Be optimistic(第二个方案: 乐观)

做法:
1. 先只发给一个副本(便宜)
2. 设一个 timeout(“我等多久算它慢”)
3. 如果超时, 再把请求发给其它副本(fallback)
权衡:
- 优点: 大多数时候只花 1 次 RPC(系统成本低)
- 缺点: timeout 设得越短, fallback 越频繁 →\rightarrow 负载升高
- timeout 设得越长, fallback 不常发生 →\rightarrow 尾延迟下降有限

所以这里的核心是一个经典 tradeoff: 更激进的超时 ⇒\Rightarrow 更低 tail, 但更高系统负载;

Third Idea: Hedge Your Bets(第三个方案: 对冲/投保: hedged requests)

这是业界很常用的尾延迟技巧(Google/Meta 等都用);

做法(比"乐观"更平滑):
1. 先发给一个副本
2. 不要等到很长的 timeout, 只等一个较短的 delay(比如 p95 的一部分)
3. 如果还没回来, 就"加注"发第二个请求给另一个副本
4. 一旦任意一个返回, 就发送 cancel 给其他副本(或忽略结果)

它介于"全并行"和"超时 fallback"之间:
- 不是一上来 N 倍开销
- 也不会等到超时那么久才补救
- 以较小额外负载换很明显的 tail 改善

Why does this work?(为什么 hedge 可行)

这页在强调一个网络/系统现实:
- 如果副本在同一个 datacenter:
- 到数据中心的网络 RTT 很低且稳定(比如 <1ms)
- 真正的慢通常来自 数据中心内部: 排队, 调度, GC, 磁盘抖动, 量级可能是 10ms 甚至更多
因此你可以把 hedge delay 设成几毫秒:
- 如果第一台真的卡住了, 几毫秒后补发第二台通常能救回来
- cancel 消息也大概率能赶在第二台真正做很多工作前到达(尤其是第二台还在排队)

简单说: 慢主要来自服务端排队/抖动(10ms 级), 而网络传输很快(<1ms 级), 所以"短延迟后补发"很赚;

The key insight: Affirmative statements(关键洞见: 肯定式信息更好用)

这页在讲一个"控制系统"风格的观察:
- "absence of something(没收到)"是一种很弱的信号, 你不知道是它真慢, 丢包, 还是对方崩了
- "presence of something(收到明确消息)"是强信号, 比如 cancel, ack

对应到前面两种方案:
- optimistic 依赖"没收到响应 →\rightarrow 推测慢 →\rightarrow fallback" 这是基于缺失信息的推断
- hedging 引入了明确的 cancel(以及更早的第二条请求) 更像"用确定动作覆盖不确定性", 而不是等待缺失触发

这页的意思不是说 optimistic 不行, 而是说明: hedging 设计得更"可控";

Caching Strategy

透写缓存 (Write-Through Cache)

  • 机制: 客户端从缓存读取, 如果未命中则从数据库(DB, 持久状态)读取;在写入操作中, 数据库和缓存都会同时更新;
  • 问题: 这种模式很快就会导致缓存成为瓶颈;
  • 复杂性: 为了平衡负载, 缓存需要被复制;但要保持所有缓存副本与数据库一致, 数据库需要在写入时通知并使其他缓存副本失效或更新;由于大规模系统(如 Facebook)使用多种数据库(Haystack, MyRocksDB, Cassandra)且独立维护, 这种跨系统协调非常复杂;

旁路缓存 (Look-Aside Cache)

这种模式通常用于 Facebook 的 Memcache 等系统, 解决了透写缓存的瓶颈问题, 但引入了新的并发挑战;

  • 写入 机制: 客户端首先更新数据库(DB), 然后 从缓存中删除(delete) 对应的旧值;
  • 读取 机制: 客户端首先尝试从缓存读取;如果未命中(miss), 则从 DB 读取, 然后将新值写入缓存;
  • 为何 删除 而非更新: 写入时选择删除而不是更新缓存是为了避免竞态条件(Race condition);
    • 例如, 客户端 C1 和 C2 并发更新 DB, 如果 C1 较慢地更新了缓存, 可能会用一个旧值覆盖 (overwrite) C2 写入的较新值;
    • 删除操作确保了下一次读取缓存时, 一定会未命中, 从而迫使客户端从 DB 读取最新的数据并重新填充缓存;

咨询锁解决并发问题 (Advisory Locks / Leases)

在旁路缓存模式下, 需要解决多个客户端同时未命中缓存导致的并发问题, 特别是当客户端并发地访问数据库时; Advisory Lock (在上下文中也称为租约 Leases) 是用来解决这个问题的方案;

  1. 读取客户端的行为
    • 首次未命中: 客户端尝试从缓存中获取值, 未命中;
    • 请求锁: 作为未命中操作的附带效果, 客户端请求一个咨询锁(advisory lock);
    • 获取锁: 如果锁被授予("首次未命中"的客户端获得 “临时优先权”), 该客户端继续从数据库读取, 然后尝试将检索到的值添加到缓存中;
    • 未获得锁: 如果锁未被授予, 说明有其他客户端持有该锁;该客户端会 等待一小段时间, 然后重试;
  2. 写入客户端的行为
    • 写入数据库: 在写入新值时, 客户端首先写入数据库;
    • 删除与破锁: 客户端向旁路缓存发送一个 删除(delete)请求, 这个删除操作会打破 (breaks) 已被授予的咨询锁;
    • 拒绝安装: 如果一个正在进行读取的客户端(它持有一个现已被打破的咨询锁) 尝试将它从 DB 中读取的值安装到缓存中, 那么这个被添加的值会被 拒绝(rejected);
    • 最终填充: 下一个尝试读取该键的客户端将负责填充新的正确值;

Thundering Herd (惊群效应)

惊群指: 某个热门 key 突然过期/被删除/刚上线缓存为空, 成千上万请求同时 miss →\rightarrow 全去 DB →\rightarrow DB 雪崩;

没有 lease 的情况下
- 每个客户端都 miss →\rightarrow 都去 DB →\rightarrow 都写 cache(重复工作 + DB 过载)
- 即使 cache 写很快, 也救不了 DB 的短期尖峰
有 lease 的情况下
- 只有一个客户端获得 lease 去 DB 重建
- 其他客户端等它把 cache 填好(或者短暂退避重试)
- DB 压力从 “QPS 数万” 变成 “1 次重建 + 少量重试”, 尖峰被削平

这极大地降低了数据库负载, 消除了因负载引起的延迟尖峰, 并使缓存填充速度更快

Lease 的存在相当于给所有客户端加了一个等待机制，防止疯狂抨击 DB