背景

过去的项目开发中，我们常常选用的数据库是 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（最大支持 25＝32 个，原理同 datacenterId），所以 datacenterId*workerId 最多支持部署 1024 个节点，最后 12 位是毫秒内的计数（12 位的计数顺序号支持每个节点每毫秒产生 212＝4096 个 ID 序号）。}

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

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

优缺点

优点：
趋势递增：毫秒数在高位，序列号在低位
性能高无单点：本地计算不依赖数据库等第三方
使用灵活：三个组成部分的位数可按需求调整

缺点：
序列不连续
无法控制生成规则（比如序列起始等）
强依赖机器时钟，如果时钟回拨，会导致序列重复或者系统不可用

实现代码

Python 版实现代码如下所示（仅供参考）

#coding: utf-8
import datetime
# 起始时间, 不能改变, 2020-04-10
twepoch = 1586448000000
datacenter_id_bits = 5
worker_id_bits = 15
sequence_id_bits = 2
max_datacenter_id = 1 << datacenter_id_bits
max_worker_id = 1 << worker_id_bits
max_sequence_id = 1 << sequence_id_bits
max_timestamp = 1 << (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) << datacenter_id_bits << worker_id_bits << sequence_id_bits
    sid += (datacenter_id % max_datacenter_id) << worker_id_bits << sequence_id_bits
    sid += (worker_id % max_worker_id) << sequence_id_bits
    sid += sequence_id % max_sequence_id

我们的服务在部署中，由于采用的是单机部署模式，所以将 ID 的生成部分加入到了程序代码中。如果是多机部署模式，Snowflake 唯一 ID 的生成，常常部署一个独立的服务，需要 ID 的时候，来请求该服务获取。

效果

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

总结

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