分布式理論：分布式 ID 方案、雪花算法與時鐘回撥問題
一、為什么需要全局唯一ID
傳統的單體架構的時候，我們基本是單庫然后業務單表的結構。每個業務表的ID一般我們都是從1增，通過AUTO_INCREMENT=1設置自增起始值，但是在分布式服務架構模式下分庫分表的設計，使得多個庫或多個表存儲相同的業務數據。這種情況根據數據庫的自增ID就會產生相同ID的情況，不能保證主鍵的唯一性。
如上圖，如果第一個訂單存儲在 DB1 上則訂單 ID 為1，當一個新訂單又入庫了存儲在 DB2 上訂單 ID 也為1。我們系統的架構雖然是分布式的，但是在用戶層應是無感知的，重復的訂單主鍵顯而易見是不被允許的。那么針對分布式系統如何做到主鍵唯一性呢？
二、UUID
UUID （Universally Unique Identifier），通用唯一識別碼的縮寫。UUID是由一組32位數的16進制數字所構成，所以UUID理論上的總數為 16^32=2^128，約等于 3.4 x 10^38。也就是說若每納秒產生1兆個UUID，要花100億年才會將所有UUID用完。
生成的UUID是由 8-4-4-4-12格式的數據組成，其中32個字符和4個連字符' - '，一般我們使用的時候會將連字符刪除 uuid.toString().replaceAll("-","")。
目前UUID的產生方式有5種版本，每個版本的算法不同，應用范圍也不同。
- 基于時間的UUID - 版本1：這個一般是通過當前時間，隨機數，和本地Mac地址來計算出來，可以通過 org.apache.logging.log4j.core.util包中的 UuidUtil.getTimeBasedUuid()來使用或者其他包中工具。由于使用了MAC地址，因此能夠確保唯一性，但是同時也暴露了MAC地址，私密性不夠好。
- DCE安全的UUID - 版本2 DCE（Distributed Computing Environment）安全的UUID和基于時間的UUID算法相同，但會把時間戳的前4位置換為POSIX的UID或GID。這個版本的UUID在實際中較少用到。
- 基于名字的UUID（MD5）- 版本3 基于名字的UUID通過計算名字和名字空間的MD5散列值得到。這個版本的UUID保證了：相同名字空間中不同名字生成的UUID的唯一性；不同名字空間中的UUID的唯一性；相同名字空間中相同名字的UUID重復生成是相同的。
- 隨機UUID - 版本4 根據隨機數，或者偽隨機數生成UUID。這種UUID產生重復的概率是可以計算出來的，但是重復的可能性可以忽略不計，因此該版本也是被經常使用的版本。JDK中使用的就是這個版本。
- 基于名字的UUID（SHA1） - 版本5 和基于名字的UUID算法類似，只是散列值計算使用SHA1（Secure Hash Algorithm 1）算法。
雖然 UUID 生成方便，本地生成沒有網絡消耗，但是使用起來也有一些缺點，
- 不易于存儲：UUID太長，16字節128位，通常以36長度的字符串表示，很多場景不適用。
- 信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露，暴露使用者的位置。
- 對MySQL索引不利：如果作為數據庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起數據位置頻繁變動，嚴重影響性能。
三、中間層
從為什么需要全局唯一ID里面可知，是因為獲取ID的源從以前的一個變成了多個，所以才會導致重復，那我們只需要做一個公共的獲取ID的中間層就可以了，像利用公共的Mqsql、公共的Redis、公共的MongoDB、公共的ID生成服務組件都是這樣的道理。
總的來說有三種方案：
(1) 單純遞增
比如：Mysql的自增、redis的INCR、mongoDB的自增等，優點是簡單易實現，缺點是競爭過大、吞吐量低、可用性差。
(2) 步長遞增
以Mysql舉例，假設現在根據業務分了4個庫了，代表有4個表，分別是T1、T2、T3、T4，我們設置它們的起始值為1,2,3,4，步長為4，那它們id則為下所示：
T1：1,5,9,13,17
T2：2,6,10,14,18
T3：3,7,11,15,19
T4：4,8,12,16,20可見一樣也不會重復，優點是打破單調遞增的局限、性能相比較好，缺點不利于拓展，特殊情況可能會導致重復。
(3) 號段模式
同樣以Mysql為例，以上ID都是一個一個的分發，自然導致了并發可能過大的問題，此模式就是為了降低對中間層的訪問次數，一次性發放一批ID給客戶端緩存，用完了在重新獲取，這就是這模式的核心思想，具體以實際為準。
四、雪花算法-Snowflake
Snowflake，雪花算法是由Twitter開源的分布式ID生成算法，以劃分命名空間的方式將 64-bit位分割成多個部分，每個部分代表不同的含義。而 Java中64bit的整數是Long類型，所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 來存儲的。
- 第1位占用1bit，其值始終是0，可看做是符號位不使用。
- 第2位開始的41位是時間戳，41-bit位可表示2^41個數，每個數代表毫秒，那么雪花算法可用的時間年限是(1L<<41)/(1000L360024*365)=69 年的時間。
- 中間的10-bit位可表示機器數，即2^10 = 1024臺機器，但是一般情況下我們不會部署這么臺機器。如果我們對IDC（互聯網數據中心）有需求，還可以將 10-bit 分 5-bit 給 IDC，分5-bit給工作機器。這樣就可以表示32個IDC，每個IDC下可以有32臺機器，具體的劃分可以根據自身需求定義。
- 最后12-bit位是自增序列，可表示2^12 = 4096個數。
這樣的劃分之后相當于在一毫秒一個數據中心的一臺機器上可產生4096個有序的不重復的ID。但是我們 IDC 和機器數肯定不止一個，所以毫秒內能生成的有序ID數是翻倍的。
雪花算法提供了一個很好的設計思想，雪花算法生成的ID是趨勢遞增，不依賴數據庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也是非常高的，而且可以根據自身業務特性分配bit位，非常靈活。
但是雪花算法強依賴機器時鐘，如果機器上時鐘回撥，會導致發號重復或者服務會處于不可用狀態。如果恰巧回退前生成過一些ID，而時間回退后，生成的ID就有可能重復。官方對于此并沒有給出解決方案，而是簡單的拋錯處理，這樣會造成在時間被追回之前的這段時間服務不可用。并發足夠大的情況下，ID會用完，因為自增序列會達到上限。
以上每種模式都有自己的缺點，實際上大多是以上幾種模式的結合來運用的，比如美團的Leaf、百度的UidGenerator，所以大方向是兩個方案：
- 綜合后的緩存+號段
- 雪花的改良，天然的唯一性。
五、如何解決時鐘回撥問題
時鐘回撥：指的是系統時鐘被向后調整到之前的時間，也就是在某一瞬間，系統時間突然跳回到之前的某個時間點；
這對雪花來說無疑是致命！
這個問題談不上解決，只能說規避或者保證唯一的解決方案：
(1) 拒絕策略
這個很簡單，就是檢測到時鐘回撥后，拒絕ID的生成。
(2) 使用物理時鐘和邏輯時鐘結合的方式
物理時鐘是指系統硬件上的時鐘，它具有不同步的風險。而邏輯時鐘則是指根據本地時鐘和網絡時間協議（NTP）獲取的網絡時鐘計算出來的時間戳，它具有更好的同步性能。
在使用邏輯時鐘時，可以將本地的邏輯時鐘與 NTP 服務提供的時間進行比較，并使用兩個時鐘之間的差值來確定當前的本地時間。如果本地時鐘發生回撥，可以通過記錄回撥的信息以及處理回撥前后的時間變化來避免ID重復或生成失敗。
(3) 時間后移消費
每次產生ID的時候保存一次時間，發生時間回撥的時候，取出緩存的時間+1s，缺點是時間可能會錯位。
