概述

在实际工作中，在关系数据库（MysqL、Postgresql）的单表数据量上亿后，往往会出现查询和分析变慢甚至无法执行统计分析的情况。这时就需要将大表拆分为多个小表，将小表分布在多个数据库上，形成一个数据库集群。这样的话，一条 sql 统计语句就可以在多台服务器上并发执行，然后将执行结果汇总，实现关系数据库的大数据量分析

数据库三范式

范式是具有最小冗余的表结构，三范式的概念如下所述

第一范式：如果每列都是不可再分的最小数据单元，则满足第一范式，第一范式的目标是确保每列的原子性。例如 Address 列存储地址信息，值为“中国北京市”，违背了第一范式列不可再分的原则，要满足第一范式，就需要将 Address 列拆分为 Country 列和 Ciy 列，分别存储“中国”和“北京市”

第二范式：第二范式在第一范式的基础上，规定表中的非主键列不存在对主键的部分依赖，即第二范式要求每个表都只描述一件事情。例如 Orders 表有“订单编号”，“产品编号”，“订单日期”，“产品价格”列，既包含了订单信息，也包含了产品信息，需要拆分成订单表和产品表

第三范式：满足第一范式和第二范式，并且表中的列不存在对非主键列的业务依赖。例如 Orders 表有“订单编号”，“顾客编号”，“订单日期”，“顾客姓名”列，除了主键“订单编号”，“顾客姓名”依赖于“顾客编号”，因此需要将该“顾客编号”移去

按照范围分表

按照范围分表指在某个字段上按照范围对数据进行拆分，例如将数据按照用户 ID 的范围 0-10w、10w-20w、20w-30w 分别划分到不同的数据库中。采用这种方法扩容简单，按照规划提前建好库和表即可，缺点是大部分读和写操作都会访问新的数据，造成新库压力过大

哈希取模

哈希取模指在某个字段上计算该字段的哈希值，按照其哈希值对数据进行拆分。哈希取模的具体做法是首先对 N 台服务器从 0 到 N-1 进行编号，按照自定义的哈希算法，对每个请求的哈希值都按 N 取模，得到的余数即该数据所在的服务器编号。采用该方法的好处是数据分布均衡，数据库的整体压力小，缺点是扩缩容麻烦，在扩缩容过程中需要对所有数据重新进行哈希分配和迁移

一致性哈希算法

一致性哈希算法取代传统的哈希取模，避免服务器集群数量发生变化导致哈希值失效，以致整个集群数据都需要重新分配的问题

一致性哈希算法将整个哈希空间虚拟成一个 0-2^(32-1) 的哈希环，将服务器节点和数据分别映射到哈希环上，并将对象映射到服务器节点，来实现数据在各台服务器上的哈希分
布，具体过程如下：

构建哈希环：将整个哈希空间组成一个 0-2^(32-1) 的虚拟圆环，即哈希环，如图所示

将服务器节点映射到哈希环：使用哈希函数将服务器映射到虚拟的哈希环上，一般可以使用服务器节点机器的 IP 地址或者机器名作为哈希函数的计算值。假设有 3 个服务器节点：node-0、node-1、node-2，通过哈希函数计算出服务器 IP 地址的哈希值，并将其分布在哈希环上

将数据映射到哈希环：使用相同的哈希函数计算需要存储的数据的哈希值，并将数据映射到哈希环上。假设有 4 个对象：o1、o2、o3、o4，通过哈希函数计算出对象的哈希值，并将其分布在哈希环上

将对象映射到服务器节点：找到对象的哈希值在哈希环上的位置，从该位置开始沿哈希环顺时针寻找，遇到的第 1 台服务器就是该对象的存储节点服务器，将该对象映射
到该服务器上。如图所示，对象 o1 被映射到 cs1 上，对象 o2 被映射到 cs2 上，对象 o3 被映射到 cs1 上，对象 o4 被映射到 cs3 上

传统的哈希取模，当服务器有变动（增加节点或移除节点）时，整个系统的哈希值都会失效（因为服务器的数量发生了变化，即被除数发生了变化），从而需要重新计算哈希值，并进行哈希映射和数据分布。而一致性哈希在服务器发生变动时，由于对象的数据分布只与顺时针方向的下一台服务器相关，因此只会影响所变化节点的下一个节点的数据分布

移除节点：假设某台服务器宕机，受影响的对象仅仅是原本映射到该服务器的对象，根据一致性哈希顺时针数据映射的原则，只需将原本映射到该服务器上的对象重新映射到下一个正常的服务器即可。例如 cs1 宕机，只需将 o1 重新映射到 cs3 即可

添加节点：添加节点，受影响的数据仅是新节点到沿逆时针方向的第一个节点之间的对象，将这些对象重新映射到新加入的节点即可。例如在 cs1 和 cs2 之间加入新节点 cs3，cs3 位于 o1 和 o3 之间，只需要将 o3 重新映射到 cs3 即可

一致性哈希算法不能保证数据的绝对平衡，在集群对象数据较少的情况下，对象并不能被均匀映射到各个节点上。为了解决数据分布不均的问题，一致性哈希算法引入“虚拟节点”的概念。虚拟节点是实际节点在哈希空间中的副本，一个实际节点对应若干虚拟节点，对应的个数也被称为副本个数，虚拟节点在哈希空间中以哈希值排列。在引入虚拟节点后，映射关系就从对象到节点转换为从对象到虚拟节点