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

分布式全局唯一ID生成器

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

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

imagepng

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

时间戳

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

利用数据库自增

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

利用Redis原子操作incrBy

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

UUID/GUID

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

snowflake

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

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

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

不同的星球上。。。

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

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

snowflake名字起得真好

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

好处与不足

snowflake有以下几个特点:

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

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

长度合适

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

趋势递增

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

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

为何追求递增

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

隐患

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

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

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


我有一壶酒,
足以慰风尘。
尽倾江海里,
赠饮天下人。