分布式自增ID算法Snowflake简介

背景

过去的项目开发中，我们常常选用的数据库是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、序列号的位数是可以根据需要调整的。

优缺点

优点：

01

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

02

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

03

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

缺点：

01

序列不连续

02

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

03

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

实现代码

#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

效果

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

总结

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