欢迎关注本人公众号
全局唯一ID生成方案对比
汇总了各大公司的全局唯一ID生成方案,并做了一个简单的优劣比较
背景:在实现大型分布式程序时,通常会有全局唯一ID(也成GUID)生成的需求,用来对每一个对象标识一个代号。本文就列举了博主收集的各种全局唯一ID生成的方案,做一个简单的类比和备忘。
GUID的基本需求
一般对于唯一ID生成的要求主要这么几点:
- 毫秒级的快速响应
- 可用性强
- prefix有连续性方便DB顺序存储
- 体积小,8字节为佳
业界成熟方案列举
目前看到过的唯一ID生成方法主要有以下几种:
- UUID 16字节
- Twitter的Snowflake 8字节
- Flikr的数据库自增 4/8字节
- Instagram的存储过程 8字节
- 基于MySQL UUID的变种 16字节
各个方案优劣的对比
四种方案各有优劣,下面简要描述以下:
- UUID:
- 优:java自带,好用。
- 劣:占用空间大
- Snowflake: timestamp + work number + seq number
- 优:可用性强,速度快
- 劣:需要引入zookeeper 和独立的snowflake专用服务器
- Flikr:基于int/bigint的自增
- 优:开发成本低
- 劣:如果需要高性能,需要专门一套MySQL集群只用于生成自增ID。可用性也不强
- Instagram:41b ts + 13b shard id + 10b increment seq
- 优: 开发成本低
- 劣: 基于postgreSQL的存储过程,通用性差
- UUID变种:timestamp + machine number + random (具体见:变种介绍
- 优: 开发成本低
- 劣: 基于MySQL的存储过程,性能较差
-
其他可参考链接:如何在高并发分布式系统中生成全局唯一Id
http://www.cnblogs.com/heyuquan/archive/2013/08/16/global-guid-identity-maxId.html
Twitter 早期用 MySQL 存储数据,随着用户的增长,单一的 MySQL 实例没法承受海量的数据,开发团队就开始用 Cassandra 和 sharded MySQL 替代原有的系统。然而和 MySQL 不同的是,Cassandra 没有内置为每一条数据生成唯一 ID 的功能,因为在一个分布式环境下,很难有完美的 ID 生成方案。
对于 Twitter 而言,这样的 ID 生成方案要满足两个基本的要求,一是每秒能生成几十万条 ID 用于标识不同的 tweet;二是这些 ID 应该可以有个大致的顺序,也就是说发布时间相近的两条 tweet,它们的 ID 也应当相近,这样才能方便各种客户端对 tweet 进行排序。
第一个要求意味着 ID 生成要以一种非协作的(uncoordinated)的方式进行,例如不能有一个全局的原子变量。
第二个要求使得 tweet 按 ID 排序后满足 k-sorted 条件。如果序列 A 要满足 k-sorted,当且仅当对于任意的 p, q,如果 1 <= p <= q - k (1 <= p <= q <= n),则有 A[p] <= A[q]。换句话说,如果元素 p 排在 q 前面,且相差至少 k 个位置,那么 p 必然小于或等于 q。如果 tweet 序列满足这个条件,要获取第 r 条 tweet 之后的消息,只要从第 r - k 条开始查找即可。
Twitter 解决这两个问题的方案非常简单高效:每一个 ID 都是 64 位数字,由时间戳、节点号和序列编号组成。其中序列编号是每个节点本地生成的序号,而节点号则由 ZooKeeper 维护。
具体的参数可以在这个 IdWorker.scala 中看到。序列编号有 12 位,意味着每个节点在每毫秒可以产生 4096 个 ID。节点号在源码中被分成两部分,数据中心的 ID 和节点 ID,各自占 5 位。时间戳则是记录了从 1288834974657 (Thu, 04 Nov 2010 01:42:54 GMT) 这一时刻到当前时间所经过的毫秒数,占 41 位(还有一位是符号位,永远为 0)。
欢迎关注本人公众号