目錄

1. 引言

2. 三種鏈接生成方法

3. 重定向過程

4. 緩存優(yōu)化

5. 高可用設(shè)計

6. 后記
   

01 引言

1）背景

這是本人在面試“字節(jié)抖音”部門的一道系統(tǒng)設(shè)計題，崗位是“后端高級開發(fā)工程師”，二面的時候問到的。一開始，面試官笑瞇瞇地讓我做個自我介紹，然后聊了聊項目。

當(dāng)完美無瑕（吞吞吐吐）地聊完項目，并寫了一道算法題之后。

面試官就開始發(fā)問了：小伙子，簡歷里面寫到了熟悉架構(gòu)設(shè)計是吧，那你知道程序設(shè)計的‘三高’指什么嗎？

我心想，那不是由于程序員的系統(tǒng)不靠譜，領(lǐng)導(dǎo)不當(dāng)人，天天加班改 BUG，導(dǎo)致年紀(jì)輕輕都高血脂、高血壓和高血糖嘛！

但是，既然是面試，那領(lǐng)導(dǎo)肯定不愿意聽這，于是我回答：程序三高，就是系統(tǒng)設(shè)計時需要考慮的高并發(fā)、高性能和高可用：

• 高并發(fā)就是在系統(tǒng)開發(fā)的過程中，需要保證系統(tǒng)可以同時并行處理很多請求；

• 高性能是指程序需要盡可能地占用更少的內(nèi)存和 CPU，并且處理請求的速度要快；

• 高可用通常描述系統(tǒng)在一段時間內(nèi)不可服務(wù)的時候很短，比如全年停機(jī)不超過 31.5 秒，俗稱 6 個 9，即保證可用的時間為 99.9999%。

于是，面試官微微點(diǎn)頭，心想小伙子還行，既然這難不住你，那我可得出大招了，就來道系統(tǒng)設(shè)計題吧！

2）需求說明

眾所周知，當(dāng)業(yè)務(wù)場景需要給用戶發(fā)送網(wǎng)絡(luò)地址或者二維碼時，由于地址的長度比較長，通常為了占用更少的資源和提升用戶體驗。例如，谷歌搜索“計算機(jī)”詞條地址如下：

https://www.google.com/search?q=%E8%AE%A1%E7%AE%97%E6%9C%BA&ei=KNZ5Y7y4MpiW-AaI4LSACw&ved=0ahUKEwi87MGgnbz7AhUYC94KHQgwDbAQ4dUDCBA&uact=5&oq=%E8%AE%A1%E7%AE%97%E6%9C%BA&gs_lcp=Cgxnd3Mtd2l6LXNlcnAQAzIECAAQQzIFCAAQgAQyBQgAEIAEMgUIABCABDIFCC4QgAQyBQgAEIAEMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDoKCAAQRxDWBBCwAzoLCC4QgAQQxwEQ0QM6FggAEOoCELQCEIoDELcDENQDEOUCGAE6BwguENQCEENKBAhBGABKBAhGGABQpBZYzSVglydoA3ABeACAAZ0DiAGdD5IBCTAuNy4xLjAuMZgBAKABAbABCsgBCsABAdoBBAgBGAc&sclient=gws-wiz-serp

很明顯，如果將這一長串網(wǎng)址發(fā)給用戶，是十分不“體面”的。而且，遇到一些有字?jǐn)?shù)限制的系統(tǒng)里面，比如微博發(fā)帖子就有字?jǐn)?shù)限制，肯定無法發(fā)送這樣的長鏈接地址。一般的短信鏈接中，大多也都是短鏈接地址：

所以，為了提升用戶體驗，以及日常業(yè)務(wù)的需要。我們需要設(shè)計一個短鏈接生成系統(tǒng)，除了業(yè)務(wù)功能實現(xiàn)以外，我們還得為全國的網(wǎng)絡(luò)地址服務(wù)。在這么大的用戶量下，數(shù)據(jù)該如何存儲，高并發(fā)如何處理呢？

02 三種鏈接生成方法

1）需求分析

我心想，這面試官看著“慈眉善目”還笑瞇瞇的，但出的題目可不簡單，這種類型的系統(tǒng)需要考慮的點(diǎn)太多了，絕對不能掉以輕心。

于是，我分別從鏈接生成、網(wǎng)址訪問、緩存優(yōu)化和高可用四個方面開始著手設(shè)計。

首先，生成短鏈地址，可以考慮用 UUID 或者自增 ID。對于每一個長鏈接轉(zhuǎn)短鏈地址時，都必須生成一個全局唯一的短鏈值，不然就會發(fā)生沖突。所以，短鏈接的特點(diǎn)是：

• 數(shù)據(jù)存儲量很大，全國的網(wǎng)址每天至少都是百萬個短鏈接地址需要生成；

• 并發(fā)量也不小，遇到同時來訪問系統(tǒng)，按一天 3600 秒來算，平均每秒至少上千個請求數(shù)；

• 短鏈接不可重復(fù)，否則會引起數(shù)據(jù)訪問沖突。

2）雪花算法

首先，生成短鏈接，可以用雪花算法+哈希的方式來實現(xiàn)。

雪花算法是在分布式場景下，根據(jù)時間戳、不同的機(jī)器 ID 以及序列號生成的唯一數(shù)。它的優(yōu)點(diǎn)在于簡單方便，隨取隨用。

通過雪花算法取到的唯一數(shù)，再用哈希映射，將數(shù)字轉(zhuǎn)為一個隨機(jī)的字符串，如果短鏈字符串比較長，可以直接取前 6 位。但是，由于哈希映射的結(jié)果可能會發(fā)生沖突，所以對哈希算法的要求比較高。

2）62 進(jìn)制數(shù)生成短鏈接

除了雪花算法，還可以用 62 進(jìn)制數(shù)（A-Za-z0-9）來生成短鏈接地址。首先得到一個自增 ID，再將此值轉(zhuǎn)換為 62 進(jìn)制（a-zA-Z0-9）的字符串，一個億的數(shù)字轉(zhuǎn)換后也就五六位（1億 ->?zAL6e）。

將短鏈接服務(wù)器域名，與這個字符串進(jìn)行拼接，就能得到短鏈接的 URL，比如：t.cn/zAL6e。

而生成自增 ID 需要考慮性能影響和并發(fā)安全性，所以我們可以通過 Redis 的 incr 命令來做一個發(fā)號器，它是一個原子操作，因此我們不必?fù)?dān)心數(shù)字的安全性。而 Redis 是內(nèi)存操作，所以效率也挺高。

3）隨機(jī)數(shù)+布隆過濾器

除了自增 ID 以外，我們還可以生成隨機(jī)數(shù)再轉(zhuǎn) 62 進(jìn)制的方法來生成短鏈接。但是，由于隨機(jī)數(shù)可能重復(fù)，因此我們需要用布隆過濾器來去重。

布隆過濾器是一個巧妙設(shè)計的數(shù)據(jù)結(jié)構(gòu)，它的原理是將一個值多次哈希，映射到不同的 bit 位上并記錄下來。當(dāng)新的值使用時，通過同樣的哈希函數(shù)，比對各個 bit 位上是否有值：如果這些 bit 位上都沒有值，說明這個數(shù)是唯一的；否則，就可能不是唯一的。

當(dāng)然，這可能會產(chǎn)生誤判，布隆過濾器一定可以發(fā)現(xiàn)重復(fù)的值，但也可能將不重復(fù)的值判斷為重復(fù)值，誤判率大概為 0.05%，是可以接受的范圍，而且布隆過濾器的效率極高。

因此，通過布隆過濾器，我們能判斷生成的隨機(jī)數(shù)是否重復(fù)：如果重復(fù)，就重新生成一個；如果不重復(fù)，就存入布隆過濾器和數(shù)據(jù)庫，從而保證每次取到的隨機(jī)數(shù)都是唯一的。

4）將短鏈接存到數(shù)據(jù)庫

存庫時，可能會因為庫存量和技術(shù)棧，選用不同的數(shù)據(jù)庫。但由于公司部門用 MySQL 比較多，且當(dāng)前題目未提及技術(shù)選型，所以我們還是選用 MySQL 作為持久化數(shù)據(jù)庫。

每當(dāng)生成一個短鏈接后，需要在 MySQL 存儲短鏈接到長鏈接的映射關(guān)系并加上唯一索引，即 zAL6e -> 真實URL。

03 重定向過程

瀏覽器訪問短鏈接服務(wù)時，根據(jù)短鏈地址取到原始 URL，然后進(jìn)行網(wǎng)址重定向。我們通常有兩種重定向方式：

• 一種是返回給瀏覽器 301 響應(yīng)碼永久重定向，讓其后續(xù)直接訪問真實的 URL 地址；

• 一種是 302 臨時重定向，讓瀏覽器當(dāng)前這次訪問真實 URL，但后續(xù)請求時還是根據(jù)短鏈地址訪問。

雖然用 301 瀏覽器只需一次請求，后續(xù)可以直接從瀏覽器獲取長鏈接，這種方法可以提升訪問速度，但是它沒法統(tǒng)計短鏈接的訪問次數(shù)。

所以根據(jù)業(yè)務(wù)需要，我們一般選用 302 重定向。

04 緩存設(shè)計

由于短鏈接是分發(fā)到多個用戶手里的，可能在短時間內(nèi)會多次訪問，所以從 MySQL 寫入/獲取到長鏈接后可以放入 redis 緩存。

1）加入緩存

并且，短鏈接和長鏈接的對應(yīng)關(guān)系一般不會頻繁修改，所以數(shù)據(jù)庫和緩存的一致性通過簡單的旁路緩存模式來保證：

• 讀（Read）數(shù)據(jù)時，若緩存未命中，則先讀 DB，從 DB 中取出數(shù)據(jù)，放入緩存，同時返回響應(yīng)；

• 寫（Write）數(shù)據(jù)時，先更新 DB，再刪除緩存。

當(dāng)用戶需要生成短鏈接時，先到這個映射表中看一下有沒有對應(yīng)的短鏈接地址。有就直接返回，并將這個 key-value 的過期時間增加一小時；沒有就重新生成，并且將對應(yīng)關(guān)系存入這個映射表中。

緩存的淘汰策略可以選用：

• LRU：Least Recently Used，最近最少使用算法，最近經(jīng)常被讀寫的短鏈地址作為熱點(diǎn)數(shù)據(jù)可以一直存在于緩存，淘汰那些很久沒有訪問過的短鏈 key；

• LFU：Least Frequently Userd，最近最不頻繁使用算法，最近訪問頻率高的短鏈地址作為熱點(diǎn)數(shù)據(jù)，淘汰那些訪問頻率較低的短鏈 key。

2）緩存穿透

但是，使用緩存也防止不了一些異常情況，比如“緩存穿透”。所謂緩存穿透，就是查詢一個緩存和數(shù)據(jù)庫中都不存在的短鏈接，如果并發(fā)量很大，就會導(dǎo)致所有在緩存中不存在的請求都打到 MySQL 服務(wù)器上，導(dǎo)致服務(wù)器處理不了這么多請求而阻塞，甚至崩潰。

所以，為了防止不法分子通過類似“緩存穿透”的方式來攻擊服務(wù)器，我們可以采用兩種方法來應(yīng)對：

• 對不存在的短鏈地址加緩存，key 為短鏈接地址，value 值為空，過期時間可以設(shè)置得短一點(diǎn)；

• 采用布隆過濾器將已有的短鏈接多次哈希后存起來，當(dāng)有短鏈接請求時，先通過布隆過濾器判斷一下該地址是否存在數(shù)據(jù)庫中；如果不在，則說明數(shù)據(jù)庫中不存在該地址，就直接返回。

05 高可用設(shè)計

由于緩存和數(shù)據(jù)庫持久化依賴于 Redis 和 MySQL，因此 MySQL 和 Redis 的高可用性必須要保證。

1）MySQL 高可用

MySQL 數(shù)據(jù)庫采用主從復(fù)制，進(jìn)行讀寫分離。Master 節(jié)點(diǎn)進(jìn)行寫操作，Slave 節(jié)點(diǎn)用作讀操作，并且可以用 Keepalived 來實現(xiàn)高可用。

Keepalived 的原理是采用虛擬 IP，檢測入口的多個節(jié)點(diǎn)，選用一臺熱備服務(wù)器作為主服務(wù)器，并分配給它一個虛擬 IP，外部請求都通過這個虛擬 IP 來訪問數(shù)據(jù)庫。

同時，Keepalived 會實時檢測多個節(jié)點(diǎn)的可用狀態(tài)，當(dāng)發(fā)現(xiàn)一臺服務(wù)器宕機(jī)或出現(xiàn)故障時，會從集群中將這臺服務(wù)器踢除。如果這臺服務(wù)器是主服務(wù)器，keepalived 會觸發(fā)選舉操作，從服務(wù)器集群中再選出一個服務(wù)器充當(dāng) master 并分配給它相同的虛擬 IP，以此完成故障轉(zhuǎn)移。

并且，在 Keepalived 的支持下，這些操作都不需要人工參與，只需修復(fù)故障機(jī)器即可。

2）Redis 高可用

由于在大數(shù)據(jù)高并發(fā)的場景下，寫請求全部落在 Redis 的 master 節(jié)點(diǎn)上，壓力太大。如果一味地采用增加內(nèi)存和 CPU 這種縱向擴(kuò)容的方式，那么一臺機(jī)器所面臨的磁盤 IO，網(wǎng)絡(luò)等壓力逐漸增大，也會影響性能。

所以 Redis 采用集群模式，實現(xiàn)數(shù)據(jù)分片。并且，加入了哨兵機(jī)制來保證集群的高可用。它的基本原理是哨兵節(jié)點(diǎn)監(jiān)控集群中所有的主從節(jié)點(diǎn)，當(dāng)主節(jié)點(diǎn)宕機(jī)或者發(fā)生故障以后，哨兵節(jié)點(diǎn)會標(biāo)記它為主觀下線；當(dāng)足夠多的哨兵節(jié)點(diǎn)將 Redis 主節(jié)點(diǎn)標(biāo)記為主觀下線，就將其狀態(tài)改為客觀下線。

此時，哨兵節(jié)點(diǎn)們通過選舉機(jī)制選出一個領(lǐng)頭哨兵，對 Redis 主節(jié)點(diǎn)進(jìn)行故障轉(zhuǎn)移操作，以保障 Redis 集群的高可用，這整個流程都不需要人工干預(yù)。

3）系統(tǒng)容錯

服務(wù)在上線之前，需要做好充分的業(yè)務(wù)量評估，以及性能測試。做好限流、熔斷和服務(wù)降級的邏輯，比如：采用令牌桶算法實現(xiàn)限流，hystrix 框架來做熔斷，并且將常用配置放到可以熱更新的配置中心，方便對其實時更改。

當(dāng)業(yè)務(wù)量過大時，將同步任務(wù)改為異步任務(wù)處理。通過這些服務(wù)治理方案，讓系統(tǒng)更加穩(wěn)定。

06 后記

當(dāng)我答完最后一個字的時候，面試官看著我，眼神中充滿了“欣賞”與疑惑。我想，他應(yīng)該是被我這番表現(xiàn)給鎮(zhèn)住了，此次面試應(yīng)該是十拿九穩(wěn)。

但是，出奇地，面試官沒有對剛才的架構(gòu)設(shè)計提出評價，只看了看我說：“那今天的面試就到這里，你有什么想要問的嗎？”

這下，輪到我震驚了，那到底過不過呢？倒是給句話呀，于是我問道：“通過這次面試，您覺得我有哪些方面需要提升呢？”

“算法和項目需要再多練練，但是我發(fā)現(xiàn)了你一個優(yōu)點(diǎn)。”面試官笑了笑接著說，“八股文背的倒是挺不錯的！”

懸著的心總算放下，我心想：“哦，那穩(wěn)了~”