Akkio: 分片再分片

OSDI '18论文阅读·可扩展的数据库分片区域管理

Posted by Donggu Ho on 2018-12-28

这学期修的分布式系统课程安排同著名的 MIT 6.824 ,主要就是上课读各个公司的分布式系统相关架构的论文,课下用 Go 进行一些 MapReduce 跟 Raft 的实现。分布式系统是个很工程的问题,需求来自于涌现的跨国互联网企业和应用,各家有各家的需求和实现细节,这大概也是这门课没有其他课程一样的系统性的知识点结构,而是以 case study 作为教授的主体的原因。讲道理的话还是非常充实的,教授每周过两篇 paper,两周一个作业 due,就是头有点冷。

虽然说课程跟的是 MIT 6.824 的骨架,但是我们教授也有考虑这门课的与时俱进,他更新替换了部分课程的内容(主要是靠后面的一些paper)安排,让我们阅读了一些更加学术前沿的东西。Final 的布置里面包括自选两篇2018年10月新鲜出炉的 OSDI 论文进行 Summary 保证网上根本什么资料都搜不到只能自己啃论文。MIT 6.824 标配的那几篇 paper 的分析总结网上到处都是,但是 OSDI 这两篇好像搜了一下中文都还没有相关结果,那辛辛苦苦啃完的论文感觉不发一下 blog 就太亏了……

背景

对于 Facebook 这样的跨国大型应用服务,其数据库必须要通过分片、分布式、多地多副本部署等方式提高用户的访问速度及实现负载均衡。一些很常见的思路是,这些公司会在全球到处开数据中心,然后对数据库表分片(shard),每个分片通常会在3个或以上位于不同区域的数据中心存有副本来保障容错;然后为了保证多地并发读写的一致性,需要其中一个副本作为主副本,其它数据中心收到访问请求后,都转发到这一副本进行处理。

在这种架构下,如果数据片的区域设置不合理,比如存储在了一个遥远的数据中心,就会导致产生大量不必要的系统内部跨数据中心通讯,而带宽就会成为瓶颈。显然,对于一些读写有明显的区域相关性的数据来说,把这些数据放在访问集中的区域会减少带宽占用和响应时间,这就是数据区域优化的基本出发点。

为什么不用 Cache

的确,在各个数据中心部署cache以减少跨数据中心的访问并加快响应是一个很常见的方案,简单粗暴有钱任性。但 cache 方案有三个主要问题:

首先,cache 的效率取决于访问的命中率。如果访问命中率太低,那么cache的存在反而消耗了更多的资源,还拉低了响应速度。根据论文的说法,cache 只有在命中率特别高(extreamly high)的情况下才适用。同时,cache方案无法提供足够强的一致性(strong consistency),这就限制了它的应用场景。另外,由于cache只能加速读操作,所以当数据的读写比例较低(如用户的在线状态)时,cache就无法起到较明显的作用。

为什么不用别的

PNUTS 这样的各个数据中心全复制方案就更简单粗暴了,但是真的太贵了。全复制意味着所有数据中心都必须存储所有的数据,那么此时分布式的意义只是提高访问速度,并不能起到减少数据管理负载的作用。通常来说,一份数据拥有三个副本已经是具有非常高的可用性/稳定性了。而且全复制意味着每次数据更新都要有请求发送到所有数据中心,这带宽谁顶得住啊……

那在数据产生的一开始就把它安排好区域不就好了吗?为什么要单独搞一个复杂的系统又迁移又统计呢?因为数据访问的区域也是会变的。用户可能满世界乱跑,以及往往会有数据中心迁移数据以错峰访问的需要。

Akkio

基于以上背景,Facebook 开发了 Akkio 进行分布式数据库的数据区域管理。Akkio 服务处于应用层和数据库层之间,对两端均透明。它主要负责决定一个数据块应分配到哪一区域,以及规划相关的数据迁移工作。Akkio 从 2014 年起在 Facebook 投入生产,在论文发布时已在管理约 100 PB 的数据。FB 自己的分析认为 Akkio 的存在减少了 50% 以上的数据读取延迟,还减少了 50% 以上的跨数据中心流量。FB 强调了 Akkio 在支持强一致性的同时,具有高性能、高可扩展性,并且易于在不同的底层数据库之间迁移。

当谈到数据块的分配和迁移,数据分块分片的粒度显得非常关键。Akkio 实现这些特性的核心之一是 FB 的数据仓库使用了一个比 shard 更小的分片单位: μ-shard。

μ-shards

虽然已经是看似较小的“分片”,但实际一个 shard 平均能达到 2GB 的数据量。以 2GB 作为迁移的粒度显然还是太粗。在把数据分配到 shard 时,通常的做法是使用哈希或者键值区间的方式根据数据的 Key 来决定其所在区块,核心是均匀分配、负载均衡。但在这种分配方式下,同一个 shard 内不同记录并没有访问区域上必然的联系,用来作为区域管理的单位显然是不合适的。因此,论文引入了新的单位 μ-shard(微分片?) 作为区域管理的基础单位。

μ-shard 被称为“手指粒度(finger grained)”级别的单位,每个 μ-shard 里的数据具有一定程度上的区域共性(high expectation of access locallity),具体的分配算法由应用层指定,毕竟只有应用才知道什么数据之间会有相同的访问区域……单个 μ-shard 的平均大小约为 200 KB,远比 shard 轻量。每个 shard 都被分割成若干个 μ-shard 进行管理,这就是论文标题 Shard the shards 的由来。FB 内部使用的一些数据库,如 ZippyDB,已经支持使用 μ-shard 作为一级抽象。

副本组(replication set),和副本组集合(replication set collection)

这里是一些 ZippyDB 相关的术语解释,可以跳过……

对于一个 shard 的所有副本(replica),我们称其为一个副本组。一个 shard 的副本组配置包括这个 shard 使用多少个副本,以及它的副本如何部署在各个数据仓库节点中。对于副本组配置相同的一系列副本组,我们称其为一个副本组集合

功能

虽然 μ-shard 由客户端应用层指定,但是 Akkio 的运作仍然是对应用层和数据库层透明的。Akkio 负责四个功能:

  • 跟踪 与统计客户端的数据访问
  • 决定 每个 μ-shard 放置的区域
  • 根据最近访问数据优化迁移 μ-shard 到更合适的区域
  • 将各个数据访问请求导航到正确的 μ-shard

架构

Akkio系统架构
Akkio 的主要逻辑位于 Akkio Client Library,其嵌入在数据库的库中。当客户端向数据库发起数据访问请求的时候,会唤起 Akkio 的业务逻辑。Akkio 服务主要由三个服务组成,分别是 ALS(Akkio Location Service,位置服务),ACS(Akkio Counter Service,计数服务)和 DPS(Data Placement Service,数据放置服务)。

ALS

ALS 维护了一个区域数据库,用于为各个访问请求查找目标 μ-shard 所在的区域。这个数据库会在 μ-shard 被迁移时进行更新。该数据库在每个数据中心都有一个副本,并通过分布式 cache 减少数据库负载。虽然 cache 可能导致一致性问题,比如应用有可能读到未更新的区域映射然后将请求发送到了错误的数据中心,但是基本上问题不大,底层数据库会发现这个问题并及时更新。

由于这个数据库非常小,对每个数据中心来说维护这个数据库增加不了多少负担(“trival”);而且这个数据库也能通过增加 cache 的方式轻松地进行扩展。

ACS

ACS 维护了一个访问计数数据库,用于追踪所有的访问以及一定时间窗口内的访问频率,作为对 μ-shard 进行区域分配的参考。每个数据访问都会触发 ACS 对访问的客户端地区、访问种类以及被访问的数据进行记录。访问的追踪计数是异步的过程,不会造成数据读写的阻塞。

ACS 可以简单地实现扩展,只要多弄几台服务器就行了。另外也可以进行优化,比如让一些具有相同的访问特征的应用层服务共用同一个计数器,从而减少 ACS 的负担;这种方式被称为“代理”。另外,这些追踪的请求会批量优化后进行,从而减少了额外的通讯消耗。

DPS

DPS 决定每个 μ-shard 所在的区域,并努力优化以实现最低的访问延迟及资源占用。同时, DPS 也负责启动和管理 μ-shard 的迁移工作。当一个数据有可能需要进行区域优化时,DPS 会收到来自 ACS 的通知,并开始评估是否需要进行迁移。DPS 作为一个分布式服务,部署在每一个数据中心里。

定位

给一个 μ-shard 决定其区域时,默认的策略是对所有可用的副本组(replica set)进行评分,并把 μ-shard 分配给得分最高的副本组。评分由两步组成:

  1. 计算过去 X 天(X 可配置)内每个数据中心访问该 μ-shard 的总次数,并给予时间更近的访问以更高的权重。对于每个副本组,将其所在的数据中心的得分相加得到总分。如果存在最高分,那么就直接分配到这个副本组。
  2. 如果存在两个以上的最高分,那么对于这些副本组计算其资源占用情况,并把 μ-shard 分配到压力最小的副本组。

迁移

迁移 μ-shard 根据底层数据库的功能差别采用不同的方法。简单来说就是支持 ACL(access control list)的就直接通过 ACL 修改数据读写权限并完成迁移;而对于不支持 ACL 的,比如 Cassandra,就通过时间戳来保障迁移过程的强一致性。

容错

ALS 和 ACS 因为都即时永久化了,所以出现宕机直接重启就行。DPS 就需要多费点心思,因为有可能在迁移中途出现错误而宕机。论文的方案是使用 ZooKeeper 维护一个全局的自增序列号,通过验证这一序列号防止同一迁移被多次执行。

总结

其实这个东西吧……我当时看的第一反应觉得思路还挺自然的。把东西放到它应该放到的地方,这样的优化可以说是从源头解决问题,相比起来加 cache 大法就只是疯狂补锅罢辽。不过细节是魔鬼,实际操作的时候到底怎么 shard the shards,到底怎么分辨数据的 locality,这些问题感觉还是只能经验主义。从结果而言,大幅的延迟降低和带宽占用减少感觉还是很漂亮的,对上下层透明这点感觉也很舒服。


参考文献:Sharding the Shards: Managing Datastore
Locality at Scale with Akkio