前言

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、高可用：

5个 9， 99.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的标准型式包含32个16进位数字。那么UUID以连字号分为五段，形式为8-4-4-4-12的 32个字符，加上“-”一共是 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：

2.2.1、生成原理

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

2.2.2、问题总结

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

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

问题2：雪花算法的 id 是什么类型的？

答案：java 中 64bit 刚好就是整数 long 类型，所以 SnowFlake 雪花算法中的 id 是 long 类型存储

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之上挂 N 个 Server ，每个 Server 启动时，都会去 DB 拿固定长度的ID List。这样就做到了完全基于分布式的架构，同时因为ID是由内存分发，所以也可以做到很高效。

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

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

⬤ 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、Leaf 双 Buffer 优化

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

工作流程：

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 中间件 Zebra 加 MHA 做的主从切换。未来追求完全的强一致，会考虑切换到 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。

3.2.1、workerID 的分配

启动步骤如下：

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

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

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

3.2.2、避免时钟回拨

1、服务启动时

⬤ 在服务启动时，首先检查自己是否写过 zookeeper leaf_forever 节点；

⬤ 如果写过，则用自身系统时间与 leaf_forever/${self} 节点记录时间做比较，若小于则认为机器时间发生了大步长回拨，服务启动失败并告警；

⬤ 如果没有写过，直接创建持久节点 leaf_forever/${self}，并写入自身系统时间；

⬤ 然后取 leaf_temporary 下的所有临时节点(所有运行中的 Leaf-snowflake 节点)的服务 IP：Port，然后通过 RPC 请求得到所有节点的系统时间，计算 sum(time)/nodeSize；

⬤ 如果若 abs ( 系统时间 - sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点 leaf_temporary/${self} 维持租约；否则认为本机系统时间发生大步长偏移，启动失败并报警；

⬤ 每隔一段时间(3s)上报自身系统时间写入 leaf_forever/${self}。

2）服务运行时

⬤ 会检查时钟回拨时间是否小于 5ms，若时钟回拨时间小于等于 5ms，等待时钟回拨时间后，重新产生新的 ID；若时钟回拨时间大于 5ms，直接抛异常给到业务侧。