生成ID的基本要求

1.必須全局唯一,包括在分布式的環(huán)境下
2.一般都需要單調(diào)遞增,因?yàn)橐话愣紩娴綌?shù)據(jù)庫,而Innodb的特性就是將內(nèi)容存儲在主鍵索引樹上的葉子節(jié)點(diǎn),而且是從左往右,遞增的,所以考慮到數(shù)據(jù)庫性能,一般生成的id也最好是單調(diào)遞增.
3.可能還會需要無規(guī)則,因?yàn)槿绻褂梦ㄒ籌D作為訂單號這種,為了不然別人知道一天的訂單量是多少,就需要這個規(guī)則.

常見唯一Id生成方案

UUID

數(shù)據(jù)庫生成

Leaf-segment數(shù)據(jù)庫方案

Leaf-snowflake方案

UUID

UUID(Universally Unique Identifier)的標(biāo)準(zhǔn)型式包含32個16進(jìn)制數(shù)字，以連字號分為五段，形式為8-4-4-4-12的36個字符.
目前共有5種方式生成UUID，詳情見IETF發(fā)布的UUID規(guī)范 A Universally Unique IDentifier (UUID) URN Namespace。

優(yōu)點(diǎn):

本地生成刀崖，沒有網(wǎng)絡(luò)消耗，性能很高

缺點(diǎn):

①不易于存儲：UUID太長蜀撑，16字節(jié)128位村怪，通常以36長度的字符串表示，很多場景不適用冀膝。
②信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露唁奢，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
③ID作為主鍵時在特定的環(huán)境會存在一些問題窝剖，比如做DB主鍵的場景下麻掸，UUID就非常不適用：對MySQL索引不利：如果作為數(shù)據(jù)庫主鍵，在InnoDB引擎下赐纱，UUID的無序性可能會引起數(shù)據(jù)位置頻繁變動脊奋，嚴(yán)重影響性能。

雪花算法snowflake

把64-bit分別劃分成多段疙描，分開來標(biāo)示機(jī)器诚隙、時間

雪花算法.png

41-bit的時間可以表示（1L<<41）/(1000L360024*365)=69年的時間，10-bit機(jī)器可以分別表示1024臺機(jī)器起胰。如果我們對IDC劃分有需求久又，還可以將10-bit分5-bit給IDC，分5-bit給工作機(jī)器效五。這樣就可以表示32個IDC地消，每個IDC下可以有32臺機(jī)器，可以根據(jù)自身需求定義畏妖。12個自增序列號可以表示2^12個ID脉执，理論上snowflake方案的QPS約為409.6w/s，這種分配方式可以保證在任何一個IDC的任何一臺機(jī)器在任意毫秒內(nèi)生成的ID都是不同的戒劫。

優(yōu)點(diǎn):

①毫秒數(shù)在高位半夷，自增序列在低位，整個ID都是趨勢遞增的
②不依賴數(shù)據(jù)庫等第三方系統(tǒng)谱仪，以服務(wù)的方式部署玻熙，穩(wěn)定性更高，生成ID的性能也是非常高的疯攒。
③可以根據(jù)自身業(yè)務(wù)特性分配bit位嗦随，非常靈活。

缺點(diǎn):

強(qiáng)依賴機(jī)器時鐘，如果機(jī)器上時鐘回?fù)苊赌幔瑫?dǎo)致發(fā)號重復(fù)或者服務(wù)會處于不可用狀態(tài)贴浙。而多機(jī)下時鐘不同步是很正常的

數(shù)據(jù)庫生成

利用給字段設(shè)置auto_increment_increment和auto_increment_offset(表示步長,即每次自增多少)來保證ID自增，每次業(yè)務(wù)使用下列SQL讀寫MySQL得到ID號署恍。

begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');SELECT LAST_INSERT_ID();
commit;

優(yōu)點(diǎn):

①非常簡單崎溃，利用現(xiàn)有數(shù)據(jù)庫系統(tǒng)的功能實(shí)現(xiàn)，成本小盯质，有DBA專業(yè)維護(hù)袁串。
②ID號單調(diào)自增，可以實(shí)現(xiàn)一些對ID有特殊要求的業(yè)務(wù)呼巷。

缺點(diǎn):

①強(qiáng)依賴DB囱修，當(dāng)DB異常時整個系統(tǒng)不可用，屬于致命問題王悍。配置主從復(fù)制可以盡可能的增加可用性破镰，但是數(shù)據(jù)一致性在特殊情況下難以保證。主從切換時的不一致可能會導(dǎo)致重復(fù)發(fā)號压储。
②ID發(fā)號性能瓶頸限制在單臺MySQL的讀寫性能鲜漩。

當(dāng)然也可以在數(shù)據(jù)庫壓力不是很大的時候,批量生成加載至redis中,需要的時候直接從redis中獲取,同時監(jiān)控,redis里的使用,達(dá)到一定百分比時觸發(fā)數(shù)據(jù)庫再生成一批導(dǎo)入至redis中.

Leaf-segment數(shù)據(jù)庫方案

原方案每次獲取ID都得讀寫一次數(shù)據(jù)庫，造成數(shù)據(jù)庫壓力大集惋。改為利用proxy server批量獲取孕似，每次獲取一個segment(step決定大小)號段的值。用完之后再去數(shù)據(jù)庫獲取新的號段芋膘，可以大大的減輕數(shù)據(jù)庫的壓力鳞青。
各個業(yè)務(wù)不同的發(fā)號需求用biz_tag字段來區(qū)分，每個biz-tag的ID獲取相互隔離为朋，互不影響臂拓。如果以后有性能需求需要對數(shù)據(jù)庫擴(kuò)容，不需要上述描述的復(fù)雜的擴(kuò)容操作习寸，只需要對biz_tag分庫分表就行胶惰。

表設(shè)計(jì)如下:

+-------------+--------------+------+-----+-------------------+-----------------------------+| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

字段說明

biz_tag用來區(qū)分業(yè)務(wù)，max_id表示該biz_tag目前所被分配的ID號段的最大值霞溪，step表示每次分配的號段長度孵滞。原來獲取ID每次都需要寫數(shù)據(jù)庫，現(xiàn)在只需要把step設(shè)置得足夠大鸯匹，比如1000坊饶。那么只有當(dāng)1000個號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫。讀寫數(shù)據(jù)庫的頻率從1減小到了1/step

Leaf-segment方案架構(gòu)圖.png

test_tag在第一臺Leaf機(jī)器上是1-1000的號段殴蓬，當(dāng)這個號段用完時匿级，會去加載另一個長度為step=1000的號段蟋滴，假設(shè)另外兩臺號段都沒有更新，這個時候第一臺機(jī)器新加載的號段就應(yīng)該是3001~4000痘绎。同時數(shù)據(jù)庫對應(yīng)的biz_tag這條數(shù)據(jù)的max_id會從3000被更新成4000津函，更新號段的SQL語句如下：

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxxSELECT tag, max_id, step FROM table WHERE biz_tag=xxx;
Commit

優(yōu)點(diǎn):

①Leaf服務(wù)可以很方便的線性擴(kuò)展，性能完全能夠支撐大多數(shù)業(yè)務(wù)場景孤页。
②ID號碼是趨勢遞增的8byte的64位數(shù)字尔苦，滿足上述數(shù)據(jù)庫存儲的主鍵要求。
③容災(zāi)性高：Leaf服務(wù)內(nèi)部有號段緩存行施，即使DB宕機(jī)允坚，短時間內(nèi)Leaf仍能正常對外提供服務(wù)。
④可以自定義max_id的大小蛾号，非常方便業(yè)務(wù)從原有的ID方式上遷移過來屋讶。

缺點(diǎn):

①ID號碼不夠隨機(jī)，能夠泄露發(fā)號數(shù)量的信息须教，不太安全。
②TP999數(shù)據(jù)波動大斩芭，當(dāng)號段使用完之后還是會hang在更新數(shù)據(jù)庫的I/O上轻腺，tg999數(shù)據(jù)會出現(xiàn)偶爾的尖刺。
③DB宕機(jī)會造成整個系統(tǒng)不可用划乖。

優(yōu)化方案

對于第二個缺點(diǎn)贬养，可以做如下優(yōu)化，不需要在DB取號段的時候阻塞請求線程琴庵，即當(dāng)號段消費(fèi)到某個點(diǎn)時就異步的把下一個號段加載到內(nèi)存中误算。而不需要等到號段用盡的時候才去更新號段。這樣做就可以很大程度上的降低系統(tǒng)的TP999指標(biāo)迷殿。如下圖所示：

Leaf預(yù)加載優(yōu)化.png

服務(wù)內(nèi)部有兩個號段緩存區(qū)segment儿礼。當(dāng)前號段已下發(fā)10%時，如果下一個號段未更新庆寺，則另啟一個更新線程去更新下一個號段蚊夫。當(dāng)前號段全部下發(fā)完后，如果下個號段準(zhǔn)備好了則切換到下個號段為當(dāng)前segment接著下發(fā)懦尝，循環(huán)往復(fù)知纷。

每個biz-tag都有消費(fèi)速度監(jiān)控，通常推薦segment長度設(shè)置為服務(wù)高峰期發(fā)號QPS的600倍（10分鐘）陵霉，這樣即使DB宕機(jī)琅轧，Leaf仍能持續(xù)發(fā)號10-20分鐘不受影響。
每次請求來臨時都會判斷下個號段的狀態(tài)踊挠，從而更新此號段乍桂，所以偶爾的網(wǎng)絡(luò)抖動不會影響下個號段的更新。

對于數(shù)據(jù)庫宕機(jī)的優(yōu)化,可以使用數(shù)據(jù)庫的集群部署,保證高可用

Leaf-snowflake方案

由于Leaf-segment方案可以生成趨勢遞增的ID，同時ID號是可計(jì)算的,所以是可以計(jì)算業(yè)務(wù)量的

而Leaf-snowflake又有什么改進(jìn)呢?

Leaf-snowflake方案.png

Leaf-snowflake方案完全沿用snowflake方案的bit位設(shè)計(jì)模蜡，即是“1+41+10+12”的方式組裝ID號漠趁。對于workerID的分配，當(dāng)服務(wù)集群數(shù)量較小的情況下忍疾，完全可以手動配置闯传。Leaf服務(wù)規(guī)模較大，動手配置成本太高卤妒。所以使用Zookeeper持久順序節(jié)點(diǎn)的特性自動對snowflake節(jié)點(diǎn)配置wokerID甥绿。Leaf-snowflake是按照下面幾個步驟啟動的：

1.啟動Leaf-snowflake服務(wù)，連接Zookeeper则披，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點(diǎn)）共缕。

2.如果有注冊過直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類型ID號），啟動服務(wù)士复。

3.如果沒有注冊過图谷，就在該父節(jié)點(diǎn)下面創(chuàng)建一個持久順序節(jié)點(diǎn)，創(chuàng)建成功后取回順序號當(dāng)做自己的workerID號阱洪，啟動服務(wù)便贵。

除了每次會去ZK拿數(shù)據(jù)以外，也會在本機(jī)文件系統(tǒng)上緩存一個workerID文件冗荸。當(dāng)ZooKeeper出現(xiàn)問題承璃，恰好機(jī)器出現(xiàn)問題需要重啟時，能保證服務(wù)能夠正常啟動蚌本。這樣做到了對三方組件的弱依賴盔粹。一定程度上提高了可用性

Leaf-snowflake-zookeeper.png

另外關(guān)于時鐘回退的解決

時鐘回退解決.png

服務(wù)啟動時首先檢查自己是否寫過ZooKeeper leaf_forever節(jié)點(diǎn)：

若寫過，則用自身系統(tǒng)時間與leaf_forever/{self}時間則認(rèn)為機(jī)器時間發(fā)生了大步長回?fù)芟衔耍?wù)啟動失敗并報(bào)警。

若未寫過席楚，證明是新服務(wù)節(jié)點(diǎn)咬崔，直接創(chuàng)建持久節(jié)點(diǎn)leaf_forever/${self}并寫入自身系統(tǒng)時間，接下來綜合對比其余Leaf節(jié)點(diǎn)的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準(zhǔn)確烦秩，具體做法是取leaf_temporary下的所有臨時節(jié)點(diǎn)(所有運(yùn)行中的Leaf-snowflake節(jié)點(diǎn))的服務(wù)IP：Port垮斯，然后通過RPC請求得到所有節(jié)點(diǎn)的系統(tǒng)時間，計(jì)算sum(time)/nodeSize只祠。

若abs( 系統(tǒng)時間-sum(time)/nodeSize ) < 閾值兜蠕，認(rèn)為當(dāng)前系統(tǒng)時間準(zhǔn)確，正常啟動服務(wù)抛寝，同時寫臨時節(jié)點(diǎn)leaf_temporary/${self} 維持租約熊杨。

否則認(rèn)為本機(jī)系統(tǒng)時間發(fā)生大步長偏移曙旭，啟動失敗并報(bào)警。

每隔一段時間(3s)上報(bào)自身系統(tǒng)時間寫入leaf_forever/${self}晶府。