theme: smartblue

大家好啊，我是码财同行。

今天来聊一个老生常谈的问题：唯一ID生成。不过，探讨的思路可能和其他文章不太一样，我们看看唯一ID生成和猪肉是什么关系，目的还是想借助生活中的现象，更深入理解事情的本质。

这是唯一ID生成的第一篇文章，主要谈谈经典的雪花算法。话不多说，我们开始吧。

雪花算法 snowflake

雪花（snowflake）算法是最为知名的分布式唯一ID生成算法，它是twitter公司（被马斯克收购后改名X）用的唯一ID生成算法，天然适合分布式环境。

取名 “雪花”，意思是没有两片完全相同的雪花，也就是具有生成的 id 具有唯一性的意思。

这个唯一 ID 是一个 64位的数字ID。量级上，64位数字基本是完全够用的；用数字表示，相比字符串形式，也有足够高的效率来传输和存储。

来看一下这个64位数字id是怎么组成的：

主要就是四个部分：

• 正负符号位
• 时间
• 机器id
• 自增序列号

乍一看，似乎有点不明所以，为什么这么设计？

设计思路推演

通过一番思考，我们可以用逻辑一步步推演出这样的思路：

1. 雪花算法是分布式的唯一id算法，但是解决方案总是从简单到复杂。咱们首先还是 从解决单应用的唯一ID问题开始。通常我们在写程序的时候，最简单的 id 生成就是用一个变量来自增即可，这就是 自增序列号 部分，是最直观最容易想到的：每次需要生成id的时候，加1之后返回。

1. 有自增序列号肯定是不够的，毕竟这个生成的 id 只是存在于内存中的。试想，如果程序宕机了呢？或者就是程序重启了，内存中这个用于自增的变量丢失，那唯一ID就回退到开始状态了，结果就糟糕了：程序重新生成的ID可能会和之前生成的ID重复。

   你可能会想到，何不把这个自增的序列号存储起来，比如数据库中？但是，雪花算法有自己的设计原则：尽量不借助第三方组件来实现，因此存数据库这个方法不可行。其实，我们需要解决的问题是自增序列号会和之前生成的ID重复，恰巧，有一个自动流逝、永不回退的因素：时间，天然可以解决这个问题。无论发生什么事情（程序重启、宕机等），时间会不停流逝、更新，不会担心重复的问题。当然，时间毕竟也是有精度的，在单位精度的时间内可能需要生成很多个唯一ID，这个时候，时间+自增序列号的组合应该能工作的很好。

1. 至此，单应用内的唯一ID生成算是被解决了，而我们的最终目标是分布式环境下唯一ID的生成。在分布式环境，整个系统由多个单应用组成，如果每个单应用都用时间+自增序列号的方式生成ID，很显然，有很大概率重复，这不符合我们的要求。这个时候，就要再引入别的因素解决这个问题。

   从前面 时间因素的引入，我们可能也能联想到引入 空间因素。分布式的系统天然是有 空间 差异的，多个单应用被部署在多台机器，每个应用都是独立的进程。通常，每个应用一般都会有自己的标记，可能是机器ID，也可能是进程的实例序号，可以事先给每个进程分配好，通过配置文件的形式读取。ID 中附加这样的空间标记（应用空间标识），多个单应用生成的 ID 就有了区分，即使他们可能是在相同的时间，恰巧相同的序列号的情况下。

1. 其实，这三个（再加符号位）因素基本也就构成了雪花算法的基本组成部分。64个比特位的数字，每个因素占用一些比特位，整体就是一个唯一ID。

   有时候，还需要考虑多个因素的先后顺序问题。分布式唯一ID通常会作为数据库的主键来存储数据，因此，对于时序性也是有要求的，后生成的ID尽量比先生成的ID要大。这样考察这主要的三个因素，时间因素就被放到了最前面，应用空间标识和自增序列号依次往后放置：

雪花算法细节

雪花算法生产的ID是64位数字，因此上述三个主要因素都需要在满足需求的情况下尽量压缩占用的位数。

对于 时间 因素来说，如果用绝对时间戳，这个数值目前是十几亿的级别，占用的比特位数会很高，这势必压缩其他因素的取值范围。稍微优化一下，我们可以规定一个应用的起始点（代码中定死），然后用时间差值来代表时间因素。

典型的雪花算法是用41位比特表示时间差，计算一下：

2 ^ 41 / (60 * 60 * 24 * 365) = 69730

从设置的起始时间算起，可以用 69730 年。这个单位时间是秒级别。如果单位时间（1秒）内，会生成多个唯一ID，就会有碰撞，此时序列号因素就可以起效，需要生成ID时，自增即可。经典的雪花算法中，自增序列号分配的是12个bit，2^12 = 4096，可以支持1秒内并发生成4096个唯一ID，数量比较有限。

如果我们把单位时间的精确度提高，从1秒提高到1毫秒，可以使得单位时间碰撞的几率变得很小，而序列号在单位时间（1毫秒）内还是4096个，那么，每秒生成的id数量是 4096 * 1000 = 4096000 个，百万量级的，这对于大并发也是够用的。

时间精度提高之后，使用的年限就会缩短1000倍，69730 / 1000 = 69 年，也基本够用了。

精度能不能继续提高呢？答案是不太合适。一是毫秒以下的精度可能不准，有可能发生碰撞；而是年限继续缩短可能导致不够使用。

异常情况

并发过大

前面说了，如果时间的精度是1毫秒，可以支持1毫秒内生成4096个唯一ID。

假如瞬时并发比这个还高呢？4096个在单位时间内消耗光？算法必须要考虑这种并发异常情况的处理。

通常的解决方案是让程序等着，自旋等待，一直等到时间自然流逝到下一个毫秒，此时程序相当于卡住了。

注意不是 sleep 1ms，因为1ms太短，程序无法控制很精确的控制该sleep多久才能进入下一毫秒。

另外，sleep 1ms 的代价太大，程序需要从用户态切入内核态，还不如用for不停的循环检查时间是否到了，自旋等待。

时间回拨

雪花算法用到了时间，一般取的就是机器上的时间。通常，各个机器上的时间应该是一致的。但是有时候时间同步也会出现异常。NTP通常被用作时间同步，有的机器可能时间走快了点，有的机器时间可能走慢了点，快的机器会被NTP强行和其他机器拉齐到一致的进度，这个异常就是时间回拨。

前面说了，雪花算法生成的ID保证唯一的重要前提是时间永远往后更新，不会回退。但是时间回拨打破了这个约定。只要有时间回退，生成的ID就有可能重复，这是万万不可接受的。

这个时候怎么办呢？

似乎也没有特别好的办法，这主要还是工程应用上出现的异常问题。

标准的解决办法是拒绝服务，接口直接返回错误，由应用层处理唯一ID分配失败的情况。

优化方案

上面说的两种特殊情况，一种是并发高峰在单位时间内发生碰撞，连序列号也用完了（4096个）；一种是时间回拨，直接拒绝服务。

不知道你有没有这样的感觉，这两种异常的处理方式都有点粗暴，解决方案本身会对业务造成较大影响，通常是有损服务。

我们再想想有没有更优化的方法。

在前面的解释中，不知你是否发现，算法中用到了时间因素，时间其实是一个自动更新的因素：不管单位时间内是否需要分配ID，时间都是持续流逝的。而业务的需求很可能是波动的：比如晚上是业务低谷，自然分配ID的需求比较低，白天业务繁忙，分配ID的需求比较高。这样，单位时间内的分配能力和实际业务需求很可能出现一个错配，不需要的时候被浪费掉，需要的时候能力不足：

那我们能不能 把业务低谷期间可分配的ID提前缓存起来，后面分配的时候优先用这些？缓存的没有了再实时分配新的id。缓存的生成可以用个定时器，在不忙的时候生成。

这种提前缓存起来应对需求波动的方法，在日常生活中其实也很常见，即各种储备机制：储备粮、储备石油、储备猪肉：

储备ID机制其实和储备猪肉机制其实思想是类似的。

实际在使用时，为什么先用缓存的储备ID？

还是回到我们之前提到的ID时序性原则；因为缓存的储备ID都是过去时间分配的ID，如果要保证ID是递增的，就得优先用过去时间对应的，如果储备的ID不够再动用当前的分配能力。

通过提前储备，我们可以显著提升并发量；而如果发生了时间回拨的异常情况，不需要拒绝服务，直接用储备的ID即可，等下次需要新分配，很可能时间已经正常了。

业内解决方案

业内实际上有不少根据自己的实际情况，对雪花算法做一些变形的解决方案。

百度的唯一ID生成

项目地址是 https://github.com/baidu/uid-generator。主要是两方面的变形：

1）DefaultUidGenerator

具体改动如下：

• 时间部分，压缩比特占用，将经典雪花算法的41bit调整为28bit，时间精度调整为秒，可以使用8.7年。这里可能是考虑到毫秒精度的必要性，减少浪费。
• 时间精度调整为秒之后，碰撞肯定会增加，对应的序列号肯定也要相应增大。百度的算法序列号占用的bit改为 13bit，总数为8192个，理论上也够了。
• 空间应用标识，原来的算法占用10bit，总数是1024，在大体量的分布式环境下，不是很够。改为22bit，并且不是固定分配的，而是进程启动由数据库来自增分配，可以支持400多w次启动。当然，这里和经典雪花算法的不依赖第三方组件的原则有区别，这里更多是从工程实践的角度来考虑的，比较数据库在分布式系统中普遍存在，引入进来并不会造成额外负担。

2）CachedUidGenerator

支持带缓存的ID生成。和我们上面提到的储备ID是类似的。

使用RingBuffer缓存生成的id。RingBuffer是个环形数组，默认大小为8192个，里面缓存着预先储备的ID，并且新ID会逐渐替代之前的老ID。

== 获取id

会从RingBuffer中拿一个id，支持并发获取。

== 填充id

RingBuffer填充时机

• 程序启动时，将RingBuffer填充满，缓存着8192个ID
• 在调用getUID()获取id时，检测到RingBuffer中的剩余id个数小于总个数的50%，将RingBuffer填充满，使其重新填满 8192个。
• 定时填充（可配置是否使用以及定时任务的周期）

百度的这个算法，每次生成ID都是从RingBuffer里拿，但是不够了它不会去实时新计算。只会等待专门的填充线程来做填充。

好了，看了这么多，一定很费脑力吧。来个笑话放松一下 :)

【笑话一则】问：在野外遇到老虎应该怎么保命？答：肯定是跪下认爹啊，因为虎毒不食子。

感谢您花时间阅读这篇文章！如果觉得有趣或有收获，请来个关注、评论、点赞吧，您的鼓励是我持续创作的动力，蟹蟹！