大规模IM用户数据分库分表之二叉树分库分表

绝地灬酷狼 2022-07-16 13:48 163阅读 0赞

# 1、起因 #

互联网发展带来来了数据量巨增，单数据无法解决，导致出现了数据库分库和分表，其主要目的是为突破单节点数据库服务器的 I/O 能力限制，解决数据库扩展性问题。但是分库和分表带来的问题是业务数据的一致性，线性可扩展性，管理的复杂性和容错性带来了很大的挑战。

本文讨论的数据库分表是不改变数据库表结构的水平拆分，不讨论业务的按照纵向拆分。水平拆分数据分库和分表的核心问题是表的ID唯一，然后根据唯一的ID映射到一个物理存储位置，这个映射方案要考虑到满足数据量暴增线性扩展和业务上容易保持一致，本文主要讨论分库分表如何映射的问题。

# 2、分库分表常见方式分析 #

## 2.1最简单方法 ##

1、按照时间分表，这种情况尤其对于历史数据

2、简单分库分表，一张表存数据和库的关系，一张表保存详细信息，举例：用户表分库，可以分为二张表：表1（用户ID，数据库ID），表2（用户ID，用户基本信息）。

这二种情况对于小规模的应用能满足绝大多数的应用。

## 2.2直接映射 ##

**原理：**直接根据主键的ID通过一次映射到一个物理存储位置上。用户访问数据库直接根据映射方法可以访问，但是如果物理节点有变化，访问组件也要变化。

**按区间分表**

比如用户0--1000W第一张表，1000W到2000W第二张表,…….

优点：按照范围容易管理，如果主键ID包括时间信息，一定程度上可以做区间范围统计方便

缺点：不能满足发展初期的数据的均匀分布，小于1000W无法利用物理机器的IO和CPU能力（假设每张表都对立于一个物理db）

**取模映射**

比如：ID%4映射，数据分布到4个节点上，每个节点上可以按照时间来进行重新分表

优点：数据分布比较均匀

缺点：增加节点后，数据的重新分布非常麻烦

## 2.3空间映射 ##

原理：主键ID映射到一个虚拟空间，虚拟空间再和物理存储有一个映射关系。访问数据分为二个阶段，根据ID映射获得对应的虚拟地址，然后根据虚拟地址到物理地址转换，有点像操作系统访问虚拟存储，扩展性增大。

**一致性hash分表**

将ID映射到一个虚拟空间，然后虚拟空间映射到物理节点。一致性hash也可以看做是按区间分表，在0-2^32之间创建几个节点，节点可以看做是表，同时增加虚拟节点（对0-2^32分成多个区间段，然后多个区间段分别指定到几个表中）来保证各表的数据基本均衡

优点：数据的均匀性和可扩展性较直接映射较大改进

缺点：空间映射的方式维护起来困难，数据迁移麻烦

**二叉树分表：**

统一对2取模，left节点库存放可整除的数据，right存放不可被2整除的数据。如果某个节点压力较大则对该节点继续二叉，同时对分库指标加固定前缀或后缀，再hash对2取模。这样的话就可以避免添加表的时候全部数据要从新分配，也节省了维护成本。

优点：树节点可以是物理节点，也可以是表，初期可以可以考虑少量的物理库，每个库上和多表，当物理能力受限后，将对应的表迁移出去

缺点：如果设计不合理，同时存在每个节点都需要分裂的情况下，比较麻烦。另外一开始最好将所有的表都规划出来，否则的话，分裂的时候需要dba耗费较多的时间进行数据迁移。

# 3、二叉树分库分表举例 #

这种方式是现在常见通用的方式，下面详细举例：

**虚拟结构：**8张物理表，按照二叉树的排列如下

[![image][]][image 1]

**初期：**

**初期规划：**2台物理机器，0/4相关的节点在机器A上，5/8相关的数据在物理机器B上，

A机器有0、1、2、4张表，B机器有5、6、7、8表。1/2，3/4,5/6，7/8都为虚拟节点

**映射：**ID通过%2映射到物理机器上，然后剩下的部分%4映射到对应的表上。

比如：(18%4)/2=0,选择物理机为A，(18%4)=2，选择表为2，实际存储的位置为物理机A的表2

**查找过程：**从根节点，查找到物理节点，确定物理机器；查找到表节点为表节点，其中忽略虚拟节点；然后访问物理节点上的表。

[![image][image 2]][image_image 2]

**扩容：**

**物理机B(5/8)节点负载大**，需要扩容，那么增加**物理机C(7/8)，**

**映射过程：**映射过程不变。

**数据迁移：**将表7和表8迁移到物理机器C上，物理机器B上只保留5/6二张表

**查找过程：**举例（查找表7），访问路径1/8---->5/8--->7/8(节点C)，最终在**节点C**上找到表7

[![image][image 3]][image_image 3]

**逻辑库和物理库映射：**

逻辑库：绿色的节点

物理库：红色的节点

映射过程：业务ID--->逻辑库，逻辑库--->物理库

**前置条件：**当前方案数据ID要保证全局唯一

# 4、总结 #

如果数据库切分方案发生变化，那么现网升级也是一个麻烦的事情，如何平滑升级。网络上分库分表文章很多，但都不是特别好，唯一推荐的文章是蘑菇街九如的文章，见：[http://sanwen8.cn/p/3334qPr.html][http_sanwen8.cn_p_3334qPr.html]，有很大的参考价值。其实当前分库分表大体的方法都比较相似。

[image]: /images/20220715/415981811fdc4b31affa211415b47254.png
[image 1]: https://img-blog.csdn.net/20161119190637770
[image 2]: https://img-blog.csdn.net/20161123144646251
[image_image 2]: /images/20220715/fdbcbbbaf5714821b0fa3f15a2d237ec.png
[image 3]: https://img-blog.csdn.net/20161123144646798
[image_image 3]: /images/20220715/51b89456df734eefa6c9d22ae55acfe9.png
[http_sanwen8.cn_p_3334qPr.html]: http://sanwen8.cn/p/3334qPr.html