前言

博客：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 生成；而依赖的第三方服务越少可用性越高；

位	解释	详情
1`bit`	0，这个是无意义的，二进制中最高位为1的都是负数，但是我们生成的 `id`一般都使用整数，所以这个最高位固定是0	就是固定的0
41`bit`	是时间戳，即为当前的毫秒数	⬤ 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年
10`bit`	用来记录工作机器`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 是什么类型的？

答案：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，直接抛异常给到业务侧。

4、常见的公司订单号生成规则

ContactAuthor

HealeJean的梦想博客

一个高级软件开发工程师的成长之路

分布式之_1_分布式Id生成

1、分布式 `Id` 问答

1.1、有了数据库自增Id，还不够吗？

1.2、`id`生成需要注意什么

1.2.1、全局唯一性

1.2.2、趋势递增

1.2.3、单调递增

1.2.4、信息安全：

1.2.5、含时间戳

1.3、`id` 生成的性能考核

1.3.1、高可用：

1.3.2、低延迟

1.2.3、高 `QPS`：

2、分布式 `Id` 实现方案

2.1、`UUID`

2.1.1、生成原理

2.1.2、优点：

2.1.3、缺点：

2.2、`SnowFlake` 方案

2.2.1、生成原理

2.2.2、问题总结

2.2.3、优点

2.2.4、缺点

3、美团 `Leaf`

3.1、`Segment` 模式

3.2.1、`Segment` 模式发展

3.1.1.1、`Leaf` 诞生

2.3.1.2、`Leaf` 双 `Buffer` 优化

2.3.1.3、`Leaf` 动态调整 `Step`

2.3.1.4、`MySQL` 高可用

3.2.2、问题总结

3.2.2、优点

3.2.3、缺点

3.2、`Leaf-snowflake`

3.2.1、`workerID` 的分配

3.2.2、避免时钟回拨

4、常见的公司订单号生成规则

1、分布式 Id 问答

1.1、有了数据库自增Id，还不够吗？

1.2、id生成需要注意什么

1.2.1、全局唯一性

1.2.2、趋势递增

1.2.3、单调递增

1.2.4、信息安全：

1.2.5、含时间戳

1.3、id 生成的性能考核

1.3.1、高可用：

1.3.2、低延迟

1.2.3、高 QPS：

2、分布式 Id 实现方案

2.1、UUID

2.1.1、生成原理

2.1.2、优点：

2.1.3、缺点：

2.2、SnowFlake 方案

2.2.1、生成原理

2.2.2、问题总结

2.2.3、优点

2.2.4、缺点

3、美团 Leaf

3.1、Segment 模式

3.2.1、Segment 模式 发展

3.1.1.1、Leaf 诞生

2.3.1.2、Leaf 双 Buffer 优化

2.3.1.3、Leaf 动态调整 Step

2.3.1.4、MySQL 高可用

3.2.2、问题总结

3.2.2、优点

3.2.3、缺点

3.2、Leaf-snowflake

3.2.1、workerID 的分配

3.2.2、避免时钟回拨

4、常见的公司订单号生成规则

1、分布式 `Id` 问答

1.2、`id`生成需要注意什么

1.3、`id` 生成的性能考核

1.2.3、高 `QPS`：

2、分布式 `Id` 实现方案

2.1、`UUID`

2.2、`SnowFlake` 方案

3、美团 `Leaf`

3.1、`Segment` 模式

3.2.1、`Segment` 模式发展

3.1.1.1、`Leaf` 诞生

2.3.1.2、`Leaf` 双 `Buffer` 优化

2.3.1.3、`Leaf` 动态调整 `Step`

2.3.1.4、`MySQL` 高可用

3.2、`Leaf-snowflake`

3.2.1、`workerID` 的分配