前言

Github:https://github.com/HealerJean

博客:http://blog.healerjean.com

1、分布式 Id 问答

1.1、有了数据库自增Id,还不够吗?

⬤ 随着业务数据量的增长,存储在数据库中的数据越来越多,当索引占用的空间超出可用内存大小后,就会通过磁盘索引来查找数据,这样就会极大的降低数据查询速度;

⬤ 如何解决这样的问题呢? 一般我们首先通过分库分表来解决:分库分表后就无法使用数据库自增 ID 来作为数据的唯一编号,那么就需要使用分布式 ID 来做唯一编号了;

1.2、id生成需要注意什么

1.2.1、全局唯一性

不能出现重复的 ID号,既然是唯一标识,这是最基本的要求。

1.2.2、趋势递增

MySQL InnoDB 引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能(我理解这里主要还是说的分库分表后的主键)

1.2.3、单调递增

保证下一个 ID 一定大于上一个 ID,例如事务版本号、IM 增量消息、排序等特殊需求。

1.2.4、信息安全:

如果ID是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要ID无规则、不规则

1.2.5、含时间戳

这样就能在开发中快速了解分布式id的生成时间

1.3、id 生成的性能考核

1.3.1、高可用:

5999.999% 。发一个获取分布式ID的请求,服务器就要保证99.999%的情况下给我创建一个唯一分布式ID

1.3.2、低延迟

发一个获取分布式 ID 的请求,服务器就要快,极速

1.2.3、高QPS

假如并发一口气创建分布式ID请求同时杀过来,服务器要顶得住且一下子成功创建10万

2、分布式 Id 实现方案

2.1、UUID

public static void main(String[] args) { 
       String uuid = UUID.randomUUID().toString().replaceAll("-","");
       System.out.println(uuid);
 }

2.1.1、生成原理

通用唯一识别码(Universally Unique Identifier,缩写:UUID)是用于计算机体系中以识别信息数目的一个128位标识符,也就是可以通过16个字节来表示。

UUID可以根据标准方法生成,不依赖中央机构的注册和分配,UUID具有唯一性,这与其他大多数编号方案不同。重复UUID码概率接近零,可以忽略不计。

问题1:UUID 有显示几个字符?

答案:显示在由连字符分隔 ‘-‘ 的五个组中,以连字号分为五段,形式为8-4-4-4-12,总共 36 个字符(32 个字母数字字符和 4 个连字符)

123e4567-e89b-12d3-a456-426655440000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

问题2:UUID占几个字节

答案:UUID的标准型式包含3216进位数字。那么UUID以连字号分为五段,形式为8-4-4-4-1232个字符,加上“-”一共是 36 位,所以咱们可以先取出 uuid,再把 - 去掉就是 16 个字节(一个十六进制数占4位,也就是半个字节,,那么UUID就是16个字节)

2.1.2、优点:

1、生成足够简单

2、ID 唯一(几乎不会产生重复id),但是理论上还是会有重复的

3、本地生成无网络消耗,基本不会有性能问题

2.1.3、缺点:

1、对 MySQL索引不利:无序的字符串,不具备趋势自增特性,如果作为数据库主键,在InnoDB引擎下,UUID的无序性可能会引起数据位置频繁变动,严重影响性能

2、不易于存储:UUID 太长,16 字节128位,通常以36长度的字符串表示,很多场景不适用。

3、信息不安全:基于MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置

2.2、SnowFlake 方案

Twitter 利用 zookeeper 实现了一个全局ID生成的服务 Snowflake

image-20210824212608302

2.2.1、生成原理

Snowflake 算法可以做到分配好机器号后就可以使用,不依赖任何第三方服务实现本地 ID 生成; 而依赖的第三方服务越少可用性越高;

解释 详情
1bit 0,这个是无意义的,二进制中最高位为1的都是负数,但是我们生成的 id一般都使用整数,所以这个最高位固定是0 就是固定的0
41bit 是时间戳,即为当前的毫秒数 ⬤ 41位可以表示$2^{41}-1$个数字,
⬤ 如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至 $2{41}-1$,减1是因为可表示的数值范围是从0开始算的,而不是1,也就是说41位可以表示$2{41}-1$个毫秒的值,转化成单位年则是$(2^{41}-1) (1000 * 60 * 60 * 24 * 365) = 69$年
⬤ 说明雪花算法可表示的范围为69年(从1970年开始),说明雪花算法能用到2039年
10bit 用来记录工作机器id ⬤ 可以部署在$2^{10} = 1024$个节点,包括 5位datacenterId 和 5位workerId,5位(bit)可以表示的最大正整数是$2^{5}-1 = 31$,即可以用0、1、2、3、….31这32个数字,来表示不同的datecenterId或workerId
⬤ 10 bit 里 5 个 bit` 代表机房 id,5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房(32 个机房),每个机房里可以代表 2 ^ 5 个机器(32 台机器),也可以根据自己公司的实际情况确定
12 bit 某个机房某台机器上这一毫秒内同时生成的 id 的序号 ⬤ 12位(bit)可以表示的最大正整数是$2^{12}-1 = 4095$,即可以用0、1、2、3、….4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号

2.2.2、问题总结

问题1:⬤SnowFlake 算法在同一毫秒内最多可以生成多少个全局唯一ID呢?

答案:做一个简单的乘法:同一毫秒的ID数量 = 1024 X 4096 = 4194304,这个数字在绝大多数并发场景下都是够用的

问题2:雪花算法的 id 是什么类型的?

答案:java64bit 刚好就是整数 long 类型,所以 SnowFlake 雪花算法中的 idlong 类型存储

2.2.3、优点

1、生成 ID 时不依赖于 DB 等第三方服务,完全在内存生成,高性能高可用。

2、ID 呈趋势递增,后续插入索引树的时候性能较好。

2.2.4、缺点

1、依赖于系统时钟的一致性。如果某台机器的系统时钟回拨,有可能造成ID冲突,或者ID乱序。

2、单机上是递增的,但是如果是分布式环境,每台机器的时钟不可能完全同步,有时候也会出现不是完全递增的情况,但是一般意义上是无所谓的,一般分布式Id要求趋势递增,并不是严格要求递增。90%的需求要求趋势递增

3、美团Leaf

https://tech.meituan.com/2019/03/07/open-source-project-leaf.html

⬤ 号段模式:低位趋势增长,较少的 ID 号段浪费,能够容忍MySQL的短时间不可用。

Snowflake 模式:完全分布式,ID 有语义。

1、全局唯一,绝对不会出现重复的ID,且ID整体趋势递增。

2、高可用,服务完全基于分布式架构,即使MySQL宕机,也能容忍一 段时间的数据库不可用。

3、高并发低延时,在CentOS 4C8G的虚拟机上,远程调用QPS可达5W+,TP99在1ms内。

4、接入简单,直接通过公司RPC 服务或者 HTTP 调用即可接入。

3.1、Segment 模式

3.2.1、Segment 模式 发展

3.1.1.1、Leaf 诞生

Leaf 第一个版本采用了预分发的方式生成 ID,即可以在DB之上挂 NServer ,每个 Server 启动时,都会去 DB 拿固定长度的ID List。这样就做到了完全基于分布式的架构,同时因为ID是由内存分发,所以也可以做到很高效。

接下来是数据持久化问题,Leaf 每次去 DB 拿固定长度的 ID List,然后把最大的ID持久化下来,也就是并非每个ID都做持久化,仅仅持久化一批ID中最大的那一个。这个方式有点像游戏里的定期存档功能,只不过存档的是未来某个时间下发给用户的 ID,这样极大地减轻了DB持久化的压力。

整个服务的具体处理过程如下:

image-20220126135250411

⬤ Leaf Server 1:从DB加载号段[1,1000]。

⬤ Leaf Server 2:从DB加载号段[1001,2000]。

⬤ Leaf Server 3:从DB加载号段[2001,3000]。

用户通过Round-robin的方式调用Leaf Server的各个服务,所以某一个Client获取到的ID序列可能是:1,1001,2001,2,1002,2002……也可能是:1,2,1001,2001,2002,2003,3,4……当某个Leaf Server号段 用完之后,下一次请求就会从DB中加载新的号段,这样保证了每次加载的号段是递增的。

Leaf数据库中的号段表格式如下:

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

Leaf Server加载号段的SQL语句如下:

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

整体上,V1版本实现比较简单,主要是为了尽快解决业务层 DB 压力的问题,而快速迭代出的一个版本。因而在生产环境中,也发现了些问题。比如:

1、在更新DB的时候会出现耗时尖刺,系统最大耗时取决于更新DB号段的时间

2、当更新DB号段的时候,如果DB宕机或者发生主从切换,会导致一段时间的服务不可用

2.3.1.2、LeafBuffer 优化

为了解决这上面的两个问题,Leaf 采用了异步更新的策略,同时通过双 Buffer的方式,保证无论何时 DB出现问题,都能有一个Buffer的号段可以正常对外提供服务,只要 DB 在一个 Buffer 的下发的周期内恢复,就不会影响整个Leaf的可用性。

image-20220126135758946

工作流程:

1、如设置 step 为 1000;

2、当发号期已经分发到100的时候(即取了步长step的10%),就会触发一个异步操作去初始化下一个号段;

3、当1~1000用尽并且分配到1100的时候,又会触发异步操作去初始化又1个号段(2001~3000),以此类推;

通过这种方案设计,每次获取唯一ID都只需要操作内存即可。至于对数据库的操作,完全异步完成。

这个版本代码在线上稳定运行了半年左右,Leaf又遇到了新的问题

1、号段长度始终是固定的,假如 Leaf 本来能在 DB 不可用的情况下,维持10分钟正常工作,那么如果流量增加 10倍就只能维持1分钟正常工作了。

2、号段长度设置的过长,导致缓存中的号段迟迟消耗不完,进而导致更新 DB 的新号段与前一次下发的号段 ID跨度过大。

2.3.1.3、Leaf 动态调整 Step

假设服务QPS为Q,号段长度为L,号段更新周期为T,那么Q * T = L。最开始 L长度是固定的,导致随着 Q的增长,T 会越来越小。但是 Leaf 本质的需求是希望T是固定的。那么如果 L可以和 Q 正相关的话,T 就可以趋近一个定值了。所以Leaf每次更新号段的时候,根据上一次更新号段的周期 T 和号段长度 step,来决定下一次的号段长度nextStep

⬤ T < 15min,nextStep = step * 2,

⬤ 15min < T < 30min,nextStep = step

⬤ T > 30min,nextStep = step / 2

至此,满足了号段消耗稳定趋于某个时间区间的需求。当然,面对瞬时流量几十、几百倍的暴增,该种方案仍不能满足可以容忍数据库在一段时间不可用、系统仍能稳定运行的需求。因为本质上来讲,Leaf 虽然在 DB 层做了些容错方案,但是号段方式的 ID下发,最终还是需要强依赖DB。

2.3.1.4、MySQL 高可用

MySQL这一层,Leaf 目前采取了半同步的方式同步数据,通过公司 DB 中间件 ZebraMHA 做的主从切换。未来追求完全的强一致,会考虑切换到 MySQL Group Replication

现阶段由于公司数据库强一致的特性还在演进中,Leaf 采用了一个临时方案来保证机房断网场景下的数据一致性:

1、多机房部署数据库,每个机房一个实例,保证都是跨机房同步数据。高可用

2、半同步超时时间设置到无限大,防止半同步方式退化为异步复制,防止数据不一致

3.2.2、问题总结

问题1:这种方案是如何避免重启后分配重复的ID呢?

答案:我们假设已经分配到 1122,这个1122 又没有持久化到任何一个地方,数据库中只保存了(max_id = 2001, step = 1000),如果这时候 leaf 宕机。leaf 的做法是在第一次获取唯一 ID 的时候,会首先更新数据库跳到下一个号段(max_id = 3001, step = 1000),那么这时候获取的唯一ID 就是 2001,至于1123~2000之前的ID全部被抛弃,不会被分配了

问题2:Segment 模式有时钟回拨问题吗?

答案:很明显没有,因为通过这种模式获取的 ID没有任何时间属性,所以不存在时钟回拨问题。

3.2.2、优点

1、非常简单,利用现有数据库系统的功能实现,成本小,有DBA专业维护。

2、ID 号单调自增,可以实现一些对ID有特殊要求的业务。

3.2.3、缺点

1、强依赖 DB,当 DB 异常时整个系统不可用,属于致命问题。配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号

2、ID 发号性能瓶颈限制在单台 MySQL的读写性能

3、ID 不够随机,能够泄露发号数量的信息,不安全,一般不会严格要求。

3.2、Leaf-snowflake

该方案完全沿用 snowflake 方案设计。对于 workerID 的分配,当服务器集群数量较小的情况下,完全可以手动配置。服务规模较大时,动手配置成本太高,所以使用 Zookeeper 持久顺序节点的特性自动对 snowflake 节点配置

在这里,Leaf 提供了 Java 版本的实现,同时对 Zookeeper生成机器号做了弱依赖处理,即使 Zookeeper 有问题,也不会影响服务。Leaf 在第一次从 Zookeeper 拿取 workerID 后,会在本机文件系统上缓存一个 workerID文件。即使ZooKeeper出现问题,同时恰好机器也在重启,也能保证服务的正常运行。这样做到了对第三方组件的弱依赖,一定程度上提高了SLA

启动步骤如下:

1、启动 Leaf-snowflake 服务,连接 Zookeeper,在 leaf_forever 父节点下检查自己是否已经注册过。

2、如果有注册过直接取回自己的 workerID,启动服务。

3、如果没有注册过,就在该父节点下面创建一个持久顺序节点,创建成功后取回顺序号当做自己的 workerID 号。

ContactAuthor