背景
在一次游泳的时候，想起一个问题，为什么 hdfs 的 namenode 没有存储块的对应节点信息，导致启动 hdfs 的时候，datanode 需要扫描所有的数据块，再将该 datanode 上的块信息发送给 namenode，namenode 才能构建完整的元数据信息。根据文件和数据块的多少，启动 hdfs 的时候需要几分钟到几个小时。
对比下分布式数据库，如果把记录对应的节点信息发送给 Master，那就不可想象了。所以在分布式数据库中 hdfs 的存储策略不可取。同时最近一直被目前的分布式数据库的存储上有几个问题困扰着:
- 在节点数固定的时候，Hdfs 的数据是根据机器负载来决定存储在哪个节点上的，这样做的好处是数据平均分布，可以根据机器的存储大小加权平均，并且依据机器的负载情况动态调整；目前分布式分布式数据库中做的很有限，该如何改进呢
- 添加新节点的时候， Hdfs 配置好新节点指向的 namenode，然后启动新节点即可，存储过一段时间会收敛到平均，如果想加入后马上使得数据平均分布，可以执行 rebalance 操作；而分布式数据库添加节点的时候，配置好新节点指向的 Master，然后启动新节点之后，通常还需要根据分布的规则进行数据重新分布，甚至规则也可能需要进行拆分合并扩展等修改，分布式数据库能做到什么程度，如何做 当然如果能做到数据重新分布，rebalance 的操作也就可以加入到分布式数据库中，两者是共通的，都是做数据的移动，数据重新分布关注过程，rebalance 关注结果。
Hadoop 中的 hdfs 和分布式数据库的对比
在进一步的讨论如何改进分布式数据库的存储之前，先看看分布式数据库和 hadoop 中 hdfs 的对比。
Figure 1: 分布式数据库的架构
Figure 2:hadoop 中 hdfs 的架构
前面提到分布式数据库中把记录对应的节点信息上报给 master 是不可行的方案，这里其实是一种夸大的对比，两者中的概念按照如下的类比更加合适：
从以上的对比可以看出，如果分布式数据库的节点如果和 datanode 一样，能够在启动的时候扫描该实例上的表信息，上报给 master，那么分布式数据库的做法就可以和 hadoop 中的 hdfs 方式一样，即表的分区随机分散在 dbnode 上，这样元数据的大小也不会特别大。但我们需要注意到这种随机的方式，使得读写数据的时候，客户端需要知道数据位于哪个或者哪些节点，这样对已有数据的读写需要经过两步，首先请求 master 数据位于哪个节点，如 hadoop 中 hdfs 需要向 namenode 请求读写数据所在的 datanode 信息，然后在向 datanode 发送读写命令；如果数据是有规则的分布在节点中，那么可以将这些规则信息存储在客户端中，避免读写操作频繁请求 master，这对高并发的场合非常有效。所以这篇文章我们还是抛弃随机的分布，采用有规则的方式来讨论分布式数据库的存储。
核心思想
从存储架构和概念上看这两者非常的相似，甚至都可以归一化了，所以分布式数据库的 sql 计算也可以借鉴 hadoop 中的 mapreduce 计算模型，这篇文章主要讨论存储的改进，为计算打好基础；从上面的背景和问题可以看出，hdfs 有缺点，也有优点；目前的分布式数据库有不足，也有比 hdfs 做的好地方；这篇文章基于这些优缺点，带着这些问题，采众家之长，对目前的分布式数据库的存储进行了分析和改进，为基于分布式数据库的分布式 sql 计算能够更好的利用 hadoop 生态圈中的 mapreduce，spark 等分布式计算模型打下良好的基础。
从上面的问题中，经过思考可以发现，分布式数据库的数据是不能随机分布的，是必须有规则的，但是规则需要能够动态调整，才能解决以上问题，同时没有 hdfs 启动扫描数据块导致启动时间过长的问题。正因为规则是需要能够动态调整的，所以需要采集数据库节点的负载情况，因为这是规则动态调整的依据。下面就具体分析如何做，有哪些方式可以做。
负载情况
需要采集的负载数据，大概包括如下方面:
- 机器的 cpu，内存使用，io 情况，网络流量，磁盘存储大小等
- 数据库的存储大小，qps，tps，慢查询，锁，临时表，连接数等
这些指标中比较关键的指标任何一个超过了它的阈值，这节点就不可以再插入数据，每个指标的阈值根据机器的配置决定；
下面给出一个指标的阈值例子，如下表所示:
通过这只指标可以计算一个值 db_node_load(0<=db_node_load<=1，0 表示没有负载，1 表示负载已满)，并且设置一个阈值 insert_load_threshold，db_node_load 小于 insert_load_threshold 的时候，这个节点是可以插入数据的； db_node_load 大于等于 insert_load_threshold 的时候，这个节点是不可以插入数据的；这里只考虑了插入；对于删除，都必须在这个节点执行；对于更新，如果更新前和更新后的数据都在该节点上，也必须在这个节点执行；如果不在同一个节点，那么在当前节点删除，重新按照规则加负载情况选择一个新的节点进行插入。计算 db_node_load 的公式是每个因素的当前值除以该因素的最大值的加权平均，指标的最大值根据机器的配置决定，各个指标的所占比例的例子如下：
那么 db_node_load = 20%*300/600 +8%*5/100+ 20%*10/100+ 2%*80/100+ 20%*200/500+ 10%*1000/10000+ 10%*50/1000+ 10%*2/50 =0.239
数据分布规则
所谓的分布规则，包含两个要素
- 分割字段，也叫均衡字段， 存储数据的时候决定将数据插入分布式表的某个节点的依据字段，可以是一个或者多个有顺序关系的字段，字段可以是数字，也可以是字符串，字符串通常转换为数字；如常用的用户 id
- 分割方法，也叫均衡策略， 存储的时候决定如何根据分割字段将数据插入分布式表的某个节点的方法，如列表，范围，取余
基本均衡策略
先简单举例说明基本的均衡策略，基本信息如下：表名字：tab_user_login表描述：用于存储用户登录信息节点数：4，分别为 0、1、2、3字段信息：
列表
以登录省份作为均衡字段
范围
从 0 到一亿，以用户 id 作为均衡字段
取余 (节点数为除数，即除以节点数取余数)
以用户 id 作为均衡字段，节点数为 4
基本均衡策略的分析
- 列表的均衡策略使用的场景主要是依据几个列表值，如省份，大区，按月存储等，多个列表值可以存储到同一个节点中；
- 范围的均衡策略，根据需求确定数据的最大最小值，然后根据每个节点的存储计算能力和节点数决定每个节点分配范围，即按照节点能力进行加权平均分配，范围小的数据分为到 id 小的节点上；需要增加节点的时候，从以前最大节点的最大值开始，为新添加的节点重新分配数据的范围；这种均衡策略的应用场景比较广泛， 可以使用在自增的虚拟 id，用户 id，时间等字段上面；而且在分布式数据库中执行 select 查询的时候，涉及到 order，group，非等值 join 等需要排序的操作，并且这些操作的字段是均衡字段的时候，洗牌 (shuffle) 就可以忽略，因为节点 id 是顺序的，节点 id 小的节点中存储的数据小，再加上均衡字段上通常有索引，排序的操作会非常高效。 这种均衡策略也有一些不足，数据是否平均分布依赖为每个节点分配的最大最小值；如果数据是虚拟 id 作为分割字段，递增，插入的数据基本上都是在最大的节点中，其他节点基本上没有插入，只有查询；如果数据是用户 id 作为分割字段，新注册的用户 id 是递增，那么新注册的用户数据基本上都是在最大的节点中，数据分步有个明显的特征，连续注册的用户的数据基本都在相同的节点中，这样在高峰期，推广期，活动期某些节点的负载比较高，负载就会出现不均衡；
- 取余的均衡策略能够解决范围的均衡策略节点负载可能不均衡的问题，数据理论上是平均分布的；但是如果节点之间的性能是不平均的，那么就存在木桶效应，每个节点的存储容量和性能最大值 (性能瓶颈) 就是性能最差的那个节点；同时这种均衡策略不具备范围的均衡策略中某些场景中洗牌和排序的高效特征。
基本均衡策略下的数据重新分布
前面提到规则需要动态调整，或者数据重新分布，这里指的是调整某个均衡策略内部的参数或者规则数据本身，而非转换均衡策略， 这三种均衡策略下的数据重新分布如下：
- 列表的均衡策略需要将变动的列表数据重新分布，如上面的例子中将黑龙江省的数据从 2 号节点移动到 3 号节点，那么只需要移动黑龙江省的数据；
- 范围的均衡策略，可以移动节点中的整个范围，也可以移动节点中的部分范围，从这点来说，范围的均衡策显得更加灵活，如上面例子中将用户 id 范围为 2500w <=value<5000w 的整体范围从 2 号节点移动到 3 号节点，也可以将用户 id 范围为 4500w <=value<5000w 的部分范围从 2 号节点移动到 3 号节， 用户 id 范围为 2500w <=value<4500w 的部分范围保留在 2 号节点；
- 取余的均衡策略比较特殊， 列表和范围的均衡策略在节点数不变的时候可以重新分布数据，而取余的均衡策略则不能重新分布；如果增加节点数，节点 id 依次增加，计算新的节点数和老的节点数的最小公倍数， 一条记录的均衡字段对最小公倍数取余，如果余数小于等于老的节点数 (小的节点数)，那么这条记录不用移动，否则需要移动这条记录到均衡字段对新的节点数的余数对应的节点中；如果减少节点数，删除节点 id 的大的节点， 计算新的节点数和老的节点数的最小公倍数， 一条记录的均衡字段对最小公倍数取余，如果余数小于等于新的节点数 (小的节点数)，那么这条记录不用移动，否则需要移动这条记录到均衡字段对新的节点数的余数对应的节点中；举例说明，增加节点的时候，从 4 个节点增加到 6 个节点，4 和 6 的公倍数是 12，用记录的均衡字段对最小公倍数取余，结果为 0 到 11，那么余数 0 到 4 的记录不用移动，余数为 5 到 11 的需要移动；减少节点的时候，从 8 个节点减少到 6 个节点，8 和 6 的公倍数是 24，用记录的均衡字段对最小公倍数取余，结果为 0 到 23，那么余数 0 到 6 的记录不用移动，余数为 7 到 23 的需要移动。
组合均衡策略
两个基本均衡策略的组合
以上的均衡策略可以任意的组合，如果选择两个，则有六种组合的均衡策略。
挑选比较典型的序号为 4 的组合， 先使用范围，再使用取余为例进行说明
先使用范围，再使用取余
例如，以用户 id 作为均衡字段，每个范围有 10000 个值，节点数为 4，那么结果如下：
从这个例子中，可以发现， 先使用范围，再使用取余的组合策略可以综合两者的优势，包含范围的大小顺序和取余的数据平均分布优势，但其实也在一定程度上削弱了优势，具体的说，某个表的记录就不是总体上按照顺序大小存储，而是每 10000 条记录这个小范围内是有顺序大小的，每 10000 个的节点分布是按照取余规则的分布在不同的节点上；某个表的数据也不是在记录级别上平均分布，而是以 10000 条记录为粒度进行平均分布的；我们设计的时候需要根据实际情况来确定是选择 10000，还是 1024 或者 1048576 等。选择的越小 (细粒度)，在动态调整的时候也可以更加灵活；在实际中，节点数通常不多，那么细粒度就会打折扣；如 4 个节点，我们需要移动 1 亿条记录中的 1000 万，那么每个节点平均需要移动的是 250w， 每个范围有 10000 个值就显得小了，导致范围数就多，元数据就显著增加；如果有 10 个节点，那么每个节点平均只需要移动 100w 记录。同时观察上面的例子，可以发现，取余之后的值 V2 和节点 id 是一一对应并且数量一致。但其实我们也采用其他方式，如列表，范围和取余方式；处理方法是将取余计算中除数换成的节点数的倍数 (而非节点数本身)，具体几倍依据数据量的大小和以后系统的扩容需求； 这种实际上已经是三个基本均衡策略的组合了，在下面的讨论中，这种方式对元数据的大小没有显著的增加， 通常选择较大的数比较好，如节点数的 8 倍，32 倍甚至 128 倍。
三个基本均衡策略的组合
按照上面的分析， 三个基本均衡策略的组合是基于两个个基本均衡策略的组合，如下：
先使用范围，再使用取余，再使用范围
例如，以用户 id 作为均衡字段，每个范围有 10000 个值，取余的除数为 32，结果如下：
在上一步得到 V2 的基础上，如果节点数为 4， 那么每 8 个余数顺序放到节点中，结果如下：
先使用范围，再使用取余，再使用取余
例如，以用户 id 作为均衡字段，每个范围有 10000 个值，取余的除数为 32，结果如下：
在上一步得到 V2 的基础上，如果节点数为 4， 那么 V2 按照 4 取余，意义对应到节点 id，结果如下：
这两种均衡策略的结果从效果上看都是先使用范围，再使用取余；最后使用范围策略的使得每 8 万一个范围，最后使用取余策略的范围还是 1 万一个，除数都为节点数，这样一来，使得数据重新分布的灵活性增加，同时不失规则性，为数据的动态重新分布打好基础。
数据动态重新分布
首先介绍一个概念移动逻辑数据块，或者叫数据窗口 (move logic data chunk)， 移动数据时，一个节点内可以移动到另外一个节点内的连续实际数据记录数。需要根据老的分布规则和新的分布规则的确定，通常是针对范围的均衡策略或者包含范围的组合均衡策略，窗口的大小要小于等于移动的数据所处的那个范围的大小，如范围的均衡策略例子中，0 号节点中 0<=value<2500w ， 那么数据窗口可以选择 1 到 2500w 中 2500w 的因子，如 1000，100w 等，太小导致窗口数太多，太大导致窗口数小，并发数提高不了。 进一步说，窗口的大小是老的分布规则和新的分布规则中数据所处的那个范围的大小的公约数，实际中两者是倍数的关系，取小的即可，如果小的数也比较大，如 500w，还可以取这个数的足够小的某个约数，如 1w。
场景
下面从以下几个场景说明数据动态重新分布:
1. 插入数据的时候，本来这条记录需要插入节点 A，发现节点 A 的负载高，不允许插入，这时调整规则，将节点 A 中的这条记录所处范围的一部分或者整体移动到 B 节点；
2. 加入新节点的时候，需要将原来某几个节点 (如 A1 到 A4) 上某些范围的一部分或者整体移动到新节点上；删除节点的时候， 需要将删除的节点 (如 A3 到 A4) 上范围整体移动到其他不删除的节点上；
3. 发现数据不均衡，人工手动触发数据重新分布，这种场景和加入和删除节点，本质上没有区别，就是在已有的节点中移动数据，而不涉及新加的或者要删除的节点。
业务影响分析
数据的移动，特别是大量数据的移动，势必对业务的操作带来影响，如果控制不好的话，可能是灾难；问题列举如下:
场景 1 下，插入的数据是先插入老节点再移动还是先移动再插入新节点，先插入情况下可能偶尔数据库本身负载高到不能插入，先移动情况下，可能导致插入延迟又比较大，导致用户响应比较慢；
场景 1，2，3 下，移动数据窗口的时候，业务上可能对这个窗口进行数据操作，插入，更新，删除都有可能，时间上可能业务先操作和锁定记录，然后移动，也有可能先移动，移动过程中，操作了已经移动的数据或者操作和锁定还没有移动的记录；
如何处理数据重新分布
设计好的系统，可能不太需要数据的移动，但是从一般的角度考虑，它是一个比较频繁的操作，而且涉及跨节点的插入数据，删除数据，修改规则元数据，这三者需要在一个事务中完成，所以需要使用分布式事务。为了保证移动数据的时候业务的正常运行，我们需要做如下的设计：
- 场景 1 的先插入还是先移动的问题，可以动态调整，在插入很少的记录的时候，先插入，再移动，如果运行中先插入失败，则退化为先移动在插入；在插入大量的数据的时候，先移动，再插入；这种场景应该不多见，很多情况可以直接插入，移动去让后台线程来完成。
- 场景 1，2，3 下业务操作了需要移动的数据的问题，调整移动的窗口大小，使得一个窗口的处理时间控制在可以接受的时间以内，一个窗口的内的数据一次锁定，例如时间设置为 1s，窗口大小选择 2k，使用 select for update 来锁定，最后直接删除这些记录，最后更新规则元数据。对于窗口比较大的情况，可以数据操作可以将大窗口调整为小窗口，每个小窗口使用以上的处理方式，同时业务的操作使用类似触发器的检查机制来同步更新到新节点上，具体的说：
o 对于已经移动的小窗口内的插入或者覆盖 (replace) 操作，插入或者覆盖 (replace) 到新节点
o 对于已经移动的小窗口内的删除操作，在新节点删除对应记录
o 对于已经移动的小窗口内的更新操作，在新节点更新对应记录
以上所讨论的数据重新分布主要是确定好前后的规则，后面的工作就是根据前后的规则去迁移数据和修改元数据
使用范围的数据动态重新分布
如老的均衡策略从 0 到一亿，以用户 id 作为均衡字段； 分布如下:
场景 1:4 个节点存储或者性能都达到了阈值，需要扩容，计划每个节点拆分成两个相等的部分，那么新的分布结果如下：
场景二：3 号节点由于性能不足，添加一个 4 号节点， 3 号节点的数据拆到 3 号和 4 号中，同时扩大用户范围到 4 亿，使用性能比较高的 5，6，7 号节点，每个节点存储一个亿，那么新的分布结果如下:
使用先使用范围，再使用取余的数据动态重新分布
举例说明，以上的先使用范围，再使用取余作为老的分布，如下:
场景 1: 现在需要按照 20000 一个范围，那么就是每 8w 条记录平均分布在 4 个节点中，新的分布结果如下:
小结
数据的均衡策略或者分布规则是一把双刃剑，Hdfs 的数据是随机的，节点上报的形式，所以能够动态调整，无需数据重新分布，缺点是启动需要扫描，导致启动慢；分布式数据库的均衡策略是有规则的，规则通常存在在元数据中，Master 启动时加载元数据就可以，元数据通常很小，所以启动很快；但是规则的动态调整比较麻烦， 数据的重新分布也是必须的工作；基本的规则比较简单，但调整动态调整量比较大，耗时长；组合的规则稍微复杂，但调整的数据量会缩小，耗时短。 |
