器→工具, 开源项目, 术→技巧, 研发

分布式全局唯一ID生成方案

钱魏Way · · 0 次浏览

在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。对数据分库分表后需要有一个唯一ID来标识一条数据或消息,数据库的自增ID显然不能满足需求此时一个能够生成全局唯一ID的系统是非常必要的。概括下来,那业务系统对ID号的要求有哪些呢?

  • 全局唯一性:不能出现重复的ID号。
  • 趋势递增:在MySQL InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
  • 单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
  • 信息安全:如果ID是连续的,恶意用户的抓取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞争对手可以直接知道一天的单量。所以在一些应用场景下,会需要ID无规则、不规则。

以业务端对订单号的需求为例:

  • 订单号不能重复
  • 订单号没有规则,即编码规则不能加入任何和公司运营相关的数据,外部人员无法通过订单ID猜测到订单量。不能被遍历。
  • 订单号长度固定,且不能太长
  • 易读,易沟通,不要出现数字字母换乱现象
  • 能够快速生成

常见全局唯一ID方案:

数据库自增长ID

优点:

  • 无需编码

缺点:

  • 大表不能做水平分表,否则插入删除时容易出现问题
  • 高并发下插入数据需要加入事务机制
  • 在业务操作父、子表(关联表)插入时,先要插入父表,再插入子表

Redis自增长ID

Redis来生成分布式ID,其实和利用Mysql自增ID类似,可以利用Redis中的incr命令来实现原子性的自增与返回,比如:

127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id      // 增加1,并返回
(integer) 2
127.0.0.1:6379> incr seq_id      // 增加1,并返回
(integer) 3

使用Redis的效率是非常高的,但是要考虑持久化的问题。Redis支持RDB和AOF两种持久化的方式。

  • RDB持久化相当于定时打一个快照进行持久化,如果打完快照后,连续自增了几次,还没来得及做下一次快照持久化,这个时候Redis挂掉了,重启Redis后会出现ID重复。
  • AOF持久化相当于对每条写命令进行持久化,如果Redis挂掉了,不会出现ID重复的现象,但是会由于incr命令过得,导致重启恢复数据时间过长。

优点:

  • 有序递增,可读性强。

缺点:

  • 占用带宽,每次要向Redis进行请求。

时间戳+随机数

优点:

  • 编码简单

缺点:

  • 随机数存在重复问题,即使在相同的时间戳下。每次插入数据库前需要校验下是否已经存在相同的数值。

时间戳+会员ID

优点:

  • 同一时间,一个用户不会存在两张订单

缺点:

  • 会员ID也会透露运营数据,鸡生蛋,蛋生鸡的问题

UUID/GUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,示例:550e8400-e29b-41d4-a716-446655440000,到目前为止业界一共有5种方式生成UUID,详情见IETF发布的UUID规范 A Universally Unique IDentifier (UUID) URN Namespace

优点:

  • 简单
  • 性能非常高:本地生成,没有网络消耗。

缺点:

  • 用户不友好
  • 不易于存储:UUID太长,16字节128位,通常以36长度的字符串表示,很多场景不适用。
  • 信息不安全:基于MAC地址生成UUID的算法可能会造成MAC地址泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
  • ID作为主键时在特定的环境会存在一些问题,比如做DB主键的场景下,UUID就非常不适用:
    • MySQL官方有明确的建议主键要尽量越短越好,36个字符长度的UUID不符合要求。
    • 对MySQL索引不利:如果作为数据库主键,在InnoDB引擎下,UUID的无序性可能会引起数据位置频繁变动,严重影响性能。

UUID变种

UUID变种比较流行的是基于MySQL UUID的变种:timestamp + machine number + random,具体介绍见:GUID/UUID Performance Breakthrough

优点:

  • 开发成本较低

缺点:

  • 基于MySQL的存储过程,性能较差

另外,随着UUID_TO_BIN(str, swap_flag)方法的出现,以上实现方式已不太适用。

Snowflake

Snowflake是由Twitter开源的全局唯一ID生成方案。Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。Snowflake算法核心把时间戳,工作机器id,序列号(毫秒级时间41位+机器ID 10位+毫秒内序列12位)组合在一起。

在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。

除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年,10bit的工作机器id可以支持1023台机器,序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

严格意义上来说工作机器id这个bit段的使用可以是进程级,机器级的话你可以使用MAC地址来唯一标示工作机器,工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少,可以使用配置文件来设置这个id是一个不错的选择,如果机器过多配置文件的维护是一个灾难性的事情。

这里的解决方案是需要一个工作id分配的进程,可以使用自己编写一个简单进程来记录分配id。

工作进程与工作id分配器只是在工作进程启动的时候交互一次,然后工作进程可以自行将分配的id数据落文件,下一次启动直接读取文件里的id使用。这个工作机器id的bit段也可以进一步拆分,比如用前5个bit标记进程id,后5个bit标记线程id之类。

序列号就是一系列的自增id(多线程建议使用atomic),为了处理在同一毫秒内需要给多条消息分配id,若同一毫秒把序列号用完了,则“等待至下一毫秒”。

Snowflake大致来说是一种以划分命名空间(UUID也算,由于比较常见,所以单独分析)来生成ID的一种算法,这种方案把64-bit分别划分成多段:timestamp + work number + seq number,分开来标示机器、时间等。

优点:

  • 毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。
  • 不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。
  • 可以根据自身业务特性分配bit位,非常灵活。

缺点:

  • 强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。
  • 需要引入zookeeper 和独立的snowflake专用服务器

具体实现除了官方的Scala版本外,还有以下选择:

Snowflake变种

snowflake的算法还是不错的,其实本身不复杂,复杂的是你客户端怎么用。遇到的问题如下:

  • 代码部署在不同的服务器上,中间的机器ID如何设置,有没有更方便的获取机器ID的方式?
  • 整个算法依赖时间的连续性,但是显示环境是线上服务器都开启了ntp,ntp情况下会出现时间倒退的问题。

Snowflake 生成的 unique ID 过程:

  • 10 bits 的机器号, 在 ID 分配 Worker 启动的时候, 从一个 Zookeeper 集群获取 (保证所有的 Worker 不会有重复的机器号)
  • 41 bits 的 Timestamp: 每次要生成一个新 ID 的时候, 都会获取一下当前的 Timestamp, 然后分两种情况生成 sequence number:
  • 如果当前的 Timestamp 和前一个已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一个 ID 的 sequence number + 1 作为新的 sequence number (12 bits); 如果本毫秒内的所有 ID 用完, 等到下一毫秒继续 (这个等待过程中, 不能分配出新的 ID)
  • 如果当前的 Timestamp 比前一个 ID 的 Timestamp 大, 随机生成一个初始 sequence number (12 bits) 作为本毫秒内的第一个 sequence number

整个过程中, 只是在 Worker 启动的时候会对外部有依赖 (需要从 Zookeeper 获取 Worker 号), 之后就可以独立工作了, 做到了去中心化.

异常情况讨论:

  • 在获取当前 Timestamp 时, 如果获取到的时间戳比前一个已生成 ID 的 Timestamp 还要小怎么办? Snowflake 的做法是继续获取当前机器的时间, 直到获取到更大的 Timestamp 才能继续工作 (在这个等待过程中, 不能分配出新的 ID)

从这个异常情况可以看出, 如果 Snowflake 所运行的那些机器时钟有大的偏差时, 整个 Snowflake 系统不能正常工作 (偏差得越多, 分配新 ID 时等待的时间越久)。从 Snowflake 的官方文档 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明确要求 “You should use NTP to keep your system clock accurate”. 而且最好把 NTP 配置成不会向后调整的模式. 也就是说, NTP 纠正时间时, 不会向后回拨机器时钟。

解决时间同步问题

为了解决上述的时间问题,可以采取的方案:

import java.security.SecureRandom;
 
/**
 * 自定义 ID 生成器
 * ID 生成规则: ID长达 64 bits
 * 
 * | 41 bits: Timestamp (毫秒) | 3 bits: 区域(机房) | 10 bits: 机器编号 | 10 bits: 序列号 |
 */
public class CustomUUID {
    // 基准时间
    private long twepoch = 1288834974657L; //Thu, 04 Nov 2010 01:42:54 GMT
    // 区域标志位数
    private final static long regionIdBits = 3L;
    // 机器标识位数
    private final static long workerIdBits = 10L;
    // 序列号识位数
    private final static long sequenceBits = 10L;
 
    // 区域标志ID最大值
    private final static long maxRegionId = -1L ^ (-1L << regionIdBits);
    // 机器ID最大值
    private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 序列号ID最大值
    private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    // 机器ID偏左移10位
    private final static long workerIdShift = sequenceBits;
    // 业务ID偏左移20位
    private final static long regionIdShift = sequenceBits + workerIdBits;
    // 时间毫秒左移23位
    private final static long timestampLeftShift = sequenceBits + workerIdBits + regionIdBits;
 
    private static long lastTimestamp = -1L;
 
    private long sequence = 0L;
    private final long workerId;
    private final long regionId;
 
    public CustomUUID(long workerId, long regionId) {
 
        // 如果超出范围就抛出异常
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");
        }
        if (regionId > maxRegionId || regionId < 0) {
            throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0");
        }
 
        this.workerId = workerId;
        this.regionId = regionId;
    }
 
    public CustomUUID(long workerId) {
        // 如果超出范围就抛出异常
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");
        }
        this.workerId = workerId;
        this.regionId = 0;
    }
 
    public long generate() {
        return this.nextId(false, 0);
    }
 
    /**
     * 实际产生代码的
     *
     * @param isPadding
     * @param busId
     * @return
     */
    private synchronized long nextId(boolean isPadding, long busId) {
 
        long timestamp = timeGen();
        long paddingnum = regionId;
 
        if (isPadding) {
            paddingnum = busId;
        }
 
        if (timestamp < lastTimestamp) {
            try {
                throw new Exception("Clock moved backwards.  Refusing to generate id for " + (lastTimestamp - timestamp) + " milliseconds");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        //如果上次生成时间和当前时间相同,在同一毫秒内
        if (lastTimestamp == timestamp) {
            //sequence自增,因为sequence只有10bit,所以和sequenceMask相与一下,去掉高位
            sequence = (sequence + 1) & sequenceMask;
            //判断是否溢出,也就是每毫秒内超过1024,当为1024时,与sequenceMask相与,sequence就等于0
            if (sequence == 0) {
                //自旋等待到下一毫秒
                timestamp = tailNextMillis(lastTimestamp);
            }
        } else {
            // 如果和上次生成时间不同,重置sequence,就是下一毫秒开始,sequence计数重新从0开始累加,
            // 为了保证尾数随机性更大一些,最后一位设置一个随机数
            sequence = new SecureRandom().nextInt(10);
        }
 
        lastTimestamp = timestamp;
 
        return ((timestamp - twepoch) << timestampLeftShift) | (paddingnum << regionIdShift) | (workerId << workerIdShift) | sequence;
    }
 
    // 防止产生的时间比之前的时间还要小(由于NTP回拨等问题),保持增量的趋势.
    private long tailNextMillis(final long lastTimestamp) {
        long timestamp = this.timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }
        return timestamp;
    }
 
    // 获取当前的时间戳
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

使用这种方法需要注意:

  • 为了保持增长的趋势,要避免有些服务器的时间早,有些服务器的时间晚,需要控制好所有服务器的时间,而且要避免NTP时间服务器回拨服务器的时间。
  • 在跨毫秒时,序列号总是归0,会使得序列号为0的ID比较多,导致生成的ID取模后不均匀,所以序列号不是每次都归0,而是归一个0到9的随机数。
  • 使用这个CustomUUID类,最好在一个系统中能保持单例模式运行。

解决分布式部署

Snowflake 有一些变种,各个应用结合自己的实际场景对 Snowflake 做了一些改动。

Boundary flake

变化:

  • ID 长度扩展到 128 bits
  • 最高 64 bits 时间戳
  • 然后是 48 bits 的 Worker 号 (和 Mac 地址一样长)
  • 最后是 16 bits 的 Seq Number
  • 由于它用 48 bits 作为 Worker ID,和 Mac 地址的长度一样,这样启动时不需要和 Zookeeper 通讯获取 Worker ID。做到了完全的去中心化。
  • 基于 Erlang

它这样做的目的是用更多的 bits 实现更小的冲突概率, 这样就支持更多的 Worker 同时工作。同时每毫秒能分配出更多的 ID。

Simpleflake

Simpleflake 的思路是取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits。

Simpleflake 的特点:

  • sequence number 完全靠随机产生 (这样也导致了生成的 ID 可能出现重复)
  • 没有 Worker 号, 也就不需要和 Zookeeper 通讯, 实现了完全去中心化
  • Timestamp 保持和 Snowflake 一致, 今后可以无缝升级到 Snowflake

Simpleflake 的问题就是 sequence number 完全随机生成, 会导致生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长。

所以Simpleflake 的限制就是每秒生成的 ID 不能太多(最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用了,建议切换回 Snowflake)。

MongoDB ObjectID

MongoDB官方文档 ObjectID可以算作是和snowflake类似方法,通过“时间+机器码+pid+inc”共12个字节,通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。相比snowflake长度及可读性要差一些。

百度 uid-generator

uid-generator使用的就是snowflake,只是在生产机器id,也叫做workId时有所不同。uid-generator中的workId是由uid-generator自动生成的,并且考虑到了应用部署在docker上的情况,在uid-generator中用户可以自己去定义workId的生成策略,默认提供的策略是:应用启动时由数据库分配。说的简单一点就是:应用在启动时会往数据库表(uid-generator需要新增一个WORKER_NODE表)中去插入一条数据,数据插入成功后返回的该数据对应的自增唯一id就是该机器的workId,而数据由host,port组成。对于uid-generator中的workId,占用了22个bit位,时间占用了28个bit位,序列化占用了13个bit位,需要注意的是,和原始的snowflake不太一样,时间的单位是秒,而不是毫秒,workId也不一样,同一个应用每重启一次就会消费一个workId。

美团 Leaf

美团的Leaf也是一个分布式ID生成框架。它非常全面,即支持号段模式,也支持snowflake模式。

号段模式可以理解成批量获取,比如DistributIdService从数据库获取ID时,如果能批量获取多个ID并缓存在本地的话,那样将大大提供业务应用获取ID的效率。比如DistributIdService每次从数据库获取ID时,就获取一个号段,比如(1,1000],这个范围表示了1000个ID,业务应用在请求DistributIdService提供ID时,DistributIdService只需要在本地从1开始自增并返回即可,而不需要每次都请求数据库,一直到本地自增到1000时,也就是当前号段已经被用完时,才去数据库重新获取下一号段。

Leaf中的snowflake模式和原始snowflake算法的不同点,也主要在workId的生成,Leaf中workId是基于ZooKeeper的顺序Id来生成的,每个应用在使用Leaf-snowflake时,在启动时都会都在Zookeeper中生成一个顺序Id,相当于一台机器对应一个顺序节点,也就是一个workId。

Flickr的数据库自增

Flickr是用的一个叫做Ticket Servers的玩意,使用纯MySQL来实现的。

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

先插入一条记录,然后再用replace去获取这个id

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

优点:

  • 非常简单,利用现有数据库系统的功能实现,成本小,有DBA专业维护。
  • ID号单调自增,可以实现一些对ID有特殊要求的业务。

缺点:

  • 强依赖DB,当DB异常时整个系统不可用,属于致命问题。配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
  • ID发号性能瓶颈限制在单台MySQL的读写性能。

对于MySQL性能问题,可用如下方案解决:在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。比如有两台机器。设置步长step为2,TicketServer1的初始值为1(1,3,5,7,9,11…)、TicketServer2的初始值为2(2,4,6,8,10…)

Instagram的存储过程

Instagram的ID生成方式简单的描述为:41b ts + 13b shard id + 10b increment seq,

  • 41 bits:Timestamp (毫秒)
  • 13 bits:每个 logic Shard 的代号 (最大支持8 * 1024个logic Shards)
  • 10 bits:sequence number,每个 Shard 每毫秒最多可以生成1024个ID

具体实现方式如下:

  • 先把每个 Table 划分为多个逻辑分片(logic Shard),逻辑分片的数量可以很大,例如2000个逻辑分片
  • 然后制定一个规则,规定每个逻辑分片被存储到哪个数据库实例上面;数据库实例不需要很多,例如对有 2 个 PostgreSQL 实例的系统(instagram 使用 PostgreSQL)可以使用奇数逻辑分片存放到第一个数据库实例,偶数逻辑分片存放到第二个数据库实例的规则
  • 每个 Table 指定一个字段作为分片字段(例如对用户表可以指定 uid 作为分片字段)
  • 插入一个新的数据时先根据分片字段的值,决定数据被分配到哪个逻辑分(logic Shard)
  • 然后再根据 logic Shard 和 PostgreSQL 实例的对应关系, 确定这条数据应该被存放到哪台 PostgreSQL 实例上

生成 unique ID 时41 bits 的 Timestamp 和 Snowflake 类似,这哭主要介绍一下 13 bits 的 logic Shard 代号 和 10 bits 的 sequence number 怎么生成。

logic Shard 代号:

  • 假设插入一条新的用户记录, 插入时, 根据 uid 来判断这条记录应该被插入到哪个 logic Shard 中.
  • 假设当前要插入的记录会被插入到第 1341 号 logic Shard 中 (假设当前的这个 Table 一共有 2000 个logic Shard)
  • 新生成 ID 的 13 bits 段要填的就是 1341 这个数字

sequence number 利用 PostgreSQL 每个 Table 上的 auto-increment sequence 来生成:

  • 如果当前表上已经有 5000 条记录, 那么这个表的下一个 auto-increment sequence 就是 5001 (直接调用 PL/PGSQL 提供的方法可以获取到)
  • 然后把这个 5001 对 1024 取模就得到了 10 bits 的 sequence number

Instagram 这个方案的优势在于:

  • 利用 logic Shard 号来替换 Snowflake 使用的 Worker 号就不需要到中心节点获取 Worker 号,做到了完全去中心化
  • 可以通过 ID 直接知道这条记录被存放在哪个 logic Shard 上
  • 今后做数据迁移的时候, 也是按 logic Shard 为单位做数据迁移的,也不会影响到今后的数据迁移

详细介绍见:Sharding & IDs at Instagram

优点:

  • 开发成本低

缺点:

  • 基于postgreSQL的存储过程,通用性差

发表评论

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