所謂系統(tǒng)設(shè)計(jì)，就是給一個(gè)場(chǎng)景，讓你給出對(duì)應(yīng)的架構(gòu)設(shè)計(jì)，需要考慮哪些問題，采用什么方案解決。很多面試官喜歡出這么一道題來考驗(yàn)?zāi)愕闹R(shí)廣度和邏輯思考能力。

雖然各個(gè)系統(tǒng)千差萬別，但是設(shè)計(jì)思想基本一致，學(xué)會(huì)一些經(jīng)典的架構(gòu)設(shè)計(jì)，掌握基本的設(shè)計(jì)方法和常見需要考慮的問題，用這一套方法論去應(yīng)對(duì)面試，應(yīng)該就沒啥問題了。

目前專欄已經(jīng)包含以下幾個(gè)經(jīng)典系統(tǒng)設(shè)計(jì)題：

高性能短鏈系統(tǒng)

高性能計(jì)數(shù)器

高性能未讀數(shù)計(jì)數(shù)器

高性能 Feed 流

高性能限流器

...... 后續(xù)會(huì)不斷增加

今天來分享下如何設(shè)計(jì)一個(gè)高性能的短鏈系統(tǒng)，字節(jié)三面的真實(shí)面試題。

什么是短鏈？為什么要用短鏈？

短鏈的好處如下：

鏈接變短，在對(duì)內(nèi)容長度有限制的平臺(tái)發(fā)文，可編輯的文字就變多了。比如微博限定了只能發(fā) 140 個(gè)字，如果一串長鏈直接復(fù)制上去就沒地方再寫其他文字了

大家接受各種短信的時(shí)候，能發(fā)現(xiàn)大部分鏈接都是短鏈形式，因?yàn)橐话愣绦虐l(fā)文有長度限度，如果用長鏈，一條短信很可能要拆分成兩三條發(fā)，相應(yīng)的成本也就增加了

使用短鏈在排版上更加美觀

短鏈跳轉(zhuǎn)的基本原理

點(diǎn)擊短鏈后，看下控制臺(tái)：

可以看到返回了狀態(tài)碼 302（重定向）與 location 值為長鏈的響應(yīng)，然后瀏覽器會(huì)再請(qǐng)求這個(gè)長鏈以得到最終的響應(yīng),整個(gè)交互流程圖如下：

那么問題來了，301 和 302 都是重定向，到底該用哪個(gè)，這里需要注意一下 301 和 302 的區(qū)別：

301，代表 永久重定向：第一次請(qǐng)求拿到長鏈接后，下次瀏覽器再去請(qǐng)求短鏈的話，不會(huì)向短鏈服務(wù)器請(qǐng)求了，而是直接從瀏覽器的緩存里拿，這樣的話短鏈服務(wù)器就無法獲取到短鏈的點(diǎn)擊數(shù)了，不利于數(shù)據(jù)分析，所以我們一般不采用 301

302，代表 臨時(shí)重定向：每次去請(qǐng)求短鏈都會(huì)去請(qǐng)求短鏈服務(wù)器（除非響應(yīng)中用 Cache-Control 或 Expired 暗示瀏覽器緩存），這樣便于短鏈服務(wù)器統(tǒng)計(jì)點(diǎn)擊數(shù)

生成短鏈的兩種方法

方法一：哈希算法

哈希算法可以將一個(gè)不管多長的字符串，轉(zhuǎn)化成一個(gè)長度固定的哈希值。我們可以利用哈希算法，來生成短鏈。

常見的哈希算法就是 MD5、SHA 等，但實(shí)際上并不需要這些復(fù)雜的哈希算法。因?yàn)樵谏啥替溸@個(gè)問題上不需要考慮反向解密的難度，只需要關(guān)心哈希算法的計(jì)算速度和沖突概率就可以了。

能夠滿足這樣要求的簡單的哈希算法有很多，其中比較著名并且應(yīng)用廣泛的一個(gè)哈希算法，那就是 MurmurHash 算法。盡管這個(gè)哈希算法在 2008 年才被發(fā)明出來，但現(xiàn)在它已經(jīng)廣泛應(yīng)用到 Redis、MemCache、Cassandra、HBase、Lucene 等眾多著名的軟件中。

MurmurHash 算法提供了兩種長度的哈希值，一種是 32bits，一種是 128bits。為了讓最終生成的短鏈盡可能短，我們可以選擇 32bits 的哈希值。比如假設(shè)某個(gè)長鏈接經(jīng)過 MurmurHash 計(jì)算后得到的哈希值是 181338494，再拼上短鏈服務(wù)的域名就變成了最終的短鏈 。

如何讓短鏈更短

不過，通過 MurmurHash 算法得到的短鏈還是很長啊。別著急，我們只需要稍微改變一個(gè)哈希值的表示方法，就可以輕松把短鏈變得更短些。

將 10 進(jìn)制的哈希值，轉(zhuǎn)化成更高進(jìn)制的哈希值，這樣哈希值就變短了。

16 進(jìn)制中，用 A～F，來表示 10～15。在網(wǎng)址 URL 中，常用的合法字符有 0～9、a～z、A～Z 這樣 62 個(gè)字符。為了讓哈希值表示起來盡可能短，我們可以將 10 進(jìn)制的哈希值轉(zhuǎn)化成 62 進(jìn)制。具體的計(jì)算過程如下圖。最終用 62 進(jìn)制表示的=短鏈就是 http://sourl.cn/cgSqq。

如何解決哈希沖突

哈希算法無法避免的一個(gè)問題，就是哈希沖突。盡管 MurmurHash 算法，沖突的概率非常低。但是，一旦沖突，就會(huì)導(dǎo)致兩個(gè)原始網(wǎng)址被轉(zhuǎn)化成同一個(gè)短鏈。當(dāng)用戶訪問短鏈的時(shí)候，我們就無從判斷，用戶想要訪問的是哪一個(gè)原始網(wǎng)址了。這個(gè)問題該如何解決呢？

一般情況下，我們會(huì)保存短鏈跟原始網(wǎng)址之間的對(duì)應(yīng)關(guān)系，以便后續(xù)用戶在訪問短鏈的時(shí)候，可以根據(jù)對(duì)應(yīng)關(guān)系，查找到原始網(wǎng)址。存儲(chǔ)這種對(duì)應(yīng)關(guān)系的方式有很多，比如我們自己設(shè)計(jì)存儲(chǔ)系統(tǒng)或者利用現(xiàn)成的數(shù)據(jù)庫比如 MySQL、Redis。

以 MySQL 為例，當(dāng)有一個(gè)新的原始網(wǎng)址需要生成短鏈的時(shí)候，我們先利用 MurmurHash 算法，生成短鏈。然后將這個(gè)新生成的短鏈，在 MySQL 數(shù)據(jù)庫中查找：

當(dāng)用戶訪問短鏈的時(shí)候，短鏈服務(wù)先通過短鏈，在數(shù)據(jù)庫中查找到對(duì)應(yīng)的原始網(wǎng)址。如果原始網(wǎng)址有拼接特殊字符（這個(gè)很容易通過字符串匹配算法找到），就先將特殊字符去掉，然后再將不包含特殊字符的原始網(wǎng)址返回給瀏覽器。

如果沒有找到相同的短鏈，這就表明這個(gè)新生成的短鏈沒有沖突。于是我們就將這個(gè)短鏈返回給用戶，然后將這個(gè)短鏈與原始網(wǎng)址之間的對(duì)應(yīng)關(guān)系，存儲(chǔ)到 MySQL 數(shù)據(jù)庫中

如果在數(shù)據(jù)庫中找到了相同的短鏈，那也并不一定說明就沖突了。我們先從數(shù)據(jù)庫中將這個(gè)短鏈對(duì)應(yīng)的原始網(wǎng)址取出來：

如果數(shù)據(jù)庫中的原始網(wǎng)址，跟我們現(xiàn)在正在處理的原始網(wǎng)址是一樣的，這就說明已經(jīng)有人請(qǐng)求過這個(gè)原始網(wǎng)址的短鏈了。我們就可以拿這個(gè)短鏈直接用。

如果數(shù)據(jù)庫中記錄的原始網(wǎng)址，跟我們正在處理的原始網(wǎng)址不一樣，那就說明哈希算法發(fā)生了沖突。不同的原始網(wǎng)址，經(jīng)過計(jì)算，得到的短鏈重復(fù)了。這個(gè)時(shí)候，我們可以給原始網(wǎng)址拼接一串特殊字符，比如 DUPLICATED，然后再重新計(jì)算哈希值，兩次哈希計(jì)算都沖突的概率，顯然是非常低的。

假設(shè)出現(xiàn)非常極端的情況，又發(fā)生沖突了，我們可以再換一個(gè)拼接字符串，比如 OHMYGOD，再計(jì)算哈希值。然后把計(jì)算得到的哈希值，跟原始網(wǎng)址拼接了特殊字符串之后的文本，一并存儲(chǔ)在 MySQL 數(shù)據(jù)庫中。

如何優(yōu)化性能

在短鏈生成的過程中，服務(wù)器會(huì)執(zhí)行兩條 SQL 語句：

第一個(gè) SQL 語句是通過短鏈查詢短鏈與原始網(wǎng)址的對(duì)應(yīng)關(guān)系

第二個(gè) SQL 語句是將新生成的短鏈和原始網(wǎng)址之間的對(duì)應(yīng)關(guān)系存儲(chǔ)到數(shù)據(jù)庫

很顯然，第二步是無法避免的，而第一步可以通過給短鏈字段建立唯一索引來優(yōu)化

這樣，當(dāng)有新的原始網(wǎng)址需要生成短鏈的時(shí)候，并不會(huì)拿生成的短鏈在數(shù)據(jù)庫中查找判重，而是直接將生成的短鏈與對(duì)應(yīng)的原始網(wǎng)址嘗試存儲(chǔ)到數(shù)據(jù)庫中。如果數(shù)據(jù)庫能夠?qū)?shù)據(jù)正常寫入，那說明并沒有違反唯一索引，也就是說，這個(gè)新生成的短鏈并沒有沖突。

當(dāng)然，如果數(shù)據(jù)庫反饋違反唯一性索引異常，那我們還得重新執(zhí)行上述的“查詢、寫入”過程，SQL 語句執(zhí)行的次數(shù)不減反增。但是，MurmurHash 的沖突概率還是比較低的，所以，從整體上看，總的 SQL 語句執(zhí)行次數(shù)會(huì)大大減少。

那如果數(shù)據(jù)量非常大，沖突概率大幅上升，這種情況下該怎么辦？

可以使用布隆過濾器。

把已經(jīng)生成的短鏈，構(gòu)建成布隆過濾器。當(dāng)有新的短鏈生成的時(shí)候，我們先拿這個(gè)新生成的短鏈，在布隆過濾器中查找。如果查找的結(jié)果是不存在，那就說明這個(gè)新生成的短鏈并沒有沖突。這個(gè)時(shí)候，我們只需要再執(zhí)行寫入短鏈和對(duì)應(yīng)原始網(wǎng)頁的 SQL 語句就可以了。

方法二：ID 生成器

我們可以維護(hù)一個(gè) ID 自增生成器。它可以生成 1、2、3…這樣自增的整數(shù) ID。當(dāng)短鏈服務(wù)接收到一個(gè)原始網(wǎng)址轉(zhuǎn)化成短鏈的請(qǐng)求之后，它先從 ID 生成器中取一個(gè)號(hào)碼，然后將其轉(zhuǎn)化成 62 進(jìn)制表示法，拼接到短鏈服務(wù)的域名（比如http://sourl.cn/）后面，就形成了最終的短鏈。最后，我們還是會(huì)把生成的短鏈和對(duì)應(yīng)的原始網(wǎng)址存儲(chǔ)到數(shù)據(jù)庫中。

理論非常簡單好理解。不過，這里有幾個(gè)細(xì)節(jié)問題需要處理。

相同的原始網(wǎng)址可能會(huì)對(duì)應(yīng)不同的短鏈

每次新來一個(gè)原始網(wǎng)址，我們就生成一個(gè)新的短鏈，這種做法就會(huì)導(dǎo)致兩個(gè)相同的原始網(wǎng)址生成了不同的短鏈。這個(gè)該如何處理呢？實(shí)際上，我們有兩種處理思路。

第一種處理思路是不做處理。聽起來有點(diǎn)匪夷所依，但實(shí)際上，相同的原始網(wǎng)址對(duì)應(yīng)不同的短鏈，這個(gè)用戶是完全可以接受的。在大部分短鏈的應(yīng)用場(chǎng)景里，用戶只關(guān)心短鏈能否正確地跳轉(zhuǎn)到原始網(wǎng)址。至于短鏈長什么樣子，他其實(shí)根本就不關(guān)心。

第二種處理思路是拿原始網(wǎng)址在數(shù)據(jù)庫中查找，看數(shù)據(jù)庫中是否已經(jīng)存在相同的原始網(wǎng)址了。如果數(shù)據(jù)庫中存在，那我們就取出對(duì)應(yīng)的短鏈，直接返回給用戶。

不過，這種處理思路有個(gè)問題，我們需要給數(shù)據(jù)庫中的短鏈和原始網(wǎng)址這兩個(gè)字段，都添加索引。短鏈上加索引是為了提高用戶查詢短鏈對(duì)應(yīng)的原始網(wǎng)頁的速度，原始網(wǎng)址上加索引是為了加快剛剛講的通過原始網(wǎng)址查詢短鏈的速度。這種解決思路雖然能滿足 “相同原始網(wǎng)址對(duì)應(yīng)相同短鏈” 這樣一個(gè)需求，但是是有代價(jià)的：一方面兩個(gè)索引會(huì)占用更多的存儲(chǔ)空間，另一方面索引還會(huì)導(dǎo)致插入、刪除等操作性能的下降。

如何實(shí)現(xiàn)高性能的 ID 生成器

實(shí)現(xiàn) ID 生成器的方法有很多，比如利用數(shù)據(jù)庫自增。當(dāng)然我們也可以自己維護(hù)一個(gè)計(jì)數(shù)器，不停地加一加一。但是，一個(gè)計(jì)數(shù)器來應(yīng)對(duì)頻繁的短鏈生成請(qǐng)求，顯然是有點(diǎn)吃力的（因?yàn)橛?jì)數(shù)器必須保證生成的 ID 不重復(fù)，籠統(tǒng)概念上講，就是需要加鎖）。如何提高 ID 生成器的性能呢？關(guān)于這個(gè)問題，實(shí)際上，有很多解決思路。我這里給出兩種思路。

第一種思路是給 ID 生成器裝多個(gè)前置發(fā)號(hào)器。我們批量地給每個(gè)前置發(fā)號(hào)器發(fā)送 ID 號(hào)碼段（這一段的 ID 歸屬于這個(gè)發(fā)號(hào)器，不用擔(dān)心ID 重復(fù)）。當(dāng)我們接受到短鏈生成請(qǐng)求的時(shí)候，只需要選擇一個(gè)前置發(fā)號(hào)器來取號(hào)碼就行了。這樣通過多個(gè)前置發(fā)號(hào)器，明顯提高了并發(fā)發(fā)號(hào)的能力。

可能不是很好理解，這里類比下 “無鎖的并發(fā)生產(chǎn)者 - 消費(fèi)者模型”：

對(duì)于生產(chǎn)者來說，它往隊(duì)列中添加數(shù)據(jù)之前，先申請(qǐng)可用空閑存儲(chǔ)單元，并且是批量地申請(qǐng)連續(xù)的 n 個(gè)（n≥1）存儲(chǔ)單元。當(dāng)申請(qǐng)到這組連續(xù)的存儲(chǔ)單元之后，后續(xù)往隊(duì)列中添加元素，就可以不用加鎖了，因?yàn)檫@組存儲(chǔ)單元是這個(gè)線程獨(dú)享的。不過，申請(qǐng)存儲(chǔ)單元的過程還是需要加鎖的。

對(duì)于消費(fèi)者來說，處理的過程跟生產(chǎn)者是類似的。它先去申請(qǐng)一批連續(xù)可讀的存儲(chǔ)單元（這個(gè)申請(qǐng)的過程也是需要加鎖的），當(dāng)申請(qǐng)到這批存儲(chǔ)單元之后，后續(xù)的讀取操作就可以不用加鎖了。

第二種思路跟第一種差不多。不過，我們不再使用一個(gè) ID 生成器和多個(gè)前置發(fā)號(hào)器這樣的架構(gòu)，而是直接實(shí)現(xiàn)多個(gè) ID 生成器同時(shí)服務(wù)。每個(gè) ID 生成器按照不同的規(guī)則來生成 ID 號(hào)碼，從而保證每個(gè) ID 生成器生成的 ID 不重復(fù)。比如，第一個(gè) ID 生成器只能生成尾號(hào)為 0 的，第二個(gè)只能生成尾號(hào)為 1 的，以此類推。這樣通過多個(gè) ID 生成器同時(shí)工作，也提高了 ID 生成的效率。

審核編輯：劉清