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

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

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

• 高性能短鏈系統(tǒng)
• 高性能計(jì)數(shù)器
• 高性能未讀數(shù)計(jì)數(shù)器
• 高性能 Feed 流
• 高性能限流器
• ...... 后續(xù)會不斷增加

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

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

比如將 https://flowus.cn/veal/share/3306b991-e1e3-4c92-9105-95abf086ae4e 縮短為 https://sourl.cn/aY95qu，點(diǎn)擊后面的短鏈接將會重定向到前面的長鏈接。

短鏈的好處如下：

1. 鏈接變短，在對內(nèi)容長度有限制的平臺發(fā)文，可編輯的文字就變多了。比如微博限定了只能發(fā) 140 個字，如果一串長鏈直接復(fù)制上去就沒地方再寫其他文字了
2. 大家接受各種短信的時候，能發(fā)現(xiàn)大部分鏈接都是短鏈形式，因?yàn)橐话愣绦虐l(fā)文有長度限度，如果用長鏈，一條短信很可能要拆分成兩三條發(fā)，相應(yīng)的成本也就增加了
3. 使用短鏈在排版上更加美觀

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

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

圖片

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

圖片

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

• 301，代表 永久重定向：第一次請求拿到長鏈接后，下次瀏覽器再去請求短鏈的話，不會向短鏈服務(wù)器請求了，而是直接從瀏覽器的緩存里拿，這樣的話短鏈服務(wù)器就無法獲取到短鏈的點(diǎn)擊數(shù)了，不利于數(shù)據(jù)分析，所以我們一般不采用 301
• 302，代表 臨時重定向：每次去請求短鏈都會去請求短鏈服務(wù)器（除非響應(yīng)中用 Cache-Control 或 Expired 暗示瀏覽器緩存），這樣便于短鏈服務(wù)器統(tǒng)計(jì)點(diǎn)擊數(shù)

生成短鏈的兩種方法

方法 1：哈希算法

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

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

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

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

如何讓短鏈更短

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

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

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

圖片

如何解決哈希沖突

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

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

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

• 如果沒有找到相同的短鏈，這就表明這個新生成的短鏈沒有沖突。于是我們就將這個短鏈返回給用戶，然后將這個短鏈與原始網(wǎng)址之間的對應(yīng)關(guān)系，存儲到 MySQL 數(shù)據(jù)庫中
• 如果在數(shù)據(jù)庫中找到了相同的短鏈，那也并不一定說明就沖突了。我們先從數(shù)據(jù)庫中將這個短鏈對應(yīng)的原始網(wǎng)址取出來：

• 如果數(shù)據(jù)庫中的原始網(wǎng)址，跟我們現(xiàn)在正在處理的原始網(wǎng)址是一樣的，這就說明已經(jīng)有人請求過這個原始網(wǎng)址的短鏈了。我們就可以拿這個短鏈直接用。
• 如果數(shù)據(jù)庫中記錄的原始網(wǎng)址，跟我們正在處理的原始網(wǎng)址不一樣，那就說明哈希算法發(fā)生了沖突。不同的原始網(wǎng)址，經(jīng)過計(jì)算，得到的短鏈重復(fù)了。這個時候，我們可以給原始網(wǎng)址拼接一串特殊字符，比如 DUPLICATED，然后再重新計(jì)算哈希值，兩次哈希計(jì)算都沖突的概率，顯然是非常低的。假設(shè)出現(xiàn)非常極端的情況，又發(fā)生沖突了，我們可以再換一個拼接字符串，比如 OHMYGOD，再計(jì)算哈希值。然后把計(jì)算得到的哈希值，跟原始網(wǎng)址拼接了特殊字符串之后的文本，一并存儲在 MySQL 數(shù)據(jù)庫中。
  當(dāng)用戶訪問短鏈的時候，短鏈服務(wù)先通過短鏈，在數(shù)據(jù)庫中查找到對應(yīng)的原始網(wǎng)址。如果原始網(wǎng)址有拼接特殊字符（這個很容易通過字符串匹配算法找到），就先將特殊字符去掉，然后再將不包含特殊字符的原始網(wǎng)址返回給瀏覽器。

如何優(yōu)化性能

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

1. 第一個 SQL 語句是通過短鏈查詢短鏈與原始網(wǎng)址的對應(yīng)關(guān)系
2. 第二個 SQL 語句是將新生成的短鏈和原始網(wǎng)址之間的對應(yīng)關(guān)系存儲到數(shù)據(jù)庫

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

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

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

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

可以使用布隆過濾器。

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

方法二：ID 生成器

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

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

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

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

1. 第一種處理思路是不做處理。聽起來有點(diǎn)匪夷所依，但實(shí)際上，相同的原始網(wǎng)址對應(yīng)不同的短鏈，這個用戶是完全可以接受的。在大部分短鏈的應(yīng)用場景里，用戶只關(guān)心短鏈能否正確地跳轉(zhuǎn)到原始網(wǎng)址。至于短鏈長什么樣子，他其實(shí)根本就不關(guān)心。
2. 第二種處理思路是拿原始網(wǎng)址在數(shù)據(jù)庫中查找，看數(shù)據(jù)庫中是否已經(jīng)存在相同的原始網(wǎng)址了。如果數(shù)據(jù)庫中存在，那我們就取出對應(yīng)的短鏈，直接返回給用戶。
   不過，這種處理思路有個問題，我們需要給數(shù)據(jù)庫中的短鏈和原始網(wǎng)址這兩個字段，都添加索引。短鏈上加索引是為了提高用戶查詢短鏈對應(yīng)的原始網(wǎng)頁的速度，原始網(wǎng)址上加索引是為了加快剛剛講的通過原始網(wǎng)址查詢短鏈的速度。這種解決思路雖然能滿足 “相同原始網(wǎng)址對應(yīng)相同短鏈” 這樣一個需求，但是是有代價的：一方面兩個索引會占用更多的存儲空間，另一方面索引還會導(dǎo)致插入、刪除等操作性能的下降。

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

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

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

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

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

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

圖片

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

圖片