关于数据库:一种自平衡解决数据倾斜的分表方法

作者：京东批发 梁强

1、背景

这篇次要形容了 B 端令牌零碎利用数据分表解决业务数据量增大，且存在的数据歪斜问题，次要面向的场景是一对多数据歪斜问题

1）B 令牌的业务背景

先简述一下 B 令牌的业务背景，B 令牌零碎是用于营销场景中，将许多用户绑定在一个令牌上，再将令牌绑定在促销上，从而实现差别和精准营销，个别状况下一个令牌的生命周期等同于这个促销。

2）B 端令牌的构造现状

令牌和令牌用户关系是一个一对多的关系，晚期的令牌零碎应用 jed 分库，2 个分片，两头进行了一次扩容达到了 8 个分片，存储的数据行数达到了 1.2 亿

3）数据和业务现状

1.2 亿数据，散布在 8 个分库中，每个分库均匀 1500 万，但因为分库字段应用的是令牌 ID(token_uuid)，有得令牌用户少，只有几千到一万，有的令牌用户多，有 100 万到 150 万，令牌总数量并不多，只有 2 万左右，所以导致数据存在歪斜，有的分库有 3000 多万数据，有的分库可能只有几百万，这曾经开始导致数据库读写性能降落。而又因为令牌用户关系表数据结构很简略，尽管数据行数很多，但占用的空间却不大。8 个分库总占用量还有余 20G。同时令牌的生命周期根本和促销雷同，一个令牌服务于一个或几个促销后，就会缓缓过期被弃之不必，后续会持续创立新的令牌。所以这些过期令牌是能够进行归档的。

同时因为 B 端业务的倒退，业务诉求也更多，和业务沟通中理解到，将来会上线主动选人零碎，由零碎主动创立令牌，并抉择适宜促销的人群，将来每个月数据增量在 3000 万左右，如果运行一年就会减少 3.6 亿，届时单表数据量均匀会达到 6000 万，以后的设计架构曾经齐全不能满足业务需要。

同时目前也存在依据令牌 ID 分页查问令牌下用户的性能，但仅限于给治理端经营应用，应用也不频繁。

2、解决方案的思考

1) 怎么解决这个问题

面对日益降落的数据库读写性能，以及业务增长的需要，当下面临以下几个问题：

1. 如何解决单表数据行数过多的问题
2. 以后分库计划存在比较严重的数据歪斜
3. 如果应答将来数据的增长

2) 技术计划调研和比照

a. 数据库分表

个别状况应答第一个问题，通常都是分库分表，而当下咱们曾经是 8 个分库，而且 8 个分库才占用了有余 20G 空间，单库资源节约重大，所以齐全不会思考持续减少分库的形式，所以分表才是解决办法。

数据分表通常有两种形式：垂直分表和程度分表。

垂直分表指的是将数据的列进行拆分，而后利用主键或其余业务字段进行关联，从而升高单表数据占用空间，或缩小冗余存储，B 令牌的场景数据结构简略，数据占用空间小，所以不会应用该分表形式。

程度分表指的是将数据的行以一种路由算法拆分到多张表中，读取时候也基于这种路由算法来读取数据，这种分表策略个别用来应答数据结构不简单，但数据行特地多的场景。这也是咱们行将应用的形式。应用这种形式须要思考的就是如何设计路由算法，这里也是应用这种形式来分表。

b. 路由算法

数据分表路由算法的应用在业内也有多种，一种是利用 一致性 hash，抉择适合的分表字段，对字段值 hash 后值是固定的，应用该值通过取模或者按位运算的形式失去一个固定的序号，从而确定数据存储在哪张表中。

比拟常见的利用如分库大多就是应用一致性 hash 的形式，通过即时计算分库字段的值判断数据属于哪个分库从而决定将数据存入哪个分库或者从哪个分库读取数据。而如果查问时没有指定分库字段则须要同时向所有分库收回查问申请，最初在汇总后果。

另外像 java 代码的 HashMap 数据结构其实也是一种一致性 hash 算法的分表策略，通过对 key 进行 hash 后决定将数据存入数组的哪个序号，HashMap 外面用的不是取模的形式获取序号，而是应用按位运算的形式，应用这种形式也决定了 HashMap 的扩容都是依照 2 的 x 次方的大小进行扩容，当前有机会能够介绍这个原理。

下面就是 HashMap 中的一个简化的数据 Hash 存储过程，当然我省略了一些细节，比方 HashMap 中每一个节点都是一个链表（抵触过多还会变成红黑树）。利用在咱们的场景中就能够将每个序号当成是一张数据表即可。

以上这种路由算法的长处的路由策略简略，实时计算也不必减少额定存储空间，但也存在一个问题就是如果要扩容则须要将历史数据从新 hash 一遍进行迁徙，比方数据库分库如果减少分库则须要将所有数据从新计算分库，HashMap 扩容也会执行 rehash 从新计算 key 在数组的序号。如果数据量太大，这种计算过程耗时将会很长。同时，如果数据表太少，或者抉择分片的字段离散水平低都会导致数据歪斜。

还有一种分表算法优化了这种 rehash 过程，这便是一致性 hash 环，这种形式是在实体节点之间形象出很多虚构节点，而后再利用一致性 hash 算法将数据打在这些虚构节点上，而每个实体节点其实是负责的该实体节点逆时针方向上和另一个实体节点相邻的虚构节点的数据。这种形式的益处是如果须要扩容减少节点，减少的节点放在环上任意地位，也只会影响到该节点顺时针方向上相邻节点的数据，只须要将该节点中的局部数据迁徙到这个新节点上即可，大大降低 rehash 的过程。同时因为虚构节点多，也能够减少让数据更平均的散布在这个环上，只有将实体节点搁置在适合的地位，就能最大水平保障的解决数据歪斜问题。

比方图上就是一个一致性 Hash 环的 hash 过程，在整个环上有从 0 到 2^32- 1 个节点，其中实线的就是实在节点，其余都是虚构节点，张三通过 hash 后落到环上的虚构节点，而后从虚构节点的地位顺时针寻找实在节点，最终数据就存储在实在节点上，所以疯驴子和李四就存储在节点 2 上，王五在节点 3 上，郑六在节点 4 上。

扩容了一个节点 5 号后，则须要将节点 1 和节点 5 之间的数据迁徙到节点 5 上，其余节点数据则不必变更。但如图上看到的，只加这一个节点，也容易导致每个节点负责的数据不平均，比方节点 2 和节点 5，相比于其余节点负责的数据就少了很多，所以扩容时最好是成倍扩容，这样数据能够持续放弃平均。

3) 思考我的计划

再回到 B 令牌的业务场景上来，须要能达成以下诉求

1. 首先必须应用程度分表来解决单表数据量过大的问题
2. 须要能反对依据令牌分页查问用户
3. 因为以后业务数据增量在 3000 万，但不排除将来业务持续增长的可能，分表数量须要能反对将来扩大
4. 数据行数过高，将来在扩大时必须保障无需数据迁徙或者数据迁徙成本低
5. 须要解决数据歪斜问题，确保不因为单表数据量过大而导致整体性能升高

基于以上诉求，首先看问题 b，如果要反对依据令牌分页查问用户，就须要保障令牌下的所有用户都在同一张表上，能力简略的反对分页查问，否则用一些汇总归并算法则复杂程度过高了，而且表太多也会升高查问性能。尽管也能够通过将数据异构 es 提供查问性能，但仅仅是为了大量治理端的查问诉求再进行数据异构，老本有些高收益并不显著，也有些浪费资源。所以分表字段就只能确定应用令牌 ID。

而下面也提到令牌 ID 数量并不多，而且令牌下的用户也从 1 万到 100 万不等，单纯应用一致性 hash 的形式用令牌 ID 作为分表策略则会导致数据歪斜重大，而且将来扩容时数据迁徙老本也很高。

但应用一致性 hash 环又会导致将来在扩容时最好是按 2 的倍数扩容，不然就会存在有的节点负责的虚构节点多，有的节点负责虚构节点少，导致数据不平均。然而在和数据库共事进行沟通，一个数据库下的数据表数量不宜太多，否则会对数据库带来较大压力，而一致性 hash 环这种形式可能扩两三次容就会导致分表数达到一个很高的数值。

基于以上问题，在确定应用令牌 id 作为分表的前提下，就须要着重思考如何 反对动静扩容和解决数据歪斜 的问题。

3、计划落地

1) 计划概述

a. 如何反对动静扩容

分表的字段曾经确定应用令牌 ID，而后面也提到咱们的数据结构是令牌和用户是一对多的关系数据，那么在创立令牌时 hash 出的分表序号存储下来，后续基于存储的分表序号进行路由，就能够保障将来扩容时也不会影响存量数据的路由，无需进行数据迁徙。

b. 如何解决数据歪斜

因为选用了令牌 ID 作为分表字段，而各令牌数据量大小不一，数据歪斜就会是一个大问题。所以这里就想方法引入了一个分表水位的概念。

在用户申请保留或删除关系用户数的时候，基于分表序号对以后分表数量进行一个增减的计数，当某个分表中的数据量处于高水位时，就将该分表从分表算法中剔除，从而让该分表不会持续产生新的数据。

比方当设置阈值 1000 万为高水位，因为以上 5 张表都没有达到高水位，则创立令牌时依据令牌 ID 进行 Hash 后取模失去 3，按程序获取表，则以后令牌的分表号为 b2b\_token\_user_3。后续关系数据都从该表中获取。

运行一段时间后，表 b2b\_token\_user\_1 数据量曾经增长到了 1200 万，超过了 1000 万的水位，这时候在创立令牌则将该表移除，在此进行 Hash 后取模失去 1，则以后分到的表就是 b2b\_token\_user\_2。而如果 b2b\_token\_user_1 的水位如果始终不能降下来，则该表后续都不会再参加分表，表中的数据量也不会再减少。

当然有一种可能就是所有表都进入了高水位，为了兜底，这时水位性能就生效，所有表都退出到分表中来。

c. 定期数据归档，升高分表水位

如果表中的数据量只会一直减少，而不会缩小的话，那么早晚所有的表都会达到高水位，这就不能达到动静的成果。下面背景中有提到，令牌创立后是为某一批促销服务，促销终止后，令牌也会失去作用，同时令牌上也有有效期，超过有效期的令牌也会失去作用。所以定期对数据进行归档就能够让那些处于高水位的表把水位缓缓降下来，重新加入到分表中。

而且以后令牌曾经存在了一张 b2b\_token\_user 的表，外面的数据曾经有 1.2 亿，能够将该表作为图上的 0 号表，这样在第一次上线时只有将历史令牌都的分表序号都记为 0 即可，存量数据就不须要再进行迁徙，而该表数据量水位高，也不会参加分表。再搭配定期的数据归档，该表的水位也会缓缓将下来。

d. 监控机制

尽管能够通过定期进行数据归档，能够让表的水位降下来，但随着业务倒退，可能会存在大多数表都进入了高水位，并且都是无效数据的状况。这时候零碎就会像 HashMap 判断容量达到 75% 就主动扩容一样，咱们不可能主动创立表，但当 75% 的表都进入高水位能够告警进去，开发人员监听到告警人工染指，察看是须要调高水位，还是进行表的扩容。

3) 有余

• 水位阈值和扩容监控

目前水位的阈值还是依附人工手动设置，应该设置多大还是比拟理性的，只能设置一个，在告警当前适当调整。不过其实能够在零碎中主动监控接口读写性能的稳定，发现大多数表白到高水位时，接口读写性能都没有显著变动，能够零碎主动调高阈值，从而造成智能阈值。

而接口性能读写呈现显著变动时发现大多数表都达到了阈值，则能够告警提醒该当思考扩容。

4、总结

解决问题素来没有银弹，咱们须要利用手里的技术手段和工具，进行组合、适配，使之适宜咱们当下的业务和场景，没有好或不好，只有适不适宜。