论文笔记：[OSDI'16] Slicer: Auto-Sharding for Datacenter Applications

发表于 更新于 分类于

Slicer [1] 是 Google 内部支持应用按照 Sharding 的方式进行扩展的，与 RPC 框架集成的基础组件。论文中提到其对比其他通用 Sharding 框架论文的独特之处有：

  1. 控制侧和数据侧分离

  2. 高效的负载均衡算法，在尽可能减少 key churn 的情况下提供很好的负载均衡效率

  3. 提供一些在大规模生产环境下的 evaluation

个人认为其独特之处有：

  1. 将存储系统经常需要解决的 Sharding 问题独立出一个基础组件集成到 RPC 框架中，这个想法本身就比较有意思

  2. 在 Sharding 的基础上可以做一些比较特别的事情，例如：

    1. 指导应用进行 Sharding 的重分布（类似于 rehashing）

    2. 支持 Sharding 的分裂与合并

    3. 屏蔽失效的节点，并且指导应用将失效节点的负载转移到健康节点上继续提供服务

    4. 为热点增加副本数以承载更高的读负载（论文中提到了这个想法但是貌似没进行实现）

    5. 提供 key range 粒度的租约控制（论文中使用租约控制来保证这个 key range 同时至多只存在一个服务提供者，但是并没有在生产环境中使用这一功能）

基本思路和整体架构

Slicer 整体上是在 Centrifuge [2] 上进行改进，总体有 3 个主要部分，见Abstract Slicer architecture：

  1. Slicer Service: 系统核心部分，负责控制 Shard 的分布并提供查询

  2. Clerk: 嵌入到客户端 RPC 库中的部分，负责和 Slicer Service 进行交互，指导 RPC 请求的路由

  3. Slicelet: 嵌入到服务器端的部分，负责和 Slicer Service 进行交互，接受 Slicer Service 对于 Shard 重分布的控制

Abstract Slicer architecture
Figure 1. Abstract Slicer architecture

这里的核心思想在于由 Slicer Service 控制 Logical Shard（论文中为 key range）和 Physical Server（论文中称为 task）之间的映射关系，并且根据反馈信息进行适当的调整。

出于 Availability 的考虑，Slicer 对于 Slicer Service 进行了进一步的拆分，见Slicer backend service architecture：

  1. Assigner: 负责调整和控制 Logical Shard 和 Physical Server 之间的映射关系

  2. Distributor: 负责查询（被动分发）Assigner 的控制结果

  3. Backup Distributor: Assigner 挂掉时的后备方案

  4. Store: Assigner 背后的可靠存储

Slicer backend service architecture
Figure 2. Slicer backend service architecture

这样的另一个额外的好处是，如果 Client 和 Assigner 在不同的 DataCenter 中的话，可以将 Distributor 和 Client 部署在同一个 DataCenter 内，节省跨 DataCenter 流量，提升效率（Distributor 自带缓存）。

另一种常见的跨 DataCenter 策略是使用传统的 SLB 进行跨 DataCenter 的中转，见Centrifuge cross datacenter。

Centrifuge cross datacenter
Figure 3. Datacenter applications are often divided into multiple component services, and servicing clients requests frequently requires communicating with multiple such services. Centrifuge is designed to replace only the internal network load balancers used by the component services.

负载均衡

Slicer 使用 RPC 的 Metrics 数据作为输入，对 Shard 进行负载均衡评估，然后进行调整。从之前的架构可以发现，产生一个调整（Assignment）到生效是最终一致的。

Slicer 的负载均衡考虑了以下几个方面：

  1. 使得尖峰负载尽可能低

  2. 在调整的过程中，减少 key churn 的情况

  3. key range 的合并和分裂

但是不考虑根据负载增加一些 Logical Shard 的副本数量，或者自动调整 Physical Server 的资源。

我们首先考虑怎么抽象负载指标的问题。在 Slicer 中，使用 Load imbalance value 这一经验指标抽象整个系统的负载均衡状况。定义一个 Physical Server 的 load 为其所负责的 Logical Shard 数量，则 Load imbalance value 为整个系统中的最大 load 与平均 load 的比值。

个人觉得这个经验指标看起来有点问题：

  1. 其假设整个系统的负载在 key 上是均匀分布的，实际上即便是对于哈希分布的 key space 也可能是不成立的

  2. 其假设 Logical Shard 的大小是一致的，但是后面又会对 Logical Shard 进行分裂与合并

然后是怎么抽象 key churn 的问题。在 Slicer 中，使用一轮调整产生的 key 重分配的比例作为 key churn 的指标。Slicer 对于 CPU 负载较低的 Physical Server 不会进行 key range 的重分配，以此避免过度优化产生的 key churn 开销。

Slicer 进行负载均衡的算法也是经验得出的，里面的一些 threshold 的具体 number 也是经验得出的，在此不再赘述。

强一致性

Slicer 通过租约（Lease）机制实现强一致性（这里强一致性指同一时刻至多只有一个 Physical Server 对 key 提供服务）。需要注意的是租约机制蕴含了时钟对齐的要求。显然我们没办法对每个 key 提供租约管理，一个简单的思路是对 key range 粒度进行租约管理。但是 Slicer 更进一步的可以只使用至多 3 个 Chubby locks 完成租约管理，并且由于租约管理是由 Chubby 进行的，所以即使 Slicer 挂掉也不会影响用户服务。

  1. job lease: 首先需要一个锁来保证同一时刻内只有一个 Assigner 负责整个分配

  2. guard lease: Assigner 会为每一轮分配生成一个租约，只有得到租约许可的 slicelet 才可以提供服务，这样当分配更新时，持有过期信息的 slicelet 就会停止提供服务，避免因信息不同步导致的多个 slicelet 对同一个 key 提供服务的情况

  3. bridge lease: 如果只使用 guard lease，则在每一轮分配期间，都会导致全服务的 guard lease 整体失效。但是显然每一轮分配只改变了一小部分 key range 的分布，其他没有发生变化的部分不应该受影响。因此对这部分没有变化的分配，引入一个 bridge lease，使其不受 guard lease 失效的影响。

个人觉得这个想法还是比较有意思的，相当于 Slicer 既可以控制分配，也可以控制选主，这样只要用户自己实现 replication 机制，就可以很容易的做一个有状态服务了。

Slicelet 中和强一致性相关的 API 如下：

Opaque getSliceKeyHandle(String key);
boolean isAssignedContinuously(Opaque handle);

使用的方法类似于这样（参考了 [2]）：

boolean Subscribe(String key, String address) {
  // (1) Check that this is the correct node
  Opaque handle = getSliceKeyHandle(key);
  if (handle == null) return false;

  // (2) Perform arbitrary operation on this state;
  // store lease number with any created state
  // in this case, simply add subscription
  this.subscriptionLists[key].add(address);

  // (3) Check that lease has been continuously held;
  // if so, return result
  if (!isAssignedContinuously(handle)) {
    // Rollback subscription
    this.subscriptionLists[key].remove(address);
    return false;
  }

  // Commit subscription
  return true;
}

与一致性哈希的比较

一致性哈希的一个大问题是其哈希算法固定，如果发现数据分布不符合哈希算法的预设的话，几乎没有任何机会进行调整。这在负载均衡的场景下就显得不是那么合适。另一方面，如果想要支持非对称副本数（例如有的 key range 只有 2 副本，但是有的热点 key range 有 200 副本），一致性哈希也是一个很大的限制。

参考文献

  • [1] ADYA A, MYERS D, HOWELL J, etc. Slicer : Auto-Sharding for Datacenter Applications[J]. Osdi, 2016: 739–754.

  • [2] ADYA A, DUNAGAN J, WOLMAN A. Centrifuge: Integrated Lease Management and Partitioning for Cloud Services[C]. NSDI’10 Proceedings of the 7th USENIX conference on Networked systems design and implementation. USENIX Association, 2010.