# DDIA第六章: Partitioning

---

tags:

* ddia
    
* 读书笔记
    

---

在分布式数据存储的系统中，Partition(分片)是绕不开的一个技术点，原因在于随着数据规模的增加，总有一天需要一台机器装不下所有的数据的时候，所以需要将数据进行切分并且存放到各个机器上去；对于整个系统来说，分片也会极大的提升系统本身的scalability; 如果所有的数据都存储在一台机器上，那么就表示通过增加机器无法为系统提供扩展性；

当然这个技术已经在不上的数据存储系统中应用；当然不同的系统所叫的名字各不相同；

* Mongodb: shard, 这个算是物理意义上的分片，比这个更加小的话叫做chunk
    
* Hbase: region
    
* bigtable: tablet
    
* Cassandra: vnode
    

等等..

## 1.分片有哪种方式并且各自的优缺点是什么？

### 1.1 按照range进行切分

通常数据都会包含有一个`primary-key`,当然也可以不用`primary-key`但是一定会有一个key用来做为切分的依据；而所谓的range进行切分，通常是按照是字典排序的顺序进行切分，每个region会包含`[min,max)`，在同一个region的数据按照切分依赖的key是有序的；有点类似于字典，如果按照word的首字母进行切分，那么第一个region就是A开头，这里面包含了所有的A开头的word，并且是有序排列；

这种切分的好处是:

1. range scan会非常快，正常的切分是按照primary-key，那么如果对primary-key进行range-scan就会非常快，因为这些key是存储在一起，并且有序…类似于你查字典以A开头的word，那就是第一个区域遍历即可；
    
2. range查询性能：range查询会集中在某一些partition上，而不会在全部的partition上；这其实很重要，因为会限制你查询性能的上限（后面解释）；
    

缺点：

**倾斜问题**：不管是read还是write，甚至于存储的空间都会倾斜的很厉害的；而且极端容易出发hotspot的问题，导致整个服务集群出现不可用；

### 1.2 按照hash分片

range分片的问题很明显，而且处理起来并不是很简单的，尤其是hot spot的问题，出现了除了限流就只能限流，可以加入平时的rebalance的机制，但是rebalance本质上都是一种比较重的操作的；而hash分片就是应对这种倾斜问题所提出的；

依照上面提到的，range 分片是按照某一个用户指定的key来进行分片，那么hash分片的唯一的区别在于依据变成了`hash(key)`计算之后的数值进行分片；因为有hash函数的存在，即使只是普通的md5，都能很好的达到所谓的随机性，这样可以把原本相关的数据分散到不同的partition上的；这样就极大极大概率减少了所谓的倾斜问题；

* 优点
    
    1. 相关数据会被分散到各个分区，减少了数据倾斜和热点问题的产生
        
    2. 单点query也是非常快速的；
        
* 缺点
    
    1. range-scan：对于hash分片的数据，其数据相关性已经被hash函数所打破，所以相关的数据不会在同一个分区，而且你也不知道和没发去跟踪所在的partition；所以针对的range scan或者模糊查询都是需要被发送到所有的partition上；这会导致一个短板效应，latency会依赖于最慢的partition返回的时间的；
        
    2. 性能：每一个range-scan都要往全部分区上查询，那么整个集群的range-scan性能就是单节点的range-scan的性能，所以上限很明显；
        

是否可以兼顾呢？通常的方法是组合索引，本质上依然还是range分片，但是用户主动将相对随机的字段加在最前面，从而达到随机的效果；这个需要用户去识别，尤其是第一个字段是否足够的随机；还有就是这种情况的话，想要有比较好的range-scan的查询的话，只能按照组合索引的顺序去查询，比如组合索引`(a,b,c)`,那么你有效率的scan的方式是提供`a or a,b or a,b,c`这种模式，一定要有顺序，因为索引第一部分是a字段，你不能只使用`b`来进行查询，因为这样不能明确找到具体的partition，那就全量搜索。

### 1.3 关于负载倾斜和热点问题

上面讲到了hash 分片可以解决绝大多数的热点问题，但是这也只是绝大多数而已；依然还有会一些corner case让你不得不面对的；其中比如单key的多量访问，比如就对某一个key进行过量的并发访问最终导致对应的分区出现过载，最终导致服务短暂不可用的；对于这种情况的话，解决的方式其实有几种：

1. 服务保护；即当系统出现过载的时候，限流熔断机制的引入可以帮助系统可用性的提高的；当然这其实就是所谓的系统极限，对外用户来说体验可能不算太好；
    
2. 可以适当引入所谓的cache，但是cache也会面临单机的硬件瓶颈；比如就是网卡打满了什么的，这种时候依然还是不能解决本质上的问题；
    
3. 系统本身能自动去检测数据倾斜或访问热点的时候，通过对于key+random num来进行分散，这样调整整体数据的倾斜性；但是这种方式带来的问题是有几个：
    
    1. 需要维护这种meta-信息，尤其是需要记住哪些key做了类似的操作，而且也查询也变得更加麻烦，需要同时向所有的randum key进行查询
        
    2. 反应的速度太慢，需要检测并且加入所谓的均衡机制；对于read倾斜来说，不要到要何年马月才能有效果；对写倾斜可能效果会比较好；
        

当然现在很多系统目前还没有所谓的这种机制，起码没有自动检测和实施的机制，估计未来会出现的；

```markdown
关于这段我也是深有感触，之前维护过规模比较大的mongodb集群的；不同区域的mongodb集群选择了不同的分片模式的：
整体使用下来range分片模式在维护过程中整体的需要关心的事情还是太多的，尤其是负载均衡和热点问题的，动不动就因为热点请求导致服务抖动严重的，而且mongodb集群的负载也很不均衡，这个里面是由于mongodb按照的是chunk的个数进行均衡，但是不考虑真实数据的均衡程度，所以时不时就需要进行调整，当然hash也有这个问题，但是整个的存储均衡好不少的；所以后期新开集群我们默认使用的hash分片，因为当时的mongodb整体的自动化做的不好，虽然我们在外围一套工具进行均衡和迁移，但是依然是很麻烦的操作；
当然hash也遇到了一些问题，老板观察到整个模糊查询的性能已经达到了上限，希望后面能提到更加好的，这样可以做更多的事情；但是模糊查询或者range-scan在hash分片中本身就是需要发送到所有的partition进行查询的，单机瓶颈就是集群瓶颈，所以如果要提高可能需要思考其他的方案；

关于极端情况的hot spot问题，我们当时也遇到了，就一个用户疯狂的查一个key的value，并且这个value有点大，就导致了单partition的网卡被打满了，整个集群就开抖动；对于这种问题，后期我们基本是限流熔断的方式来进行，没有从本质上去解决这个问题；

DDIA很多章节讲的真的很不错的，缓缓道来，并且该讲的都讲到了；
```

## 2\. 第二索引分片的问题

第二索引主要是提升用户的使用方式的，可以用其他的字段进行索引，增加了业务上的便利性的；那么对于第二索引数据存储也是一个问题的，因为不可能存储在同一个节点上，也涉及到了所谓的分片的问题；常见的方案有两种：

### 2.1 按照文档进行分片

> 这种方法本质上就是数据在那个节点，就在那个节点进行索引存储的；别名叫做：`a local index`

这种方法应该是比较常见的方式的，这样每一个分片的索引是独立的，只对当下的数据进行负责的；对于这种分片的优缺点分析：

* 优点：
    
    * 整个写入逻辑比较简单的，而且写入数据和index是在同一个节点做的，更加方便做所为的事务
        
* 缺点：
    
    * 对于模糊查询可能需要查询所有的分片；因为正常情况下，路由层是没办法对除了主键以外的条件进行有效的效率上的过滤的；那么就会遇到hash分片的问题；
        

### 2.2 按照Term进行分片

> 这边的term，书上的解释看上去更加是类似于具体的二级索引构建的key，也就是按照真实的索引key来进行分片；可以这么去思考：索引的分区依赖于具体索引组成的key； 这个索引方式的别名: `a global index`

这个时候数据和索引其实是本分离在不同的节点上的；

* 优点：每次查询可以根据查询的条件优先过滤，找到部分的分区，然后快速找到所有相关的数据；其实本质上也是range分片的过程；通过索引找到所有的id然后再去根据id的list查询所有的数据；
    
* 缺点：很明显的复杂度变高了，而且数据和索引的原子性就很难把握了；如果index写入成功，数据还在写入的过程中，查询发现索引有但是数据层没有，这种不一致性就很难把握；再加上故障处理等等，会有不少的用户体验；
    

```markdown
这两个索引我在之前的工作环境中都遇到过；
1. mongodb的索引是使用第一种方式的；模糊查询的话，尤其是没有涉及到分区key的模糊查询的话，那必然就会触发全分区的查询的；但是如果在查询的时候加入所谓的分区key的部分的话，在range分片下还是有一定的优化的；
2. 一个朋友的公司在内部做influxdb的分布式架构，influxdb的索引数据和时序数据本身就是用了第二种方式的，不是很确定关于不一致部分是如何处理的；我猜可能是先写数据再async同步index吧；这样只会触发所谓的index延迟，而不会出现index有数据没有这种情况的；
```

## 3\. rebalance

和开头讲的一样，分片的好处是为了提升集群的可扩展性的；当新节点上线之后，需要去别的节点拉取一些分片到自己的节点，从而开始分担集群的服务；如果系统发现一些节点的负载过于沉重，需要系统将当前节点的部分分区迁移到其他的节点上，用来减轻当前节点的压力的；而这种迁移的过程就是所谓的`rebalance`

### 3.1 Rebalance的策略

* 不要使用`hash(key) mod N`这种方式；
    
* 固定分区数量
    
    在集群初始化的时候已经确定了分区的个数，后面的运行过程的时候分区的个数是不会变换的；但是分区到node之间的关系可以是人为指定或者自动自动执行的；
    
* 动态分区的方式
    
    所谓动态指的是系统会设置每一个分区的max value，可能是数据的条数又或者是存储大小等等，也就是说系统会根据运行情况，记录每一个分区的大小，如果达到了所谓的max value就进行split，又或者当两个相邻的分区都很小的情况下进行merge；这样系统的分区的个数是在变化的；
    

rebalance迁移的最小维度是`分片`,每一个节点上存储了多个分片；当系统觉得当前节点有太多的分片或者压力过大的时候，就会启动将当前的节点的部分分区迁移到其他的节点上的；这个过程就是rebalance的过程的；

### 3.2 rebalance 自动还是人工

理论上应该是需要自动的，但是rebalance是一个很重的操作的，有的时候会影响到正常的读写请求的，所以需要去trade-off；按照目前的技术发展自动化一定是趋势的；

```markdown
mongodb的rebalance机制比较单一，老版本是按照chunk的个数做均衡，新版本加入了按照数据存储余量来进行均衡；但是这种单一的均衡策略并不能解决读写不平衡的问题的；尤其是range分片的情况下；
所以我们在维护mongodb集群的过程中，加入了外围的工具，加各种策略去判断哪些节点压力比较大的，然后通过mongodb自带的迁移分区的command来迁移；关于这块我觉得mongodb现在做的并不是很好的；

关于为什么rebalance是一个比较重的op呢？因为实际上分片本质上是一个逻辑上的概念，它并不是真的类似于物理隔离在一个节点上的；当然这几年已经有不少数据库的公司开始思考做成物理隔离；这样迁移的过程整体的波动会小很多的；因为在节点维度多个分片数据是融合在一起的，所以你在迁移的时候需要先去找到这些数据，然后进行迁移，并且迁移完毕之后再删除的；整个过程，当分片比较大，或者分片数比较多的时候，其实会消耗比较多的当前节点的资源，而且迁移本身涉及到了网络带宽和本地的磁盘io、cpu的占用，不控制好的确会影响到了当下的在线业务；

不同的数据库系统都会给予一些配置来进行控制，比如每次只能同时启动一个分片的迁移的，这样的方式来保证影响范围的；
说一下物理隔离的好处，如果是真实的物理隔离，那么进行迁移的时候只需要消耗少许的io和网络即可，不会因为查询数据对整个节点的内存什么的进行很大的影响的；而且删除也只是物理层面的直接delete，这个就很好，之前听TIDB目前就这么做，每一个region一个rocksdb，当然他们的说大概一块nvme的话放2000多个rocksdb问题不大的；如果真的是这样，其实好处真的不少；分布式系统的迁移问题真的很麻烦的，涉及到到的状态很多的，并且又要控制影响，快了不好，慢了就赶不及；
```

## 4\. 请求路由

既然数据被分散在多个节点上，那么client的请求如何路由到正确的节点上呢？这个问题更加普通的叫法是: `service discovery`，并不只是限制在数据库领域；对于这个问题目前业界的几个解决方法是:

![image](https://cdn.nomoshen.com/typora_img/image.png align="left")

1. 允许client可以连接所有节点，这个节点会作为中转节点，把请求转到正确的节点上去的；
    
2. 有一个单独组件叫做`routing tier`,路由层,client直接访问的是路由层，由路由层去请求到正确的node；这就表示路由层需要感觉到底层分区部署的变化的，这样它才能路由请求到正确的node上去；要如何做呢？通常系统会依赖类似于zookeeper的组件，通过监听zookeeper的节点变化来感知底层分区的变化，这种架构由kafka，hbase等等，mongodb的话，路由层是mongos，configserver就是作为zookeeper的角色存在；当然和zk的监听不一样的是，mongodb还有一套触发机制，让mongos主动去拉configsrv来进行更新；
    
    由另外一种方式是cassandra类似的系统使用的，节点之间使用gossip的系列就传递集群的节点的信息，原因是cassandra这类系统数据存储在什么节点是通过计算获得的，而并不是存储起来的，但是关键计算的信息是集群的node信息，所以节点变化是需要传递到所有的节点的；但是gossip这种协议最终收敛，但是时间上不确定的，所以比较复杂…好处你可以感知到的就是meta信息需要保存的很少；
    
3. client直接连接到正确的节点上，如果连接不到正确的节点，错误节点会和它说你应该去什么节点，然后再直接连接过去的…redis的集群模式就是这样的；
    

## 5\. 总结

这章节主要讲了

1. 为什么要分片
    
2. 分片的2种方式
    
3. 第二索引的分片方式
    
4. rebalance的方式和面对的问题
    
5. 请求路由的几种方式
    

基本上包含了分区所有的信息, 后面会配合副本机制来来保证整体的高可用和高可扩展性；在分片这个阶段，最为重要的是如何找到合适业务方式的分区方式和如何高效的去rebalance，目前不同数据库系统的rebalance的大致机制是类似的，但是实现上会有一些差别，但是这样也会让效率差别很大；