聽說你學過架構設計?來,弄個短鏈系統

語言: CN / TW / HK

目錄

  1. 引言
  2. 三種連結生成方法
  3. 重定向過程
  4. 快取優化
  5. 高可用設計
  6. 後記

*01 引言*

1)背景

這是本人在面試“位元組抖音”部門的一道系統設計題,崗位是“後端高階開發工程師”,二面的時候問到的。一開始,面試官笑眯眯地讓我做個自我介紹,然後聊了聊專案。

當完美無瑕(吞吞吐吐)地聊完專案,並寫了一道演算法題之後。

面試官就開始發問了:小夥子,簡歷裡面寫到了熟悉架構設計是吧,那你知道程式設計的‘三高’指什麼嗎?

我心想,那不是由於程式設計師的系統不靠譜,領導不當人,天天加班改 BUG,導致年紀輕輕都高血脂、高血壓和高血糖嘛!

但是,既然是面試,那領導肯定不願意聽這,於是我回答:程式三高,就是系統設計時需要考慮的高併發、高效能和高可用:

  • 高併發就是在系統開發的過程中,需要保證系統可以同時並行處理很多請求;
  • 高效能是指程式需要儘可能地佔用更少的記憶體和 CPU,並且處理請求的速度要快;
  • 高可用通常描述系統在一段時間內不可服務的時候很短,比如全年停機不超過 31.5 秒,俗稱 6 個 9,即保證可用的時間為 99.9999%。

於是,面試官微微點頭,心想小夥子還行,既然這難不住你,那我可得出大招了,就來道系統設計題吧!

2)需求說明

眾所周知,當業務場景需要給使用者傳送網路地址或者二維碼時,由於地址的長度比較長,通常為了佔用更少的資源和提升使用者體驗。例如,谷歌搜尋“計算機”詞條地址如下:

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

很明顯,如果將這一長串網址發給使用者,是十分不“體面”的。而且,遇到一些有字數限制的系統裡面,比如微博發帖子就有字數限制,肯定無法傳送這樣的長連結地址。一般的簡訊連結中,大多也都是短連結地址:

所以,為了提升使用者體驗,以及日常業務的需要。我們需要設計一個短連結生成系統,除了業務功能實現以外,我們還得為全國的網路地址服務。在這麼大的使用者量下,資料該如何儲存,高併發如何處理呢?

*02 三種連結生成方法*

1)需求分析

我心想,這面試官看著“慈眉善目”還笑眯眯的,但出的題目可不簡單,這種型別的系統需要考慮的點太多了,絕對不能掉以輕心。

於是,我分別從連結生成、網址訪問、快取優化和高可用四個方面開始著手設計。

首先,生成短鏈地址,可以考慮用 UUID 或者自增 ID。對於每一個長連結轉短鏈地址時,都必須生成一個全域性唯一的短鏈值,不然就會發生衝突。所以,短連結的特點是:

  • 資料儲存量很大,全國的網址每天至少都是百萬個短連結地址需要生成;
  • 併發量也不小,遇到同時來訪問系統,按一天 3600 秒來算,平均每秒至少上千個請求數;
  • 短連結不可重複,否則會引起資料訪問衝突。

2)雪花演算法

首先,生成短連結,可以用雪花演算法+雜湊的方式來實現。


雪花演算法是在分散式場景下,根據時間戳、不同的機器 ID 以及序列號生成的唯一數。它的優點在於簡單方便,隨取隨用。

通過雪花演算法取到的唯一數,再用雜湊對映,將數字轉為一個隨機的字串,如果短鏈字串比較長,可以直接取前 6 位。但是,由於雜湊對映的結果可能會發生衝突,所以對雜湊演算法的要求比較高。

2)62 進位制數生成短連結

除了雪花演算法,還可以用 62 進位制數(A-Za-z0-9)來生成短連結地址。首先得到一個自增 ID,再將此值轉換為 62 進位制(a-zA-Z0-9)的字串,一個億的數字轉換後也就五六位(1億 -> zAL6e)。

將短連結伺服器域名,與這個字串進行拼接,就能得到短連結的 URL,比如:t.cn/zAL6e。

而生成自增 ID 需要考慮效能影響和併發安全性,所以我們可以通過 Redis 的 incr 命令來做一個發號器,它是一個原子操作,因此我們不必擔心數字的安全性。而 Redis 是記憶體操作,所以效率也挺高。

3)隨機數+布隆過濾器

除了自增 ID 以外,我們還可以生成隨機數再轉 62 進位制的方法來生成短連結。但是,由於隨機數可能重複,因此我們需要用布隆過濾器來去重。

布隆過濾器是一個巧妙設計的資料結構,它的原理是將一個值多次雜湊,對映到不同的 bit 位上並記錄下來。當新的值使用時,通過同樣的雜湊函式,比對各個 bit 位上是否有值:如果這些 bit 位上都沒有值,說明這個數是唯一的;否則,就可能不是唯一的。

當然,這可能會產生誤判,布隆過濾器一定可以發現重複的值,但 也可能將不重複的值判斷為重複值,誤判率大概為 0.05%,是可以接受的範圍,而且布隆過濾器的效率極高。

因此,通過布隆過濾器,我們能判斷生成的隨機數是否重複:如果重複,就重新生成一個;如果不重複,就存入布隆過濾器和資料庫,從而保證每次取到的隨機數都是唯一的。

4)將短連結存到資料庫

存庫時,可能會因為庫存量和技術棧,選用不同的資料庫。但由於公司部門用 MySQL 比較多,且當前題目未提及技術選型,所以我們還是選用 MySQL 作為持久化資料庫。

每當生成一個短連結後,需要在 MySQL 儲存短連結到長連結的對映關係並加上唯一索引,即 zAL6e -> 真實URL。

*03 重定向過程*

瀏覽器訪問短連結服務時,根據短鏈地址取到原始 URL,然後進行網址重定向。我們通常有兩種重定向方式:

  • 一種是返回給瀏覽器 301 響應碼永久重定向,讓其後續直接訪問真實的 URL 地址;
  • 一種是 302 臨時重定向,讓瀏覽器當前這次訪問真實 URL,但後續請求時還是根據短鏈地址訪問。

雖然用 301 瀏覽器只需一次請求,後續可以直接從瀏覽器獲取長連結,這種方法可以提升訪問速度,但是它沒法統計短連結的訪問次數。

所以根據業務需要,我們一般選用 302 重定向。

*04 快取設計*

由於短連結是分發到多個使用者手裡的,可能在短時間內會多次訪問,所以從 MySQL 寫入/獲取到長連結後可以放入 redis 快取。

1)加入快取

並且,短連結和長連結的對應關係一般不會頻繁修改,所以資料庫和快取的一致性通過簡單的旁路快取模式來保證:

  • 讀(Read)資料時,若快取未命中,則先讀 DB,從 DB 中取出資料,放入快取,同時返回響應;
  • 寫(Write)資料時,先更新 DB,再刪除快取。

當用戶需要生成短連結時,先到這個對映表中看一下有沒有對應的短連結地址。有就直接返回,並將這個 key-value 的過期時間增加一小時;沒有就重新生成,並且將對應關係存入這個對映表中。

快取的淘汰策略可以選用:

  • LRU:Least Recently Used,最近最少使用演算法,最近經常被讀寫的短鏈地址作為熱點資料可以一直存在於快取,淘汰那些很久沒有訪問過的短鏈 key;
  • LFU:Least Frequently Userd,最近最不頻繁使用演算法,最近訪問頻率高的短鏈地址作為熱點資料,淘汰那些訪問頻率較低的短鏈 key。

2)快取穿透

但是,使用快取也防止不了一些異常情況,比如“快取穿透”。所謂快取穿透,就是查詢一個快取和資料庫中都不存在的短連結,如果併發量很大,就會導致所有在快取中不存在的請求都打到 MySQL 伺服器上,導致伺服器處理不了這麼多請求而阻塞,甚至崩潰。

所以,為了防止不法分子通過類似“快取穿透”的方式來攻擊伺服器,我們可以採用兩種方法來應對:

  • 對不存在的短鏈地址加快取,key 為短連結地址,value 值為空,過期時間可以設定得短一點;
  • 採用布隆過濾器將已有的短連結多次雜湊後存起來,當有短連結請求時,先通過布隆過濾器判斷一下該地址是否存在資料庫中;如果不在,則說明資料庫中不存在該地址,就直接返回。

*05 高可用設計*

由於快取和資料庫持久化依賴於 Redis 和 MySQL,因此 MySQL 和 Redis 的高可用性必須要保證。

1)MySQL 高可用

MySQL 資料庫採用主從複製,進行讀寫分離。Master 節點進行寫操作,Slave 節點用作讀操作,並且可以用 Keepalived 來實現高可用。

Keepalived 的原理是採用虛擬 IP,檢測入口的多個節點,選用一臺熱備伺服器作為主伺服器,並分配給它一個虛擬 IP,外部請求都通過這個虛擬 IP 來訪問資料庫。

同時,Keepalived 會實時檢測多個節點的可用狀態,當發現一臺伺服器宕機或出現故障時,會從叢集中將這臺伺服器踢除。如果這臺伺服器是主伺服器,keepalived 會觸發選舉操作,從伺服器叢集中再選出一個伺服器充當 master 並分配給它相同的虛擬 IP,以此完成故障轉移。

並且,在 Keepalived 的支援下,這些操作都不需要人工參與,只需修復故障機器即可。

2)Redis 高可用

由於在大資料高併發的場景下,寫請求全部落在 Redis 的 master 節點上,壓力太大。如果一味地採用增加記憶體和 CPU 這種縱向擴容的方式,那麼一臺機器所面臨的磁碟 IO,網路等壓力逐漸增大,也會影響效能。

所以 Redis 採用叢集模式,實現資料分片。並且,加入了哨兵機制來保證叢集的高可用。它的基本原理是哨兵節點監控叢集中所有的主從節點,當主節點宕機或者發生故障以後,哨兵節點會標記它為主觀下線;當足夠多的哨兵節點將 Redis 主節點標記為主觀下線,就將其狀態改為客觀下線

此時,哨兵節點們通過選舉機制選出一個領頭哨兵,對 Redis 主節點進行故障轉移操作,以保障 Redis 叢集的高可用,這整個流程都不需要人工干預。

3)系統容錯

服務在上線之前,需要做好充分的業務量評估,以及效能測試。做好限流、熔斷和服務降級的邏輯,比如:採用令牌桶演算法實現限流,hystrix 框架來做熔斷,並且將常用配置放到可以熱更新的配置中心,方便對其實時更改。

當業務量過大時,將同步任務改為非同步任務處理。通過這些服務治理方案,讓系統更加穩定。

*06 後記*

當我答完最後一個字的時候,面試官看著我,眼神中充滿了“欣賞”與疑惑。我想,他應該是被我這番表現給鎮住了,此次面試應該是十拿九穩。

​但是,出奇地,面試官沒有對剛才的架構設計提出評價,只看了看我說:“那今天的面試就到這裡,你有什麼想要問的嗎?”

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

“演算法和專案需要再多練練,但是我發現了你一個優點。”面試官笑了笑接著說,“八股文背的倒是挺不錯的!”

懸著的心總算放下,我心想:“哦,那穩了~”