What Are Snowflake IDs?

Credit by: Wei-Yu Chen (感謝分享)

本文介紹了 Universal Unique Identifiers（UUIDs）的用途及其重要性，UUID 以固定且標準的方式為每個物件產生出獨立的 ID，且 產生出來的 ID 幾乎不可能會重複導致發生碰撞。

通常 UUID 由幾個部分組合而成，像是以時間、執行節點的 MAC address，或以 MD5 hash 來生成。UUID 以 128 bits 的數字組成，為了更方便識別及操作，通常都會以十六進制來表示，總長度為 36 個字（加上連字符號 -）。也因用來產生 UUID 的亂數種子包含了時間、節點資訊等參數，所以 UUID 也具有獨特性，在分散式系統執行也不容易發生碰撞。

而為了避免在你的 apps 裡實作 UUID 的產生機制，常見會使用兩種作法，分別是：Persistence Layer Generated ID 和 ID Servers。一種使用 Database 自動產生出來的序號來作為識別物件的 ID（如 MongoDB 的 ObjectID、MySQL 的 AUTO_INCREMENT ... 等），另一種是使用獨立的 ID server 來產生物件的 ID。

以 Database 來作為序號產生器會碰到一個問題，當你在每次建立新物件時，都會需要向資料庫讀取這個物件的「自動產生 ID」，假設應用程式的規模一大，效能勢必會大受影響。

而使用 ID server（也就是本文主要介紹的 Snowflake IDs）去產生 UUID 的話，就可利用架構於 app 以外的第三方序號產生器。以 Twitter 來說，平均每秒鐘有九千個推文，在高峰期間更甚至會出現一秒 143199 則推文的流量，他們所需要的 UUID 不僅要能夠支援龐大的架構，也需要在以非常快的速度產生出 ID，這也是 Snowflake 專案的由來。

因此，Twitter 以這幾個參數來組成 UUID：
- 保留不使用的位元，固定為 0 - 共 1 位
- Timestamp（以毫秒為單位） - 共 41 位
- 機器 ID - 共 10 位
- 序列號 - 從 0 ~ 4095 依序重複使用 - 共 12 位

雖然說以 ID servers 來產生 UUID 之後，效能還是會被這種架構拖累（必須在建立物件就去向 ID server 發送請求，並等待產生出來的 ID），但這種作法和資料庫系統相比起來已經讓效能降低的問題變得更輕微。

在本文當中介紹了三種常見的 ID 產生方式：在 local app 端產生 ID、在資料庫產生 ID、集中式的 ID server 產生 ID，這些策略的選擇也根據你的使用情境而定，畢竟沒有一種一套打天下的解決方案，在選擇時仍須衡量每個專案的需求。

https://betterprogramming.pub/uuid-generation-snowflake-identifiers-unique-2aed8b1771bc

Gorilla 是 Facebook 這兩年開發的 time-series 資料庫，這篇論文是去年下半年就已經發表了，小編當時想說找時間慢慢看，沒想到已經有強者寫了一篇導讀文，真的是該拜一下 XD

Facebook 為了要讓監控系統操作人員快速容易取得系統發生狀況時的主因，並同時兼顧高效率、可擴充性及可靠度，所以開發了這套 in-memory 的 TSDB。

Facebook 在 Gorilla 上面存了許多系統資料，比如說 CPU loading, latency......等，而且每秒可以存上千萬級的資料點，相同資料只需要幾毫秒就能取得。

另外 Gorilla 要接受的挑戰還有以下這些：

* 一個字串可以一次表示 20 億個時序數字
* 1 分鐘可以存 70 億筆 timestamp 及數值
* 可以存 26 個小時的資料
* 高峰時 1 秒可以容納 4 萬個以上的讀取
* 1 毫秒以內可以讀取成功
* 能支援 15 秒的粒度
* 不在同一區域，但又要相同的兩份 in-memory 資料
* 單一台伺服器當掉時仍然可以正常讀取資料
* 可以很快速的掃描所有資料
* 至少支援每年 2 倍以上的成長。

這篇文章內另外介紹的是 Gorilla 如何壓縮資料，用的是 delta of delta 及 XOR 運算，導讀文跟原論文的內容都很棒！推薦 Backend 的大家一讀！

* Gorilla: A Fast, Scalable, In-Memory Time Series Database: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

#facebook #gorilla #tsdb #hbase