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