最近，公司有个项目升级换代，MySQL 从一个拓展成多个。这就带来了一个问题，原本的数据表都在用自增 ID，如果继续用下去，坑会越来越大。
所以，我们用了新方案来生成 ID：雪花算法（snowflake）。
需求
在分布式数据库中，ID 要满足 3 个要求：唯一、趋势递增、数字类型。
- ID 必须是唯一的，不能出现重复 ID。
这是最基本的条件，可以是全局唯一，也可以业务内唯一。
- ID 要按照顺序逐步递增。
由于 InnoDB 的索引用的是 B+Tree 结构，所以主键要尽量是有序的，保证写入的性能。还有就是，你做排序的时候，直接用 ID 就行，快捷方便。
- ID 优先使用数字类型。
在数据库中，数字不用编码就能直接保存。但字符串就得先编码，这样会造成性能下降，和一些意想不到的问题。
除了这些，我们系统的订单表已经有了几十万条数据，所以还得再加一个要求：
- 不入侵业务，兼容原来的系统。
上面就是这次的需求，我们就按单抓药，来选一种方案吧。
常见的两种方案
在中小公司，比较流行两种生成 ID 的方案。
数据库自增 ID
自增 ID 大概是中小公司的首选，它有两个优点：
- 绝对递增。
每个 ID 都是唯一的，而且完全按照插入的先后顺序，1，2，3，4 一直下去。
- 非常简单。
在表字段后面加一个 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
看到这儿，我们可以说，雪花算法是靠谱的。
