雪花算法 Snowflake & Sonyflake

唯一ID算法

Snowflake

相信大家都不墨生，他是Twitter公司提出來的算法。非常廣泛的應用在各種業務系統裡。也因為

Snowflake

的靈活性和缺點，對他的改造層出不窮，比百度的 UidGenerator 、美團的 Leaf 、索尼的 Sonyflake 等等。這篇文章主要是講一下原生的

Snowflake

算法、缺點及改造方案，并分析索尼的 源碼對原生

Snowflake

的改造，

原生Snowflake

原生

Snowflake

算法使用一個

64 bit

的整形資料，根據目前的時間來生成ID。

Snowflake

結構如下：

• 因為最高位是辨別位，為1表示為負數，是以最高位不使用。
• 41bit 儲存時間戳，精确到毫秒。也就是說最大可使用的年限是69年。
• 10bit 的機器位，能部屬在1024台機器節點來生成ID。
• 12bit 的序列号，一毫秒最大生成唯一ID的數量為4096個。

原生的

Snowflake

算法是完全依賴于時間的，如果有時鐘回撥的情況發生，會生成重複的ID，市場上的解決方案也是非常多的：

• 最簡單的方案，就是關閉生成唯一ID機器的時間同步。
• 使用阿裡雲的的時間伺服器進行同步，2017年1月1日的閏秒調整，阿裡雲伺服器NTP系統24小時“消化”閏秒，完美解決了問題。
• 如果發現有時鐘回撥，時間很短比如

  5

  毫秒,就等待，然後再生成。或者就直接報錯，交給業務層去處理。
• 可以找2bit位作為時鐘回撥位，發現有時鐘回撥就将回撥位加1，達到最大位後再從0開始進行循環。

個人比較推薦的是最後一個方案

找2bit位作為時鐘回撥位，發現有時鐘回撥就将回撥位加1，達到最大位後再從0開始進行循環。

比如下圖這樣，從機器位上，均出來2位做回撥位：

Snowflake

算法是相當靈活的，我們可以根據自己的業務需要，對63 bit的的各個部分進行增減。索尼公司的

對原生的

Snowflake

進行改進，重新配置設定了各部分的bit位:

• 39bit 來儲存時間戳，與原生的

  Snowflake

  不同的地方是，

  Sonyflake

  是以10毫秒為機關來儲存時間的。這樣的話，可以使用的年限為

  174年

  比

  Snowflake

  長太多了。

const sonyflakeTimeUnit = 1e7 // nsec, i.e. 10 msec
func toSonyflakeTime(t time.Time) int64 {
    return t.UTC().UnixNano() / sonyflakeTimeUnit
}
func currentElapsedTime(startTime int64) int64 {
    return toSonyflakeTime(time.Now()) - startTime
}           

• 8bit 做為序列号，每10毫最大生成256個，1秒最多生成25600個，比原生的

  Snowflake

  少好多，如果感覺不夠用，目前的解決方案是跑多個執行個體為生成同一業務的ID來彌補。
• 16bit 做為機器号，預設的是目前機器的私有IP的最後兩位

sf.machineID, err = lower16BitPrivateIP()           

func lower16BitPrivateIP() (uint16, error) {
    ip, err := privateIPv4()
    if err != nil {
        return 0, err
    }
    return uint16(ip[2])<<8 + uint16(ip[3]), nil
}           

對于時間回撥的問題

Sonyflake

簡單暴力，就是直接等待 :

func (sf *Sonyflake) NextID() (uint64, error) {
    const maskSequence = uint16(1<<BitLenSequence - 1)
    sf.mutex.Lock()
    defer sf.mutex.Unlock()
    current := currentElapsedTime(sf.startTime)
    if sf.elapsedTime < current {
        sf.elapsedTime = current
        sf.sequence = 0
    } else { // sf.elapsedTime >= current
        sf.sequence = (sf.sequence + 1) & maskSequence
        if sf.sequence == 0 {
            sf.elapsedTime++
            overtime := sf.elapsedTime - current
            time.Sleep(sleepTime((overtime)))
        }
    }    
    return sf.toID()
}