概述

网上关于分布式id生成器的文章已经很多了，本文章主要是想介绍下之前设计和开发的两种分布式id生成器。具体背景和其他生成器的优劣不会着重介绍。先简单说下分布式id的需求（载自新美大Leaf方案技术博客，下面会附上链接）：

1.全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。

2.趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能（避免索引页分裂导致的性能问题）。

3.单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。

4.信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

笔者当时接到的需求是订单id和凭证id的生成。凭证id分为两部分：六位取票码和六位验证码（都是字母和数字的结合）。关于其他方案的调研请参考新美大Leaf系统的技术博客，写的比我好。先说下订单id生成器方案，订单id生成器是基于snowflake改造的。

基于snowflake的分布式id生成器

说到分布式id生成器方案，首先大方向上会首先考虑是搞成一个服务还是一个SDK。考虑到如下原因，选择了SDK的方案：

SDK的设计和开发复杂度要低很多，产品都是慢慢迭代的，先搞一版能满足短期内需求的方案。
SDK完全内存生成，没有网络开销，也没有网络调用带来的不稳定性。

再介绍下snowflake。

Snowflake ID有64bits长，由以下三部分组成：

1.第一位为0，不用。

2.timestamp—41bits,精确到ms，那就意味着其可以表示长达(2^41-1)/(1000360024*365)=139.5年，另外使用者可以自己定义一个开始纪元（epoch)，然后用(当前时间-开始纪元）算出time，这表示在time这个部分在140年的时间里是不会重复的，官方文档在这里写成了41bits，应该是写错了。另外，这里用time还有一个很重要的原因，就是可以直接更具time进行排序，对于twitter这种更新频繁的应用，时间排序就显得尤为重要了。

3.machine id—10bits,该部分其实由datacenterId和workerId两部分组成，这两部分是在配置文件中指明的。

datacenterId，方便搭建多个生成uid的service，并保证uid不重复，比如在datacenter0将机器0，1，2组成了一个生成uid的service，而datacenter1此时也需要一个生成uid的service，从本中心获取uid显然是最快最方便的，那么它可以在自己中心搭建，只要保证datacenterId唯一。如果没有datacenterId，即用10bits，那么在搭建一个新的service前必须知道目前已经在用的id，否则不能保证生成的id唯一，比如搭建的两个uid service中都有machine id为100的机器，如果其server时间相同，那么产生相同id的情况不可避免。
workerId是实际server机器的代号，最大到32，同一个datacenter下的workerId是不能重复的。它会被注册到consul上，确保workerId未被其他机器占用，并将host:port值存入，注册成功后就可以对外提供服务了。

4.sequence id —12bits,该id可以表示4096个数字，它是在time相同的情况下，递增该值直到为0，即一个循环结束，此时便只能等到下一个ms到来，一般情况下4096/ms的请求是不太可能出现的，所以足够使用了。

其中考虑点主要是第三部分和第四部分的设计。

第三部分在实践中并没有考虑datacenterId，只需要生成6bit的workId就行（业务规模并没有那么大,63台机器是考虑了三年业务增长量）。workId的生成需要业务方建立一张辅助表t。主要字段：id（unsigned），server_ip。id是数据库的自增id，会用作workId。server_ip是相应work的ip。业务方需要事先建好表t，并初始化63条空数据。当业务方项目启动时需要抢占id。循环执行如下sql：

update table t set server_ip = ip where id=id and server_ip is NULL;

抢占成功id就是当前机器的workid。失败时也就是需要更进技术方案的时候了。

当业务方某台机器停服时会把相应数据行的server_ip更新成null。

第四部分序列号，也就是毫秒内的并发量。自然而然想到一个数据结构，代码如下：

    static class TMCounter {
        long tm = 0;
        AtomicLong counter = new AtomicLong(0);

        public TMCounter() {
        }

        public TMCounter(long tm) {
            this.tm = tm;
        }
    }

之前开发的时候还不了解LongAdder，之后会有一篇文章说明LongAddder解决了AtomicLong的什么问题。

另外还会有个属性存储上一次请求的TMCounter信息：

    private volatile TMCounter preCounter = new TMCounter();

当一个获取唯一id的请求来时，首先会判断当前时间戳和上一次请求的时间戳的大小关系。

若大于说明是新的时间戳，会new一个新的TMCounter对象。
若等于或者小于（时钟回拨的情况）会算进上一次的并发里。

最后，按照各位的偏移量把四部分拼接在一起，代码如下：

     private TMCounter queryCurCounter() {
        // 计算与起始时间的差值
        long tm = System.currentTimeMillis() - START_TM;
        if (tm > curCounter.tm) {
            lock.lock();
            try {
                if (tm > curCounter.tm) {
                    // 更新计数器
                    curCounter = new TMCounter(tm);
                }
            } finally {
                lock.unlock();
            }
        }
        return curCounter;
    }

    @Override
    public Long generateUniqueId(int workerId) {
        TMCounter tmCounter = queryCurCounter();
        int countValue = tmCounter.counter.addAndGet(1);
        return (tmCounter.tm << (WORKER_ID_BITS + COUNTER_VALUE_BITS)) | (workerId << COUNTER_VALUE_BITS) | countValue;
    }

定时任务预生成方案

凭证id对长度和内容都有要求，snowflake方案就不能满足了。当时设计的方案分为两部分：

生成

生成策略：每天凌晨两点定时生成一定量的凭证id（取票码和验证码建联合唯一索引，随机生成两个字符串插入表中。半夜跑也就不管什么性能了。）以及同步到redis的list结构里。并且相应的数据会考虑到表里数据越多，冲突就会越多。会定期将一个月之前的数据迁移到ES同时删除表里面相应的数据（是不是有点冷热数据隔离的思想）。
生成数量：第一次是预计业务量的两倍（建议搞成动态配置）。之后生成的数量是业务量的两倍-redis还剩余的量。