Skip to main content

什么是雪花算法?

作者:程序员马丁

在线博客:https://open8gu.com

note

大话面试,技术同学面试必备的八股文小册,以精彩回答应对深度问题,助力你在面试中拿个offer。

回答话术

分布式系统中,有一些需要使用全局唯一 ID 的场景,这种时候为了防止 ID 冲突可以使用 36 位的 UUID,但是 UUID 有一些缺点,首先他相对比较长,另外 UUID 一般是无序的。

有些时候我们希望能使用一种简单些的 ID,并且希望 ID 能够按照时间有序生成。

1. 什么是雪花算法

Snowflake 中文的意思是雪花,所以常被称为雪花算法,是 Twitter 开源的分布式 ID 生成算法。

Twitter 雪花算法生成后是一个 64bit 的 long 型的数值,组成部分引入了时间戳,基本保持了自增。

2. 雪花算法优缺点

算法优点:

  1. 高性能高可用:生成时不依赖于数据库,完全在内存中生成。
  2. 高吞吐:每秒钟能生成数百万的自增 ID。
  3. ID 自增:存入数据库中,索引效率高。

算法缺点:依赖与系统时间的一致性,如果系统时间被回调,或者改变,可能会造成 ID 冲突或者重复。

3. 适用场景

因为雪花算法有序自增,保障了 MySQL 中 B+ Tree 索引结构插入高性能。

所以,日常业务使用中,雪花算法更多是被应用在数据库的主键 ID 和业务关联主键。

问题详解

snowflake 结构如下图所示:

包含四个组成部分:

不使用:1bit,最高位是符号位,0 表示正,1 表示负,固定为 0。

时间戳:41bit,毫秒级的时间戳(41 位的长度可以使用 69 年)。

标识位:5bit 数据中心 ID,5bit 工作机器 ID,两个标识位组合起来最多可以支持部署 1024 个节点。

序列号:12bit 递增序列号,表示节点毫秒内生成重复,通过序列号表示唯一,12bit 每毫秒可产生 4096 个 ID。

通过序列号 1 毫秒可以产生 4096 个不重复 ID,则 1 秒可以生成 4096 * 1000 = 409w ID

默认的雪花算法是 64 bit,具体的长度可以自行配置。如果希望运行更久,增加时间戳的位数;如果需要支持更多节点部署,增加标识位长度;如果并发很高,增加序列号位数。

雪花算法并不是一成不变的,可以根据系统内具体场景进行定制。