1 介绍
雪花算法（Snowflake）是一种生成分布式全局唯一ID的算法，生成的ID称为Snowflake IDs或snowflakes。这种算法由Twitter创建，并用于推文的ID。目前仓储平台生成ID是用的雪花算法修改后的版本。
雪花算法几个特性
- 生成的ID分布式唯一和按照时间递增有序，毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
- 不依赖数据库等三方系统，稳定性更高，性能非常高的。
- 可以根据自身业务特性分配bit位，非常灵活。
2 其他分布式唯一ID生成方案
2.1 数据库生成
以MySQL为例，单库单表，给字段设置auto_increment来生成全局唯一ID
优点:
- 非常简单，维护成本比较低
- ID唯一，单调递增，可以设置固定步长
缺点:
- 可用性难以保证，每次生成ID都需要访问数据库，瓶颈在于单台MySQL读写性能上，如果数据库挂掉会造成服务不可用，这是一个致命的问题
2.2 UUID
UUID是由一组32位数的16进制数字所构成，故UUID理论上的总数为16^32=2^128，约等于3.4 x 10^38。也就是说若每纳秒产生1兆个UUID，要花100亿年才会将所有UUID用完。UUID的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的32个字符。示例：550e8400-e29b-41d4-a716-446655440000
优点:
- 本地生成ID，不需要进行远程调用，没有网络耗时
- 基本没有性能上限
缺点:
- 可读性差
- 长度过长，16字节128位，生成的UUID通常是36位(包含-)，有些场景可能不适用。如果用作数据库主键，在MySQL的InnoDB引擎下长度过长，二级索引(非主键索引)会占用很大的空间。
- 无法保证趋势递增，在MySQL的InnoDB引擎下，新插入数据会根据主键来寻找合适位置，会导致频繁的移动、分页增加了很多开销。
3 snowflake算法实现细节
3.1 拆解64bit位
snowflake生成的id通常是一个64bit数字，java中用long类型。
图1：snowflake算法中的64-bit划分方式
- 1-bit不用于生成ID(符号位) long 范围[-2^(64-1), 2^(64-1) ] , (64-1)中的1代表的就是符号位
- 41-bit时间戳(毫秒)可以表示1 x 2^41 / (1000 x 3600 x 24 x 365) = 69年的时间
- 10-bit可以分别表示1 x 2^10 = 1024台机器,范围[0,1023]
- 12-bit表示1ms内自动递增的序列号，1 x 2^12 = 4096个 范围[0,4095]。单机1ms可以生成4096个不重复的ID
通过上述方式进行生成ID，可以保证1024台机器在任意69年的时间段里不会出现重复的ID，而且单台机器支持一秒能够生成409.6万个ID。
这种方式可以支撑大部分业务，如果不满足，可以根据自身业务特点来调整不同命名空间占用的bit数。如果我们有划分IDC的需求，可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器。如果我们的机器位比较特殊，数值相对较大，但是对并发要求不高，还可以将时间位调整为秒级，时间位节省出10-bit留给机器位。
- 1-bit符号位
- 31-bit时间戳(秒)1 x 2^31/ (3600 x 24 x 365) = 68年
- 22-bit机器位 运维平台给提供的数值 范围 [0,2^22-1]
- 10-bit序列号 范围[0, 2^10 - 1]共1024个
通过上述方式进行生成ID，可以保证4194303台机器在任意68年的时间段里不会出现重复的ID，而且单台机器支持一秒能够生成1024个ID。
3.2 Java实现
public class IdGenerator {
// 起始时间
private final long from = 1422720000000L;
// 机器位所占bit位数
private final long instanceIdBits = 10L;
// 序列号所占bit位数
private final long sequenceBits = 12L;
// 机器位左移长度
private final long instanceIdShift = sequenceBits;
// 时间位左移长度
private final long timestampLeftShift = sequenceBits + instanceIdBits;
// 序号1: 最大机器ID
private final long maxInstanceId = -1L ^ (-1L
