在业务系统中很多场景下需要生成不重复的ID，比如订单编号、支付流水单号、优惠券编号等都需要使用到。本文将介绍分布式ID的产生原因，以及目前业界常用的四种分布式ID实现方案，并且详细介绍其中两种的实现以及优缺点，希望可以给您带来关于分布式ID的启发。
为什么要用分布式ID
随着业务数据量的增长，存储在数据库中的数据越来越多，当索引占用的空间超出可用内存大小后，就会通过磁盘索引来查找数据，这样就会极大的降低数据查询速度。如何解决这样的问题呢？一般我们首先通过分库分表来解决，分库分表后就无法使用数据库自增ID来作为数据的唯一编号，那么就需要使用分布式ID来做唯一编号了。
分布式ID实现方案
目前，关于分布式ID，业界主要有以下四种实现方案：
UUID：使用JDK的UUID#randomUUID()生成的ID；Redis的原子自增：使用Jedis#incr(Stringkey)生成的ID；Snowflake算法：以时间戳机器号和毫秒内并发组成的64位Long型ID；分段步长：按照步长从数据库读取一段可用范围的ID；我们总结一下这几种方案的特点：
前面两种实现方案的用法以及实现大家日常了解较多，就不在此赘述...本文我们会详细介绍Snowflake算法以及分段步长方案。
Snowflake算法可以做到分配好机器号后就可以使用，不依赖任何第三方服务实现本地ID生成，依赖的第三方服务越少可用性越高，那么我们先来介绍一下Snowflake算法。
Snowflake算法
长整型数字（即Long型数字）的十进制范围是-2^64到2^64-1。
Snowflake使用的是无符号长整型数字，即从左到右一共64位二进制组成，但其第一位是不使用的。所以，在Snowflake中使用的是63bit的长整型无符号数字，它们由时间戳、机器号、毫秒内并发序列号三个部分组成：
时间戳位：当前毫秒时间戳与新纪元时间戳的差值（所谓新纪元时间戳就是应用开始使用Snowflake的时间。如果不设置新纪元时间，时间戳默认是从年开始计算的，设置了新纪元时间可以延长Snowflake的可用时间）。41位2进制转为十进制是2^41，除以（天*24小时*秒*毫秒），约等于69年，所以最多可以使用69年；机器号：10位2进制转为十进制是2^10，即，也就是说最多可以支持有个机器节点；毫秒内并发序列号：12位2进制转为十进制是2^12，即，也就是说一毫秒内在一个机器节点上并发的获取ID，最多可以支持个并发；下面我们来看一下各个分段的使用情况：
那么Snowflake生成的ID长什么样子呢？下面我们来举几个例子（假设我们的时间戳新纪元是-12-:00:00）：
Snowflake可以使用三种不同的部署方式来部署，集成分布式部署方式、中心集群式部署方式、直连集群式部署方式。下面我们来分别介绍一下这几种部署方式。
Snowflake集成分布式部署方式
当使用ID的应用节点比较少时，比如个节点以内，适合使用集成分布式部署方式。每个应用节点在启动的时候决定了机器号后，运行时不依赖任何第三方服务，在本地使用时间戳、机器号、以及毫秒内并发序列号生成ID。
下图展示的是应用服务器通过引入jar包的方式实现获取分布式ID的过程。每一个使用分布式ID的应用服务器节点都会分配一个拓扑网络内唯一的机器号。这个机器号的管理存放在MySQL或者ZooKeeper上。
当拓扑网络内使用分布式ID的机器节点很多，例如超过个机器节点时，使用集成部署的分布式ID就不合适了，因为机器号位一共是10位，即最多支持个机器号。当机器节点超过个机器节点时，可以使用下面要介绍的中心集群式部署方式。
Snowflake中心集群式部署方式
中心集群式部署需要新增用来做请求转发的ID网关，比如使用nginx反向代理（即下图中的IDRESTAPIGateway）。
使用ID网关组网后，应用服务器通过HTTP或RPC请求ID网关获取分布式ID。这样相比于上面的集成分布式部署方式，就可以支撑更多的应用节点使用分布式ID了。
如图所示，机器号的分配只是分配给下图中的IDGeneratornode节点，应用节点是不需要分配机器号的。
使用中心集群式部署方式需要引入新的nginx反向代理做网关，增加了系统的复杂性，降低了服务的可用性。那么我们下面再介绍一种不需要引入nginx又可以支持超过个应用节点的直连集群部署方式。
Snowflake直连集群式部署方式
相比于中心集群部署方式，直连集群部署方式可以去掉中间的ID网关，提高服务的可用性。
在使用ID网关的时候，我们需要把IDgeneratornode的服务地址配置在ID网关中。而在使用直连集群式部署方式时，IDgeneratornode的服务地址可以配置在应用服务器本地配置文件中，或者配置在配置中心。应用服务器获取到服务地址列表后，需要实现服务路由，直连ID生成器获取ID。
Snowflake算法存在的问题
Snowflake算法是强依赖时间戳的算法，如果一旦发生时钟回拨就会产生ID重复的问题。那么时钟回拨是怎么产生的，我们又需要怎么去解决这个问题呢？
NTP（NetworkTimeProtocol）服务自动校准可能导致时钟回拨。我们身边的每一台计算机都有自己本地的时钟，这个时钟是根据CPU的晶振脉冲计算得来的，然而随着运行时间的推移，这个时间和世界时间的偏差会越来越大，那么NTP就是用来做时钟校准的服务。
一般情况下发生时钟回拨的概率也非常小，因为一旦出现本地时间相对于世界时间需要校准，但时钟偏差值小于STEP阈值（默认毫秒）时，计算机会选择以SLEW的方式进行同步，即以0.5毫秒/秒的速度差调整时钟速度，保证本地时钟是一直连续向前的，不产生时钟回拨，直到本地时钟和世界时钟对齐。
然而如果本地时钟和世界时钟相差大于STEP阈值时，就会发生时钟回拨。这个STEP阈值是可以修改的，但是修改的越大，在SLEW校准的时候需要花费的校准时间就越长，例如STEP阈值设置为10分钟，即本地时钟与世界时钟偏差在10分钟以内时都会以SLEW的方式进行校准，这样最多会需要14天才会完成校准。
为了避免时钟回拨导致重复ID的问题，可以使用毫秒的STEP阈值，同时在获取SnowflakeID的时候与上一次的时间戳相比，判断时钟回拨是否在1秒钟以内，如果在1秒钟以内，那么等待1秒钟，否则服务不可用，这样可以解决时钟回拨1秒钟的问题。
分段步长方案
Snowflake由于是将时间戳作为长整形的高位，所以导致生成的最小数字也非常大。比如超过时间新纪元1秒钟，机器号为1，毫秒并发序列为1时，生成的ID就已经到了。那么有没有一种方法能够实现在初始状态生成数字较小的ID呢？答案是肯定的，下面来介绍一下分段步长ID方案。
使用分段步长来生成ID就是将步长和当前最大ID存在数据库中，每次获取ID时更新数据库中的ID最大值增加步长。
数据库核心表结构如下所示：
在获取ID时，使用开启事务，利用行锁保证读取到当前更新的最大ID值：
分段步长ID生成方案的优缺点：
优点：ID生成不依赖时间戳，ID生成初始值可以从0开始逐渐增加；缺点：当服务重启时需要将最大ID值增加步长，频繁重启的话就会浪费掉很多分段。针对上述两种实现方案的优化
上文介绍了Snowflake算法以及分段步长方案，他们各有优缺点，针对他们各自的情况我们在本文也给出相应的优化方案。
ID缓冲环
为了提高SnowflakeID的并发性能和可用性，可以使用ID缓冲环（即IDBufferRing）。提高并发性提现在通过使用缓冲环能够充分利用毫秒时间戳，提高可用性提现在可以相对缓解由时钟回拨导致的服务不可用。缓冲环是通过定长数组加游标哈希实现的，相比于链表会不需要频繁的内存分配。
在ID缓冲环初始化的时候会请求ID生成器将ID缓冲环填满，当业务需要获取ID时，从缓冲环的头部依次获取ID。当ID缓冲环中剩余的ID数量少于设定的阈值百分比时，比如剩余ID数量少于整个ID缓冲环的30%时，触发异步ID填充加载。异步ID填充加载会将新生成的ID追加到ID缓冲环的队列末尾，然后按照哈希算法映射到ID缓冲环上。另外有一个单独的定时器异步线程来定时填充ID缓冲环。
下面的动画展示了ID缓冲环的三个阶段：ID初始化加载、ID消费、ID消费后填充：
BufferRingInitializeload，ID缓冲环初始化加载：从IDgenerator获取到ID填充到ID缓冲环，直到ID缓冲环被填满；BufferRingconsume，ID缓冲环消费：业务应用从ID缓冲环获取ID；Asyncreload，异步加载填充ID缓冲环：定时器线程负责异步的从IDgenerator获取ID添加到ID缓冲队列，同时按照哈希算法映射到ID缓冲环上，当ID缓冲环被填满时，异步加载填充结束；
下面的流程图展示了ID缓冲环的运行的整个生命周期，其中：
IDConsumerServer：表示使用分布式ID的业务系统；IDBufferRing：ID缓冲环；IDGenerator：ID生成器；IDBufferRingAsyncLoadThread：异步加载ID到缓冲环的线程；Timer：负责定时向异步加载线程添加任务来装载ID；ID消费流程：即上面提到的BufferRingconsume；整体流程：客户端业务请求到应用服务器，应用服务器从ID缓冲环获取ID，如果ID缓冲环内空了那么抛出服务不可用；如果ID缓冲环内存有ID那么就消费一个ID。同时在消费ID缓冲环中的ID时，如果发现ID缓冲环中存留的ID数量少于整个ID缓冲环容量的30%时触发异步加载填充ID缓冲环。
ID双桶Buffer
在使用分段步长ID时，如果该分段的ID用完了，需要更新数据库分段最大值再继续提供ID生成服务，为了减少数据库更新查询可能带来的延时对ID服务的性能影响，可以使用双桶缓存方案来提高ID生成服务的可用性。
其主要原理：设计两个缓存桶：currentBufferBucket和nextBufferBucket，每个桶都存放一个步长这么多的ID，如果当前缓存桶的ID用完了，那么就将下一个缓存桶设置为当前缓存桶。
下面的动画展示了双桶缓存初始化、异步加载预备桶和将预备桶切换成当前桶的全过程：
Currentbucketinitialload：初始化当前的缓存桶，即更新max=max+step，然后获取更新后的max值，比如步长是，更新后的max值是，那么桶的高度就是步长即，桶min=max-step+1=1，max=；Currentbucketremainingidcountdownto20%，Nextbucketstarttoload。当前缓存桶的ID剩余不足20%的时候可以加载下一个缓存桶，即更新max=max+step，后获取更新后的max值，此时更新后的max值是0，min=max-step+1=，max=0；Currentbucketisdrained，Switchcurrentbuckettothenextbucket，如果当前桶的ID全部用完了，那么就将下一个ID缓存桶设置为当前桶；
下面是双桶Buffer的流程图：
总结
本文主要介绍了分布式ID的实现方案，并详细介绍了其中Snowflake方案和分段步长方案，以及针对这两种方案的优化方案。我们再简单总结一下两个方案：
在高并发场景下生成大量的分布式ID，适合使用Snowflake算法方案，毫秒内并发序列为2^12=，单机QPS支持高达4百万，但是需要对ID生成器的机器号进行管理；使用分段步长方式生成ID就可以免去对机器号的管理，但是需要合理的设置步长，如果步长太短满足不了并发需求，如果步长太长又会造成分段的过渡浪费；以上就是本文的全部内容，如果有更多关于分布式ID的技术也欢迎留言与我们交流。
作者介绍
古德，网易云信资深JAVA开发工程师。现在负责网易会议账户体系、互动直播等模块的设计与研发。对微服务、分布式事务等中间件技术方面有一定的经验。热爱技术喜欢Coding，善于面向对象设计编程、领域驱动设计与代码优化重构。