常见的分布式Id生成器剖析

在高并发或者分表分库情况下怎么保证数据id的幂等性呢？

经常用到的解决方案有以下几种。

微软公司通用唯一识别码（UUID）
Twitter公司雪花算法（SnowFlake）
基于数据库的id自增
对id进行缓存

一、SnowFlake算法

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。

其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号，最后还有一个符号位，永远是0。

snowflake算法所生成的ID结构，如下图：

image.png

整个结构是64位，所以我们在Java中可以使用long来进行存储。

该算法实现基本就是二进制操作,单机每秒内理论上最多可以生成1024*(2^12)，也就是409.6万个ID(1024 X 4096 = 4194304)

• 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

• 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0

• 41位时间截(毫秒级)。注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)

• 这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69

• 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId

• 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

• 加起来刚好64位，为一个Long型。

• SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高

  经测试，SnowFlake每秒能够产生26万ID左右。

snowFlake算法的优点：

1. 生成ID时不依赖于DB，完全在内存生成，高性能高可用。

2. ID呈趋势递增，后续插入索引树的时候性能较好。

SnowFlake算法的缺点：

依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成ID冲突，或者ID乱序

二、基于数据库的id自增

image.png

字段说明：

• id代表该obj本次set后的maxid

• 不同业务不同的ID需求可以用obj字段区分，每个obj的ID获取相互隔离，互不影响

• step 步长，代表每次获取多长ID段到缓存

基本要求：

• 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求
• 趋势递增：在MySql InnoDB引擎使用的是聚集索引, 由于多数的RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上应该尽量使用有序的主键保证写入性能
• 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求
• 信息安全：如果ID是联系的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量。所以在这些场景下，会需要ID无规则，不规则。

性能要求：

• 平均延迟和TP999延迟都要尽可能低
• 可用性5个9（99.999%）
• 高QPS

优点：

• 支持全局唯一、系统唯一、表级别唯一三种形式，绝对不会出现重复ID，且ID整体趋势递增；
• 大大的降低了数据库的压力，ID生成可以做到每秒生成几万几十万个
• 一定的高可用，服务采用预分配ID的方案，每次调用分配10000个id到系统缓存集群，即使MySQL宕机，也能容忍一段时间数据不可用；
• 接入简单，直接通过公司的RPC服务或者HTTP调用即可使用;

缺点：

• 强依赖数据库，当MySQL服务长时间不可用，那么对公司业务将是一场灾难；

• 并发性能较低，假设公司业务量急剧增长，idgenerator服务请求并发量增高，而实际上在更新数据库时会触发表锁，可能造成ID获取失败,导致服务不可用;

• 缺少服务自身监控，无法通过web层的内存数据映射界面实时观测所有号段的下发状态及使用情况

• 服务仍然是单点

• 如果服务挂了，服务重启起来之后，继续生成ID可能会不连续，中间出现空洞（服务内存是保存着0,1,2,3,4,5，数据库中max-id是5，分配到3时，服务重启了，下次会从6开始分配，4和5就成了空洞，不过这个问题也不大）

• 虽然每秒可以生成几万几十万个ID，但毕竟还是有性能上限，无法进行水平扩展

三、UUID

UUID 是指Universally Unique Identifier，翻译为中文是通用唯一识别码，UUID 的目的是让分布式系统中的所有元素都能有唯一的识别信息。如此一来，每个人都可以创建不与其它人冲突的 UUID，就不需考虑数据库创建时的名称重复问题。

定义

UUID 是由一组32位数的16进制数字所构成，是故 UUID 理论上的总数为1632=2128，约等于3.4 x 10123。

也就是说若每纳秒产生1百万个 UUID，要花100亿年才会将所有 UUID 用完

格式

UUID 的十六个八位字节被表示为 32个十六进制数字，以连字号分隔的五组来显示，形式为 8-4-4-4-12，总共有 36个字符（即三十二个英数字母和四个连字号）。例如：

123e4567-e89b-12d3-a456-426655440000

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

数字 M的四位表示 UUID 版本，当前规范有5个版本，M可选值为1, 2, 3, 4, 5 ；

数字 N的一至四个最高有效位表示 UUID 变体( variant )，有固定的两位10xx因此只可能取值8, 9, a, b

UUID版本通过M表示，当前规范有5个版本，M可选值为1, 2, 3, 4, 5。这5个版本使用不同算法，利用不同的信息来产生UUID，各版本有各自优势，适用于不同情景。具体使用的信息

• version 1, date-time & MAC address
• version 2, date-time & group/user id
• version 3, MD5 hash & namespace
• version 4, pseudo-random number
• version 5, SHA-1 hash & namespace

使用较多的是版本1和版本4，其中版本1使用当前时间戳和MAC地址信息。版本4使用(伪)随机数信息，128bit中，除去版本确定的4bit和variant确定的2bit，其它122bit全部由(伪)随机数信息确定。

因为时间戳和随机数的唯一性，版本1和版本4总是生成唯一的标识符。若希望对给定的一个字符串总是能生成相同的 UUID，使用版本3或版本5。

随机 UUID 的重复机率

Java中 UUID 使用版本4进行实现，所以由 java.util.UUID类产生的 UUID，128个比特中，有122个比特是随机产生，4个比特标识版本被使用，还有2个标识变体被使用。利用 生日悖论，可计算出两笔 UUID 拥有相同值的机率约为

image

其中x为 UUID 的取值范围，n为 UUID 的个数。

以下是以 x = 2122 计算出n笔 UUID 后产生碰撞的机率：

n	机率
68,719,476,736 = 236	0.0000000000000004 (4 x 10-16)
2,199,023,255,552 = 241	0.0000000000004 (4 x 10-13)
70,368,744,177,664 = 246	0.0000000004 (4 x 10-10)

换句话说，每秒产生10亿笔 UUID ，100年后只产生一次重复的机率是50%。如果地球上每个人都各有6亿笔 UUID，发生一次重复的机率是50%。与被陨石击中的机率比较的话，已知一个人每年被陨石击中的机率估计为170亿分之1，也就是说机率大约是0.00000000006 (6 x 10-11)，等同于在一年内生产2000亿个 UUID 并发生一次重复。

参考文档：

• 1. 雪花算法(Twitter ): https://github.com/souyunku/SnowFlake
• 2. Tinyid（滴滴）: https://github.com/didi/tinyid
• 3. https://tech.meituan.com/2017/04/21/mt-leaf.html
• 4. UidGenerator(百度)： https://github.com/baidu/uid-generator
• 5. Leaf (美团)： https://github.com/Meituan-Dianping/Lea