Snowflake算法介绍

Snowflake算法介绍

22 2019-03-15 19:00:15

### 算法描述
Snowflake算法本身非常简单，一张图即可表示：
![](/img/pic/2019031518585756303_png_800_271_50083)
> Snowflake算法生成的64bit-id组成

- `1bit` 始终为0，保证生成的id是正数
- `41bit` 时间戳，可以保证生成的id是局部递增
- `10bit` 工作机器id，可保证不同机器生成的id分布在不同的区间，绝不重复
- `12bit` 序列号，保证单一时间单位内生成的id不重复

### Snowflake的优点
**算法简单，易实现，易定制**
几乎使用位操作就可以完成计算。
工作机器id可使用6bit，序列号可以使用16bit，单机理论生成总id数会更多，很好定制。

**生成的id局部递增**
这一点由时间戳和序列号保证。但是多机结果不是单调递增的。

**全局唯一**
单机情况下每台机器生成的id可以是单调递增的，不会重复。
多机情况下，每台机器的生成结果分布在不同空间，不会重复。

**生成id数量不易猜测**
如果使用单调递增id，那么使用该id的数据量级很容易被猜测。
比如今天12点生成一个订单id1，明天12点再生成一个订单id2，那么这一天内生成的订单总数可以通过id2 - id1来推测。

### Snowflake的缺点
**有理论最高生成数量限制**
每个时间单位内理论上可生成2^12即4096个id。
当然，如果41bit时间戳的单位是毫秒的话，目前id生成速度还无法达到理论速度。但这一点天然就是这个算法的瓶颈。

**系统时间回拨问题**
由于该算法严重依赖系统时间，一旦系统时间发生回拨，会导致算法生成重复的id。
这一点有不少规避方案，比如等待系统时间追上最后生成id的时间，更换workerId等。

**实现问题**
如果时间戳以毫秒为单位，目前一毫秒内id几乎生成不了多少个，会造成大量id空间浪费；
如果以秒为单位，一秒内12bit的sequence序列又根本不够用。
id的各部分分配的bit数需要仔细权衡。

### 实例
**[例1. 百度的uid-generator](https://github.com/baidu/uid-generator)**
采用Buffer思想，提前生成未来时间的id，避免了单位时间内理论生成id数量限制的问题，同时将读写分离，实现单线程生成id，并发获取id的模式。
优点：
- 可根据xml配置方便地定制自己的生成策略
- 由于读写分离及缓存策略，吞吐量高，据说qps可达600w

缺点：
- 不是开箱即用，不自定义的话依赖MySql记录工作机器
- 使用秒为时间戳单位，且在吞吐量大时可能使用未来的时间戳生成id，减弱了与时间的关联性，可能造成id的时间戳部分因为过于超前变得不可读
- 由于进行了缓存，且没有清理缓存的策略，也并非每秒填充一次缓存，同样减弱了与时间的关联性，当吞吐量过小时也可能导致时间戳部分由于过于落后变得不可读

**[例2. 基于redis的icicle](https://github.com/intenthq/icicle)**

### 参考资料
[理解分布式id生成算法SnowFlake - SegmentFault思否](https://segmentfault.com/a/1190000011282426#articleHeader7)
[分布式唯一id：snowflake算法思考 - 掘金](https://juejin.im/post/5a7f9176f265da4e721c73a8)
[Leaf——美团点评分布式ID生成系统 - 美团技术团队](https://tech.meituan.com/2017/04/21/mt-leaf.html)