当数据量大到单机存不下时就需要分布式存储系统。分布式存储与单机存储最大的区别就是把数据按一定规则切分 为多个部分，每个机器只存储其中一部分，这样理论上来讲分布式存储可以应付无穷大的数据量。但是这里带来一 个新的问题，即如何找到我需要的数据是存储在哪台机器呢？这就是分布式系统的分区管理模块需要解决的问题， 除了这个问题外，还需要解决负载均衡和容灾的问题。

分区管理是有一定成本的，随机器数量增加而增加，所以分布式存储的伸缩性不是无穷的，伸缩能力主要取决于 分区管理。所以分区管理是分布式系统中相当重要的模块。

本文将介绍分区管理的一般解决思路，并介绍实际的分布式系统的解决方案，最后总结不同需求场景下应采用的 解决方案。

分区管理应该解决的问题

分区管理主要解决以下问题：

1. 分区，如何将数据集且分为多个分区？
2. 路由
   1. 如何找到分区所在节点？
   2. 如何保证路由信息的一致性？比如，如何解决客户端缓存的过期路由信息？如果读写请求因为过期的路由信息 由错误的节点处理，可能导致数据丢失。
3. 容灾
   1. 如何检测节点的失败？
   2. 节点失败多种多样，基本可分为两种情况：短暂的失败和长期失败。短暂的失败可能是由于临时过载处理不 及时导致的，长期失败可能是硬件故障导致的，短期无法恢复。针对这两种失败应采用不同的容灾策略。

分区

数据通常都有唯一标识，也就是key，所以我们可以根据key来切分数据，通常有以下的切分方案：

• 根据key的范围来划分
  • 优点：可执行按范围查询
  • 缺点：可能分布不均匀，可以结合时间戳或者数据来源进一步分区来缓解
• 根据key的hash来划分
  • 优点：hash可将不均匀的key转换为均匀的数字，所以分布是均匀的
  • 缺点：只能精确查找，无法按范围查询。不过可以设计聪明的hash算法来执行模糊匹配，比如GeoHash可用来 查询附近的地理位置。
  • 例子：一致性hash

路由

路由策略

路由要解决的问题是讲分区映射到节点上，通常需要考虑以下几个需求：

1. 分区尽量均匀分布到节点上；
2. 在进行负载均衡操作时，分区仍然是可用的；
3. 负载均衡时移动的数据量尽量少.

一种容易想到的映射方案是将分区hash对节点数量取模，这种分区方案严重依赖节点的数量。当节点数量变化时，所有 分区到节点的映射都要发生变化，不满足上述的第3点要求，所以不建议使用。

常见的路由策略有两种：

1. 查表
   • 分区到节点的映射存储在一张表里
2. 伪随机算法
   • 分区到节点的映射通过一个伪随机算法计算，如Ceph的CRUSH算法。
   • 优点：路由信息的空间复杂度只跟节点数量有关，存储空间小

路由信息的一致性

另一个问题是如何保证路由信息的一致性：如果读写请求由于过期的路由信息发送到错误的节点，轻则导致读到 错误的数据（比如请求的key不是由该节点负责，所以该节点返回找不到这个key，其实系统中是有这个key的）， 重则导致数据写到错误的节点上，最终数据被丢弃。

权威的路由信息一定会存储在某些节点上，根据存储节点的不同可分为一些两种：

1. 中心化路由
   • 路由信息储存在某些特殊的节点上，他们构成路由层，专门转发客户端的路由请求.
   • 例如，GFS的路由信息存储在主节点上；BigTable的路由信息由Chubby服务来维护；MongoDB的客户端请求由 路由节点转发，其路由信息由一组配置服务器维护；Ceph的路由信息由一组Monitor节点维护，Monitor集群采 用Paxos协议保证路由信息的一致性和可靠性。
2. 去中心化路由
   • 每个节点都存储路由信息的一部分或全部，由所有节点共同维护，他们之间通过一种复制协议（比如Gossip 协议）来保证一致性，所有节点均可路由客户端请求。
   • 最典型的例子就是Dynamo，所有节点存储了完整的路由信息，通过Gossip协议保证路由信息的最终一致。 Cassandra, CouchDB, Voldemort和Redis Cluster也采用了类似的方案。

采用去中心化路由的好处是更好的可用性，任何节点均可单独转发客户端请求。若采用中心化的方式，路由层若发生 故障将导致系统不可用，例如BigTable的可用性将直接受到Chubby的限制，而Dynamo就没有此问题，除非其所有节点 均不可用（BigTable的可用性不超过4个9，而Dynamo的可用性可达到5个9）。

不管采用哪种路由存储方式，均无法保证客户端路由信息与系统的完全一致。当客户端从系统获取到路由信息后到 访问数据这段时间，路由信息此时可能已经发生了变化（节点的状态随时可能变化）。为了容灾，数据的分布必须 随节点状态的变化而变化，不可能在客户端访问数据期间将路由信息锁定起来，因而不能严格保证客户端的路由信息 与系统完全一致。我们只要能保证在客户端的路由信息错误时能够纠正即可。一般采用如下两种方式来解决这个问题：

• 数据节点具有其自身负责的分区的权威信息。若客户端请求的key不由其负责，则返回路由错误给客户端，由其 重新刷新路由信息重试（如BigTable）；或者数据节点有完整的路由信息，直接将其请求转发给正确的节点 （如Dynamo）.
• 数据节点与其它节点发生网络分区了，导致其负责的分区信息本身已经过时，而客户端的路由信息与其刚好一致， 此时数据节点无法判断客户端的路由错误。为了防止这种情况的发生，在新节点接管该节点的分区前必须保证旧节点 不再处理客户端的请求。例如，Ceph和BigTable都采用租约机制来保证旧节点一定不会处理客户端的请求。

还有些系统本身是容忍部分数据丢失的，因而也没有机制保证客户端路由信息的一致性，比如Redis Cluster，当 客户端访问的数据节点与其它节点发生网络分区时（此时客户端和数据节点的路由信息都是旧的并可能相同） 会依然接受读写请求，直到它检测到了网络分区为止，这段时间写的数据将在主节点迁移后丢失。

路由转发

路由的转发直接影响到请求处理的延迟，转发次数过多会导致延迟过高，而且延迟也不稳定。转发方式可分为3种：

1. 客户端直接转发
   • 客户端可缓存或预取路由信息，此后将直接路由请求给正确的节点，可最大程度减少转发次数。即使路由信息 过期也可以通过系统的转发纠正。
   • 客户端逻辑会比较复杂，通常这部分逻辑会以客户端库的形式由系统提供，编译链接到应用程序。
2. 路由层转发
   • 如果由于某种场景限制无法使用客户端库，可由负载均衡器来实现路由功能.
3. 数据节点转发
   • 对于采用去中心化的路由存储可由数据节点转发.

一般来讲，路由转发的策略与路由一致性的解决方案有关，中心化的路由一般可支持客户端转发和路由层转发，去 中心化的路由可支持以上3种，比如Voldemort可配置以上3种方案。

容灾

容灾的第一步是检测失败节点，不管是什么检测算法都需要发送心跳，所以检测的通信模式将直接制约系统的可伸缩 性。根据心跳的通信模式分为3种：

1. 星形模式
   • 主节点定期发送心跳给数据节点，数据节点也可发送心跳给主节点
   • 例子：GFS, BigTable, ElasticSearch
2. 全连通模式
   • 所有节点相互之间发送心跳
   • 例子：Dynamo, Cassandra, Redis Cluster
3. 分组模式
   • 仅某个分区的副本节点之间发送心跳
   • 例子：Ceph, MongoDB

很明显，星形模式对主节点的负担比较重，可伸缩性完全由主节点制约。全连通模式的通信量比较大，伸缩性也会 有所限制，但是其可用性比较好，因为所有节点均可作为备胎用于数据迁移，只要有一个节点可用，整个系统就可用。 分组模式的伸缩性是最好的，节点数的增多不会引起通信量增加，同时若其数据可在整个集群间迁移，其可用性也 非常好。

大多数系统的失败检测是周期性运行的，不过Dynamo和Cassandra的失败检测是客户端驱动的，因此检测算法的触发 方式分两种：

1. 周期性触发
   • 大多数系统是这种
2. 客户端驱动
   • Dynamo和Cassandra

节点失败的原因有很多，有些是短暂的，有些是永久的，检测算法一般无法区分这两者，所以在处理失败时必须有 所权衡，既不能太敏感也不能过于迟钝，否则会导致失败处理不及时或者系统不稳定。所以检测到失败后还必须权 衡失败的性质然后再处理。有的系统是用中心化的方式来判断失败的性质，有些是用去中心化的方式，所以基本可 分为两种：

1. 中心化检测
   • 检测结果上报到某个节点或者监控集群进行全局性判断是否需要进行数据迁移.
   • GFS, BigTable, Ceph, ElasticSearch, Redis Cluster
2. 去中心化检测
   • 本地自行判断，由于缺乏全局信息，仅可处理短暂失败，长期失败需要人工干预.
   • Dynamo, Cassandra

对于短暂失败一般通过重试或者hinted handoff解决。永久性失败必须迁移数据。有些系统需要人为干预来迁移， 比如Dynamo和Cassandra.

案例介绍

本节将重点介绍几个著名的分布式系统的实际例子，它们对许多系统的设计都有很大影响，了解这几个系统的设计 方案将有助于了解其它系统，也可在自己设计系统时参考。

GFS

GFS是Google设计的分布式文件系统，将多个机器的硬盘抽象成了一个硬盘。由一个主节点、多个数据节点和客户端 库组成。主节点负责维护全局的路由信息，并检测数据节点的状态。数据节点负责数据的可靠存储。客户端负责读写 请求，从主节点拉取路由信息。

由于只需要根据文件名来查找所以采用Hash分区。并采用动态路由策略。路由信息采用中心化方式，便于全局协调。 节点的状态监测采用星形通信模式和中心化监测机制。很容易看出，单一的主节点是容量瓶颈和系统的风险点。后来 Google增加了主节点的冷备来防止单点风险，但是仍然解决不了容量问题。之所以采用这样的中心化架构就是因为 实现简单。

BigTable

GFS存储的是非结构化数据，不方便查询。BigTable是基于GFS设计的结构化存储系统，支持列式数据模型。其架构 类似于GFS，包括一个主节点、多个数据节点和客户端库。主节点负责维护全局路由信息，它存储在Chubby上，并 周期性检测数据节点的状态。数据节点负责客户端的读写请求，而数据是存储在GFS。

由于需要支持按范围查询，所以采用范围分区方案。分区的大小可根据数据量动态调整，拆分或合并。与GFS一样采用 中心化路由。为了保证路由信息的一致性，必须保证任意时刻每个分区只有一个数据节点可访问，BigTable用租约 机制来保证这一点（基于Chubby的带超时的锁）。数据节点的状态由主节点周期性检测，若失败则调整路由信息由 新节点来接管之前的分区。

虽然主节点只有一个，但并不会过于影响可用性，因为客户端的访问路径并不经过主节点，而是从Chubby获取路由 信息。主节点只是负责检测数据节点的状态、负载均衡等。但是如果主节点长期故障将影响可用性。

Dynamo

Dynamo是Amazon设计的用于存储用户购物车的分布式存储系统，主要强调可用性。所以其设计思路与以上两个系统 有很大的区别。它是一个完全去中心化的架构，所有节点都是数据节点，角色完全对称，不存在特殊的节点。客户端 可访问任何节点进行读写，只要有一个节点存活则整个系统就是可用的。

由于不需要按范围查询并为了保证数据分布均匀，采用hash分区。为了保证路由信息变化时数据迁移量尽量小，采用 一致性Hash方案。所有节点存储全局的路由信息，并通过Gossip协议维护最终一致性。所有节点相互之间检测状态， 由客户端驱动，本地化决策，可容忍短暂的失败。长期的节点失败由人工干预解决。

正是由于采用了完全去中心化的架构，其可用性达到了惊人的5个9.

Cassandra

Cassandra是Facebook开发的高可用存储系统，用于其消息搜索。它结合了BigTable的数据模型和Dynamo的分区管 理方案，也是一个完全去中心化的架构。与Dynamo相比，只是在一致性hash和多版本冲突解决等细节上有区别。

Ceph

Ceph也是一个分布式文件系统，强调伸缩性。由客户端库、一小组Monitor集群和许多OSD组成。Monitor集群维护全局的 OSD拓扑结构，在节点失败时调整拓扑结构。Monitor集群运行Paxos协议来保证拓扑结构的一致性和可靠性。Monitor集群的 拓扑结构信息通过类似Gossip的协议传递给所有OSD。OSD负责数据存储及复制，处理读写请求，相互之间检测心跳 状态，并在节点失败时迁移数据等。

由于只需要支持精确查找，Ceph采用按hash分区。分区大小不可自动调整，但可以人工增加。Ceph最具创新的地方 是其路由算法，跟其它系统不同的是，分区到节点的映射不是查表而是伪随机算法CRUSH计算出来的，具有以下特点：

1. 根据key、拓扑结构和分配规则即可算出节点地址；
2. 确定性：相同的输入产生相同的输出；
3. 一定程度上保证分区的分布是均匀的，并可考虑到节点的网络层次结构；
4. 当拓扑结构发生变化时数据迁移量很小。

由于CRUSH算法的支持，路由信息只需要存储拓扑结构就可以了，其存储空间只与OSD的数量有关，而与分区数量无关， 大大减小了需要的存储量，有助于伸缩性的实现。

与BigTable类似，Ceph采用租约机制保证路由信息的一致性。

Ceph的心跳检测是分组模式，即保存同一分区的OSD之间发送心跳，当发现节点失败时请求Monitor集群更新拓扑结构 重新分布数据。分组模式有助于减小通行量，增加了伸缩性。同时为了减小Monitor集群的负载，更新拓扑结构的请求 会合并批量上报给Monitor集群。

与GFS相比，Ceph提高伸缩性的策略有：

1. 分区的粒度更粗，路由信息更小，增加了系统容量
   • GFS的分区粒度是文件，Ceph的一个分区可存储多个文件，粒度由分区的数量决定，这样有助于减小路由信息， 使得中心化的路由节点可支持更多数据。
   • Ceph采用CRUSH算法计算路由信息，进一步压缩了路由信息。
2. 路由信息扩散至所有数据节点，可以让数据节点承担更多工作（包括数据复制、失败检测及恢复、负载均衡）， 减轻Monitor集群的压力
   • GFS的路由信息仅存储在主节点，导致许多管理工作只能由主节点来负责，成为性能瓶颈。

Conclusion

综合以上几个例子可以看出，设计分布式系统基本有两种思路：中心化和去中心化架构。中心化架构比较简单，容 易实现，而且由于有全局信息便于全局协调，包括数据分布、负载均衡、数据迁移等。为了防止中心节点成为性能 瓶颈，通常将控制逻辑和数据逻辑分离，只有控制逻辑经过中心节点，而数据逻辑尽量直接与数据节点通信。比如， 尽量让客户端缓存路由信息，防止每次都要访问中心节点。Ceph是一个极好的案例，尽量让数据节点分担管理工作， 有助于高伸缩性的实现。完全的去中心化架构任何模块都没有单点风险，拥有极好的可用性，但是实现比较复杂， 因此很少系统采用。由于其节点的功能是对称的，所以负载分布也较为均匀，没有节点会因为承担更多的工作而成 为性能瓶颈，可伸缩性也很好。

设计分布式系统时一个重要的考虑是CAP理论，其中P代表分区容忍性，这个是世界的现实，无法绕过去，所以只能 在一致性和可用性之间进行权衡。强调可用性的系统可参考Dynamo的解决方案，采用去中心化的架构。而强调一致 性的系统则建议采用中心化架构，因为一致性必然涉及到多个节点的协调，若维护有一个全局信息将更方便进行协 调。

References

• The Google File System
• Ceph: A Scalable, High-Performance Distributed File System
• Dynamo: Amazon’s Highly Available Key-value Store
• Cassandra - A Decentralized Structured Storage System
• RADOS: A Scalable, Reliable Storage Service for Petabyte-scale Storage Clusters
• Bigtable: A Distributed Storage System for Structured Data