概述
网上关于分布式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还剩余的量。
取Id
直接从redis的list取并更新数据库相应凭证状态为已使用。
这两种方案都比较简单，方案略显粗糙，都是为了应付业务初期遇到的问题。
