Snow Algorithm 雪花演算法

什麼是雪花演算法？

我們都知道在自然界當中每一片雪花都是獨一無二的。在目前提倡容器化、分散式的架構時代下，很可能會遇到 ID 重號的問題，我們對 ID 的期望就會希望雪花般一樣都不重複。

這個演算法最早是由 Twitter 所創建的，主要是拿來產推文的 ID，後來這套演算法被 Discord、Instagram採用，也衍伸許多不同格式的版本。

會想要使用這套演算法的原因是因為筆者想要拿它產生 token，快取在 redis 上，合法的使用者可以拿著這個 token 存取筆者在部署 Docker 上的微服務系統。

雪花演算法核心組成

筆者先為大家科普一下雪花演算法的組成的成分，主要共分 4 個欄位組成 64 位元，頭一個位元我們不使用，其他欄位下方逐一跟各位說明。

時間戳記

第二欄位是時間戳記，共 41 個位元，以 UNIX 時間（起始年是 1970 年）的毫秒為單位正好可以填滿41 bits 的空間，可表示最大數為 2,199,023,255,551，以毫秒計算約 69 年，這個數值是兩個時戳相減得出的。

如果是拿當下的時間戳填進去這個欄位，那麼數值很快就會到達天花板，我們身為生活智慧王，當然要善用空間，所以才會以產生 token 的時間戳減去一個開始時間戳。

由於前面有提到是微服務，為了保持一致，開始時間戳需要寫死，建議可以訂在系統上線前的日期，像筆者就選擇把開始時間的時戳訂成自己的生日。

工作站台 ID

第三欄位是工作站台 ID，共 10 個位元，用來區分哪ㄧ台機器發出的 token。

流水號

第四欄位是流水號 ID，共 12 個位元，意思是同一個時間下同一機器所配發出去的流水號，從 0 開始遞增，直到進入下一個毫秒，流水號再重新編號。

演算法說明

位元分配器

筆者建立一個類別叫作 BitsAllocator，主要做兩件工作，第一件事是初起化各個欄位位元數，第二件是配發雪花演算法的唯一 ID，以下筆者會逐一說明。

一開始在 BitsAllocator 的建構子決定好各欄位要多長，由參考 BitsAllocator 的類別去制定，假設我們按造預設的長度，那麼建構子內的三個參數分別為 41, 10, 12。

第二步就是要製作位元遮罩，所以我們要取得這三個欄位的最大值，舉例來說如果我們想要取得工作站 ID 的最大值 2¹⁰ — 1，也就是 10 個位元都是 1。

如何取得最大值呢？在 Java 的世界中整數採用二的補數，先將 — 1 向左位移 10 個位元的位置，再位元 NOT 運算，就可以得到囉。

第三步要把各個欄位擺放到正確的位置，像是時間戳記需要位元要向左位移 10 + 12 個位元，工作站站台 ID 要向左位移 12 個位元，流水號則不需要移動，所以我們需要紀錄一下到時候要位移的個數。

第四步就是把它們像積木一樣拼起來，筆者這邊設計一個方法，讓參考BitsAllocator 的類別呼叫 allocate，把當下的時間戳、機器的 ID、配發的流水號傳進來，該方法會把這三個欄位推到正確的位置，用到的是我們上面紀錄下來位移的各個去推，最後用 OR 運算合併。

唯一性 ID 取號器

筆者設計了一個 SnowFlakeAlg 類別用來取號。

一開始建構 SnowFlakeAlg 類別，首先先注入 BitsAllocator，後續我們取號的時候會使用到。由於每一個放置在 Docker 容器內每一個微服務都會分配一組 IP，所以筆者是取其 IPv4 第四個欄位作為工作站站台 ID。

這組 IP 是怎麼得來的呢？Java 會在作業系統建立 Socket 連線，使用 InetAddress.getLocalHost().getHostAddress() ，可以得到本機的主機位址。

至於時戳怎麼產生呢？是呼叫 System.currentTimeMillis() 取得系統當下的時戳，記得前面我們有說雪花演算法時戳這個欄位是兩個毫秒相減得出的嗎？系統當下的時戳減去一個我們是先制定好的開始時戳，這邊我減去的是我去年的生日那天，如果結果值大於 2⁴¹ — 1，那就代表時戳佔用位元已耗盡，無法產製唯一性 ID。

會呼叫 nextMilliSecond() 方法原因在上一毫秒的流水號已經分配完，所以要循環等待到下一毫秒，為了避免因為機器硬體時鐘問題造成時戳還停留在過去，所以我們有寫了 while 迴圈，重新取時戳，同時判斷是否有大於上一個時戳的時間。

SnowFlakeAlg 類別主要功能也就是取號，第一先取得系統當下的時戳，同一個毫秒下，我們就讓遞增取流水號，在取號的過程中，我們會拿遞增後的流水號跟流水號的最大值做 AND 運算，看結果值是否為 0？如果是，那代表該時戳可分配的流水號全部分玩了，需要等到下一個毫秒，再重新分配。

最後我們拿系統時戳減開始時戳、工作站 ID、流水號當作參數呼叫bitsAllocator.allocate()，就可以拿到唯一性的 ID 當作 token 使用了。

完整程式碼

SnowflakeAlgo