分佈式 id 生成策略

1、背景

在我們的日常業務中，常常需要一些唯一 id，用來標識一個數據。例如：消息 Id，文件 Id，人員 Id 等。不同的業務場景需要的 id 的特性也不盡相同。so, 一個優秀的業務系統在不同的場景下應該選擇合適的分佈式 id 生成策略。

2、分佈式 Id 的特性

（1）、全局唯一

不能出現重複的 ID 號，既然是唯一標識，這是最基本的要求

（2）、遞增

遞增又分爲兩種場景：單調遞增和趨勢遞增；遞增特性能夠維護數據的新舊特性。同時對於排序等需求支持比較友好。其次，大多數場景下，業務數據的存儲會對 id 建立唯一索引的，自增的數據對索引數據的添加性能更加高效（例如：大多數互聯網公司使用的數據庫是 MySQL，存儲引擎爲 innoDB，對於 BTree 索引來講，數據以自增順序來寫入的話，b+tree 的結構不會時常被打亂重塑，存取效率是最高的，在主鍵的選擇上面我們應該儘量使用有序的主鍵保證寫入性能）。

（3）、信息安全

由於數據是遞增的，所以，惡意用戶的可以根據當前 ID 推測出下一個，非常危險，所以，我們的分佈式 ID 儘量做到不易被破解。如果 ID 是連續的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定 URL 即可；如果是訂單號就更危險了，競對可以直接知道我們一天的單量。所以在一些應用場景下，會需要 ID 無規則、不規則。

顯然，特性 2 與特性 3 是互斥的，在特定的場景下需要權衡選擇特性

3、分佈式 id 生成方案對比

我把生成方案分成了三大類：1、單調遞增型 id, 2、趨勢遞增型 id,3、僅保持唯一的 id。

（1）、單調遞增型 id

對某些業務場景對 id 的要求保證下一個 ID 一定大於上一個 ID，例如事務版本號、IM 增量消息、排序等特殊需求，這一類業務場景就要求使用單調遞增了。單調遞增型 id 主要有兩種方案：

使用數據庫的 id 自增策略，如 MySQL 的 auto_increment。並且可以使用兩臺數據庫分別設置不同步長，生成不重複 ID 的策略來實現高可用

優點：數據庫生成的 ID 絕對有序，高可用實現方式簡單
缺點：需要獨立部署數據庫實例，成本高，有性能瓶頸

使用 Redis, Redis 的所有命令操作都是單線程的，本身提供像 incr 和 increby 這樣的自增原子命令，所以能保證生成的 ID 肯定是唯一有序的

優點：不依賴於數據庫，靈活方便，且性能優於數據庫；數字 ID 天然排序，對分頁或者需要排序的結果很有幫助。
如果系統中沒有 Redis，還需要引入新的組件，增加系統複雜度；需要編碼和配置的工作量比較大。

同時爲防止機器宕機造成的 id 回退，數據的持久化也需要考慮

（2）、單調趨勢遞增

這一類模式 id 的生成效率很高，能夠適應高併發下的 id 生成。同時 id 是趨勢遞增的，安全性比較有保證，所以像訂單 id, 優惠券等瞬時高併發的業務場景會採用這一類 id 生成算法。基於單調趨勢遞增的 id 生成策略主要有兩種方案：基於數據庫的號段模式，基於雪花算法（snowflake）模式.

號段模式可以理解爲從數據庫批量的獲取自增 ID，每次從數據庫取出一個號段範圍，例如 (1,1000] 代表 1000 個 ID，具體的業務服務將本號段，生成 1~1000 的自增 ID 並加載到內存。表結構如下：

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '當前最大id',
  step int(20) NOT NULL COMMENT '號段的布長',
  biz_type  int(20) NOT NULL COMMENT '業務類型',
  version int(20) NOT NULL COMMENT '版本號',
  PRIMARY KEY (`id`)
)

等這批號段 ID 用完，再次向數據庫申請新號段，對max_id字段做一次update操作，update max_id= max_id + step，update 成功則說明新號段獲取成功，新的號段範圍是(max_id ,max_id +step]

update id_generator 
  set max_id = #{max_id+step}, version = version + 1 
  where version = # {version} and biz_type = XXX

由於存在多實例併發的場景，所以使用 version 的樂觀鎖維持冪等性。這種 id 生成策略對數據庫的訪問壓力比較小，同時使用多副本能良好的適應宕機的問題。

雪花算法（Snowflake）是 twitter 公司內部分佈式項目採用的 ID 生成算法，開源後廣受國內大廠的好評，在該算法影響下各大公司相繼開發出各具特色的分佈式生成器。本文也重點介紹一下這個算法

snowflake 生成的是 int64 的整型數據，分別由四部分組成

第一個 bit 位（1bit）：Java 中 long 的最高位是符號位代表正負，正數是 0，負數是 1，一般生成 ID 都爲正數，所以默認爲 0。
時間戳部分（41bit）：毫秒級的時間，不建議存當前時間戳，而是用（當前時間戳 - 固定開始時間戳）的差值，可以使產生的 ID 從更小的值開始；41 位的時間戳可以使用 69 年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69 年
工作機器 id（10bit）：也被叫做workId，這個可以靈活配置，機房或者機器號組合都可以。
序列號部分（12bit），自增值支持同一毫秒內同一個節點可以生成 4096 個 ID

通過提前規劃好 workId 可以實現該算法，但目前的分佈式生產環境，借用了多種雲計算、容器化技術，實例的個數隨時會變化，還需要處理服務器時鐘回退的問題，固定規劃 ID 然後通過配置來使用 snowflake 的場景可行性不高，一般是自動啓停，增減機器，這樣就需要對 snowflake 進行一些改造才能更好地應用到生產環境中。mongodb 中的 objectId 的生成算法和 Sony 公司的 sonyflake 是基於雪花算法改造的兩個比較經典的算法

sonyflake 是 Sony 公司的一個開源項目，基本思路和 snowflake 差不多，不過位分配上稍有不同，如下圖

這裏的時間只用了 39 個 bit，但時間的單位變成了 10ms，所以理論上比 41 位表示的時間還要久 (174 年)。

Sequence ID和之前的定義一致，Machine ID其實就是節點 id。sonyflake與衆不同的地方在於其在啓動階段的配置參數：

func NewSonyflake(st Settings) *Sonyflake

Settings數據結構如下：

type Settings struct {
    StartTime      time.Time
    MachineID      func() (uint16, error)
    CheckMachineID func(uint16) bool
}

StartTime選項是設置起始時間，如果不設置的話，默認是從2014-09-01 00:00:00 +0000 UTC開始。

MachineID可以由用戶自定義的函數，如果用戶不定義的話，會默認將本機 IP 的低 16 位作爲machine id。

CheckMachineID是由用戶提供的檢查MachineID是否衝突的函數

使用起來比較簡單：

func main() {
    t, _ := time.Parse("2006-01-02", "2018-01-01")
    settings := sonyflake.Settings{
        StartTime:      t,
        MachineID:      getMachineID,
        CheckMachineID: checkMachineID,
    }
    sf := sonyflake.NewSonyflake(settings)
    id, err := sf.NextID()
    if err != nil {
        fmt.Println(err)
        os.Exit(1)
    }
    fmt.Println(id)
}

mongodb 的 objectid 是生成的一個字節數組，使用時將字節數組進行 hex 編碼，所以最終的 id 是一個 string 型的，這一點與 snowflake 是不同的。objectId 也由四部分組成：1、4 bytes 的時間戳；2、3 bytes hostName 的 md5 值；3、2 bytes 的進程 id; 4、自增部分的數值

// NewObjectId returns a new unique ObjectId.
func NewObjectId() ObjectId {
  var b [12]byte
  // Timestamp, 4 bytes, big endian
  binary.BigEndian.PutUint32(b[:], uint32(time.Now().Unix()))
  // Machine, first 3 bytes of md5(hostname)
  b[4] = machineId[0]
  b[5] = machineId[1]
  b[6] = machineId[2]
  // Pid, 2 bytes, specs don't specify endianness, but we use big endian.
  b[7] = byte(processId >> 8)
  b[8] = byte(processId)
  // Increment, 3 bytes, big endian
  i := atomic.AddUint32(&objectIdCounter, 1)
  b[9] = byte(i >> 16)
  b[10] = byte(i >> 8)
  b[11] = byte(i)
  return ObjectId(b[:])
}

其中 machineId 默認是有機器的 hostName 進行 md5 運算出來的，如果機器沒有配置使用時間戳代替，代碼如下：

func readMachineId() []byte {
  var sum [3]byte
  id := sum[:]
  hostname, err1 := os.Hostname()
  if err1 != nil {
    n := uint32(time.Now().UnixNano())
    sum[0] = byte(n >> 0)
    sum[1] = byte(n >> 8)
    sum[2] = byte(n >> 16)
    return id
  }
  hw := md5.New()
  hw.Write([]byte(hostname))
  copy(id, hw.Sum(nil))
  return id
}

採用進程 id 可以很好的避免一個機器上多容器部署時 id 衝突的問題，加上操作系統對 pid 的銷燬和創建策略，容器重啓後分配的 pid 前後時不相同的，所以重啓後的 id 也是不會重複的

objectId 在自增數據上也採取了其實數據隨機的策略，提高了 id 的抗碰撞性，代碼如下：

var objectIdCounter uint32 = readRandomUint32()
// readRandomUint32 returns a random objectIdCounter.
func readRandomUint32() uint32 {
  // We've found systems hanging in this function due to lack of entropy.
  // The randomness of these bytes is just preventing nearby clashes, so
  // just look at the time.
  return uint32(time.Now().UnixNano())
}

（3）、僅保持唯一的 id。

UUID 是通用唯一識別碼（Universally Unique Identifier)的縮寫，開放軟件基金會 (OSF) 規範定義了包括網卡 MAC 地址、時間戳、名字空間（Namespace）、隨機或僞隨機數、時序等元素。利用這些元素來生成 UUID。

優點：本地生成，生成簡單，性能好，沒有高可用風險
缺點：長度過長，存儲冗餘，且無序不可讀，查詢效率低

uuid 適用場景：客戶端請求鏈路追蹤 reqId（每次請求服務端，使用 uuid 爲請求設置一個唯一標識），

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Snp6DY9B7y_u6F28CzA2og

猜你喜歡