[go 面试] 雪花算法与分布式ID生成

简介: [go 面试] 雪花算法与分布式ID生成

生成全局唯一ID的雪花算法原理


雪花算法是一种用于生成全局唯一ID的算法,最初由Twitter开发,用于解决分布式系统中生成ID的问题。其核心思想是将一个64位的长整型ID划分成多个部分,每个部分用于表示不同的信息,确保了生成的ID在分布式环境下的唯一性。


ID结构


  1. 符号位(1位):始终为0,用于保证ID为正数。
  2. 时间戳(41位):表示生成ID的时间戳,精确到毫秒级。
  3. 工作节点ID(10位):表示生成ID的机器的唯一标识。
  4. 序列号(12位):表示在同一毫秒内生成的多个ID的序列号。


生成步骤


  1. 获取当前时间戳,精确到毫秒级。
  2. 如果当前时间小于上次生成ID的时间,或者在同一毫秒内生成的ID数量超过最大值,等待下一毫秒再继续生成。
  3. 如果当前时间等于上次生成ID的时间,序列号自增1。
  4. 如果当前时间大于上次生成ID的时间,序列号重新从0开始。
  5. 将各个部分的值组合,得到最终的64位ID。


Go实现雪花算法的高并发ID生成器


package main
import (
 "fmt"
 "sync"
 "time"
)
const (
 workerBits     = 10
 sequenceBits   = 12
 workerMax      = -1 ^ (-1 << workerBits)
 sequenceMask   = -1 ^ (-1 << sequenceBits)
 timeShift      = workerBits + sequenceBits
 workerShift    = sequenceBits
 epoch          = 1609459200000
)
type Snowflake struct {
 mu          sync.Mutex
 lastTime    int64
 workerID    int64
 sequence    int64
}
func NewSnowflake(workerID int64) *Snowflake {
 if workerID < 0 || workerID > workerMax {
  panic(fmt.Sprintf("worker ID must be between 0 and %d", workerMax))
 }
 return &Snowflake{
  lastTime: time.Now().UnixNano() / 1e6,
  workerID: workerID,
  sequence: 0,
 }
}
func (sf *Snowflake) NextID() int64 {
 sf.mu.Lock()
 defer sf.mu.Unlock()
 currentTime := time.Now().UnixNano() / 1e6
 if currentTime < sf.lastTime {
  panic(fmt.Sprintf("clock moved backwards, refusing to generate ID for %d milliseconds", sf.lastTime-currentTime))
 }
 if currentTime == sf.lastTime {
  sf.sequence = (sf.sequence + 1) & sequenceMask
  if sf.sequence == 0 {
   for currentTime <= sf.lastTime {
    currentTime = time.Now().UnixNano() / 1e6
   }
  }
 } else {
  sf.sequence = 0
 }
 sf.lastTime = currentTime
 id := (currentTime-epoch)<<timeShift | (sf.workerID << workerShift) | sf.sequence
 return id
}
func main() {
 sf := NewSnowflake(1) // 假设工作节点ID为1
 for i := 0; i < 10; i++ {
  id := sf.NextID()
  fmt.Println(id)
  time.Sleep(time.Millisecond)
 }
}


高并发下的唯一性和递增性保障


在高并发场景下,保障雪花算法生成的ID唯一性和递增性的关键在于:


  1. 唯一性: 工作节点ID的设置保证了不同节点生成的ID不会冲突。序列号的自增和位运算保证了同一毫秒内生成的ID唯一。
  2. 递增性: 在同一毫秒内生成的多个ID按序列号的递增顺序排列。即使在极端情况下,同一毫秒内生成的ID数量超过了最大值,会等待下一毫秒重新开始,也保证了递增性。


总体来说,雪花算法在高并发下是一个可靠的ID生成方案。它的高性能和低碰撞概率使得它在分布式系统中被广泛应用。

相关文章
|
6月前
|
开发框架
osharp集成Yitter.IdGenerator并实现分布式ID
本文介绍了在 osharp 框架中集成 Yitter.IdGenerator 实现分布式 ID 的方法。osharp 是一个基于 .NET Core 的快速开发框架,而 Yitter.IdGenerator 是一种高效的分布式 ID 生成器。通过实现 `IKeyGenerator&lt;long&gt;` 接口并创建 `YitterSnowKeyGenerator` 类,结合 `YitterIdGeneratorPack` 模块化配置,实现了分布式环境下唯一 ID 的生成。
103 0
|
10月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
449 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
10月前
|
NoSQL 算法 关系型数据库
分布式 ID 详解 ( 5大分布式 ID 生成方案 )
本文详解分布式全局唯一ID及其5种实现方案,关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
分布式 ID 详解 ( 5大分布式 ID 生成方案 )
|
10月前
|
NoSQL Java 数据处理
基于Redis海量数据场景分布式ID架构实践
【11月更文挑战第30天】在现代分布式系统中,生成全局唯一的ID是一个常见且重要的需求。在微服务架构中,各个服务可能需要生成唯一标识符,如用户ID、订单ID等。传统的自增ID已经无法满足在集群环境下保持唯一性的要求,而分布式ID解决方案能够确保即使在多个实例间也能生成全局唯一的标识符。本文将深入探讨如何利用Redis实现分布式ID生成,并通过Java语言展示多个示例,同时分析每个实践方案的优缺点。
312 8
|
10月前
|
存储 算法 安全
SnowflakeIdGenerator-雪花算法id生成方法
SnowflakeIdGenerator-雪花算法id生成方法
323 1
|
10月前
|
算法
雪花算法反思:订单ID生成的痛点与解决方案
雪花算法(Snowflake Algorithm)因其生成唯一ID的能力而被广泛应用于分布式系统中。然而,随着业务的发展和系统规模的扩大,一些隐藏的问题逐渐浮现。本文将探讨使用雪花算法生成订单ID后可能遇到的挑战,并提供相应的解决方案。
427 2
|
12月前
|
算法 程序员 Go
PHP 程序员学会了 Go 语言就能唬住面试官吗?
【9月更文挑战第8天】学会Go语言可提升PHP程序员的面试印象,但不足以 solely “唬住” 面试官。学习新语言能展现学习能力、拓宽技术视野,并增加就业机会。然而,实际项目经验、深入理解语言特性和综合能力更为关键。全面展示这些方面才能真正提升面试成功率。
129 10
|
7月前
|
编译器 Go
揭秘 Go 语言中空结构体的强大用法
Go 语言中的空结构体 `struct{}` 不包含任何字段,不占用内存空间。它在实际编程中有多种典型用法:1) 结合 map 实现集合(set)类型;2) 与 channel 搭配用于信号通知;3) 申请超大容量的 Slice 和 Array 以节省内存;4) 作为接口实现时明确表示不关注值。此外,需要注意的是,空结构体作为字段时可能会因内存对齐原因占用额外空间。建议将空结构体放在外层结构体的第一个字段以优化内存使用。
|
7月前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
28天前
|
数据采集 Go API
Go语言实战案例:多协程并发下载网页内容
本文是《Go语言100个实战案例 · 网络与并发篇》第6篇,讲解如何使用 Goroutine 和 Channel 实现多协程并发抓取网页内容,提升网络请求效率。通过实战掌握高并发编程技巧,构建爬虫、内容聚合器等工具,涵盖 WaitGroup、超时控制、错误处理等核心知识点。