baby sword‘s blog
xugaoyi
2023-06-09
目录

分布式id设计

# 1. 一个分布式id要满足哪些条件

  • 全局唯一
  • 方便易用
  • 高可用
  • 高性能
  • 安全

一个高质量的分布式id，最好也可以满足下面的条件

  • 安全：不包含敏感信息，如数量、mac地址等
  • 有序递增：满足数据库的索引性质
  • 有具体的业务含义：方便发生bug时进行定位操作
  • 可以独立部署

# 2. 分布式id常见解决方案

# 数据库模式

通关关系型数据库生成id，如mysql

具体方案：

①创建一个数据库：

CREATE TABLE `sequence_id` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `stub` char(10) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
1
2
3
4
5
6

stub 字段无意义，只是为了占位，便于我们插入或者修改数据。并且，给 stub 字段创建了唯一索引，保证其唯一性。

② 使用replace into语句

BEGIN;
REPLACE INTO sequence_id (stub) VALUES ('stub');
SELECT LAST_INSERT_ID();
COMMIT;
1
2
3
4

插入数据这里，我们没有使用 insert into 而是使用 replace into 来插入数据，具体步骤是这样的：

1)第一步： 尝试把数据插入到表中。

2)第二步： 如果主键或唯一索引字段出现重复数据错误而插入失败时，先从表中删除含有重复关键字值的冲突行，然后再次尝试把数据插入到表中。

  • 优缺：实现简单、ID保持自增、存储消耗的空间较小
  • 缺点：传统的mysql无法支持大并发量、存在数据库单点问题、id无法提现具体的业务逻辑、存在安全问题（数量）、每次都需要访问数据库磁盘效率低下。

# 数据库号段模式

数据库模式的每次获取都要从数据库中获取磁盘数据，在并发量比较大的情况下，获取id的速度慢且容易造成数据库宕机。那么什么方法可以解决呢？号段模式：批量获取id，存在内存里，当我们需要用到的时候，直接从内存中里取数据就可以了。

①创建一个数据库表

CREATE TABLE `sequence_id_generator` (
  `id` int(10) NOT NULL,
  `current_max_id` bigint(20) NOT NULL COMMENT '当前最大id',
  `step` int(10) NOT NULL COMMENT '号段的长度',
  `version` int(20) NOT NULL COMMENT '版本号',
  `biz_type`    int(20) NOT NULL COMMENT '业务类型',
   PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
1
2
3
4
5
6
7
8

current_max_id 字段和step字段主要用于获取批量 ID，获取的批量 id 为： current_max_id ~ current_max_id+step。

![image-20230410111433253](/Users/zhengjian/Library/Application Support/typora-user-images/image-20230410111433253.png)

version 字段主要用于解决并发问题（乐观锁）,biz_type 主要用于表示业

②插入数据

INSERT INTO `sequence_id_generator` (`id`, `current_max_id`, `step`, `version`, `biz_type`)
VALUES
	(1, 0, 100, 0, 101);
1
2
3

③获取指定业务下的一批唯一ID

SELECT `current_max_id`, `step`,`version` FROM `sequence_id_generator` where `biz_type` = 101
1

结果：

id	current_max_id	step	version	biz_type
1	0	100	0	101
1
2

④如果下次来取数据，更新之后重新查询即可

UPDATE sequence_id_generator SET current_max_id = 0+100, version=version+1 WHERE version = 0  AND `biz_type` = 101
SELECT `current_max_id`, `step`,`version` FROM `sequence_id_generator` where `biz_type` = 101
1
2

结果

id	current_max_id	step	version	biz_type
1	100	100	1	101
1
2
  • 优点 ：ID 有序递增、存储消耗空间小、减小了并发问题、优化了查询的效率
  • 缺点 ：存在数据库单点问题（可以使用数据库集群解决，不过增加了复杂度）、ID 没有具体业务含义、安全问题（比如根据订单 ID 的递增规律就能推算出每天的订单量，商业机密啊！ ）

# redis

一般情况下，NoSQL 方案使用 Redis 多一些。我们通过 Redis 的 incr 命令即可实现对 id 原子顺序递增。

127.0.0.1:6379> set sequence_id_biz_type 1
OK
127.0.0.1:6379> incr sequence_id_biz_type
(integer) 2
127.0.0.1:6379> get sequence_id_biz_type
"2"
1
2
3
4
5
6

为了提高可用性和并发，我们可以使用 Redis Cluster。Redis Cluster 是 Redis 官方提供的 Redis 集群解决方案（3.0+版本）

Redis 方案的优缺点：

  • 优点 ： 性能不错并且生成的 ID 是有序递增的
  • 缺点 ： 和数据库主键自增方案的缺点类似

# mongodb ObjectId

objectId结构 12字节

  • 0~3：时间戳

  • 3~6： 代表机器 ID

  • 7~8：机器进程 ID

  • 9~11 ：自增值

  • 优点 ： 性能不错并且生成的 ID 是有序递增的

  • 缺点 ： 需要解决重复 ID 问题（当机器时间不对的情况下，可能导致会产生重复 ID） 、有安全性问题（ID 生成有规律性）

这里关注一下时间不对造成重复id问题。

问题存在的原因是因为存在时间回拨问题：

# 什么是时间回拨

时间回拨（Time Drift）是指时钟的误差导致时间变慢或者变快，从而影响计时准确性的现象。在分布式系统中，不同机器上的时钟可能存在微小的差异，如果系统依赖于时钟来进行排序、计算超时等操作，就可能出现问题。

例如，在使用雪花算法生成ID时，如果某个机器发生了时间回拨，那么当前时间戳就会比之前生成ID的时间戳还要小，这就会导致生成的ID重复。为了避免这种情况，通常需要进行一定的时间同步，确保各个机器上的时钟尽量保持同步，并且需要对时间回拨进行处理，避免产生重复ID或者其他的错误。

解决时间回拨的方法有很多种，常见的方式包括：

  1. 使用网络时间协议（NTP）等工具对时钟进行同步；
  2. 在生成ID时检测时间戳是否小于之前生成的ID的时间戳，如果是则等待直到时间追上去后再生成ID；
  3. 对整个系统进行时钟漂移的监控和调整，及时进行修正。

就从objectId来看，对于同一个机器来说，在时间戳110时间段生成了一个id：110 0000 00 001

然后在111阶段生成了一个id：111 0000 00 001。这两个id不会出现重复问题，但是如果本在111时间戳阶段发生了时间回拨问题，那么机器生成的id可能是110 0000 00 001，此时生成的id就算是重复了。

发生时间回拨的可能原因是什么？

时间回拨的原因可能有很多，主要包括以下几种情况：

  1. 硬件故障：例如电源故障、主板故障、硬盘损坏等问题都可能导致时钟发生回拨；
  2. 软件错误：例如操作系统异常、BIOS 设置错误、应用程序故障等也可能会导致时钟发生回拨；
  3. 时间同步问题：如果某些机器没有使用时间同步服务或者同步误差较大，也可能导致时钟不同步，出现回拨现象；
  4. 其他因素：例如电压不稳定、温度过高等因素也可能影响时钟的精度和准确性。

需要注意的是，时间回拨虽然在分布式系统中比较常见，但是在单机环境中也可能会出现。因此，在进行计时和时间戳相关处理时，都需要格外注意时间回拨带来的影响。

# UUID

UUID包含32个16进制数字，且被分割为5个部分

467e8542-2275-4163-95d6-7adc205580a9

各部分的数字个数为：8-4-4-4-12

image-20230410113501693

UUID也有不同的版本，不同的版本生成UUID的规则也不一样

5 种不同的 Version(版本)值分别对应的含义（参考维基百科对于 UUID 的介绍open in new window (opens new window)）：

image-20230410113945616

JDK 中通过 UUID 的 randomUUID() 方法生成的 UUID 的版本默认为 4。

UUID uuid = UUID.randomUUID();
int version = uuid.version();// 4
1
2

从上面的介绍中可以看出，UUID 可以保证唯一性，因为其生成规则包括 MAC 地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素，计算机基于这些规则生成的 UUID 是肯定不会重复的。

虽然，UUID 可以做到全局唯一性，但是，我们一般很少会使用它。

比如使用 UUID 作为 MySQL 数据库主键的时候就非常不合适：

  • 数据库主键要尽量越短越好，而 UUID 的消耗的存储空间比较大（32 个字符串，128 位）。
  • UUID 是无顺序的，InnoDB 引擎下，数据库主键的无序性会严重影响数据库性能。

最后，我们再简单分析一下 UUID 的优缺点 （面试的时候可能会被问到的哦！） :

  • 优点 ：生成速度比较快、简单易用。无序网络，单机自行生成。速度快
  • 缺点 ： 存储消耗空间大（32 个字符串，128 位） 、 不安全（基于 MAC 地址生成 UUID 的算法会造成 MAC 地址泄露)、无序（非自增）、没有具体业务含义、需要解决重复 ID 问题（当机器时间不对的情况下，可能导致会产生重复 ID）

# 雪花算法

Snowflake 是 Twitter 开源的分布式 ID 生成算法。Snowflake 由 64 bit 的二进制数字组成，这 64bit 的二进制被分成了几部分，每一部分存储的数据都有特定的含义：

  • 第 0 位： 符号位（标识正负），始终为 0，没有用，不用管。
  • 第 1~41 位 ：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑 2 ^41 毫秒（约 69 年）
  • 第 42~52 位 ：一共 10 位，一般来说，前 5 位表示机房 ID，后 5 位表示机器 ID（实际项目中可以根据实际情况调整）。这样就可以区分不同集群/机房的节点。
  • 第 53~64 位 ：一共 12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数(2^12 = 4096),也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID。

Snowflake 示意图

如果你想要使用 Snowflake 算法的话，一般不需要你自己再造轮子。有很多基于 Snowflake 算法的开源实现比如美团 的 Leaf、百度的 UidGenerator，并且这些开源实现对原有的 Snowflake 算法进行了优化。

另外，在实际项目中，我们一般也会对 Snowflake 算法进行改造，最常见的就是在 Snowflake 算法生成的 ID 中加入业务类型信息。

我们再来看看 Snowflake 算法的优缺点 ：

  • 优点 ：生成速度比较快、生成的 ID 有序递增、比较灵活（可以对 Snowflake 算法进行简单的改造比如加入业务 ID）
  • 缺点 ： 需要解决重复 ID 问题（依赖时间，当机器时间不对的情况下，可能导致会产生重复 ID）。

可以看到，只要与时间相关的，基本上都需要注意时间回拨的问题

解决方案有：

  • 将ID生成交给少量服务器，并关闭时钟同步。
  • 直接报错，交给上层业务处理。
  • 如果回拨时间较短，在耗时要求内，比如5ms，那么等待回拨时长后再进行生成。
  • 如果回拨时间很长，那么无法等待，可以匀出少量位（1~2位）作为回拨位，一旦时钟回拨，将回拨位加1，可得到不一样的ID，2位回拨位允许标记三次时钟回拨，基本够使用。如果超出了，可以再选择抛出异常。

# 谈一谈mongodb的object_id

3.2 版本之前

Object_id的组成。一共12字节【和mysql主键类比的话，多了4字节】

  • 4字节timestamp，秒级别
  • 3字节 机器识别码
  • 2字节 进程id
  • 3字节 随机数开始的计数器

"在同一秒内，两个进程实例产生了相同的5字节随机数，且刚巧这两个进程的自增计数器的值也相同"--这种情况发生的概率实在太低了，完全可以认为不可能发生，所以使用互联无关的随机数来区分不同进程实例是完全合乎需求的。

3.2 后

  • A 4-byte timestamp, representing the ObjectId's creation, measured in seconds since the Unix epoch.
  • A 5-byte random value generated once per process. This random value is unique to the machine and process.
  • A 3-byte incrementing counter, initialized to a random value.
  • 4字节 Unix时间戳
  • 5字节 随机数
  • 3字节 随机数开始的计数器

为什么不继续使用“机器标识+进程号”？

  • 机器标识码，ObjectId 的机器标识码是取系统 hostname 哈希值的前几位，问题来了，想必在座的各位都有干过吧：准备了几台虚拟机，hostname 都是默认的 localhost，谁都想着这玩意儿能有什么用，还得刻意给不同机器起不同的 hostname？此外，hostname 在容器、云主机里一般默认就是随机数，也不会检查同一集群里是否有 hostname 重名
  • 进程号，这个问题就更大了，要知道，容器内的进程拥有自己独立的进程空间，在这个空间里只用它自己这一个进程（以及它的子进程），所以它的进程号永远都是 1。也就是说，如果某个服务（既可以是 mongo 实例也可以是 mongo 客户端）是使用容器部署的，无论部署多少个实例，在这个服务上生成的 ObjectId，第八第九个字节恒为 0000 0001，相当于说这两个字节废了

# 分布式id框架

UidGenerator(百度)、Leaf(美团)、Tinyid(滴滴)

https://www.cnblogs.com/itxiaoshen/p/15208459.html (opens new window)

编辑 (opens new window)
上次更新: 2024/02/22, 14:03:19
分布式理论
幂等性问题

← 幂等性问题→

最近更新
01
spark基础
02-22
02
mysql读写分离和分库分表
02-22
03
数据库迁移
02-22
更多文章>
Theme by Vdoing | Copyright © 2019-2024 Evan Xu | MIT License