Twitter Snowflake 唯一ID生成算法

分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求。如在分布式环境, workerId可以使用redis分布式锁来保证唯一。

Snowflake算法核心:

把时间戳,工作机器id,序列号组合在一起。

除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。

示例:

package com.dream7788.cloud.utils;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Twitter Snowflake 唯一ID生成算法
 * <p>
 * <p>对系统时间的依赖性非常强,当检测到ntp时间调整后,将会拒绝分配id。</p>
 *
 * <p>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
 * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
 * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位,为一个Long型。<br>
 * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
 * </p>
 */
public class IdWorker {

    private static final Logger log = LoggerFactory.getLogger(IdWorker.class);

    private long workerId;    //节点 ID
    private long datacenterId;    //数据中心ID
    private long sequence = 0L;    //序列编号

    private long twepoch = 1420041600000L;    //时间戳,2015年1月1日 0:00:00

    private long workerIdBits = 5L;    //节点标识位数
    private long datacenterIdBits = 5L;    //数据中心标识位数
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);    //节点ID最大值
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);    //数据中心ID最大值
    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) {
        // 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));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
        log.info(String.format("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId));
    }

    /**
     * 生成唯一ID
     *
     * @return ID
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            log.error(String.format("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) {    // 如果上一个timestamp与新产生的相等,则sequence加一(0-4095循环); 对新的timestamp,sequence从0开始
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);    // 重新生成timestamp
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

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

    /**
     * 等待下一个毫秒的到来, 保证返回的毫秒数在参数lastTimestamp之后
     *
     * @param lastTimestamp 最新的时间戳
     * @return 时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 获得系统当前时间,单位毫秒
     *
     * @return 当前时间
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

//    public static void main(String[] args) {
//        IdWorker idWorker = new IdWorker(1, 1);
//        System.out.println(idWorker.nextId());
//    }
}

未经允许不得转载:君子如兰 » Twitter Snowflake 唯一ID生成算法

赞 (0) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏