Snowflake算法生成分布式系统唯一ID
在复杂的系统中唯一ID是我们在设计的时候常常会遇见的问题,生成ID的方法有很多,适应不同的场景、需求以及性能要求。所以有些比较复杂的系统会有多个ID生成的策略,下面就介绍一些常见的ID生成策略。
1. 数据库自增长序列或字段
最常见的方式。利用数据库,全数据库唯一。
优点:
- 简单,代码方便,性能可以接受。
- 数字ID天然排序,对分页或者需要排序的结果很有帮助。
缺点:
- 不同数据库语法和实现不同,数据库迁移的时候或多数据库版本支持的时候需要处理。
- 在单个数据库或读写分离或一主多从的情况下,只有一个主库可以生成。有单点故障的风险。
- 在性能达不到要求的情况下,比较难于扩展。
- 如果遇见多个系统需要合并或者涉及到数据迁移会相当痛苦。
优化方案:
- 针对主库单点,如果有多个Master库,则每个Master库设置的起始数字不一样,步长一样,可以是Master的个数。比如:Master1 生成的是 1,4,7,10,Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12。这样就可以有效生成集群中的唯一ID,也可以大大降低ID生成数据库操作的负载。
2. UUID
UUID(Universally Unique Identifier)的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,示例:550e8400-e29b-41d4-a716-446655440000,到目前为止业界一共有5种方式生成UUID。
优点:
- 简单,代码方便。
- 生成ID性能非常好,基本不会有性能问题,本地生成,没有网络消耗。
- 全球唯一,在遇见数据迁移,系统数据合并,或者数据库变更等情况下,可以从容应对。
缺点:
- 不易于存储,UUID太长,16字节128位,通常以36长度的字符串表示,很多场景不适用。MySQL官方有明确的建议主键要尽量越短越好
- 信息不安全:基于MAC地址生成UUID的算法可能会造成MAC地址泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
- 生成ID无序对MySQL索引不利:如果作为数据库主键,在InnoDB引擎下,UUID的无序性可能会引起数据位置频繁变动,严重影响性能。
3. snowflake方案
大致来说是一种以划分命名空间(UUID也算,由于比较常见,所以单独分析)来生成ID的一种算法,这种方案把64-bit分别划分成多段,分开来标示机器、时间等,比如在snowflake中的64-bit分别表示如下图所示:
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
- 1bit 表示符号位,表示是正数还是负数,设为正数固定为0
- 41bit 的时间戳 可以表示( 1L<<41 ) / ( 1000L 3600 24 *365 )=69年的时间。
- 10bit机器可以分别表示1024台机器。如果我们对IDC划分有需求,还可以将10bit分5bit给IDC,分5bit给工作机器。这样就可以表示32个IDC,每个IDC下可以有32台机器,可以根据自身需求定义。
- 12bit可以表示的最大正整数是2^12-1=4095,即可以用0、1、2、3、....4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号,这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。
优点:
- 毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。
- 不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。
- 可以根据自身业务特性分配bit位,非常灵活。
缺点:
- 强依赖机器时钟,在单机上是递增的,但是由于涉及到分布式环境,每台机器上的时钟不可能完全同步,还有闰秒的存在,会导致重复或者服务会处于不可用状态。
附上相关的代码:
package com.dm.tool.util;
/**
* 通过 snowFlake 雪花算法生成唯一且在时间段内趋势递增的
* 分布式ID
* @author Nick
* @projectName dm-mt
* @package com.dm.tool.util
* @createDate 2019/01/17 09:17
* @updateDate 2019/01/17 09:17
*/
public class SnowFlake{
private static volatile SnowFlake instance ;
/**
* 起始的时间戳
* 从 2019/01/01 00:00:00 开始
*/
private final static long START_STMP = 1546272000000L;
/**
* 序列号占用的位数
*/
private final static long SEQUENCE_BIT = 12;
/**
* 机器标识占用的位数
*/
private final static long MACHINE_BIT = 5;
/**
* 数据中心占用的位数
*/
private final static long DATACENTER_BIT = 5;
/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
/**
* 数据中心
*/
private long datacenterId;
/**
* 机器标识
*/
private long machineId;
/**
* 序列号
*/
private long sequence = 0L;
/**
* 上一次时间戳
*/
private long lastStmp = -1L;
/**
*
* @param datacenterId 数据中心ID (0~31)
* @param machineId workerId 工作ID (0~31)
*/
private SnowFlake(long datacenterId, long machineId) {
if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenterId can't be greater than %d or less than 0",MAX_DATACENTER_NUM));
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException(String.format("machineId can't be greater than %d or less than 0",MAX_MACHINE_NUM));
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}
public static SnowFlake getInstance(long datacenterId, long machineId){
if (instance == null){
synchronized (SnowFlake.class){
if (instance == null){
instance = new SnowFlake(datacenterId,machineId);
}
}
}
return instance;
}
/**
* 产生下一个ID
*
* @return
*/
protected synchronized long nextId() {
long currStmp = getNewTimestamp();
if (currStmp < lastStmp) {
String msg = String.format("Clock moved backwards. Refusing to generate id! currStmp=%d,lastStmp=%d",currStmp,lastStmp);
throw new RuntimeException(msg);
}
if (currStmp == lastStmp) {
// 相同毫秒内,序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
// 同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
// 不同毫秒内,序列号置为0
sequence = 0L;
}
lastStmp = currStmp;
// 时间戳 41 数据中心 5 机器标识 5 序列号 12
return (currStmp - START_STMP) << TIMESTMP_LEFT
| datacenterId << DATACENTER_LEFT
| machineId << MACHINE_LEFT
| sequence;
}
private long getNextMill() {
long mill = getNewTimestamp();
while (mill <= lastStmp) {
mill = getNewTimestamp();
}
return mill;
}
private long getNewTimestamp() {
return System.currentTimeMillis();
}
public static long getSequenceBit() {
return SEQUENCE_BIT;
}
public static long getMachineBit() {
return MACHINE_BIT;
}
public static long getDatacenterBit() {
return DATACENTER_BIT;
}
public static long getStartStmp() {
return START_STMP;
}
}
工具类如下:
package com.dm.tool.util;
import org.apache.commons.lang.StringUtils;
import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;
/**
*
* snowFlake工具类
*
* @author Nick
* @projectName dm-mt
* @package com.dm.tool.util
* @createDate 2019/01/16 09:30
* @updateDate 2019/01/16 09:30
*/
public class SnowFlakeIDUtil {
private static final int radix = 2;
/**
* 数据中心ID 0,机器ID 0
* @param datacenterId
* @param machineId
* @return
*/
public static long getNextId(long datacenterId, long machineId){
return SnowFlake.getInstance(datacenterId,machineId).nextId();
}
/**
* 获得订单ID生成时的时间戳
* @param id
* @return
*/
public static long getIDTimestamp(long id){
return (id >> SnowFlake.getTimestmpLeft() & ~(-1L << 41))+SnowFlake.getStartStmp();
}
/**
* 获取数据中心 ID
* @param id
* @return
*/
public static long getDatacenterId(long id){
return id >> SnowFlake.getDatacenterLeft() & ~(-1L << SnowFlake.getDatacenterBit());
}
/**
* 获得机器ID
* @param id
* @return
*/
public static long getMachineId(long id){
return id >> SnowFlake.getMachineLeft() & ~(-1L << SnowFlake.getMachineBit());
}
/**
* 获取序列ID
* @param id
* @return
*/
public static long getSequence(long id){
return id & ~(-1L << SnowFlake.getSequenceBit());
}
public static void main(String[] args){
MyThread thread1 = new MyThread();
MyThread thread2 = new MyThread();
MyThread thread3 = new MyThread();
MyThread thread4 = new MyThread();
thread1.start();
thread2.start();
thread3.start();
thread4.start();
}
static class MyThread extends Thread{
@Override
public void run() {
while (true){
long id = SnowFlakeIDUtil.getNextId(0,0);
System.out.println("ID="+id+"时间戳= "+getIDTimestamp(id)+" DatacenterId= "+getDatacenterId(id)+" MachineId="+getMachineId(id)+" Sequence="+getSequence(id));
}
}
}
}
最后更新于 2019-01-21 10:01:04 并被添加「java snowflake」标签,已有 71 位童鞋阅读过。
本站使用「署名 4.0 国际」创作共享协议,可自由转载、引用,但需署名作者且注明文章出处,且在文章页面明显位置给出原文连接
此处评论已关闭