snowflake
源碼地址
由于源碼是scala編寫的，翻譯成java
public class IdWorker{
private long workerId;
private long datacenterId;
private long sequence;
public IdWorker(long workerId, long datacenterId, long sequence){
// sanity check for workerId
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
}
System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);
this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}
private long twepoch = 1288834974657L;
private long workerIdBits = 5L;
private long datacenterIdBits = 5L;
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private long sequenceBits = 12L;
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L << sequenceBits);
private long lastTimestamp = -1L;
public long getWorkerId(){
return workerId;
}
public long getDatacenterId(){
return datacenterId;
}
public long getTimestamp(){
return System.currentTimeMillis();
}
public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
System.err.printf("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private long timeGen(){
return System.currentTimeMillis();
}
//---------------測試---------------
public static void main(String[] args) {
IdWorker worker = new IdWorker(1,1,1);
for (int i = 0; i < 30; i++) {
System.out.println(worker.nextId());
}
}
}
snowflake 64bit組成
41位的時間戳能夠用到約69年捆毫。假設(shè)時間從2010年開始的話，可以用到2079年。10bit工作機(jī)器可以支持1024個實例部署，12bit序列號代表每ms最多能夠產(chǎn)生4096個seq,所以snowflake理論上的QPS大約為400w/s县踢。
優(yōu)點：
- 整個ID趨勢遞增
- 不依賴第三方系統(tǒng)，性能好
缺點：強(qiáng)依賴機(jī)器時鐘伟件，如果機(jī)器上時鐘回?fù)芘鹌。瑫?dǎo)致發(fā)號重復(fù)或者服務(wù)會處于不可用狀態(tài)。
美團(tuán)Leaf改進(jìn)的Snowflake
參見上圖整個啟動流程圖斧账，服務(wù)啟動時首先檢查自己是否寫過ZooKeeper leaf_forever節(jié)點：
1谴返、若寫過，則用自身系統(tǒng)時間與leaf_forever/self節(jié)點記錄時間做比較咧织，若小于leaf_forever/self時間則認(rèn)為機(jī)器時間發(fā)生了大步長回?fù)苌じぃ?wù)啟動失敗并報警。
2习绢、若未寫過渠抹，證明是新服務(wù)節(jié)點，直接創(chuàng)建持久節(jié)點leaf_forever/self并寫入自身系統(tǒng)時間，接下來綜合對比其余Leaf節(jié)點的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準(zhǔn)確逼肯，具體做法是取leaf_temporary下的所有臨時節(jié)點(所有運(yùn)行中的Leaf-snowflake節(jié)點)的服務(wù)IP：Port，然后通過RPC請求得到所有節(jié)點的系統(tǒng)時間桃煎，計算sum(time)/nodeSize篮幢。
3、若abs( 系統(tǒng)時間-sum(time)/nodeSize ) < 閾值为迈，認(rèn)為當(dāng)前系統(tǒng)時間準(zhǔn)確三椿，正常啟動服務(wù)，同時寫臨時節(jié)點leaf_temporary/{self}葫辐。
由于強(qiáng)依賴時鐘搜锰，對時間的要求比較敏感，在機(jī)器工作時NTP同步也會造成秒級別的回退耿战，建議可以直接關(guān)閉NTP同步蛋叼。要么在時鐘回?fù)艿臅r候直接不提供服務(wù)直接返回ERROR_CODE，等時鐘追上即可剂陡”蜂蹋或者做一層重試，然后上報報警系統(tǒng)鸭栖，更或者是發(fā)現(xiàn)有時鐘回?fù)苤笞詣诱旧砉?jié)點并報警歌馍，如下：
//發(fā)生了回?fù)埽丝虝r間小于上次發(fā)號時間
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
//時間偏差大小小于5ms晕鹊，則等待兩倍時間
wait(offset << 1);//wait
timestamp = timeGen();
if (timestamp < lastTimestamp) {
//還是小于松却，拋異常并上報
throwClockBackwardsEx(timestamp);
}
} catch (InterruptedException e) {
throw e;
}
} else {
//throw
throwClockBackwardsEx(timestamp);
}
}
//分配ID
同時，Leaf服務(wù)規(guī)模較大溅话，動手配置成本太高晓锻。所以使用Zookeeper持久順序節(jié)點的特性自動對snowflake節(jié)點配置wokerID。Leaf-snowflake是按照下面幾個步驟啟動的：
1飞几、啟動Leaf-snowflake服務(wù)带射，連接Zookeeper，在leaf_forever父節(jié)點下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點）循狰。
2窟社、如果有注冊過直接取回自己的workerID（zk順序節(jié)點生成的int類型ID號），啟動服務(wù)绪钥。
3灿里、如果沒有注冊過，就在該父節(jié)點下面創(chuàng)建一個持久順序節(jié)點程腹，創(chuàng)建成功后取回順序號當(dāng)做自己的workerID號匣吊，啟動服務(wù)。
美團(tuán)Leaf 號段模式
每次從數(shù)據(jù)庫獲取一個segment(step決定大小)號段的值，Segment結(jié)構(gòu)如下色鸳，用完之后再去數(shù)據(jù)庫獲取社痛。為了防止表過大，可以對biz_tag水平分庫分表命雀。
public class Segment {
private AtomicLong value = new AtomicLong(0);
private volatile long max;
private volatile int step;
private SegmentBuffer buffer;
}
表字段
CREATE TABLE `leaf_alloc` (
`biz_tag` varchar(128) NOT NULL DEFAULT '',
`max_id` bigint(20) NOT NULL DEFAULT '1',
`step` int(11) NOT NULL,
`description` varchar(256) DEFAULT NULL,
`update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;
缺點：
1蒜哀、ID號碼不夠隨機(jī)，能夠泄露發(fā)號數(shù)量的信息吏砂，不太安全撵儿。
2、TP999數(shù)據(jù)波動大狐血，當(dāng)號段使用完之后還是會hang在更新數(shù)據(jù)庫的I/O上淀歇，tg999數(shù)據(jù)會出現(xiàn)偶爾的尖刺。
3匈织、DB宕機(jī)會造成整個系統(tǒng)不可用浪默。
針對第二點，leaf做法：當(dāng)號段消費(fèi)到某個點時就異步的把下一個號段加載到內(nèi)存中缀匕。而不需要等到號段用盡的時候才去更新號段浴鸿。這樣做就可以很大程度上的降低系統(tǒng)的TP999指標(biāo)。
采用雙buffer的方式弦追，Leaf服務(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ò)抖動不會影響下個號段的更新
參考：https://segmentfault.com/a/1190000011282426
https://tech.meituan.com/2017/04/21/mt-leaf.html
