MANKA の Blog
讲讲雪花算法

2022-04-22

#Twitter#Snowflakes

作为爬 Twitter 大军的一员,了解生成 tweet_iduid 等纯数字id的 Snowflakes 是很有必要的。这篇东西我很早就想写了,只是一直在咕,从未开工。

被坑

刚做 Twitter Monitor 的时候,我是不了解这玩意的,对类型问题、溢出问题都是一知半解,因此在设计数据库结构时,tweet_iduid 的类型只是一个 int,于是喜闻乐见地丢了精度,我一看不对劲,怎么一堆用户的 uid 最后面三位都是 0 ?直到查了资料才知道这玩意。

后来类型改成了 bigint,json中也增加了类型为 string 的相关字段,也看了不少相关资料,终于决定开这个新坑。

Snowflakes的由来

根据维基百科的说法, Snowflakes 出自 Twitter,曾经还公开了用 scala 写的源码,我对 scala 并不熟悉,只能看看别人的说法了。维基百科是这么描述 Snowflakes 的:

雪花算法 (Snowflake)是一种生成分布式全局唯一ID的算法,生成的ID称为Snowflake IDs或snowflakes。这种算法由 Twitter 创建,并用于推文的ID。

根据README,这个系统将会生成一个64bit的值:

  • 第一个bit为符号位,固定为0,确保任何时候都是正整数
  • 然后的41bit是一个精确到毫秒的当前时刻减去固定的启示时刻的差值,因此可用的时长为 (2^41)/(1000*60*60*24*365)≈69yr,至于69年后用满了怎么计算嘛,项目能不能撑那么久都是个问题,到时候再说吧(万一那会128位已经普及了呢),顺带一提的是 Twitter 的这个起始时刻为 1288834974657,更多关于这个时刻的细节请阅读我们的老朋友 igorbrigadir/twitter-advanced-search。至于为什么不用128位,Twitter 是这么解释的(128位CPU出现了么)

    There are many otherwise reasonable solutions to this problem that require 128bit numbers. For various reasons, we need to keep our ids under 64bits.

  • 接下来的10bit是机器编码,这下就能塞1024台机器进来了
  • 剩下的12bit就是纯粹自增的顺序编号了

文字说明不清晰,我们来张图

  +----------------------   Snowflake IDs  64bits   ---------------------+
  |                                                                      |
  v                                                                      v
  0 0000000000 0000000000 0000000000 0000000000 0 0000000000 0000000000 00
  ^ ^                                           ^ ^        ^ ^           ^
  | |                                           | |        | |           |
  | +-------------------------------------------+ +--------+ +-----------+
Sign                    Time                      Machine id  Sequence number
1bit                   41bits                        10bits       12bits

从这图我们就能看出 Snowflakes 的生成总是绕不开 首bit为 0 + 时间差 + 机器id + 顺序数 这个规则

目前 Twitter 已经不再维护这个被称为snowflake-2010的版本了,他们使用与内部硬件强关联的重构版本,也没再公开过代码

优劣

优势

  • 非常简单实用的不重复id的生成算法
  • 纯数字,不需要考虑任何奇奇怪怪的分隔符
  • 强依赖时钟,可根据时间排序
  • 非常强大的高并发支持,单机QPS能达到 2^12*1000=4,096,000

劣势

  • 时钟回拨问题,由于 Snowflakes 强依赖时钟,NTP服务同步可能导致的时间跳动会反映在生成的id上,有可能出现后发送的消息得到的id比早发送的消息的id小的情况发生,更严重时甚至会发生id重复,因此对同步时间这项服务的要求非常高,不知道现在 Twitter 解决了没有,衍生的算法或多或少都会提及自家的解决方案
  • 由于前面有41bit跟时间相关、中间有10bit与机器相关,因此不能用上所有的数,有id的浪费
  • 尾部的顺序数导致其不能够无状态生成

变种

虽然本体已经不再公开源码,但大家都根据这个思路玩出了自己的花样

美团Leaf

  +--------------------   Leaf Snowflake IDs  64bits   ------------------+
  |                                                                      |
  v                                                                      v
  0 0000000000 0000000000 0000000000 0000000000 0 0000000000 0000000000 00
  ^ ^                                           ^ ^        ^ ^           ^
  | |                                           | |        | |           |
  | +-------------------------------------------+ +--------+ +-----------+
Sign                    Time                       Worker id  Sequence number
1bit                   41bits                        10bits       12bits

翻了一圈,这玩意是看到最多的,只要提及 Snowflakes 就会带上它

早期的Leaf采用的是发号模式,提前分配一批id,分布式的系统取得id使用,发完再取,为了解决取号这个空档不可用的问题,美团人提出了双Buffer优化,使用另一个线程提前取号,确保当前一批id用完以后还能有号可取

上面扯远了,跟 Snowflakes 没太大关系,Leaf的Snowflake模式跟Twitter一致,不过使用Zookeeper进行机器码派号,本地缓存这个机器号(被称为 workerID),同时使用一套操作判断时钟是否准确,不准确直接抛出错误,反正高可用又不等于一定可用

百度UidGenerator

  +--------------------    UidGenerator IDs  64bits    ------------------+
  |                                                                      |
  v                                                                      v
  0 0000000000 0000000000 00000000 0000000000 0000000000 00 0000000000 000
  ^ ^                            ^ ^                      ^ ^            ^
  | |                            | |                      | |            |
  | +----------------------------+ +----------------------+ +------------+
Sign         Delta seconds                 Worker id        Sequence number
1bit             28bits                     22bits               13bits

百度人觉得未来自然会有解决办法,时间上问题不大,所以大刀一挥砍掉了时间上的毫秒位,精确到秒(28 bits),于是这个 UidGenerator 可以用8.7年,不过这玩意可以自行分配各项的位数

关于UID比特分配的建议 对于并发数要求不高、期望长期使用的应用, 可增加timeBits位数, 减少seqBits位数. 例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为12次/天, 那么配置成{"workerBits":23,"timeBits":31,"seqBits":9}时, 可支持28个节点以整体并发量14400 UID/s的速度持续运行68年.

对于节点重启频率频繁、期望长期使用的应用, 可增加workerBitstimeBits位数, 减少seqBits位数. 例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为24*12次/天, 那么配置成{"workerBits":27,"timeBits":30,"seqBits":6}时, 可支持37个节点以整体并发量2400 UID/s的速度持续运行34年.

剩下的部分跟美团Leaf差不多,就不重复了

Sonyflake

  +--------------------      Sonyflake IDs  64bits     -----------------+
  |                                                                     |
  v                                                                     v
  0 0000000000 0000000000 0000000000 000000000 00000000 0000000000 000000
  ^ ^                                        ^ ^      ^ ^               ^
  | |                                        | |      | |               |
  | +----------------------------------------+ +------+ +---------------+
Sign                    Time                Sequence number   Machine id   
1bit                   39bits                    8bits          16bits     

跟前面两者用java不同,这玩意是用go写的

索尼也觉得用到毫秒太浪费了,所以时间码只精确到 10ms,可用年限瞬间来到了174年,也许这就是日企百年如一日的坚守吧

接下来的8bits用作顺序数,为什么顺序数摆在中间?他们没说,反正能用就行

节省下来的空间分配给机器id,默认的机器id为内网IP地址的低16位,很简单粗暴。

那索尼怎么解决时钟回拨问题?等就完事了

// NextID generates a next unique ID.// After the Sonyflake time overflows, NextID returns an error.func (sf *Sonyflake) NextID() (uint64, error) {    const maskSequence = uint16(1<<BitLenSequence - 1)    sf.mutex.Lock()    defer sf.mutex.Unlock()    current := currentElapsedTime(sf.startTime)    if sf.elapsedTime < current {        sf.elapsedTime = current        sf.sequence = 0    } else { // sf.elapsedTime >= current        sf.sequence = (sf.sequence + 1) & maskSequence        if sf.sequence == 0 {            sf.elapsedTime++            overtime := sf.elapsedTime - current            time.Sleep(sleepTime((overtime)))        }    }    return sf.toID()}

自制

既然有那么多的变种,我们也可以仿造一个这种id实现

时间为和机器id都可以实时生成或者静态保存,但最后的顺序数是需要有地方解决自增问题的,上面那些用java或者golang的都有运行状态,可我一个写PHP哪来的状态?虽然session可行,但是考虑到自增、重置、高并发等需求,我还是找来了Redis,用上了Redis的INCR命令,利用Redis单线程的特性取得一个自增的值,还能够设定有效时间,到期重置,简直完美。你说Redis挂了怎么办?那是另一个问题了

其实我是在思考next.js自带的那个api后端该怎么保存顺序数时翻到Spring那个叫RedisAtomicLong的类,然后靠这个类的实现方法想到的

其他

当然,研究这些都只是个人喜好,一般的项目也遇不上超高并发的情况,在这个后端人均秒杀商城的时代,应该没太多人全部都自己折腾吧……也许

n9语录

n9语录

相关链接


评论区