5.1 分布式系统分区之数据拆分

把key尽量平均分配到各个partition/node上

1. 拆分key的选择

1.1. 主键ID

比如自增主键。优点是数据分布均匀，缺点是根据业务字段查询慢时需要读取所有分区

1.2. 业务ID

比如用户ID、商品ID等。优点是根据业务字段查询快，缺点是数据分布可能不均匀

1.3. 举例

• MySQL由程序员手动指定，可以是主键ID，也可以是业务ID
• Redis本身就是key-value数据库，所以直接使用key，可以理解为业务key
• Kafka使用key，可以理解为业务key
• Zookeeper没有使用分区
• Elasticsearch使用自动生成的主键ID，可以自定义业务ID

2. 拆分策略

2.1. assigned paritioning

• 指定分区
  • 手动指定key分配给某个partition

2.2. random partitioning

• 随机分区
  • key随机分配给partition

2.3. range partitioning

• 顺序分区
  • 为每个partition指定一块连续的key范围（从最小值到最大值）
  • 比如user:1->user:N，把user:1-user:1000的分到partition1，user:1001-user:2000分到partition2，依此类推

2.4. hash partitioning

2.4.1. hash%N

• hash%N

  • 计算key的hash值，对partition总数量取模，然后把数据放在取模结果的partition上即可。

• 好处

  • 简单高效

• 坏处

  • 如果某台机器宕机了，那么有(N-1)/N台缓存不命中
    • 为何是 (N-1)/N 呢？ 比如有 3 台机器，hash值 1-6 在这3台上的分布就是：

      host 0: 3 6
      host 1: 1 4
      host 2: 2 5

    • 如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成：

      host 0: 2 4 6
      host 1: 1 3 5

    • 可以看到，还在数据位置不变的只有2个： 1，6，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3。

• 使用场景

  • 一般数据库分库分区使用这个方案，并且采用翻倍扩容以减少数据迁移量。为什么不使用一致性Hash呢，一致性Hash需要确定partition数，而如果partition数确定那么后续就无法扩容了 -

2.4.2. consistent hash partitioning

• 一致性Hash
  • 每个partition负责一个hash值范围，计算key的hash值，确定这个hash值是哪个partition负责的hash范围即可

2.4.2.1. hash ring partitioning

• hash环：
  • 求出服务器partition的hash值，配置在0-2^32-1个partition的圆上
  • 求出key的hash值，同样将其映射在圆上
  • 从key映射的位置开始顺时针查找，保存在第一个服务器上
  • 
• 好处
  • 如果某台服务器挂了，那么这台服务器的key会顺时针转移到下一个服务器上，只有1/N不命中
• 坏处
  • 数据倾斜：服务器过少时，数据不是均匀分布在圆上，可能大部分key都会落在同一个partition上，导致其压力过大
  • 无法解决热点key的问题：通过有限一致性Hash解决

2.4.2.1.1. hash ring+virtual node

• 对每个服务器partition计算多个hash，配置在圆上
• 数据定位算法依然不变
• 优点：解决数据倾斜问题
• 缺点：添加一个partition时迁移的数据多。如果全是物理partition，加入一个物理partition只会影响一个和他相邻的partition。如果是虚拟partition，加入一个物理partition所生成的虚拟partition，会影响的partition比较多，但是影响的范围会变小

2.4.2.2. slot partitioning

• 哈希槽：
  • Redis集群没有使用一致性hash，而是引入了哈希槽的概念。
  • redis cluster有16384个hash slot用于存储数据，每个partition负责一部分slot。
  • key通过CRC16（key）% 16384计算属于哪个slot进而决定分配在哪个partition上
    • 
• hash ring vs slot partition：本质上都是增加了一层来保证key hash之后映射的位置（一致性Hash是直接用hash定位，Hash slot取模的数是16384也是固定的）不会随partition的个数变化而变化

2.5. random vs range vs hash

	random	range	hash
优点	在所有partition上平均分配数据	范围扫描非常高效，天然支持水平扩展	键的范围比较均匀分布
缺点	查询一个数据需要并行的访问所有partition	会有热点数据的问题，比如新增加的数据集中在一个partition会有写入瓶颈	范围扫描效率低

2.6. 举例

• MySQL由程序员指定，一般使用Hash%N
• Redis使用consistent hash中的slot partitioning
• Kafka默认使用range，可以是Hash%N，或者指定分区
• Zookeeper没有使用分区
• Elasticsearch使用Hash%N