分布式系统ID--雪花算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了分布式系统ID--雪花算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4033字，纯文字阅读大概需要6分钟。

内容图文

前言

在实际的应用中，我们经常会遇到id生成问题。其中最基本的就是要保证id的唯一性。常见解决方案如下。

1. 微软公司通用唯一识别码（UUID）
2. Twitter公司雪花算法（SnowFlake）
3. 基于数据库的id自增

其中，使用数据库进行id自增是在单机应用中使用最普遍的id生成方式，它能够完全保证id的不重复。但id的自增并不是在任何数据库都支持，这就给数据库迁移造成了麻烦。并且，数据库的解决方案在分布式环境下的只能保证单个数据库作为生产数据库，存在单点故障的危险。

而微软的UUID显然是一种极佳的解决方案，它由当前日期时间、时钟序列、全局唯一的机器标识号来生成一段无序的字符串id。 它的确实现了ID的唯一性但肉眼可辨识度比较差。虽然满足了我们的基本要求，但实际很多的生产中我们还有id根据时间进行递增的进阶要求。这显然是无法实现的。

所以，下面我们就讲讲Twitter公司的雪花算法是如何进行id生成的。

雪花的结构

首先，我们从它的设计入手，自己想一下，如果让我们设计一个id，如何保证既能唯一又能按照时间递增？

首先，既然要按照时间递增，那么这个id一定是个数，而不是字符串。并且在id中时间要作为第一影响因素，越晚生成的id，数字越大。那么整个数字id的前几位一定是时间戳。这就实现了按照时间递增。

那么同时间的并发生成如何保证唯一性呢？我们还会想到在分布式情况下要在多台机器上生成id，那么直接再加上这台机器的id就好了。

Ok，继续思考，时间相同，在同一台机器上生成的多个id如何保证唯一性，这时候就会想，也许可以再在后面加一串随机数或者序列之类的。

想到这，就有了下面的雪花算法的结构图。

可以看出，雪花算法生成的id既保证了唯一性，又因为是long存储，所以能够按照时间进行排序。至于69年的限制可以忽略不计。

/**
 * 雪花算法--分布式系统ID
 * @author huzhiyong
 *
 */
public class IdWorker {
    private long workerId;
    private long datacenterId;
    private long sequence;

    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;
    }

    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 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;
        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();
    }

    // ---------------测试---------------
    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1, 1, 1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }
}

 

内容总结

以上是互联网集市为您收集整理的分布式系统ID--雪花算法全部内容，希望文章能够帮你解决分布式系统ID--雪花算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---