Design Unique ID Generator

Design Unique ID Generator

Requirement clarification

Function requirement

  • IDs must be unique 全局唯一

  • ID will be numerical values only

  • length 64 bit 尽可能短

  • need to be incremental，按照时间粗略有序

现实中很多业务都有生成唯一 ID 的需求，例如：用户 ID, 微博 ID, 聊天消息 ID, 帖子 ID, 订单 ID。

Design a system that can generate a unique identifier for users when they join a platform like Twitter, This twitter will support around 1 billion users in its lifespan, additionally, you will expect requests for unique id to occur concurrently, 就是同一个时间需要返回多个 GUID (global unique identifier) or UUID (universal unique identifier)

Scale of the system - data size

估算 url 长度

我们前面已经估算过我们需要 1 Billion 的 unique url （地球上有70亿人，70 billion）。我们先要做估算看我们需要长度为多少的 short url。

因为我们有 10 个数字，所以 base 10:

10^1=10          
10^2=100    
10^3= 1000  
10^4=10000
10^5=100000  
   …  
10^9 = 1 billion
10^10 = 10 billion > 1 billion

所以我们需要 10 位的 base 10 长度就够了.

估算 TPS

TPS=1010/5年/365天/24小时/3600秒=7req/secTPS = 10^10 / 5 年 / 365 天 / 24 小时 / 3600 秒 = 7 req/sec

我们做这个 tps 估算的目的是用 round robin 去做 server 的时候计算数量。

API design

GET /v1/uuid

Database

  • 如果使用的是 range assignment, 给个 mysql 来 acid 保存哪些区间被使用过了

  • 使用 auto_increase 的时候也可以用 PostgreSQL

几种 high level 的方法来 generate unique id

Ticket Servers

Flickr is using it. Reading this doc.

  • 通过数据库（比如 MySQL）的 auto_increment 功能来实现

  • 如果有 k 台机器，我们就让每个机器自增 k

假如有 3 台机器：

machine 1： 1，4，7，...
machine 2： 2，5，8，...
machine 3： 3，6，9，...

  • 在 MySQL 前放一个 round-robin LB，每次来一个 request，随机地将请求发给任意一台机器，然后返回一个 ID。

Flickr 就是这么做的，仅仅使用了两台 MySQL 服务器。可见这个方法虽然简单无脑，但是性能足够好。不过要注意，在 MySQL 中，不需要把所有 ID 都存下来，每台机器只需要存一个 MAX_ID 就可以了。这需要用到 MySQL 的一个 REPLACE INTO 特性。

  • 缺点：这个方法跟单台数据库比，缺点是 ID 是不是严格递增的，只是粗略递增的。因为不过这个问题不大，我们的目标是粗略有序，不需要严格递增。

Range Server

  • 如果不要求有序，但是又要避免前面由于 NTP (Network Time protocol) 导致的 clock drift (这里指的是如果前面只依赖于 clock 不加入其它的机器 id 和 sequenceID 等)

  • 我们有一个 RangeKeeper server, 每次分发 10 万个 id 给来要的 id server。

    • id server 拿到这个 range 之后开始进行 id 产生和 hash 加密；

    • application server 来 call id server 拿到 id；

    • 然后 id server 用完这 10 万个名额之后再去找 RangeKeeper server 要.

  • RangeKeeper 可以把谁用了那个区间的数字放到 SQL DB 中，因为本身更新地也不会特别频繁。

  • RangeKeeper 可以选用 Apache Zookeeper。

直接使用 UUID

example：3F2504E0-4F89-11D3-9A0C-0305E82C3301

  • Universally Unique IDentifier (UUID)，有着正儿八经的 RFC 规范，是一个 128bit 的数字，也可以表现为 32 个 16 进制的字符，中间用 "-" 分割

    • 时间戳 ＋ UUID 版本号，分三段占 16 个字符 (60 bit + 4bit)，

    • Clock Sequence 号与保留字段，占 4 个字符(13 bit ＋ 3 bit)，

    • 节点标识占 12 个字符 (48 bit)

  • Pro:

    • 不需要担心 distributed collision, 1秒产生1百万个，产生100年也只有1个 collison 有 50% 机会产生，非常好 scale

  • Con:

    • 太长了 128 bit, 而且有字母

    • 没有 increment 顺序大小，不好排序

Twitter Snowflake - (UUID modified version)

一共 64 位：0 - 41位时间戳 - 5位数据中心标识 - 5位机器标识 - 12位序列号

  • 1 位，不用。二进制中最高位为 1 的都是负数，但是我们生成的 id 一般都使用整数，所以这个最高位固定是 0

  • 41 位，用来记录时间戳（毫秒）。

    • 41 位可以表示 2^41−1 个数字，如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 2^41−1，减 1 是因为可表示的数值范围是从 0 开始算的，而不是 1。

    • 也就是说 41 位可以表示 2^41−1 个毫秒的值，转化成单位年则是 (2^41−1)/(1000∗60∗60∗24∗365) = 69年

  • 10 位，用来记录工作机器 id。

    • 可以部署在 2^10=1024 个节点，包括 5 位 datacenterId 和5位 workerId

    • 5位（bit）可以表示的最大正整数是 2^5−1=31，即可以用 0、1、2、3、....31 这 32 个数字，来表示不同的 datecenterId 或 workerId

  • 12 位，序列号，用来记录同毫秒内产生的不同 id。

    • 12位（bit）可以表示的最大正整数是 2^12−1=4095，即可以用 0、1、2、3、....4094 这 4095 个数字，来表示同一机器同一时间截（毫秒)内产生的4095 个 ID 序号

    • 由于在 Java 中 64bit 的整数是 long 类型，所以在 Java 中 SnowFlake算法生成的 id 就是 long 来存储的。

41 位时间戳的部分可以转化为 epoch time 来用机器时间 clock

follow up: 如果多台机器时间不定，发生了 NTP(Network Time Protocol)

NTP keeps clock on multiple servers aligned since clocks can naturally drift, 就会导致我们产生了出了一些未来的时间，sync 时间后再次产生。

解决方式：见 range server solution，牺牲了sort。

Instagram ID - (UUID modified version)

Reading this doc.

Each of our IDs consists of:

  • 41 bits for time in milliseconds (gives us 41 years of IDs with a custom epoch)

  • 13 bits that represent the logical shard ID

  • 10 bits that represent an auto-incrementing sequence, modulus 1024. This means we can generate 1024 IDs, per shard, per millisecond

41 位表示时间戳，13 位表示 shard Id(一个shard Id对应一台PostgreSQL机器),最低 10 位表示自增 ID，怎么样，跟 Snowflake 的设计非常类似吧。这个方案用一个 PostgreSQL 集群代替了 Twitter Snowflake 集群，优点是利用了现成的PostgreSQL，容易懂，维护方便。

有的面试官会问，如何让 ID 可以粗略的按照时间排序？上面的这种格式的 ID，含有时间戳，且在高位，恰好满足要求。如果面试官又问，如何保证ID严格有序呢？在分布式这个场景下，是做不到的，要想高性能，只能做到粗略有序，无法保证严格有序。

不同 UUID 衍生版本的比较

Version1 变种 – Hibernate

Hibernate 的 CustomVersionOneStrategy.java，解决了之前 version 1 的两个问题

  • 时间戳(6bytes, 48bit)：毫秒级别的，从 1970 年算起，能撑 8925 年….

  • 顺序号(2bytes, 16bit, 最大值65535): 没有时间戳过了一秒要归零的事，各搞各的，short 溢出到了负数就归 0

  • 机器标识(4bytes 32bit): 拿 localHost 的 IP 地址，IPV4 正好 4 个 byte，但如果是 IPV6 要 16 个 bytes，就只拿前 4 个 byte。

  • 进程标识(4bytes 32bit)： 用当前时间戳右移 8 位再取整数应付，不信两条线程会同时启动。

Version1变种 – MongoDB

MongoDB 的 ObjectId.java

  • 时间戳(4bytes 32bit): 是秒级别的，从 1970 年算起，能撑 136 年。

  • 自增序列(3bytes 24bit, 最大值一千六百万)： 是一个从随机数开始（机智）的Int 不断加一，也没有时间戳过了一秒要归零的事，各搞各的。因为只有 3bytes，所以一个 4bytes 的 Int 还要截一下后 3bytes。

  • 机器标识(3bytes 24bit): 将所有网卡的 Mac 地址拼在一起做个 HashCode，同样一个 int 还要截一下后 3bytes。搞不到网卡就用随机数混过去。

  • 进程标识(2bytes 16bits)：从 JMX 里搞回来到进程号，搞不到就用进程名的hash 或者随机数混过去。 可见，MongoDB 的每一个字段设计都比 Hibernate 的更合理一点，比如时间戳是秒级别的。总长度也降到了12 bytes 96bit，但如果用 64bit 长的 Long 来保存有点不上不下的，只能表达成 byte 数组或 16 进制字符串。

另外对 Java 版的 driver 在自增序列那里好像有bug。

Summary

PreviousDesigning a URL Shortening service like TinyURLNextDesigning Pastebin

Last updated