一步步带你了解ID发号器是什么、为什么、如何做！
一步步带你了解ID发号器是什么、为什么、如何做！
一、前言
上一篇文章《面试必备：如何将一个长URL转换为一个短URL？》中谈到如何将长地址URL转换为短地址URL，其中谈到了一个比较理想的解决方案就是使用发号器生成一个唯一的整数ID，然后转换为62进制，作为短地址URL。
其中使用到了ID发号器，可能很多小伙伴还不懂什么是ID发号器以及如何去实现，今天我们就一起探讨一下什么是ID发号器？ID发号器的原理是什么？如何实现一个ID发号器等。
二、从数据库主键ID说起
1、单机数据库
当我们的业务访问量不是很大的时候，我们可以使用一台数据库服务器满足我们的业务需求，我们一般设计数据库的时候主键ID用bigint类型，并且设置为自增、无符号，如下所示：
这种方式完全可以满足我们的业务需求，生成全局唯一递增ID是数据库可以提供给我们的功能，具有如下优点：
（1）能够保证唯一性； （2）能够保证递增性； （3）步长固定；
但是当我们的业务逐渐扩大，我们需要对数据库进行分库分表等操作的时候，这种方式是就变得没有办法了！
试想一下，如果我们有一个业务，每一个省份维护自己的一台数据库，User表用于记录当前省份的用户信息，假如有一天我们需要把每一个省份的User表用户信息全部合并到一台中央数据库User表中进行统计的时候，结果是不是会崩掉，因为每一个省份User表中的ID都是从1主键递增的！
2、数据库集群、分库分表
当我们的数据库达到一定规模的时候，就需要对其进行分库分表，分库分表的时候我们就很难保证主键ID的唯一性，这一点很好理解。这是因为，我们的一张表被分割到不同机器上的数据库中，如果还依靠与数据库自带的自增功能的话就很那保证ID唯一性！如下图所示：
可以看出，User表中的100W数据被分到两个数据库中，在每一个数据库内部主键ID是自增的，但是却没法保证全局主键ID自增的，这显然是错误的！如何解决这种问题哪？
（1）使用UUID
最简单、最容易想到的就应该是使用UUID了，根据UUID的特性，可以产生一个唯一的字符串，这一点大家都知道。UUID是在本地生成的，所以相对性能较高、时延低、扩展性高，完全不受分库分表的影响！
但是使用UUID是有点小问题的，主要体现在：
- UUID无法保证趋势递增；
- UUID过长，往往用32位字符串表示，占用数据库空间较大，做主键的时候索引中主键ID占据的空间较大；
- UUID作为主键建立索引查询效率低，常见优化方案为转化为两个uint64整数存储；
- 由于使用实现版本的不一样，在高并发情况下可能会出现UUID重复的情况；
UUID虽然能够保证全局主键ID的唯一性，但是UUID并不具有有序性，会导致B+树索引在写的时候有过多的随机写操作（连续的ID会产生部分的顺序写）；另外，由于在写的时候不能产生有顺序的append操作，而需要进行insert操作，将会读取整个B+树节点加到内存中，在插入这条记录后将整个节点写回磁盘，这种操作在记录占用空间比较大的情况下，性能下降明显。
（2）ID分组
虽然，UUID很方便，但由于他的一些弊端我们无法接受，所以在很多对一些性能要求较高的业务场景中，我们是很少使用UUID的，那我们还有没有什么其他方法哪？接下来让我们看一下ID分组的使用：
如上图所述，由1个数据库变成4个库，每个数据库设置不同的auto_increment初始值init，以及相同的增长步长step，以保证每个数据库生成的ID是不同的，改进后的架构保证了可用性，但缺点是：
- 丧失了ID生成的“绝对递增性”，但这个问题不大，我们的目标是趋势递增，不是绝对递增；
- 数据库的写压力依然很大，每次生成ID都要访问数据库；
- 可扩展性差；
我们可以想象的是，目前虽然我们的机器只有4台，然后由不同的init和不同的step，但是如果我们需要在其中再加一台机器的话，可想而知我们需要手动更新init和step，这是一件比较繁琐的事情！但有人可能会说了，我们可以直接把 step设置大一些，假如，我们预期数据最大规模的时候用100台数据库服务器就可以了，那我们就可以设置step为100。尽管如此，扩展性还不是很高！
3、还有什么操作哪？
上述我们讨论了一个一个的优缺点，当然，还有很多其他的主键ID生成方案。但总的来说，我们讨论问题的关键浮出水面：如何高效生成趋势有序的全局唯一ID，兼顾有序性、高性能、可扩展等因素！
这就需要我们今天的主角登场了，他就是：ID发号器！ID发号器的主要思想大致相同，但不同平台的实现方式可能会有所不同，本文主要介绍一下：Twitter公司的SnowFlake、如何自己实现一个ID发号器、Vesta框架。
三、SnowFlake简介
Twitter公司的SnowFlake算法就是著名的《雪花算法》，SnowFlake是通过Scala语言实现的，目前GitHub上已经看不到源代码了，只有一个2010年的版本，地址为：https://github.com/twitter/snowflake/releases/tag/snowflake-2010，因此很难在我们实际的项目中真正的使用到 ，我们更多的是采用雪花算法的思想，去构建自己属于自己的ID发号器。
1、SnowFlake原理
SnowFlake产生的ID是一个64位的整型，结构如下（每一部分用“-”符号分隔）：
（1）1位：标识部分，在java中由于long的最高位是符号位，正数是0，负数是1，一般生成的ID为正数，所以为0；
（2）41位：时间戳部分，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间-固定的开始时间），这样可以使产生的ID从更小值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年；
（3）10位：节点部分，Twitter实现中使用前5位作为数据中心标识，后5位作为机器标识，可以部署1024个节点；
（4）12位：序列号部分，支持同一毫秒内同一个节点可以生成4096个ID；
SnowFlake算法生成的ID大致上是按照时间递增的，用在分布式系统中时，需要注意数据中心标识和机器标识必须唯一，这样就能保证每个节点生成的ID都是唯一的！
2、SnowFlake算法如何实现
SnowFlake算法的实现在GitHub或者码云上有各种实现版本！SnowFlake算法为我们提供了一个可行的思路，但是我们不一定都需要像上面那样使用5位作为数据中心标识，5位作为机器标识，可以根据我们业务的需要，灵活分配节点部分，如：若不需要数据中心，完全可以使用全部10位作为机器标识；若数据中心不多，也可以只使用3位作为数据中心，7位作为机器标识。所以，我们可以看出SnowFlake算法只是一种指导思想，我们下边自己简单的实现一个一下！
四、如何自己实现一个ID发号器
注意这里只有生成ID的部分，没有Client也没有Server，如果想要详细的，请看第五节《Vesta框架简介》！
/**
* Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数，然后转化为62进制变成一个短地址URL
* @author beyond https://github.com/beyondfengyu/SnowFlake
* @author xuliugen
* @date 2018/04/23
*/
public class SnowFlake {
/**
* 起始的时间戳
*/
private final static long START_TIMESTAMP = 1480166465631L;
/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 12; //序列号占用的位数
private final static long MACHINE_BIT = 5; //机器标识占用的位数
private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数
/**
* 每一部分的最大值
*/
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
private long dataCenterId; //数据中心
private long machineId; //机器标识
private long sequence = 0L; //序列号
private long lastTimeStamp = -1L; //上一次时间戳
/**
* 根据指定的数据中心ID和机器标志ID生成指定的序列号
* @param dataCenterId 数据中心ID
* @param machineId 机器标志ID
*/
public SnowFlakeShortUrl(long dataCenterId, long machineId) {
if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0！");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0！");
}
this.dataCenterId = dataCenterId;
this.machineId = machineId;
}
/**
* 产生下一个ID
* @return
*/
public synchronized long nextId() {
long currTimeStamp = getNewTimeStamp();
if (currTimeStamp < lastTimeStamp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (currTimeStamp == lastTimeStamp) {
//相同毫秒内，序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currTimeStamp = getNextMill();
}
} else {
//不同毫秒内，序列号置为0
sequence = 0L;
}
lastTimeStamp = currTimeStamp;
return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
| dataCenterId << DATA_CENTER_LEFT //数据中心部分
| machineId << MACHINE_LEFT //机器标识部分
| sequence; //序列号部分
}
private long getNextMill() {
long mill = getNewTimeStamp();
while (mill <= lastTimeStamp) {
mill = getNewTimeStamp();
}
return mill;
}
private long getNewTimeStamp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);
for (int i = 0; i < (1 << 4); i++) {
//10进制
System.out.println(snowFlake.nextId());
}
}
}
//输出结果：
185892988017455104
185892988021649408
185892988021649409
185892988021649410
185892988021649411
185892988021649412
185892988021649413
185892988021649414
185892988021649415
185892988021649416
185892988021649417
185892988021649418
185892988021649419
185892988021649420
185892988021649421
185892988021649422还记得上一篇《面试必备：如何将一个长URL转换为一个短URL？》文中提到的短地址吗？上文中已经生成了唯一不重复的ID，我们只需要增加一个进制转换的工具就可以了，进制转换的工具如下：
/**
* 进制转换工具，最大支持十进制和62进制的转换
* 1、将十进制的数字转换为指定进制的字符串；
* 2、将其它进制的数字（字符串形式）转换为十进制的数字
* @author xuliugen
* @date 2018/04/23
*/
public class NumericConvertUtils {
/**
* 在进制表示中的字符集合，0-Z分别用于表示最大为62进制的符号表示
*/
private static final char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
/**
* 将十进制的数字转换为指定进制的字符串
* @param number 十进制的数字
* @param seed 指定的进制
* @return 指定进制的字符串
*/
public static String toOtherNumberSystem(long number, int seed) {
if (number < 0) {
number = ((long) 2 * 0x7fffffff) + number + 2;
}
char[] buf = new char[32];
int charPos = 32;
while ((number / seed) > 0) {
buf[--charPos] = digits[(int) (number % seed)];
number /= seed;
}
buf[--charPos] = digits[(int) (number % seed)];
return new String(buf, charPos, (32 - charPos));
}
/**
* 将其它进制的数字（字符串形式）转换为十进制的数字
* @param number 其它进制的数字（字符串形式）
* @param seed 指定的进制，也就是参数str的原始进制
* @return 十进制的数字
*/
public static long toDecimalNumber(String number, int seed) {
char[] charBuf = number.toCharArray();
if (seed == 10) {
return Long.parseLong(number);
}
long result = 0, base = 1;
for (int i = charBuf.length - 1; i >= 0; i--) {
int index = 0;
for (int j = 0, length = digits.length; j < length; j++) {
//找到对应字符的下标，对应的下标才是具体的数值
if (digits[j] == charBuf[i]) {
index = j;
}
}
result += index * base;
base *= seed;
}
return result;
}
}写个测试用例如下：
public static void main(String[] args) {
SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);
for (int i = 0; i < (1 << 4); i++) {
//10进制
Long id = snowFlake.nextId();
//62进制
String convertedNumStr = NumericConvertUtils.toOtherNumberSystem(id, 62);
//10进制转化为62进制
System.out.println("10进制：" + id + " 62进制短地址:" + convertedNumStr);
//TODO 执行具体的存储操作，可以存放在Redis等中
//62进制转化为10进制
System.out.println("62进制短地址：" + convertedNumStr + " 10进制:" + NumericConvertUtils.toDecimalNumber(convertedNumStr, 62));
System.out.println();
}
}
//执行结果如下：
10进制：185894506410029056 62进制短地址:dJoJ1Xyo3C
62进制短地址：dJoJ1Xyo3C 10进制:185894506410029056
10进制：185894506414223360 62进制短地址:dJoJ1XPZbG
62进制短地址：dJoJ1XPZbG 10进制:185894506414223360
10进制：185894506414223361 62进制短地址:dJoJ1XPZbH
62进制短地址：dJoJ1XPZbH 10进制:185894506414223361
10进制：185894506414223362 62进制短地址:dJoJ1XPZbI
62进制短地址：dJoJ1XPZbI 10进制:185894506414223362
10进制：185894506414223363 62进制短地址:dJoJ1XPZbJ
62进制短地址：dJoJ1XPZbJ 10进制:185894506414223363
10进制：185894506414223364 62进制短地址:dJoJ1XPZbK
62进制短地址：dJoJ1XPZbK 10进制:185894506414223364
......所有代码地址在：https://gitee.com/xuliugen/codes/9upvmzyk6c2i78eb3lgnj63
五、Vesta框架简介
Vesta是一款通用的ID产生器，互联网俗称统一发号器，它具有全局唯一、粗略有序、可反解和可制造等特性，它支持三种发布模式：嵌入发布模式、中心服务器发布模式、REST发布模式，根据业务的性能需求，它可以产生最大峰值型和最小粒度型两种类型的ID，它的实现架构使其具有高性能，高可用和可伸缩等互联网产品需要的质量属性，是一款通用的高性能的发号器产品。
码云：https://gitee.com/robertleepeak/vesta-id-generator GitHub：https://github.com/cloudatee/vesta-id-generator
由于Vesta的设计与实现较为复杂，一小节不足以说明清楚，后续我们再单独写一篇文章讨论，这里不再详细的介绍，有兴趣的参考上述仓库地址文档！