Go 語(yǔ)言 分布式 id 生成器

原文鏈接：https://chai2010.cn/advanced-go-programming-book/ch6-cloud/ch6-01-dist-id.html

6.1 分布式 id 生成器

有時(shí)我們需要能夠生成類似 MySQL 自增 ID 這樣不斷增大，同時(shí)又不會(huì)重復(fù)的 id。以支持業(yè)務(wù)中的高并發(fā)場(chǎng)景。比較典型的，電商促銷(xiāo)時(shí)，短時(shí)間內(nèi)會(huì)有大量的訂單涌入到系統(tǒng)，比如每秒 10w+。明星出軌時(shí)，會(huì)有大量熱情的粉絲發(fā)微博以表心意，同樣會(huì)在短時(shí)間內(nèi)產(chǎn)生大量的消息。

在插入數(shù)據(jù)庫(kù)之前，我們需要給這些消息、訂單先打上一個(gè) ID，然后再插入到我們的數(shù)據(jù)庫(kù)。對(duì)這個(gè) id 的要求是希望其中能帶有一些時(shí)間信息，這樣即使我們后端的系統(tǒng)對(duì)消息進(jìn)行了分庫(kù)分表，也能夠以時(shí)間順序?qū)@些消息進(jìn)行排序。

Twitter 的 snowflake 算法是這種場(chǎng)景下的一個(gè)典型解法。先來(lái)看看 snowflake 是怎么一回事，見(jiàn) 圖 6-1：

圖 6-1 snowflake 中的比特位分布

首先確定我們的數(shù)值是 64 位，int64 類型，被劃分為四部分，不含開(kāi)頭的第一個(gè) bit，因?yàn)檫@個(gè) bit 是符號(hào)位。用 41 位來(lái)表示收到請(qǐng)求時(shí)的時(shí)間戳，單位為毫秒，然后五位來(lái)表示數(shù)據(jù)中心的 id，然后再五位來(lái)表示機(jī)器的實(shí)例 id，最后是 12 位的循環(huán)自增 id（到達(dá) 1111,1111,1111 后會(huì)歸 0）。

這樣的機(jī)制可以支持我們?cè)谕慌_(tái)機(jī)器上，同一毫秒內(nèi)產(chǎn)生 2 ^ 12 = 4096 條消息。一秒共 409.6 萬(wàn)條消息。從值域上來(lái)講完全夠用了。

數(shù)據(jù)中心加上實(shí)例 id 共有 10 位，可以支持我們每數(shù)據(jù)中心部署 32 臺(tái)機(jī)器，所有數(shù)據(jù)中心共 1024 臺(tái)實(shí)例。

表示 timestamp 的 41 位，可以支持我們使用 69 年。當(dāng)然，我們的時(shí)間毫秒計(jì)數(shù)不會(huì)真的從 1970 年開(kāi)始記，那樣我們的系統(tǒng)跑到 2039/9/7 23:47:35 就不能用了，所以這里的 timestamp 只是相對(duì)于某個(gè)時(shí)間的增量，比如我們的系統(tǒng)上線是 2018-08-01，那么我們可以把這個(gè) timestamp 當(dāng)作是從 2018-08-01 00:00:00.000 的偏移量。

6.1.1 worker_id 分配

timestamp，datacenter_id，worker_id 和 sequence_id 這四個(gè)字段中，timestamp 和 sequence_id 是由程序在運(yùn)行期生成的。但 datacenter_id 和 worker_id 需要我們?cè)诓渴痣A段就能夠獲取得到，并且一旦程序啟動(dòng)之后，就是不可更改的了（想想，如果可以隨意更改，可能被不慎修改，造成最終生成的 id 有沖突）。

一般不同數(shù)據(jù)中心的機(jī)器，會(huì)提供對(duì)應(yīng)的獲取數(shù)據(jù)中心 id 的 API，所以 datacenter_id 我們可以在部署階段輕松地獲取到。而 worker_id 是我們邏輯上給機(jī)器分配的一個(gè) id，這個(gè)要怎么辦呢？比較簡(jiǎn)單的想法是由能夠提供這種自增 id 功能的工具來(lái)支持，比如 MySQL:

mysql> insert into a (ip) values("10.1.2.101");
Query OK, 1 row affected (0.00 sec)

mysql> select last_insert_id();
+------------------+
| last_insert_id() |
+------------------+
|                2 |
+------------------+
1 row in set (0.00 sec)

從 MySQL 中獲取到 worker_id 之后，就把這個(gè) worker_id 直接持久化到本地，以避免每次上線時(shí)都需要獲取新的 worker_id。讓單實(shí)例的 worker_id 可以始終保持不變。

當(dāng)然，使用 MySQL 相當(dāng)于給我們簡(jiǎn)單的 id 生成服務(wù)增加了一個(gè)外部依賴。依賴越多，我們的服務(wù)的可運(yùn)維性就越差。

考慮到集群中即使有單個(gè) id 生成服務(wù)的實(shí)例掛了，也就是損失一段時(shí)間的一部分 id，所以我們也可以更簡(jiǎn)單暴力一些，把 worker_id 直接寫(xiě)在 worker 的配置中，上線時(shí)，由部署腳本完成 worker_id 字段替換。

6.1.2 開(kāi)源實(shí)例

6.1.2.1 標(biāo)準(zhǔn) snowflake 實(shí)現(xiàn)

github.com/bwmarrin/snowflake 是一個(gè)相當(dāng)輕量化的 snowflake 的 Go 實(shí)現(xiàn)。其文檔對(duì)各位使用的定義見(jiàn) 圖 6-2 所示。

圖 6-2 snowflake 庫(kù)

和標(biāo)準(zhǔn)的 snowflake 完全一致。使用上比較簡(jiǎn)單：

package main

import (
    "fmt"
    "os"

    "github.com/bwmarrin/snowflake"
)

func main() {
    n, err := snowflake.NewNode(1)
    if err != nil {
        println(err)
        os.Exit(1)
    }

    for i := 0; i < 3; i++ {
        id := n.Generate()
        fmt.Println("id", id)
        fmt.Println(
            "node:", id.Node(),
            "step:", id.Step(),
            "time:", id.Time(),
            "\n",
        )
    }
}

當(dāng)然，這個(gè)庫(kù)也給我們留好了定制的后路，其中預(yù)留了一些可定制字段：

    // Epoch is set to the twitter snowflake epoch of Nov 04 2010 01:42:54 UTC
    // You may customize this to set a different epoch for your application.
    Epoch int64 = 1288834974657

    // Number of bits to use for Node
    // Remember, you have a total 22 bits to share between Node/Step
    NodeBits uint8 = 10

    // Number of bits to use for Step
    // Remember, you have a total 22 bits to share between Node/Step
    StepBits uint8 = 12

Epoch 就是本節(jié)開(kāi)頭講的起始時(shí)間，NodeBits 指的是機(jī)器編號(hào)的位長(zhǎng)，StepBits 指的是自增序列的位長(zhǎng)。

6.1.2.2 sonyflake

sonyflake 是 Sony 公司的一個(gè)開(kāi)源項(xiàng)目，基本思路和 snowflake 差不多，不過(guò)位分配上稍有不同，見(jiàn) 圖 6-3：

圖 6-3 sonyflake

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

Sequence ID 和之前的定義一致，Machine ID 其實(shí)就是節(jié)點(diǎn) id。sonyflake 與眾不同的地方在于其在啟動(dòng)階段的配置參數(shù)：

func NewSonyflake(st Settings) *Sonyflake

Settings 數(shù)據(jù)結(jié)構(gòu)如下：

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

StartTime 選項(xiàng)和我們之前的 Epoch 差不多，如果不設(shè)置的話，默認(rèn)是從 2014-09-01 00:00:00 +0000 UTC 開(kāi)始。

MachineID 可以由用戶自定義的函數(shù)，如果用戶不定義的話，會(huì)默認(rèn)將本機(jī) IP 的低 16 位作為 machine id。

CheckMachineID 是由用戶提供的檢查 MachineID 是否沖突的函數(shù)。這里的設(shè)計(jì)還是比較巧妙的，如果有另外的中心化存儲(chǔ)并支持檢查重復(fù)的存儲(chǔ)，那我們就可以按照自己的想法隨意定制這個(gè)檢查 MachineID 是否沖突的邏輯。如果公司有現(xiàn)成的 Redis 集群，那么我們可以很輕松地用 Redis 的集合類型來(lái)檢查沖突。

redis 127.0.0.1:6379> SADD base64_encoding_of_last16bits MzI0Mgo=
(integer) 1
redis 127.0.0.1:6379> SADD base64_encoding_of_last16bits MzI0Mgo=
(integer) 0

使用起來(lái)也比較簡(jiǎn)單，有一些邏輯簡(jiǎn)單的函數(shù)就略去實(shí)現(xiàn)了：

package main

import (
    "fmt"
    "os"
    "time"

    "github.com/sony/sonyflake"
)

func getMachineID() (uint16, error) {
    var machineID uint16
    var err error
    machineID = readMachineIDFromLocalFile()
    if machineID == 0 {
        machineID, err = generateMachineID()
        if err != nil {
            return 0, err
        }
    }

    return machineID, nil
}

func checkMachineID(machineID uint16) bool {
    saddResult, err := saddMachineIDToRedisSet()
    if err != nil || saddResult == 0 {
        return true
    }

    err := saveMachineIDToLocalFile(machineID)
    if err != nil {
        return true
    }

    return false
}

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)
}