个人网站设计报告书,园区建设网站的方案,app 网站建设,网站产品网页设计模板雪花算法学习笔记
来源 https://pdai.tech/md/algorithm/alg-domain-id-snowflake.html概述
雪花算法是推特开源的分布式ID生成算法#xff0c;以划分命名空间的方式将64位分割成多个部分#xff0c;每一个部分代表不同的含义#xff0c;这种就是将64位划分成不同的段以划分命名空间的方式将64位分割成多个部分每一个部分代表不同的含义这种就是将64位划分成不同的段每一个段代表不同的涵义时间戳 机器ID 序列数
结构
第一位占用一个bit 值始终为0可以看作符号位不可使用第二位开始的41位是时间戳41bit可以表示2^41个数字每一个数字代表s,那么雪花算法表示的时间年限是69年时间中间的10bit将其中5bit分给IDC(互联网数据中心)5bit给工作机器这样就可以表示32个IDC然后每一个IDC有32台机器最后12bit是自增序列可以表示2^124096
这样划分相当于在一毫秒的一个数据中心的一台机器上可以产生4096个有序的不重复的ID package SnowFlake;/*** Twitter_Snowflakebr* SnowFlake的结构如下(每部分用-分开):br* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 br* 1位标识由于long基本类型在Java中是带符号的最高位是符号位正数是0负数是1所以id一般是正数最高位是0br* 41位时间截(毫秒级)注意41位时间截不是存储当前时间的时间截而是存储时间截的差值当前时间截 - 开始时间截)* 得到的值这里的的开始时间截一般是我们的id生成器开始使用的时间由我们程序来指定的如下下面程序IdWorker类的startTime属性。41位的时间截可以使用69年年T (1L 41) / (1000L * 60 * 60 * 24 * 365) 69br* 10位的数据机器位可以部署在1024个节点包括5位datacenterId和5位workerIdbr* 12位序列毫秒内的计数12位的计数顺序号支持每个节点每毫秒(同一机器同一时间截)产生4096个ID序号br* 加起来刚好64位为一个Long型。br* SnowFlake的优点是整体上按照时间自增排序并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)并且效率较高经测试SnowFlake每秒能够产生26万ID左右。*/
public class SnowflakeDistributeId {// Fields/*** 开始时间截 (2015-01-01)*/private final long twepoch 1420041600000L;/*** 机器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位(125)*/private final long datacenterIdShift sequenceBits workerIdBits;/*** 时间截向左移22位(5512)*/private final long timestampLeftShift sequenceBits workerIdBits datacenterIdBits;/*** 生成序列的掩码这里为4095 (0b1111111111110xfff4095)*/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/*** 构造函数** param workerId 工作ID (0~31)* param datacenterId 数据中心ID (0~31)*/public SnowflakeDistributeId(long workerId, long datacenterId) {if (workerId maxWorkerId || workerId 0) {throw new IllegalArgumentException(String.format(worker Id cant be greater than %d or less than 0, maxWorkerId));}if (datacenterId maxDatacenterId || datacenterId 0) {throw new IllegalArgumentException(String.format(datacenter Id cant 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位的IDreturn ((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是趋势递增不依赖数据库等第三方系统依赖机器始终如果机器时钟回拨会导致发号重复或者服务处于不可用状态如果恰巧回退前生成过一些ID,但是时间回退之后生成的ID就有可能重复
