分布式唯一id，雪花算法

一.产生原因

为什么需要分布式全局唯一Id,以及分布式Id的业务需求

在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。

如在美团点评的金融、支付、餐饮、酒店;猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一Id来标识一条数据或消息;特别一点的如订单、骑手、优惠券也都需要有唯一Id坐标时。

此时一个能够生成全局唯一Id的系统是非常必要的。

二.生成规则要求

Id生成规则部分硬性要求

全局唯一；
趋势递增：在Mysql的InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用Btree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键来保证写入性能；
单调递增：尽量保证下一个Id一定大于上一个Id,例如事务版本号、IM增量消息、排序等特殊需求；
信息安全：如果Id是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量.所以在一些应用场景下,需要Id无规则不规则,让竞争对手不好猜；
含时间戳：这样就能够在开发中快速了解这个分布式Id的生成时间。

Id生成系统的可用性要求

高可用：发一个获取分布式Id的请求,服务器就要保证99.999%的情况下给我创建一个唯一分布式Id；
低延迟：发一个获取分布式Id的请求,服务器要快,极速；
高QPS：例如并发一口气10万个创建分布式Id请求同时杀过来,服务器要顶得住且一下子成功创建10万个分布式Id。

三.一般通用方案

1.UUID

UUID(Univesally Unique Identifler)的标准型包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符

性能非常高: 本地生成,没有网络消耗；
如果只是考虑唯一性:OK,关键是他无序,入数据库性能比较差。

为什么无序的UUID会导致入库性能变差呢?

无序,无法预测他的生成顺序,不能生成递增有序的数字。首先分布式Id一般都会作为主键,但是按照mysql官方推荐的主键尽量越短越好,UUID每一个都很长,所以不是很推荐；
主键,ID作为主键时在特定的环境会存在一些问题。比如做DB主键的场景下,UUID就非常不适用MySQL官方有明确的建议主键尽量越短越好36个字符长度的UUID不符合要求；
索引,B+树索引的分裂。
既然分布式Id是主键,然后主键是包含索引的,然后mysql的索引是通过B+树来实现的,每一次新的UUID数据的插入,为了查询的优化,都会对索引底层的B+树进行修改,因为UUID是无序的,所以每一次UUID数据的插入都会对主键地城的B+树进行很大的修改,这一点很不好.插入完全无序,不但会导致一些中间节点产生分裂,也会白白创造出很多不饱和的节点,这样大大降低了数据库插入的性能。

2.数据库自增主键(小公司)

在分布式里面,数据库的自增Id机制的主要原理是:数据库自增Id和mysql数据库的replace into实现的，这里的replace into跟insert功能类似；
不同点在于: replace into首先尝试插入数据列表中,如果发现表中已经有此行数据(根据主键或唯一索引判断)则先删除,再插入,否则直接插入新数据。

REPLACE INTO 的含义是插入一条记录,如果表中唯一索引的值遇到冲突,则替换老数据

那数据库自增ID机制适合做分布式ID吗?答案是不太合适

系统水平扩展比较困难,比如定义好了步长和机器台数之后,如果要添加机器该怎么做?假设现在只有一台机器发号是1.2.3.4.5(步长是1),这个时候需要扩容机器一台.可以这样做;把第二台机器的初始值设置的比第一台超过很多,貌似还好,现在想象一下如果我们线上有100台机器,这个时候要扩容该怎么做?简直是噩梦.所以系统水平扩展方案复杂难以实现；
数据库压力还是很大,每次获取ID都得读写一次数据库,非常影响性能,不符合分布式ID里面的延迟低和高QPS的规则(在高并发下,如果都去数据库里面获取ID,那是非常影响性能的)。

3.Redis生成全局Id策略（部署麻烦）

因为Redis是单线的天生保证原子性,可以使用原子操作INCR和INCRBY来实现。

注意: 在Redis集群情况下,同样和Mysql一样需要设置不同的增长步长,同时key一定要设置有效期。

可以使用Redis集群来获取更高的吞吐量。

综上分析：那么问题就来了，自增id会担心主键重复，UUID不能保证有序性，有没有一种ID既是有序的，又是唯一的呢？有的兄弟，有的，就是雪花ID。

四.雪花ID算法

1、什么是雪花算法

雪花算法（Snowflake）是一种生成全局唯一ID的算法，由Twitter公司开发。它可以在分布式系统中生成全局唯一的ID，解决分布式系统中的数据合并和分片等问题。

雪花算法生成的ID是一个64位的长整型数字，由以下部分组成：

1个bit：符号位，始终为0。

41个bit：时间戳，精确到毫秒级别，可以使用69年。

10个bit：工作机器ID，可以部署在1024个节点上。

12个bit：序列号，每个节点每毫秒内最多可以生成4096个ID。

雪花算法生成ID的过程非常简单，首先记录一个开始时间，然后每次生成ID时计算当前时间和开始时间之间的时间差，将时间戳和工作机器ID、序列号组合成一个64位的长整型数字，返回给调用方。

雪花算法是一种高效、可靠的全局唯一ID生成算法，已经被广泛应用于分布式系统中。

2、雪花算法的优缺点

优点：

全局唯一：雪花算法生成的ID是全局唯一的，可以用于分布式系统中的数据分片和数据合并，避免了ID冲突的问题。
时间有序：雪花算法生成的ID中包含了时间戳信息，可以根据ID的大小推算出生成的时间，方便进行数据排序和查询
高性能：雪花算法生成ID的速度很快，可以满足高并发的场景需求。
可扩展性：雪花算法的数据结构相对简单，易于扩展和修改。

缺点：

长度固定：雪花算法生成的ID长度固定为64位，可能会导致存储和传输成本较高。
不支持分布式计算：雪花算法生成ID的过程是单线程的，不能支持分布式计算。

雪花算法是一种高效、可靠的全局唯一ID生成算法，但需要注意时钟回拨和长度固定等缺点。在选择ID生成算法时，需要综合考虑应用场景和需求，选择适合的算法。

3、spring boot项目中使用雪花算法使用

1、使用Hutool 的雪花算法（推荐，稳定）

<!-- hutool-all -->
<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.8.34</version>
</dependency>

2.创建一个工具类SnowflakeConfig

配置Snowflake算法的参数：

import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.util.IdUtil;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class SnowflakeConfig {
    
    @Bean
    public Snowflake snowflake() {
        // 参数1为终端ID, 参数2为数据中心ID
        return IdUtil.getSnowflake(1, 1);
    }
}

3、注入雪花算法对象

@Autowired
private Snowflake snowflake;

// 使用示例
public void example() {
    long id = snowflake.nextId();
    // 使用生成的ID
}

使用snowflake.nextId()方法既可以获取生成的雪花ID。

五。拓展--市面上几种雪花算法的实现

hutool版

百度UidGenerator

美团Leaf

twitter-archive/snowflake（github仓库已经不对外开放）

yitter / 多语言新雪花算法（SnowFlake IdGenerator），没上面几个出名，是码云上较火的一个snowflake项目

更多关于具体的各类雪花算法实现参考

雪花算法（几种常见的雪花算法生成ID方案简单介绍：Hutool、百度Uid-Generator、美团Leaf、Yitter）-CSDN博客