分布式id生成策略，我和面試官扯了一個半小時
面試官：小伙子，你還記得我嗎？我是上次面試你的那個面試官。
我心想：我去，怎么會不記得，我又不是青年癡呆，上次害我畫了那么多圖，還使勁敲了一個多鐘的電腦，滿腦子都是你的陰影。
我：記得記得，您好，很高興能通過二面，能夠繼續(xù)和您交流技術(shù)問題。
我違背良心說這話真的好嗎，姑且就那么一次吧，面?zhèn)€試都那么難？
面試官又快速的掃了一下的簡歷，可能上次看過一次，都快過了一個多星期了，估計他都都忘了我的簡歷了吧。
面試官：我看你簡歷上面寫著深入了解分布式，并且也做過分布式項目，挺好的，那你知道分布式項目中生成分布式ID的方法有哪些嗎？
我：這個我知道，生成分布式Id的方法主要有以下幾種：
-
數(shù)據(jù)庫自增ID。 -
數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長。 -
批量申請自增ID。 -
UUID生成。 -
Redis的方式。 -
雪花算法。 -
百度UidGenerator算法 -
美團Leaf算法
面試官：哦，不錯能說出那么多，你能說一說對于上面的每一種方式的分析和理解嗎？
我心想：我去，這下可糗大了，那么多，我只是大概知道主要的，怎么可能每一種都去了解和深入，一下子說了那么多不是給自己挖坑嗎？
哎，沒辦法出來混，總是要還的，只能說自己知道的吧？不知道的大概粗糙的略過。
我：嗯嗯，好的。數(shù)據(jù)庫的自增，很容易理解，開發(fā)過的人員都知道，在創(chuàng)建表的時候，指定主鍵auto_increment（自增）便可以實現(xiàn)。
我：但是使用數(shù)據(jù)庫的自增ID，雖然簡單，會帶來ID重復(fù)的問題，并且單機版的ID自增，并且每次生成一個ID都會訪問數(shù)據(jù)庫一次，DB的壓力也很大，并沒有什么并發(fā)性能可言。
面試官：恩額。
我看看面試官正聽著有味，時不時摸摸他稀少的發(fā)量額頭，深邃的目光透露出他的沉穩(wěn)，這可能就是一個成熟架構(gòu)師的魅力吧，讓多少碼渣苦讀《Java編程思想》《Java核心技術(shù)》《Effectice java》《Java并發(fā)編程實戰(zhàn)》《代碼整潔之道》《重構(gòu): 改善既有代碼的設(shè)計》......，都無法達(dá)到的境界，我乘熱打鐵，接著下面的回答。
我：針對上面的數(shù)據(jù)庫自增ID出現(xiàn)的問題：ID重復(fù)、性能不好。就出現(xiàn)了集群版的生成分布式ID方案。「數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長」和「批量申請自增ID」。
我：「數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長」是指在DB集群的環(huán)境下，將數(shù)據(jù)庫進行水平劃分，然后每個數(shù)據(jù)庫設(shè)置「不同的初始值」和「相同的步長」，這樣就能避免ID重復(fù)的情況。
面試官：小伙子，不好意思打斷一下，你可以畫個圖嗎，這個我有點沒明白你講的意思？
我能有什么辦法啊，完全沒辦法，只能從褲兜里拿出筆和紙，快速的畫了一張圖。
我：我這里假設(shè)有三個數(shù)據(jù)庫，為每一個數(shù)據(jù)庫設(shè)置初始值，設(shè)置初始值可以通過下面的sql進行設(shè)置：
set @@auto_increment_offset = 1; // 設(shè)置初始值
set @@auto_increment_increment = 2; // 設(shè)置步長
我：三個數(shù)據(jù)的初始值分別設(shè)置為1、2、3，一般步長設(shè)置為數(shù)據(jù)庫的數(shù)據(jù)，這里數(shù)據(jù)庫數(shù)量為3，所以步長也設(shè)置為3。
面試官：若是面對再次擴容的情況呢？
我：恩額，擴容的情況是這種方法的一個缺點，上面我說的步長一般設(shè)置為數(shù)據(jù)庫的數(shù)量，這是在確保后期不會擴容的情況下，若是確定后期會有擴容情況，在前期設(shè)計的的時候可以將步長設(shè)置長一點，「預(yù)留一些初始值給后續(xù)擴容使用」。
我：總之，這種方案還是優(yōu)缺點的，但是也有自己的優(yōu)點，缺點就是：「后期可能會面對無ID初始值可分的窘境，數(shù)據(jù)庫總歸是數(shù)據(jù)庫，抗高并發(fā)也是有限的」。
我：它的優(yōu)點就是算是解決了「DB單點的問題」。
面試官：恩額。
我：「批量申請自增ID」的解決方案可以解決無ID可分的問題，它的原理就是一次性給對應(yīng)的數(shù)據(jù)庫上分配一批的id值進行消費，使用完了，再回來申請。
這次我很自覺的從褲兜里拿出筆和紙，畫出了下面的這張圖，歷史總是那么驚人的相似。
我：在設(shè)計的初始階段可以設(shè)計一個有初始值字段，并有步長字段的表，當(dāng)每次要申請批量ID的時候，就可以去該表中申請，每次申請后「初始值=上一次的初始值+步長」。
我：這樣就能保持初始值是每一個申請的ID的最大值，避免了ID的重復(fù)，并且每次都會有ID使用，一次就會生成一批的id來使用，這樣訪問數(shù)據(jù)庫的次數(shù)大大減少。
我：但是這一種方案依舊有自己的缺點，依然不能抗真正意義上的高并發(fā)。
我：第四種方式是使用「UUID生成」的方式生成分布式ID，UUID的核心思想是使用「機器的網(wǎng)卡、當(dāng)?shù)貢r間、一個隨機數(shù)」來生成UUID。
我：使用UUID的方式只需要調(diào)用UUID.randomUUID().toString()就可以生成，這種方式方便簡單，本地生成，不會消耗網(wǎng)絡(luò)。
我：當(dāng)時簡單的東西，出現(xiàn)的問題就會越多，不利于存儲，16字節(jié)128位，通常是以36位長度的字符串表示，很多的場景都不適合。
我：并且UUID生成的無序的字符串，查詢效率低下，沒有實際的業(yè)務(wù)含義，不具備自增特性，所以都不會使用UUID作為分布式ID來使用。
面試官：恩額，那你知道生成UUID的方式有幾種嗎？不知道沒關(guān)系，這個只是作為一個擴展。
我：這個我只知道可以通過「當(dāng)前的時間戳及機器mac地址」來生成，可以確保生成的UUID全球唯一，其它的沒有了解過。
面試官：嗯嗯，沒關(guān)系的。
我：為了解決上面純關(guān)系型數(shù)據(jù)庫生成分布式ID無法抗高并發(fā)的問題，可以使用Redis的方式來生成分布式ID。
我：Redis本身有incr和increby 這樣自增的命令，保證原子性，生成的ID也是有序的。
我：Redis基于內(nèi)存操作，性能高效，不依賴于數(shù)據(jù)庫，數(shù)據(jù)天然有序，利于分頁和排序。
我：但是這個方案也會有自己的缺點，因為增加了中間件，需要自己編碼實現(xiàn)工作量增大，增加復(fù)雜度。
我：使用Redis的方式還要考慮持久化，Redis的持久化有兩種「RDB和AOF」，「RDB是以快照的形式進行持久化，會丟失上一次快照至此時間的數(shù)據(jù)」。
我：「AOF可以設(shè)置一秒持久化一次，丟失的數(shù)據(jù)是秒內(nèi)的」，也會存在可能上一次自增后的秒內(nèi)的ID沒有持久化的問題。
我：但是這種方法相對于上面的關(guān)系型數(shù)據(jù)庫生成分布式ID的方法而言，已經(jīng)優(yōu)越了許多。
我：若是數(shù)據(jù)量比較大的話，重啟Redis的時間也會比較長，可以采用Redis的集群方式。
面試官：你能手寫一下Redis的生成分布式ID的工具類代碼嗎？
我奔潰了，我最怕手寫了，因為工具類這種東西，基本就是項目開始的時候?qū)懸淮?，后面對后市重?fù)使用，記不住，還要手寫，這也太難為我怕虎了吧。
我：手寫應(yīng)該不行，因為有些API記不住，工具類基本就是項目開始的時候?qū)懸恍罄m(xù)都沒有去看過了，沒有專門去記它。
我：我可以使用您的電腦嗎？使用電腦應(yīng)該可以敲出這些工具類。
面試官：可以的，這邊電腦給你，你在這個測試項目下吧。
我：好的，謝謝。
時間流逝中........
大概敲了幾分鐘，廢了九牛二虎之力，終于敲出來了，有好多API記不住，只能慢慢的找了，寫了主要兩種方式來生成分布式ID。
第一種是使用RedisAtomicLong 原子類使用CAS操作來生成ID。
@Service
public class RedisSequenceFactory {
@Autowired
RedisTemplate<String, String> redisTemplate;
public void setSeq(String key, int value, Date expireTime) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.set(value);
counter.expireAt(expireTime);
}
public void setSeq(String key, int value, long timeout, TimeUnit unit) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.set(value);
counter.expire(timeout, unit);
}
public long generate(String key) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
return counter.incrementAndGet();
}
public long incr(String key, Date expireTime) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.expireAt(expireTime);
return counter.incrementAndGet();
}
public long incr(String key, int increment) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
return counter.addAndGet(increment);
}
public long incr(String key, int increment, Date expireTime) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.expireAt(expireTime);
return counter.addAndGet(increment);
}
}
第二種是使用redisTemplate.opsForHash()和結(jié)合UUID的方式來生成生成ID。
public Long getSeq(String key,String hashKey,Long delta) throws BusinessException{
try {
if (null == delta) {
delta=1L;
}
return redisTemplate.opsForHash().increment(key, hashKey, delta);
} catch (Exception e) { // 若是redis宕機就采用uuid的方式
int first = new Random(10).nextInt(8) + 1;
int randNo=UUID.randomUUID().toString().hashCode();
if (randNo < 0) {
randNo=-randNo;
}
return Long.valueOf(first + String.format("%16d", randNo));
}
}
我把電腦移回給面試官，他很快的掃了一下我的代碼，說了一句。
面試官：小伙子，不寫注釋哦，這個習(xí)慣不好哦。
我：哦哦，謝謝提醒，不好意思，下次我會注意的。
我：第六種方式是「雪花算法」，也是現(xiàn)在市面上比較流行的生成分布式ID的方法。
說著說著，我知道畫圖又是必不可少的了，于是在桌子上又畫了起來，面試官好奇的看看我，知道了我在干啥，又耐心的等了等。
我：他是采用64bit作為id生成類型，并且將64bit劃分為，如下圖的幾段。
我順手把我畫的圖遞給他看了看，接著對著這個圖進行解釋。
我：第一位作為標(biāo)識位，因為Java中l(wèi)ong類型的時代符號的，因為ID位正數(shù)，所以第一位位0。
我：接著的41bit是時間戳，毫秒級位單位，注意這里的時間戳并不是指當(dāng)前時間的時間戳，而是值之間差（「當(dāng)前時間-開始時間」）。
我：這里的開始時間一般是指ID生成器的開始時間，是由我們程序自己指定的。
我：接著后面的10bit：包括5位的「數(shù)據(jù)中心標(biāo)識ID（datacenterId）和5位的機器標(biāo)識ID（workerId）」，可以最多標(biāo)識1024個節(jié)點（1<<10=1024）。
我：最后12位是序列號，12位的計數(shù)順序支持每個節(jié)點每毫秒差生4096序列號（1<<12=4096）。
我：雪花算法使用數(shù)據(jù)中心ID和機器ID作為標(biāo)識，不會產(chǎn)生ID的重復(fù)，并且是在本地生成，不會消耗網(wǎng)絡(luò)，效率高，有數(shù)據(jù)顯示，每秒能生成26萬個ID。
我：但是雪花算法也是有自己的缺點，因為雪花算法的計算依賴于時間，若是系統(tǒng)時間回?fù)?，就會產(chǎn)生重復(fù)ID的情況。
面試官：那對于時間回?fù)墚a(chǎn)生重復(fù)ID的情況，你有什么比較好的解決方案嗎？
我：在雪花算法的實現(xiàn)中，若是其前置的時間等于當(dāng)前的時間，就拋出異常，也可以關(guān)閉掉時間回?fù)堋?/p>
我：對于回?fù)軙r間比較短的，可以等待回?fù)軙r間過后再生成ID。
面試官：你可以幫我敲一個雪花算法嗎？我這鍵盤給你。
我：。。。
我：好的。
時間流逝中......
過了幾分鐘時間，也總算是把雪花算法給敲出來了，真正要老命，面?zhèn)€試怎么就那么難呢？
/**
* 雪花算法
* @author：黎杜
*/
public class SnowflakeIdWorker {
/** 開始時間截 */
private final long twepoch = 1530051700000L;
/** 機器id的位數(shù) */
private final long workerIdBits = 5L;
/** 數(shù)據(jù)標(biāo)識id的位數(shù) */
private final long datacenterIdBits = 5L;
/** 最大的機器id，結(jié)果是31 */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 最大的數(shù)據(jù)標(biāo)識id，結(jié)果是31 */
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
/** 序列的位數(shù) */
private final long sequenceBits = 12L;
/** 機器ID向左移12位 */
private final long workerIdShift = sequenceBits;
/** 數(shù)據(jù)標(biāo)識id向左移17位 */
private final long datacenterIdShift = sequenceBits + workerIdBits;
/** 時間截向左移22位*/
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/** 生成序列的掩碼 */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** 工作機器ID(0~31) */
private long workerId;
/** 數(shù)據(jù)中心ID(0~31) */
private long datacenterId;
/** 毫秒內(nèi)序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的時間截 */
private long lastTimestamp = -1L;
/**
* 構(gòu)造函數(shù)
* @param workerId 工作ID (0~31)
* @param datacenterId 數(shù)據(jù)中心ID (0~31)
*/
public SnowflakeIdWorker(long workerId, long datacenterId) {
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));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
/**
* 獲得下一個ID (該方法是線程安全的)
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = getCurrentTime();
//如果當(dāng)前時間小于上一次生成的時間戳，說明系統(tǒng)時鐘回退過就拋出異常
if (timestamp < lastTimestamp) {
throw new BusinessionException("回?fù)艿臅r間為："+lastTimestamp - timestamp);
}
//如果是同一時間生成的，則進行毫秒內(nèi)序列
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//毫秒內(nèi)序列溢出
if (sequence == 0) {
//獲得新的時間戳
timestamp = tilNextMillis(lastTimestamp);
}
} else { //時間戳改變，毫秒內(nèi)序列重置
sequence = 0L;
}
//上次生成ID的時間截
lastTimestamp = timestamp;
//移位并通過或運算拼到一起組成64位的ID
return ((timestamp - twepoch) << timestampLeftShift) // 計算時間戳
| (datacenterId << datacenterIdShift) // 計算數(shù)據(jù)中心
| (workerId << workerIdShift) // 計算機器ID
| sequence; // 序列號
}
/**
*獲得新的時間戳
* @param lastTimestamp 上次生成ID的時間截
* @return 當(dāng)前時間戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = getCurrentTime();
// 若是當(dāng)前時間等于上一次的1時間就一直阻塞，知道獲取到最新的時間（回?fù)芎蟮臅r間）
while (timestamp <= lastTimestamp) {
timestamp = getCurrentTime();
}
return timestamp;
}
/**
* 獲取當(dāng)前時間
* @return 當(dāng)前時間(毫秒)
*/
protected long getCurrentTime() {
return System.currentTimeMillis();
}
為了給面試官留下個好印象，這下也寫上了注解，免得他又說我，敲完我又把電腦移回給他，他快速的看了看，點了點頭，嘴角露出一絲絲的笑意。
面試官：嗯，你的底子還算比價扎實，面試之前早有準(zhǔn)備吧，看了很多的面試資料。
我心想怎么是面試之前準(zhǔn)備呢？我是一直在準(zhǔn)備，從工作到現(xiàn)在都在總結(jié)自己的知識點，形成自己的知識體系，為了迎合他，也只能說是。
我：嗯嗯，是的，準(zhǔn)備了很久，算是比較充分。
面試官：嗯，最后的兩種算法，你還深入了解嗎？
我：最后兩種確實沒有深入了解，之前有看網(wǎng)上的資料說美團Leaf算法需要依賴于數(shù)據(jù)庫，ZK，并且也能保證去全局ID的唯一性，單項遞增。
我：而百度UidGenerator算法是基于雪花算法進行實現(xiàn)的，也是需要借助于數(shù)據(jù)庫，與雪花算法不同的是，「UidGenerator支持自定義時間戳、主句中心ID和機器ID、序列號的位數(shù)」。
面試官：嗯嗯，好的，小伙子今天的面試就到這里，下次我們再見吧。
得意洋洋中......
【文章參考】
特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
