Facebook地理复制的缓存

发表于 | 分类于

6.824 2020 Lecture 16: Scaling Memcache at Facebook

Scaling Memcache at Facebook, by Nishtala et al, NSDI 2013

为什么读这篇论文？

  • 实践论文，并非设想和方法
  • 三个方式：
    • 最开始就没很关心一致性的警告
    • 从现有的软件看，有超高的容量，这是一个令人印象深刻的故事
    • 性能与一致性之间的根本斗争
  • 我们讨论它的设计，而非它的成功

当有更多用户时，网址要怎么处理？ 典型的进化史：

  1. 单个web服务器 + 应用 + DB
    • DB提供持久化、故障恢复、事务、sql
    • 应用查询DB，格式化html
    • 但是，随着负载提高，应用将消耗更多cpu资源
  2. 多台web FEs，一个DB
    • 易于改变，因为web服务器+app已经和存储分离了，
    • FE是无状态的，所有公共资源（并发控制）通过DB
    • 无状态：每个FE都能无差别的处理请求，即使一台挂了也没事
    • 但是，随着负载提高，需要更多FE，很快单个DB服务器就会成为性能瓶颈
  3. 多台FEs，DB集群
    • 通过key划分数据分区，app通过key（比如user）选择DB服务器
    • 好的数据分布，可以获得好的并行度
    • 糟糕的情况：跨分区的事务和查询可能做不到，很难完美地划分数据分区
    • 但是，DB是慢的，即使是读操作，为什么不缓存读请求呢？
  4. 多台FEs，多个缓存做读操作，多台DB做写操作
    • 性价比高的重读的情况，memcached比DB快10倍，memcached只是操作内存中的hash表，非常快
    • 复制的DB操作，memcached会失去同步
    • 脆弱的缓存命中率容易造成DB过载

（下一个瓶颈是DB写操作——很难解决）

facebook框架一览

许多客户、好友列表、状态、推文、喜欢、照片的数据

更新/一致性数据非准确的，人可以容忍

高负载：每秒10亿操作，相当于一个DB服务器的1w倍的吞吐量

多数据中心（只少有东部、西部海岸）

每个数据中心——region：

  • 真实的数据在Mysql数据库做分片
  • 缓存层（mc）
  • web服务器（缓存的客户端）

每个数据中心的数据库包含全量的备份 西海岸是primary，其他都是secondary备份（基于Mysql的异步log备份）

FB的应用如何使用mc？Figure1

FB用作mc做“旁观”（look-aside）的缓存

  • 真实数据在DB
  • 缓存的值应该和DB的一样

读：

1
2
3
4
5
    v = get(k) (computes hash(k) to choose mc server)
    if v is nil {
      v = fetch from DB
      set(k, v)
    }

写：

1
2
3
    v = new value
    send k,v to DB
    delete(k)

应用需要检测mc和DB的操作，而mc是不直接和DB通讯的

mc里存的是什么？ 论文没有涉及到，可能是userID -> name; userID -> friend list; postID -> text; URL -> likes 数据来自数据库查询

旁观缓存比看起来要复杂——一致性，论文尝试去整合相互隔离的存储层

缓存时重要的：并不是为了减少客户可见的延迟，而是主要为了避免数据库承受高负载

人类用户可以容忍适度的脏读，虽然脏读也是令人头疼的问题:

  • 想要避免无限的旧数据（比如，丢失了一个delete()）
  • 要能读到自己写的
  • 更多的缓存，就会有更多的旧数据出现

大量的扇出，就可以并行的获取数据，内部阻塞

首先谈性能：论文主要谈论的是避免旧数据，但是旧数据的解决只和性能设计向矛盾

性能源于多台机器的并行，多个活跃用户，多台web服务器（clients），两个基本的并行策略：分区和复制

分区和复制会给mc带来吞吐量的提升吗？ 分区：把key分到不同mc的服务器 复制：把clients分到不同mc的服务器 分区：

  • +加大内存利用率（拷贝每个k/v）
  • +没有热点key将表现良好
  • -每个web服务器都要和多台mc通信（可能过载） 复制：
  • +支持热点key
  • +更少的TCP连接
  • -可以缓存的总数据量少了

性能和区域（Sec5）

[diagram: west, db primary shards, mc servers, clients | east, db secondary shards, … feed from db primary to secondary ]

Q：每个区域都是完整的副本，有什么作用？

  • 减小用户访问的RTT（东海岸、西海岸）
  • 本地读很快，从本地的mc或DB读（但是写是耗时的，因为要发给primary）
  • 可能热点副本是网站失败的主要原因

Q：为什么分区用户的数据要跨区域呢？ 比如为什么东海岸的用户数据不放到东海岸？那就不需要复制了，可能硬件成本能减半， 因为：社交网络，不总是局部的，要对一些功能支持，比如e-mail

Q：即使所有的写操作都要发到primary区域，性能也没问题？ 写操作比读操作少得多 发到primary耗时100ms，对人类用户并不是很长 用户不需要等待写操作的效果全部完成，比如删除所有旧缓存

一个区域的性能（Sec4）

[diagram: db shards, multiple clusters, each w/ mc’s and clients ]

每个区域有多个mc的集群 这里的集群，就是一组mc缓存服务器，缓存所有数据，也就是一个副本

为什么每个区域都有多个集群？ 为什么不把服务器都加到一个集群呢？

  1. 加到一个进群无助于热点数据，复制对热点数据有帮助
  2. 集群的mc越多，每个client 请求更多的服务器，导致web服务器内部拥堵， client请求20~500个keys，越多的mc服务器，而请求肯定是并行的（否则总延迟就大了）， 那么返回几乎是同时回来的，导致网络交换机、NIC耗尽buffers
  3. 很难为单个大集群构建网络， 统一的client/server访问， 所以跨区域的带宽很大——成本高， 而两个集群，就是1/2的跨区的带宽

但是——复制操作对非热点项是是浪费RAM的 所有的集群共享“区域池” 非热点的对象（不需要太多拷贝） 应用软件决定向区域池放入什么 空出RAM，复制更多的热点数据

带来一个新mc集群也是一个性能问题 新的集群是0%的命中率 如果client使用它，将会使得DB受突发流量，如果是一般1%的错失率， 那添加一个新集群将错失50%的操作，也就是DB收到50倍的流量 因此新集群的client首先要从已有的集群get()，然后set()进新集群，基本的懒拷贝。 从现有的集群获得两倍的负载比从数据获得30倍要好

另一个过载的问题：雪崩 一个client更新DB和delete()一个key，许多的client的get()将错失，于是他们都从DB获取，再调用set() 这不是很好：不需要这么多DB操作的 mc给了第一个错失的client一个租约（lease） 这个租约内承诺从DB获取最新数据，然后mc告诉其他的client一会再试：“try get() again in a few milliseconds”

效果：只有一个client从DB读和做set()，其他的get()一会儿会重试和得到期望的命中

要是一台mc服务器挂了？

  • DB服务器无法处理错失——负载太高了
  • 不能把负载交给其他mc服务器——太多了
  • 不能重新数据分区——太耗时
  • Gutter——空闲mc服务器的池，client在mc挂了访问它
  • 过一会，失败的mc将被替换

问题： 为什么client不发生invalidate给Gutter？ 我的猜想：可能有双重delete()的麻烦，会发送很多delete()给小的Gutter池，因为每个key都可能再gutter池中

重要的实践网络问题：

  • n^2的TCP连接状态太多，因此client的get()用的UDP
  • UDP不是可靠和按顺序的，因此client的set()用的TCP，mcrounter减少n
  • 每个packet一个请求并非很有效（对于TCP、UDP），每个packet的头部（比如中断）占比大， 因此mcrounter会把一组请求塞进一个packet中

现在来谈一致性

他们的一致性目标是什么？

  • 写操作是直接到primaryDB的，并带有事务，因此写是一致性的
  • 那读操作呢？
  • 读并不总是能看到最新的写，比如跨集群的操作
  • 一致性更像“不超过几秒旧数据”，也就是最终一致性
  • 写操作能看到他们自己的写操作（由于delete()），读自己的写也是很重要的

首先，跨区域的DB副本如何保证一致性？

  1. 有个区域是primary的
  2. primary的DB分发更新的log给其他区域的DB
  3. secondary的DB应用log
  4. secondary的DB是完整的副本（非缓存）
  5. DB复制的延迟是可以接受的（几秒）

如何保证mc的内容和DB的内容一致性？

  1. DB发送invalidates(delete（）)给所有可能有缓存数据的mc，这是Figure6的McSqueal
  2. 写client也invalidate本地集群的mc，因为要能读自己的写

他们也有DB和mc一致性的问题

多client的DB读操作和put()进mc的竞争 或者说：是否有一条路径，按顺序更新？

这里的竞争是什么？怎么解决？

Race 1:

1
2
3
4
5
6
  k not in cache
  C1 get(k), misses
  C1 v1 = read k from DB
    C2 writes k = v2 in DB
    C2 delete(k)
  C1 set(k, v1)

现在mc是旧数据了，delete(k)已经发生了， 那么旧数据将一直存在，直到k下一次被写入

使用租约解决——C1从mc获取租约，C2的delete使得租约无效，所以mc会拒掉C1的set， 于是key仍然错失，下一次的读取，将从数据库刷新进缓存

Race 2:

在新集群warm-up时（错失时，client将从已有的集群get，并set到新集群）

1
2
3
4
5
6
  k starts with value v1
  C1 updates k to v2 in DB
  C1 delete(k) -- in cold cluster
  C2 get(k), miss -- in cold cluster
  C2 v1 = get(k) from warm cluster, hits
  C2 set(k, v1) into cold cluster

现在mc是旧数据v1了，但是delete()已经发生了， 那么旧数据将一直存在，直到k下一次被写入

通过两秒延迟（two-second hold-off），只用在新集群上：

  1. 在C1发delete后，cold mc忽略set请求两秒
  2. 那以后，delete（大概）通过DB传播给warm cluster

Race 3:

1
2
3
4
5
6
7
  k starts with value v1
  C1 is in a secondary region
  C1 updates k=v2 in primary DB
  C1 delete(k) -- local region
  C1 get(k), miss
  C1 read local DB  -- sees v1, not v2!
  later, v2 arrives from primary DB

通过”远程记号”（remote mark）解决， C1的delete标记key是remote，get错失后得到”remote”，表明C1要从primary区域读取， 来自primary区域的新数据到达后，清掉”remote”

Q：这些问题不会造成client拷贝DB数据到mc吗？ 为什么不让DB发新值到mc，这样client只从mc读即可？那么client就不会有竞争了，只是顺序写操作

A：

  1. DB一般不知道如何即使mc要的值，一般client应用代码从DB的结果计算，也就是mc缓存的内容并不等于数据库记录
  2. 会增加读自己的写操作延迟
  3. DB不知道缓存什么，以及那些是不需要的缓存

PNUTS确实采用了这种primary更新所有备份（primary-updates-all-copies）的方案

FB/mc对于存储系统设计的启示？

  1. 缓存对吞吐量是很重要，不仅仅是减低延迟
  2. 需要灵活的工具控制分区和复制
  3. 需要更好的想法，一致性地整合存储层