怎么生成唯一ID？用雪花算法

最近，公司有个项目升级换代，MySQL 从一个拓展成多个。这就带来了一个问题，原本的数据表都在用自增 ID，如果继续用下去，坑会越来越大。

所以，我们用了新方案来生成 ID：雪花算法（snowflake）。

需求

在分布式数据库中，ID 要满足 3 个要求：唯一、趋势递增、数字类型。

  1. ID 必须是唯一的，不能出现重复 ID。

这是最基本的条件，可以是全局唯一，也可以业务内唯一。

  1. ID 要按照顺序逐步递增。

由于 InnoDB 的索引用的是 B+Tree 结构，所以主键要尽量是有序的，保证写入的性能。还有就是，你做排序的时候，直接用 ID 就行，快捷方便。

  1. ID 优先使用数字类型。

在数据库中，数字不用编码就能直接保存。但字符串就得先编码，这样会造成性能下降，和一些意想不到的问题。

除了这些，我们系统的订单表已经有了几十万条数据，所以还得再加一个要求：

  1. 不入侵业务，兼容原来的系统。

上面就是这次的需求，我们就按单抓药，来选一种方案吧。

常见的两种方案

在中小公司，比较流行两种生成 ID 的方案。

数据库自增 ID

自增 ID 大概是中小公司的首选，它有两个优点：

  1. 绝对递增。

每个 ID 都是唯一的，而且完全按照插入的先后顺序，1，2，3，4 一直下去。

  1. 非常简单。

在表字段后面加一个 auto_increment，就能用了。

除此之外，我们公司一直在用这个方案，大家都能接受。然而，如果继续用下去，有两个问题没法解决。

首先是，性能瓶颈。

数据库每次自增 ID 的时候，都会先找到表里最大的 ID，然后再 +1。并发量大的时候，很容易出现数据库连接超时。

更致命的是，拓展困难。

每台 MySQL 服务器都要专门去改配置文件，而且每拓展一台新机器，配置文件都得从头改一遍。

如果两三台倒还好，但要是十几台机器，想想就头疼，根本没法执行。

我们再来看看第二个方案，UUID。

UUID

UUID 能生成一串唯一的 32 位随机数，由字母和数字组成。这个方案能保证 ID 的唯一性，直接用 Java 的 UUID 类就行，简单粗暴。

但这仅仅满足了最低要求，没法用在读写频繁的场景。

首先， UUID 是字符串，而且每一个都有 32 位，这占用了更多的储存空间。

其次，UUID 是无序的。人看不懂就算了，关键是：数据库的性能会大大降低。

数据表中，ID 是主键索引，而且大家普遍用 MySQL 的 InnoDB 引擎，这就导致带了一个结果。InnoDB 为了保证索引的查询效率，在每次插入数据的时候，都会大幅修改 InnoDB 底层索引结构。

只有几千条记录的时候还好，但如果增长到几万几十万条，这就是一笔大开销，分分钟让你服务宕机。

UUID 当主键，不仅占用空间大，效率还低。所以，果断 pass。

这样看来，第三种方案，雪花算法是最合适的了。

雪花算法

雪花算法是 Twitter 公司开源的分布式 ID 算法。

理论上，这个算法每秒能生成 409.6 万个整数，完美解决了美国总统的发推问题。而且，生成出来的整数是 64 位，刚好能用 Long 类型来保存。

那么，怎么实现呢？

最简单的，就是用现成的开源代码。这里我就不多说，有兴趣的，可以直接看文档：Id生成器-Snowflake

我这儿是自己写代码，方便后面的改进。话不多说，先看代码：

import java.util.HashSet;
import java.util.Set;

public class SnowflakeIdWorkerV1 {
    /********************** Fields ***************************/
    /**
     * 开始时间截
     */
    private static final long START_STMP;

    static {
        // START_STMP是服务器第一次上线时间点, 设置后不允许修改
        START_STMP = 1596211200000L;
    }

    /**
     * 每一部分占用的位数
     */
    // 序列号占用的位数
    private final static long SEQUENCE_BITS = 12;
    // 数据中心占用的位数
    private final static long DATA_CENTER_BITS = 5;
    // 机器标识占用的位数
    private final static long MACHINE_BITS = 5;


    /**
     * 每一部分的最大值，这个移位算法，可以很快的计算出几位二进制数所能表示的最大十进制数
     */
    // 序列号最大值
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BITS);
    // 数据中心最大id
    private final static long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_BITS);
    // 机器标识最大id
    private final static long MAX_MACHINE_ID = -1L ^ (-1L << MACHINE_BITS);

    /**
     * 每一部分向左的位移
     */
    // 机器左移位数
    private final static long MACHINE_LEFT_SHIFT_BITS = SEQUENCE_BITS;
    // 数据中心左移位数
    private final static long DATA_CENTER_LEFT_SHIFT_BITS = SEQUENCE_BITS + MACHINE_BITS;
    // 时间戳左移位数
    private final static long TIMESTAMP_LEFT_SHIFT_BITS = SEQUENCE_BITS + DATA_CENTER_BITS + MACHINE_BITS;


    /**
     * 支持参数
     */
    // 数据中心
    private long dataCenterId;
    // 机器标识
    private long machineId;
    // 序列号
    private long sequence = 0L;
    // 上一次时间戳
    private long lastStamp = -1L;


    /********************** Constructors ***************************/

    public SnowflakeIdWorkerV1(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
            throw new IllegalArgumentException("dataCenterId can't be greater than MAX_DATA_CENTER_ID or less than 0");
        }
        if (machineId > MAX_MACHINE_ID || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_ID or less than 0");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }


    /********************** Methods ***************************/

    /**
     * 产生下一个ID
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        /** 获取当前时间 **/
        long currentStamp = getCurrentTime();

        /** 阻塞时间 **/
        // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (currentStamp < lastStamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastStamp - currentStamp));
        }

        // 如果是同一时间生成的，则进行自增序列号
        if (lastStamp == currentStamp) {
            // 相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            // 同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                // 阻塞到下一个毫秒，获得新的时间戳
                currentStamp = wait2NextTime();
            }
        }
        // 时间戳改变，重置序列号
        else {
            sequence = 0L;
        }

        // 上次生成ID的时间截
        lastStamp = currentStamp;

        /** 生成id **/
        // 移位并通过或运算拼到一起组成64位的ID
        // 时间戳部分
        long timestampShift = ((currentStamp - START_STMP) << TIMESTAMP_LEFT_SHIFT_BITS);
        // 数据中心部分
        long centerShift = dataCenterId << DATA_CENTER_LEFT_SHIFT_BITS;

        // 机器标识部分
        long machineShift = machineId << MACHINE_LEFT_SHIFT_BITS;
        // 序列号部分
        long sequenceShift = sequence;

        // 或逻辑，拼接id值
        long id = timestampShift | centerShift | machineShift | sequenceShift;
        return id;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @return 当前时间戳
     */
    private long wait2NextTime() {
        long timestamp = getCurrentTime();
        while (timestamp <= lastStamp) {
            timestamp = getCurrentTime();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    private long getCurrentTime() {
        return System.currentTimeMillis();
    }

}

具体怎么实现，大家可以看上面的代码注释。我这儿主要说下怎么编写测试用例。

测试

先从最简单的测试开始，我们模拟两台服务器，看看有没有出现重复id。

是这么个思路：先创建两个对象，然后循环生成 id，再把这些 id 放到 Set 里。如果有重复 id ，就抛出异常，停止运行。

    /********************** Test ***************************/
    /**
     * 测试
     */
    public static void main(String[] args) {
        SnowflakeIdWorkerV1 server1 = new SnowflakeIdWorkerV1(2, 3);
        SnowflakeIdWorkerV1 server2 = new SnowflakeIdWorkerV1(2, 4);

        Set<String> dataSet = new HashSet<String>();

        for (int i = 0; i < (1 << 12); i++) {
            checkId(dataSet, server1.nextId());
            checkId(dataSet, server2.nextId());
        }
        
        System.out.println("测试通过，没有重复，共生成 " + dataSet.size() + " 个id");
    }

    private static void checkId(Set<String> dataSet, long id) {
        System.out.println("id：" + id);
        boolean isRepeat = !dataSet.add(id + "");
        if (isRepeat) {
            throw new IllegalArgumentException("id is repeat");
        }
    }

测试没问题，来看下运行结果：

···这里是一大堆id，直接忽略

测试通过，没有重复，共生成 8192 个id

可以说，至今为止，代码都是正常的。但事情哪有这么简单？

在正式环境上，肯定是几千个请求同时过来，这个测试根本没考虑到这些问题。

那好，我们再升级一下测试，来模拟正式环境的请求。

还是上面的那个思路，但在循环生成 id 环节升级，加上多线程。看看还能不能通过升级版测试。

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;

public class ConcurrentTesting {
    // 请求总个数
    private static final int requestTotal = (1 << 12);

    // 同一时刻，最大并发线程数
    private static final int concurrentThreadNum = (1 << 12);

    // id结果集
    private static Set<String> dataSet = new HashSet<>();
    private final SnowflakeIdWorkerV1 server1 = new SnowflakeIdWorkerV1(2, 3);
    private final SnowflakeIdWorkerV1 server2 = new SnowflakeIdWorkerV1(2, 4);

    /**
     * 并发执行，模拟正式环节的Http请求
     */
    @Test
    public void runConcurrent() throws InterruptedException {
        ExecutorService executorService = Executors.newCachedThreadPool();
        CountDownLatch countDownLatch = new CountDownLatch(requestTotal);
        Semaphore semaphore = new Semaphore(concurrentThreadNum);
        for (int i = 0; i < requestTotal; i++) {
            executorService.execute(() -> {
                try {
                    semaphore.acquire();

                    // todo 执行业务
                    generateId();

                    semaphore.release();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        executorService.shutdown();

        System.out.println("测试通过，没有重复，共生成 " + dataSet.size() + " 个id");
    }


    private void generateId() {
        checkId(dataSet, server1.nextId());
        checkId(dataSet, server2.nextId());
    }

    private static void checkId(Set<String> data, long id) {
        System.out.println("id：" + id);
        boolean isRepeat = !data.add(id + "");
        if (isRepeat) {
            throw new IllegalArgumentException("id is repeat");
        }
    }
}

这次的测试也通过了，来看下运行结果：

···还是一大堆id，直接忽略

测试通过，没有重复，共生成 8192 个id

看到这儿，我们可以说，雪花算法是靠谱的。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,126评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,254评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,445评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,185评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,178评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,970评论 1赞 284
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,276评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,927评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,400评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,646评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,213评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2赞 345