aiwiki.page
中文

分片

分片将数据或计算状态划分为独立管理的分区,以将存储、处理和工作负载分散到多个资源上。

30 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
数据库分布式计算数据库管理系统数据库复制主键哈希函数元数据负载均衡分片

分片是一种将数据集或计算状态划分为较小单元的技术,这些单元称为分片,可以分别存储和处理。在最常见的应用中,数据库将不同的记录子集分布到多台服务器上,同时向应用程序呈现单一的逻辑服务。每个分片只负责一部分数据,而不是保存数据的完整副本。

分片使系统能够突破单台机器在存储容量、写入吞吐量或处理能力方面的限制。它是分布式计算中的一项核心技术,但也带来了协调问题:请求必须到达正确的分片,跨分片操作必须保持预期的语义,有时还需要在系统保持可用的同时迁移数据。分片的效果与其说取决于服务器的数量,不如说取决于数据分布方式与工作负载的匹配程度。

分片一词也用于搜索系统、分布式缓存、区块链和机器学习基础设施。这些应用都遵循分摊职责的原则,但划分的对象以及分区交互时所需的保障各不相同。

基本原理与历史发展

数据库分片通常是水平分区的一种形式:不同的行或记录归属不同的分区,但其逻辑结构保持不变。例如,一张客户表可以将编号为 1–1,000,000 的客户放在一个分片中,将编号为 1,000,001–2,000,000 的客户放在另一个分片中。垂直分区则是将不同属性分开存储,例如将个人资料与大型文档内容放入不同的存储结构中。将应用程序拆分为客户、库存和计费等独立服务,属于功能分解;此后,每个服务还可以对自身的数据进行分片。

分区与分片是相互关联但并不等同的术语。数据库管理系统可以在单台服务器内对表进行分区,以简化维护或提高查询执行效率。分片通常意味着各分区可以部署在独立配置的资源上,一般是不同的机器。不同产品对术语的用法有所不同:一个分片可能指一个逻辑分区、一个物理存储单元,也可能指一组副本。因此,分片数量不一定等于服务器数量。

分片也不同于数据库复制。复制维护同一份信息的多个副本,而分片将不同的信息分配到不同的分区。系统可以结合这两种技术,将数据划分为 100 个分片,并为每个分片维护三个副本。复制可以提高可用性和读取能力,而分片可以扩大总存储容量并分散写入负载。两者都不会自动带来对方的优势:增加副本不一定能减轻单个写入主节点的负担,而将没有副本的数据分散存储,会增加一些一旦丢失就可能导致部分记录不可用的组件。

这些基本思想早在“分片”(sharding)一词广泛使用之前就已出现。20 世纪 70 年代和 80 年代,分布式关系数据库与无共享并行数据库就已开始探索数据分区。1984 年在威斯康星大学麦迪逊分校启动的 Gamma 数据库机项目,是分区并行查询处理的一个重要实例。后来,互联网规模的系统使分区成为日常运维中需要考虑的问题。Google 于 2006 年发表的 Bigtable 论文描述了将表划分为 tablet 的方式,Amazon 于 2007 年发表的 Dynamo 论文则介绍了去中心化的键放置与复制机制。

这些发展并未形成一种通用架构。有些系统在数据库引擎内部实现分区,另一些则在应用程序代码或中间件中实现。现代分布式关系数据库通常会自动完成数据放置、复制和事务协调,而由应用程序管理的分片则将其中更多的责任交给开发者。这些架构的共同目标,是分散主要资源需求,同时避免引入更大的协调瓶颈。

分区策略与分片键选择

分片键决定一条记录由哪个分区负责。它可以是主键、租户标识符、时间戳,也可以是复合值。分片键的选择会影响数据分布、查询局部性、事务边界,以及后续扩容的难度。能够均匀分布存储数据量的键,未必能均匀分布请求:即使每个分片包含的客户数量大致相同,也可能有一个客户产生了大部分流量。

范围分区将连续的键值区间分配给各个分片。例如,一个分片可能包含某个时间分界点之前的记录,另一个分片则包含随后一个月的记录。这种方式保留了键的顺序,而且相关的键集中在少量相邻分区中,因此能够支持高效的范围扫描。它的主要难点是数据倾斜。单调递增的键可能使几乎所有新写入都流向最后一个区间。拆分历史区间并不能消除这个不断移动的写入热点,除非同时调整当前写入的分布方式。

哈希分区对键应用哈希函数,再将结果映射到分区。对于具有 nn 个分片的系统,一种简单方案是

s(k)=h(k) mod n.s(k)=h(k)\bmod n.

如果哈希函数选择得当,且不同键的数量足够多,这种方式通常比直接按分布不均的业务属性分区更能均匀地分布记录。不过,原本相邻的键不再彼此相邻,因此查询某个客户编号区间或时间戳区间时,可能需要访问所有分片。在这个简单公式中,改变 nn 还会使大量现有记录的目标分片发生变化,因此,如果不增加一层间接映射,它就不适合低成本的渐进式扩容。

一致性哈希能够在参与节点发生变化时减少重新分配的键。在经典的环形模型中,键和节点位置处于同一个环形哈希空间内,每个键都分配给沿环向前遇到的下一个节点位置。虚拟节点让每台物理机器拥有多个位置,从而改善分布,并适应容量不等的机器。在理想的均匀分布条件下,向 nn 个同等节点中添加一个节点,大约会移动 1/(n+1)1/(n+1) 的键。另一些系统则不使用环,而是采用固定的逻辑桶,以及可变的桶到服务器映射。

基于目录的方案和分层方案提供了更大的灵活性。目录可以明确地将每个租户映射到一个分片,从而让大型租户获得专用资源。复合设计可以先选择地理区域,再在该区域内对客户标识符进行哈希。这类安排以更多的元数据和控制平面职责为代价,换取了比简单放置公式更灵活的分配方式。键的高基数、工作负载均衡、局部性和归属稳定性都是理想特性,但它们可能相互冲突;因此,分片键的选择是一项针对具体工作负载的设计决策,而不是纯粹的统计分析。

路由、元数据与逻辑归属

分片系统需要一种路由机制,将逻辑请求转换为与正确分区的通信。在客户端路由中,客户端库获取分区映射,并直接向存储服务器发送请求。这避免了必须经过代理中转的一跳,但也使路由逻辑分散到各个应用中。在基于代理的路由中,应用连接到网关,由网关转发请求。数据库内置的路由可以使应用基本感知不到数据的分布,但这种透明性并不能消除底层的网络和协调开销。

路由元数据通常会区分逻辑归属与物理位置。即使副本在不同机器之间迁移,逻辑分片标识符也可以保持不变。目录可以记录键范围边界、副本地址、当前负责写入的主节点,以及归属版本。将这些概念分开,可以在不改变应用所用键的情况下调整容量,也允许大量小型逻辑分片共享数量较少的物理服务器,从而使负载均衡能够迁移选定的单元,而不必迁移整台机器的工作负载。

客户端和路由器通常会缓存放置信息,以免每次请求都查询中央目录。迁移或主节点变更后,缓存的信息就会过时。系统可以通过重定向、明确的版本过期错误、刷新元数据,或由原归属节点转发请求等方式处理这种情况。版本号或纪元用于区分先后不同的归属配置。服务器收到针对旧配置的请求时,不能仅仅因为旧路由器仍认为它拥有处理权限,就接受存在冲突的写入。

因此,放置目录也是保障系统正确性所必须涵盖的一部分。如果相互竞争的控制器将同一个可写范围分配给不同的归属节点,就可能导致状态分歧。许多系统使用分布式共识、租约或多种机制的组合来保障配置变更的安全。租约在特定的时序假设下,授予一段有限时间内的权限;纪元则可以充当隔离令牌,使下游组件拒绝来自已被替代的归属节点的操作。这些机制需要与存储层谨慎集成,而不能仅仅依赖路由约定。

路由还与应用接口相互影响。包含租户标识符和记录标识符的请求,可能可以立即确定其目标位置;而仅包含电子邮件地址的请求,则可能需要额外查询。有些系统将路由信息编码进标识符,另一些系统则维护全局目录。当记录的归属发生变化时,这两种方式都会产生成本。通过间接寻址,可以将稳定的外部标识符与可变的内部放置位置分离,但这次额外查询也会成为另一个需要缓存、复制和维护的依赖环节。

查询执行、索引与数据局部性

当路由层能够确定少量相关分片时,查询成本最低。分区裁剪利用谓词和分区元数据,排除不可能包含匹配记录的分片。如果订单表按客户标识符分片,查询某一客户的订单通常只需访问一个分片。而查询价格高于某个阈值的所有订单,则可能需要访问全部分片,除非存在其他访问路径。这两种查询的 SQL结构化查询语言 语句看起来可能很相似,但分布式执行成本却可能相差很大。

散播—汇集查询将任务发送到多个分片,再合并各分片的响应。简单的聚合操作通常很容易拆分:每个分片可以计算记录数和局部总和,再由协调节点将其合并。平均值必须根据总和与记录数重新计算,而不能对各分片的平均值直接取不加权的平均。精确的去重计数、百分位数以及某些统计运算需要维护更多状态,或进行更多通信。如果近似方法的误差保证符合应用需求,就可以用它们降低这类成本。

连接操作对数据放置尤其敏感。如果客户和订单使用相同的客户键进行分区,且对应分区位于同一节点上,许多连接就可以在本地执行。如果相关行位于彼此不对应的分片上,系统可能需要通过网络重新分布一侧或两侧的输入数据。另一种方法是将足够小的表广播给所有参与计算的工作节点。查询优化器必须比较数据量、可用索引、网络成本和预期选择率,而它所依赖的分布式数据统计信息往往并不完善。

数据库索引可以是局部索引,也可以是全局索引。局部索引只涵盖单个分片中的记录,更容易随本地写入操作一同维护。但仅凭局部索引,无法确定任意给定索引值所在的分片。全局索引覆盖整个逻辑数据集,通常采用自身独立的分区方案。它可以加快对非分片键的查找,但此时一次更新可能既涉及基础记录所在的分片,也涉及索引分片。强制保证全局唯一性也面临同样的根本困难:所有相互竞争的插入操作都必须汇集到一个能够检测冲突的权威节点或服务。

结果汇总还会带来其他约束。对于全局前 kk 项查询,只要各分片的排序语义一致,每个分片就可以返回本地的前 kk 项,再由协调节点合并这些候选项。基于偏移量的深度分页可能导致反复扫描,并产生大量中间结果。键集分页可以减少这类开销,但需要稳定的排序方式,以及用于继续查询的状态。即使每个分片的响应都很快,最慢的参与节点仍可能主导整体延迟,因此,扇出宽度是查询规划的重要考量,而不只是一个实现细节。

事务与跨分片一致性

局限于单个分片内的数据库事务,通常可以使用与传统数据库相同的并发控制和恢复机制。一旦事务需要更新多个分片,系统就必须协调各分片的执行结果。账户转账可以说明这一问题:在一个分片上扣款、在另一个分片上入账,不应在发生故障后只留下其中一项持久化变更。分片改变了易于实现原子执行的物理边界。

两阶段提交是一种用于在多个参与者之间实现原子提交的标准协议。在准备阶段,每个参与者判断自己能否提交,并将必要状态持久化记录下来。如果所有参与者都投票同意提交,协调者就记录并分发提交决定;否则,事务中止。参与者在等待结果期间,可能需要持有锁或保留数据版本。如果协调者在关键时刻发生故障,已完成准备的参与者可能无法独立作出决定,只能等待提交或中止的决定变得可用。复制协调者和参与者的状态可以提高容错能力,但原子提交仍然需要通信和恢复规则。

原子提交并不等同于事务隔离。系统即使能够确保所有写入一起提交,也仍可能出现并发事务引发的异常。要实现可串行化执行,就需要采用分布式锁、验证或基于时间戳的排序等并发控制策略,覆盖相关的读写依赖关系。同样,一致的跨分片快照也需要某种机制,确保所有读取都对应于相容的逻辑时点。除非正确处理了可见性和事务依赖关系,否则仅仅分配时间戳并不能解决这个问题。

因此,不能仅凭数据库是否采用分片,就推断其是否具备ACID特性。有些分片系统提供分布式可串行化事务;另一些系统仅支持单个分区内的事务,或在跨分区操作中提供较弱的保证。CAP定理讨论的是:在网络分区期间,无法同时保证该定理所定义的一致性和可用性。它并不是说,分片数据库始终必须在所有有用的一致性形式与正常运行时的可用性之间二选一,也不直接用于划分事务隔离级别。

应用有时会用Saga模式取代单个分布式事务,即执行一系列已提交的本地事务,并配套补偿操作。例如,一个预订流程可能先预留库存,再进行支付授权,最后创建发货单。如果后续步骤失败,先前的步骤可能需要通过取消或退款操作来补偿。补偿是一项业务操作,不一定能完美还原此前的状态。此类设计需要明确规定中间状态、重试行为和对账机制。它们将一部分一致性管理职责转移到了应用中,而不是让跨分片依赖关系消失。

复制、故障与可用性边界

生产系统通常会为每个分片建立多个副本,避免其数据仅由一台机器持有。采用复制机制的分片可以由一个领导者确定写入顺序,再由跟随者复制其日志;也可以采用由多个副本共同参与接受操作的协议。Raft共识算法就是用于维护复制状态的一种共识协议。许多分布式数据库为每个键范围或分片运行独立的复制组,因此,同一台机器可能承载某些组的领导者副本,同时承载另一些组的跟随者副本。

复制策略决定了分片能够容忍哪些故障。在一个由三个投票副本组成、基于多数派的共识组中,通常需要两个投票副本可用才能继续推进操作;这样的组可以容忍一个投票副本不可用。这一结论以协议正确运行、且不存在模型之外的故障为前提。如果将三个副本全部放在同一台机器上,就无法达到预期的机器故障防护效果。将它们放在同一处设施内,或许能够抵御单台服务器故障,却无法抵御整处设施失效。

分片会形成多个可用性边界。如果一个分片不可用,仅访问健康分片的请求仍可能继续执行。然而,只要任何必需的参与方不可用,跨分片事务或查询就可能失败。在简化假设下,若所需的 mm 个分片各自以概率 aa 独立可用,则所有分片均可用的概率为 ama^m。实际故障往往存在相关性,因此,这个表达式不能作为通用的可靠性预测,但它说明了为什么大范围扇出会增加操作受到组件不可用影响的风险。

故障检测和恢复本身也可能造成负载骤增。选举新领导者、重建副本、重放日志和预热缓存,都会消耗原本可用于处理请求的资源。如果发生故障的服务器承载了许多分片的副本,替换该服务器就可能触发集群范围内的大量数据复制。恢复流量必须与前台业务流量共享资源,而副本的放置方式会影响一次故障是否会使少数仍在运行的机器过载。因此,充足的富余容量是容错能力的一部分,而不仅仅是资源配置上的便利。

复制也不同于数据备份。错误的删除操作或造成数据损坏的应用更新,可能会传播到所有在线副本。要恢复到先前的状态,必须保留快照、日志或其他恢复资料。对于分片数据库,如果将各个分片分别恢复到任意时刻,就可能得到一种在逻辑上从未存在过的状态组合,尤其是在事务跨越分片边界的情况下。协调一致的快照、能够识别事务的日志重放,以及有明确记录的恢复点,都是分布式数据灾难恢复的重要组成部分。

拆分、迁移与在线重新分片

分片很少是一次性的划分。数据量会增长,租户的行为会变化,机器会被替换,原本适用的分片键也会导致分布失衡。重新分片会改变记录的分区方式或归属。它可能指将现有分片迁移到另一台服务器、将较大的范围拆分为多个较小范围、合并小分区,或使用不同的键对数据集重新分区。这些操作在成本及其对路由的影响上存在显著差异。

迁移一个保持不变的分片,比改变分区函数更简单,因为记录的归属在逻辑上基本不变。典型的在线迁移会先将快照从源端复制到目标端,再传输复制期间发生的变更。这些变更可以由预写日志或变更数据捕获流提供。目标端充分追上源端的进度后,系统便会切换归属,并将新操作路由到目标端。旧副本会暂时保留,或者在协议确认不再需要它之后被删除。

切换是对正确性要求最高的阶段。从最后一次复制的更新到新归属方接受首个操作之间,写入不能悄无声息地丢失。常见技术包括短暂暂停写入、设置协调式归属切换屏障、交接日志位置,或依据带版本号的归属信息转发请求。对于已经发出但尚未完成的请求,也需要明确的处理规则。否则,重试超时请求可能导致同一操作执行两次,因此,除了常规的路由更新,还可能需要请求标识符和去重机制。

更改分片键的要求更高,因为每条记录都可能被分配到不同的目标端。应用也可能依赖原有的数据局部性:原本在本地完成的事务可能变成分布式事务,原本只访问一个分片的查询可能变成分散查询后汇总结果的操作。过渡方案有时会同时读取新旧两种布局,或暂时同时维护两者。未经协调的双写并不安全,因为一端可能接受了更新,另一端却写入失败。可靠的迁移需要一个持久化的权威数据源,在必要时按顺序传播变更,并通过校验发现缺失或不一致的记录。

迁移成本既取决于数据集大小,也取决于持续发生的数据变更。如果目标端接收复制数据的速率仅略高于源端的数据变更速率,那么追上源端进度可能需要很长时间。复制还会争用磁盘带宽、网络容量和缓存空间。因此,自动化系统会对迁移进行限速、限制并发迁移的数量,并将副本布局纳入考虑。在存储结构允许的情况下,范围拆分在元数据层面的成本通常很低,但重新分布拆分后的范围,仍然需要移动数据或改变对数据的物理访问方式。

容量规划、热点与运维控制

分片在理想情况下的吸引力在于线性扩展:性能相当的服务器数量翻倍,所能承载的数据量或工作量也随之翻倍。但实际吞吐量会受到负载不均、共享依赖和协调开销的限制。如果工作负载中有比例为 ff 的部分本质上只能串行执行,而其余部分可以在 pp 个工作单元上实现完全并行,那么根据阿姆达尔定律,加速比的上限为

S(p)=1f+(1−f)/p.S(p)=\frac{1}{f+(1-f)/p}.

全局标识符服务、事务协调器、元数据存储或争用激烈的记录,都可能成为串行执行的部分。网络通信和额外的协调还可能进一步降低性能。

衡量分片是否均衡,不能只看字节数或记录数。重要维度还包括请求速率、写放大、处理器时间、内存占用、磁盘操作量和复制流量。一个存放小型但频繁更新的记录的分片,其资源消耗可能高于另一个存放大型但很少被访问的对象的分片。容量规划还需要区分平均利用率与短时峰值。即使集群的平均利用率留有充足余量,当某个分片达到饱和,或许多后台任务同时启动时,仍可能出现严重的延迟。

热点键是一种特殊的限制。如果对同一个逻辑键的所有操作都必须串行执行,那么将该键迁移到性能更强或负载更低的服务器上,也只能在一定程度上改善情况。拆分该键所在的键范围,并不能拆分这个键本身。有些工作负载允许将一个逻辑计数器分散到多个子键上,并在读取时合并结果;另一些则要求严格的顺序,因而无法这样拆解。读副本和缓存可以减少重复读取,但并不会自动消除写入争用,也不能保证更新立即可见。

运维控制措施包括请求准入限制、租户配额、有界请求队列、迁移限速和负载丢弃。这些措施在共享服务中尤为重要,否则某个租户的突发流量就可能影响其他无关用户。可观测性必须将逻辑查询与其分布式执行过程关联起来:各分片的延迟、队列深度、主节点变更、复制延迟和扇出程度,比单一的集群整体平均值更有参考价值。尾延迟十分重要,因为一个用户请求可能需要等待多个分片响应中最慢的那一个。

安全策略和数据放置策略会带来额外约束。地域限制可能会限定哪些服务器可以存放特定记录,而访问控制必须在数据归属发生变化时仍然保持正确。分片边界本身并不构成安全边界;共享进程、凭据、备份和管理工具都可能跨越这些边界。同样,如果副本、日志或导出的数据存储在其他地方,仅仅指定一个按地域划分的分片键,并不能满足数据隐私方面的义务。数据在运行环境中的放置位置,是一项贯穿数据全生命周期的端到端属性。

事务型数据库之外的用途

搜索引擎通常将文档集合划分为多个分片,每个分片维护一个本地倒排索引。查询被分发到相关分片,各分片返回候选文档及其评分,再进行合并。副本可以处理更多查询,也可以在其他副本发生故障时接替其工作。相关性评分可能依赖整个文档集合的统计信息,例如文档频率,因此,使用分片本地统计信息与使用全局协调的统计信息,可能得到不同的排序结果。增加分片数量可以提高并行度,但也会增加协调成本、每个分片的开销,以及获得完整结果所需的响应数量。

分布式缓存和键值存储通过对键进行分区,扩展内存容量和请求吞吐量。例如,Redis Cluster 将键映射到 16,384 个哈希槽,再将这些槽分配给集群节点。哈希标签允许将选定的键映射到同一个槽,从而支持要求相关键位于同一位置的操作。哈希槽这一层将逻辑放置单元的数量与服务器数量解耦。这体现了一种通用模式:采用固定或独立管理的分区空间,可以简化数据迁移,而无须在每个应用键中暴露物理服务器的身份。

在流处理中,分区往往决定由哪个工作进程负责某个键的状态。同一账户或设备的事件可以被路由到同一个分区,让工作进程在本地维护聚合结果,并在系统提供的顺序保证范围内按序处理这些事件。增加工作进程时,可能既要转移状态的管理权,也要迁移累积的状态。输入分区的数量及其分布可能限制并行度,而高度活跃的键也会造成数据库中常见的热点问题。协调恢复时,必须将状态快照与输入日志中的位置对应起来。

区块链分片将分区机制应用于数据存储、交易执行或验证职责。其核心难点不仅在于路由:参与者还必须获得充分保证,确信其他分片的数据可用,且其状态转换有效。跨分片转账需要相应协议,以便在适用的对抗模型下防止资产归属不一致或双重支付。有些设计对执行过程进行分区,另一些则侧重于将数据可用性职责分散出去。这些是“分片”一词的不同用法;一个被称为采用分片的网络,并不一定会在不同分片上分别执行独立的智能合约状态。

在深度学习中,分片可以将模型参数、梯度和优化器状态分散到多个加速器上。2019 年提出的零冗余优化器(Zero Redundancy Optimizer)描述了逐步对优化器状态、梯度和参数进行分区的多个阶段,而不是在每个数据并行工作进程中完整保留所有这些数据。全分片训练通过通信,重建计算所需的参数部分,并重新分发更新。这不同于为各工作进程分配不同训练样本的数据集分片,也不同于将单个张量运算拆分到多个设备上的张量并行。在这种场景中,稀缺资源往往是加速器内存,而性能上的权衡则在于减少冗余存储与增加额外通信之间的取舍。