最近在proxy的分庫分表蹬敲，需要給表中的主字段產生一個全局唯一ID兵琳，考慮到后期DBA會拿這個ID做索引的仰担，所以產生的這個ID也要盡可能的有序统阿， 總體要求如下
- 不能有單點問題...
- 全局唯一且有序
- 盡量64位可以表示
于是乎調研了一下炊林， 貌似有幾個典型的代表
twitter的snowflake
生成方式：
41位的時間序列（ms, 大約可以用69年）
10位的機器標志（大約可以支持部署1024臺機器, 5bit設置為機器ID姥卢，5bit設置為進程ID）
12位的計數(shù)順序號（這就決定了每個節(jié)點的并發(fā)不超過4096）
最高位作為符號位， 始終為0
優(yōu)點：高性能渣聚， 低延遲独榴，基本能按時間有序， 需要獨立的開發(fā)和部署
很明顯奕枝， 這個缺點在proxy那邊來看并不是缺點棺榔，我就是參考他的思路，把這部分的實現(xiàn)放在proxy的
基于Mysql的解決方案
因為MySQL本身支持auto_increment操作隘道，很自然地掷豺，我們會想到借助這個特性來實現(xiàn)這個功能。
Flicker在解決全局ID生成方案里就采用了MySQL自增長ID的機制（auto_increment + replace into + MyISAM）薄声。一個生成64位ID
方案具體就是這樣的：
- 先創(chuàng)建單獨的數(shù)據(jù)庫当船， 然后創(chuàng)建一個表：
CREATE TABLE Tickets64 (
id bigint(20) unsigned NOT NULL auto_increment,
stub char(1) NOT NULL default '',
PRIMARY KEY (id),
UNIQUE KEY stub (stub)
) ENGINE=MyISAM
- 然后插入一條記錄，并插入一條記錄默辨， 執(zhí)行執(zhí)行
SELECT * from Tickets64查詢的結果就是這樣的：
+-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |
+-------------------+------+
在我們的應用端需要做下面這兩個操作德频，在一個事務會話里提交
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
這樣我們就能拿到不斷增長且不重復的ID了。
到上面為止缩幸，我們只是在單臺數(shù)據(jù)庫上生成ID壹置，從高可用角度考慮竞思，接下來就要解決單點故障問題：Flicker啟用了兩臺數(shù)據(jù)庫服務器來生成ID，通過區(qū)分auto_increment的起始值和步長來生成奇偶數(shù)的ID
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2
最后钞护，在客戶端只需要通過輪詢方式取ID就可以了盖喷。
優(yōu)點：充分借助數(shù)據(jù)庫的自增ID機制，提供高可靠性难咕，生成的ID有序课梳。
缺點：占用兩個獨立的MySQL實例，依賴外部服務余佃，難運維
UUID
UUID生成的是length=32的16進制格式的字符串暮刃，如果回退為byte數(shù)組共16個byte元素，即UUID是一個128bit長的數(shù)字爆土，
一般用16進制表示椭懊。
算法的核心思想是結合機器的網(wǎng)卡、當?shù)貢r間步势、一個隨即數(shù)來生成UUID氧猬。
從理論上講，如果一臺機器每秒產生10000000個GUID坏瘩，則可以保證（概率意義上）3240年不重復
優(yōu)點：
- 本地生成ID盅抚，不需要進行遠程調用，時延低
- 擴展性好桑腮，基本可以認為沒有性能上限
缺點：
- 無法保證趨勢遞增
- uuid過長，往往用字符串表示蛉幸，作為主鍵建立索引查詢效率低破讨，常見優(yōu)化方案為“轉化為兩個uint64整數(shù)存儲”或者“折半存儲”（折半后不能保證唯一性）
UUID這兩個致命缺點導致我們首先拋棄UUID
基于REDIS的分布式ID生成器
首先，要知道redis的EVAL奕纫，EVALSHA命令：
原理：
利用redis的lua腳本執(zhí)行功能提陶，在每個節(jié)點上通過lua腳本生成唯一ID。
生成的ID是64位的：
使用41 bit來存放時間匹层，精確到毫秒隙笆，可以使用41年。
使用12 bit來存放邏輯分片ID升筏，最大分片ID是4095
使用10 bit來存放自增長ID撑柔，意味著每個節(jié)點，每毫秒最多可以生成1024個ID
比如GTM時間 Fri Mar 13 10:00:00 CST 2015 您访，它的距1970年的毫秒數(shù)是 1426212000000铅忿，假定分片ID是53，自增長序列是4灵汪，則生成的ID是：
5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41
redis提供了TIME命令檀训，可以取得redis服務器上的秒數(shù)和微秒數(shù)柑潦。因些lua腳本返回的是一個四元組:
(second, microSecond, partition, seq)
客戶端可以自己處理
((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq
MongoDB文檔（Document）全局唯一ID
為了考慮分布式，“_id”要求不同的機器都能用全局唯一的同種方法方便的生成它峻凫。因此不能使用自增主鍵（需要多臺服務器進行同步渗鬼，既費時又費力），
因此選用了生成ObjectId對象的方法荧琼。
ObjectId使用12字節(jié)的存儲空間譬胎，其生成方式如下：
|0|1|2|3|4|5|6|7|8|9|10|11|
|時間戳 |機器ID|PID|計數(shù)器|
前四個字節(jié)時間戳是從標準紀元開始的時間戳，單位為秒铭腕，有如下特性：
- 時間戳與后邊5個字節(jié)一塊银择，保證秒級別的唯一性；
- 保證插入順序大致按時間排序累舷；
- 隱含了文檔創(chuàng)建時間浩考；
- 時間戳的實際值并不重要，不需要對服務器之間的時間進行同步（因為加上機器ID和進程ID已保證此值唯一被盈，唯一性是ObjectId的最終訴求）析孽。
機器ID是服務器主機標識，通常是機器主機名的散列值只怎。
同一臺機器上可以運行多個mongod實例袜瞬，因此也需要加入進程標識符PID。
前9個字節(jié)保證了同一秒鐘不同機器不同進程產生的ObjectId的唯一性身堡。后三個字節(jié)是一個自動增加的計數(shù)器（一個mongod進程需要一個全局的計數(shù)器）邓尤，保證同一秒的ObjectId是唯一的。同一秒鐘最多允許每個進程擁有（256^3 = 16777216）個不同的ObjectId贴谎。
總結一下：時間戳保證秒級唯一汞扎，機器ID保證設計時考慮分布式，避免時鐘同步擅这，PID保證同一臺服務器運行多個mongod實例時的唯一性澈魄，最后的計數(shù)器保證同一秒內的唯一性（選用幾個字節(jié)既要考慮存儲的經濟性，也要考慮并發(fā)性能的上限）仲翎。
"_id"既可以在服務器端生成也可以在客戶端生成痹扇，在客戶端生成可以降低服務器端的壓力。
