分布式系统中唯一ID的生成

本是古典何须时尚 2022-06-05 00:17 217阅读 0赞

分布式系统中唯一ID的生成

http://www.raychase.net/4408?utm\_source=tuicool&utm\_medium=referral

其实老早就像写一点这个话题。几乎我见过的所有大型系统中，都需要一个唯一ID的生成逻辑。别看小小的ID，需求和场景还挺多：

*  这个ID多数为数字，但有时候是数字字母的组合；
 *  可能随机，也可能要求随时间严格递增；
 *  有时ID的长度和组成并不重要，有时候却要求它严格遵循规则，或者考虑可读性而要求长度越短越好；
 *  某些系统要求ID可以预期，某些系统却要求ID随机性强，无法猜测（例如避免爬虫等等原因）。

**独立的生成服务**

比如数据库。最常见的一种，也是应用最多的一种，就是利用数据库的自增长序列。比如Oracle中的sequence的nextVal。有多台application的host，但是只有一个数据库。本质上这是耍了个小赖皮，把某分布式系统唯一ID的生成逻辑寄托到一个特定的数据库上，于是分布式系统存在中心节点了。

这个方法简单，而且可以严格保证单调递增。不过中心化带来的问题众所周知，比如单点故障，比如性能方面的扩展上限。有一种workaround，正如同数据库有主从库一样，可以给不同的数据库设置sequence范围（比如一个是从1~100000000，另一个是从100000001到200000000），或者是设置相同的步长（比如一个是1、3、5、7……另一个是2、4、6、8……），但是互相不重复，从而保证唯一性。不过这样不同sequence生成节点整体内的ID递增性就丢失了。

其它的生成服务也有很多，很多系统中设计的ticket server本质上也就是扮演这样一个角色，特点是这个ID生成服务系统必须独立于现有母系统（客户系统）。但是注意，单点service不代表一定会存在单点故障，单点service一样可以HA。因为这个service也可以是去中心化的。

既然说到这样的service，开源ID生成算法上，最最有名的是Twitter的[snowflake][]，它正是重点考虑到high scale而设计的。64bit长度以下，无需节点间复杂的协作，ID有序。每一条snowflake生成的ID都包含三个部分：timestamp、节点编号，以及一个自增的子序列号。额外地，需要提及其中两个问题的处理：

*  timestamp冲突：timestamp本身是毫秒级的，如果出现冲突，那么其中的自增子序列号会自动+1从而保证生成的ID不会和上一条的冲突。
 *  节点编号的生成：这个其实是从Zookeeper去获取的，也是被诟病说它不够去中心化的原因之一（一个改进方案是Boundary Flake，不需要依赖于这个获取逻辑）。

**本地生成器**

这个也很常见，局限性也非常明显。通常必须满足这样的要求：在不同的host（分布式节点）之间没有关系保证（比如递增性）。

比如我见过这样的逻辑，用host的唯一编号来作前缀（保证环境中节点编号的唯一性即可），毫秒数来生成ID的主体部分。看似简单，一样可以解决唯一ID的问题。当然它的局限性也很多，如果使用当前毫秒数，无法对于不同host生成的ID进行先后比较（因为无法确保时间是严格一致的）；而且只能一个毫秒最多只能生成一个ID，如果要生成两个就会产生冲突。这两个问题当中，对于后者有一个改进方案，就是使用一个AtomicLong来保证冲突情况下的自增序列。

既然提到了AtomicLong，有一些开源项目做到了对AtomicLong的分布式实现。比如[Redisson][]（基于Redis）。但这不属于这里讨论的本地生成器范畴。

还有一种典型是[UUID][]。UUID的全称叫做universally unique identifier，Java中一个UUID代表一个128bit的数。在分布式系统中，它比前面说的方案有更多优势，比如长度一致，比如没有一个毫秒内最多只能生成一个的要求。但是，尽管可以认为它是唯一的，基于随机数产生的UUID冲突却是[理论上可能存在][Link 1]的。

**文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接[《四火的唠叨》][Link 2]**

[snowflake]: https://github.com/twitter/snowflake
[Redisson]: https://github.com/redisson/redisson
[UUID]: https://docs.oracle.com/javase/7/docs/api/java/util/UUID.html
[Link 1]: https://zh.wikipedia.org/wiki/%E9%80%9A%E7%94%A8%E5%94%AF%E4%B8%80%E8%AF%86%E5%88%AB%E7%A0%81#.E9.9A.A8.E6.A9.9FUUID.E7.9A.84.E9.87.8D.E8.A4.87.E6.A9.9F.E7.8E.87
[Link 2]: http://www.raychase.net/4408