如何生成全局唯一ID

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

前言

在分布式环境中，生成全局唯一ID是非常需求。本文将介绍几种常见生成方法，并对它们的优缺点做出点评。

0. 8个字节

语言或数据库	内建类型
Golang	uint64
Java	long
Python	int
MySQL	bigint unsigned

2 ^ 32（4个字节）最多只有40多亿，对于高并发的系统，肯定不是够的。
以新浪微博为例，每天的新增的微博量都过亿，所以考虑到ID的容量，这个ID的长度至少是8个字节

1. UUID

长度: 为16 bytes, 128 bits
44e91a8a58d111e8ae84784f43a6cab8

见参考资料1：
5种版本
1. 时间的版本
2. DCE Security
3. MD5哈希
4. (伪)随机数
5. SHA-1哈希

以Version 1为例子

time_inc + clk_seq + node

points

1. time_inc时间精度为100 ns
   即使在100ns以内，2次生成的time_inc也不会重复，因为会自动加1
2. clk_seq 为2个bytes一般是随机数（2 ^ 16 为65536）
   协议文档中写明，此字段可以用来防止时钟回拨，但是在高并发情况下，也很难保证不出现冲突。
3. node取mac地址

下面是python的uuid库生成的一组ID

a7748921-58d9-11e8-a727-784f43a6cab8
a70b016e-58d9-11e8-8a8c-784f43a6cab8
a6991957-58d9-11e8-8874-784f43a6cab8
a5b143ba-58d9-11e8-9600-784f43a6cab8

2. snowflake

长度: 8 bytes

216627617464324190

time + workerID + inc

points

1. time的精度是到毫秒
2. workerID的数量最大为1024，workerID的获取和分配可能比较麻烦
3. 1毫秒内生成的最大ID数量为2的12次方，约为4096
4. 时钟回拨会产生ID冲突
5. snowflake是由twitter提出的，在twitter中用于生成twitterID

3. Mongdb objectID

长度: 12 bytes
再按照16进制表示，如果是字符串占24个字节

time + machine + pid + inc

points

1. 为了降低Server端的压力, objectID是在客户端生成的
2. time的精度是到秒
3. machine 一般是机器主机名的散列值
4. 1秒内生成的最大ID数量为2的24次方，约为1600w

如果要冲突2种情况
1. 主机标识完全一样
2. 一秒内产生的ID要超过1600w
3. 时钟回拨会产生ID冲突

4. 数据库生成1.0

长度: 8 bytes
数据库中的表结构

CREATE TABLE `wuid1` (
    `h` bigint(10) unsigned NOT NULL AUTO_INCREMENT,
    `x` tinyint(4) NOT NULL DEFAULT '0',
    PRIMARY KEY (`x`),
    UNIQUE KEY `h` (`h`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

从数据库获取ID的高位

REPLACE INTO  wuid1(x) VALUES (0);
SELECT LAST_INSERT_ID();

注意 LAST_INSERT_ID()返回的是自增字段的最新值，它与具体的session相关，每个Session相互独立，因此无需使用事务

Points

• 生成速度取决于数据库速度，但至少可以达到1w/s

5. 数据库生成2.0

长度: 8 bytes
一次申请一个ID段，用完之后再重新申请
以edwingeng/wuid为例，它生成的ID为8 bytes(64 bits), 其中高24bits在数据库中维护，支持MySQL/Redis/MongoDB 三种数据库

数据库中的表结构

CREATE TABLE `wuid2` (
    `h` int(10) NOT NULL AUTO_INCREMENT,
    `x` tinyint(4) NOT NULL DEFAULT '0',
    PRIMARY KEY (`x`),
    UNIQUE KEY `h` (`h`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

从数据库获取ID的高位

REPLACE INTO  wuid2(x) VALUES (0);
SELECT LAST_INSERT_ID();

Points

• 生成速度可达1000w/s
• 在腾讯内部被用于生成微信ID
• 美团内部被使用生成

总结

• 其它生成ID的方法，还有很多，比如使用Redis，但是需要当心，Redis宕机以后，再次启动的起始数据的问题。

• 对ID唯一性要求更高的场景，比如业务订单ID，消息ID，建议使用方法4或者方法5，其它情况可以使用方法2或者方法1

• 另外由于UUID长度为16个字节，如果要存储入数据库，一般是保存它的16进制形式（32个字节）是以字符串形式保存，要考虑索引的开销和存储开销。

扩展思考

这几种方法生成的ID是否满足以下条件
1. 全局唯一性
2. 趋势递增
3. 单调递增
4. 信息安全

参考资料

1. uuid协议
2. Twitter-Snowflake，64位自增ID算法详解
3. Leaf——美团点评分布式ID生成系统
4. MongoDB深究之ObjectId
5. 微信序列号生成器架构设计及演变

---