那些惊艳的算法们（四）——唯一ID生成器snowflake

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了那些惊艳的算法们（四）——唯一ID生成器snowflake，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3936字，纯文字阅读大概需要6分钟。

内容图文

同步发表在个人博客中：http://blog.lanjingdejia.com/articles/2019/01/15/1547516544183.html

分布式全局唯一ID生成器

很多场景需要使用全局唯一ID，用来标识唯一一条消息，唯一一笔交易，唯一一个用户，唯一一张图片等等。
传统数据库表的自增主键是很简单的一种实现方式，前提是你没有分库，也没有分表，如果你分表了，id就会重复，失去唯一性：

当然，通过数据库的一些配置，使不同的分表以不同的起始值但是相同的步长自增，可以绕开这个限制：

但是，如果哪天发现数据量增大，原先的分表不够用了，需要扩容，这时，就很麻烦很难搞了。
所以，如果存在一种和业务数据无关的全局唯一ID生成器就好了。开动脑筋，我们能想到的有以下几种：

时间戳

用时间做唯一id，这个在并发比较高或者分布式环境中基本不可行，统一时间生成的id是重复的，不满足全局唯一。

利用数据库自增

依然利用数据库产生自增id，保证唯一性，和开头提到的不同之处是，单独使用一张（或固定几张）数据库表专门用来产生自增id，与业务无关，后续不再重新分表，数据量大时，可以删除早一些时候产生的数据。
这样做的好处是，实现简单，容易理解。
不好的地方是，严重依赖数据库，id产生速率受数据库性能以及连接数据库的网络影响。

利用Redis原子操作incrBy

好处：实现简单，容易理解。
坏处：依赖Redis，且Redis需要持久化。

UUID/GUID

好处：使用非常简单，不需要依赖其他设施。
坏处：太长，128bit，不适合做数据库主键。

snowflake

通常情况下，用时间来表示是最简单的，如果同一时间（毫秒）有很多请求进来怎么办？
时间戳后面拼接上一个数字，这个数字可以通过锁控制每次递增，每毫秒清零，重新开始递增。

即便这样，只是解决了单机的问题，如果是分布式环境，不同的机器，还是可能产生一样的id的，这怎么解决？
在上述时间戳和数字的基础上在拼接上机器的id，这样就不会重复了。

不同的数据中心，机器id是可能重复的，怎么搞？
再拼接上数据中心的id就行了。

不同的星球上。。。

思想朴实无华，但是大道至简。

最终产生的id是这个样子的，时间戳，工作机器id，序列号可以根据实际需要调整长度（通常情况下不需要调整，完全够用），总体64bit就行：

snowflake名字起得真好

雪花(snowflake)的形状和算法的思想十分吻合，沿着主干（时间戳），如果有重复，那么分叉分出机器id，如果仍有重复，再分叉，分出序列号

好处与不足

snowflake有以下几个特点：

算法简单，不需要依靠额外组件

id可以直接靠算法在内存中产生，靠锁控制并发，不需有诸如MySQL，Redis这样的外部依赖，无维护成本。

长度合适

snowflake产生的id长度为64bit，对应大多数语言的long类型，用于作为数据库唯一键建立索引时，也不会因为长度过大影响性能。

趋势递增

snowflake产生的id并不是严格递增的，而是趋势递增的。
这是因为，当id生成器分布式部署的时候，比如统一毫秒由不同机器产生的id，时间戳的部分肯定是一样的，后面机器id的部分并不一定是递增的。
举个例子，有两个机器，id分别是0和1，那么同一毫秒内产生的id可能是这样的顺序：

从图中可以看出，由于机器id的存在，在同1毫秒内产生的id并不一定是递增的，但是因为时间戳的存在，在毫秒间总体上id是递增的。
所以总体上说snowflake产生的id是趋势递增的。

为何追求递增

为何追求递增？因为递增最大的优势就是对磁盘IO是友好的。
熟悉磁盘结构的同学们都知道，随机写的效率是很慢的，因为磁头需要转动到指定的位置，这个磁头转动的过程比起cpu或者内存来，完全不是一个数量级的，太慢太慢了，所以如果能尽可能的使数据靠近在一一起（递增就能靠在一起），那么就不需要频繁的抬起磁头，转动磁盘，写数据了，一路写到底会快很多。
一些大型分布式数据库，比如HBase，ElasticSearch等，也都是利用顺序写这个特点提高数据的写入性能的。

隐患

snowflake并不完美，因为有一种情况，snowflake产生的id是有可能会出现重复的。
为什么会重复，我们再回头看看snowflake产生的id的组成：时间戳+机器id+序列号。
这三部分，机器id可以不重复，序列号也可以做到不重复，那唯一可能重复的就是时间戳了。
什么？时间怎么回重复？时间明明是一直向前的，除非时间倒退，退回到之前的某个时间点，再次产生的id才可能是重复的。
你说对了，人类感受的时间是不会倒退的，但是，机器上的时间都是时钟，时钟可能会因为种种原因变慢了或者变快了，比如有一天你（或者机器上的时间同步器）发现有一台机器的时钟变快了，于是往回拨1秒，然后。。。 你懂的

时钟的问题，一直都是老大难，某些对时间及其敏感的程序，甚至会考虑使用GPS上的原子钟来做时钟同步，或者，干脆有土豪（某歌）直接在数据中心自己搞原子钟，然并卵，时间同步时的网络传输延迟、抖动，依然无解。
永远都是只能减小，无法消灭。

##最后
忍不住再夸一下算法的名字，snowflake，真是美妙。

内容总结

以上是互联网集市为您收集整理的那些惊艳的算法们（四）——唯一ID生成器snowflake全部内容，希望文章能够帮你解决那些惊艳的算法们（四）——唯一ID生成器snowflake所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---