Twitter Snowflake算法详解

一、简介

Twitter Snowflake算法是用来在分布式场景下生成唯一ID的。

举个栗子:我们有10台分布式MySql服务器,我们的系统每秒能生成10W条数据插入到这10台机器里,现在我们需要为每一条数据生成一个全局唯一的ID, 并且这些 ID 有大致的顺序。

二、算法图解

这里写图片描述
如图:最后生成的ID是一个long类型,long占64bit,符号位占1位,剩下63位,我们将这63位拆分成4段,就可以表示:某一毫秒内的某一集群内的某一机器的第几个ID。

有人会问:为什么时间戳要占41位?sequence要占12位?而其他两个要各占5位?
答:这是根据具体需求来分的,你也可以自己再去将这63为重新拆分。例如:sequence占12位就可以在同一毫秒内的同一集群的同一机器上同时有2^12 – 1 个线程。

三、快快上码

public class IdWorker {

    protected static final Logger LOG = LoggerFactory.getLogger(IdWorker.class);

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

    private long twepoch = 1288834974657L;

    private long workerIdBits = 5L;
    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) {
        // 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));
    }

    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) {
            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 <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

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

四、Q&A

问题1:twepoch 为什么要等于1288834974657L 而不等于其他数?
答: 1288834974657 是 (Thu, 04 Nov 2010 01:42:54 GMT) 这一时刻到1970-01-01 00:00:00时刻所经过的毫秒数。当前时刻减去1288834974657 的值刚好在2^41 里,因此占41位。 所以这个数是为了让时间戳占41位才特地算出来的。

问题2:类似这种long maxWorkerId = -1L ^ (-1L << workerIdBits);操作是什么意思?
答: -1L ^ (-1L << n)表示占n个bit的数字的最大值是多少。举个栗子:-1L ^ (-1L << 2)等于10进制的3 ,即二进制的11表示十进制3。

注意:计算机存放数字都是存放数字的补码,正数的原码、补码、反码都一样,负数的补码是其反码加一。符号位做取反操作时不变,做逻辑与、或、非、异或操作时要参与运算。

再来个栗子:
-1L原码 : 1000 0001
-1L反码 : 1111 1110
-1L补码 : 1111 1111
-1L<<5 : 1110 0000
1111 1111 ^ 1110 0000 : 0001 1111
0001 1111是正数,所以补码、反码、原码都一样,所以0001 1111是31

问题3:((timestamp – twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence是什么意思?
答:我只发图不说话
这里写图片描述

PS:如果您想和业内技术大牛交流的话,请加qq群(521571209)或者关注微信公众 号(AskHarries),谢谢!

转载请注明原文出处:Harries Blog™ » Twitter Snowflake算法详解

赞 (1)

分享到:更多 ()

评论 0

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