1. 雪花算法

1.1.1. 关于雪花

雪花(snowflake)在自然界中，是极具独特美丽，又变幻莫测的东西：

  • 1.雪花属于六方晶系，它具有四个结晶轴，其中三个辅轴在一个基面上，互相以60度的角度相交，第四轴(主晶轴)与三个辅轴所形成的基面垂直；
  • 2.雪花的基本形状是六角形，但是大自然中却几乎找不出两朵完全相同的雪花，每一个雪花都拥有自己的独有图案，就象地球上找不出两个完全相同的人一样。许多学者用显微镜观测过成千上万朵雪花，这些研究最后表明，形状、大小完全一样和各部分完全对称的雪花，在自然界中是无法形成的。

1.1.2. 雪花算法

雪花算法的原始版本是scala版，用于生成分布式ID（纯数字，时间顺序）,订单编号等。

自增ID：对于数据敏感场景不宜使用，且不适合于分布式场景。 GUID：采用无意义字符串，数据量增大时造成访问过慢，且不宜排序。

雪花算法 - 图1

1.1.3. 算法描述

  • 最高位是符号位，始终为0，不可用。
  • 41位的时间序列，精确到毫秒级，41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。
  • 10位的机器标识，10位的长度最多支持部署1024个节点。
  • 12位的计数序列号，序列号即一系列的自增id，可以支持同一节点同一毫秒生成多个ID序号，12位的计数序列号支持每个节点每毫秒产生4096个ID序号。

代码：

  1. package main
  3. import (
  4.     "errors"
  5.     "fmt"
  6.     "sync"
  7.     "time"
  8. )
  10. const (
  11.     workerBits  uint8 = 10
  12.     numberBits  uint8 = 12
  13.     workerMax   int64 = -1 ^ (-1 << workerBits)
  14.     numberMax   int64 = -1 ^ (-1 << numberBits)
  15.     timeShift   uint8 = workerBits + numberBits
  16.     workerShift uint8 = numberBits
  17.     startTime   int64 = 1525705533000 // 如果在程序跑了一段时间修改了epoch这个值 可能会导致生成相同的ID
  18. )
  20. type Worker struct {
  21.     mu        sync.Mutex
  22.     timestamp int64
  23.     workerId  int64
  24.     number    int64
  25. }
  27. func NewWorker(workerId int64) (*Worker, error) {
  28.     if workerId < 0 || workerId > workerMax {
  29.         return nil, errors.New("Worker ID excess of quantity")
  30.     }
  31.     // 生成一个新节点
  32.     return &Worker{
  33.         timestamp: 0,
  34.         workerId:  workerId,
  35.         number:    0,
  36.     }, nil
  37. }
  39. func (w *Worker) GetId() int64 {
  40.     w.mu.Lock()
  41.     defer w.mu.Unlock()
  42.     now := time.Now().UnixNano() / 1e6
  43.     if w.timestamp == now {
  44.         w.number++
  45.         if w.number > numberMax {
  46.             for now <= w.timestamp {
  47.                 now = time.Now().UnixNano() / 1e6
  48.             }
  49.         }
  50.     } else {
  51.         w.number = 0
  52.         w.timestamp = now
  53.     }
  54.     ID := int64((now-startTime)<<timeShift | (w.workerId << workerShift) | (w.number))
  55.     return ID
  56. }
  57. func main() {
  58.     // 生成节点实例
  59.     node, err := NewWorker(1)
  60.     if err != nil {
  61.         panic(err)
  62.     }
  63.     for {
  64.         fmt.Println(node.GetId())
  65.     }
  66. }