Twitter的分布式自增ID雪花算法snowflake (Java版)

 

概述

分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。

有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。

而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra，因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。

结构

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型。(转换成字符串长度为18)

snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。据说：snowflake每秒能够产生26万个ID。

1.  
   /** Snowflake */
2.  
   public class IdWorker {
3.  
    
4.  
   private final long twepoch = 1288834974657L;
5.  
   private final long workerIdBits = 5L;
6.  
   private final long datacenterIdBits = 5L;
7.  
   private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
8.  
   private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
9.  
   private final long sequenceBits = 12L;
10.  
    private final long workerIdShift = sequenceBits;
11.  
    private final long datacenterIdShift = sequenceBits + workerIdBits;
12.  
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
13.  
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
14.  
     
15.  
    private long workerId;
16.  
    private long datacenterId;
17.  
    private long sequence = 0L;
18.  
    private long lastTimestamp = -1L;
19.  
     
20.  
    public IdWorker(long workerId, long datacenterId) {
21.  
    if (workerId > maxWorkerId || workerId < 0) {
22.  
    throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
23.  
    }
24.  
    if (datacenterId > maxDatacenterId || datacenterId < 0) {
25.  
    throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
26.  
    }
27.  
    this.workerId = workerId;
28.  
    this.datacenterId = datacenterId;
29.  
    }
30.  
     
31.  
    public synchronized long nextId() {
32.  
    long timestamp = timeGen();
33.  
    if (timestamp < lastTimestamp) {
34.  
    throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
35.  
    }
36.  
    if (lastTimestamp == timestamp) {
37.  
    sequence = (sequence + 1) & sequenceMask;
38.  
    if (sequence == 0) {
39.  
    timestamp = tilNextMillis(lastTimestamp);
40.  
    }
41.  
    } else {
42.  
    sequence = 0L;
43.  
    }
44.  
     
45.  
    lastTimestamp = timestamp;
46.  
     
47.  
    return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
48.  
    }
49.  
     
50.  
    protected long tilNextMillis(long lastTimestamp) {
51.  
    long timestamp = timeGen();
52.  
    while (timestamp <= lastTimestamp) {
53.  
    timestamp = timeGen();
54.  
    }
55.  
    return timestamp;
56.  
    }
57.  
     
58.  
    protected long timeGen() {
59.  
    return System.currentTimeMillis();
60.  
    }
61.  
     
62.  
    public static void main(String[] args) {
63.  
    IdWorker idWorker = new IdWorker(0, 0);
64.  
    for (int i = 0; i < 1000; i++) {
65.  
    long id = idWorker.nextId();
66.  
    System.out.println(id);
67.  
    }
68.  
    }
69.  
    }