让人眼前一亮的算法------唯一ID生成器snowflake

怼烎@ 2023-06-29 02:22 33阅读 0赞

# 分布式全局唯一ID生成器 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 1][]

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

### 时间戳 ###

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

### 利用数据库自增 ###

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

### 利用Redis原子操作incrBy ###

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

### UUID/GUID ###

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

### snowflake ###

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

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

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

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

## snowflake名字起得真好 ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 3][]

### 好处与不足 ###

snowflake有以下几个特点：

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

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

### 长度合适 ###

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

### 趋势递增 ###

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

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

### 为何追求递增 ###

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

### 隐患 ###

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

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200109213132704.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200109213153351.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200109213346413.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/202001092134232.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200109213553833.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw,size_16,color_FFFFFF,t_70