Twitter服务器用户ID生成算法--snowflake

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。
其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后，第一个符号位 (+、-)，永远是0。

snowflake ID组成公式：

snowflake ID(64bit) = 符号位(1) + 毫秒位(41) + 数据中心ID位(5) + ID生成器位(5) + 毫秒内序号(12)

具体实现的代码可以参看: https://github.com/twitter/snowflake
Github上源码中不仅这一个类，如snowflakeServer，但是引用了twitter自己的类库，所以仅对生成ID的类（IdWorker）进行翻译。
ps: 这个项目暂时性停止，目测不会再更新，官方正在开发下一版本（说是不再依赖twitter的基础设施，任何环境下都能跑），但是其代码任然可以下载（scala语言，类似Java）
下面是JAVA版ID生成器：

/**
 * An object that generates IDs.
 * This is broken into a separate class in case
 * we ever want to support multiple worker threads
 * per process
 */
public class IdWorker {

    private long workerId;
    private long datacenterId;
    private long sequence = 0L;

    private static long twepoch = 1288834974657L;

    private static long workerIdBits = 5L;
    private static long datacenterIdBits = 5L;
    private static long maxWorkerId = -1L ^ (-1L << (int) workerIdBits);
    private static long maxDatacenterId = -1L ^ (-1L << (int) datacenterIdBits);
    private static long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << (int) sequenceBits);

    private static long lastTimestamp = -1L;

    public IdWorker(long workerId, long datacenterId){
        // sanity check for workerId
        if (workerId > maxWorkerId || workerId < 0) {
            throw new ControllerException(500, "worker Id can't be greater than %d or less than 0");
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new ControllerException(500, "datacenter Id can't be greater than %d or less than 0");
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

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

        if (timestamp < lastTimestamp){
            throw new ControllerException(500, "Clock moved backwards.  Refusing to generate id for %d milliseconds");
        }
        if (timestamp == lastTimestamp){
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0){
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

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

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

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

    public long getWorkerId(){
        return workerId;
    }
    public long getDatacenterId(){
        return datacenterId;
    }
}

Contact:

• 作者 : Jason
• Email : [e-mail]
• 版权归作者所有，未经允许禁止转载