- 在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识
- 如在美团点评的金融、支付、餐饮、酒店;
- 猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一ID来标识一条数据或消息;
- 特别一点的如订单、骑手、优惠券也都需要有唯-1D做标识。
- 此时一个能够生成全局唯-ID的系统是非常必要的。
- 不能出现重复的ID号，既然是唯一ID，这是最基本的要求。
- 在Mysql 的InnoDB引擎中使用的是聚集索引，即B树的数据结构来存储索引数据，在主键的选择上，我们应该尽量使用有序的主键保证写入性能。
- 尽量保证下一个ID大于上一个ID,例如事务版本号，IM增量消息，排序等特殊要求。
- 如果ID是连续的，恶意用户的爬取工作就非常容易了，直接按照顺序下载指定的URL即可。
- 如果是订单号，那就更危险了。竞对可以根据单号知道我们一天的单量
- 所以在一些场景下，需要Id不规则，让竞争对手不好猜测
- 这样可以在开发中快速了解这个分布式Id的生成时间.
- 分一个获取分布式ID的请求,服务器要保证99.999%的情况下给我创建一个唯一的分布式ID
- 获取一个分布式Id的速度要够快，否则拖慢调用方系统。
- 在业务高峰期，服务器要能抗住非常大的并发，并且正确返回为一个ID
- UUID(Universally Unique Identifer) 的标准形式是 包含32位的16进制数字，以连子号分为5段，形式为 8-4-4-4-12的36个字符。
- 不重复，性能非常高。本地生成，没有网络消耗。
- 生成的ID是无序的，入库性能较差。
-
无序,无法预测他的生成顺序,不能生成递增有序的数字。
-
主键, ID作为主键时在特定的环境会存在一些问题。
比如做DB主键的场景下, UUID就非常不适用。MySQL官方有明确的建议主键要尽量越短越好。36个字符长度的UUID不符合要求
All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains theprimary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search forthe row in the clustered index.**if fth primary key is long, the secondary indexes use more space, so it is advantageous to have a shortprimary keyt
-
索引, B+树索引的分裂
主键的无序会导致数据库在构建主键对应的索引的时候，产生出很多不饱和的节点，浪费空间，降低插入性能。
- 在单机情况下，使用数据库自增主键来产生全局唯一Id是可行的。主要的方式是通过 数据库自增Id配合replace info 语句实现。
- replace into 和insert into 功能类似。不同点在于replace into 首先会尝试插入数据到表中，如果发现表中已经有此行数据（根据主键或唯一索引去判断）则先删除，后插入。否则直接插入新数据。
- 即有就替换，没有就插入。
-- 创建一个表，id 自增组件，stub 唯一约束
CREATE TABLE `id_generator` (
`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
`stub` char(1) DEFAULT NULL UNIQUE,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
-- 插入一条记录,因为stub是唯一约束，所以这里重复执行的话就会替换到之前的b，但是主键值会增长。
replace into id_generator(stub) values('b');
-- 获取最新生成的id
select LAST_INSERT_ID();
分布式系统集群
- 正式环境下，id生成肯定是需要集群部署的。
- 如果使用数据库自增主键作为Id,会有如下问题
- 系统水平扩展比较困难。比如定义好了步长和机器台数之后,如果要添加机器该怎么做?假设现在只有一台机器发号是1,2.3,4.5 (步长是1) ,这个时候需要扩容机器一台。可以这样做:把第二台机器的初始值设置得比第一台超过很多,貌似还好,现在想象一下如果我们线上有100台机器,这个时候要扩容该怎么做?简直是噩梦。所以系统水平扩展方案复杂难以实现。
- 数据库压力还是很大,每次获取ID都得读写一次数据库,非常影响性能,不符合分布式ID里面的延迟低和要高QPS的规则(在高并发下,如果都去数据库里面获取id,那是非常影响性能的)
- 一般小型应用的话，该种方案是可以使用的。
- 因为redis是单线程的，天生保证了原子性，可以使用incr和incrby来原子的生成唯一id。
- redis服务低延迟高QPS要求。
- redis在集群部署的情况下，同样存在和mysql一样，横向扩展困难的问题。一旦发生横向扩容，id生成规则就得重新安排，还得考虑历史数据问题，非常麻烦。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fPKRV0rz-1637636068276)(images/image-20200427205143066.png)]
建议- 中小型项目一般来说够用了。
-
最初Twitter把存储系统从MySQL迁移到Cassandra(由Facebook开发一套开源分布式NoSQL数据库系统)，因为Cassandra没有顺序ID生成机制,所以开发了这样一套全局唯一ID生成服务。
-
Twitter的分布式雪花算法SnowFlake ,经测试snowflake每秒能够产生26万个自增可排序的ID
-
twitter的SnowFlake生成ID能够按照时间有序生成
-
SnowFlake算法生成id的结果是一个64bit大小的整数,为一个Long型(转换成字符串后长度最多19)
-
分布式系统内不会产生ID碰撞(由datacenter和workerld作区分)，并且效率较高。
- 分布式系统中,有一些需要使用全局唯-ID的场景,生成ID的基本要求：
- 在分布式的环境下必须全局且唯一。
- 一般都需要单调递增,因为一般唯一ID都会存到数据库,而innodb的特性就是将内容存储在主键索引树上的叶子节点,而且是从左往右，递增的，所以考虑到数据库性能，一般生成的id也最好是单调递增。为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长,另外UUID一般是无序的。
- 可能还会需要无规则，因为如果使用唯一id作为订单号，竞争对手就能通过唯一id推测出日单数量。
- 永远不用,因为二进制中最高位是符号位, 1表示负数, 0表示正数。生成的id .般都是用整数,所以最高位固定为0
-
用来记录时间戳,毫秒级
-
41位可以表示2^41-1个数字,
-
如果只用来表示正整数(计算机中正数包含0) ,可以表示的数值范围是: 0至2^41-1。减1是因为可表示的数值范围是从0开始算的,而不是也就是说41位可以表示2^41-1个毫秒的值,转化成单位年则是(2^41-1)/(1000 60 * 60 *24 *365)=69年。即可以用到2039年。
-
用来记录工作机器id。10位的数字，可以用来标识任意机房的任意机器。比如5位分配给机房，5位分配给机器，则可标识的机房就是2^5=32 个机房，每个机房下可以标识的机器有 2^5=32 个。
-
可以部署在2^10=1024个节点,包括5位datacenterld和5位warkerld。
-
5位(bit)可以表示的最大正整数是2^5-1=31,即可以用0、1、2、3、… 31这32个数字,来表示不同的datecenterld或workerld。
- 用来记录同一毫秒内产生的不同id
- 12位(bit)可以表示的最大正整数是2^12-1=4095,即可以用0、1、2、3、…4094 这4095 个数字,来表示同一机器同一时间戳(毫秒)内产生的4095个ID序号。
- 简单来说，你的某个服务假设要生成一个全局唯一 id，那么就可以发送一个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来生成唯一 id。
- SnowFlake 算法系统首先肯定是知道自己所在的机房和机器的，比如机房 id = 17，机器 id = 12。
- 接着 SnowFlake 算法系统接收到这个请求之后，首先就会用二进制位运算的方式生成一个 64 bit 的 long 型 id，64 个 bit 中的第一个 bit 是无意义的。
- 接着 41 个 bit，就可以用当前时间戳（单位到毫秒），然后接着 5 个 bit 设置上这个机房 id，还有 5 个 bit 设置上机器 id。
- 最后再判断一下，当前这台机房的这台机器上这一毫秒内，这是第几个请求，给这次生成 id 的请求累加一个序号，作为最后的 12 个 bit。
最终一个 64 个 bit 的 id 就出来了，类似于：
- 整个分布式系统内不会产生重复id (因为有datacenterld和workerld来做区分)
- 单调递增
- 无规律
- 源码地址 https://github.com/twitter-archive/snowflake
- 雪花算法最开始是使用 scala写的。
- 网上有高人将该算法转译为java语言。
package com.fcbox.fms.util;
public class IdWorker {
//因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。
//机器ID 2进制5位 32位减掉1位 31个
private long workerId;
//机房ID 2进制5位 32位减掉1位 31个
private long datacenterId;
//代表一毫秒内生成的多个id的最新序号 12位 4096 -1 = 4095 个
private long sequence;
//设置一个时间初始值 2^41 - 1 差不多可以用69年
private long twepoch = 1585644268888L;
//5位的机器id
private long workerIdBits = 5L;
//5位的机房id
private long datacenterIdBits = 5L;
//每毫秒内产生的id数 2 的 12次方
private long sequenceBits = 12L;
// 这个是二进制运算，就是5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 这个是一个意思，就是5 bit最多只能有31个数字，机房id最多只能是32以内
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L << sequenceBits);
//记录产生时间毫秒数，判断是否是同1毫秒
private long lastTimestamp = -1L;
public long getWorkerId(){
return workerId;
}
public long getDatacenterId() {
return datacenterId;
}
public long getTimestamp() {
return System.currentTimeMillis();
}
public IdWorker(long workerId, long datacenterId, long sequence) {
// 检查机房id和机器id是否超过31 不能小于0
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));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}
// 这个是核心方法，通过调用nextId()方法，让当前这台机器上的snowflake算法程序生成一个全局唯一的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));
}
// 下面是说假设在同一个毫秒内，又发送了一个请求生成一个id
// 这个时候就得把seqence序号给递增1，最多就是4096
if (lastTimestamp == timestamp) {
// 这个意思是说一个毫秒内最多只能有4096个数字，无论你传递多少进来，
//这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
sequence = (sequence + 1) & sequenceMask;
//当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
// 这儿记录一下最近一次生成id的时间戳，单位是毫秒
lastTimestamp = timestamp;
// 这儿就是最核心的二进制位运算操作，生成一个64bit的id
// 先将当前时间戳左移，放到41 bit那儿；将机房id左移放到5 bit那儿；将机器id左移放到5 bit那儿；将序号放最后12 bit
// 最后拼接起来成一个64 bit的二进制数字，转换成10进制就是个long型
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) | sequence;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
//获取当前时间戳
private long timeGen(){
return System.currentTimeMillis();
}
public static void main(String[] args) {
System.out.println(1&4596);
System.out.println(2&4596);
System.out.println(6&4596);
System.out.println(6&4596);
System.out.println(6&4596);
System.out.println(6&4596);
// IdWorker worker = new IdWorker(1,1,1);
// for (int i = 0; i < 22; i++) {
// System.out.println(worker.nextId());
// }
}
}
工程落地经验
糊涂工具包
-
官网地址 https://hutool.cn/
-
github源码地址 https://github.com/looly/hutool/
-
gitee 源码地址 https://gitee.com/loolly/hutool/
-
Hutool是一个小而全的Java工具类库，通过静态方法封装，降低相关API的学习成本，提高工作效率，使Java拥有函数式语言般的优雅，让Java语言也可以“甜甜的”。
-
Hutool中的工具方法来自于每个用户的精雕细琢，它涵盖了Java开发底层代码中的方方面面，它既是大型项目开发中解决小问题的利器，也是小型项目中的效率担当；
-
Hutool是项目中“util”包友好的替代，它节省了开发人员对项目中公用类和公用工具方法的封装时间，使开发专注于业务，同时可以最大限度的避免封装不完善带来的bug。
- 在SpringBoot的pom文件中引入糊涂工具包依赖 hutool-all。
cn.hutool hutool-all 5.3.2 org.springframework.boot spring-boot-starter-web org.projectlombok lombok
- 在项目中使用糊涂工具包封装的雪花算法工具
package com.atguigu.springcloud.service;
import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.net.NetUtil;
import cn.hutool.core.util.IdUtil;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;
import javax.annotation.PostConstruct;
@Service
@Slf4j
public class IdGeneratorService {
private long workerId = 7;
private long dataCenter = 1;
private Snowflake snowflake = IdUtil.createSnowflake(workerId, dataCenter);
@PostConstruct
public void init(){
try {
workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
log.info("当前机器的workerId为：{}", workerId);
} catch (Exception e) {
log.info("当前机器workId获取失败", e);
workerId = NetUtil.getLocalhostStr().hashCode();
}
}
public synchronized long generateId(){
// 使用雪花算法获取一个ID
return snowflake.nextId();
}
public synchronized long generateId(long workerId, long dataCenter){
Snowflake snowflake = IdUtil.createSnowflake(workerId, dataCenter);
return snowflake.nextId();
}
}
- 对外提供一个接口用于获取全局唯一id
package com.atguigu.springcloud.controller;
import com.atguigu.springcloud.service.IdGeneratorService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.stream.Collectors;
@RestController
public class IdGeneratorController {
@Autowired
private IdGeneratorService idGeneratorService;
@GetMapping("/generateId")
public long generateId(){
return idGeneratorService.generateId();
}
@GetMapping("/generateId/batch")
public List generateId(@RequestParam("count") Integer count){
ExecutorService executorService = Executors.newFixedThreadPool(count);
List> futures = new ArrayList<>();
for (int i = 0; i < count; i++) {
CompletableFuture future =
CompletableFuture.supplyAsync(() -> idGeneratorService.generateId(), executorService);
futures.add(future);
}
executorService.shutdown();
return futures.stream().map(CompletableFuture::join).collect(Collectors.toList());
}
}
- 浏览器中访问 http://localhost:8888/generateId ，可以看到成功获取数据id
- 浏览器中访问 http://localhost:8888/generateId/batch?count=10 ，可以看到批量接口也是成功的。
-
毫秒数在高位, 自增序列在低位，整个ID都是趋势递增的。
-
不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。
-
可以根据自身业务特性分配bit位,非常灵活。
- 依赖机器时钟,如果机器时钟回拨,会导致重复ID生成
- 在单机上是递增的,但是由于设计到分布式环境,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况(此缺点可以认为无所谓, 一般分布式ID只要求趋势递增,并不会严格要求递增, 90%的需求都只要求趋势递增)
-
针对上面的雪花算法的时钟回拨问题，业界已经有了相关的解决方案。
-
百度开源的分布式唯一ID生成器 UidGenerator
-
Leaf - 美团点评分布式id生成系统。
