面試官心理分析
其實(shí)這是分庫分表之后你必然要面對(duì)的一個(gè)問題闭树，就是 id 咋生成？因?yàn)橐欠殖啥鄠€(gè)表之后荒澡，每個(gè)表都是從 1 開始累加报辱，那肯定不對(duì)啊，需要一個(gè)全局唯一的 id 來支持单山。所以這都是你實(shí)際生產(chǎn)環(huán)境中必須考慮的問題碍现。
面試題剖析
基于數(shù)據(jù)庫的實(shí)現(xiàn)方案
數(shù)據(jù)庫自增 id
這個(gè)就是說你的系統(tǒng)里每次得到一個(gè) id，都是往一個(gè)庫的一個(gè)表里插入一條沒什么業(yè)務(wù)含義的數(shù)據(jù)米奸，然后獲取一個(gè)數(shù)據(jù)庫自增的一個(gè) id昼接。拿到這個(gè) id 之后再往對(duì)應(yīng)的分庫分表里去寫入。
這個(gè)方案的好處就是方便簡單悴晰，誰都會(huì)用辩棒；缺點(diǎn)就是單庫生成自增 id，要是高并發(fā)的話，就會(huì)有瓶頸的一睁；
如果你硬是要改進(jìn)一下钻弄，那么就專門開一個(gè)服務(wù)出來，這個(gè)服務(wù)每次就拿到當(dāng)前 id 最大值者吁，然后自己遞增幾個(gè) id窘俺，一次性返回一批 id，然后再把當(dāng)前最大 id 值修改成遞增幾個(gè) id 之后的一個(gè)值复凳；但是無論如何都是基于單個(gè)數(shù)據(jù)庫瘤泪。
適合的場景：你分庫分表就倆原因，要不就是單庫并發(fā)太高育八，要不就是單庫數(shù)據(jù)量太大对途；除非是你并發(fā)不高，但是數(shù)據(jù)量太大導(dǎo)致的分庫分表擴(kuò)容髓棋，你可以用這個(gè)方案实檀，因?yàn)榭赡苊棵胱罡卟l(fā)最多就幾百，那么就走單獨(dú)的一個(gè)庫和表生成自增主鍵即可按声。
設(shè)置數(shù)據(jù)庫 sequence 或者表自增字段步長
適合的場景：在用戶防止產(chǎn)生的 ID 重復(fù)時(shí)，這種方案實(shí)現(xiàn)起來比較簡單柒凉，也能達(dá)到性能目標(biāo)族阅。但是服務(wù)節(jié)點(diǎn)固定，步長也固定扛拨，將來如果還要增加服務(wù)節(jié)點(diǎn)耘分，就不好搞了。
UUID
好處就是本地生成绑警，不要基于數(shù)據(jù)庫來了求泰；不好之處就是，UUID 太長了计盒、占用空間大渴频，作為主鍵性能太差了；更重要的是北启，UUID 不具有有序性卜朗，會(huì)導(dǎo)致 B+ 樹索引在寫的時(shí)候有過多的隨機(jī)寫操作（連續(xù)的 ID 可以產(chǎn)生部分順序?qū)懀┌蔚冢€有，由于在寫的時(shí)候不能產(chǎn)生有順序的 append 操作场钉，而需要進(jìn)行 insert 操作蚊俺，將會(huì)讀取整個(gè) B+ 樹節(jié)點(diǎn)到內(nèi)存，在插入這條記錄后會(huì)將整個(gè)節(jié)點(diǎn)寫回磁盤逛万，這種操作在記錄占用空間比較大的情況下泳猬，性能下降明顯。
適合的場景：如果你是要隨機(jī)生成個(gè)什么文件名宇植、編號(hào)之類的得封，你可以用 UUID，但是作為主鍵是不能用 UUID的指郁。
UUID.randomUUID().toString().replace(“-”, “”) -> sfsdf23423rr234sfdaf
獲取系統(tǒng)當(dāng)前時(shí)間
這個(gè)就是獲取當(dāng)前時(shí)間即可忙上，但是問題是，并發(fā)很高的時(shí)候闲坎，比如一秒并發(fā)幾千疫粥，會(huì)有重復(fù)的情況，這個(gè)是肯定不合適的箫柳∈中危基本就不用考慮了啥供。
適合的場景：一般如果用這個(gè)方案悯恍，是將當(dāng)前時(shí)間跟很多其他的業(yè)務(wù)字段拼接起來，作為一個(gè) id伙狐，如果業(yè)務(wù)上你覺得可以接受涮毫，那么也是可以的。你可以將別的業(yè)務(wù)字段值跟當(dāng)前時(shí)間拼接起來贷屎，組成一個(gè)全局唯一的編號(hào)罢防。
snowflake 算法
snowflake 算法是 twitter 開源的分布式 id 生成算法，采用 Scala 語言實(shí)現(xiàn)唉侄，是把一個(gè) 64 位的 long型的 id咒吐，1 個(gè) bit 是不用的，用其中的 41 bit 作為毫秒數(shù)属划，用 10 bit 作為工作機(jī)器 id恬叹，12 bit 作為序列號(hào)。
1 bit：不用同眯，為啥呢绽昼？因?yàn)槎M(jìn)制里第一個(gè) bit 為如果是 1，那么都是負(fù)數(shù)须蜗，但是我們生成的 id都是正數(shù)硅确，所以第一個(gè) bit 統(tǒng)一都是 0目溉。
41 bit：表示的是時(shí)間戳，單位是毫秒菱农。41 bit 可以表示的數(shù)字多達(dá) 2^41 - 1缭付，也就是可以標(biāo)識(shí) 2^41 - 1 個(gè)毫秒值，換算成年就是表示 69 年的時(shí)間循未。
10 bit：記錄工作機(jī)器 id蛉腌，代表的是這個(gè)服務(wù)最多可以部署在 2^10 臺(tái)機(jī)器上哪，也就是 1024 臺(tái)機(jī)器只厘。但是 10 bit 里 5 個(gè) bit 代表機(jī)房 id烙丛，5 個(gè) bit 代表機(jī)器 id。意思就是最多代表 2^5個(gè)機(jī)房（32 個(gè)機(jī)房）羔味，每個(gè)機(jī)房里可以代表 2^5 個(gè)機(jī)器（32 臺(tái)機(jī)器）河咽。
12 bit：這個(gè)是用來記錄同一個(gè)毫秒內(nèi)產(chǎn)生的不同 id，12 bit 可以代表的最大正整數(shù)是 2^12 -1 = 4096赋元，也就是說可以用這個(gè) 12 bit 代表的數(shù)字來區(qū)分同一個(gè)毫秒內(nèi)的 4096 個(gè)不同的 id忘蟹。
0 | 0001100 10100010 10111110 10001001 01011100 00 | 10001 | 1 1001 | 0000 00000000
public class IdWorker {
private long workerId;
private long datacenterId;
private long sequence;
public IdWorker(long workerId, long datacenterId, long sequence) {
// sanity check for workerId
// 這兒不就檢查了一下，要求就是你傳遞進(jìn)來的機(jī)房 id 和機(jī)器 id 不能超過 32搁凸，不能小于 0
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(
String.format("worker Id can't be greater than %d or less than 0",
maxWorkerId));
91
}
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;
// 這個(gè)是二進(jìn)制運(yùn)算媚值，就是 5 bit 最多只能有 31 個(gè)數(shù)字，也就是說機(jī)器 id 最多只能是 32 以內(nèi)
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 這個(gè)是一個(gè)意思护糖，就是 5 bit 最多只能有 31 個(gè)數(shù)字褥芒，機(jī)房 id 最多只能是 32 以內(nèi)
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
92
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() {
// 這兒就是獲取當(dāng)前時(shí)間戳，單位是毫秒
long timestamp = timeGen();
93
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) {
// 這個(gè)意思是說一個(gè)毫秒內(nèi)最多只能有 4096 個(gè)數(shù)字
// 無論你傳遞多少進(jìn)來嫡良，這個(gè)位運(yùn)算保證始終就是在 4096 這個(gè)范圍內(nèi)锰扶，避免你自己傳遞個(gè)
sequence 超過了 4096 這個(gè)范圍
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
// 這兒記錄一下最近一次生成 id 的時(shí)間戳，單位是毫秒
lastTimestamp = timestamp;
// 這兒就是將時(shí)間戳左移寝受，放到 41 bit 那兒坷牛；
// 將機(jī)房 id 左移放到 5 bit 那兒；
// 將機(jī)器 id 左移放到 5 bit 那兒很澄；將序號(hào)放最后 12 bit京闰；
// 最后拼接起來成一個(gè) 64 bit 的二進(jìn)制數(shù)字，轉(zhuǎn)換成 10 進(jìn)制就是個(gè) long 型
94
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();
}
// ---------------測(cè)試---------------
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());
}
}
}
怎么說呢甩苛，大概這個(gè)意思吧蹂楣，就是說 41 bit 是當(dāng)前毫秒單位的一個(gè)時(shí)間戳，就這意思浪藻；然后 5 bit 是你傳遞進(jìn)來的一個(gè)機(jī)房 id（但是最大只能是 32 以內(nèi)）捐迫，另外 5 bit 是你傳遞進(jìn)來的機(jī)器 id（但是最大只能是 32 以內(nèi)），剩下的那個(gè) 12 bit 序列號(hào)爱葵，就是如果跟你上次生成 id 的時(shí)間還在一個(gè)毫秒內(nèi)施戴，那么會(huì)把順序給你累加反浓，最多在 4096 個(gè)序號(hào)以內(nèi)。
所以你自己利用這個(gè)工具類赞哗，自己搞一個(gè)服務(wù)雷则，然后對(duì)每個(gè)機(jī)房的每個(gè)機(jī)器都初始化這么一個(gè)東西，剛開始這個(gè)機(jī)房的這個(gè)機(jī)器的序號(hào)就是 0肪笋。然后每次接收到一個(gè)請(qǐng)求月劈，說這個(gè)機(jī)房的這個(gè)機(jī)器要生成一個(gè) id，你就找到對(duì)應(yīng)的 Worker 生成藤乙。
利用這個(gè) snowflake 算法猜揪，你可以開發(fā)自己公司的服務(wù)，甚至對(duì)于機(jī)房 id 和機(jī)器 id坛梁，反正給你預(yù)留了 5bit + 5 bit而姐，你換成別的有業(yè)務(wù)含義的東西也可以的。
這個(gè) snowflake 算法相對(duì)來說還是比較靠譜的划咐，所以你要真是搞分布式 id 生成拴念，如果是高并發(fā)啥的，那么用這個(gè)應(yīng)該性能比較好褐缠，一般每秒幾萬并發(fā)的場景政鼠，也足夠你用了。
