分布式基础-分片和路由

一 前言

大数据的概念已经热了几年了，以后大数据越来越平常。而大数据的存储和处理，必然会用到分布式系统，所以有必要对分布式系统有所了解。在此，想结合自己学习写些文章， 这些文章可能有些无聊，尽量结合些实例来说明下。

大数据虽然不是纯粹说是数据量大，比如还有数据种类多，格式多样等，但是数量大也算是大数据的特点之一了。大数据的首要问题就是如何存下这么大量的数据，单台机器一般情况下因为存储介质小或性能不够等原因，需要将数据保存在不同的机器上。就像一个大蛋糕，需要切成几片一样，大数据也需要切成几份，来保存。这些份总体组成我们整体的大数据内容。

数据分片和数据复制一般结合起来的，数据分片提升了数据新建的速度。数据复制或者叫数据的副本越多，读取性能更好，因为可以同时在不同的副本上进行读取。

数据分片示意图

二 分片算法要求

• 均衡性
  分布式的目的就是用多台机器来分担单台机器难以完成的任务，那么数据在分片的时候，均衡性是我们首要考虑的问题，如果不均衡会严重影响整体的性能。所以我们分片要尽量保持均衡。
  比如我们有3台机器，一万条数据，那么尽量一台保存三千三百条左右比较好。

• 数据的稳定性
  数据稳定性是指当分布式系统中的一台坏了或添加新的一台机器，数据按照我们的分布规则，带来的影响尽量小。

• 高性能
  分区算法是每条数据都需要进行的操作，无论是新建还是查询，均需要进行分区计算，所以性能要尽可能高。

三 常见的分片算法

在介绍之前，先来看下通用的数据分片和路由通用模型，来完成从一条具体的数据映射到具体的物理节点上存储。数据分片是讲根据何算法来划分数据子集，而数据路由包括数据到分片，再从数据分片映射到物理节点上。

分片和路由模型

如上图 抽象成二层映射，首先根据数据的key做key和shard的映射，将数据划分到不同的分片上去，这种是一种多对一的关系，即多条数据映射到一个分片上去。第二层映射是分片和物理机器的映射，也是一种多对一的关系。一台物理机器可以包含多个shard分片，比如solr就可以这样。

• 轮询
  比如在消息含有key的情况下，kafka默认的分区器（这里可以看作是分片器）尽力确保相同的key路由到同一个paratitioner(Java版本的生产者使用murmur2算法计算key的哈希值)；若没有指定key则按照轮询方式确保消息在topic的不同paratitioner上均匀分配。由于kafka算是个消息引擎系统，所以很少做查询可以这样做，一般需要查询的系统很少用轮询方式来分片数据。

-哈希算法
哈希算法是非常常见的数据分片方式，数据分片根据key映射到不同的分片上去。举个简单的例子，在Solr集群中，计算文档归属的shard的公式：

Math.abs(id.hashcode() % numShards)

solr里面使用的hash算法是Murmurhash算法。这是刚才说的第一层映射key-shard的映射。shard和solr的节点如何映射那。solr在cloud 模式下，按照开始划分的shard数，将0-ffffffff这个数据空间划分shard数个，不同的shard保存不同范围的数据，可以看看下面的state.json配置，注意其中的range。

"collection1":{
    "replicationFactor":"1",
    "router":{"name":"compositeId"},
    "maxShardsPerNode":"1",
    "autoAddReplicas":"false",
    "shards":{"shard1":{
        "range":"80000000-7fffffff",
        "state":"active",
        "replicas":{"core_node1":{
            "core":"collection1_shard1_replica1",
            "base_url":"http://ip:8181/solr",
            "node_name":"ip:8181_solr",
            "state":"active",
            "leader":"true"}}}}}}

哈希算法的好处是速度快，比较简单，但是也有坏处，就是刚才说的数据稳定性。比如我们机器从4台变更为5台后，如果没有特殊处理办法，所有的数据都会发生变动，需要迁移大量数据。而且哈希算法中各个机器的地位是均等的，不适合于异构类型的机器。

哈希算法适用
原因： 这种哈希算法，将key-shard映射和shard-machine映射合二为一了，且以物理节点数作为模，物理节点数和映射紧耦合

• 一致性哈希算法
  一致性哈希算法将物理节点和数据都映射到一个环上，存储节点可以根据IP地址等进行哈希，数据通常通过顺时针方向寻找，来确定数据存储的物理节点。
  如下图：

一致性哈希算法

上图中，首先我们将节点按照IP计算哈希值，映射到哈希空间中去，一般这个空间定义为0-2³²-1。
一个数据的hash值为8，按照一致性哈希算法，顺时针寻找存储节点，即数据保存到物理节点N14上；另外一个数据计算哈希的值为19，数据保存在物理节点N20上。

如何实现算法那？ 当我们在一个物理节点查询数据的时候，如果值在这个范围则直接返回，如果不在这个物理节点那，那通过此物理节点的后续节点继续寻找。不过这种方法比较低效，一般优化办法，是在每个节点上保存路由表信息，路由表保存距离当前节点2ⁱ的哈希空间距离：
2⁰ 2¹ 2² .. .2ⁿ
然后可以通过类似二分查找的速度快速定位到物理节点。

Cassandra 和Dynamo很多分布式系统都采用这种算法的变体。可以看出利用这种算法，如果增加一个节点或者删除一个节点，影响的范围有限。

虽然一致性哈希算法提升了数据的稳定性，但是如果又节点挂了，数据迁移到另外的节点上去，导致这个节点的压力过大，挂了，再顺时针寻找下一个节点，将刚才挂掉的2个节点的数据再迁移到这个节点上，从而导致这个节点挂掉，就这样导致整个系统的节点都挂掉； 另外一致性哈希算法也没有解决异构物理节点的问题，即如果机器的性能不同，采用一致性哈希算法是一样的权重，实际上导致了不均衡问题。

• 带负载的一致性哈希算法
  类似于一致性哈希算法，但是节点上保存节点存储数量的上限，当数据按照哈希算法应该保存到这个节点的时候，先判断这个节点的数据是否达到了上限，如果此节点的数据已经到底了上限，继续按照顺时针方向寻找。

这样可以解决刚才的节点负载过重而导致的挂掉问题，但是仍然没有解决异构物理节点的问题。
HAProxy 就采用带负载的一致性哈希算法来进行数据分片。

• 带虚拟节点的一致性哈希算法
  这种虚拟节点的一致性哈希算法，也比较简单，就是在数据映射到物理节点加一层中间层。即先把数据或分片映射到虚拟节点上，再将虚拟节点映射到物理节点上。这样我们可以根据物理节点的性能情况来配置虚拟节点的个数。
  比如我们有三台机器A，B，C，它们的性能比为1：2：3 ，我们给A机器分配100个虚拟节点，给B机器分配200个虚拟节点，给C机器分配300个虚拟节点。

带虚拟节点的一致性哈希算法优点：

1. 解决了物理节点的异构性问题，我们可以根据机器的性能不同，而分配不同的虚拟节点数，再将虚拟节点映射到哈希空间环上，数据整体上更均衡。
2. 当一个物理节点挂了之后，它对应的N多个虚拟节点需要移除，这些虚拟节点的数据按照顺时针的方向，找到的物理节点很可能是不同的物理机器，从而不会因为机器挂掉而导致另外一台物理节点压力过大的问题。

memcache 就采用带虚拟节点的哈希一致性算法。

这里面稍微说下，数据分区和数据分片，数据分区是从数据存储的维度划分，不同的分区一般位于不同的物理节点上，可以存储相同的数据也可以存储不同的数据。数据分片是从数据本身出发，每个分片是数据集合的一个子集。