Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | 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哈希

image_1cdjrrfvt1hhg14vcjfe1e7l1kp415.png-14.9kB

以Version 1为例子
image_1d5tpmfbm9icp6i3pj15d61uvfrd.png-14.1kB
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

image_1d5tppsg7e9c1aah1tk7j84ssbtk.png-53.1kB

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个字节

image_1d5tpohs1b1vfvckg11mjh7sbs7.png-60.3kB
image_1d5tpo1c7db817d9qfcai17h4rq.png-18.6kB

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 三种数据库

image_1d5tpr3vp15b9gglj111jis1q3ou1.png-10.2kB
数据库中的表结构

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. 微信序列号生成器架构设计及演变

微信公众号

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注