关于分布式:分布式要点数据分区

采纳数据分区的次要目标是进步可扩展性。不同的分区能够放在一个无共享集群的不同节点上。这样一个大数据集能够扩散在更多的磁盘上，查问负载也随之散布到更多的处理器上。

对单个分区进行查问时，每个节点对本人所在分区能够独立执行查问操作，因而增加更多的节点能够进步查问吞吐量。超大而简单的查问只管比拟艰难，但也可能做到跨节点的并行处理。

分区通常与复制联合应用，即每个分区在多个节点都存有正本。这意味着某条记录属于特定的分区，而同样的内容会保留在不同的节点上以进步零碎的容错性。

一个节点上可能存储了多个分区。每个分区都有本人的主正本，而从正本则调配在其余一些节点。一个节点可能即是某些分区的主正本，同时又是其余分区的从正本。

键 - 值数据的分区

当初假如数据是简略的键 - 值数据模型，这意味着总是能够通过关键字来拜访记录。

基于关键字区间分区

一种分区形式是为每个分区调配一段间断的关键字或者关键字区间范畴（以最小值和最大值来批示）。如果晓得关键字区间的上上限，就能够轻松确定哪个分区蕴含这些关键字。如果还晓得哪个分区调配在哪个节点，就能够间接向该节点发出请求。

关键字的区间段不肯定非要均匀分布，这次要是因为数据自身可能就不平均。分区边界能够由管理员手动确定，或者由数据库主动抉择。每个分区内能够依照关键字排序保留，这样能够轻松反对区间查问，行将关键字作为一个拼接起来的索引项从而一次查问失去多个相干记录。例如，对于一个保留网络传感器数据的利用零碎，抉择测量的工夫戳（年 - 月 - 日 - 时 - 分 - 秒）作为关键字，此时区间查问会十分有用，它能够疾速取得某个月份内的所有数据。

然而， 基于关键字的区间分区的毛病是某些拜访模式会导致热点 。如果关键字是工夫戳，则分区对应于一个工夫范畴，例如每天一个分区。然而，当测量数据从传感器写入数据库时，所有的写入操作都集中在同一个分区（即当天的分区），这会导致该分区在写入时负载过高，而其余分区始终处于闲暇状态。

为了防止上述问题，须要应用工夫戳以外的其余内容作为关键字的第一项。例如，能够在工夫戳后面加上传感器名称作为前缀，这样首先由传感器名称，而后按工夫进行分区。假如同时有许多传感器处于活动状态，则写入负载最终会比拟平均地散布在多个节点上。接下来，当须要获取一个工夫范畴内、多个传感器的数据时，能够依据传感器名称，各自执行区间查问。

基于关键字哈希值分区

对于上述数据歪斜与热点问题，许多分布式系统采纳了基于关键字哈希函数的形式来分区。

一个好的哈希函数能够解决数据歪斜并使其均匀分布。一旦找到适合的关键字哈希函数，就能够为每个分区调配一个哈希范畴（而不是间接作用于关键字范畴），关键字依据其哈希值的范畴划分到不同的分区中。

这种办法能够很好地将关键字平均地调配到多个分区中。分区边界能够是平均距离，也能够是伪随机抉择（在这种状况下，该技术有时被称为一致性哈希）。

然而， 通过关键字哈希进行分区，咱们丢失了良好的区间查问个性。即便关键字相邻，但通过哈希之后会扩散在不同的分区中，区间查问就失去了原有的有序相邻的个性 。

负载歪斜与热点

如前所述，基于哈希的分区办法能够加重热点，但无奈做到完全避免。一个极其状况是，所有的读 / 写操作都是针对同一个关键字，则最终所有申请都将被路由到同一个分区。

这种负载或者并不广泛，但也并非不可能：例如，社交媒体网站上，一些名人用户有数百万的粉丝，当其公布一些热点事件时可能会引发一场拜访风暴，呈现大量的对雷同关键字的写操作（其中关键字可能是名人的用户 ID，或者人们正在评论的事件 ID）。此时，哈希起不到任何帮忙作用，因为两个雷同 ID 的哈希值依然雷同。

大多数的零碎明天依然无奈主动打消这种高度歪斜的负载，而只能通过应用层来加重歪斜水平。例如，如果某个关键字被确认为热点，一个简略的技术就是在关键字的结尾或结尾处增加一个随机数。只需一个两位数的十进制随机数就能够将关键字的写操作散布到 100 个不同的关键字上，从而调配到不同的分区上。

然而，随之而来的问题是，之后的任何读取都须要些额定的工作，必须从所有 100 个关键字中读取数据而后进行合并。因而通常只对大量的热点关键字附加随机数才有意义；而对于写入吞吐量低的绝大多数关键字，这些都意味着不必要的开销。此外，还须要额定的元数据来标记哪些关键字进行了非凡解决。

分区与二级索引

在分区方案设计中，如果波及二级索引，状况会变得复杂。二级索引通常不能惟一标识一条记录，而是用来减速特定值的查问。二级索引是关系数据库的必备个性，在文档数据库中利用也十分广泛。

二级索引带来的次要挑战是它们不能规整的地映射到分区中。有两种次要的办法来反对对二级索引进行分区：基于文档的分区和基于词条的分区。

基于文档的二级索引

在这种索引办法中， 每个分区齐全独立，各自保护本人的二级索引，且只负责本人分区内的文档而不关怀其余分区中数据 。每当须要写数据库时，包含增加，删除或更新文档等，只须要解决蕴含指标文档 ID 的那一个分区。因而文档分区索引也被称为本地索引，而不是全局索引。

但读取时须要留神：除非对文档 ID 做了特地的解决，否则不太可能所有特定查问条件的数据都放在一个分区中。因而须要将查问发送到所有的分区，而后合并所有返回的后果。

这种查问分区数据库的办法有时也称为扩散 / 汇集，显然这种二级索引的查问代价昂扬。即便采纳了并行查问，也容易导致读提早显著放大。

基于词条的二级索引

另一种办法，咱们能够对所有的数据构建全局索引，而不是每个分区保护本人的本地索引。而且，为防止成为瓶颈，不能将全局索引存储在一个节点上，否则就毁坏了设计分区平衡的指标。所以，全局索引也必须进行分区，且能够与数据关键字采纳不同的分区策略。

和后面探讨的办法一样，能够间接通过关键词来全局划分索引，或者对其取哈希值。间接分区的益处是能够反对高效的区间查问；而采纳哈希的形式则能够更平均的划分分区。

这种全局的词条分区相比于文档分区索引的次要长处是， 它的读取更为高效，即它不须要采纳 scatter/gather 对所有的分区都执行一遍查问，相同，客户端只须要向蕴含词条的那一个分区收回读申请。然而全局索引的不利之处在于，写入速度较慢且非常复杂，次要因为单个文档的更新时，外面可能会波及多个二级索引，而二级索引的分区又可能齐全不同甚至在不同的节点上，由此势必引入显著的写放大 。

实际中，对全局二级索引的更新往往都是异步的。

分区再均衡

迁徙负载的过程称为再均衡（或者动态平衡）。无论对于哪种分区计划，分区再均衡通常至多要满足：

• 均衡之后，负载、数据存储、读写申请等应该在集群范畴更平均地散布。
• 再均衡执行过程中，数据库应该能够持续失常提供读写服务。
• 防止不必要的负载迁徙，以放慢动静再均衡，并尽量减少网络和磁盘 I / O 影响。

动静再均衡的策略

为什么不必取模？

对节点数取模办法的问题是，如果节点数 N 产生了变动，会导致很多关键字须要从现有的节点迁徙到另一个节点。这种频繁的迁徙操作大大增加了再均衡的老本。

固定数量的分区

有一个相当简略的解决方案：首先， 创立远超理论节点数的分区数，而后为每个节点调配多个分区 。例如，对于一个 10 节点的集群，数据库能够从一开始就逻辑划分为 1000 个分区，这样大概每个节点承当 100 个分区。

接下来， 如果集群中增加了一个新节点，该新节点能够从每个现有的节点上匀走几个分区，直到分区再次达到全局均衡 。如果从集群中删除节点，则采取相同的平衡措施。

选中的整个分区会在节点之间迁徙，但分区的总数量仍维持不变，也不会扭转关键字到分区的映射关系。这里惟一要调整的是分区与节点的对应关系。思考到节点间通过网络传输数据总是须要些工夫，这样调整能够逐渐实现，在此期间，旧的分区依然能够接管读写申请。

原则上，也能够将集群中的不同的硬件配置因素思考进来，即性能更弱小的节点将调配更多的分区，从而分担更多的负载。

如果数据集的总规模高度不确定或可变，此时如何抉择适合的分区数就有些艰难。每个分区蕴含的数据量的下限是固定的，理论大小应该与集群中的数据总量成正比。如果分区里的数据量十分大，则每次再均衡和节点故障复原的代价就很大；然而如果一个分区太小，就会产生太多的开销。分区大小应该“恰到好处”，不要太大，也不能过小，如果分区数量固定了但总数据量却高度不确定，就难以达到一个最佳取舍点。

动静分区

对于采纳关键字区间分区的数据库，如果边界设置有问题，最终可能会呈现所有数据都挤在一个分区而其余分区根本为空，那么设定固定边界、固定数量的分区将十分不便，而手动去重新配置分区边界又十分繁琐。

因而，一些数据库如 HBase 等采纳了动态创建分区。 当分区的数据增长超过一个可配的参数阈值，它就拆分为两个分区，每个承当一半的数据量。如果大量数据被删除，并且分区放大到某个阈值以下，则将其与相邻分区进行合并。 该过程相似于 B 树的决裂操作。

每个分区总是调配给一个节点，而每个节点能够承载多个分区，这点与固定数量的分区一样。当一个大的分区产生决裂之后，能够将其中的一半转移到其余某节点以均衡负载。

动静分区的一个长处是分区数量能够主动适配数据总量。如果只有大量的数据，大量的分区就足够了，这样零碎开销很小；如果有大量的数据，每个分区的大小则被限度在一个可配的最大值。

按节点比例分区

采纳动静分区策略，拆分和合并操作使每个分区的大小维持在设定的最小值和最大值之间，因而分区的数量与数据集的大小成正比关系。另一方面，对于固定数量的分区形式，其每个分区的大小也与数据集的大小成正比。两种状况，分区的数量都与节点数无关。

Cassandra 和 Ketama 则采纳了第三种形式，使分区数与集群节点数成正比关系。换句话说，每个节点具备固定数量的分区。此时，当节点数不变时，每个分区的大小与数据集大小放弃反比的增长关系；当节点数减少时，分区则会调整变得更小。较大的数据量通常须要大量的节点来存储，因而这种办法也使每个分区大小保持稳定。

当一个新节点退出集群时，它随机抉择固定数量的现有分区进行决裂，而后拿走这些分区的一半数据量，将另一半数据留在原节点。随机抉择可能会带来不太偏心的分区决裂，然而当均匀分区数量较大时，新节点最终会从现有节点中拿走相当数量的负载。

随机抉择分区边界的前提要求采纳基于哈希分区 （能够从哈希函数产生的数字范畴里设置边界）。这种办法也最合乎本章结尾所定义一致性哈希。一些新设计的哈希函数也能够以较低的元数据开销达到相似的成果。

申请路由

概括来讲，这个问题有以下几种不同的解决策略（别离如图所示的三种状况）：

1. 容许客户端连贯任意的节点（例如，采纳循环式的负载均衡器）。如果某节点恰好领有所申请的分区，则间接解决该申请；否则，将申请转发到下一个适合的节点，接管回答，并将回答返回给客户端。
2. 将所有客户端的申请都发送到一个路由层，由后者负责将申请转发到对应的分区节点上。 路由层自身不解决任何申请，它仅充一个分区感知的负载均衡器。
3. 客户端感知分区和节点分配关系。此时，客户端能够间接连贯到指标节点，而不须要任何中介。

这其实是一个很有挑战性的问题，所有参与者都要达成共识这一点很重要。否则申请可能被发送到谬误的节点，而没有失去正确处理。分布式系统中有专门的共识协定算法，但通常难以正确实现。

许多分布式数据系统依附独立的协调服务（如 ZooKeeper）跟踪集群范畴内的元数据。每个节点都向 ZooKeeper 中注册本人，ZooKeeper 保护了分区到节点的最终映射关系。其余参与者（如路由层或分区感知的客户端）能够向 ZooKeeper 订阅此信息。一旦分区产生了扭转，或者增加、删除节点，ZooKeeper 就会被动告诉路由层，这样使路由信息放弃最新状态。

Cassandra 和 Riak 则采纳了不同的办法，它们在节点之间应用 gossip 协定来同步群集状态的变动。申请能够发送到任何节点，由该节点负责将其转发到指标分区节点。这种形式减少了数据库节点的复杂性，然而防止了对 ZooKeeper 之类的内部协调服务的依赖。

当应用路由层或随机抉择节点发送申请时，客户端依然须要晓得指标节点的 IP 地址。IP 地址的变动往往没有分区 - 节点变动那么频繁，采纳 DNS 通常就足够了。