超高性能且不受时间回拨影响的全局唯一 ID 生成算法,即薄雾算法
薄雾算法是不同于 snowflake 的全局唯一 ID 生成算法。相比 snowflake ,薄雾算法具有更高的数值上限和更长的使用期限。
现在薄雾算法拥有比雪花算法更高的性能!
用到全局唯一 ID 的场景不少,这里引用美团 Leaf 的场景介绍:
在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一个唯一 ID 来标识一条数据或消息,数据库的自增 ID 显然不能满足需求;特别一点的如订单、骑手、优惠券也都需要有唯一 ID 做标识。此时一个能够生成全局唯一ID 的系统是非常必要的。
引用微信 seqsvr 的场景介绍:
微信在立项之初,就已确立了利用数据版本号实现终端与后台的数据增量同步机制,确保发消息时消息可靠送达对方手机。
爬虫数据服务的场景介绍:
数据来源各不相同,且并发极大的情况下难以生成统一的数据编号,同时数据编号又将作为爬虫下游整个链路的溯源依据,在爬虫业务链路中十分重要。
这里参考美团 Leaf 的要求:
1、全局唯一性:不能出现重复的 ID 号,既然是唯一标识,这是最基本的要求;
2、趋势递增:在 MySQL InnoDB 引擎中使用的是聚集索引,由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能;
3、单调递增:保证下一个 ID 一定大于上一个 ID,例如事务版本号、IM 增量消息、排序等特殊需求;
4、信息安全:如果 ID 是连续的,恶意用户的爬取工作就非常容易做了,直接按照顺序下载指定 URL 即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要 ID 无规则、不规则;
可以用“全局不重复,不可猜测且呈递增态势”这句话来概括描述要求。
薄雾算法采用了与 snowflake 相同的位数——64,在考量业务场景和要求后并没有沿用 1-41-10-12 的占位,而是采用了 1-47-8-8 的占位。即:
* 1 2 48 56 64
* +------+-----------------------------------------------------+----------+----------+
* retain | increas | salt | salt |
* +------+-----------------------------------------------------+----------+----------+
* 0 | 0000000000 0000000000 0000000000 0000000000 0000000 | 00000000 | 00000000 |
* +------+-----------------------------------------------------+------------+--------+薄雾自增数为 1~10 的运行结果类似如下:
171671
250611
263582
355598
427749
482010
581550
644278
698636
762474根据运行结果可知,薄雾算法能够满足“全局不重复,不可猜测且呈递增态势”的场景要求。
snowflake 是由 Twitter 公司提出的一种全局唯一 ID 生成算法,它具有“递增态势、不依赖数据库、高性能”等特点,自 snowflake 推出以来备受欢迎,算法被应用于大大小小公司的服务中。snowflake 高位为时间戳的二进制,遂完全受到时间戳的影响,倘若时间回拨(当前服务器时间回到之前的某一时刻),那么 snowflake 有极大概率生成与之前同一时刻的重复 ID,这直接影响整个业务。
snowflake 受时间戳影响,使用上限不超过 70 年。
薄雾算法 Mist 由书籍《Python3 反爬虫原理与绕过实战》的作者韦世东综合 百度 UidGenerator、 美团 Leaf 和 微信序列号生成器 seqsvr 中介绍的技术点,同时考虑高性能分布式序列号生成器架构后设计的一款“递增态势、不依赖数据库、高性能且不受时间回拨影响”的全局唯一序列号生成算法。
薄雾算法不受时间戳影响,受到数值大小影响。薄雾算法高位数值上限计算方式为`int64(1 性能实验:采用时间戳种子随机方法时性能约为 8800 ns/op,采用大数真随机方法时性能约为 335 ns/op,采用常数时性能约为 15 ns/op
暂无开放 Issues,或尚未同步最近议题。