Twitter的分布式雪花算法 SnowFlake

原创
2018/03/14 14:07
阅读数 1.2K

原理

Twitter的雪花算法SnowFlake,使用Java语言实现。

SnowFlake算法产生的ID是一个64位的整型,结构如下(每一部分用“-”符号分隔):

1位标识部分,在java中由于long的最高位是符号位,正数是0,负数是1,一般生成的ID为正数,所以为0;

41位时间戳部分,这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的ID从更小值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年;

10位节点部分,Twitter实现中使用前5位作为数据中心标识,后5位作为机器标识,可以部署1024个节点;

12位序列号部分,支持同一毫秒内同一个节点可以生成4096个ID;

SnowFlake算法生成的ID大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的ID都是唯一的。或许我们不一定都需要像上面那样使用5位作为数据中心标识,5位作为机器标识,可以根据我们业务的需要,灵活分配节点部分,如:若不需要数据中心,完全可以使用全部10位作为机器标识;若数据中心不多,也可以只使用3位作为数据中心,7位作为机器标识。

snowflake生成的ID整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和workerId作区分),并且效率较高。这个算法单机每秒内理论上最多可以生成1000*(2^12),也就是409.6万个ID。

源码

/**
 * 描述: Twitter的分布式自增ID雪花算法snowflake (Java版)
 *
 * @author jinzg
 * @create 2018-03-14 12:37
 **/
public class IdWorker {

    /**
     * 起始的时间戳
     */
    private final long twepoch = Date
      .from(LocalDate.of(2018, 1, 1).atStartOfDay()
          .atZone(ZoneId.systemDefault()).toInstant()).getTime();

    /**
     * 每一部分占用的位数
     */
    private final long sequenceBits = 12L;
    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 sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 每一部分向左的位移
     */
    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    private long workerId;// 数据中心
    private long datacenterId;// 机器标识
    private long sequence = 0L;// 序列号
    private long lastTimestamp = -1L;// 上一次时间戳

    /**
     * Init.
     */
    @PostConstruct
    public void init() {
        try {
            String ip = IpUtils.getRealIp();
            if (StringUtils.isEmpty(ip)) {
                throw new RuntimeException("IdWorker get ip is empty");
            }
            this.workerId = this.datacenterId = Math.abs(ip.hashCode() % 31);
            log.info("ip:{},workerId:{},datacenterId;{}", ip, workerId, datacenterId);
        } catch (SocketException e) {
            log.error("init error,error:{}", e);
            throw new RuntimeException("IdWorker init error");
        }
    }

    /**
     * Instantiates a new Id worker.
     */
    public IdWorker() {
        super();
    }

    /**
     * Instantiates a new Id worker.
     *
     * @param workerId     the worker id
     * @param datacenterId the datacenter id
     */
    public IdWorker(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;
    }

    /**
     * Next id long.
     *
     * @return the long
     */
    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;
    }

    /**
     * Til next millis long.
     *
     * @param lastTimestamp the last timestamp
     * @return the long
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * Time gen long.
     *
     * @return the long
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     * test
     */
    static class IdWorkThread implements Runnable {
        private Set<Long> set;
        private IdWorker idWorker;

        /**
         * Instantiates a new Id work thread.
         *
         * @param set      the set
         * @param idWorker the id worker
         */
        public IdWorkThread(Set<Long> set, IdWorker idWorker) {
            this.set = set;
            this.idWorker = idWorker;
        }

        @Override
        public void run() {
            while (true) {
                long id = idWorker.nextId();
                System.out.println(Thread.currentThread().getName() + ":" + id);
                if (!set.add(id)) {
                    System.out.println("duplicate:" + id);
                }
            }
        }
    }

    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        Set<Long> set = new HashSet<Long>();
        final IdWorker idWorker1 = new IdWorker(0, 0);
        final IdWorker idWorker2 = new IdWorker(1, 0);
        Thread t1 = new Thread(new IdWorkThread(set, idWorker1));
        Thread t2 = new Thread(new IdWorkThread(set, idWorker2));
        t1.setDaemon(true);
        t2.setDaemon(true);
        t1.start();
        t2.start();
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

特点

优点:

  • 快。
  • 没有啥依赖,实现也特别简单。
  • 知道原理之后可以根据实际情况调整各各位段,方便灵活。

缺点:

  • 只能趋势递增。(有些也不叫缺点,网上有些如果绝对递增,竞争对手中午下单,第二天在下单即可大概判断该公司的订单量,危险!!!)
  • 依赖机器时间,如果发生回拨会导致可能生成id重复。
展开阅读全文
打赏
1
7 收藏
分享
打赏
0 评论
7 收藏
1
分享
返回顶部
顶部