分布式中唯一ID生成算法

前言

分布式系统中，难免会需要生成唯一ID作为标识符的需求。数据库主键，订单系统，日志系统，消息队列，会话管理，当并发量巨大且需要唯一标识信息的ID时，唯一ID生成算法就显得非常重要。

UUID

UUID（Universally Unique Identifier，通用唯一标识符）是一种标准化的唯一标识符生成算法，它能够在全球范围内保证生成的标识符是唯一的。UUID 根据不同的版本有不同的生成方式，其中比较常用的是 UUIDv1 和 UUIDv4。

UUIDv1

UUIDv1 基于主机的 MAC 地址和时间戳生成

结构：
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

//生成：
package main

import (
    "fmt"
    "github.com/google/uuid"
)

func main() {
    id := uuid.New()
    fmt.Printf("UUIDv1 : %s\n" , id)
}

输出：UUIDv1 : 39d00ade-312e-455a-92f3-bbfdda307a30

UUIDv4

UUIDv4 是基于随机数生成的 UUID

结构：
xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx

//生成
package main

import (
    "fmt"
    "github.com/google/uuid"
)

func main() {
    id , _ := uuid.NewRandom()
    fmt.Printf("UUIDv4: %s\n", id)
}

输出：UUIDv4: d6a291ab-ddc5-4b5a-9640-c6c3a32fe9e0

Snowflake

看似uuid已经可以满足唯一性了，但是面对不同的场景，他的功能往往不够全面，
例如，在日志记录和审计跟踪中，为确保事件顺序的正确性，支持时间段的日志检索抑或在消息队列中为顺序处理业务逻辑，避免数据竞争和冲突，uuid往往不能完全胜任，为满足id更细致的排序，进化出了snoeflake雪花算法

Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义

第一部分1 bit，是无意义的：
因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。
第二部分41 bit：表示的是时间戳，单位是毫秒，41 bit 可以表示的数字多达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。
第三部分是 10 个 bit：记录工作机器 id，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。但是 10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房里可以代表 2 ^ 5 个机器（32 台机器），这里可以随意拆分，比如拿出4位标识业务号，其他6位作为机器号。可以随意组合。
第四部分这个是用来记录同一个毫秒内产生的不同 id。
12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096，也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。也就是同一毫秒内同一台机器所生成的最大ID数量为4096

　　简单来说，你的某个服务假设要生成一个全局唯一 id，那么就可以发送一个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来生成唯一 id。这个 SnowFlake 算法系统首先肯定是知道自己所在的机器号，（这里姑且讲10bit全部作为工作机器ID）接着 SnowFlake 算法系统接收到这个请求之后，首先就会用二进制位运算的方式生成一个 64 bit 的 long 型 id，64 个 bit 中的第一个 bit 是无意义的。接着用当前时间戳（单位到毫秒）占用41 个 bit，然后接着 10 个 bit 设置机器 id。最后再判断一下，当前这台机房的这台机器上这一毫秒内，这是第几个请求，给这次生成 id 的请求累加一个序号，作为最后的 12 个 bit。

//源码：
func NewNode(node int64) (*Node, error) {
	// 加锁以防止在重新计算常量时的并发访问。
	mu.Lock()
	defer mu.Unlock() // 在函数返回时确保解锁互斥锁。

	// 已废弃：根据自定义的 NodeBits 或 StepBits 设置重新计算常量。
	nodeMax = -1 ^ (-1 << NodeBits)
	nodeMask = nodeMax << StepBits
	stepMask = -1 ^ (-1 << StepBits)
	timeShift = NodeBits + StepBits
	nodeShift = StepBits

	// 初始化一个新的 Node 实例。
	n := Node{}
	n.node = node
	n.nodeMax = nodeMax
	n.nodeMask = nodeMask
	n.stepMask = stepMask
	n.timeShift = timeShift
	n.nodeShift = nodeShift

	// 验证节点号是否在有效范围内。
	if n.node < 0 || n.node > n.nodeMax {
		return nil, errors.New("节点号必须在 0 到 " + strconv.FormatInt(n.nodeMax, 10) + " 之间")
	}

	// 基于当前系统时间设置起始时间。
	curTime := time.Now()
	n.epoch = curTime.Add(time.Unix(Epoch/1000, (Epoch%1000)*1000000).Sub(curTime))

	// 返回初始化后的 Node 实例。
	return &n, nil
}

// Generate 生成并返回一个唯一的雪花算法 ID
// 为了确保唯一性：
// - 确保您的系统保持准确的系统时间
// - 确保永远不要有多个节点使用相同的节点 ID 运行
func (n *Node) Generate() ID {
   // 加锁，保护并发访问
   n.mu.Lock()
   defer n.mu.Unlock()

   // 计算当前时间戳（毫秒）
   now := time.Since(n.epoch).Nanoseconds() / 1000000

   // 如果当前时间与上次生成的时间相同，则增加步长
   if now == n.time {
   	n.step = (n.step + 1) & n.stepMask

   	// 如果步长溢出，则等待直到时间变化
   	if n.step == 0 {
   		for now <= n.time {
   			now = time.Since(n.epoch).Nanoseconds() / 1000000
   		}
   	}
   } else {
   	// 如果当前时间不同，重置步长
   	n.step = 0
   }

   // 更新记录的时间
   n.time = now

   // 构造雪花 ID
   r := ID((now)<<n.timeShift |
   	(n.node << n.nodeShift) |
   	(n.step),
   )
   return r
}
// Int64 返回雪花 ID 的 int64 表示
func (f ID) Int64() int64 {
   return int64(f)
}

实例：

package main

import (
    "fmt"
    "github.com/bwmarrin/snowflake"
)
const(
    stateId = 1
)
func main() {
    sf , _:= snowflake.NewNode(stateId)
    id := sf.Generate().Int64()
    fmt.Println(id)
}

输出：1812727190702264320

Snowflake 算法之所以能够实现时间排序，主要是因为它在设计上解决了 UUIDv1 中存在的一些问题，特别是时钟回退和精度问题
以下来自chatGPT，说的挺中肯的

1.	独立时间戳和序列号：
   •	Snowflake 算法中，生成的唯一 ID 包含了一个以毫秒为单位的时间戳和一个序列号。这两部分都是独立的，时间戳部分记录了生成 ID 的精确时间，序列号部分确保在同一毫秒内生成的 ID 是递增的。
   2.	自定义起始时间：
   •	Snowflake 算法可以设置一个起始时间（epoch），通常是一个固定的时间点（例如 Unix 时间戳的起始时间）。这样可以确保算法在不同系统上始终使用相同的时间基准，避免时钟回退问题带来的影响。
   3.	高精度时间戳：
   •	Snowflake 算法使用的是毫秒级别的时间戳，相比 UUIDv1 的 100 纳秒精度更为适中，既能满足高并发生成 ID 的需求，又不会因为精度过高导致性能问题。
   4.	节点标识和数据中心标识：
   •	Snowflake 算法中，节点标识和数据中心标识是作为配置参数传入的，确保了不同节点生成的 ID 在全局范围内是唯一的。这样即使在分布式环境下，也能保证生成的 ID 是唯一且时间顺序的。
   5.	简单的逻辑和高效性：
   •	Snowflake 算法的设计相对简单且高效，使其能够在高并发环境下快速生成 ID，而不会成为系统性能的瓶颈。

时间对比

Generated 10000 UUIDs in 7.605208ms

Generated 10000 Snowflake IDs in 1.7125ms

百度 UidGenerator

雪花算法提供了一个很好的设计思想，雪花算法生成的ID是趋势递增，不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的，而且可以根据自身业务特性分配bit位，非常灵活。

但是雪花算法强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID，而时间回退后，生成的ID就有可能重复。官方对于此并没有给出解决方案，而是简单的抛错处理，这样会造成在时间被追回之前的这段时间服务不可用。

由此便演化出了一些改进算法
以百度开源的基于Snowflake优化的的ID生成器为例子，UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略，适用于docker等虚拟化环境下实例自动重启、漂移等场景。
细节可参考click here

目前有个很大的问题是该算法只有java版本，如果有机会完全可以自己手写一个（现在还太菜）。。

标签：生成,Snowflake,算法,bit,id,ID,分布式
From： https://www.cnblogs.com/atongmuhao/p/18303755