分布式惟一 ID 介绍
分布式系统全局惟一的 id 是所有零碎都会遇到的场景，往往会被用在搜寻，存储方面，用于作为惟一的标识或者排序，比方全局惟一的订单号，优惠券的券码等，如果呈现两个雷同的订单号，对于用户无疑将是一个微小的 bug。
在单体的零碎中，生成惟一的 id 没有什么挑战，因为只有一台机器一个利用，间接应用单例加上一个原子操作自增即可。而在分布式系统中，不同的利用，不同的机房，不同的机器，要想生成的 ID 都是惟一的，的确须要下点功夫。
一句话总结：
分布式惟一 ID 是为了给数据进行惟一标识。
分布式惟一 ID 的特色
分布式惟一 ID 的外围是唯一性，其余的都是附加属性，一般来说，一个优良的全局惟一 ID 计划有以下的特点，仅供参考：
- 全局惟一：不能够反复，外围特点！
- 大抵有序或者枯燥递增：自增的个性有利于搜寻，排序，或者范畴查问等
- 高性能：生成 ID 响应要快，提早低
- 高可用：要是只能单机，挂了，全公司依赖全局惟一 ID 的服务，全副都不可用了，所以生成 ID 的服务必须高可用
- 方便使用：对接入者敌对，能封装到开箱即用最好
- 信息安全：有些场景，如果间断，那么很容易被猜到，攻打也是有可能的，这得取舍。
分布式惟一 ID 的生成计划
UUID 间接生成
写过 Java 的敌人都晓得，有时候咱们写日志会用到一个类 UUID，会生成一个随机的 ID，去作为以后用户申请记录的惟一识别码, 只有用以下的代码：
String uuid = UUID.randomUUID();用法简略粗犷，UUID 的全称其实是Universally Unique IDentifier, 或者GUID(Globally Unique IDentifier), 它实质上是一个 128 位的二进制整数，通常咱们会示意成为 32 个 16 进制数组成的字符串，简直不会反复，2 的 128 次方，那是无比宏大的数字。
以下是百度百科阐明：
UUID 由以下几局部的组合：
（1）UUID 的第一个局部与工夫无关，如果你在生成一个 UUID 之后，过几秒又生成一个 UUID，则第一个局部不同，其余雷同。
（2）时钟序列。
（3）全局惟一的 IEEE 机器辨认号，如果有网卡，从网卡 MAC 地址取得，没有网卡以其余形式取得。
UUID 的惟一缺点在于生成的后果串会比拟长。对于 UUID 这个规范应用最广泛的是微软的 GUID(Globals Unique Identifiers)。在 ColdFusion 中能够用 CreateUUID()函数很简略地生成 UUID，其格局为：xxxxxxxx-xxxx- xxxx-xxxxxxxxxxxxxxxx(8-4-4-16)，其中每个 x 是 0-9 或 a-f 范畴内的一个十六进制的数字。而规范的 UUID 格局为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)，能够从 cflib 下载 CreateGUID() UDF 进行转换。[2]
（4）在 hibernate（Java orm 框架）中，采纳 IP-JVM 启动工夫 - 以后工夫右移 32 位 - 以后工夫 - 外部计数（8-8-4-8-4）来组成 UUID
要想反复，两台完全相同的虚拟机，开机工夫统一，随机种子统一，同一时间生成 uuid，才有极小的概率会反复，因而咱们可认为，实践上会反复，理论不可能反复！！！
uuid 长处：
- 性能好，效率高
- 不必网络申请，间接本地生成
- 不同的机器个干个的，不会反复
uuid 这么好，难不成是银弹？当然毛病也很突出：
- 没方法保障递增趋势，没法排序
- uuid 太长了，存储占用空间大，特地落在数据库，对建设索引不敌对
- 没有业务属性，这货色就是一串数字，没啥意义，或者说法则
当然也有人想要改良这家伙，比方不可读性革新，用uuid to int64，把它转成 long 类型：
byte[] bytes = Guid.NewGuid().ToByteArray();
return BitConverter.ToInt64(bytes, 0);又比方，革新无序性，比方 NHibernate 的 Comb 算法，把 uuid 的前 20 个字符保留下来，前面 12 个字符用 guid 生成的工夫, 工夫是大抵有序的，是一种小改良。
点评：UUID 不存在数据库当索引，作为一些日志，上下文的辨认，还是挺香的，然而要是这玩意用来当订单号，真是令人解体
数据库自增序列
单机的数据库
数据库的主键自身就领有一个自增的人造个性，只有设置 ID 为主键并且自增，咱们就能够向数据库中插入一条记录，能够返回自增的 ID，比方以下的建表语句：
CREATE DATABASE `test`;
use test;
CREATE TABLE id_table (id bigint(20) unsigned NOT NULL auto_increment,
value char(10) NOT NULL default '',
PRIMARY KEY (id),
) ENGINE=MyISAM;插入语句：
insert into id_table(value) VALUES ('v1');长处：
- 单机，简略，速度也很快
- 人造自增，原子性
- 数字 id 排序，搜寻，分页都比拟无利
毛病也很显著：
- 单机，挂了就要提桶跑路了
- 一台机器，高并发也不可能
集群的数据库
既然单机高并发和高可用搞不定，那就加机器，搞集群模式的数据库，既然集群模式，如果有多个 master，那必定不能每台机器本人生成本人的 id，这样会导致反复的 id。
这个时候，每台机器设置 起始值 和步长，就尤为重要。比方三台机器 V1，V2，V3：
对立步长：3
V1 起始值：1
V2 起始值：2
V3 起始值：3生成的 ID：
V1：1, 4, 7, 10...
V2：2, 5, 8, 11...
V3：3, 6, 9, 12...设置命令行能够应用：
set @@auto_increment_offset = 1; // 起始值
set @@auto_increment_increment = 3; // 步长这样的确在 master 足够多的状况下，高性能保障了，就算有的机器宕机了，slave 也能够补充上来，基于主从复制就能够，能够大大降低对单台机器的压力。然而这样做还是有毛病：
- 主从复制提早了，master 宕机了，从节点切换成为主节点之后，可能会反复发号。
- 起始值和步长设置好之后，要是前面须要减少机器（程度拓展），要调整很麻烦，很多时候可能须要停机更新
批量号段式数据库
下面的拜访数据库太频繁了，并发量一上来，很多小概率问题都可能产生，那为什么咱们不间接一次性拿出一段 id 呢？间接放在内存里，以供应用，用完了再申请一段就能够了。同样也能够保留集群模式的长处，每次从数据库取出一个范畴的 id，比方 3 台机器，发号：
每次取 1000，每台步长 3000
V1：1-1000,3001-4000,
V2：1001-2000,4001-5000
V3：2001-3000,5001-6000当然，如果不搞多台机器，也是能够的，一次申请 10000 个号码，用乐观锁实现，加一个版本号，
CREATE TABLE id_table (id int(10) NOT NULL,
max_id bigint(20) NOT NULL COMMENT '以后最大 id',
step int(20) NOT NULL COMMENT '号段的步长',
version int(20) NOT NULL COMMENT '版本号',
`create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,
`update_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,
PRIMARY KEY (`id`)
) 只有用完的时候，才会从新去数据库申请，竞争的时候乐观锁保障只能一个申请胜利，其余的间接等着他人取出来放在利用内存外面，再取就能够了，取的时候其实就是一个 update 操作：
update id_table set max_id = #{max_id+step}, version = version + 1 where version = # {version}重点：
- 批量获取，缩小数据库申请
- 乐观锁，保证数据精确
- 获取只能从数据库中获取，批量获取能够做成异步定时工作，发现少于某个阈值，主动补充
Redis 自增
redis 有一个原子命令incr, 原子自增，redis 速度快，基于内存：
127.0.0.1:6379> set id 1
OK
127.0.0.1:6379> incr id
(integer) 2当然，redis 如果单机有问题，也能够上集群，同样能够用初始值 + 步长，能够用 INCRBY 命令，搞几台机器根本能抗住高并发。
长处：
- 基于内存，速度快
- 人造排序，自增，有利于排序搜寻
毛病：
- 步长确定之后，减少机器也比拟难调整
-
须要关注长久化，可用性等，减少零碎复杂度
redis 长久化如果是 RDB，一段时间打一个快照，那么可能会有数据没来得及被长久化到磁盘，就挂掉了，重启可能会呈现反复的 ID，同时要是主从提早，主节点挂掉了，主从切换，也可能呈现反复的 ID。如果应用 AOF，一条命令长久化一次，可能会拖慢速度，一秒钟长久化一次，那么就可能最多失落一秒钟的数据，同时，数据恢复也会比较慢，这是一个取舍的过程。
Zookeeper 生成惟一 ID
zookeeper 其实是能够用来生成惟一 ID 的，然而大家不必，因为性能不高。znode 有数据版本，能够生成 32 或者 64 位的序列号，这个序列号是惟一的，然而如果竞争比拟大，还须要加分布式锁，不值得，效率低。
美团的 Leaf
上面均来自美团的官网文档：https://tech.meituan.com/2019…
Leaf 在设计之初就秉承着几点要求：
- 全局惟一，相对不会呈现反复的 ID，且 ID 整体趋势递增。
- 高可用，服务齐全基于分布式架构，即便 MySQL 宕机，也能容忍一段时间的数据库不可用。
- 高并发低延时，在 CentOS 4C8G 的虚拟机上，近程调用 QPS 可达 5W+，TP99 在 1ms 内。
- 接入简略，间接通过公司 RPC 服务或者 HTTP 调用即可接入。
文档外面讲得很清晰，一共有两个版本：
- V1：预散发的形式提供 ID，也就是后面说的号段式散发，表设计也差不多，意思就是批量的拉取 id
这样做的毛病就是更新号段的时候，耗时比拟高，还有就是如果这时候宕机或者主从复制，就不可用。
优化：
- 1. 先做了一个双 Buffer 优化，就是异步更新，意思就是搞两个号段进去，一个号段比方被耗费 10% 的时候，就开始调配下一个号段，有种提前调配的意思，而且异步线程更新
- 2. 下面的计划，号段可能固定，跨度可能太大或者太小，那就做成动态变化，依据流量来决定下一次的号段的大小，动静调整
- V2：Leaf-snowflake，Leaf 提供了 Java 版本的实现，同时对 Zookeeper 生成机器号做了弱依赖解决，即便 Zookeeper 有问题，也不会影响服务。Leaf 在第一次从 Zookeeper 拿取 workerID 后，会在本机文件系统上缓存一个 workerID 文件。即便 ZooKeeper 呈现问题，同时恰好机器也在重启，也能保障服务的失常运行。这样做到了对第三方组件的弱依赖，肯定水平上进步了 SLA。
snowflake(雪花算法）
snowflake 是 twitter 公司外部分布式我的项目采纳的 ID 生成算法, 开源后广受欢迎，它生成的 ID 是 Long 类型，8 个字节，一共 64 位，从左到右：
- 1 位：不应用，二进制中最高位是为 1 都是正数，然而要生成的惟一 ID 都是正整数，所以这个 1 位固定为 0。
- 41 位：记录时间戳(毫秒)，这个位数能够用 $(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$ 年
- 10 位：记录工作机器的 ID，能够机器 ID，也能够机房 ID + 机器 ID
- 12 位：序列号，就是某个机房某台机器上这一毫秒内同时生成的 id 序号
那么每台机器依照下面的逻辑去生成 ID，就会是趋势递增的，因为工夫在递增，而且不须要搞个分布式的，简略很多。
能够看出 snowflake 是强依赖于工夫的，因为工夫实践上是一直往前的，所以这一部分的位数，也是趋势递增的。然而有一个问题，是工夫回拨，也就是工夫忽然间倒退了，可能是故障，也可能是重启之后工夫获取出问题了。那咱们该如何解决工夫回拨问题呢？
- 第一种计划：获取工夫的时候判断，如果小于上一次的工夫戳，那么就不要调配，持续循环获取工夫，直到工夫符合条件。
- 第二种计划：下面的计划只适宜时钟回拨较小的，如果距离过大，阻塞期待，必定是不可取的，因而要么超过肯定大小的回拨间接报错，拒绝服务，或者有一种计划是利用拓展位，回拨之后在拓展位上加 1 就能够了，这样 ID 仍然能够放弃惟一。
Java 代码实现：
public class SnowFlake {// 数据中心(机房) id
private long datacenterId;
// 机器 ID
private long workerId;
// 同一时间的序列
private long sequence;
public SnowFlake(long workerId, long datacenterId) {this(workerId, datacenterId, 0);
}
public SnowFlake(long workerId, long datacenterId, long sequence) {
// 非法判断
if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);
this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}
// 开始工夫戳
private long twepoch = 1420041600000L;
// 机房号，的 ID 所占的位数 5 个 bit 最大:11111(2 进制)--> 31(10 进制)
private long datacenterIdBits = 5L;
// 机器 ID 所占的位数 5 个 bit 最大:11111(2 进制)--> 31(10 进制)
private long workerIdBits = 5L;
// 5 bit 最多只能有 31 个数字，就是说机器 id 最多只能是 32 以内
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 5 bit 最多只能有 31 个数字，机房 id 最多只能是 32 以内
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
// 同一时间的序列所占的位数 12 个 bit 111111111111 = 4095 最多就是同一毫秒生成 4096 个
private long sequenceBits = 12L;
// workerId 的偏移量
private long workerIdShift = sequenceBits;
// datacenterId 的偏移量
private long datacenterIdShift = sequenceBits + workerIdBits;
// timestampLeft 的偏移量
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
// 序列号掩码 4095 (0b111111111111=0xfff=4095)
// 用于序号的与运算，保障序号最大值在 0 -4095 之间
private long sequenceMask = -1L ^ (-1L << sequenceBits);
// 最近一次工夫戳
private long lastTimestamp = -1L;
// 获取机器 ID
public long getWorkerId() {return workerId;}
// 获取机房 ID
public long getDatacenterId() {return datacenterId;}
// 获取最新一次获取的工夫戳
public long getLastTimestamp() {return lastTimestamp;}
// 获取下一个随机的 ID
public synchronized long nextId() {
// 获取以后工夫戳，单位毫秒
long timestamp = timeGen();
if (timestamp < lastTimestamp) {System.err.printf("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
// 去重
if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;
// sequence 序列大于 4095
if (sequence == 0) {
// 调用到下一个工夫戳的办法
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 如果是以后工夫的第一次获取，那么就置为 0
sequence = 0;
}
// 记录上一次的工夫戳
lastTimestamp = timestamp;
// 偏移计算
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
// 获取最新工夫戳
long timestamp = timeGen();
// 如果发现最新的工夫戳小于或者等于序列号曾经超 4095 的那个工夫戳
while (timestamp <= lastTimestamp) {
// 不合乎则持续
timestamp = timeGen();}
return timestamp;
}
private long timeGen() {return System.currentTimeMillis();
}
public static void main(String[] args) {SnowFlake worker = new SnowFlake(1, 1);
long timer = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {worker.nextId();
}
System.out.println(System.currentTimeMillis());
System.out.println(System.currentTimeMillis() - timer);
}
}
百度 uid-generator
换汤不换药，百度开发的，基于 Snowflake 算法，不同的中央是能够本人定义每局部的位数, 也做了不少优化和拓展：https://github.com/baidu/uid-…
UidGenerator 是 Java 实现的, 基于 Snowflake 算法的惟一 ID 生成器。UidGenerator 以组件模式工作在利用我的项目中, 反对自定义 workerId 位数和初始化策略, 从而实用于 docker 等虚拟化环境下实例主动重启、漂移等场景。在实现上, UidGenerator 通过借用将来工夫来解决 sequence 人造存在的并发限度; 采纳 RingBuffer 来缓存已生成的 UID, 并行化 UID 的生产和生产, 同时对 CacheLine 补齐，防止了由 RingBuffer 带来的硬件级「伪共享」问题. 最终单机 QPS 可达 600 万。
秦怀の观点
不论哪一种 uid 生成器，保障唯一性是外围，在这个外围上能力去思考其余的性能，或者高可用等问题，总体的计划分为两种：
-
中心化：第三方的一个核心，比方 Mysql，Redis，Zookeeper
- 长处：趋势自增
- 毛病：减少复杂度，个别得集群，提前约定步长之类
-
无中心化：间接本地机器上生成，snowflake，uuid
- 长处：简略，高效，没有性能瓶颈
- 毛病：数据比拟长，自增属性较弱
没有哪一种是完满的，只有合乎业务以及以后体量的计划，技术计划外面，没有最优解。
【作者简介】：
秦怀，公众号【秦怀杂货店 】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis， 分布式 ， 剑指 Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。
剑指 Offer 全副题解 PDF
2020 年我写了什么？
开源编程笔记