一篇文章徹底搞懂snowflake演算法及百度美團的最佳實踐
- 2019 年 10 月 25 日
- 筆記
寫在前面的話
一提到分散式ID自動生成方案,大家肯定都非常熟悉,並且立即能說出自家拿手的幾種方案,確實,ID作為系統數據的重要標識,重要性不言而喻,而各種方案也是歷經多代優化,請允許我用這個視角對分散式ID自動生成方案進行分類:
實現方式
- 完全依賴數據源方式
ID的生成規則,讀取控制完全由數據源控制,常見的如資料庫的自增長ID,序列號等,或Redis的INCR/INCRBY原子操作產生順序號等。
- 半依賴數據源方式
ID的生成規則,有部分生成因子需要由數據源(或配置資訊)控制,如snowflake演算法。
- 不依賴數據源方式
ID的生成規則完全由機器資訊獨立計算,不依賴任何配置資訊和數據記錄,如常見的UUID,GUID等
實踐方案
實踐方案適用於以上提及的三種實現方式,可作為這三種實現方式的一種補充,旨在提升系統吞吐量,但原有實現方式的局限性依然存在。
- 實時獲取方案
顧名思義,每次要獲取ID時,實時生成。
簡單快捷,ID都是連續不間斷的,但吞吐量可能不是最高。
- 預生成方案
預先生成一批ID放在數據池裡,可簡單自增長生成,也可以設置步長,分批生成,需要將這些預先生成的數據,放在存儲容器里(JVM記憶體,Redis,資料庫表均可)。
可以較大幅度地提升吞吐量,但需要開闢臨時存儲空間,斷電宕機後可能會丟失已有ID,ID可能有間斷。
方案簡介
以下對目前流行的分散式ID方案做簡單介紹
- 資料庫自增長ID
屬於完全依賴數據源的方式,所有的ID存儲在資料庫里,是最常用的ID生成辦法,在單體應用時期得到了最廣泛的使用,建立數據表時利用資料庫自帶的auto_increment作主鍵,或是使用序列完成其他場景的一些自增長ID的需求。
- 優點:非常簡單,有序遞增,方便分頁和排序。
- 缺點:分庫分表後,同一數據表的自增ID容易重複,無法直接使用(可以設置步長,但局限性很明顯);性能吞吐量整個較低,如果設計一個單獨的資料庫來實現 分散式應用的數據唯一性,即使使用預生成方案,也會因為事務鎖的問題,高並發場景容易出現單點瓶頸。
- 適用場景:單資料庫實例的表ID(包含主從同步場景),部分按天計數的流水號等;分庫分表場景、全系統唯一性ID場景不適用。
- Redis生成ID
也屬於完全依賴數據源的方式,通過Redis的INCR/INCRBY自增原子操作命令,能保證生成的ID肯定是唯一有序的,本質上實現方式與資料庫一致。
- 優點:整體吞吐量比資料庫要高。
- 缺點:Redis實例或集群宕機後,找回最新的ID值有點困難。
- 適用場景:比較適合計數場景,如用戶訪問量,訂單流水號(日期+流水號)等。
- UUID、GUID生成ID
UUID:按照OSF制定的標準計算,用到了乙太網卡地址、納秒級時間、晶片ID碼和許多可能的數字。由以下幾部分的組合:當前日期和時間(UUID的第一個部分與時間有關,如果你在生成一個UUID之後,過幾秒又生成一個UUID,則第一個部分不同,其餘相同),時鐘序列,全局唯一的IEEE機器識別號(如果有網卡,從網卡獲得,沒有網卡以其他方式獲得)
GUID:微軟對UUID這個標準的實現。UUID還有其它各種實現,不止GUID一種,不一一列舉了。
這兩種屬於不依賴數據源方式,真正的全球唯一性ID
- 優點:不依賴任何數據源,自行計算,沒有網路ID,速度超快,並且全球唯一。
- 缺點:沒有順序性,並且比較長(128bit),作為資料庫主鍵、索引會導致索引效率下降,空間佔用較多。
- 適用場景:只要對存儲空間沒有苛刻要求的都能夠適用,比如各種鏈路追蹤、日誌存儲等。
4、snowflake演算法(雪花演算法)生成ID
屬於半依賴數據源方式,原理是使用Long類型(64位),按照一定的規則進行填充:時間(毫秒級)+集群ID+機器ID+序列號,每部分佔用的位數可以根據實際需要分配,其中集群ID和機器ID這兩部分,在實際應用場景中要依賴外部參數配置或資料庫記錄。
- 優點:高性能、低延遲、去中心化、按時間有序
- 缺點:要求機器時鐘同步(到秒級即可)
- 適用場景:分散式應用環境的數據主鍵
雪花ID演算法聽起來是不是特別適用分散式架構場景?照目前來看是的,接下來我們重點講解它的原理和最佳實踐。
snowflake演算法實現原理
snowflake演算法來源於Twitter,使用scala語言實現,利用Thrift框架實現RPC介面調用,最初的項目起因是資料庫從mysql遷移到Cassandra,Cassandra沒有現成可用 的ID生成機制,就催生了這個項目,現有的github源碼有興趣可以去看看。
snowflake演算法的特性是有序、唯一,並且要求高性能,低延遲(每台機器每秒至少生成10k條數據,並且響應時間在2ms以內),要在分散式環境(多集群,跨機房)下使用,因此snowflake演算法得到的ID是分段組成的:
- 與指定日期的時間差(毫秒級),41位,夠用69年
- 集群ID + 機器ID, 10位,最多支援1024台機器
- 序列,12位,每台機器每毫秒內最多產生4096個序列號
如圖所示:
- 1bit:符號位,固定是0,表示全部ID都是正整數
- 41bit:毫秒數時間差,從指定的日期算起,夠用69年,我們知道用Long類型表示的時間戳是從1970-01-01 00:00:00開始算起的,咱們這裡的時間戳可以指定日期,如2019-10-23 00:00:00
- 10bit:機器ID,有異地部署,多集群的也可以配置,需要線下規劃好各地機房,各集群,各實例ID的編號
- 12bit:序列ID,前面都相同的話,最多可以支援到4096個
以上的位數分配只是官方建議的,我們可以根據實際需要自行分配,比如說我們的應用機器數量最多也就幾十台,但並發數很大,我們就可以將10bit減少到8bit,序列部分從12bit增加到14bit等等
當然每部分的含義也可以自由替換,如中間部分的機器ID,如果是雲計算、容器化的部署環境,隨時有擴容,縮減機器的操作,通過線下規划去配置實例的ID不太現實,就可以替換為實例每重啟一次,拿一次自增長的ID作為該部分的內容,下文會講解。
github上也有大神用Java做了snowflake最基本的實現,這裡直接查看源碼:
snowflake java版源碼
/** * twitter的snowflake演算法 -- java實現 * * @author beyond * @date 2016/11/26 */ public class SnowFlake { /** * 起始的時間戳 */ private final static long START_STMP = 1480166465631L; /** * 每一部分佔用的位數 */ private final static long SEQUENCE_BIT = 12; //序列號佔用的位數 private final static long MACHINE_BIT = 5; //機器標識佔用的位數 private final static long DATACENTER_BIT = 5;//數據中心佔用的位數 /** * 每一部分的最大值 */ private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT); private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); /** * 每一部分向左的位移 */ private final static long MACHINE_LEFT = SEQUENCE_BIT; private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT; private long datacenterId; //數據中心 private long machineId; //機器標識 private long sequence = 0L; //序列號 private long lastStmp = -1L;//上一次時間戳 public SnowFlake(long datacenterId, long machineId) { if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) { throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0"); } if (machineId > MAX_MACHINE_NUM || machineId < 0) { throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0"); } this.datacenterId = datacenterId; this.machineId = machineId; } /** * 產生下一個ID * * @return */ public synchronized long nextId() { long currStmp = getNewstmp(); if (currStmp < lastStmp) { throw new RuntimeException("Clock moved backwards. Refusing to generate id"); } if (currStmp == lastStmp) { //相同毫秒內,序列號自增 sequence = (sequence + 1) & MAX_SEQUENCE; //同一毫秒的序列數已經達到最大 if (sequence == 0L) { currStmp = getNextMill(); } } else { //不同毫秒內,序列號置為0 sequence = 0L; } lastStmp = currStmp; return (currStmp - START_STMP) << TIMESTMP_LEFT //時間戳部分 | datacenterId << DATACENTER_LEFT //數據中心部分 | machineId << MACHINE_LEFT //機器標識部分 | sequence; //序列號部分 } private long getNextMill() { long mill = getNewstmp(); while (mill <= lastStmp) { mill = getNewstmp(); } return mill; } private long getNewstmp() { return System.currentTimeMillis(); } public static void main(String[] args) { SnowFlake snowFlake = new SnowFlake(2, 3); for (int i = 0; i < (1 << 12); i++) { System.out.println(snowFlake.nextId()); } } }
基本上通過位移操作,將每段含義的數值,移到相應的位置上,如機器ID這裡由數據中心+機器標識組成,所以,機器標識向左移12位,就是它的位置,數據中心的編號向左移17位,時間戳的值向左移22位,每部分佔據自己的位置,各不干涉,由此組成一個完整的ID值。
這裡就是snowflake最基礎的實現原理,如果有些java基礎知識不記得了建議查一下資料,如二進位-1的表示是0xffff(裡面全是1),<<表示左移操作,-1<<5等於-32,異或操作-1 ^ (-1 << 5)為31等等。
了解snowflake的基本實現原理,可以通過提前規劃好機器標識來實現,但目前的分散式生產環境,借用了多種雲計算、容器化技術,實例的個數隨時有變化,還需要處理伺服器實例時鐘回撥的問題,固定規劃ID然後通過配置來使用snowflake的場景可行性不高,一般是自動啟停,增減機器,這樣就需要對snowflake進行一些改造才能更好地應用到生產環境中。
百度uid-generator項目
UidGenerator項目基於snowflake原理實現,只是修改了機器ID部分的定義(實例重啟的次數),並且64位bit的分配支援配置,官方提供的默認分配方式如下圖:
Snowflake演算法描述:指定機器 & 同一時刻 & 某一併發序列,是唯一的。據此可生成一個64 bits的唯一ID(long)。
- sign(1bit) 固定1bit符號標識,即生成的UID為正數。
- delta seconds (28 bits)
當前時間,相對於時間基點"2016-05-20"的增量值,單位:秒,最多可支援約8.7年 - worker id (22 bits) 機器id,最多可支援約420w次機器啟動。內置實現為在啟動時由資料庫分配,默認分配策略為用後即棄,後續可提供復用策略。
- sequence (13 bits) 每秒下的並發序列,13 bits可支援每秒8192個並發。
具體的實現有兩種,一種是實時生成ID,另一種是預先生成ID方式
- DefaultUidGenerator
- 啟動時向資料庫WORKER_NODE表插入當前實例的IP,Port等資訊,再獲取該數據的自增長ID作為機器ID部分。
簡易流程圖如下:
- 提供獲取ID的方法,並且檢測是否有時鐘回撥,有回撥現象直接拋出異常,當前版本不支援時鐘順撥後漂移操作。簡易流程圖如下:
核心程式碼如下:
/** * Get UID * * @return UID * @throws UidGenerateException in the case: Clock moved backwards; Exceeds the max timestamp */ protected synchronized long nextId() { long currentSecond = getCurrentSecond(); // Clock moved backwards, refuse to generate uid if (currentSecond < lastSecond) { long refusedSeconds = lastSecond - currentSecond; throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds); } // At the same second, increase sequence if (currentSecond == lastSecond) { sequence = (sequence + 1) & bitsAllocator.getMaxSequence(); // Exceed the max sequence, we wait the next second to generate uid if (sequence == 0) { currentSecond = getNextSecond(lastSecond); } // At the different second, sequence restart from zero } else { sequence = 0L; } lastSecond = currentSecond; // Allocate bits for UID return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence); }
- CachedUidGenerator
機器ID的獲取方法與上一種相同,這種是預先生成一批ID,放在一個RingBuffer環形數組裡,供客戶端使用,當可用數據低於閥值時,再次調用批量生成方法,屬於用空間換時間的做法,可以提高整個ID的吞吐量。
- 與DefaultUidGenerator相比較,初始化時多了填充RingBuffer環形數組的邏輯,簡單流程圖如下:
核心程式碼:
/** * Initialize RingBuffer & RingBufferPaddingExecutor */ private void initRingBuffer() { // initialize RingBuffer int bufferSize = ((int) bitsAllocator.getMaxSequence() + 1) << boostPower; this.ringBuffer = new RingBuffer(bufferSize, paddingFactor); LOGGER.info("Initialized ring buffer size:{}, paddingFactor:{}", bufferSize, paddingFactor); // initialize RingBufferPaddingExecutor boolean usingSchedule = (scheduleInterval != null); this.bufferPaddingExecutor = new BufferPaddingExecutor(ringBuffer, this::nextIdsForOneSecond, usingSchedule); if (usingSchedule) { bufferPaddingExecutor.setScheduleInterval(scheduleInterval); } LOGGER.info("Initialized BufferPaddingExecutor. Using schdule:{}, interval:{}", usingSchedule, scheduleInterval); // set rejected put/take handle policy this.ringBuffer.setBufferPaddingExecutor(bufferPaddingExecutor); if (rejectedPutBufferHandler != null) { this.ringBuffer.setRejectedPutHandler(rejectedPutBufferHandler); } if (rejectedTakeBufferHandler != null) { this.ringBuffer.setRejectedTakeHandler(rejectedTakeBufferHandler); } // fill in all slots of the RingBuffer bufferPaddingExecutor.paddingBuffer(); // start buffer padding threads bufferPaddingExecutor.start(); }
public synchronized boolean put(long uid) { long currentTail = tail.get(); long currentCursor = cursor.get(); // tail catches the cursor, means that you can't put any cause of RingBuffer is full long distance = currentTail - (currentCursor == START_POINT ? 0 : currentCursor); if (distance == bufferSize - 1) { rejectedPutHandler.rejectPutBuffer(this, uid); return false; } // 1. pre-check whether the flag is CAN_PUT_FLAG int nextTailIndex = calSlotIndex(currentTail + 1); if (flags[nextTailIndex].get() != CAN_PUT_FLAG) { rejectedPutHandler.rejectPutBuffer(this, uid); return false; } // 2. put UID in the next slot // 3. update next slot' flag to CAN_TAKE_FLAG // 4. publish tail with sequence increase by one slots[nextTailIndex] = uid; flags[nextTailIndex].set(CAN_TAKE_FLAG); tail.incrementAndGet(); // The atomicity of operations above, guarantees by 'synchronized'. In another word, // the take operation can't consume the UID we just put, until the tail is published(tail.incrementAndGet()) return true; }
- ID獲取邏輯,由於有RingBuffer這個緩衝數組存在,獲取ID直接從RingBuffer取出即可,同時RingBuffer自身校驗何時再觸發重新批量生成即可,這裡獲取的ID值與DefaultUidGenerator的明顯區別是,DefaultUidGenerator獲取的ID,時間戳部分就是當前時間的,CachedUidGenerator里獲取的是填充時的時間戳,並不是獲取時的時間,不過關係不大,都是不重複的,一樣用。簡易流程圖如下:
核心程式碼:
public long take() { // spin get next available cursor long currentCursor = cursor.get(); long nextCursor = cursor.updateAndGet(old -> old == tail.get() ? old : old + 1); // check for safety consideration, it never occurs Assert.isTrue(nextCursor >= currentCursor, "Curosr can't move back"); // trigger padding in an async-mode if reach the threshold long currentTail = tail.get(); if (currentTail - nextCursor < paddingThreshold) { LOGGER.info("Reach the padding threshold:{}. tail:{}, cursor:{}, rest:{}", paddingThreshold, currentTail, nextCursor, currentTail - nextCursor); bufferPaddingExecutor.asyncPadding(); } // cursor catch the tail, means that there is no more available UID to take if (nextCursor == currentCursor) { rejectedTakeHandler.rejectTakeBuffer(this); } // 1. check next slot flag is CAN_TAKE_FLAG int nextCursorIndex = calSlotIndex(nextCursor); Assert.isTrue(flags[nextCursorIndex].get() == CAN_TAKE_FLAG, "Curosr not in can take status"); // 2. get UID from next slot // 3. set next slot flag as CAN_PUT_FLAG. long uid = slots[nextCursorIndex]; flags[nextCursorIndex].set(CAN_PUT_FLAG); // Note that: Step 2,3 can not swap. If we set flag before get value of slot, the producer may overwrite the // slot with a new UID, and this may cause the consumer take the UID twice after walk a round the ring return uid; }
另外有個細節可以了解一下,RingBuffer的數據都是使用數組來存儲的,考慮CPU Cache的結構,tail和cursor變數如果直接用原生的AtomicLong類型,tail和cursor可能會快取在同一個cacheLine中,多個執行緒讀取該變數可能會引發CacheLine的RFO請求,反而影響性能,為了防止偽共享問題,特意填充了6個long類型的成員變數,加上long類型的value成員變數,剛好佔滿一個Cache Line(Java對象還有8byte的對象頭),這個叫CacheLine補齊,有興趣可以了解一下,源碼如下:
public class PaddedAtomicLong extends AtomicLong { private static final long serialVersionUID = -3415778863941386253L; /** Padded 6 long (48 bytes) */ public volatile long p1, p2, p3, p4, p5, p6 = 7L; /** * Constructors from {@link AtomicLong} */ public PaddedAtomicLong() { super(); } public PaddedAtomicLong(long initialValue) { super(initialValue); } /** * To prevent GC optimizations for cleaning unused padded references */ public long sumPaddingToPreventOptimization() { return p1 + p2 + p3 + p4 + p5 + p6; } }
以上是百度uid-generator項目的主要描述,我們可以發現,snowflake演算法在落地時有一些變化,主要體現在機器ID的獲取上,尤其是分散式集群環境下面,實例自動伸縮,docker容器化的一些技術,使得靜態配置項目ID,實例ID可行性不高,所以這些轉換為按啟動次數來標識。
美團ecp-uid項目
在uidGenerator方面,美團的項目源碼直接集成百度的源碼,略微將一些Lambda表達式換成原生的java語法,例如:
// com.myzmds.ecp.core.uid.baidu.impl.CachedUidGenerator類的initRingBuffer()方法 // 百度源碼 this.bufferPaddingExecutor = new BufferPaddingExecutor(ringBuffer, this::nextIdsForOneSecond, usingSchedule); // 美團源碼 this.bufferPaddingExecutor = new BufferPaddingExecutor(ringBuffer, new BufferedUidProvider() { @Override public List<Long> provide(long momentInSecond) { return nextIdsForOneSecond(momentInSecond); } }, usingSchedule);
並且在機器ID生成方面,引入了Zookeeper,Redis這些組件,豐富了機器ID的生成和獲取方式,實例編號可以存儲起來反覆使用,不再是資料庫單調增長這一種了。
結束語
本篇簡單介紹了snowflake演算法的原理及落地過程中的改造,在此學習了優秀的開源程式碼,並挑出部分進行了簡單的示例,美團的ecp-uid項目不但集成了百度現有的UidGenerator演算法,原生的snowflake演算法,還包含優秀的leaf segment演算法,鑒於篇幅沒有詳盡描述。文章內有任何不正確或不詳盡之處請留言指出,謝謝。
專註Java高並發、分散式架構,更多技術乾貨分享與心得,請關注公眾號:Java架構社區