关于java:一口气说出9种分布式ID生成方式面试官有点懵

39次阅读

共计 12741 个字符,预计需要花费 32 分钟才能阅读完成。

送大家以下 java 学习材料,文末有支付形式




一、为什么要用分布式 ID?

在说分布式 ID 的具体实现之前,咱们来简略剖析一下为什么用分布式 ID?分布式 ID 应该满足哪些特色?

1、什么是分布式 ID?

拿 MySQL 数据库举个栗子:

在咱们业务数据量不大的时候,单库单表齐全能够撑持现有业务,数据再大一点搞个 MySQL 主从同步读写拆散也能凑合。

但随着数据日渐增长,主从同步也扛不住了,就须要对数据库进行分库分表,但分库分表后须要有一个惟一 ID 来标识一条数据,数据库的自增 ID 显然不能满足需要;特地一点的如订单、优惠券也都须要有 惟一 ID做标识。此时一个可能生成 全局惟一 ID的零碎是十分必要的。那么这个 全局惟一 ID就叫 分布式 ID

2、那么分布式 ID 须要满足那些条件?
  • 全局惟一:必须保障 ID 是全局性惟一的,根本要求
  • 高性能:高可用低延时,ID 生成响应要块,否则反倒会成为业务瓶颈
  • 高可用:100% 的可用性是骗人的,然而也要有限靠近于 100% 的可用性
  • 好接入:要秉着拿来即用的设计准则,在零碎设计和实现上要尽可能的简略
  • 趋势递增:最好趋势递增,这个要求就得看具体业务场景了,个别不严格要求

二、分布式 ID 都有哪些生成形式?

明天次要剖析一下以下 9 种,分布式 ID 生成器形式以及优缺点:

  • UUID
  • 数据库自增 ID
  • 数据库多主模式
  • 号段模式
  • Redis
  • 雪花算法(SnowFlake)
  • 滴滴出品(TinyID)
  • 百度(Uidgenerator)
  • 美团(Leaf)

那么它们都是如何实现?以及各自有什么优缺点?咱们往下看

图片源自网络

以上图片源自网络,如有侵权分割删除

1、基于 UUID

在 Java 的世界里,想要失去一个具备唯一性的 ID,首先被想到可能就是 UUID,毕竟它有着寰球惟一的个性。那么UUID 能够做 分布式 ID吗?答案是能够的,然而并不举荐!



public static void main(String\[\] args) {String uuid = UUID.randomUUID().toString().replaceAll("-","");  
       System.out.println(uuid);  
 }  


UUID的生成简略到只有一行代码,输入后果 c2b8c2b9e46c47e3b30dca3b0d447718,但 UUID 却并不适用于理论的业务需要。像用作订单号 UUID 这样的字符串没有丝毫的意义,看不出和订单相干的有用信息;而对于数据库来说用作业务 主键 ID,它不仅是太长还是字符串,存储性能差查问也很耗时,所以不举荐用作 分布式 ID

长处:

  • 生成足够简略,本地生成无网络耗费,具备唯一性

毛病:

  • 无序的字符串,不具备趋势自增个性
  • 没有具体的业务含意
  • 长度过长 16 字节 128 位,36 位长度的字符串,存储以及查问对 MySQL 的性能耗费较大,MySQL 官网明确倡议主键要尽量越短越好,作为数据库主键 UUID 的无序性会导致数据地位频繁变动,重大影响性能。
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,但这种形式有一个比拟致命的毛病,访问量激增时 MySQL 自身就是零碎的瓶颈,用它来实现分布式服务危险比拟大,不举荐!

长处:

  • 实现简略,ID 枯燥自增,数值类型查问速度快

毛病:

  • DB 单点存在宕机危险,无奈扛住高并发场景
3、基于数据库集群模式

前边说了单点数据库形式不可取,那对上边的形式做一些高可用优化,换成主从模式集群。胆怯一个主节点挂掉没法用,那就做双主模式集群,也就是两个 Mysql 实例都能独自的生产自增 ID。

那这样还会有个问题,两个 MySQL 实例的自增 ID 都从 1 开始,会生成反复的 ID 怎么办?

解决方案 :设置 起始值 自增步长

MySQL\_1 配置:



set @@auto\_increment\_offset = 1;     -- 起始值  
set @@auto\_increment\_increment = 2;  -- 步长  


MySQL\_2 配置:



set @@auto\_increment\_offset = 2;     -- 起始值  
set @@auto\_increment\_increment = 2;  -- 步长  


这样两个 MySQL 实例的自增 ID 别离就是:

1、3、5、7、9 
2、4、6、8、10

那如果集群后的性能还是扛不住高并发咋办?就要进行 MySQL 扩容减少节点,这是一个比拟麻烦的事。

在这里插入图片形容

从上图能够看出,程度扩大的数据库集群,有利于解决数据库单点压力的问题,同时为了 ID 生成个性,将自增步长依照机器数量来设置。

减少第三台 MySQL 实例须要人工批改一、二两台 MySQL 实例 的起始值和步长,把 第三台机器的 ID起始生成地位设定在比现有 最大自增 ID的地位远一些,但必须在一、二两台 MySQL 实例ID 还没有增长到 第三台 MySQL 实例 起始 ID值的时候,否则 自增 ID就要呈现反复了,必要时可能还须要停机批改

长处:

  • 解决 DB 单点问题

毛病:

  • 不利于后续扩容,而且实际上单个数据库本身压力还是大,仍旧无奈满足高并发场景。
4、基于数据库的号段模式

号段模式是当下分布式 ID 生成器的支流实现形式之一,号段模式能够了解为从数据库批量的获取自增 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\`)  
)   


biz\_type:代表不同业务类型

max\_id:以后最大的可用 id

step:代表号段的长度

version:是一个乐观锁,每次都更新 version,保障并发时数据的正确性

id

biz\_type

max\_id

step

version

1

101

1000

2000

0

等这批号段 ID 用完,再次向数据库申请新号段,对 max_id 字段做一次 update 操作,update max_id= max_id + step,update 胜利则阐明新号段获取胜利,新的号段范畴是(max_id ,max_id +step]



update id\_generator set max\_id = #{max\_id+step}, version = version + 1 where version = # {version} and biz\_type = XXX  


因为多业务端可能同时操作,所以采纳版本号 version 乐观锁形式更新,这种 分布式 ID生成形式不强依赖于数据库,不会频繁的拜访数据库,对数据库的压力小很多。

5、基于 Redis 模式

Redis也同样能够实现,原理就是利用 redis 的 incr命令实现 ID 的原子性自增。



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有两种长久化形式 RDBAOF

  • RDB会定时打一个快照进行长久化,如果间断自增但 redis 没及时长久化,而这会 Redis 挂掉了,重启 Redis 后会呈现 ID 反复的状况。
  • AOF会对每条写命令进行长久化,即便 Redis 挂掉了也不会呈现 ID 反复的状况,但因为 incr 命令的特殊性,会导致 Redis 重启复原的数据工夫过长。
6、基于雪花算法(Snowflake)模式

雪花算法(Snowflake)是 twitter 公司外部分布式我的项目采纳的 ID 生成算法,开源后广受国内大厂的好评,在该算法影响下各大公司相继开发出各具特色的分布式生成器。

在这里插入图片形容

以上图片源自网络,如有侵权分割删除

Snowflake生成的是 Long 类型的 ID,一个 Long 类型占 8 个字节,每个字节占 8 比特,也就是说一个 Long 类型占 64 个比特。

Snowflake ID 组成构造:正数位 (占 1 比特)+  工夫戳 (占 41 比特)+  机器 ID(占 5 比特)+ 数据中心 (占 5 比特)+  自增值(占 12 比特),总共 64 比特组成的一个 Long 类型。

  • 第一个 bit 位(1bit):Java 中 long 的最高位是符号位代表正负,负数是 0,正数是 1,个别生成 ID 都为负数,所以默认为 0。
  • 工夫戳局部(41bit):毫秒级的工夫,不倡议存以后工夫戳,而是用(以后工夫戳 – 固定开始工夫戳)的差值,能够使产生的 ID 从更小的值开始;41 位的工夫戳能够应用 69 年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69 年
  • 工作机器 id(10bit):也被叫做workId,这个能够灵便配置,机房或者机器号组合都能够。
  • 序列号局部(12bit),自增值反对同一毫秒内同一个节点能够生成 4096 个 ID

依据这个算法的逻辑,只须要将这个算法用 Java 语言实现进去,封装为一个工具办法,那么各个业务利用能够间接应用该工具办法来获取分布式 ID,只需保障每个业务利用有本人的工作机器 id 即可,而不须要独自去搭建一个获取分布式 ID 的利用。

Java 版本的 Snowflake 算法实现:

`/**`
 `* 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`
 `*`
 `* @return`
 `*/`
 `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 {`
 `// 不同毫秒内,序列号置为 0`
 `sequence = 0L;`
 `}`
 `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、百度(uid-generator)

uid-generator是由百度技术部开发,我的项目 GitHub 地址 https://github.com/baidu/uid-…

uid-generator是基于 Snowflake 算法实现的,与原始的 snowflake 算法不同在于,uid-generator反对自 定义工夫戳 工作机器 ID和 序列号  等各局部的位数,而且uid-generator 中采纳用户自定义 workId 的生成策略。

uid-generator须要与数据库配合应用,须要新增一个 WORKER_NODE 表。当利用启动时会向数据库表中去插入一条数据,插入胜利后返回的自增 ID 就是该机器的 workId 数据由 host,port 组成。

对于uid-generator ID 组成构造

workId,占用了 22 个 bit 位,工夫占用了 28 个 bit 位,序列化占用了 13 个 bit 位,须要留神的是,和原始的 snowflake 不太一样,工夫的单位是秒,而不是毫秒,workId也不一样,而且同一利用每次重启就会生产一个workId

参考文献
https://github.com/baidu/uid-…\_cn.md

8、美团(Leaf)

Leaf由美团开发,github 地址:https://github.com/Meituan-Di…

Leaf同时反对号段模式和 snowflake 算法模式,能够切换应用。

号段模式

先导入源码 https://github.com/Meituan-Di…,在建一张表leaf_alloc



DROP TABLE IF EXISTS \`leaf\_alloc\`;  
  
CREATE TABLE \`leaf\_alloc\` (\`biz\_tag\` varchar(128)  NOT NULL DEFAULT ''COMMENT' 业务 key',  
  \`max\_id\` bigint(20) NOT NULL DEFAULT '1' COMMENT '以后曾经调配了的最大 id',  
  \`step\` int(11) NOT NULL COMMENT '初始步长,也是动静调整的最小步长',  
  \`description\` varchar(256)  DEFAULT NULL COMMENT '业务 key 的形容',  
  \`update\_time\` timestamp NOT NULL DEFAULT CURRENT\_TIMESTAMP ON UPDATE CURRENT\_TIMESTAMP COMMENT '数据库保护的更新工夫',  
  PRIMARY KEY (\`biz\_tag\`)  
) ENGINE=InnoDB;  


而后在我的项目中开启 号段模式 ,配置对应的数据库信息,并敞开snowflake 模式



leaf.name=com.sankuai.leaf.opensource.test  
leaf.segment.enable=true  
leaf.jdbc.url=jdbc:mysql://localhost:3306/leaf\_test?useUnicode=true&characterEncoding=utf8&characterSetResults=utf8  
leaf.jdbc.username=root  
leaf.jdbc.password=root  
  
leaf.snowflake.enable=false  
#leaf.snowflake.zk.address=  
#leaf.snowflake.port=  


启动 leaf-server 模块的 LeafServerApplication 我的项目就跑起来了

号段模式获取分布式自增 ID 的测试 url:http://localhost:8080/api/segment/get/leaf-segment-test

监控号段模式:http://localhost:8080/cache

snowflake 模式

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



leaf.snowflake.enable=true  
leaf.snowflake.zk.address=127.0.0.1  
leaf.snowflake.port=2181  


snowflake 模式获取分布式自增 ID 的测试 url:http://localhost:8080/api/snowflake/get/test

9、滴滴(Tinyid)

Tinyid由滴滴开发,Github 地址:https://github.com/didi/tinyid。

Tinyid是基于号段模式原理实现的与 Leaf 一模一样,每个服务获取一个号段(1000,2000]、(2000,3000]、(3000,4000]

在这里插入图片形容

Tinyid提供 httptinyid-client两种形式接入

Http 形式接入

(1)导入 Tinyid 源码:

git clone https://github.com/didi/tinyi…

(2)创立数据表:



CREATE TABLE \`tiny\_id\_info\` (\`id\` bigint(20) unsigned NOT NULL AUTO\_INCREMENT COMMENT '自增主键',  
  \`biz\_type\` varchar(63) NOT NULL DEFAULT ''COMMENT' 业务类型,惟一 ',  
  \`begin\_id\` bigint(20) NOT NULL DEFAULT '0' COMMENT '开始 id,仅记录初始值,无其余含意。初始化时 begin\_id 和 max\_id 应雷同',  
  \`max\_id\` bigint(20) NOT NULL DEFAULT '0' COMMENT '以后最大 id',  
  \`step\` int(11) DEFAULT '0' COMMENT '步长',  
  \`delta\` int(11) NOT NULL DEFAULT '1' COMMENT '每次 id 增量',  
  \`remainder\` int(11) NOT NULL DEFAULT '0' COMMENT '余数',  
  \`create\_time\` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '创立工夫',  
  \`update\_time\` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新工夫',  
  \`version\` bigint(20) NOT NULL DEFAULT '0' COMMENT '版本号',  
  PRIMARY KEY (\`id\`),  
  UNIQUE KEY \`uniq\_biz\_type\` (\`biz\_type\`)  
) ENGINE=InnoDB AUTO\_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'id 信息表';  
  
CREATE TABLE \`tiny\_id\_token\` (\`id\` int(11) unsigned NOT NULL AUTO\_INCREMENT COMMENT '自增 id',  
  \`token\` varchar(255) NOT NULL DEFAULT ''COMMENT'token',  
  \`biz\_type\` varchar(63) NOT NULL DEFAULT ''COMMENT' 此 token 可拜访的业务类型标识 ',  
  \`remark\` varchar(255) NOT NULL DEFAULT ''COMMENT' 备注 ',  
  \`create\_time\` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '创立工夫',  
  \`update\_time\` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新工夫',  
  PRIMARY KEY (\`id\`)  
) ENGINE=InnoDB AUTO\_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'token 信息表';  
  
INSERT INTO \`tiny\_id\_info\` (\`id\`, \`biz\_type\`, \`begin\_id\`, \`max\_id\`, \`step\`, \`delta\`, \`remainder\`, \`create\_time\`, \`update\_time\`, \`version\`)  
VALUES  
    (1, 'test', 1, 1, 100000, 1, 0, '2018-07-21 23:52:58', '2018-07-22 23:19:27', 1);  
  
INSERT INTO \`tiny\_id\_info\` (\`id\`, \`biz\_type\`, \`begin\_id\`, \`max\_id\`, \`step\`, \`delta\`, \`remainder\`, \`create\_time\`, \`update\_time\`, \`version\`)  
VALUES  
    (2, 'test\_odd', 1, 1, 100000, 2, 1, '2018-07-21 23:52:58', '2018-07-23 00:39:24', 3);  
  
  
INSERT INTO \`tiny\_id\_token\` (\`id\`, \`token\`, \`biz\_type\`, \`remark\`, \`create\_time\`, \`update\_time\`)  
VALUES  
    (1, '0f673adf80504e2eaa552f5d791b644c', 'test', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');  
  
INSERT INTO \`tiny\_id\_token\` (\`id\`, \`token\`, \`biz\_type\`, \`remark\`, \`create\_time\`, \`update\_time\`)  
VALUES  
    (2, '0f673adf80504e2eaa552f5d791b644c', 'test\_odd', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');  


(3)配置数据库:



datasource.tinyid.names=primary  
datasource.tinyid.primary.driver-class\-name\=com.mysql.jdbc.Driver  
datasource.tinyid.primary.url=jdbc:mysql://ip:port/databaseName?autoReconnect=true&useUnicode=true&characterEncoding=UTF-8  
datasource.tinyid.primary.username=root  
datasource.tinyid.primary.password=123456  


(4)启动 tinyid-server 后测试



获取分布式自增 ID: http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c'  
返回后果: 3  
  
批量获取分布式自增 ID:  
http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c&batchSize=10'  
返回后果:  4,5,6,7,8,9,10,11,12,13  


Java 客户端形式接入

反复 Http 形式的(2)(3)操作

引入依赖



       <dependency>  
            <groupId\>com.xiaoju.uemc.tinyid</groupId\>  
            <artifactId>tinyid-client</artifactId>  
            <version>${tinyid.version}</version>  
        </dependency\>  


配置文件



tinyid.server =localhost:9999  
tinyid.token =0f673adf80504e2eaa552f5d791b644c  


testtinyid.token是在数据库表中事后插入的数据,test 是具体业务类型,tinyid.token示意可拜访的业务类型



// 获取单个分布式自增 ID  
Long id =  TinyId . nextId("test");  
  
// 按需批量分布式自增 ID  
List< Long > ids =  TinyId . nextId("test" , 10);  



总结

本文只是简略介绍一下每种分布式 ID 生成器,旨在给大家一个具体学习的方向,每种生成形式都有它本人的优缺点,具体如何应用还要看具体的业务需要。

正文完
 0