分布式 id 生成策略选型

我们一般对分布式id会有什么诉求，一个好的分布式id生成策略，应该具备哪些要素？其实还是由业务决定的（废话，啥不是由业务决定- -！），但一些通用的诉求大致可以总结为以下几点吧:

1. 全局唯一性：这是最基本的要求。
2. 信息安全：说到id,我们总会不自觉地想到mysql自增id ，这其实很不安全，一看id就能大致猜测出来我们系统每天的业务量，也容易被暴力穷举。
3. 高 QPS : 如果因为 id 生成而成为业务的瓶颈，是不是有点尴尬？
4. 趋势递增：在 MySQL InnoDB 引擎中使用的是聚集索引，用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
5. 高可用 : 如今这年代，高可用是一个永远逃不开的命题，我们应该能在任何时候，都能保证id能被生成出来，局部挂了，不能影响整体服务。
6. id 生成要尽量少的依赖其他组件：依赖的组件越多，理论上越没法保证高可用（如果依赖组建挂了），也可能意味着你的业务方接入代价会比较高，出错了，排错代价也会比较高

目前市场上流行的方案

UUID

• 优点：本地生成，没有高可用风险，性能好
• 缺点：长度过长，存储冗余，且无序不可读，查询效率低

使用MySQL 的 auto_increment

• 优点：数据库生成的 ID 绝对有序，高可用实现方式简单（使用两台数据库分别设置不同步长，生成不重复 ID 的策略来实现高可用）
• 缺点：需要独立部署数据库实例，成本高，有性能瓶颈，上面也说过，绝对有序会造成信息安全问题，我们的业务量可猜测，穷举

利用数据库分段批量生成 ID

在上一个方案的基础上，改为利用 proxy server 批量获取，每次获取一个 segment(step 决定大小) 号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力

• 优点：基本同上一个方案，在上一个方案基础上有巨大的性能提升
• 缺点：也基本上同上一个方案，DB 宕机仍然会造成整个系统不可用。

Redis 生成 ID

Redis 的所有命令操作都是单线程的，本身提供像 incr 和 increby 这样的自增原子命令，所以能保证生成的 ID 肯定是唯一有序的。

• 优点：数字 ID 天然排序，redis性能也比较好。
• 缺点：ID 号码不够随机，仍然有安全问题，类似DB方案，仍然强依赖了三方组件 ，如果redis不可用，会影响服务

Twitter 的雪花算法（snowflake）【推荐】

如果大家百度下雪花算法，介绍一大堆。这里仍然作下简要介绍。雪花算法大致来说是一种以划分命名空间来生成 ID 的一种算法，这种方案把 64-bit 分别划分成多段，分开来标示机器、时间等。snowflake 中的 64-bit 分别表示如下图所示：

image.png

41-bit 的时间可以表示（1L<<41）/(1000L360024*365)=69 年的时间，10-bit 机器可以分别表示 1024 台机器。如果我们对 IDC 划分有需求，还可以将 10-bit 分 5-bit 给 IDC，分 5-bit 给工作机器。这样就可以表示 32 个 IDC，每个 IDC 下可以有 32 台机器，可以根据自身需求定义。12 个自增序列号可以表示 2^12 = 4096 个 ID，理论上 snowflake 方案的 QPS 约为 409.6w/s，这种分配方式可以保证在任何一个 IDC 的任何一台机器在任意毫秒内生成的 ID 都是不同的。

• 优点：基本符合了我们上面提出的各个要求

1. 毫秒数在高位，自增序列在低位，整个 ID 都是趋势递增的。
2. 不依赖数据库等第三方系统，生成 ID 的性能也是非常高的。
3. 可以根据自身业务特性分配 bit 位，非常灵活。

• 缺点：

1. 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
2. 分布式情况下，我们需要确定机器的编号，机器量小的情况下，完全可以手工编号，但是有新机器加入，就需要新编号，带来额外工作量，机器多的情况下，手工和配置都是不小的维护量

总结

再回顾开头对分布式id的需求分析，雪花算法综合来说是一个比较优的方案。代码实现也是百度一下一大把，这里贴一个美团点评的实现。核心实现类https://github.com/Meituan-Dianping/Leaf/blob/master/leaf-core/src/main/java/com/sankuai/inf/leaf/snowflake/SnowflakeIDGenImpl.java
对于上面雪花算法的缺点，比如时钟回拨，机器编号等，一些三方优化过的实现版本，都有相应优化，美团也是。比如

1. 通过弱依赖 zookeeper 解决机器编号问题（启动依赖，得到自己的机器编号后，会缓存。后续 zookeeper 可挂，不影响）

2. 时钟回拨：通过RPC请求获得集群中各节点的机器时间，取平均值，来判断本节点时钟是否正常，从而做时钟回拨的补偿方案。仔细阅读美团 github 开源的代码，貌似并没有发现类似实现，开源的有阉割？应该是吧。下图大致描述了服务启动流程图

   
   image.png