详解雪花算法 snowflake 生成分布式 ID

站长

2024年03月27日 16:00 · 阅读数 8

在大量的业务场景中，在将数据插入数据库前，需要一个自增的 ID，同时又不会重复。比如：春节期间的购票网站，短时间内会有大量的购票订单涌入系统；现在流行的各大社交网站，出现热点事件时，会有许多的报道评论等，产生大量的消息。这些订单、消息需要一个全局唯一 ID 进行标识，以更好地支持业务，尤其是在高并发场景下。

snowflack 算法就是在分布式系统下全局唯一 ID 的典型解决方案。

1. 分布式ID

分布式 ID 基本要求

全局唯一性：分布式ID既然是业务数据的唯一标识，那么ID自身的唯一性是最基本的要求；
趋势递增：由于分布式ID同时作为插入数据的主键ID插入数据，而许多数据库的索引是基于B+树，非趋势递增会导致页分裂，从而影响性能；
单调递增：保证上一个 ID 的大小一定小于下一个 ID，对于某些有排序需求的场景有一定的必要性，比如 IM 消息触达到端，或者就是单纯的有需要基于 ID 进行排序的需求。
信息安全：如果 ID 可以被简单的枚举出来，那么有潜在的数据安全问题。并且如果是订单号的场景，通过订单号的简单相减就预估出当天的订单量的话，会导致商业数据泄漏。

2. snowflake 算法介绍

Snowflake 雪花算法是 Twitter 开源的分布式 ID 生成算法。首先确定，分布式 ID 是64个bit位，并分割为4个部分。

第1位 占用1bit，符号位，永远为0；

第2位开始的41位 占用41bit，表示生成分布式 ID 请求时的时间戳毫秒值，大约可以使用69年；

中间10位 标识节点ID，其中5位标识数据中心的 ID，再用5位标识机器实例的 ID，最多可以表示 2^10=1024个节点；

最后12位 是循环自增，这意味着在1ms内一个节点最多可以生成 2^12=4096 个有效 ID

详解雪花算法 snowflake 生成分布式 ID

3. GO 实现 snowflake

因为第1个bit位是符号位，固定为0，不用考虑，从第2个bit位开始实现

3.1 时间戳为了延长分布式 ID 的使用时间，这里的时间戳选择一个相对于更晚的某个时间的毫秒值增量，例如以2024-01-24开始，把请求时间相对于该时间的偏移量作为 ID 的时间戳。我们定义一个 twepoch 变量，即 2024-01-24 00：00：00 的时间戳毫秒值，使用请求的时间戳毫秒值减去这个twepoch即得到 ID 的时间戳

const (
   timestampBits        = 41
   workerIdBits         = 10
   sequenceBits         = 12
   timestampShift       = workerIdBits + sequenceBits
   workIdShift          = sequenceBits
   sequenceMask         = 1<<sequenceBits - 1
   workIdMax      int64 = -1 ^ (-1 << workerIdBits)
)

var ( 
/* 
start time： 2024-01-24 
*/ 
twepoch = time.Date(2024, 1, 24, 0, 0, 0, 0, time.UTC).UnixMilli() 
)

/*
get the newest timestamp relative to twepoch
*/
func getNewestTimestamp(lastTimestamp int64) int64 {
   return lastTimestamp - twepoch
}

分布式 ID 一共64位，而时间戳位于从第2位开始的41个bit位，而右侧还有10位节点 ID 和12位递增序号，共22位，只要将得到的时间戳再向左位移22个bit位即得到时间戳在分布式 ID 的位置。同理，节点 ID 右侧有12位的序号，因此将节点 ID 向左位移12个bit位即得到节点 ID 的位置在最终的结果中，我们会看到返回的 ID 是通过如下的位运算得到的：

id = (ts << timestampShift) | (n.workId << workIdShift) | (n.sequence)

其中，timestampShift 时间戳的位移量（节点位数+序号位数），workIdShift 是节点 ID 的位移量（序号位数），ts 是相对于twepoch的时间戳毫秒值增量

3.2 节点 ID

为了简单，我们将 datacenter id 和 machine id 合并为节点 ID 即 work id，与 timestamp 和 sequence id 不同的是，节点 ID并不是在程序运行期间生成的，而是在部署节点就确定了。我们可以在初始化读取配置等方式确定节点 ID。定义了一个生成分布式 ID 的结构体，在初始化的时候，传入节点 ID，需要判断节点 ID 的范围是否在0到最大值之间

type Node struct {
   lastTimestamp int64
   workId        int64
   sequence      int64

   lock sync.Mutex
}

// Init returns a new snowflake node that can be used to generate snowflake
func Init(workId int64) (*Node, error) {
   n := Node{}
   n.workId = workId
   if n.workId < 0 || n.workId > workIdMax {
      return nil, errors.New("Node number must be between 0 and " + strconv.FormatInt(workIdMax, 10))
   }
   return &n, nil
}

3.3 自增的序号 ID 如果请求的时间戳小于最后时间戳，发生了时间回拨，此时抛出异常；如果请求的时间戳等于最后时间戳，那么序号 ID 只需要在上一个 ID的基础上+1即可，在该情况下，还需要考虑到上一个ID已经达到了最大值（12位全为1），那么接下来需要从0开始，并且时间戳要加上1ms。

func (n *Node) NextId() (id int64, err error) {
   n.lock.Lock()
   defer n.lock.Unlock()
   now := time.Now().UnixMilli()
   // 发生时钟回拨
   if now < n.lastTimestamp {
      return id, fmt.Errorf("clock callback occurs")
   }

   if now == n.lastTimestamp {
      n.sequence = (n.sequence + 1) & sequenceMask
      if n.sequence == 0 {
         // 并发量太高，序列号溢出
         now = wait(n.lastTimestamp)
      }
   } else {
      n.sequence = 0
   }
   n.lastTimestamp = now
   ts := getNewestTimestamp(n.lastTimestamp)
   id = (ts << timestampShift) | (n.workId << workIdShift) | (n.sequence)
   return id, nil
}
   
   
func wait(lastTimestamp int64) int64 {
   now := time.Now().UnixMilli()
   if now <= lastTimestamp {
      time.Sleep(time.Millisecond * time.Duration(lastTimestamp-now+1))
   }
   return now
}

sequenceMask 是序列号掩码，也就是序列号最大值，即12个1。

3.4 完整代码因为生成分布式 ID，会有并发场景，所以需要加锁

package snowflake

import (
   "errors"
   "fmt"
   "strconv"
   "sync"
   "time"
)

/*
@author: shg
@since: 2024/1/24 11:34 PM
@mail: shgang97@163.com
*/

/*
0-41位毫秒级时间戳-10位节点id-12位序列号
*/

const (
   timestampBits        = 41
   workerIdBits         = 10
   sequenceBits         = 12
   timestampShift       = workerIdBits + sequenceBits
   workIdShift          = sequenceBits
   sequenceMask         = 1<<sequenceBits - 1
   workIdMax      int64 = -1 ^ (-1 << workerIdBits)
)

var (
   /*
      start time： 2024-01-24
   */
   twepoch = time.Date(2024, 1, 24, 0, 0, 0, 0, time.UTC).UnixMilli()
)

type Node struct {
   lastTimestamp int64
   workId        int64
   sequence      int64

   lock sync.Mutex
}

// Init returns a new snowflake node that can be used to generate snowflake
func Init(workId int64) (*Node, error) {
   n := Node{}
   n.workId = workId
   if n.workId < 0 || n.workId > workIdMax {
      return nil, errors.New("Node number must be between 0 and " + strconv.FormatInt(workIdMax, 10))
   }
   return &n, nil
}

func (n *Node) NextId() (id int64, err error) {
   n.lock.Lock()
   defer n.lock.Unlock()
   now := time.Now().UnixMilli()
   // 发生时钟回拨
   if now < n.lastTimestamp {
      return id, fmt.Errorf("clock callback occurs")
   }

   if now == n.lastTimestamp {
      n.sequence = (n.sequence + 1) & sequenceMask
      if n.sequence == 0 {
         // 并发量太高，序列号溢出
         now = wait(n.lastTimestamp)
      }
   } else {
      n.sequence = 0
   }
   n.lastTimestamp = now
   ts := getNewestTimestamp(n.lastTimestamp)
   id = (ts << timestampShift) | (n.workId << workIdShift) | (n.sequence)
   return id, nil
}

func wait(lastTimestamp int64) int64 {
   now := time.Now().UnixMilli()
   if now <= lastTimestamp {
      time.Sleep(time.Millisecond * time.Duration(lastTimestamp-now+1))
   }
   return now
}

/*
get the newest timestamp relative to twepoch
*/
func getNewestTimestamp(lastTimestamp int64) int64 {
   return lastTimestamp - twepoch
}

3.5 测试一下

var wg sync.WaitGroup

func main() {
    // 初始化
    node, _ := snowflake.Init(1)
    fmt.Println("***************************** start *****************************")
    for i := 0; i < 10; i++ {
       wg.Add(1)
       li := i
       go func() {
          defer wg.Done()
          id, _ := node.NextId()
          fmt.Printf("第%d协程生成的id：%d,二进制为：%b\n", li, id, id)
       }()
    }
    wg.Wait()
    fmt.Println("***************************** end *****************************")

}

运行结果如下图，其中红色框为节点 ID 部分，左侧为相对时间戳，右侧为序列号 ID

详解雪花算法 snowflake 生成分布式 ID

测试下性能：

func main() {
    start := time.Now().UnixMilli()
    for i := 0; i < 50000; i++ {
       _, _ = node.NextId()
    }
    t := time.Now().UnixMilli() - start
    fmt.Printf("生成50000个分布式id耗时：%d ms", t)
}
// 生成50000个分布式id耗时：18 ms

4. snowflake 算法缺陷

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

 now := time.Now().UnixMilli()
   // 发生时钟回拨
   if now < n.lastTimestamp {
      return id, fmt.Errorf("clock callback occurs")
   }

总结

本文首先介绍实际业务场景，引入分布式ID，并简单介绍了分布式ID的基本要求，之后介绍了 snowflake 雪花算法并实现了 snowflake 算法，详细讲解了实现思路，并在最后介绍了 snowflake 算法缺陷。