大数据存储的秘密之分区

戳蓝字「TopCoder」关注我们哦！

分区，又称为分片，是解决大数据存储的常见解决方案，大数据存储量超过了单节点的存储上限，因此需要进行分区操作将数据分散存储在不同节点上，通常每个单个分区可以理解成一个小型的数据库，尽管数据库能同时支持多个分区操作；分区引入多分区概念，可以同时对外服务提高性能。

常常和分区一并提及的概念是复制，分区通常与复制结合使⽤，使得每个分区的副本存储在多个节点上。这意味着，即使每条记录属于⼀个分区，它仍然可以存储在多个不同的节点上以获得容错能⼒。分区在许多技术或框架中都有体现，例如MQ中topic下的分区消息实现，如kafka中的partion、rocketmq中的queue等；例如SQL/NoSQL中分区数据储存实现，如ElascticSearch中的Shards分片、MySQL中的分表等。

关于分区，本文主要讨论下键值分区的几种方式、分区再平衡策略和请求路由处理机制等，最后以ES（ElascticSearch）的查询请求处理为例，分析分区下查询的请求处理流程。话不多说，Let's Go~

键值分区的几种方式

如果有大量数据需要分散存储，应该如何进行分区呢？分区的目前就是将数据均衡的分散在各节点，这样同时也能分散对数据的处理请求，如果分区不均衡，那么会造成某些分区有大量的数据或查询请求，这就是常说的倾斜。数据倾斜会造成高负载节点形成热点，避免热点可以使用随机路由方式将数据散列到各分区中。对数据进行分区操作，不能仅仅是随机数据存储，因为存储之后肯定还是要进行查询的，所以要按照固定键值来进行散列分区操作，方便后续查询请求的路由。常见的键值分区方式有按照范围分区、按照键的散列分区：

按照范围分区

按照范围分区就是每个分区存储指定一段连续的数据，比如按照时间戳来存储数据，最简单常见的日志按照时间分割为不同的文件；按照编号id来存储数据，如图书馆书籍陈列，编号连续数据存放在同一个书架上。按照范围分区有时候会造成分区数据不均衡，比如按照时间戳，可能某段时间内数据比较少而某些时间段数据较多而造成分区不均衡。

键值散列分区

由于按照范围分区容易造成数据负载不均衡问题，所以一般应用场景下（非顺序类型数据）为了避免偏斜和热点的⻛险，会使⽤散列函数来确定给定键的分区。一个好的散列函数会尽量随机分区，许多语言内都内置了散列函数，但是有些可能不太适合分区场景，比如Java的 Object.hashCode()和Ruby的 Object#hash，其同⼀个键可能在不同的进程中有不同的哈希值。 有了合适的散列函数，有时候想要让一定散列范围内的数据分布在同一分区，此时可使用一致性哈希，一致性哈希可减小因为分区变动造成会已有数据分区映射的影响。

热点问题

哈希分区可帮助减少热点，但是无法避免，极端情况下可能存在所有请求都打到同一分区中。热点分区问题解决思路是：一种是给热点分区再分区操作，比如针对热点数据的key再路由分散多个分区中；还有一种是热点数据增加冗余（也就是复制），增加热点数据的复制节点，一同对外提供服务。

分区再平衡

随着时间的推移，分区数据会有以下变化：

• 查询吞吐量增加，所以您想要添加更多的CPU来处理负载。
• 数据集⼤⼩增加，所以您想添加更多的磁盘和RAM来存储它。
• 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从⼀个节点移动到另⼀个节点。将负载从集群中的⼀个节点向另⼀个节点移动的过程称为再平衡（reblancing），再平衡过程一般要求如下：再平衡之后数据尽量均衡、在平衡时分区要正常地外提供服务、节点之间只移动必要数据以加快再平衡进度。（一般来说直接使用取余方式散列的分区再平衡时大都需要将所有数据重新取余再分区，成本较大。）

固定数目的分区

为了避免分区的扩容再平衡操作，可以创建⽐节点更多的分区，并为每个节点分配多个分区。例如，运⾏在10个节点的集群上的数据库可能会从⼀开始就被拆分为1000个分区，因此⼤约有100个分区被分配给每个节点。比如ES就是用了这种再平衡方式，ES中的shards分片在运行时是无法更改的，因此生产环境一般会建议针对分区数设定留一定的余量，方便后续扩容操作。这样的话，分区的数量不会变化，知识分区数据会在节点间移动而已，键所指定的分区也不会改变。唯⼀改变的是分区所在的节点。这种变更并不是即时的，在⽹络上传输⼤量的数据需要⼀些时间，所以在传输过程中，原有分区仍然会接受读写操作。如下图所示：

动态分区

对于使用键范围场景来说，具有固定边界的固定数量的分区将⾮常不便：如果出现边界错误，则可能会导致⼀个分区中的所有数据或者其他分区中的所有数据为空。⼿动重新配置分区边界将⾮常繁琐。因此，按键范围进行分区的数据库（如HBase和RethinkDB）会动态创建分区。当分区增⻓ 到超过配置的⼤⼩时（在HBase上，默认值是10GB），会被分成两个分区，每个分区约占⼀半的数据。与之相反，如果⼤量数据被删除并且分区缩⼩到某个阈值以下，则可以将其与相邻分区合并，类似B树的过程类似。 动态分区的⼀个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就⾜够了，所以开销很⼩；如果有⼤量的数据，每个分区的⼤⼩被限制在⼀个可配置的最⼤值，当超过阈值时触发分区操作。

再平衡操作触发时，到底应该由人为触发还是由程序自动触发呢？程序自动触发，一般是检测节点负载过高或者（通过网络心跳发现）某个节点挂了，自动再平衡可能因为某些外界环境的影响就执行了，可能达不到我们的预期，因此，一个合理的方案是，程序自动发现应该执行再平衡时，可以报警通知到运维人员，由人工介入来处理后续的再平衡执行。

请求路由处理

当处理请求时，如何确定哪个节点执行呢？随着分区再平衡，分区对节点的分配也发生变化，为了回答这个问题，需要有⼈知晓这些变化：如果我想读或写键“foo”，需要连接哪个节点IP地址和端⼝号？这个问题本质上就是 服务发现 ，它不仅仅体现在数据库，任何网络通信场景都有这个问题，特别是如果它的⽬标是⾼可⽤性（在多台机器上运⾏冗余配置），都需要服务发现。概括来说，请求路由处理，有以下几种处理方案：

1. 允许客户联系任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
2. ⾸先将所有来⾃客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。
3. 要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，⽽不需要任何中介代理。

以上所有情况的关键问题是，做出路由决策的组件（可能是节点之一、客户端或者路由代理）如何知道分区-节点之间的映射关系。映射关系可以使固定写死在代码中，也可以是配置在配置中心中。许多分布式数据系统都依赖于⼀个独⽴的协调服务，⽐如ZooKeeper来跟踪集群元数据。每个节点在ZooKeeper中注册⾃⼰，ZooKeeper维护分区到节点的可靠映射。其他参与者（如路由层或分区感知客户端）可以在ZooKeeper中订阅此信息。只要分区分配发⽣的改变，或者集群中添加或删除了⼀个节点，ZooKeeper就会通知路由层使路由信息保持最新状态。

执行查询

请求处理查询可分为两种场景，单节点查询和集群查询，前者一般是针对一类数据的查询并且该类数据存储在同一个节点上，后者是同时发给多个节点，最后再做聚合操作。集群查询也称为并行查询，通常⽤于分析的⼤规模并⾏处理（MPP, Massively parallel processing） 关系型数据库产品在 其⽀持的查询类型⽅⾯要复杂得多。⼀个典型的数据仓库查询包含多个连接，过滤，分组和聚合操作。

ES的查询处理流程

ES使用开源的Lucene作为存储引擎，它赋予ES高性能的数据检索能力，但Lucene仅仅是一个单机索引库。ES基于Lucene进行分布式封装，以支持集群管理、分布式查询、聚合分析等功能。

从使用的直观感受看，ES查询分为2个阶段，query和fetch阶段。在query阶段会从所有的shard上读取相关document的docId及相关的排序字段值，并最终在coordinating节点上收集所有的结果数进入一个全局的排序列表后，然后获取根据from+size指定page页的数据，获取这些docId后再构建一个multi-get请求发送相关的shard上从_source里面获取需要加载的数据，最终再返回给client端。

query阶段：

fetch阶段 ：

所有的搜索系统一般都是两阶段查询，第一阶段查询到匹配的DocID，第二阶段再查询DocID对应的完整文档，这种在Elasticsearch中称为query_then_fetch，还有一种是一阶段查询的时候就返回完整Doc，在Elasticsearch中称作query_and_fetch，一般第二种适用于只需要查询一个Shard的请求。由上图可知，ES允许客户联系任何节点，如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复然后聚合并传递最终的聚合结果给客户端。

小结

大数据量场景在单台机器上存储和处理不再可⾏，则分区⼗分必要。分区的⽬标是在多台机器上均匀分布数据和查询负载，避免出现热点（负载不成⽐例的节点）。这需要选择适合于您的数据的分区⽅案，并在将节点添加到集群或从集群删除时进⾏再分区。

常见的键值分区方式有按照范围分区、按照键的散列分区两种。请求的处理机制一般有客户端处理、代理处理、服务节点处理3种方式，不管哪种方式，都需要其知道分区-节点之间的映射关系，一般映射关系是保存在配置中心上，比如zookeeper。

参考资料：

1、https://book.douban.com/subject/30329536/

2、elascticsearch 查询机制