拓冰网站定制 
文档教程【免费下载链接】ddia《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译项目地址https://gitcode.com/gh_mirrors/dd/ddia点击查看免费下载本文基于 DDIA 中文翻译仓库 content/zh/ch7.md 完整梳理第七章《分片》的全部核心内容为什么需要分片、分片与复制的关系、面向多租户的分片、键范围分片与哈希分片的取舍、热点的成因与缓解、再平衡策略、请求路由以及二级索引在分片数据库中的两种落地形态本地索引与全局索引。读完本文你将能够为大规模数据系统选择合适的分区键与分片算法理解 Cassandra、HBase、MongoDB、DynamoDB、CockroachDB 等主流数据库分片方案背后的共同原理并能针对倾斜工作负载设计热点缓解策略。数据分布的两条路径复制与分片分布式数据库通常通过两种方式在节点间分布数据一是复制replication在多个节点上保存相同数据的副本已在 content/zh/ch6.md 中讨论二是分片shard也称分区partition把大规模数据集拆成更小的分片再将不同分片存放到不同节点。本章讨论的正是分片。通常情况下每条数据每条记录、每行或每个文档属于且仅属于一个分片。实际上每个分片都是自己的小型数据库尽管有些数据库支持同时涉及多个分片的操作。分片通常与复制结合使用使得每个分片的副本存储在多个节点上——这意味着即使每条记录只属于一个分片它仍然可以存储在多个不同的节点上以获得容错能力。一个节点可能存储多个分片。如果使用单主复制模型分片与复制的组合如图所示每个分片的领导者被分配给一个节点追随者被分配给其他节点每个节点可能是某些分片的领导者同时是其他分片的追随者但每个分片仍然只有一个领导者。content/zh/ch6.md 中讨论的关于数据库复制的所有内容同样适用于分片的复制。大多数情况下分片方案与复制方案可以独立选择为简单起见本章的讨论忽略复制。分片与分区本章所谓的分片在不同软件中有许多不同名称Kafka 称其为分区partitionCockroachDB 称为范围rangeHBase 和 TiDB 称为区域regionBigtable 和 YugabyteDB 称为表分片tabletCassandra、ScyllaDB 和 Riak 称为虚节点vnodeCouchbase 则称为虚桶vBucket。一些数据库把分区和分片视为两个不同概念例如 PostgreSQL 中分区是把一张大表拆成存储在同一台机器上的多个文件分片则是把数据集拆分到多台机器上而许多其他系统中分区不过是分片的另一个名称。另外注意分区与网络分区network partition也称 netsplit毫无关系——后者是节点间网络发生的一类故障将在 content/zh/ch9.md 中讨论。分片的利与弊为什么说它是重量级方案对数据库进行分片主要是为了获得可伸缩性scalability当数据量或写入吞吐量大到单个节点无法承受时分片可以把数据和写入分散到多个节点上。如果瓶颈是读取吞吐量则未必需要分片可以采用 content/zh/ch6.md 介绍的读扩展read scaling。事实上分片是实现水平扩展horizontal scaling、即 scale-out 架构的主要手段之一系统不必换用更大的机器而是通过增加更多较小的机器来扩充容量参见 content/zh/ch2.md 的共享内存、共享磁盘与无共享架构。如果能合理划分工作负载让每个分片承担大致相等的份额就可以把这些分片分配给不同机器并行处理其中的数据和查询。复制可以提供容错和离线运行能力因而无论规模大小都有用分片却是一种重量级方案主要适用于大规模场景。如果数据量和写入吞吐量仍可由单台机器处理如今单机的能力不容小觑通常最好避免分片坚持使用单分片数据库。分片往往会增加复杂性通常需要选择一个分区键partition key据此决定每条记录应放入哪个分片分区键相同的记录都会进入同一分片。这个选择十分重要——如果知道记录在哪个分片访问就很快如果不知道就只能低效地搜索所有分片而且日后很难更改分片方案。因此分片通常很适合键值数据因为可以直接按键分片关系数据则比较棘手因为可能需要通过二级索引搜索或连接散落在不同分片中的记录详见后文分片与二级索引。分片还有一个问题一次写入可能需要更新多个不同分片中的相关记录。单节点事务相当普遍但要保证多个分片之间的一致性就需要分布式事务distributed transaction。正如 content/zh/ch8.md 将要说明的有些数据库支持分布式事务但这类事务通常比单节点事务慢得多可能成为整个系统的瓶颈还有些系统根本不支持分布式事务。值得注意的还有有些系统甚至会在单台机器上使用分片通常是在每个 CPU 核心上运行一个单线程进程以利用 CPU 的并行能力或者利用非一致性内存访问NUMA架构。例如Redis、VoltDB 和 FoundationDB 都采用每个核心一个进程的方式并依靠分片把负载分摊到同一台机器的各个 CPU 核心上。面向多租户的分片软件即服务SaaS产品和云服务通常采用**多租户multitenant**模式每个租户对应一个客户。同一租户可以有多个用户账号但每个租户拥有一份自成一体、与其他租户隔离的数据集。例如在电子邮件营销服务中每家注册企业通常都是一个独立租户因为各家企业的简报订阅信息、投递数据等彼此无关。多租户系统有时通过分片来实现可以为每个租户分配一个独立分片也可以把多个小租户归入一个较大的分片。这些分片可以是物理上相互独立的数据库参见 content/zh/ch4.md 的嵌入式存储引擎也可以是一个更大逻辑数据库中能够单独管理的组成部分。用分片实现多租户有以下优点资源隔离如果某个租户执行计算开销很大的操作只要它与其他租户位于不同分片其他租户的性能就不太容易受到影响。权限隔离如果访问控制逻辑存在漏洞只要各租户的数据集在物理上彼此隔离意外让一个租户访问另一租户数据的可能性就会降低。单元化架构cell-based architecture分片不仅可以用在数据存储层也可以用来划分运行应用代码的服务。在单元化架构中为一组特定租户服务的应用与存储会组成一个自包含的单元cell不同单元大体可以彼此独立地运行。这种方法能够实现故障隔离fault isolation一个单元里的故障只影响该单元不会殃及其他单元中的租户。按租户备份和恢复分别备份每个租户的分片就能从备份中恢复某个租户的状态而不影响其他租户。租户意外删除或覆盖重要数据时这一能力很有用。法规合规性GDPR 等数据隐私法规赋予个人访问并删除关于自己的全部存储数据的权利。如果每个人的数据都存放在独立分片中实现这一权利就只需对相应分片执行简单的数据导出和删除操作。数据驻留如果数据驻留法规要求某个租户的数据必须存放在特定司法管辖区区域感知数据库可以把该租户的分片分配到指定区域。逐步推出模式变更模式迁移参见 content/zh/ch3.md 的文档模型中的模式灵活性可以逐步推出每次只迁移一个租户在问题波及所有租户之前将其发现从而降低风险不过很难以事务方式完成。使用分片实现多租户的主要挑战这种做法假定每个租户的数据量都足够小能装进单个节点。如果某个租户大到一台机器容纳不下就还必须在租户内部继续分片于是问题又回到了为了可伸缩性而分片。如果小租户很多为每个租户单独建立分片的开销可能过大。可以把多个小租户合并到一个较大的分片里但随着租户成长又会遇到如何把它从一个分片迁移到另一个分片的问题。如果日后需要支持跨租户关联数据的功能跨多个分片连接数据会使这些功能更难实现。键值数据的分片目标、倾斜与热点假设有大量数据并且想要分片如何决定在哪些节点上存储哪些记录分片的目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分担数据和负载那么理论上10 个节点应该能够处理单个节点 10 倍的数据量和 10 倍的读写吞吐量暂时忽略复制。此外在添加或移除节点时我们希望能够**再平衡rebalance**负载使它均匀分布在增加后的 11 个节点上或移除节点后剩余的 9 个节点上。如果分片不公平某些分片承载的数据或查询比其他分片更多我们就称其为倾斜skew。倾斜会大幅降低分片的效果在极端情况下全部负载都可能集中到一个分片上10 个节点中有 9 个闲置瓶颈却卡在唯一繁忙的节点上。负载高得不成比例的分片称为热分片hot shard或热点hot spot如果某个键的负载特别高例如社交网络中的名人账号则称为热键hot key。因此需要一种算法以记录的分区键为输入指出这条记录属于哪个分片。在键值存储中分区键通常就是键或键的第一部分在关系模型中它可以是表中的某一列不一定非得是主键。为了缓解热点这种算法还必须便于再平衡。按键的范围分片有序、高效但易出热点一种分片方法是为每个分片指定一段连续的分区键范围从某个最小值到某个最大值就像纸质百科全书的各卷词条标题就是分区键如果知道各范围之间的边界就能轻松确定词条所在的分片。各段键范围不一定等宽因为数据本身很可能分布不均——第 1 卷收录以 A 和 B 开头的单词第 12 卷却收录以 T 到 Z 开头的单词。为了均匀分布数据分片边界必须根据数据进行调整。分片边界既可以由管理员手工选择也可以由数据库自动确定VitessMySQL 的分片层采用手动的键范围分片Bigtable、其开源版本 HBase、MongoDB 的范围分片选项、CockroachDB、RethinkDB 和 FoundationDB 则采用自动方式YugabyteDB 同时支持手动和自动拆分表分片。每个分片内部都按顺序存储键例如使用 B 树或 SSTable参见 content/zh/ch4.md。这样很容易执行范围扫描也可以把键当作联合索引在一次查询中获取多条相关记录参见 content/zh/ch4.md 的多维索引与全文索引。例如某个应用程序存储传感器网络的数据并以测量时间戳作为键范围扫描可以轻松取出某个月份的全部读数。键范围分片的缺点是如果大量写入集中在相邻的键上很容易形成热分片。例如键若是时间戳分片就对应不同时间范围每个月一个分片。遗憾的是如果传感器在产生测量值时就立即写入数据库所有写入都会落到同一个分片本月的分片中结果该分片可能被写入压垮其他分片却无所事事。为了避免传感器数据库出现这个问题键的第一部分就不能只用时间戳可以在每个时间戳前加上传感器 ID使键先按传感器 ID、再按时间戳排序。只要有许多传感器同时工作写入负载就会更均匀地分布到各个分片。代价是要获取多个传感器在某段时间内的测量值现在必须为每个传感器分别执行一次范围查询。再平衡键范围分片数据预拆分、拆分与合并首次建立数据库时还没有数据可供划定键范围。一些数据库如 HBase 和 MongoDB允许在空数据库上配置一组初始分片这称为预拆分pre-splitting但必须事先大致了解键将如何分布才能选出合适的键范围边界。此后随着数据量和写入吞吐量增长采用键范围分片的系统会把现有分片拆成两个或更多较小分片每个新分片都保存原键范围中的一段连续子范围这些较小的分片随后可以分散到多个节点上。如果大量数据被删除几个相邻且已经变小的分片也可能需要合并成一个较大的分片。这个过程类似于 B 树顶层发生的变化参见 content/zh/ch4.md 的B 树。对于自动管理分片边界的数据库分片的拆分通常由以下情况触发分片达到配置的大小例如 HBase 默认为 10 GB或者在某些系统中写入吞吐量持续高于某个阈值——即使一个热分片存储的数据不多也可能被拆分以便将其写入负载分布得更加均匀。键范围分片的优点是分片数量能够随数据量调整数据很少时只需少量分片开销很小数据量巨大时每个分片的大小仍会被限制在可配置的上限之内。缺点是拆分分片代价很高必须把其中的全部数据重写到新文件里类似于日志结构存储引擎的压实操作。需要拆分的分片往往本就处于高负载拆分开销还会雪上加霜甚至使它彻底过载。按键的哈希分片均匀但破坏有序性如果希望相邻但不同的分区键进入同一个分片键范围分片就很有用时间戳便是一个例子。如果不关心分区键是否相邻例如多租户应用中的租户 ID常见做法是先计算分区键的哈希值再将它映射到分片。好的哈希函数可以把倾斜的数据均匀打散。假设有一个接受字符串输入的 32 位哈希函数每输入一个新字符串它都会返回一个看似随机、介于 0 和 2³² − 1 之间的数即使输入字符串非常相似所得哈希值也会均匀分布在这个范围内相同输入总会产生相同输出。用于分片的哈希函数不必具备密码学强度例如 MongoDB 使用 MD5Cassandra 和 ScyllaDB 则使用 Murmur3。许多编程语言内置的哈希表哈希函数未必适合分片例如 Java 的Object.hashCode()和 Ruby 的Object#hash可能会让同一个键在不同进程中得到不同哈希值因此不能用于分片。哈希取模节点数简单但再平衡极低效算出键的哈希值之后该如何选择存储它的分片最直接的想法是让哈希值对系统中的节点数取模许多编程语言使用%运算符。例如hash(key) % 10会返回 0 到 9 之间的数假设有 10 个节点编号为 0 到 9这似乎是把键分配到节点的简单办法。模 N 方法的问题在于只要节点数 N 发生变化大多数键就必须从一个节点移到另一个节点。上图的例子中三个节点增加到四个再平衡之前节点 0 存储哈希值为 0、3、6、9 等的键加入第四个节点之后哈希值为 3 的键移到节点 3哈希值为 6 的键移到节点 2哈希值为 9 的键移到节点 1依此类推。模 N很容易计算却会导致极其低效的再平衡因为大量记录在节点之间进行了不必要的迁移。我们需要一种只移动必要数据的办法。固定数量的分片移动分片而非移动键一种简单而常用的解决方案是创建远多于节点数的分片再给每个节点分配多个分片。例如一个运行在 10 节点集群上的数据库可以从一开始就划分成 1,000 个分片每个节点分得 100 个。键会存入编号为hash(key) % 1,000的分片而系统另行记录每个分片存放在哪个节点上。如果向集群加入一个节点系统可以把现有节点上的一部分分片重新分配给新节点直到分片再次均匀分布移除节点时则反向执行同样的操作。在这种模型中只有完整的分片在节点之间移动成本低于拆分分片。分片的数量不会改变键所指定的分片也不会改变唯一改变的是分片所在的节点。这种变更并非即时——在网络上传输大量数据需要时间——所以传输期间发生的读写仍按原有的分片到节点映射处理。分片数量通常会选成一个因数很多的数字使数据集能够均匀分配到多种不同规模的节点集群中例如不必要求节点数是 2 的幂。甚至还可以照顾集群中的硬件差异给性能更强的节点分配更多分片让它们承担更大比例的负载。CitusPostgreSQL 的分片层、Riak、Elasticsearch 和 Couchbase 等系统都采用这种分片方法。只要首次创建数据库时能较准确地估计所需分片数它就很好用此后可以轻松增删节点不过节点数不能超过分片数。如果发现最初配置的分片数不合适——例如系统规模已经大到所需节点数超过分片数——就必须执行代价高昂的重新分片拆开每个分片、写出新文件并占用大量额外磁盘空间。有些系统不允许在数据库继续接受写入时重新分片因此很难在不停机的情况下改变分片数量。如果数据集总量变化很大例如开始时很小随后可能增长许多倍选择合适的分片数就很困难。由于每个分片包含总数据量的固定比例其大小会随集群中的数据总量同比增长。分片太大再平衡和从节点失效中恢复都会十分昂贵分片太小又会带来过多管理开销。分片大小不大不小、恰到好处时性能最佳但在分片数固定而数据集大小不断变化时这一状态很难维持。按哈希范围分片键范围分片的哈希化变体如果无法事先预测需要多少分片最好采用一种能让分片数量轻松适应工作负载的方案。前述键范围分片具备这一性质但大量写入集中到相邻键时容易形成热点。一种解决办法是将键范围分片与哈希函数结合使每个分片包含一段哈希值范围而不是一段键范围。上图展示了一个 16 位哈希函数返回 0 到 65,535 2¹⁶ − 1 之间的数实际使用的哈希通常至少有 32 位。即使输入键十分相似例如连续的时间戳它们的哈希值也会均匀分布在这个范围内。于是可以为每个分片分配一段哈希值范围例如 0 到 16,383 归分片 016,384 到 32,767 归分片 1依此类推。与键范围分片一样哈希范围分片也可以在分片过大或负载过重时将其拆分。这个操作依然昂贵但可以按需执行因此分片数量会随数据量调整而不是预先固定不变。它相对于键范围分片的缺点是无法高效地对分区键执行范围查询因为范围内的键如今散布在所有分片中。不过如果键由两列或更多列组成而分区键只是其中第一列仍然可以对第二列及之后的列高效执行范围查询只要范围查询中的所有记录拥有相同分区键它们就会落在同一个分片中。数据仓库中的分区与范围查询BigQuery、Snowflake 和 Delta Lake 等数据仓库也支持类似的索引方式只是术语不同。BigQuery 中分区键决定记录属于哪个分区聚簇列决定记录在分区内的排序方式Snowflake 自动把记录分配给微分区但允许用户为表定义聚簇键Delta Lake 同时支持手动与自动分配分区也支持聚簇键。对数据进行聚簇不仅能改善范围扫描的性能还能提高压缩率和过滤效率。YugabyteDB 和 DynamoDB 采用哈希范围分片MongoDB 也把它作为一种可选方案。Cassandra 和 ScyllaDB 则采用这种方法的一个变体它们把哈希值空间划分成若干范围范围数与节点数成正比图中每个节点有 3 个范围实际默认值是 Cassandra 每个节点 8 个、ScyllaDB 每个节点 256 个各范围之间的边界随机选定。这样有些范围会比其他范围大但每个节点拥有多个范围之后这些不均衡往往能相互抵消。添加或移除节点时系统会相应增删范围边界并拆分或合并分片。例如加入节点 3 之后节点 1 把自己两个范围中的一部分交给节点 3节点 2 也把一个范围中的一部分交给节点 3。这样新节点便能分得大致公平的一份数据同时避免在节点间传输不必要的数据。一致性哈希让键尽量留在原分片**一致性哈希consistent hashing**算法是一种哈希函数它把键映射到指定数量的分片并满足两个性质映射到各个分片的键数大致相等分片数量改变时尽可能少地在分片之间迁移键。注意这里的一致性与副本一致性参见 content/zh/ch6.md或 ACID 一致性参见 content/zh/ch8.md毫无关系它描述的是让一个键尽量留在原分片中的倾向。Cassandra 和 ScyllaDB 的分片算法与一致性哈希的原始定义相似此外还有多种其他一致性哈希算法最高随机权重highest random weight也称约会哈希rendezvous hashing和跳跃一致性哈希jump consistent hash。采用 Cassandra 的算法时加入一个节点会把少量现有分片拆成若干子范围采用约会哈希或跳跃一致性哈希时新节点得到的则是此前散布在所有其他节点上的一个个键。哪种方式更合适取决于具体应用。倾斜的工作负载与缓解热点一致性哈希可以保证键大致均匀地分布到各节点却不能保证实际负载也同样均匀。如果工作负载高度倾斜——某些分区键下的数据量远大于其他键或者某些键的请求速率远高于其他键——仍然可能有些服务器不堪重负另一些服务器却几乎闲置。例如在社交媒体网站上一个拥有数百万粉丝的名人做出某个举动可能引发一场活动风暴产生针对同一个键的大量读写分区键也许是该名人的用户 ID也许是众人正在评论的事件 ID。这种情况需要更加灵活的分片策略给热键单独开分片如果系统按键范围或哈希范围定义分片就可以把一个热键单独放进一个分片甚至给它分配一台专用机器。应用层补偿倾斜例如在键的开头或末尾添加随机数。只需两位十进制随机数就能把针对该键的写入均匀拆成 100 个不同的键让它们分布到不同分片。不过写入分散到不同键之后读取就得付出额外代价必须从全部 100 个键读取数据再把结果合并起来。热键分散后每个分片承受的读取量并没有减少降低的只有写入负载。这种技术还需要额外的记录工作只有少数热键值得添加随机数对于写入吞吐量很低的绝大多数键这样做只会徒增开销。因此还需要记录哪些键已被拆分并设计一个流程把普通键转换成需要特殊管理的热键。负载还会随时间变化使问题更加复杂某条突然爆火的社交媒体帖子可能连续几天承受很高负载之后又很快归于平静。此外有些键是写入热点有些则是读取热点二者需要采用不同的处理策略。一些系统尤其是面向大规模场景设计的云服务能够自动处理热分片例如 Amazon 把相关机制称为热度管理heat management或自适应容量adaptive capacity这些系统的具体工作方式超出了本书的讨论范围。运维自动还是手动再平衡关于再平衡有一个重要问题自动还是手动进行有些系统无需人工介入会自动决定何时拆分分片、何时把分片从一个节点迁移到另一个节点另一些系统则要求管理员显式配置分片。两者之间也有折中方案例如 Couchbase 和 Riak 会自动生成建议的分片分配但必须由管理员确认提交后才会生效。全自动再平衡很方便日常维护所需的运维工作更少这样的系统甚至可以自动伸缩以适应工作负载的变化。DynamoDB 等云数据库宣称能够在几分钟内自动增删分片应对负载的大幅升降。然而自动分片管理也可能难以预测再平衡代价很高因为它要重新路由请求并在节点间迁移大量数据。如果处理不够谨慎这一过程可能使网络或节点过载拖累其他请求的性能。系统在再平衡期间还必须继续处理写入如果已经接近最大写入吞吐量分片拆分的速度甚至可能赶不上新写入到达的速度。这种自动化机制如果再与自动失效检测结合可能十分危险假设某个节点过载暂时无法及时响应请求其他节点据此断定它已经失效于是自动对集群进行再平衡把负载从该节点移走。这会给其他节点和网络施加额外负载让局面进一步恶化甚至引发级联失效其他节点也相继过载并被错误地判定为已经宕机。出于这个原因让人参与再平衡过程是一件好事——这比全自动流程慢但有助于防止运维意外。请求路由如何找到正确的节点把数据集分片到多个节点后下一个问题是如果想读写某个特定的键怎样知道应该连接哪个节点哪个 IP 地址和端口这个问题称为请求路由request routing与 content/zh/ch5.md 讨论的*服务发现service discovery*十分相似。二者最大的区别在于运行应用代码的服务实例通常是无状态的负载均衡器可以把请求发给任意实例而在分片数据库中某个键的请求只能交给持有该键所在分片副本的节点处理。因此请求路由必须了解键到分片、以及分片到节点的映射。概括来说有以下几种办法允许客户端连接任意节点例如通过轮询负载均衡器。如果该节点恰好持有请求涉及的分片就直接处理请求否则它把请求转发给正确的节点收到响应后再转交给客户端。先把所有请求发送到一个路由层由路由层判断哪个节点应当处理每个请求再相应地转发。路由层本身并不处理请求只充当一个能够感知分片的负载均衡器。让客户端了解分片方式以及分片到节点的分配关系。这样客户端无须经过任何中间层就能直接连接到正确的节点。在所有情况下都有一些关键问题由谁决定每个分片应当放在哪个节点最简单的办法是由单一协调者来决定但如果运行协调者的节点宕机怎样让协调者具备容错能力如果协调者能够故障切换到另一个节点又该如何防止发生脑裂参见 content/zh/ch6.md 的处理节点故障让两个协调者作出相互矛盾的分片分配负责路由的组件可以是某个数据库节点、路由层或客户端怎样得知分片到节点的分配发生了变化分片从一个节点迁移到另一个节点时会有一段切换期新节点已经接管但发往旧节点的请求可能仍在途中。应当如何处理这些请求许多分布式数据系统依靠ZooKeeper、etcd 等独立协调服务来记录分片分配。这些服务使用共识算法参见 content/zh/ch10.md实现容错并防止脑裂每个节点都在 ZooKeeper 中注册ZooKeeper 维护分片到节点的权威映射路由层或能够感知分片的客户端等其他参与者可以订阅 ZooKeeper 中的信息。只要分片易主或有节点加入、退出ZooKeeper 就会通知路由层使其路由信息保持最新。具体系统举例HBase 和 SolrCloud 使用 ZooKeeper 管理分片分配Kubernetes 使用 etcd 记录每个服务实例的运行位置MongoDB 的架构与之相似不过它依靠自有的*配置服务器config server*实现并以mongos守护进程作为路由层Kafka、YugabyteDB 和 TiDB 则使用内置的 Raft 共识协议实现这项协调功能。Cassandra、ScyllaDB 和 Riak 采用另一种办法节点之间通过**流言协议gossip protocol**传播集群状态的变化。它提供的一致性比共识协议弱得多因而可能出现脑裂使集群的不同部分对同一个分片持有不同的节点分配。无主数据库可以容忍这种情况因为它们本就只提供较弱的一致性保证参见 content/zh/ch6.md 的仲裁一致性的局限。无论使用路由层还是把请求发送给随机节点客户端仍然要先找到可供连接的 IP 地址。IP 地址的变化没有分片到节点的分配那么频繁因此通常用 DNS 就足够了。以上请求路由主要关注如何为单个键找到对应分片最适用于分片的 OLTP 数据库。分析型数据库通常也会分片但其查询执行方式截然不同查询一般不是在单个分片中执行而是要并行聚合并连接来自许多分片的数据。这类并行查询执行技术将在 content/zh/ch11.md 的JOIN 与 GROUP BY中讨论。分片与二级索引本地索引与全局索引到目前为止讨论的分片方案都要求客户端知道待访问记录的分区键。这在键值数据模型中最容易做到分区键是主键的第一部分或整个主键因此可以据此确定分片并把读写请求路由到负责该键的节点。涉及二级索引时情况会复杂得多另见 content/zh/ch4.md 的多列索引与二级索引。二级索引通常不能唯一标识一条记录而是用来搜索某个特定值出现在哪里例如查找用户123的所有操作、所有包含单词hogwash的文章或所有颜色为red的汽车。键值存储通常没有二级索引但它是关系数据库的基础能力在文档数据库中也十分常见更是 Solr、Elasticsearch 等全文检索引擎的立身之本。二级索引的问题在于它无法干净利落地映射到分片。对带有二级索引的数据库进行分片主要有两种办法本地索引和全局索引。本地二级索引按文档分区假设运营一个二手车交易网站每条车辆信息都有唯一 ID并以该 ID 作为分区键进行分片例如 ID 0 到 499 归分片 0ID 500 到 999 归分片 1。如果要让用户按颜色与品牌筛选车辆就需要在color和make上建立二级索引文档数据库中是字段关系数据库中则是列。声明索引后数据库会自动维护它每增加一辆红色汽车所在分片就会自动把它的 ID 加入索引条目color:red对应的 ID 列表。这种 ID 列表在 content/zh/ch4.md 中称为倒排列表postings list。在这种索引方式中每个分片都完全独立各自维护自己的二级索引只覆盖本分片中的记录。每次写入数据库——添加、删除或更新记录——只需处理包含该记录的分片。因此这种二级索引称为本地索引local index在信息检索领域它也称为按文档分区的索引document-partitioned index。读取本地二级索引时如果已经知道目标记录的分区键就只需在对应分片上搜索如果只想获得部分结果而不要求全部也可以把请求发给任意分片。但是如果需要全部结果又事先不知道这些记录的分区键就必须把查询发送到所有分片再合并返回结果因为匹配的记录可能散布在每个分片中。警告如果数据库只支持键值模型你也许会想在应用代码中建立值到 ID 的映射自行实现二级索引。如果选择这条路务必万分小心确保索引与底层数据始终一致。竞态条件和间歇性写入失败有些变更保存成功另一些却没有很容易让两者失去同步——参见 content/zh/ch8.md 的多对象事务的需求。这种查询方式会让二级索引上的读取查询相当昂贵即使并行查询所有分片也很容易出现尾部延迟放大参见 content/zh/ch2.md 的响应时间指标的应用。它还会限制应用的可伸缩性增加分片能容纳更多数据但如果每次查询仍要由所有分片处理查询吞吐量并不会随之提高。尽管如此本地二级索引依然应用广泛MongoDB、Riak、Cassandra、Elasticsearch、SolrCloud 和 VoltDB 都采用这种索引。全局二级索引按词项分区除了让每个分片各自维护本地二级索引也可以构建一个覆盖所有分片数据的全局索引global index。不过不能只把这个索引存放在单个节点上否则它很可能成为瓶颈使分片失去意义。因此全局索引本身也必须分片但可以采用与主键索引不同的分片方式。下图展示了一种可能的形式来自所有分片的红色汽车 ID 都列在索引的color:red条目下索引本身则经过分片以字母a到r开头的颜色归分片 0以s到z开头的颜色归分片 1。汽车品牌索引也以类似方式分片边界位于f与h之间。这种索引也称为按词项分区term-partitioned。回顾 content/zh/ch4.md 的全文检索在全文检索中*词项term*是文本中可供搜索的关键字这里把它推广为二级索引中任何可供搜索的值。全局索引以词项作为分区键因此查找某个词项或值时可以直接确定需要查询哪个分片。和前面一样每个分片可以包含一段连续的词项范围也可以根据词项的哈希值把词项分配到各个分片。全局索引的优点是如果查询只有一个条件如color red只需读取一个分片就能取得倒排列表。不过如果想要的不只是 ID 而是完整记录仍需读取负责存储这些 ID 的所有分片。如果查询包含多个条件或词项例如搜索某种颜色且属于某个品牌的汽车或搜索同一段文本中同时出现的多个单词这些词项很可能分属不同分片为了计算两个条件的逻辑 AND系统必须找出同时出现在两个倒排列表中的 ID。倒排列表较短时并不难但如果列表很长通过网络传输它们再计算交集速度就可能很慢。全局二级索引的另一个难题是写入比本地索引复杂写入一条记录可能影响索引的多个分片文档中的每个词项都可能位于不同分片。因此二级索引很难与底层数据保持同步。一种办法是使用分布式事务以原子方式更新保存主记录的分片及其二级索引分片参见 content/zh/ch8.md。CockroachDB、TiDB 和 YugabyteDB 都使用全局二级索引DynamoDB 则同时支持本地和全局二级索引。在 DynamoDB 中写入会异步反映到全局索引因此从全局索引读到的结果可能是陈旧的类似于 content/zh/ch6.md 的复制延迟的问题。尽管如此如果读取吞吐量高于写入吞吐量而且倒排列表不太长全局索引仍然很有用。总结分片方案选择的核心权衡在本章中我们探讨了将大数据集划分成更小子集的不同方法。数据量非常大的时候在单台机器上存储和处理不再可行而分片则十分必要。分片的目标是在多台机器上均匀分布数据和查询负载避免出现热点这需要选择适合数据的分片方案并在节点加入或移除时重新平衡分片。两种主要的分片方法键范围分片键按顺序排列每个分片拥有从某个最小值到某个最大值之间的所有键。有序存储的优点是能够高效执行范围查询但如果应用经常访问排序位置彼此接近的键就可能形成热点。采用这种方法时分片过大之后通常会把键范围拆成两个子范围从而动态地再平衡分片。哈希分片先对每个键应用哈希函数每个分片拥有一段哈希值范围也可以采用其他一致性哈希算法把哈希映射到分片。这种方法破坏了键的顺序使范围查询效率降低却可能让负载分布得更加均匀。按哈希分片时通常会预先创建固定数量的分片给每个节点分配多个分片增删节点时再把整个分片从一个节点迁移到另一个节点。也可以像键范围分片那样拆分分片。常见做法是以键的第一部分作为分区键即用来确定分片再按键的其余部分对分片内的记录排序。这样对于分区键相同的记录仍然可以高效执行范围查询。分片与二级索引的相互作用也有两种方法本地二级索引二级索引与主键及其值存储在同一个分片。写入时只需更新一个分片但查找二级索引时必须读取所有分片。全局二级索引根据索引值采用另一套分片方式。二级索引条目可以引用来自主键任意分片的记录。写入记录时可能需要更新多个二级索引分片但读取倒排列表时只需访问一个分片获取实际记录仍然要读取多个分片。最后我们还讨论了如何把查询路由到正确的分片以及如何通过协调服务记录分片到节点的分配关系。从设计上说每个分片大体独立运行——正因如此分片数据库才能伸缩到多台机器。然而需要写入多个分片的操作会变得很棘手例如一个分片写入成功另一个分片却失败时会怎样content/zh/ch8.md 将回答这个问题。延伸阅读原文档 content/zh/ch7.md 末尾附有 34 条高质量参考文献覆盖了 Citus 的 PostgreSQL 分片实践、FoundationDB 论文、Slack 使用 Vitess 的伸缩经验、Cassandra 虚节点与令牌分配算法、一致性哈希原始论文、跳跃一致性哈希、DynamoDB 论文、ZooKeeper 与分布式协调等主题是深入学习分片各子主题的绝佳索引本仓库的 content/en/ch7.md 提供英文原版对照。赞分享文档教程【免费下载链接】ddia《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译项目地址https://gitcode.com/gh_mirrors/dd/ddia点击查看免费下载相关推荐《设计数据密集型应用》第 7 章精读分片Sharding——从分区键选择、哈希策略到请求路由的分布式扩展实战指南《设计数据密集型应用》第 7 章精读分片Sharding——从分区键选择、哈希策略到请求路由的分布式扩展实战指南 本篇技术指南以《Designing Da文档教程DDIA 分片Sharding深度解析键范围与哈希分片、再平衡与请求路由实战指南DDIA 分片Sharding深度解析键范围与哈希分片、再平衡与请求路由实战指南 本篇指南以《设计数据密集型应用》DDIA第二版第七章为核心骨架系统文档教程GICv3 ITS翻译表从静态中断墙到动态路由网的架构重构GICv3 ITS翻译表从静态中断墙到动态路由网的架构重构 当服务器上的NVMe SSD阵列同时发起数百个并发I/O请求时传统的中断控制器就像一座只有102操作系统内核驱动驱动开发虚拟化嵌入式网络存储上一篇如何在openEuler系统部署LiteView浏览器30分钟完成编译与运行下一篇QEMU性能优化终极清单20个技巧提升虚拟机运行效率创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 设计数据密集型应用（DDIA）第七章精读：分片（Sharding）——从分区键选择、哈希与范围分片到请求路由的完整实战指南
文档教程【免费下载链接】ddia《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译项目地址https://gitcode.com/gh_mirrors/dd/ddia点击查看免费下载本文基于 DDIA 中文翻译仓库 content/zh/ch7.md 完整梳理第七章《分片》的全部核心内容为什么需要分片、分片与复制的关系、面向多租户的分片、键范围分片与哈希分片的取舍、热点的成因与缓解、再平衡策略、请求路由以及二级索引在分片数据库中的两种落地形态本地索引与全局索引。读完本文你将能够为大规模数据系统选择合适的分区键与分片算法理解 Cassandra、HBase、MongoDB、DynamoDB、CockroachDB 等主流数据库分片方案背后的共同原理并能针对倾斜工作负载设计热点缓解策略。数据分布的两条路径复制与分片分布式数据库通常通过两种方式在节点间分布数据一是复制replication在多个节点上保存相同数据的副本已在 content/zh/ch6.md 中讨论二是分片shard也称分区partition把大规模数据集拆成更小的分片再将不同分片存放到不同节点。本章讨论的正是分片。通常情况下每条数据每条记录、每行或每个文档属于且仅属于一个分片。实际上每个分片都是自己的小型数据库尽管有些数据库支持同时涉及多个分片的操作。分片通常与复制结合使用使得每个分片的副本存储在多个节点上——这意味着即使每条记录只属于一个分片它仍然可以存储在多个不同的节点上以获得容错能力。一个节点可能存储多个分片。如果使用单主复制模型分片与复制的组合如图所示每个分片的领导者被分配给一个节点追随者被分配给其他节点每个节点可能是某些分片的领导者同时是其他分片的追随者但每个分片仍然只有一个领导者。content/zh/ch6.md 中讨论的关于数据库复制的所有内容同样适用于分片的复制。大多数情况下分片方案与复制方案可以独立选择为简单起见本章的讨论忽略复制。分片与分区本章所谓的分片在不同软件中有许多不同名称Kafka 称其为分区partitionCockroachDB 称为范围rangeHBase 和 TiDB 称为区域regionBigtable 和 YugabyteDB 称为表分片tabletCassandra、ScyllaDB 和 Riak 称为虚节点vnodeCouchbase 则称为虚桶vBucket。一些数据库把分区和分片视为两个不同概念例如 PostgreSQL 中分区是把一张大表拆成存储在同一台机器上的多个文件分片则是把数据集拆分到多台机器上而许多其他系统中分区不过是分片的另一个名称。另外注意分区与网络分区network partition也称 netsplit毫无关系——后者是节点间网络发生的一类故障将在 content/zh/ch9.md 中讨论。分片的利与弊为什么说它是重量级方案对数据库进行分片主要是为了获得可伸缩性scalability当数据量或写入吞吐量大到单个节点无法承受时分片可以把数据和写入分散到多个节点上。如果瓶颈是读取吞吐量则未必需要分片可以采用 content/zh/ch6.md 介绍的读扩展read scaling。事实上分片是实现水平扩展horizontal scaling、即 scale-out 架构的主要手段之一系统不必换用更大的机器而是通过增加更多较小的机器来扩充容量参见 content/zh/ch2.md 的共享内存、共享磁盘与无共享架构。如果能合理划分工作负载让每个分片承担大致相等的份额就可以把这些分片分配给不同机器并行处理其中的数据和查询。复制可以提供容错和离线运行能力因而无论规模大小都有用分片却是一种重量级方案主要适用于大规模场景。如果数据量和写入吞吐量仍可由单台机器处理如今单机的能力不容小觑通常最好避免分片坚持使用单分片数据库。分片往往会增加复杂性通常需要选择一个分区键partition key据此决定每条记录应放入哪个分片分区键相同的记录都会进入同一分片。这个选择十分重要——如果知道记录在哪个分片访问就很快如果不知道就只能低效地搜索所有分片而且日后很难更改分片方案。因此分片通常很适合键值数据因为可以直接按键分片关系数据则比较棘手因为可能需要通过二级索引搜索或连接散落在不同分片中的记录详见后文分片与二级索引。分片还有一个问题一次写入可能需要更新多个不同分片中的相关记录。单节点事务相当普遍但要保证多个分片之间的一致性就需要分布式事务distributed transaction。正如 content/zh/ch8.md 将要说明的有些数据库支持分布式事务但这类事务通常比单节点事务慢得多可能成为整个系统的瓶颈还有些系统根本不支持分布式事务。值得注意的还有有些系统甚至会在单台机器上使用分片通常是在每个 CPU 核心上运行一个单线程进程以利用 CPU 的并行能力或者利用非一致性内存访问NUMA架构。例如Redis、VoltDB 和 FoundationDB 都采用每个核心一个进程的方式并依靠分片把负载分摊到同一台机器的各个 CPU 核心上。面向多租户的分片软件即服务SaaS产品和云服务通常采用**多租户multitenant**模式每个租户对应一个客户。同一租户可以有多个用户账号但每个租户拥有一份自成一体、与其他租户隔离的数据集。例如在电子邮件营销服务中每家注册企业通常都是一个独立租户因为各家企业的简报订阅信息、投递数据等彼此无关。多租户系统有时通过分片来实现可以为每个租户分配一个独立分片也可以把多个小租户归入一个较大的分片。这些分片可以是物理上相互独立的数据库参见 content/zh/ch4.md 的嵌入式存储引擎也可以是一个更大逻辑数据库中能够单独管理的组成部分。用分片实现多租户有以下优点资源隔离如果某个租户执行计算开销很大的操作只要它与其他租户位于不同分片其他租户的性能就不太容易受到影响。权限隔离如果访问控制逻辑存在漏洞只要各租户的数据集在物理上彼此隔离意外让一个租户访问另一租户数据的可能性就会降低。单元化架构cell-based architecture分片不仅可以用在数据存储层也可以用来划分运行应用代码的服务。在单元化架构中为一组特定租户服务的应用与存储会组成一个自包含的单元cell不同单元大体可以彼此独立地运行。这种方法能够实现故障隔离fault isolation一个单元里的故障只影响该单元不会殃及其他单元中的租户。按租户备份和恢复分别备份每个租户的分片就能从备份中恢复某个租户的状态而不影响其他租户。租户意外删除或覆盖重要数据时这一能力很有用。法规合规性GDPR 等数据隐私法规赋予个人访问并删除关于自己的全部存储数据的权利。如果每个人的数据都存放在独立分片中实现这一权利就只需对相应分片执行简单的数据导出和删除操作。数据驻留如果数据驻留法规要求某个租户的数据必须存放在特定司法管辖区区域感知数据库可以把该租户的分片分配到指定区域。逐步推出模式变更模式迁移参见 content/zh/ch3.md 的文档模型中的模式灵活性可以逐步推出每次只迁移一个租户在问题波及所有租户之前将其发现从而降低风险不过很难以事务方式完成。使用分片实现多租户的主要挑战这种做法假定每个租户的数据量都足够小能装进单个节点。如果某个租户大到一台机器容纳不下就还必须在租户内部继续分片于是问题又回到了为了可伸缩性而分片。如果小租户很多为每个租户单独建立分片的开销可能过大。可以把多个小租户合并到一个较大的分片里但随着租户成长又会遇到如何把它从一个分片迁移到另一个分片的问题。如果日后需要支持跨租户关联数据的功能跨多个分片连接数据会使这些功能更难实现。键值数据的分片目标、倾斜与热点假设有大量数据并且想要分片如何决定在哪些节点上存储哪些记录分片的目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分担数据和负载那么理论上10 个节点应该能够处理单个节点 10 倍的数据量和 10 倍的读写吞吐量暂时忽略复制。此外在添加或移除节点时我们希望能够**再平衡rebalance**负载使它均匀分布在增加后的 11 个节点上或移除节点后剩余的 9 个节点上。如果分片不公平某些分片承载的数据或查询比其他分片更多我们就称其为倾斜skew。倾斜会大幅降低分片的效果在极端情况下全部负载都可能集中到一个分片上10 个节点中有 9 个闲置瓶颈却卡在唯一繁忙的节点上。负载高得不成比例的分片称为热分片hot shard或热点hot spot如果某个键的负载特别高例如社交网络中的名人账号则称为热键hot key。因此需要一种算法以记录的分区键为输入指出这条记录属于哪个分片。在键值存储中分区键通常就是键或键的第一部分在关系模型中它可以是表中的某一列不一定非得是主键。为了缓解热点这种算法还必须便于再平衡。按键的范围分片有序、高效但易出热点一种分片方法是为每个分片指定一段连续的分区键范围从某个最小值到某个最大值就像纸质百科全书的各卷词条标题就是分区键如果知道各范围之间的边界就能轻松确定词条所在的分片。各段键范围不一定等宽因为数据本身很可能分布不均——第 1 卷收录以 A 和 B 开头的单词第 12 卷却收录以 T 到 Z 开头的单词。为了均匀分布数据分片边界必须根据数据进行调整。分片边界既可以由管理员手工选择也可以由数据库自动确定VitessMySQL 的分片层采用手动的键范围分片Bigtable、其开源版本 HBase、MongoDB 的范围分片选项、CockroachDB、RethinkDB 和 FoundationDB 则采用自动方式YugabyteDB 同时支持手动和自动拆分表分片。每个分片内部都按顺序存储键例如使用 B 树或 SSTable参见 content/zh/ch4.md。这样很容易执行范围扫描也可以把键当作联合索引在一次查询中获取多条相关记录参见 content/zh/ch4.md 的多维索引与全文索引。例如某个应用程序存储传感器网络的数据并以测量时间戳作为键范围扫描可以轻松取出某个月份的全部读数。键范围分片的缺点是如果大量写入集中在相邻的键上很容易形成热分片。例如键若是时间戳分片就对应不同时间范围每个月一个分片。遗憾的是如果传感器在产生测量值时就立即写入数据库所有写入都会落到同一个分片本月的分片中结果该分片可能被写入压垮其他分片却无所事事。为了避免传感器数据库出现这个问题键的第一部分就不能只用时间戳可以在每个时间戳前加上传感器 ID使键先按传感器 ID、再按时间戳排序。只要有许多传感器同时工作写入负载就会更均匀地分布到各个分片。代价是要获取多个传感器在某段时间内的测量值现在必须为每个传感器分别执行一次范围查询。再平衡键范围分片数据预拆分、拆分与合并首次建立数据库时还没有数据可供划定键范围。一些数据库如 HBase 和 MongoDB允许在空数据库上配置一组初始分片这称为预拆分pre-splitting但必须事先大致了解键将如何分布才能选出合适的键范围边界。此后随着数据量和写入吞吐量增长采用键范围分片的系统会把现有分片拆成两个或更多较小分片每个新分片都保存原键范围中的一段连续子范围这些较小的分片随后可以分散到多个节点上。如果大量数据被删除几个相邻且已经变小的分片也可能需要合并成一个较大的分片。这个过程类似于 B 树顶层发生的变化参见 content/zh/ch4.md 的B 树。对于自动管理分片边界的数据库分片的拆分通常由以下情况触发分片达到配置的大小例如 HBase 默认为 10 GB或者在某些系统中写入吞吐量持续高于某个阈值——即使一个热分片存储的数据不多也可能被拆分以便将其写入负载分布得更加均匀。键范围分片的优点是分片数量能够随数据量调整数据很少时只需少量分片开销很小数据量巨大时每个分片的大小仍会被限制在可配置的上限之内。缺点是拆分分片代价很高必须把其中的全部数据重写到新文件里类似于日志结构存储引擎的压实操作。需要拆分的分片往往本就处于高负载拆分开销还会雪上加霜甚至使它彻底过载。按键的哈希分片均匀但破坏有序性如果希望相邻但不同的分区键进入同一个分片键范围分片就很有用时间戳便是一个例子。如果不关心分区键是否相邻例如多租户应用中的租户 ID常见做法是先计算分区键的哈希值再将它映射到分片。好的哈希函数可以把倾斜的数据均匀打散。假设有一个接受字符串输入的 32 位哈希函数每输入一个新字符串它都会返回一个看似随机、介于 0 和 2³² − 1 之间的数即使输入字符串非常相似所得哈希值也会均匀分布在这个范围内相同输入总会产生相同输出。用于分片的哈希函数不必具备密码学强度例如 MongoDB 使用 MD5Cassandra 和 ScyllaDB 则使用 Murmur3。许多编程语言内置的哈希表哈希函数未必适合分片例如 Java 的Object.hashCode()和 Ruby 的Object#hash可能会让同一个键在不同进程中得到不同哈希值因此不能用于分片。哈希取模节点数简单但再平衡极低效算出键的哈希值之后该如何选择存储它的分片最直接的想法是让哈希值对系统中的节点数取模许多编程语言使用%运算符。例如hash(key) % 10会返回 0 到 9 之间的数假设有 10 个节点编号为 0 到 9这似乎是把键分配到节点的简单办法。模 N 方法的问题在于只要节点数 N 发生变化大多数键就必须从一个节点移到另一个节点。上图的例子中三个节点增加到四个再平衡之前节点 0 存储哈希值为 0、3、6、9 等的键加入第四个节点之后哈希值为 3 的键移到节点 3哈希值为 6 的键移到节点 2哈希值为 9 的键移到节点 1依此类推。模 N很容易计算却会导致极其低效的再平衡因为大量记录在节点之间进行了不必要的迁移。我们需要一种只移动必要数据的办法。固定数量的分片移动分片而非移动键一种简单而常用的解决方案是创建远多于节点数的分片再给每个节点分配多个分片。例如一个运行在 10 节点集群上的数据库可以从一开始就划分成 1,000 个分片每个节点分得 100 个。键会存入编号为hash(key) % 1,000的分片而系统另行记录每个分片存放在哪个节点上。如果向集群加入一个节点系统可以把现有节点上的一部分分片重新分配给新节点直到分片再次均匀分布移除节点时则反向执行同样的操作。在这种模型中只有完整的分片在节点之间移动成本低于拆分分片。分片的数量不会改变键所指定的分片也不会改变唯一改变的是分片所在的节点。这种变更并非即时——在网络上传输大量数据需要时间——所以传输期间发生的读写仍按原有的分片到节点映射处理。分片数量通常会选成一个因数很多的数字使数据集能够均匀分配到多种不同规模的节点集群中例如不必要求节点数是 2 的幂。甚至还可以照顾集群中的硬件差异给性能更强的节点分配更多分片让它们承担更大比例的负载。CitusPostgreSQL 的分片层、Riak、Elasticsearch 和 Couchbase 等系统都采用这种分片方法。只要首次创建数据库时能较准确地估计所需分片数它就很好用此后可以轻松增删节点不过节点数不能超过分片数。如果发现最初配置的分片数不合适——例如系统规模已经大到所需节点数超过分片数——就必须执行代价高昂的重新分片拆开每个分片、写出新文件并占用大量额外磁盘空间。有些系统不允许在数据库继续接受写入时重新分片因此很难在不停机的情况下改变分片数量。如果数据集总量变化很大例如开始时很小随后可能增长许多倍选择合适的分片数就很困难。由于每个分片包含总数据量的固定比例其大小会随集群中的数据总量同比增长。分片太大再平衡和从节点失效中恢复都会十分昂贵分片太小又会带来过多管理开销。分片大小不大不小、恰到好处时性能最佳但在分片数固定而数据集大小不断变化时这一状态很难维持。按哈希范围分片键范围分片的哈希化变体如果无法事先预测需要多少分片最好采用一种能让分片数量轻松适应工作负载的方案。前述键范围分片具备这一性质但大量写入集中到相邻键时容易形成热点。一种解决办法是将键范围分片与哈希函数结合使每个分片包含一段哈希值范围而不是一段键范围。上图展示了一个 16 位哈希函数返回 0 到 65,535 2¹⁶ − 1 之间的数实际使用的哈希通常至少有 32 位。即使输入键十分相似例如连续的时间戳它们的哈希值也会均匀分布在这个范围内。于是可以为每个分片分配一段哈希值范围例如 0 到 16,383 归分片 016,384 到 32,767 归分片 1依此类推。与键范围分片一样哈希范围分片也可以在分片过大或负载过重时将其拆分。这个操作依然昂贵但可以按需执行因此分片数量会随数据量调整而不是预先固定不变。它相对于键范围分片的缺点是无法高效地对分区键执行范围查询因为范围内的键如今散布在所有分片中。不过如果键由两列或更多列组成而分区键只是其中第一列仍然可以对第二列及之后的列高效执行范围查询只要范围查询中的所有记录拥有相同分区键它们就会落在同一个分片中。数据仓库中的分区与范围查询BigQuery、Snowflake 和 Delta Lake 等数据仓库也支持类似的索引方式只是术语不同。BigQuery 中分区键决定记录属于哪个分区聚簇列决定记录在分区内的排序方式Snowflake 自动把记录分配给微分区但允许用户为表定义聚簇键Delta Lake 同时支持手动与自动分配分区也支持聚簇键。对数据进行聚簇不仅能改善范围扫描的性能还能提高压缩率和过滤效率。YugabyteDB 和 DynamoDB 采用哈希范围分片MongoDB 也把它作为一种可选方案。Cassandra 和 ScyllaDB 则采用这种方法的一个变体它们把哈希值空间划分成若干范围范围数与节点数成正比图中每个节点有 3 个范围实际默认值是 Cassandra 每个节点 8 个、ScyllaDB 每个节点 256 个各范围之间的边界随机选定。这样有些范围会比其他范围大但每个节点拥有多个范围之后这些不均衡往往能相互抵消。添加或移除节点时系统会相应增删范围边界并拆分或合并分片。例如加入节点 3 之后节点 1 把自己两个范围中的一部分交给节点 3节点 2 也把一个范围中的一部分交给节点 3。这样新节点便能分得大致公平的一份数据同时避免在节点间传输不必要的数据。一致性哈希让键尽量留在原分片**一致性哈希consistent hashing**算法是一种哈希函数它把键映射到指定数量的分片并满足两个性质映射到各个分片的键数大致相等分片数量改变时尽可能少地在分片之间迁移键。注意这里的一致性与副本一致性参见 content/zh/ch6.md或 ACID 一致性参见 content/zh/ch8.md毫无关系它描述的是让一个键尽量留在原分片中的倾向。Cassandra 和 ScyllaDB 的分片算法与一致性哈希的原始定义相似此外还有多种其他一致性哈希算法最高随机权重highest random weight也称约会哈希rendezvous hashing和跳跃一致性哈希jump consistent hash。采用 Cassandra 的算法时加入一个节点会把少量现有分片拆成若干子范围采用约会哈希或跳跃一致性哈希时新节点得到的则是此前散布在所有其他节点上的一个个键。哪种方式更合适取决于具体应用。倾斜的工作负载与缓解热点一致性哈希可以保证键大致均匀地分布到各节点却不能保证实际负载也同样均匀。如果工作负载高度倾斜——某些分区键下的数据量远大于其他键或者某些键的请求速率远高于其他键——仍然可能有些服务器不堪重负另一些服务器却几乎闲置。例如在社交媒体网站上一个拥有数百万粉丝的名人做出某个举动可能引发一场活动风暴产生针对同一个键的大量读写分区键也许是该名人的用户 ID也许是众人正在评论的事件 ID。这种情况需要更加灵活的分片策略给热键单独开分片如果系统按键范围或哈希范围定义分片就可以把一个热键单独放进一个分片甚至给它分配一台专用机器。应用层补偿倾斜例如在键的开头或末尾添加随机数。只需两位十进制随机数就能把针对该键的写入均匀拆成 100 个不同的键让它们分布到不同分片。不过写入分散到不同键之后读取就得付出额外代价必须从全部 100 个键读取数据再把结果合并起来。热键分散后每个分片承受的读取量并没有减少降低的只有写入负载。这种技术还需要额外的记录工作只有少数热键值得添加随机数对于写入吞吐量很低的绝大多数键这样做只会徒增开销。因此还需要记录哪些键已被拆分并设计一个流程把普通键转换成需要特殊管理的热键。负载还会随时间变化使问题更加复杂某条突然爆火的社交媒体帖子可能连续几天承受很高负载之后又很快归于平静。此外有些键是写入热点有些则是读取热点二者需要采用不同的处理策略。一些系统尤其是面向大规模场景设计的云服务能够自动处理热分片例如 Amazon 把相关机制称为热度管理heat management或自适应容量adaptive capacity这些系统的具体工作方式超出了本书的讨论范围。运维自动还是手动再平衡关于再平衡有一个重要问题自动还是手动进行有些系统无需人工介入会自动决定何时拆分分片、何时把分片从一个节点迁移到另一个节点另一些系统则要求管理员显式配置分片。两者之间也有折中方案例如 Couchbase 和 Riak 会自动生成建议的分片分配但必须由管理员确认提交后才会生效。全自动再平衡很方便日常维护所需的运维工作更少这样的系统甚至可以自动伸缩以适应工作负载的变化。DynamoDB 等云数据库宣称能够在几分钟内自动增删分片应对负载的大幅升降。然而自动分片管理也可能难以预测再平衡代价很高因为它要重新路由请求并在节点间迁移大量数据。如果处理不够谨慎这一过程可能使网络或节点过载拖累其他请求的性能。系统在再平衡期间还必须继续处理写入如果已经接近最大写入吞吐量分片拆分的速度甚至可能赶不上新写入到达的速度。这种自动化机制如果再与自动失效检测结合可能十分危险假设某个节点过载暂时无法及时响应请求其他节点据此断定它已经失效于是自动对集群进行再平衡把负载从该节点移走。这会给其他节点和网络施加额外负载让局面进一步恶化甚至引发级联失效其他节点也相继过载并被错误地判定为已经宕机。出于这个原因让人参与再平衡过程是一件好事——这比全自动流程慢但有助于防止运维意外。请求路由如何找到正确的节点把数据集分片到多个节点后下一个问题是如果想读写某个特定的键怎样知道应该连接哪个节点哪个 IP 地址和端口这个问题称为请求路由request routing与 content/zh/ch5.md 讨论的*服务发现service discovery*十分相似。二者最大的区别在于运行应用代码的服务实例通常是无状态的负载均衡器可以把请求发给任意实例而在分片数据库中某个键的请求只能交给持有该键所在分片副本的节点处理。因此请求路由必须了解键到分片、以及分片到节点的映射。概括来说有以下几种办法允许客户端连接任意节点例如通过轮询负载均衡器。如果该节点恰好持有请求涉及的分片就直接处理请求否则它把请求转发给正确的节点收到响应后再转交给客户端。先把所有请求发送到一个路由层由路由层判断哪个节点应当处理每个请求再相应地转发。路由层本身并不处理请求只充当一个能够感知分片的负载均衡器。让客户端了解分片方式以及分片到节点的分配关系。这样客户端无须经过任何中间层就能直接连接到正确的节点。在所有情况下都有一些关键问题由谁决定每个分片应当放在哪个节点最简单的办法是由单一协调者来决定但如果运行协调者的节点宕机怎样让协调者具备容错能力如果协调者能够故障切换到另一个节点又该如何防止发生脑裂参见 content/zh/ch6.md 的处理节点故障让两个协调者作出相互矛盾的分片分配负责路由的组件可以是某个数据库节点、路由层或客户端怎样得知分片到节点的分配发生了变化分片从一个节点迁移到另一个节点时会有一段切换期新节点已经接管但发往旧节点的请求可能仍在途中。应当如何处理这些请求许多分布式数据系统依靠ZooKeeper、etcd 等独立协调服务来记录分片分配。这些服务使用共识算法参见 content/zh/ch10.md实现容错并防止脑裂每个节点都在 ZooKeeper 中注册ZooKeeper 维护分片到节点的权威映射路由层或能够感知分片的客户端等其他参与者可以订阅 ZooKeeper 中的信息。只要分片易主或有节点加入、退出ZooKeeper 就会通知路由层使其路由信息保持最新。具体系统举例HBase 和 SolrCloud 使用 ZooKeeper 管理分片分配Kubernetes 使用 etcd 记录每个服务实例的运行位置MongoDB 的架构与之相似不过它依靠自有的*配置服务器config server*实现并以mongos守护进程作为路由层Kafka、YugabyteDB 和 TiDB 则使用内置的 Raft 共识协议实现这项协调功能。Cassandra、ScyllaDB 和 Riak 采用另一种办法节点之间通过**流言协议gossip protocol**传播集群状态的变化。它提供的一致性比共识协议弱得多因而可能出现脑裂使集群的不同部分对同一个分片持有不同的节点分配。无主数据库可以容忍这种情况因为它们本就只提供较弱的一致性保证参见 content/zh/ch6.md 的仲裁一致性的局限。无论使用路由层还是把请求发送给随机节点客户端仍然要先找到可供连接的 IP 地址。IP 地址的变化没有分片到节点的分配那么频繁因此通常用 DNS 就足够了。以上请求路由主要关注如何为单个键找到对应分片最适用于分片的 OLTP 数据库。分析型数据库通常也会分片但其查询执行方式截然不同查询一般不是在单个分片中执行而是要并行聚合并连接来自许多分片的数据。这类并行查询执行技术将在 content/zh/ch11.md 的JOIN 与 GROUP BY中讨论。分片与二级索引本地索引与全局索引到目前为止讨论的分片方案都要求客户端知道待访问记录的分区键。这在键值数据模型中最容易做到分区键是主键的第一部分或整个主键因此可以据此确定分片并把读写请求路由到负责该键的节点。涉及二级索引时情况会复杂得多另见 content/zh/ch4.md 的多列索引与二级索引。二级索引通常不能唯一标识一条记录而是用来搜索某个特定值出现在哪里例如查找用户123的所有操作、所有包含单词hogwash的文章或所有颜色为red的汽车。键值存储通常没有二级索引但它是关系数据库的基础能力在文档数据库中也十分常见更是 Solr、Elasticsearch 等全文检索引擎的立身之本。二级索引的问题在于它无法干净利落地映射到分片。对带有二级索引的数据库进行分片主要有两种办法本地索引和全局索引。本地二级索引按文档分区假设运营一个二手车交易网站每条车辆信息都有唯一 ID并以该 ID 作为分区键进行分片例如 ID 0 到 499 归分片 0ID 500 到 999 归分片 1。如果要让用户按颜色与品牌筛选车辆就需要在color和make上建立二级索引文档数据库中是字段关系数据库中则是列。声明索引后数据库会自动维护它每增加一辆红色汽车所在分片就会自动把它的 ID 加入索引条目color:red对应的 ID 列表。这种 ID 列表在 content/zh/ch4.md 中称为倒排列表postings list。在这种索引方式中每个分片都完全独立各自维护自己的二级索引只覆盖本分片中的记录。每次写入数据库——添加、删除或更新记录——只需处理包含该记录的分片。因此这种二级索引称为本地索引local index在信息检索领域它也称为按文档分区的索引document-partitioned index。读取本地二级索引时如果已经知道目标记录的分区键就只需在对应分片上搜索如果只想获得部分结果而不要求全部也可以把请求发给任意分片。但是如果需要全部结果又事先不知道这些记录的分区键就必须把查询发送到所有分片再合并返回结果因为匹配的记录可能散布在每个分片中。警告如果数据库只支持键值模型你也许会想在应用代码中建立值到 ID 的映射自行实现二级索引。如果选择这条路务必万分小心确保索引与底层数据始终一致。竞态条件和间歇性写入失败有些变更保存成功另一些却没有很容易让两者失去同步——参见 content/zh/ch8.md 的多对象事务的需求。这种查询方式会让二级索引上的读取查询相当昂贵即使并行查询所有分片也很容易出现尾部延迟放大参见 content/zh/ch2.md 的响应时间指标的应用。它还会限制应用的可伸缩性增加分片能容纳更多数据但如果每次查询仍要由所有分片处理查询吞吐量并不会随之提高。尽管如此本地二级索引依然应用广泛MongoDB、Riak、Cassandra、Elasticsearch、SolrCloud 和 VoltDB 都采用这种索引。全局二级索引按词项分区除了让每个分片各自维护本地二级索引也可以构建一个覆盖所有分片数据的全局索引global index。不过不能只把这个索引存放在单个节点上否则它很可能成为瓶颈使分片失去意义。因此全局索引本身也必须分片但可以采用与主键索引不同的分片方式。下图展示了一种可能的形式来自所有分片的红色汽车 ID 都列在索引的color:red条目下索引本身则经过分片以字母a到r开头的颜色归分片 0以s到z开头的颜色归分片 1。汽车品牌索引也以类似方式分片边界位于f与h之间。这种索引也称为按词项分区term-partitioned。回顾 content/zh/ch4.md 的全文检索在全文检索中*词项term*是文本中可供搜索的关键字这里把它推广为二级索引中任何可供搜索的值。全局索引以词项作为分区键因此查找某个词项或值时可以直接确定需要查询哪个分片。和前面一样每个分片可以包含一段连续的词项范围也可以根据词项的哈希值把词项分配到各个分片。全局索引的优点是如果查询只有一个条件如color red只需读取一个分片就能取得倒排列表。不过如果想要的不只是 ID 而是完整记录仍需读取负责存储这些 ID 的所有分片。如果查询包含多个条件或词项例如搜索某种颜色且属于某个品牌的汽车或搜索同一段文本中同时出现的多个单词这些词项很可能分属不同分片为了计算两个条件的逻辑 AND系统必须找出同时出现在两个倒排列表中的 ID。倒排列表较短时并不难但如果列表很长通过网络传输它们再计算交集速度就可能很慢。全局二级索引的另一个难题是写入比本地索引复杂写入一条记录可能影响索引的多个分片文档中的每个词项都可能位于不同分片。因此二级索引很难与底层数据保持同步。一种办法是使用分布式事务以原子方式更新保存主记录的分片及其二级索引分片参见 content/zh/ch8.md。CockroachDB、TiDB 和 YugabyteDB 都使用全局二级索引DynamoDB 则同时支持本地和全局二级索引。在 DynamoDB 中写入会异步反映到全局索引因此从全局索引读到的结果可能是陈旧的类似于 content/zh/ch6.md 的复制延迟的问题。尽管如此如果读取吞吐量高于写入吞吐量而且倒排列表不太长全局索引仍然很有用。总结分片方案选择的核心权衡在本章中我们探讨了将大数据集划分成更小子集的不同方法。数据量非常大的时候在单台机器上存储和处理不再可行而分片则十分必要。分片的目标是在多台机器上均匀分布数据和查询负载避免出现热点这需要选择适合数据的分片方案并在节点加入或移除时重新平衡分片。两种主要的分片方法键范围分片键按顺序排列每个分片拥有从某个最小值到某个最大值之间的所有键。有序存储的优点是能够高效执行范围查询但如果应用经常访问排序位置彼此接近的键就可能形成热点。采用这种方法时分片过大之后通常会把键范围拆成两个子范围从而动态地再平衡分片。哈希分片先对每个键应用哈希函数每个分片拥有一段哈希值范围也可以采用其他一致性哈希算法把哈希映射到分片。这种方法破坏了键的顺序使范围查询效率降低却可能让负载分布得更加均匀。按哈希分片时通常会预先创建固定数量的分片给每个节点分配多个分片增删节点时再把整个分片从一个节点迁移到另一个节点。也可以像键范围分片那样拆分分片。常见做法是以键的第一部分作为分区键即用来确定分片再按键的其余部分对分片内的记录排序。这样对于分区键相同的记录仍然可以高效执行范围查询。分片与二级索引的相互作用也有两种方法本地二级索引二级索引与主键及其值存储在同一个分片。写入时只需更新一个分片但查找二级索引时必须读取所有分片。全局二级索引根据索引值采用另一套分片方式。二级索引条目可以引用来自主键任意分片的记录。写入记录时可能需要更新多个二级索引分片但读取倒排列表时只需访问一个分片获取实际记录仍然要读取多个分片。最后我们还讨论了如何把查询路由到正确的分片以及如何通过协调服务记录分片到节点的分配关系。从设计上说每个分片大体独立运行——正因如此分片数据库才能伸缩到多台机器。然而需要写入多个分片的操作会变得很棘手例如一个分片写入成功另一个分片却失败时会怎样content/zh/ch8.md 将回答这个问题。延伸阅读原文档 content/zh/ch7.md 末尾附有 34 条高质量参考文献覆盖了 Citus 的 PostgreSQL 分片实践、FoundationDB 论文、Slack 使用 Vitess 的伸缩经验、Cassandra 虚节点与令牌分配算法、一致性哈希原始论文、跳跃一致性哈希、DynamoDB 论文、ZooKeeper 与分布式协调等主题是深入学习分片各子主题的绝佳索引本仓库的 content/en/ch7.md 提供英文原版对照。赞分享文档教程【免费下载链接】ddia《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译项目地址https://gitcode.com/gh_mirrors/dd/ddia点击查看免费下载相关推荐《设计数据密集型应用》第 7 章精读分片Sharding——从分区键选择、哈希策略到请求路由的分布式扩展实战指南《设计数据密集型应用》第 7 章精读分片Sharding——从分区键选择、哈希策略到请求路由的分布式扩展实战指南 本篇技术指南以《Designing Da文档教程DDIA 分片Sharding深度解析键范围与哈希分片、再平衡与请求路由实战指南DDIA 分片Sharding深度解析键范围与哈希分片、再平衡与请求路由实战指南 本篇指南以《设计数据密集型应用》DDIA第二版第七章为核心骨架系统文档教程GICv3 ITS翻译表从静态中断墙到动态路由网的架构重构GICv3 ITS翻译表从静态中断墙到动态路由网的架构重构 当服务器上的NVMe SSD阵列同时发起数百个并发I/O请求时传统的中断控制器就像一座只有102操作系统内核驱动驱动开发虚拟化嵌入式网络存储上一篇如何在openEuler系统部署LiteView浏览器30分钟完成编译与运行下一篇QEMU性能优化终极清单20个技巧提升虚拟机运行效率创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考