雪花算法

标签：Go语言首次发布：2024-01-29最近修改：2024-06-14

常见的生成主键 id 的方式

生成主键方案：

  • UUID
  • 数据库自增主键
  • 基于 Redis 生成全局 ID 策略
  • 雪花算法，Twitter 的分布式自增 ID 算法 snowflake
  • 百度 UidGenerator 算法(基于雪花算法实现自定义时间戳)
  • 美团 Leaf 算法(依赖于数据库，ZK)

雪花算法的优缺点

优点

  1. 经测试 snowflake 每秒能生成 26 万个自增可排序的 ID。
  2. snowflake 生成的 ID 结果是一个 64bit 大小的整数，为一个 Long 型 （转换成字符串后长度最多 19）。
  3. 分布式系统内不会产生 ID 碰撞（datacenter 和 workerId 作区分）并且效率高。
  4. 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也非常高，可以根据自身业务分配 bit 位，非常灵活。

缺点

  1. 时间回拨问题：由于机器的时间是动态的调整的，有可能会出现时间跑到之前几毫秒，如果这个时候获取到了这种时间，则会出现数据重复。
  2. 机器 id 上限：机器 id 是固定的 bit，那么也就是对应的机器个数是有上限的，在有些业务场景下，需要所有机器共享同一个业务空间，那么 10bit 表示的 1024 台机器是不够的。

雪花算法的基本原理

  1. 第 1 位： 二进制中最高位为 1 的是负数，而在随机 ID 中，只能为正数，故该位只能为 0，无意义。

  2. 第 2 位~第 42 位： 共 41bit，是当前时间戳转换为二进制而来的。可以使用 69 年：year = (1L << 41) / (1000L _ 60 _ 60 _ 24 _ 365) = 69

  3. 第 43 位~第 52 位： 共 10bit，是当前机器（服务器）的 ID，其二进制数为 210 即 1024，所以使用雪花算法的服务最多可以同时部署在 1024 台服务器上。需要注意的是这里 10 位中的 5 位是给机房的，5 位是给机器（服务器）的，也就是一个雪花算法服务最多能部署在 25 个机房，每个机房最多有 2^5 个机器（服务器）。

  4. 第 53 位~第 64 位： 共 12bit，是毫秒内的序列号，即统一毫秒内生成的第几个 ID，其二进制数为 2^12 即 4096，所以同一雪花算法服务在同一毫秒内可生成 4096 个序列号 ID，如果超出了，就只能等待下一毫秒再生成。

将以上四个部分拼接起来做位或运算，就组成了一个 64 位的全局唯一 ID。

使用雪花算法生成 ID

下载雪花算法的开源库

go
go get github.com/sony/sonyflake

生成 ID

go
package main​import (    "fmt"    "github.com/sony/sonyflake"    "time")​func main() {    var setting sonyflake.Settings    //设置起始时间    startTime, err := time.Parse("2006-01-02 15:04:05", "2023-01-01 00:00:01")    if err != nil {        fmt.Println(err.Error())    }    setting.StartTime = startTime    id := sonyflake.NewSonyflake(setting)        userId, err := id.NextID()    if err != nil {        fmt.Println(err.Error())    }    fmt.Println(userId)}

运行结果如下：

powershell
PS D:\GolandProjects> go run main.go76846360686532097