DDIA 读书分享 第六章：分片方式

DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 在这里[1]。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。

上一章主要讲复制，本章转向分片。这是两个相对正交但勾连的两个概念：

1. 分片（Partition）：解决数据集尺度与单机容量、负载不匹配的问题，分片之后可以利用多机容量和负载。
2. 复制（Replication）：系统机器一多，单机故障概率便增大，为了防止数据丢失以及服务高可用，需要做多副本。

分片，Partition，有很多别称。通用的有 Shard；具体到实际系统，HBase 中叫 Region，Bigtable 中叫 tablet，等等。本质上是对数据集的一种逻辑划分，后面行文，分片和分区可能混用，且有时为名词，有时为动词。

通常来说，数据系统在分布式系统中会有三级划分：数据集（如 Database、Bucket）——分片（Partition）——数据条目（Row、KV）。通常，每个分片只属于一个数据集，每个数据条目只属于一个分片。单个分片，就像一个小点的数据库。但是，跨分区的操作的，就要复杂的多。

本章首先会介绍数据集切分的方法，并讨论索引和分片的配合；然后将会讨论分片再平衡（rebalancing），集群节点增删会引起数据再平衡；最后，会探讨数据库如何将请求路由到相应的分片并执行。

分片和复制

分片通常和复制结合使用。每个分片有多个副本，可以分散到多机上去（更泛化一点：多个容错阈）；同时，每个机器含有多个分片，但通常不会有一个分片的两个副本放到一个机器上。

如果使用多副本使用主从模型，则分片、副本、机器关系如下：

1. 从一个分片的角度看，主副本在一个机器上，从副本们在另外机器上。
2. 从一个机器的角度看，既有一些主副本分片，也有一些从副本分片。实践中，也会尽量保证主副本在集群中均匀分布，避免过多的集中到一台机器上。想想为什么？

综合分片和多副本

由于分区方式和复制策略相对正交，本章会暂时忽略复制策略（在上章讲过），专注分析分区方式。

键值对集的分区

键值对是数据的一种最通用、泛化的表示，其他种类数据库都可以转化为键值对表示：

1. 关系型数据库，primary key → row
2. 文档型数据库，document id → document
3. 图数据库，vertex id → vertex props, edge id → edge props

因此，接下来主要针对键值对集合的分区方式，则其他数据库在构建存储层时，可以首先转化为 KV 对，然后进行分区。

分片（Partition）的本质是对数据集合的划分。但在实践中，可以细分为两个步骤：

1. 对数据集进行逻辑划分
2. 将逻辑分片调度到物理节点

因此，在分片时，有一些基本要求：

1. 分片过程中，要保证每个分片的数据量多少尽量均匀，否则会有数据偏斜（skew），甚而形成数据热点。
2. 分片后，需要保存路由信息，给一个 KV 条目，能知道去哪个机器上去查；稍差一些，可以知道去哪几个机器上去找；最差的，如果需要去所有机器逐一查询，但性能一般不可接受。

这两条是互相依赖和制约的。比如说，假设分片数目确定，为了分片均匀，每来一条数据，我们可以等概率随机选择一个分片；但在查询每个数据条目时，就得去所有机器上都查一遍。

保存所有数据条目路由信息，有三种常用的策略：

1. 通过某种固定规则，比如哈希，算出一个位置。
2. 使用内存，保存所有数据条目到机器的映射。
3. 结合两种，首先通过规则算出到逻辑分片的映射，然后通过内存保存逻辑分片到物理节点的映射。

本节主要讨论根据数据条目（Data Item）算出逻辑分区（Partition），常见的有两种方式：按键范围分区，按键哈希分区。

按键范围（Key Range）分区

对于 KV 数据来说，Key 通常会有个定义域，且在定义域内可（按某种维度）排序。则，将该连续的定义域进行切分，保存每个切分的上下界，在给出某个 Key 时，就能通过比较，定位其所在分区。

如，百科全书系列，通常是按照名词的字母序来分册的，每个分册可理解为该系列的一个分区，查阅时，可根据字母排序来首先找到所在分册，再使用分册目录查阅。图书馆图书的索引编号也是类似道理。

按首字母字典序的图书类

由于键并不一定在定义域内均匀分布，因此简单按照定义域等分，并不能将数据等分。因此，需要按照数据的分布，动态调整分区的界限，保证分区间数据大致均匀。这个调整的过程，既可以手动完成 ，也可以自动进行。

按键范围分区好处在于可以进行快速的范围查询（Rang Query）。如，某个应用是保存传感器数据，并将时间戳作为键进行分区，则可轻松获取一段时间内（如某年，某月）的数据。

但坏处在于，数据分散不均匀，且容易造成热点。可能需要动态的调整的分区边界，以维护分片的相对均匀。

仍以传感器数据存储为例，以时间戳为 Key，按天的粒度进行分区，所有最新写入都被路由到最后一个分区节点，造成严重的写入倾斜，不能充分利用所有机器的写入带宽。一个解决办法是分级或者混合，使用拼接主键，如使用传感器名称+时间戳作为主键，则可以将同时写入的多个传感器的数据分散到多机上去。

按键散列（Hash）分区

为了避免数据倾斜和读写热点，许多数据系统使用散列函数对键进行分区。

因此，选择散列函数的依据是，使得数据散列尽量均匀：即给定一个 Key，经过散列函数后，以等概率在哈希区间（如 [0, 2^32-1)）内产生一个值。即使原 Key 相似，他的散列值也能均匀分布。

而加密并不在考虑之列，因此并不需要多么复杂的加密算法，如，Cassandra 和 MongoDB 使用 MD5，Voldemort 使用 Fowler-Noll-Vo 函数。

选定哈希函数后，将原 Key 定义域映射到新的散列值阈，而散列值是均匀的，因此可以对散列值阈按给定分区数进行等分。

按哈希进行分片

还有一种常提的哈希方法叫做一致性哈希[2]。其特点是，会考虑逻辑分片和物理拓扑，将数据和物理节点按同样的哈希函数进行哈希，来决定如何将哈希分片路由到不同机器上。它可以避免在内存中维护逻辑分片到物理节点的映射，而是每次计算出来。即用一套算法同时解决了我们在最初提出的逻辑分片和物理路由的两个问题。比较经典的数据系统，Amazon Dynamo[3] 就用了这种方式。

Amazon Dynamo 一致性哈希架构

如果不使用一致性哈希，我们需要在元数据节点中，维护逻辑分片到物理节点的映射。则在某些物理节点宕机后，需要调整该映射并手动进行数据迁移，而不能像一致性哈希一样，半自动的增量式迁移。

哈希分片在获取均匀散列能力的同时，也丧失了基于键高效的范围查询能力。如书中说，MongoDB 中选择基于哈希的分区方式，范围查询就要发送到所有分区节点；Riak 、Couchbase 或 Voldmort 干脆不支持主键的上的范围查询。

一种折中方式，和上小节一样，使用组合的方式，先散列，再顺序。如使用主键进行散列得到分区，在每个分区内使用其他列顺序存储。如在社交网络上，首先按 user_id 进行散列分区，再使用 update_time 对用户事件进行顺序排序，则可以通过 (user_id, update_timestamp) 高效查询某个用户一段事件的事件。

小结一下，两种分区方式区别在于，一个使用应用相关值（ Key ）分区，一个使用应用无关值（Hash(key)）分区，前者支持高效范围查询，后者可以均摊负载。但可使用多个字段，组合使用两种方式，使用一个字段进行分区，使用另一个字段在分区内进行排序，兼取两者优点。

负载偏斜和热点消除

在数据层，可以通过哈希将数据均匀散列，以期将对数据的请求均摊；但如果在应用层，不同数据条目的负载本就有倾斜，存在对某些键的热点。那么仅在数据层哈希，就不能起到消除热点的作用。

如在社交网络中的大 V，其发布的信息，天然会引起同一个键（假设键是用户 id）大量数据的写入，因为可能会有针对该用户信息的大量评论和互动。

此时，就只能在应用层进行热点消除，如可以用拼接主键，对这些大 V 用户主键进行“分身”，即在用户主键开始或者结尾添加一个随机数，两个十进制后缀就可以增加 100 种拆分可能。但这无疑需要应用层做额外的工作，请求时需要进行拆分，返回时需要进行合并。

可能之后能开发出检测热点，自动拆分合并分区，以消除倾斜和热点。

参考资料

[1]

DDIA 读书分享会: https://docs.qq.com/sheet/DWHFzdk5lUWx4UWJq

[2]

一致性哈希: https://zh.m.wikipedia.org/zh-hans/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C

[3]

Amazon Dynamo: https://www.qtmuniao.com/2020/06/13/dynamo/