分布式自增 ID 算法 Snowflake 简介

2022 年 9 月 29 日
北京
本文字数：1469 字
阅读完需：约 5 分钟

背景

过去的项目开发中，我们常常选用的数据库是 mysql，mysql 以其体积小、速度快等优势，备受中小型项目的青睐。随着项目数据量的迅速增长，mysql 已无法满足我们的项目需求，数据迁移迫在眉睫。经多方对比综合考虑，我们选择了 tidb 分布式数据库。但是数据迁移后我们遇到一个问题，之前 mysql 数据库中，我们采用的是自增 id 主键，可选用的 tidb 又对自增主键不是很友好，所以我们选用了另一种主键生成方式：Snowflake 算法。

算法原理

SnowFlake 算法是 Twitter 设计的一个可以在分布式系统中生成唯一的 ID 的算法，它可以满足每秒上万条消息 ID 分配的请求，这些消息 ID 是唯一的且有大致的递增顺序。

SnowFlake 算法产生的 ID 是一个 64 位的整型，结构如下：

第一位是标识位，一般不使用，接下来的 41 位为毫秒级时间差（以 1970 年为起始时间，41 位的长度可以使用 69 年，从 1970-01-01 08:00:00，年 = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69），然后是 5 位 datacenterId（最大支持 2^5＝32 个，二进制表示从 00000-11111，也即是十进制 0-31），和 5 位 workerId（最大支持 2^5＝32 个，原理同 datacenterId），所以 datacenterId*workerId 最多支持部署 1024 个节点，最后 12 位是毫秒内的计数（12 位的计数顺序号支持每个节点每毫秒产生 2^12＝4096 个 ID 序号）。

所有位数加起来共 64 位，恰好是一个 Long 型。

当然，实际使用过程中，时间戳、工作机 id、序列号的位数是可以根据需要调整的。

优缺点

优点：

趋势递增：毫秒数在高位，序列号在低位

性能高无单点：本地计算不依赖数据库等第三方

使用灵活：三个组成部分的位数可按需求调整

缺点：

序列不连续

无法控制生成规则（比如序列起始等）

强依赖机器时钟，如果时钟回拨，会导致序列重复或者系统不可用

实现代码

#coding: utf-8import datetime# 起始时间, 不能改变, 2020-04-10twepoch = 1586448000000datacenter_id_bits = 5worker_id_bits = 15sequence_id_bits = 2max_datacenter_id = 1 &lt;&lt; datacenter_id_bitsmax_worker_id = 1 &lt;&lt; worker_id_bitsmax_sequence_id = 1 &lt;&lt; sequence_id_bitsmax_timestamp = 1 &lt;&lt; (64 - datacenter_id_bits - worker_id_bits - sequence_id_bits)
def make_snowflake(timestamp_ms, datacenter_id, worker_id, sequence_id, twepoch=twepoch):    """generate a twitter-snowflake id, based on    :param timestamp_ms: time since UNIX epoch in milliseconds    :param datacenter_id: exec ip    :param worker_id: process id,max is 32767, min is 0    :param sequence_id: thread id, max is 3, min is 0    :param twepoch: start time stamp    :return:    """    sid = ((int(timestamp_ms) - twepoch) % max_timestamp) &lt;&lt; datacenter_id_bits &lt;&lt; worker_id_bits &lt;&lt; sequence_id_bits    sid += (datacenter_id % max_datacenter_id) &lt;&lt; worker_id_bits &lt;&lt; sequence_id_bits    sid += (worker_id % max_worker_id) &lt;&lt; sequence_id_bits    sid += sequence_id % max_sequence_id

复制代码

效果

采用 Snowflake 算法后，数据 id 可以保持时间递增并且全局唯一。

总结

Snowflake 是分布式系统中，用来生成全局唯一 ID 的一种常用算法。和 UUID 相比，Snowflake 具有简单、占用空间小、有序等优点。但 Snowflake 算法也有它的弊端，时钟回拨、时钟错乱问题，将是我们程序中需要考虑的问题。

发布于: 刚刚阅读数: 4

测吧(北京)科技有限公司

关注

社区：ceshiren.com 2022.08.29 加入

微信公众号：霍格沃兹测试开发提供性能测试、自动化测试、测试开发等资料、实事更新一线互联网大厂测试岗位内推需求，共享测试行业动态及资讯，更可零距离接触众多业内大佬

发布

暂无评论

创作场景

分布式自增 ID 算法 Snowflake 简介

测吧(北京)科技有限公司

评论