本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
本文主要基于真实踩坑经历展开
- 2.1 Snowflake工作原理
- 2.2 问题定位
- 2.3 排除时钟回拨
- 2.4 研究workerid
- 2.5 疑点
- 原因分析
- 解决方案
- 3.1 HostNameKeyGenerator
- 3.2 IPSectionKeyGenerator
- 3.3 使用我们团队自研的全局唯一ID服务
- 3.4 其他思路
感谢
彩蛋
- Ticket Servers方案缺乏顺序的保证
- 考虑过采用UUID，不过128-bit太长了
- E也考虑过采用ZooKeeper所提供的 **Unique Naming** Seuence Nodes 所提供的 Unique Naming 特性，但是性能不能满足。(Sequence Nodes的设计目标是解决分布式锁的问题，但不解决性能要求极高的ID生成问题，直接应用是一种Hack行为)
- E1-bit reserved
- E41-bit timestamp
- E10-bit machine id
- E12-bit sequence
- 你们的服务有没有什么特殊型的地方？
- 是重启的时候发生的么？
- 你能不能查一下对应重复的记录所在的机器，重复是不是只发生在这个ip段？
- 就是普通的微服务，普通的机器
- 不是重启时发生的
- 果然就是两台机器上出现了问题！
- 依赖机器时钟，如果机器时钟回拨，会导致重复ID生成
- 在单机上是递增的，但是由于设计到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况（此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会严格要求递增～90%的需求都只要求趋势递增）
2.2 问题定位
2.4 研究workerid
3.2 IPSectionKeyGenerator
3.4 其他思路
友情提示：欢迎关注公众号【芋道源码】。😈关注后，拉你进【源码圈】微信群和【芋艿】搞基嗨皮。
友情提示：欢迎关注公众号【芋道源码】。😈关注后，拉你进【源码圈】微信群和【芋艿】】搞基嗨皮。
友情提示：欢迎关注公众号【芋道源码】。😈关注后，拉你进【源码圈】微信群和【芋艿】】搞基嗨皮。
1. 异常概述
2018年1月26日下午，业务方信贷小组的同学反馈服务执行数据库插入操作出现异常，异常信息显示数据库主键出现重复：
在仔细分析了用户的重复主键ID、机器列表、雪花算法之后，下掉55这台机器，至此，异常得以解除。
本次异常看似平常，然而仔细分析起来可能造成的后果比较严重。
（1）波及面广、影响时间长。目前大量业务都采用了雪花算法的主键生成策略，如果业务、运维同学不了解雪花算法，会造成大量的时间分析排查此问题，造成一定的业务损失。
（2）存在潜在的隐患。雪花算法除了会产生此类Workid问题，也强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
2. 原因分析
为什么会造成数据库主键重复呢？
要回答这个问题要先介绍一下作为主键生成策略主要算法之一的雪花算法的工作原理。
2.1 Snowflake工作原理
对于分布式的ID生成，以Twitter Snowflake为代表的， Flake 系列算法，属于划分命名空间并行生成的一种算法，生成的数据为64bit的long型数据，在数据库中应该用大于等于64bit的数字类型的字段来保存该值，比如在MySQL中应该使用BIGINT。
Twitter在2010年6月1日（在Flickr那篇文章发布不到4个月之后），Ryan King 在Twitter的Blog 撰文 写道：
考虑过采用UUID，不过128-bit太长了
在这种情况下，Twitter给出了 64-bit 长的 Snowflake ，它的结构是：
E41-bit timestamp
E12-bit sequence
在过了不到4年，2014年的5月31日，Twitter 更新了 Snowflake 的 README，其中陈述了两个容易被忽视的事实:
“We have retired the initial release of Snowflake …”
“… heavily relies on existing infrastructure at Twitter to run. “
可以看出，这个方案所支持的最小划分粒度是「毫秒 * 线程」，单线程（Snowflake 里对应的概念是 Worker）的每秒容量是12-bit，也就是接近4096。
Snowflake的意义，不仅仅在于提供了解决方式，更多的是一种基于Long长度实现具有时间相关性的id自增序列。因此，很多公司基于它进行二次改造适应自己的场景。Snowflake家族的算法还有Instagram SnowFlake、Simpleflake、Boundary flake等等。
目前业界使用当当亮哥的sharding-jdbc，一般都会采取其内置的Snowflake算法，关于二次改造我这里列举一个58沈剑在《架构师之路》系列中提出的例子。
2.2 问题定位
收到业务方反馈以后，条件反射得第一时间连问了业务方同学三个问题：
是重启的时候发生的么？
业务方也是第一时间给了反馈
不是重启时发生的
好了，那我就定位到了是workid出现了问题，马上建议业务方下掉其中一台。为什么是workid,而不是时钟回拨等其他原因，且听我慢慢道来。
2.3 排除时钟回拨
大家应该都知道雪花算法存在的缺点是：
在单机上是递增的，但是由于设计到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况（此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会严格要求递增～90%的需求都只要求趋势递增）
我们采用的是当当的sharding-jdbc 1.4.2这个版本（1.5之前的sj并不成熟，强烈推荐使用2.x），可以说直接使用了其com.dangdang.ddframe.rdb.sharding.id.generator.self.IPIdGenerator进行主键生成，其序列号生成采用的是com.dangdang.ddframe.rdb.sharding.id.generator.self.CommonSelfIdGenerator，这里特别推荐读者读一下这两个类前面的注释，写得非常清楚。
/**
* 根据机器IP获取工作进程Id,如果线上机器的IP二进制表示的最后10位不重复,建议使用此种方式
* ,列如机器的IP为192.168.1.108,二进制表示:11000000 10101000 00000001 01101100
* ,截取最后10位 01 01101100,转为十进制364,设置workerId为364.
*
* @author DonneyYoung
*/
public class IPIdGenerator implements IdGenerator {
上面这段注释非常有用，先贴在这里，后面会详细谈到。
序列号生成采用的IPIdGenerator，当当的实现算法如下所示：
/**
* 自生成Id生成器.
*
* p
* 长度为64bit,从高位到低位依次为
* /p
*
* pre
* 1bit 符号位
* 41bits 时间偏移量从2016年11月1日零点到现在的毫秒数
* 10bits 工作进程Id
* 12bits 同一个毫秒内的自增量
* /pre
*
* p
* 工作进程Id获取优先级: 系统变量{@code sjdbc.self.id.generator.worker.id} 大于 环境变量{@code SJDBC_SELF_ID_GENERATOR_WORKER_ID}
* ,另外可以调用@{@code CommonSelfIdGenerator.setWorkerId}进行设置
* /p
*
* @author gaohongtao
*/
@Getter
@Slf4j
public class CommonSelfIdGenerator implements IdGenerator {
public static final long SJDBC_EPOCH;//时间偏移量，从2016年11月1日零点开始
private static final long SEQUENCE_BITS = 12L;//自增量占用比特
private static final long WORKER_ID_BITS = 10L;//工作进程ID比特
private static final long SEQUENCE_MASK = (1 SEQUENCE_BITS) - 1;//自增量掩码（最大值）
private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;//工作进程ID左移比特数（位数）
private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;//时间戳左移比特数（位数）
private static final long WORKER_ID_MAX_VALUE = 1L WORKER_ID_BITS;//工作进程ID最大值
@Setter
private static AbstractClock clock = AbstractClock.systemClock();
@Getter
private static long workerId;//工作进程ID
static {
Calendar calendar = Calendar.getInstance();
calendar.set(2016, Calendar.NOVEMBER, 1);
calendar.set(Calendar.HOUR_OF_DAY, 0);
calendar.set(Calendar.MINUTE, 0);
calendar.set(Calendar.SECOND, 0);
calendar.set(Calendar.MILLISECOND, 0);
SJDBC_EPOCH = calendar.getTimeInMillis();
initWorkerId();
}
private long sequence;//最后自增量
private long lastTime;//最后生成编号时间戳，单位：毫秒
static void initWorkerId() {
String workerId = System.getProperty("sjdbc.self.id.generator.worker.id");
if (!Strings.isNullOrEmpty(workerId)) {
setWorkerId(Long.valueOf(workerId));
return;
}
workerId = System.getenv("SJDBC_SELF_ID_GENERATOR_WORKER_ID");
if (Strings.isNullOrEmpty(workerId)) {
return;
}
setWorkerId(Long.valueOf(workerId));
}
/**
* 设置工作进程Id.
*
* @param workerId 工作进程Id
*/
public static void setWorkerId(final Long workerId) {
Preconditions.checkArgument(workerId = 0L && workerId WORKER_ID_MAX_VALUE);
CommonSelfIdGenerator.workerId = workerId;
}
/**
* 生成Id.
*
* @return 返回@{@link Long}类型的Id
*/
@Override
public synchronized Number generateId() {
//保证当前时间大于最后时间。时间回退会导致产生重复id
long time = clock.millis();
Preconditions.checkState(lastTime = time, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, time);
// 获取序列号
if (lastTime == time) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
time = waitUntilNextTime(time);
}
} else {
sequence = 0;
}
// 设置最后时间戳
lastTime = time;
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
// 生成编号
return ((time - SJDBC_EPOCH) TIMESTAMP_LEFT_SHIFT_BITS) | (workerId WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
//不停获得时间，直到大于最后时间
private long waitUntilNextTime(final long lastTime) {
long time = clock.millis();
while (time = lastTime) {
time = clock.millis();
}
return time;
}
}
通过这段代码可以看到当当的时钟回拨在单机上是做了处理的了，不但会抛出Clock is moving backwards balabalabala的IllegalStateException，而且也做了waitUntilNextTime一直等待的处理。如果单机是时钟回拨，除非应用重启或者回拨了时间，然而，线上服务器运行得好好的，根本没人动过，所以就不是单机时钟回拨的问题。
再考虑是否是集群回拨的情况，同样，如果workerid不同出现重复主键的概率基本不可能，并且我也仔细比对了出问题两台机器的时间基本保持一致，所以虽然我们公司的机器是渐进式时间管理（据说有些公司运维直接做了一个同步脚本，如果时钟不是脚本同步，而是渐进同步的就可能会产生重复ID），也不应该是大量出现此类问题的原因（用户反馈给了我几十个重复主键ID）。
当然，这段代码还能收获的一个信息就是，debug模式你可以看到你的workerId、sequence等等信息，可是，线上运行，哪个系统会一一给你把主键ID打出来呢？线上鸡肋，鸡肋鸡肋，食之无味，弃之有味。至于怎么拿workId，请看下节。
2.4 研究WorkId
如下图所示，这就是我们全篇讨论的雪花算法：
时间戳，41比特，从2016年11月1日零点到现在的毫秒数,可以用到2156年，100多年后才会用完
序列号，12比特，每台机器每毫秒最多产生4096个id，超过这个数的话会等到下一毫秒
我们细化2.3节中雪花算法的实现：
public synchronized Number generateId() {
long time = clock.millis();
Preconditions.checkState(lastTime = time, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, time);
if (lastTime == time) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
time = waitUntilNextTime(time);
}
} else {
sequence = 0;
}
lastTime = time;
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
return ((time - SJDBC_EPOCH) TIMESTAMP_LEFT_SHIFT_BITS) | (workerId WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
WORKER_ID_LEFT_SHIFT_BITS工作机器ID左移动12位
进一步研究一下workid基于IPIdGenerator的实现
CommonSelfIdGenerator.setWorkerId((long) (((ipAddressByteArray[ipAddressByteArray.length - 2] & 0B11) Byte.SIZE) + (ipAddressByteArray[ipAddressByteArray.length - 1] & 0xFF)));
可以很清楚得看到，这就是取ip的最后两个段，一共取10bit，和我之前强调的注释说得一模一样
根据机器IP获取工作进程Id,如果线上机器的IP二进制表示的最后10位不重复,建议使用此种方式,列如机器的IP为192.168.1.108,二进制表示:11000000 10101000 00000001 01101100,截取最后10位 01 01101100,转为十进制364,设置workerId为364.
然后把我们出问题的机器XXX.XXX.209.55，XXX.XXX.161.55(出于安全数据脱敏)转化为workid，发现都是一样的。
当然，你也可以使用下面代码自己跑出workid。
@Test
public void generateId3() throws UnknownHostException, NoSuchFieldException, IllegalAccessException {
String ipv4s =
// "XXX.XXX.161.55n"
"XXX.XXX.209.55n"
// "XXX.XXX.209.126 n" +
// "XXX.XXX.209.127tn" +
// "XXX.XXX.208.227 n" +
// "XXX.XXX.148.134 n" +
// "XXX.XXX.148.135tn" +
// "XXX.XXX.148.132tn" +
// "XXX.XXX.148.133";
;
for (String ipv4 : ipv4s.split("n")) {
ipv4 = ipv4.replaceAll("t", "").trim();
byte[] ipv4Byte = new byte[4];
String[] ipv4StingArray = ipv4.split("\.");
for (int i = 0; i 4; i++) {
ipv4Byte[i] = (byte) Integer.valueOf(ipv4StingArray[i]).intValue();
}
address = InetAddress.getByAddress("dangdang-db-sharding-dev-233", ipv4Byte);
PowerMockito.mockStatic(InetAddress.class);
PowerMockito.when(InetAddress.getLocalHost()).thenReturn(address);
IPKeyGenerator.initWorkerId();
// IPSectionKeyGenerator.initWorkerId();
Field workerIdField = DefaultKeyGenerator.class.getDeclaredField("workerId");
workerIdField.setAccessible(true);
System.out.println(ipv4 + "t" + workerIdField.getLong(DefaultKeyGenerator.class));
}
}
另外我们也可以根据用户提供的所有重复的ID反解workerid
psvm+sout+(ID/4096%1024)
/4096的意思是整除2的12次方，变相干掉12bit序列号，%1024的意思是取2的十次方的余数，拿到工作机器id 居然所有用户的重复ID反解出来的workerid都是一样的。至此，我们可以得到结论，**workerid重复导致了线上主键重复**
2.5 疑点
但是上面的推测还有一个谜团没有解开，就是只有Workerid相同，41bit的时间戳和12bit的序列号怎么可能碰撞那么严重，两天内出现了近百次冲突？如果说这个碰撞和hashmap的碰撞一样，那么也一定是高并发低概率的，为什么会这么频繁？
所以，我又追问了业务方一个问题：
业务方给我的反馈是“并发量不大”。
我顿时明白了，翻了一下上面序列号生成的代码实现，该序列是用来在同一个毫秒内生成不同的Id，该Id顺序递增，如果在这个毫秒内生成的数量超过4096(2的12次方)，那么生成器会等待到下个毫秒继续生成。从Id的组成部分看，不同进程的Id肯定是不同的，同一个进程首先是通过时间位保证不重复，如果时间相同则是通过序列位保证。 同时由于时间位是单调递增的，且各个服务器如果大体做了时间同步，那么生成的Id在分布式环境可以认为是总体有序的。
通过
psvm+sout+(ID%4096)
验证得知，所有重复主键ID的序列号都是0，完全印证了我的猜想。
所以，因为序列号是从0开始递增的，结论就是只要workerid相同，同时在这两台机器上出现请求，就会产生重复，或者说只要线上IP末尾相同，就有可能会产生重复！！！
3. 解决方案
运维下线了重复的55一台旧机器解决了此问题。了解到以前公司的机器IP都是连号的没有出现这种并行的形式，这次是新老机器并存导致的。当然还有别的解决方案。
3.1 HostNameKeyGenerator
根据机器名最后的数字编号获取工作进程编号。如果线上机器命名有统一规范,建议使用此种方式。例如，机器的 HostName 为: dangdang-db-sharding-dev-01(公司名-部门名-服务名-环境名-编号)，会截取 HostName 最后的编号 01 作为工作进程编号( workId )。
3.2 IPSectionKeyGenerator
改进版本的IP生成策略。
浏览 IPKeyGenerator 工作进程编号生成的规则后，感觉对服务器IP后10位（特别是IPV6）数值比较约束。 有以下优化思路： 因为工作进程编号最大限制是 2^10，我们生成的工程进程编号只要满足小于 1024 即可。 1.针对IPV4: ….IP最大 255.255.255.255。而（255+255+255+255) 1024。 ….因此采用IP段数值相加即可生成唯一的workerId，不受IP位限制。
-
针对IPV6: ….IP最大 ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff ….为了保证相加生成出的工程进程编号 1024,思路是将每个 Bit 位的后6位相加。这样在一定程度上也可以满足workerId不重复的问题。 使用这种 IP 生成工作进程编号的方法,必须保证IP段相加不能重复
对于 IPV6 ：2^ 6 = 64。64 * 8 = 512 1024。
// IPSectionKeyGenerator.java
static void initWorkerId() {
InetAddress address;
try {
address = InetAddress.getLocalHost();
} catch (final UnknownHostException e) {
throw new IllegalStateException("Cannot get LocalHost InetAddress, please check your network!");
}
byte[] ipAddressByteArray = address.getAddress();
long workerId = 0L;
// IPV4
if (ipAddressByteArray.length == 4) {
for (byte byteNum : ipAddressByteArray) {
workerId += byteNum & 0xFF;
}
// IPV6
} else if (ipAddressByteArray.length == 16) {
for (byte byteNum : ipAddressByteArray) {
workerId += byteNum & 0B111111;
}
} else {
throw new IllegalStateException("Bad LocalHost InetAddress, please check your network!");
}
DefaultKeyGenerator.setWorkerId(workerId);
}
PS：此人的思路虽然巧妙，也不能绝对OK，例如，254.255和255.254会重复，172.16.x.x，即使这个段，也是2的16次方，不过也能凑活得用，还是基于etcd或者zk发号靠谱。
或者只要公司机器编号准确，HostNameKeyGenerator也是非常靠谱的。
3.3 使用我们团队自研的全局唯一ID服务
做到的地方
高性能，每秒钟可以获取百万级的ID，并且不会出现阻塞
一致性，绝对保证不会获取到重复的ID（服务端保证）
做不到的地方
无法保证按照时间有序
3.4 其他思路
还有一种避免回拨的方式是用1～2台关闭NTP时钟的机器做backup
还有别的解决方案，重复的时间后面可以增加版本号，做专门的校时服务器，因为集群获取机器时间就会有时间窗口问题，造成生成的Id编号重复
上文提到的基于host，其实也是一种不错的解决方案
4. 感谢
这是公众号「工匠小猪猪的技术世界」的第一篇文章，感谢「芋道源码」芋艿在技术、排版等方面给予的大力指导！
666. 彩蛋
第一篇 公众号 的文章，如果有地方写的不正确，还望指出，谢谢。
更多 分布式ID 内容，推荐阅读如下文章：
58 —— 《细聊分布式ID生成方法》
王延炯博士 —— 《生成全局唯一ID的3个思路，来自一个资深架构师的总结》
