首页 / 算法 / SnowFlake算法
SnowFlake算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了SnowFlake算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5674字，纯文字阅读大概需要9分钟。
内容图文
分布式id生成算法(SnowFlake算法)
分布式id生成算法的有很多种，Twitter的SnowFlake就是其中经典的一种。
概述
SnowFlake算法生成id的结果是一个64bit大小的整数，它的结构如下图：
- 1位，不用。二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0。
- 41位，用来记录时间戳（毫秒）。
- 41位可以表示241?1个数字，如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0至241?1，减1是因为可表示的数值范围是从0开始算的，而不是1。也就是说41位可以表示241?1个毫秒的值，转化成单位年则是(2^41?1)/(1000?60?60?24?365)=69年。
- 10位，用来记录工作机器id。(此处可根据需要调整datacenterId和workerIdde位数，位数和为10即可)。
- 可以部署在210=1024个节点，包括5位datacenterId(机房id)5位workerId(机器id)。
- 5位（bit）可以表示的最大正整数是25?1=31，即可以用0、1、2、3、…31这32个数字，来表示不同的datecenterId或workerId。
- 可以部署在210=1024个节点，包括5位datacenterId(机房id)5位workerId(机器id)。
- 12位，序列号，用来记录同毫秒内产生的不同id。
- 12位（bit）可以表示的最大正整数是212?1=4095，即可以用0、1、2、3、…4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号。
- 12位（bit）可以表示的最大正整数是212?1=4095，即可以用0、1、2、3、…4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号。
由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。
SnowFlake可以保证：
- 所有生成的id按时间趋势递增。
- 整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）。
Java代码实现
package com.fyj.util;
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* @author fanyongju
* @Title: IdWorker
* @Description: TODO
* @date 2018/10/1219:35
*/
public class IdWorker {
private long workerId;
private long datacenterId;
private long sequence;
public IdWorker(long workerId, long datacenterId, long sequence) {
// sanity check for workerId
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;
this.sequence = sequence;
}
private long twepoch = 1539920215000L;//初始毫秒时间戳2018-10-19 11:36:55
private long workerIdBits = 7L;//机器选择2^7=128(每个机房最多128台机器)机器id为0~127
private long datacenterIdBits = 3L;//机房选择2^3=8(最多8个机房)机房id为0~7
private long maxWorkerId = -1L ^ (-1L << workerIdBits);//^异或：两个比较的位不同时其结果是1，相同结果为0
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private long sequenceBits = 12L;
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L << sequenceBits);
private long lastTimestamp = -1L;
public long getWorkerId() {
return workerId;
}
public long getDatacenterId() {
return datacenterId;
}
public long getTimestamp() {
return System.currentTimeMillis();
}
//用同步锁保证线程安全
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;
//sequence等于0说明毫秒内序列已经增长到最大值
if (sequence == 0) {
//阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {//时间戳改变，毫秒内序列重置
sequence = 0;//这种重置可能会导致id分布不均，后期如果需要的话，建议改为0-4095之间的随机数
}
//记录上次生成ID的时间截
lastTimestamp = timestamp;
/*
移位并通过或运算拼到一起组成64位的ID，将timestamp减去指定的初始时间戳twepoch结果左移timestampLeftShift(22)位
，然后与上左移datacenterIdShift(19)的datacenterId，再与上左移workerIdShift(12)位的workerId，再与上sequence。
注意：此处转换成二进制进行操作
*/
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {//通过生成的id反解出dataCenId和workId
IdWorker idWorker = new IdWorker(39, 7, 0);
while (true) {//请手动终止
Long id = idWorker.nextId();
System.out.println("generate id is:" + id);
StringBuilder dw = new StringBuilder(Long.toBinaryString(id / 4096 % 1024));
StringBuilder time = new StringBuilder(Long.toBinaryString(id / (4096 * 1024)));
if (dw.length() < 10) {
int l = 10 - dw.length();
for (int i = 0; i < l; i++) {
dw.insert(0, "0");
}
}
String dataCenterId = dw.substring(0, 3);
String workId = dw.substring(3);
Date date = new Date((Long.parseLong(time.toString(), 2) + 1288834974657L));
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
System.out.println("time:" + sdf.format(date)
+ ", dataCenterId:" + Long.parseLong(dataCenterId, 2)
+ ", workId:" + Long.parseLong(workId, 2)
+ ", sequence:" + Long.parseLong(Long.toBinaryString(id % 4096), 2));
}
}
}
代码解释
- 获得单一机器的下一个序列号，使用Synchronized控制并发，而非CAS的方式，是因为CAS不适合并发量非常高的场景。
- 如果当前毫秒在一台机器的序列号已经增长到最大值4095，则使用while循环等待直到下一毫秒。
- 如果当前时间小于记录的上一个毫秒值，则说明这台机器的时间回拨了，抛出异常。但如果这台机器的系统时间在启动之前回拨过，那么有可能出现ID重复的危险。
SnowFlake算法的优点：
- 生成ID时不依赖于DB，完全在内存生成，高性能高可用。
- ID呈趋势递增，后续插入索引树的时候性能较好。
SnowFlake算法的缺点：
- 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成ID冲突，或者ID乱序。
内容总结
以上是互联网集市为您收集整理的SnowFlake算法全部内容，希望文章能够帮你解决SnowFlake算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】