5、雪花算法
Snowflake,雪花算法是有Twitter开源的分布式ID生成算法,以划分命名空间的方式将64bit位分割成了多个部分,每个部分都有具体的不同含义,在Java中64Bit位的整数是Long类型,所以在Java中Snowflake算法生成的ID就是long来存储的。具体如下:
- 第一部分: 占用1bit,第一位为符号位,不适用
- 第二部分: 41位的时间戳,41bit位可以表示241个数,每个数代表的是毫秒,那么雪花算法的时间年限是
(241)/(1000×60×60×24×365)=69
年 - 第三部分: 10bit表示是机器数,即
2^ 10 = 1024
台机器,通常不会部署这么多机器 - 第四部分: 12bit位是自增序列,可以表示
2^12=4096
个数,一秒内可以生成4096个ID,理论上snowflake方案的QPS约为409.6w/s
雪花算法案例代码:
public class SnowflakeIdWorker { // ==============================Fields=========================================== /** * 开始时间截 (2020-11-03,一旦确定不可更改,否则时间被回调,或者改变,可能会造成id重复或冲突) */ private final long twepoch = 1604374294980L; /** * 机器id所占的位数 */ private final long workerIdBits = 5L; /** * 数据标识id所占的位数 */ private final long datacenterIdBits = 5L; /** * 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); /** * 支持的最大数据标识id,结果是31 */ private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); /** * 序列在id中占的位数 */ private final long sequenceBits = 12L; /** * 机器ID向左移12位 */ private final long workerIdShift = sequenceBits; /** * 数据标识id向左移17位(12+5) */ private final long datacenterIdShift = sequenceBits + workerIdBits; /** * 时间截向左移22位(5+5+12) */ private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; /** * 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */ private final long sequenceMask = -1L ^ (-1L << sequenceBits); /** * 工作机器ID(0~31) */ private long workerId; /** * 数据中心ID(0~31) */ private long datacenterId; /** * 毫秒内序列(0~4095) */ private long sequence = 0L; /** * 上次生成ID的时间截 */ private long lastTimestamp = -1L; //==============================Constructors===================================== /** * 构造函数 * */ public SnowflakeIdWorker() { this.workerId = 0L; this.datacenterId = 0L; } /** * 构造函数 * * @param workerId 工作ID (0~31) * @param datacenterId 数据中心ID (0~31) */ public SnowflakeIdWorker(long workerId, long datacenterId) { if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId)); } if (datacenterId > maxDatacenterId || datacenterId < 0) { throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId)); } this.workerId = workerId; this.datacenterId = datacenterId; } // ==============================Methods========================================== /** * 获得下一个ID (该方法是线程安全的) * * @return SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常 if (timestamp < lastTimestamp) { throw new RuntimeException( String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } //如果是同一时间生成的,则进行毫秒内序列 if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; //毫秒内序列溢出 if (sequence == 0) { //阻塞到下一个毫秒,获得新的时间戳 timestamp = tilNextMillis(lastTimestamp); } } //时间戳改变,毫秒内序列重置 else { sequence = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID return ((timestamp - twepoch) << timestampLeftShift) // | (datacenterId << datacenterIdShift) // | (workerId << workerIdShift) // | sequence; } /** * 阻塞到下一个毫秒,直到获得新的时间戳 * * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * * @return 当前时间(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } /** * 随机id生成,使用雪花算法 * * @return */ public static String getSnowId() { SnowflakeIdWorker sf = new SnowflakeIdWorker(); String id = String.valueOf(sf.nextId()); return id; } //=========================================Test========================================= /** * 测试 */ public static void main(String[] args) { SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); for (int i = 0; i < 1000; i++) { long id = idWorker.nextId(); System.out.println(id); } } }
雪花算法强依赖机器时钟,如果机器上时钟回拨,会导致发号重复。 通常通过记录最后使用时间处理该问题。
6、美团(Leaf)
由美团开发,开源项目链接:
Leaf同时支持号段模式和snowflake算法模式,可以切换使用。
snowflake模式依赖于ZooKeeper,不同于原始snowflake算法也主要是在workId的生成上,Leaf中workId是基于ZooKeeper的顺序Id来生成的,每个应用在使用Leaf-snowflake时,启动时都会都在Zookeeper中生成一个顺序Id,相当于一台机器对应一个顺序节点,也就是一个workId。
号段模式是对直接用数据库自增ID充当分布式ID的一种优化,减少对数据库的频率操作。相当于从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,业务服务将号段在本地生成1~1000的自增ID并加载到内存。
7、百度(Uidgenerator)
源码地址:
中文文档地址:
UidGenerator是百度开源的Java语言实现,基于Snowflake算法的唯一ID生成器。它是分布式的,并克服了雪花算法的并发限制。单个实例的QPS能超过6000000。需要的环境:JDK8+,MySQL(用于分配WorkerId)。
百度的Uidgenerator对结构做了部分的调整,具体如下:
时间部分只有28位,这就意味着UidGenerator默认只能承受8.5年(2^28-1/86400/365
),不过UidGenerator可以适当调整delta seconds、worker node id和sequence占用位数。
8、滴滴(TinyID)
由滴滴开发,开源项目链接:
Tinyid是在美团(Leaf)的leaf-segment
算法基础上升级而来,不仅支持了数据库多主节点模式,还提供了tinyid-client
客户端的接入方式,使用起来更加方便。但和美团(Leaf)不同的是,Tinyid只支持号段一种模式不支持雪花模式。Tinyid提供了两种调用方式,一种基于Tinyid-server
提供的http方式,另一种Tinyid-client
客户端方式。
总结比较
优点 | 缺点 | |
UUID | 代码实现简单、没有网络开销,性能好 | 占用空间大、无序 |
数据库自增ID | 利用数据库系统的功能实现,成本小、ID自增有序 | 并发性能受Mysql限制、强依赖DB,当DB异常时整个系统不可用,致命 |
Redis INCR | 性能优于数据库、ID有序 | 解决单点问题带来的数据一致性等问题使得复杂度提高 |
雪花算法 | 不依赖数据库等第三方系统,性能也是非高、可以根据自身业务特性分配bit位,非常灵活 | 强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。 |
号段模式 | 数据库的压力小 | 单点故障ID不连续 |
Leaf、Uidgenerator、TinyID | 高性能、高可用、接入简单 | 依赖第三方组件如ZooKeeper、Mysql |