雪花算法在生产环境中出事故啦！

大家好，我是小许 又是重复的一天

早上7：30闹钟，铃铃铃，起床，挤地铁，地铁人是真的多！

到了公司，开机一顿操作... 时间滴答滴答过去，到点了，准备下班

不过今天安静的整体来说是不怎平静的，遇到了【雪花算法】的线上产生的事故

📚 全文字数 : 3.6k+

⏳ 阅读时长 : 5min

📢 关键词 : 雪花算法、时钟回拨、NTP同步、Leaf方案

前言

其实整个问题是使用雪花算法过程是遇到的，这次刚好把事故记下来，希望对没遇到过得同学有个提醒。

先了解文章记录的内容：

我们先了解下什么是雪花算法。

雪花算法是Twitter公司发明的一种算法，主要目的是解决在分布式环境下，ID怎样生成的问题。

它使用一个 64 bit 的 long 型的数字（只有 63 位用于填充有符号整数）作为全局唯一 ID，最终数字一般以十进制序列化。

我们来看看雪花算法的生成原理：

二进制64位长整型数字：1bit 保留 + 41bit 时间戳 + 10bit 机器 + 12bit 序列号

1 bit：【不用】，二进制中最高位是符号位，1表示负数，0表示正数，生成的id一般都是用整数，所以最高位固定为0

41 bits【时间戳】：单位是毫秒，可表示2^41-1个毫秒值，转换成年就是表示 69 年的时间。

10 bits【工作机器ID】：5 bits 代表机房 id，5 个 bits 代表机器 id，最多代表 32 个机房，每个机房最多代表 32 台机器。

12 bits【自赠与】：表示在某一毫秒下，这个自增域最大可以分配的bit个数，最多可分配 4096 个不同 id

来看兰雪花算法的优缺点

优点：

• 能满足高并发分布式系统环境下ID不重复
• 基于时间戳，毫秒数在高位，自增序列在低位，保证趋势递增的
• 不依赖第三方库或中间件，以服务的方式部署
• 在内存中生成，生成ID的性能也是非常高的
• 可以根据自身业务特性分配bit位，非常灵活

缺点：

• 依赖服务器时间，服务器时钟回拨时可能会生成重复 id。

通过看优缺点，我们知道雪花算法有个致命问题【时钟回拨】

线上事故处理

事故现象

运营反馈有用户使用我们系统第一次上传数据成功后，接下来无论怎么样都上传不了数据了，用户很疑惑，导致现在无法使用了！

这也是第一次反馈这种问题，不管第几次，出现了就处理，开搞，开搞！

排查过程

1：先看检查线上系统是否可用，我们进入了同样的模块发现没问题。

2：看看反馈用户是否也遇到了同样的问题，客服和运营那边只有一个反馈，而且确定了用户那边网络是没问题。

3：那就查日志，发现有数据库操作层的报错日志【duplicate key】，这个字段我们是唯一索引而且是用雪花算法生成的，雪花算法按理不会重复。

4：联想到用户第一次上传成功了，我们直接看数据库记录，唯一索引的字段值居然是 0

文章开头我们了解到雪花优缺点，基本可以确认不是生成的ID重复导致的，因为入库的值是0，而一般雪花算法生成的ID十进制和二进制是这样的。

难道是时钟回拨导致的？

先让客服连续用户看下用户电脑时间，果然显示的不是当前的时间，估计是重装系统了，没有同步时间，好了这里就找到问题点了，先让用户同步下系统时间，让他先能用（注：软件是客户端软件，用户需要安装）。

但是为啥是0呢？这个应该不是算法的问题，应该在哪里判断导致的，继续看代码

代码分析

func (iw *IdWorker) NextId() (ts int64, err error) {
 iw.lock.Lock()
 defer iw.lock.Unlock()
 ts = iw.timeGen()
 if ts == iw.lastTimeStamp {
  iw.sequence = (iw.sequence + 1) & CSequenceMask
  if iw.sequence == 0 {
   ts = iw.timeReGen(ts)
  }
 } else {
  iw.sequence = 0
 }

 if ts < iw.lastTimeStamp {
  err = errors.New("Clock moved backwards, Refuse gen id")
  return 0, err
 }
 iw.lastTimeStamp = ts
 ts = (ts-CEpoch)<<CTimeStampShift | iw.workerId<<CWorkerIdShift | iw.sequence
 return ts, nil
}

// return in ms
func (iw *IdWorker) timeGen() int64 {
 // 当前时间纳秒 / 1000 /1000 = 当前时间毫秒
 return time.Now().UnixNano() / 1000 / 1000
}

注意看，这里面有一个error，意思是时钟向后移动，拒绝生成ID，我们来看判断条件，ts是当前时间毫秒，每次生成之前会把当前时间和上一次时间进行对比，如下图：

如果当前时间小于上次执行时间 ts < lastTimeStamp，就返回0和一个error了。

代码分析完了，生成的方式没问题，但是时钟回拨会返回0，而调用方就没处理error和0的情况，直接拿来用了，额，心真细。

这也解释了为什么唯一索引的值是 0，而第二次上传就 duplicate key 的原因了。

事故原因：时钟回拨

简单说就是时间被调整回到了之前的时间，由于雪花算法重度依赖机器的当前时间，所以一旦发生时间回拨，将有可能导致生成的 ID 可能与此前已经生成的某个 ID 重复。

这也是雪花算法经常讨论的问题，虽然用到的工具不会出现重复（时钟回拨了直接不生成了）。

时钟回拨一般是如何引起的呢

• 网络时间自动校准
• 人工设置时间
• 出现负闰秒

闰秒：就是通过给“世界标准时间”加（或减）1秒，让它更接近“太阳时”。例如，两者相差超过0.9秒时，就在23点59分59秒与00点00分00秒之间，插入一个原本不存在的“23点59分60秒”，来将时间调慢一秒钟

NTP时钟同步

导致时钟回拨是机器本地时钟因为各种原因发生不准导致，其实网络中有NTP（NTP为Network Time Protocol的缩写，即网络时间协议）服务来提供时间校准。

通过时间校准让客户端和服务器之间进行时钟同步，提供高精准度的时间校正，NTP服务器从权威时钟源（例如原子钟、GPS）接收精确的协调世界时UTC，因为NTP Pool是绝大多数主流Linux发行版和许多网络设备的默认“时间服务器”。

NTP时间同步流程如下

解决方案

我们接着看面对这种问题该如何处理呢，一般来说有以下几种方式

直接抛异常

在雪花算法原本的实现中，针对这种问题，算法本身只是返回错误，由应用另行决定处理逻辑，而这次事故中调用方却没有做对应的处理，比如告诉用户调用失败，因为唯一所用是0值的话其实是个垃圾数据了。

在一个并发不高或者请求量不大的业务系统中，错误等待或者重试的策略问题不大，但是如果是在一个高并发的系统中，这种策略显得并不是很妥当。

延迟等待

将当前线程阻塞3ms，之后再获取时间，看时间是否比上一次请求的时间大，如果大了，说明恢复正常了，则不用管如果还小，说明真出问题了，则抛出异常

百度UIDGenerator方案

百度UidGenerator方案不是每次获取 ID 时都实时计算分布式 ID，而是利用 RingBuffer 环形数组数据结构，CachedUidGenerator 实现了 ID 的缓冲区。

通过缓存的方式预生成一批唯一 ID 列表，然后通过 incrementAndGet() 方法获取下一次的时间，从而脱离了对服务器时间的依赖。

总的来说，百度 UID-Generator 预生成方式是一个不错的选择。

美团Leaf方案

美团 Leaf 引入了 zookeeper 来解决时钟回拨问题。

其大致思路为：每个 Leaf 运行时定时向 zk 上报时间戳，每次 Leaf 服务启动时，先校验本机时间与上次发 ID 的时间，再校验与 zk 上所有节点的平均时间戳。如果任何一个阶段有异常，那么就启动失败报警。

更详细的方案解析，可以看看这里：

总结

引起本次线上问题的根源是我们对雪花算法缺少认识，导致说使用第三方库的时候没有进行二次规避。

由于就是雪花算法的生成没有做成公共服务，前人处理技术方案的原因，这里后续看具体做改进。

整体来说雪花算法强依赖服务时钟，产生回拨的话会导致不少问题，这个时候可以使用NTP进行时钟同步。

百度UIDGenerator方案和美团Leaf方案在面对时钟回拨问题是有比较好的处理方案的，大家可以多多了解！

好了今天就记录到这了，喜欢的大家一键三连一下，我是爱跑步的程序员小许！