snowflake

偶然接触到这个算法，拜读过他人的文章，写写自己学习后的理解。

算法由来
算法是 twitter 的工程师设计并开发的，主要是在分布式环境中生产纯数字的序列号，不需要其他中间件，以及网络通信或者数据库的支持。

原理
算法生成的是 64 位的数字，主要分成 4 个部分：自增序列 12 位 ；机器号 5 位；数据中心号 5 位；以及由本次生成序列号当前时间减去起始时间（可配置）作为 41 位时间戳时间，最后剩下的一位是符号位 不用 默认是 0；

用二进制可表示为如下：

0-0000000000000000000000000000000000000000-00000-00000-000000000000

时间戳差值 datacenterid workid sequence

时间戳差值: 本次生成序列号时间减去程序设置的起始运行时间差值，理论上 41 位最大为-1^(-1<<41)=2199023255551(ms)  换算成年也就是 69 年

workid:工作机器号 5 位 。与数据中心号配合使用，最多可以有 1024 台服务器同时运行

dataceterid: 数据中心 5 位

sequence: 自增序列 12 位，区别同毫秒内产生的序列号。也就是理论上每秒可以产生-1^(-1<<12) * 1000 =4095999 个，可见其效率多高。

java 版代码

public class IdWorker {
/**
 * 机器号
 */
private long workerId;
/**
 * 数据中心号
 */
private long datacenterId;
/**
 * 同毫秒内自增序列号
 */
private long sequence;
/**
 * 程序序列号 第一次生成时间 可以自己配置
 */
private long twepoch = 1288834974657L;
/**
 * 机器号 5 位
 */
private long workerIdBits = 5L;
/**
 * 数据中心号 5 位
 */
private long datacenterIdBits = 5L;
/**
 * 最大机器号
 */
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
/**
 * 最大数据中心号
 */
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 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));
    }
    System.out.printf(
            "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
            timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

    this.workerId = workerId;
    this.datacenterId = datacenterId;
    this.sequence = sequence;
}


public long getWorkerId() {
    return workerId;
}

public long getDatacenterId() {
    return datacenterId;
}

public long getTimestamp() {
    return System.currentTimeMillis();
}

public synchronized long nextId() {
    /**获取当前时间*/
    long timestamp = timeGen();
    /**检查时间是否倒退*/
    if (timestamp < lastTimestamp) {
        System.err.printf("clock is moving backwards.  Rejecting requests until %d.", 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 = 0;
    }
    //更新上次生成时间
    lastTimestamp = timestamp;
    //          将 4 部分合在一起
    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();
}