全局唯一ID生成方案对比

时间：2022-09-23 11:32:41

欢迎关注本人公众号

全局唯一ID生成方案对比



全局唯一ID生成方案对比

汇总了各大公司的全局唯一ID生成方案，并做了一个简单的优劣比较

背景：在实现大型分布式程序时，通常会有全局唯一ID（也成GUID）生成的需求，用来对每一个对象标识一个代号。本文就列举了博主收集的各种全局唯一ID生成的方案，做一个简单的类比和备忘。

GUID的基本需求

一般对于唯一ID生成的要求主要这么几点：

  • 毫秒级的快速响应
  • 可用性强
  • prefix有连续性方便DB顺序存储
  • 体积小，8字节为佳

业界成熟方案列举

目前看到过的唯一ID生成方法主要有以下几种：

各个方案优劣的对比

四种方案各有优劣，下面简要描述以下：

  • 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）。



欢迎关注本人公众号

全局唯一ID生成方案对比


标签：

相关文章