雪花算法理论和实现分析

雪花算法理论和实现分析

目录

为什么需要分布式ID

分布式ID需要满足哪些条件

雪花算法原理(分布式ID的生成方式之一，基础理论)

雪花算法可以保证

不足

业内开源解决方案（都是优化上面的两个不足）

Leaf：美团的分布式唯一ID方案

leaf-snowflake方案

百度（uid-generator）

实现

CachedUidGenerator

总结

参考资料

---

雪花算法是实现分布式ID最常用的方法。本文首先讲明白雪花算法的原理，然后介绍一下业内开源实现方案的优缺点(美团leaf和百度uid-generator)，不足之处评论区交流。

为什么需要分布式ID

举两个业务场景

数据量比较大的时候，一般会选择分库分表的方案。分库分表后需要有一个唯一ID来标识每一条数据，数据库自增ID不能满足要求。比如订单、优惠券、聊天消息等都需要唯一ID做标识。新旧数据合并迁移，如果用自增ID就尴尬了。

分布式ID需要满足哪些条件

全局唯一：必须保证ID是全局性唯一的，基本要求

高性能：高可用低延时，ID生成响应要块，否则反倒会成为业务瓶颈

高可用：100%的可用性是骗人的，但是也要无限接近于100%的可用性

好接入：要秉着拿来即用的设计原则，在系统设计和实现上要尽可能的简单

趋势递增：最好趋势递增，这个要求就得看具体业务场景了，一般不严格要求

雪花算法原理(分布式ID的生成方式之一，基础理论)

雪花算法还是比较容易理解的，使用一个 64 bit 的 long 型的数字作为全局唯一 id，整体分为4个部分。

 

1bit，不用，因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为041bit-时间戳，用来记录时间戳(毫秒)，保存的是一个差值(当前时间与一个基准时间，基准时间一般是系统上线时间，确定后不可更改)，大概可用69年(2^41/365/24/60/60/1000)10bit-工作机器id，用来记录工作机器ID。

12bit-序列号，序列号，用来记录同毫秒内产生的不同id。即可以用0、1、2、3、…4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号。保证的是一个服务器同一时间的并发量。

雪花算法可以保证

1、所有生成的id按照时间趋势递增
2、整个分布式系统内不会产生重复id，工作机器id决定
3、不依赖数据库等第三方系统，稳定性高，生成ID的性能也是非常高的

不足

1、时钟回退：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态
2、workerId不易维护：集群环境下，机器太多，手动维护不方便也很容易出问题

业内开源解决方案（都是优化上面的两个不足） Leaf：美团的分布式唯一ID方案

leaf总计有两种模式：Snowflake和Segment。主要说一下Snowflake。

leaf-snowflake方案

Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号。

1、workerID分配问题

为了解决手动分配workerID容易出错的问题，leaf依赖zookeeper。使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID

2、时钟回退问题

并没有完全避免时钟回退的问题，还是通过一些策略优化手段尽量避免时钟回退带来的业务中断。例如关闭时钟同步，重试、报警并下线有问题的服务器等。

百度（uid-generator）

uid-generator是由百度技术部开发，基于Snowflake算法的唯一ID生成器。百度对雪花算法bit位设计进行了更改。四部分站位多少都可以根据业务进行灵活配置

sign(1bit)：固定1bit符号标识，即生成的UID为正数。

delta seconds (28 bits)：也是当前时间和基准时间(系统上线时间)的差值，单位是秒。最多可支持约8.7年(2^28/365/24/60/60)

worker id (22 bits):机器ID，内置实现是根据数据库自增ID进行分配，用过之后不可再用(为什么，后面会进行分析)，每次服务器启动都需要重新获取机器ID。因此最多可支持约420w(2^22)次机器启动

sequence (13 bits)：每秒下的并发序列，13 bits可支持每秒8192个并发

实现

百度提供了两种生成器

DefaultUidGenerator：没有解决时钟回退的问题，直接抛出异常。

CachedUidGenerator：是UidGenerator的重要改进实现，通过借用未来时间来解决时钟回退的问题

1、workerID分配问题

两种生成器都解决了workerID自动分配的问题，通过依赖DB来实现。每次服务启动的时候，会在数据库中新增一条数据，然后使用该条数据返回的自增ID作为workerID。

2、时钟同步问题

DefaultUidGenerator没有解决时钟同步问题。CachedUidGenerator解决了时钟同步问题。下面说一下是如何解决的。

CachedUidGenerator

 服务启动时，会获取当前启动的时间

1、服务启动时获取当前时间，和基准时间的差值，就是当前的delta seconds的值
2、获取当前秒下的所有sequence取值，组装成分布式ID，进行缓存
3、缓存中剩余的分布式ID达到阈值时，缓存的lastSecond.incrementAndGet，自增来表示下一秒
4、运行第2步

百度是通过字段自增自己维护了逻辑时间代替对系统真实时间的依赖，也因此带来一个问题：

目前CachedUidGenerator在初始化的时候lastSecond用的是当前秒，后续的只是在此基础上+1（不在依赖时钟，并发高的时候还可以预借），不过如果ID生成很少，那么就可能导致生成的ID（解析后）于实际的时间相差很多。  

为什么workerID用过之后不可再用？

如果并发很高，则逻辑时间会超过系统的真实时间，这就是借用未来时间的关键。也正是借用了未来的时间，因此使用过的workerID不可以再用，否则就有可能产生重复的分布式ID

总结

没有100%完美的方案，找到适合自己业务的方案就是最优的。有很多实现的细节，大家可以自己查看参考资料中给的链接

参考资料

Leaf——美团点评分布式ID生成系统 - 美团技术团队

https://github.com/baidu/uid-generator