Entrance
- 數(shù)據(jù)在分片時(shí)站辉，典型的是分庫(kù)分表呢撞，就有一個(gè)全局ID生成的問題。
- 單純的生成全局ID并不是什么難題饰剥，但是生成的ID通常要滿足分片的一些要求
要求
- 不能有單點(diǎn)故障殊霞。
- 以時(shí)間為序，或者ID里包含時(shí)間汰蓉。這樣一是可以少一個(gè)索引绷蹲，二是冷熱數(shù)據(jù)容易分離。
- 可以控制ShardingId。比如某一個(gè)用戶的文章要放在同一個(gè)分片內(nèi)祝钢，這樣查詢效率高比规，修改也容易。
- 不要太長(zhǎng)拦英，最好64bit蜒什。使用long比較好操作，如果是96bit疤估，那就要各種移位相當(dāng)?shù)牟环奖阍殖＃€有可能有些組件不能支持這么大的ID。
Entrance
- twitter在把存儲(chǔ)系統(tǒng)從MySQL遷移到Cassandra的過程中由于Cassandra沒有順序ID生成機(jī)制做裙，于是自己開發(fā)了一套全局唯一ID生成服務(wù)：Snowflake岗憋。
- 41位的時(shí)間序列（精確到毫秒，41位的長(zhǎng)度可以使用69年）
- 10位的機(jī)器標(biāo)識(shí)（10位的長(zhǎng)度最多支持部署1024個(gè)節(jié)點(diǎn)）
- 12位的計(jì)數(shù)順序號(hào)（12位的計(jì)數(shù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號(hào)） 最高位是符號(hào)位锚贱，始終為0。
- 優(yōu)點(diǎn)：高性能关串，低延遲拧廊；獨(dú)立的應(yīng)用；按時(shí)間有序晋修。 缺點(diǎn)：需要獨(dú)立的開發(fā)和部署吧碾。
代碼示例
public class IdWorker {
private final long workerId;
private final static long twepoch = 1288834974657L;
private long sequence = 0L;
private final static long workerIdBits = 4L;
public final static long maxWorkerId = -1L ^ -1L << workerIdBits;
private final static long sequenceBits = 10L;
private final static long workerIdShift = sequenceBits;
private final static long timestampLeftShift = sequenceBits + workerIdBits;
public final static long sequenceMask = -1L ^ -1L << sequenceBits;
private long lastTimestamp = -1L;
public IdWorker(final long workerId) {
super();
if (workerId > this.maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(
String.format("worker Id can't be greater than %d or less than 0", this.maxWorkerId));
}
this.workerId = workerId;
}
public synchronized long nextId() {
long timestamp = this.timeGen();
if (this.lastTimestamp == timestamp) {
this.sequence = (this.sequence + 1) & this.sequenceMask;
if (this.sequence == 0) {
System.out.println("###########" + sequenceMask);
timestamp = this.tilNextMillis(this.lastTimestamp);
}
} else {
this.sequence = 0;
}
if (timestamp < this.lastTimestamp) {
try {
throw new Exception(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
this.lastTimestamp - timestamp));
} catch (Exception e) {
e.printStackTrace();
}
}
this.lastTimestamp = timestamp;
long nextId = ((timestamp - twepoch << timestampLeftShift)) | (this.workerId << this.workerIdShift)
| (this.sequence);
System.out.println("timestamp:" + timestamp + ",timestampLeftShift:" + timestampLeftShift + ",nextId:" + nextId
+ ",workerId:" + workerId + ",sequence:" + sequence);
return nextId;
}
private long tilNextMillis(final long lastTimestamp) {
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
IdWorker worker2 = new IdWorker(2);
System.out.println(worker2.nextId());
}
}
來自Flicker的解決方案
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
- 因?yàn)镸ySQL本身支持auto_increment操作，很自然地墓卦，我們會(huì)想到借助這個(gè)特性來實(shí)現(xiàn)這個(gè)功能倦春。
- Flicker在解決全局ID生成方案里就采用了MySQL自增長(zhǎng)ID的機(jī)制（auto_increment + replace into + MyISAM）。一個(gè)生成64位ID方案具體就是這樣的：
先創(chuàng)建單獨(dú)的數(shù)據(jù)庫(kù)(eg:ticket)落剪，然后創(chuàng)建了Tickets64這個(gè)表
cluster
+-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |
+-------------------+------+
- 當(dāng)我們插入記錄后睁本，執(zhí)行SELECT * from Tickets64，查詢結(jié)果就是如上的
cluster
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
- 在我們的應(yīng)用端需要做下面這兩個(gè)操作忠怖，在一個(gè)事務(wù)會(huì)話里提交,這樣我們就能拿到不斷增長(zhǎng)且不重復(fù)的ID了
cluster
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2
- 到上面為止呢堰，我們只是在單臺(tái)數(shù)據(jù)庫(kù)上生成ID，從高可用角度考慮凡泣，接下來就要解決單點(diǎn)故障問題
- Flicker啟用了兩臺(tái)數(shù)據(jù)庫(kù)服務(wù)器來生成ID枉疼，通過區(qū)分auto_increment的起始值和步長(zhǎng)來生成奇偶數(shù)的ID
- 最后，在客戶端只需要通過輪詢方式取ID就可以了
- 優(yōu)點(diǎn)：充分借助數(shù)據(jù)庫(kù)的自增ID機(jī)制鞋拟，提供高可靠性骂维，生成的ID有序
- 缺點(diǎn)：占用兩個(gè)獨(dú)立的MySQL實(shí)例，有些浪費(fèi)資源贺纲，成本較高
UUID
- UUID生成的是length=32的16進(jìn)制格式的字符串航闺，如果回退為byte數(shù)組共16個(gè)byte元素，即UUID是一個(gè)128bit長(zhǎng)的數(shù)字哮笆，
- 一般用16進(jìn)制表示来颤。
- 算法的核心思想是結(jié)合機(jī)器的網(wǎng)卡汰扭、當(dāng)?shù)貢r(shí)間、一個(gè)隨即數(shù)來生成UUID
- 從理論上講福铅，如果一臺(tái)機(jī)器每秒產(chǎn)生10000000個(gè)GUID萝毛，則可以保證（概率意義上）3240年不重復(fù)
優(yōu)點(diǎn)
- 本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用滑黔，時(shí)延低
- 擴(kuò)展性好笆包，基本可以認(rèn)為沒有性能上限
缺點(diǎn)
- 無法保證趨勢(shì)遞增
- uuid過長(zhǎng)，往往用字符串表示略荡，作為主鍵建立索引查詢效率低庵佣，常見優(yōu)化方案為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲(chǔ)”或者“折半存儲(chǔ)”（折半后不能保證唯一性）
基于redis的分布式ID生成器
entrance
redis的EVAL，EVALSHA命令的原理是利用redis的lua腳本執(zhí)行功能汛兜，在每個(gè)節(jié)點(diǎn)上通過lua腳本生成唯一ID
關(guān)于生成的ID##
- 使用41 bit來存放時(shí)間巴粪，精確到毫秒，可以使用41年粥谬。
- 使用12 bit來存放邏輯分片ID肛根，最大分片ID是4095
- 使用10 bit來存放自增長(zhǎng)ID，意味著每個(gè)節(jié)點(diǎn)漏策，每毫秒最多可以生成1024個(gè)ID
舉例
- 比如GTM時(shí)間 Fri Mar 13 10:00:00 CST 2015 派哲，它的距1970年的毫秒數(shù)是 1426212000000，假定分片ID是53掺喻，自增長(zhǎng)序列是4芭届，則生成的ID是：
- 5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41
cluster
- redis提供了TIME命令，可以取得redis服務(wù)器上的秒數(shù)和微秒數(shù)感耙。因些lua腳本返回的是一個(gè)四元組褂乍。second, microSecond, partition, seq，客戶端要自己處理抑月，生成最終I树叽。
- ((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;
MongoDB文檔（Document）全局唯一ID
- 為了考慮分布式，“_id”要求不同的機(jī)器都能用全局唯一的同種方法方便的生成它谦絮。因此不能使用自增主鍵（需要多臺(tái)服務(wù)器進(jìn)行同步题诵，既費(fèi)時(shí)又費(fèi)力），因此選用了生成ObjectId對(duì)象的方法
- ObjectId使用12字節(jié)的存儲(chǔ)空間
生成方式
|0|1|2|3|4|5|6 |7|8|9|10|11|
|時(shí)間戳 |機(jī)器ID|PID|計(jì)數(shù)器 |
- 前四個(gè)字節(jié)時(shí)間戳是從標(biāo)準(zhǔn)紀(jì)元開始的時(shí)間戳层皱，單位為秒性锭，有如下特性：
- 1.時(shí)間戳與后邊5個(gè)字節(jié)一塊，保證秒級(jí)別的唯一性
- 2.保證插入順序大致按時(shí)間排序
- 3.隱含了文檔創(chuàng)建時(shí)間
- 4.時(shí)間戳的實(shí)際值并不重要叫胖，不需要對(duì)服務(wù)器之間的時(shí)間進(jìn)行同步（因?yàn)榧由蠙C(jī)器ID和進(jìn)程ID已保證此值唯一草冈，唯一性是ObjectId的最終訴求）
cluster
- 機(jī)器ID是服務(wù)器主機(jī)標(biāo)識(shí)，通常是機(jī)器主機(jī)名的散列值
- 同一臺(tái)機(jī)器上可以運(yùn)行多個(gè)mongod實(shí)例，因此也需要加入進(jìn)程標(biāo)識(shí)符PID
- 前9個(gè)字節(jié)保證了同一秒鐘不同機(jī)器不同進(jìn)程產(chǎn)生的ObjectId的唯一性怎棱。后三個(gè)字節(jié)是一個(gè)自動(dòng)增加的計(jì)數(shù)器（一個(gè)mongod進(jìn)程需要一個(gè)全局的計(jì)數(shù)器）哩俭，保證同一秒的ObjectId是唯一的。同一秒鐘最多允許每個(gè)進(jìn)程擁有（256^3 = 16777216）個(gè)不同的ObjectId
總結(jié)
- 時(shí)間戳保證秒級(jí)唯一拳恋，機(jī)器ID保證設(shè)計(jì)時(shí)考慮分布式凡资，避免時(shí)鐘同步，PID保證同一臺(tái)服務(wù)器運(yùn)行多個(gè)mongod實(shí)例時(shí)的唯一性谬运，最后的計(jì)數(shù)器保證同一秒內(nèi)的唯一性（選用幾個(gè)字節(jié)既要考慮存儲(chǔ)的經(jīng)濟(jì)性隙赁，也要考慮并發(fā)性能的上限）。
- "_id"既可以在服務(wù)器端生成也可以在客戶端生成梆暖，在客戶端生成可以降低服務(wù)器端的壓力伞访。
