Anarkh的知识库

Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。这种就是将64位划分为不同的段，每段代表不同的涵义，基本就是时间戳、机器ID和序列数。为什么如此重要？因为它提供了一种ID生成及生成的思路，当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer的缓冲设计提高性能。@anarkh

雪花算法-Snowflake

Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。而 Java中64bit的整数是Long类型，所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

第1位 占用1bit，其值始终是0，可看做是符号位不使用。
第2位 开始的41位是时间戳，41-bit位可表示2^41个数，每个数代表毫秒，那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间。
中间的10-bit位 可表示机器数，即2^10 = 1024台机器，但是一般情况下我们不会部署这么台机器。如果我们对IDC（互联网数据中心）有需求，还可以将 10-bit 分 5-bit 给 IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，具体的划分可以根据自身需求定义。
最后12-bit位 是自增序列，可表示2^12 = 4096个数。

这样的划分之后相当于在一毫秒一个数据中心的一台机器上可产生4096个有序的不重复的ID 。但是我们 IDC 和机器数肯定不止一个，所以毫秒内能生成的有序ID数是翻倍的。

Snowflake 的Twitter官方原版是用Scala写的，对Scala语言有研究的同学可以去阅读下，以下是 Java 版本的写法。

java

package com.jajian.demo.distribute;


public class SnowflakeDistributeId {


    
    
    private final long twepoch = 1420041600000L;

    
    private final long workerIdBits = 5L;

    
    private final long datacenterIdBits = 5L;

    
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    
    private final long sequenceBits = 12L;

    
    private final long workerIdShift = sequenceBits;

    
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    
    private long workerId;

    
    private long datacenterId;

    
    private long sequence = 0L;

    
    private long lastTimestamp = -1L;

    

    
    public SnowflakeDistributeId(long workerId, long datacenterId) {
        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;
    }

    

    
    public synchronized long nextId() {
        long timestamp = timeGen();

        
        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;
        }

        
        lastTimestamp = timestamp;

        
        return ((timestamp - twepoch) << timestampLeftShift) 
                | (datacenterId << datacenterIdShift) 
                | (workerId << workerIdShift) 
                | sequence;
    }

    
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp &lt;= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

测试的代码如下

java

public static void main(String[] args) {
    SnowflakeDistributeId idWorker = new SnowflakeDistributeId(0, 0);
    for (int i = 0; i < 1000; i++) {
        long id = idWorker.nextId();

        System.out.println(id);
    }
}

雪花算法提供了一个很好的设计思想，雪花算法生成的ID是趋势递增，不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的，而且可以根据自身业务特性分配bit位，非常灵活。

但是雪花算法强依赖机器时钟 ，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID，而时间回退后，生成的ID就有可能重复。官方对于此并没有给出解决方案，而是简单的抛错处理，这样会造成在时间被追回之前的这段时间服务不可用。

很多其他类雪花算法也是在此思想上的设计然后改进规避它的缺陷，后面介绍的百度 UidGenerator 和 美团分布式ID生成系统 Leaf 中snowflake模式都是在 snowflake 的基础上演进出来的。

其它相关算法

在如下文章中已经包含了所有主流的全局唯一ID实现方案：

分布式系统 - 全局唯一ID实现方案

这里给出相关的链接：

雪花算法-Snowflake ​

其它相关算法 ​

雪花算法-Snowflake

其它相关算法