欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

十种分布式ID生成方法

程序员文章站 2022-05-04 17:24:14
...

什么是分布式ID

以MySQL为例，数据量不大的时候，单库单表可以支撑现有业务，再大一点主从同步读写分离也可以。
但数据是不断增加的，当主从同步也不行了，就需要分库分表了。分库分表需要一个全局唯一ID做标识，这就是分布式ID。一个能生成分布式ID的系统是十分有必要的。

分布式ID特点

  • 全局唯一：基本要求
  • 高性能：高可用低延时，ID生成相应快，否则成为业务瓶颈；
  • 高可用：不能有单点故障
  • 好接入：在系统设计和实现上尽可能地简单；
  • 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，我们应该尽量使用有序的主键保证写入性能；
  • 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序。
  • 信息安全：在一些应用场景下，会需要ID无规则、不规则生成，例如订单号。
  • 分片支持：可以控制ShardingId。比如某一个用户的文章要放在同一个分片内，这样查询效率高，修改也容易。
  • 长度适中

生成方式

  1. UUID
  2. 数据库自增ID
  3. 数据库多主模式
  4. 数据库号段模式
  5. Redis
  6. 雪花算法（SnowFlake）
  7. 滴滴出品（TinyID）
  8. 百度（Uidgenerator）
  9. 美团（Leaf）
  10. zookeeper

1.UUID

UUID uuid=UUID.randomUUID();

UUID的标准形式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000。这种ID每个都是独一无二的，不用担心冲突问题。
优点：

  • 生成简单，本地生成无网络消耗，有唯一性

缺点：

  • 无序字符串，不具备趋势递增的特性；
  • 没有具体含义；
  • 长度过长对MySQL性能消耗较大；
  • 基于MAC地址生成的UUID可能造成MAC地址泄露

2.数据库自增ID

基于数据库的auto_increment自增ID完全可以充当分布式ID，需要一个单独的MySQL实例用来生成ID，建表结构如下：

CREATE DATABASE `SEQ_ID`;
CREATE TABLE SEQID.SEQUENCE_ID (
    id bigint(20) unsigned NOT NULL auto_increment, 
    value char(10) NOT NULL default '',
    PRIMARY KEY (id),
) ENGINE=MyISAM;
insert into SEQUENCE_ID(value)  VALUES ('values');

当我们需要一个ID的时候，向表中插入一条记录返回主键ID

优点：

  • 简单，利用数据库系统功能实现，成本小，有DBA专业维护
  • ID号单调递增

缺点：

  • 太依赖DB，当DB异常时整个系统不可用，属于致命问题。
  • 配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
  • ID发号性能瓶颈限制在单台MySQL的读写性能
  • 访问量激增时MySQL本身就是系统的瓶颈，用它来实现分布式服务风险比较大

3.数据库多主模式

对上边的方式做一些高可用优化，换成主从模式集群。再增加多几个Mysql实例，那就是多主模式集群了。

设置起始值和自增步长来解决重复ID的问题，例如：
MySQL_1起始值为1，步长为2，生成ID：1，3，5…
MySQL_2起始值为2，步长为2，生成ID：2，4，6…
当添加多一个MySQL_3时，起始值为3，步长统一改为3，那么就是
1，4，7…
2，5，8…
3，6，9…

优点：解决DB单点问题
缺点：不利于后续扩容，而且实际上单个数据库自身压力还是大，依旧无法满足高并发场景

4.数据库号段模式

从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。表结构如下：

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的长度',
  biz_type    int(20) NOT NULL COMMENT '业务类型',
  version int(20) NOT NULL COMMENT '版本号',
  PRIMARY KEY (`id`)
)

不是很依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多。

5.Redis

当使用数据库来生成ID性能不够要求的时候，我们可以尝试使用Redis来生成ID。这主要依赖于Redis是单线程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY来实现。
比较适合使用Redis来生成日切流水号。比如订单号=日期+当日自增长号。可以每天在Redis中生成一个Key，使用INCR进行累加。

127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id      // 增加1，并返回递增后的数值
(integer) 2

用redis实现需要注意一点，要考虑到redis持久化的问题。redis有两种持久化方式RDB和AOF：

  • RDB会定时打一个快照进行持久化，假如连续自增但redis没及时持久化，而这会Redis挂掉了，重启Redis后会出现ID重复的情况。
  • AOF会对每条写命令进行持久化，即使Redis挂掉了也不会出现ID重复的情况，但由于incr命令的特殊性，会导致Redis重启恢复的数据时间过长。

优点：

  • 不依赖于数据库，灵活方便，且性能优于数据库
  • 数字ID天然排序，对分页或者需要排序的结果很有帮助

缺点：

  • 如果系统中没有Redis，还需要引入新的组件，增加系统复杂度
  • 需要编码和配置的工作量比较大
  • Redis单点故障，影响序列服务的可用性

6.雪花算法（SnowFlake）

是twitter公司内部分布式项目采用的ID生成算法，开源后广受国内大厂的好评，在该算法影响下各大公司相继开发出各具特色的分布式生成器。
十种分布式ID生成方法
组成结构：正数位（占1比特）+ 时间戳（占41比特）+ 机器ID（占5比特）+ 数据中心（占5比特）+ 自增值（占12比特），总共64比特组成的一个Long类型。

  • 第一个bit位（1bit）：Java中long的最高位是符号位代表正负，正数是0，负数是1，一般生成ID都为正数，所以默认为0。
  • 时间戳部分（41bit）：毫秒级的时间，不建议存当前时间戳，而是用（当前时间戳 -固定开始时间戳）的差值，可以使产生的ID从更小的值开始；
  • 工作机器id（10bit）：也被叫做workId，这个可以灵活配置，机房或者机器号组合都可以。
  • ***部分（12bit），自增值支持同一毫秒内同一个节点可以生成4096个ID

根据这个算法的逻辑，只需要将这个算法用Java语言实现出来，封装为一个工具方法，那么各个业务应用可以直接使用该工具方法来获取分布式ID，只需保证每个业务应用有自己的工作机器id即可，而不需要单独去搭建一个获取分布式ID的应用。

/**
 * Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数，然后转化为62进制变成一个短地址URL
 *
 * https://github.com/beyondfengyu/SnowFlake
 */
public class SnowFlakeShortUrl {

    //起始的时间戳
    private final static long START_TIMESTAMP = 1480166465631L;
    //每一部分占用的位数
    private final static long SEQUENCE_BIT = 12;   //***占用的位数
    private final static long MACHINE_BIT = 5;     //机器标识占用的位数
    private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数
    //每一部分的最大值
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
    //每一部分向左的位移
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
    
    private long dataCenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //***
    private long lastTimeStamp = -1L;  //上一次时间戳
    private long getNextMill() {
        long mill = getNewTimeStamp();
        while (mill <= lastTimeStamp) {
            mill = getNewTimeStamp();
        }
        return mill;
    }
    private long getNewTimeStamp() {
        return System.currentTimeMillis();
    }
    /**
     * 根据指定的数据中心ID和机器标志ID生成指定的***
     *
     * @param dataCenterId 数据中心ID
     * @param machineId    机器标志ID
     */
    public SnowFlakeShortUrl(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0！");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0！");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }
    //产生下一个ID
    public synchronized long nextId() {
        long currTimeStamp = getNewTimeStamp();
        if (currTimeStamp < lastTimeStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }
        if (currTimeStamp == lastTimeStamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;//相同毫秒内，***自增
            if (sequence == 0L) //同一毫秒的序列数已经达到最大
            {
                currTimeStamp = getNextMill();
            }
        } 
        else 
        {
            sequence = 0L;//不同毫秒内，***置为0
        }
        lastTimeStamp = currTimeStamp;
        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
                | dataCenterId << DATA_CENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //***部分
    }
    public static void main(String[] args) {
        SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);
        for (int i = 0; i < (1 << 4); i++) {
            //10进制
            System.out.println(snowFlake.nextId());
        }
    }
}

7.滴滴出品（TinyID）

先附上项目地址：https://github.com/didi/tinyid

Tinyid是用Java开发的一款分布式id生成系统，扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性。Tinyid在滴滴客服部门使用，均通过tinyid-client方式接入，每天生成亿级别的id。
特性：

  1. 全局唯一的long型id
  2. 趋势递增
  3. 非连续性
  4. 提供http和java client方式接入
  5. 支持批量获取id
  6. 支持生成1,3,5,7,9…序列的id
  7. 支持多个db的配置，无单点

tinyid的原理：

  • tinyid是基于数据库发号算法实现的
  • 可用号段在第一次获取id时加载，如当前号段使用达到一定量时，会异步加载下一可用号段，保证内存中始终有可用号段。
  • 当使用到一定百分比时，如20%(默认)，即200时，会异步加载下一可用号段到内存。

8.百度 （Uidgenerator）

先附上项目地址：https://github.com/baidu/uid-generator

uid-generator是基于Snowflake算法实现的，但uid-generator支持自定义时间戳、工作机器ID和 *** 等各部分的位数，而且采用用户自定义workId的生成策略。
uid-generator需要与数据库配合使用，需要新增一个WORKER_NODE表。当应用启动时会向数据库表中去插入一条数据，插入成功后返回的自增ID就是该机器的workId数据由host，port组成。
ID组成结构：
workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，而且同一应用每次重启就会消费一个workId。

9.美团（Leaf）

先附上项目地址https://github.com/zhuzhong/idleaf

Leaf同时支持号段模式和snowflake算法模式，可以切换使用。

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

10.zookeeper

zookeeper主要通过其znode数据版本来生成***，可以生成32位和64位的数据版本号，客户端可以使用这个版本号来作为唯一的***。
很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper，并且是多步调用API，如果在竞争较大的情况下，需要考虑使用分布式锁。因此，性能在高并发的分布式环境下，也不甚理想。

欢迎关注我的个人公众号

十种分布式ID生成方法

相关标签： redis java 数据库 算法 分布式

上一篇： 数据结构——队列（循环队列）的基本操作（实现链队列逐一取出c语言代码）

下一篇： 【数据结构】循环队列的认识和基本操作

推荐阅读