作为爬 Twitter 大军的一员，了解生成 tweet_id、uid 等纯数字id的 Snowflakes 是很有必要的。这篇东西我很早就想写了，只是一直在咕，从未开工。
被坑
刚做 Twitter Monitor 的时候，我是不了解这玩意的，对类型问题、溢出问题都是一知半解，因此在设计数据库结构时，tweet_id 和 uid 的类型只是一个 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台机器进来了。根据Reconstructing Twitter's Firehose，
Machine id还能细分为两部分：- 高5位为数据中心ID
- 低5位为服务器ID
- 剩下的12bit就是纯粹自增的顺序编号了
文字说明不清晰，我们来张图
+---------------------- Snowflake IDs 64bits ----------------------+
| |
| Machine id |
| 10 bits |
| +---------+ |
v v v v
0 0000000000 0000000000 0000000000 0000000000 0 00000 00000 0000000000 00
^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | |
| +-------------------------------------------+ +---+ +---+ +-----------+
Sign Time DCID SID Sequence number
1bit 41bits 5bits 5bits 12 bits
DCID = Datacenter id
SID = Server id
从这图我们就能看出 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年.
对于节点重启频率频繁、期望长期使用的应用, 可增加workerBits和timeBits位数, 减少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语录