分布式全局ID生成器（雪花算法）

2018-06-18 02:13:58来源：未知阅读 ()

111111111111111111111111111111111111111111111111111111111111111
全局唯一ID生成服务 Twitter的分布式自增ID算法snowflake (Java版)

snowflake的结构如下(每部分用-分开):
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点），最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）
一共加起来刚好64位，为一个Long型。(转换成字符串后长度最多19)
snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。经测试snowflake每秒能够产生26万个ID

保证每个机器的workerId和datacenterId不同，比如你有3台服务器，那么这3台服务器的配置分别设置为0,1,2 就行了
需要指定数据中心标识ID和机器进程标识ID

问题：
系统时钟回退

解决：
记录 lasttime 并入库，回退期间使用12位序列自增的方式生成id，序列满后，lasttime 自增（计入内存并入库）且序列归0，开始下一轮的序列自增
数据库压力：
（因为单个应用是线程安全的同步操作不会出现并发）多应用同时出现时钟回退且大量并发请求会有大量的入库操作，
1，减少机器节点位数（workerId、datacenterId）增加序列节点到14位，序列可达到16000，减少lasttime的入库频率，
2，出现时钟回退报警

10110001000111101000111001111011101111100 当前毫秒数 1970.1.1
1011110011100000010011011101101111100 减去20150101后的毫秒数
10111100111000000100110111011011111001111100001000000000000

2的62次方 4611686018427387904 100000000000000000000000000000000000000000000000000000000000000 63位
2的63次方-9223372036854775808 111111111111111111111111111111111111111111111111111111111111111 63位减1 9223372036854775807

二进制11能标示4个数，但它是从0开始的，所以二进制11代表的是十进制的3，就是2的2次方减1
111111111111111111111111111111111111111111111111111111111111111，能表示9223372036854775808个数，对应十进制（减1）9223372036854775807，是Long的最大值
为什么2的63次方是负数：

最大值：Long.MAX_VALUE=9223372036854775807 （2的63次方-1）
最小值：Long.MIN_VALUE=-9223372036854775808 （-2的63次方）
数据用原码表示：
0：00000000,00000000,00000000,00000000
8：00000000,00000000,00000000,00001000
Java没有无符号整数，如果想表示负数呢？
可以让第一个数字代表符号位，0是正数，1是负数，
表示的范围是-2^16+1~-0和+0~2^16-1。
这导致了有+0和-0两种0。
+8：00000000,00000000,00000000,00001000
-8：10000000,00000000,00000000,00001000
+0：00000000,00000000,00000000,00000000
-0：10000000,00000000,00000000,00000000

^ 异或运算
& 按位与,转化为二进制数两侧的值都为真，结果才为真（二进制11111的十进制为31 11&31结果还未11，只要比31小，与的结果还为其本身）
31&0 31&32 64 96 128 都为0
| 或运算，一个为真就为真（一个为1就为1），111（7）|110000（48）得110111（十进制55）
如果第一个条件为true，会接着判断第二个条件，和||不同

UUID 组成：
UUID保证对在同一时空中的所有机器都是唯一的。通常平台会提供生成的API。按照开放软件基金会(OSF)制定的标准计算，用到了以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字
UUID由以下几部分的组合：
（1）当前日期和时间，UUID的第一个部分与时间有关，如果你在生成一个UUID之后，过几秒又生成一个UUID，则第一个部分不同，其余相同。
（2）时钟序列。
（3）全局唯一的IEEE机器识别号，如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获得。
UUID的唯一缺陷在于生成的结果串会比较长。关于UUID这个标准使用最普遍的是微软的GUID(Globals Unique Identifiers)。在ColdFusion中可以用CreateUUID()函数很简单地生成UUID。

  1 package cn.com.gome.cashier.dynamic.test;
  2  
  3 /**
  4 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
  5 第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点） ，最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）
  6 一共加起来刚好64位，为一个Long型。(转换成字符串后长度最多19)
  7 https://www.cnblogs.com/relucent/p/4955340.html  http://www.wolfbe.com/detail/201611/381.html
  8  */
  9 public class SnowflakeIdWorker2 {
 10     //得到二进制样例 10111100110111110011001010100001100111111100001000000000000
 11     /** 开始时间截 (2015-01-01) */
 12     private final long twepoch = 1420041600000L;
 13  
 14     //每一部分占用的位数
 15     /** 机器id所占的位数 */
 16     private final long workerIdBits = 5L;
 17     /** 数据标识id所占的位数 */
 18     private final long datacenterIdBits = 5L;
 19     /** 序列在id中占的位数 */
 20     private final long sequenceBits = 12L;
 21  
 22     //每一部分的最大值
 23     /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
 24     private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 25     /** 支持的最大数据标识id，结果是31 */
 26     private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 27     /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
 28     private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 29  
 30     //每一部分向左的位移
 31     /** 机器ID向左移12位 */
 32     private final long workerIdShift = sequenceBits;
 33     /** 数据标识id向左移17位(12+5) */
 34     private final long datacenterIdShift = sequenceBits + workerIdBits;
 35     /** 时间截向左移22位(5+5+12) */
 36     private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 37  
 38     
 39  
 40     /** 工作机器ID(0~31) */
 41     private long workerId;
 42     /** 数据中心ID(0~31) */
 43     private long datacenterId;
 44     /** 毫秒内序列(0~4095) */
 45     private long sequence = 0L;
 46     /** 上次生成ID的时间截 */
 47     private long lastTimestamp = -1L;
 48  
 49     //==============================Constructors=====================================
 50     /**
 51      * 构造函数
 52      * @param workerId 工作ID (0~31)
 53      * @param datacenterId 数据中心ID (0~31)
 54      */
 55     public SnowflakeIdWorker2(long workerId, long datacenterId) {
 56         if (workerId > maxWorkerId || workerId < 0) {
 57             throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
 58         }
 59         if (datacenterId > maxDatacenterId || datacenterId < 0) {
 60             throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
 61         }
 62         this.workerId = workerId;
 63         this.datacenterId = datacenterId;
 64     }
 65  
 66     // ==============================Methods==========================================
 67     /**
 68      * 获得下一个ID (该方法是线程安全的)
 69      * @return SnowflakeId
 70      */
 71     public synchronized long nextId() {
 72         long timestamp = timeGen();
 73  
 74         //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
 75         if (timestamp < lastTimestamp) {
 76             throw new RuntimeException(
 77                     String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
 78         }
 79  
 80         //如果是同一时间生成的，则进行毫秒内序列
 81         if (lastTimestamp == timestamp) {
 82             sequence = (sequence + 1) & sequenceMask;//相同毫秒内，序列号自增
 83             //毫秒内序列溢出 //同一毫秒的序列数已经达到最大
 84             if (sequence == 0) {
 85                 //阻塞到下一个毫秒,获得新的时间戳
 86                 timestamp = tilNextMillis(lastTimestamp);
 87             }
 88         }
 89         //时间戳改变，毫秒内序列重置
 90         else {
 91             sequence = 0L;
 92         }
 93  
 94         //上次生成ID的时间截
 95         lastTimestamp = timestamp;
 96  
 97         System.out.println("timestamp: "+timestamp+","+(timestamp - twepoch));
 98         //移位并通过或运算拼到一起组成64位的ID，类似于相加的方式,当前时间减去2015-01-01，41bit的时间戳可以支持该算法使用年限：69年
 99         return ((timestamp - twepoch) << timestampLeftShift) //
100                 | (datacenterId << datacenterIdShift) //
101                 | (workerId << workerIdShift) //
102                 | sequence;
103     }
104  
105     /**
106      * 阻塞到下一个毫秒，直到获得新的时间戳
107      * @param lastTimestamp 上次生成ID的时间截
108      * @return 当前时间戳
109      */
110     protected long tilNextMillis(long lastTimestamp) {
111         long timestamp = timeGen();
112         while (timestamp <= lastTimestamp) {
113             timestamp = timeGen();
114         }
115         return timestamp;
116     }
117  
118     /**
119      * 返回以毫秒为单位的当前时间
120      * @return 当前时间(毫秒)
121      */
122     protected long timeGen() {
123         return System.currentTimeMillis();
124     }
125  
126     //==============================Test=============================================
127     /** 测试 */
128     public static void main(String[] args) {
129         SnowflakeIdWorker2 idWorker = new SnowflakeIdWorker2(1, 31);
130         for (int i = 0; i < 10; i++) {
131             long id = idWorker.nextId();
132             System.out.println(Long.toBinaryString(id)+" "+id);
133         }
134     }
135 }