如何設(shè)計短網(wǎng)址服務(wù)

作者：soulmachine

地址：https://github.com/soulmachine

本文雖然是作者幾年前的文章，但并不過時！文中介紹了如何設(shè)計短網(wǎng)址服務(wù)，簡潔地指出了該服務(wù)要注意的問題和解決方案。下面是正文：

一、短網(wǎng)址的長度

短網(wǎng)址的長度該設(shè)計為多少呢？當前互聯(lián)網(wǎng)上的網(wǎng)頁總數(shù)大概是 45 億，超過了 ，那么用一個 64 位整數(shù)足夠了。

一個 64 位整數(shù)如何轉(zhuǎn)化為字符串呢？，假設(shè)我們只是用大小寫字母加數(shù)字，那么可以看做是 62 進制數(shù)  

即字符串最長 11 就足夠了。

實際生產(chǎn)中，還可以再短一點，比如新浪微博采用的長度就是 7，因為 這個量級遠遠超過互聯(lián)網(wǎng)上的URL總數(shù)了，絕對夠用了。

現(xiàn)代的 Web 服務(wù)器（例如 Apache、Nginx）大部分都區(qū)分 URL 里的大小寫了，所以用大小寫字母來區(qū)分不同的 URL 是沒問題的。

因此，正確答案：長度不超過 7 的字符串，由大小寫字母加數(shù)字共 62 個字母組成

二、一對一還是一對多映射？

一個長網(wǎng)址，對應(yīng)一個短網(wǎng)址，還是可以對應(yīng)多個短網(wǎng)址？這也是個重大選擇問題

一般而言，一個長網(wǎng)址，在不同的地點，不同的用戶等情況下，生成的短網(wǎng)址應(yīng)該不一樣，這樣，在后端數(shù)據(jù)庫中，可以更好的進行數(shù)據(jù)分析。如果一個長網(wǎng)址與一個短網(wǎng)址一一對應(yīng)，那么在數(shù)據(jù)庫中，僅有一行數(shù)據(jù)，無法區(qū)分不同的來源，就無法做數(shù)據(jù)分析了。

以這個7位長度的短網(wǎng)址作為唯一 ID，這個 ID 下可以掛各種信息，比如生成該網(wǎng)址的用戶名，所在網(wǎng)站，HTTP 頭部的 User Agent 等信息，收集了這些信息，才有可能在后面做大數(shù)據(jù)分析，挖掘數(shù)據(jù)的價值。短網(wǎng)址服務(wù)商的一大盈利來源就是這些數(shù)據(jù)。

正確答案：一對多

三、如何計算短網(wǎng)址

現(xiàn)在我們設(shè)定了短網(wǎng)址是一個長度為 7 的字符串，如何計算得到這個短網(wǎng)址呢？

最容易想到的辦法是哈希，先 hash 得到一個 64 位整數(shù)，將它轉(zhuǎn)化為 62 進制整，截取低 7 位即可。但是哈希算法會有沖突，如何處理沖突呢，又是一個麻煩。這個方法只是轉(zhuǎn)移了矛盾，沒有解決矛盾，拋棄。

MySQL 數(shù)據(jù)庫有一個自增 ID，能不能借鑒這個呢？每來一個長網(wǎng)址，就給它發(fā)一個號碼，這個號碼不斷的自增。這個方法跟哈希相比，好處是沒有沖突，不用考慮處理沖突的問題。如何實現(xiàn)單臺的發(fā)號服務(wù)器呢？可以用一臺 MySQL 服務(wù)器來做（一定要用 REPLACE INTO，不要存儲所有 ID），也可用一臺 Redis 服務(wù)器（用 INCR），一行代碼也不用寫；也可以自己寫一個 RESTful API，代碼也很簡單，就不贅述了。

單臺發(fā)號器有什么缺點呢？它是一個單點故障（SPOF, Single Point Of Failure），也會成為性能瓶頸（其實，如果你的 QPS 能大到壓垮這臺 MySQL，那說明你的短網(wǎng)址服務(wù)很成功，可以考慮上市了），所以它適合中小型企業(yè)，對于超大型企業(yè)（以及在面試顯得追求高大上），我們還是要繼續(xù)思考更好的方案，請接著往下看。

下面開始講如何打造多臺機器組成的分布式發(fā)號器。

3.1 UUID

使用 UUID 算法或者 MongoDB 產(chǎn)生的 ObjectID。其實 MongoDB 的 ObjectID 也算是一種 UUID，這類算法，每臺機器可以獨立工作，天然是分布式的，但是這類算法產(chǎn)生的 ID 通常都很長，那短網(wǎng)址服務(wù)還有什么意義呢？所以這個方法不行。

3.2 多臺 MySQL 服務(wù)器

前面講了單臺 MySQL 作為發(fā)號服務(wù)器，那么自然可以擴展一下，比如用 8 臺 MySQL 服務(wù)器協(xié)同工作，第一臺 MySQL 初始值是 1，每次自增 8，第二臺 MySQL 初始值是 2，每次自增 8，一次類推。前面用一個 round-robin load balancer 擋著，每來一個長網(wǎng)址請求，由 round-robin balancer 隨機地將請求發(fā)給 10 臺 MySQL 中的任意一個，然后返回一個 ID。Flickr 用的就是這個方案，僅僅使用了兩臺 MySQL 服務(wù)器。這個方法僅有的一個缺點是，ID 是連續(xù)的，容易被爬蟲抓數(shù)據(jù)，爬蟲基本不用寫代碼，順著 ID 一個一個發(fā)請求就是了，太方便了（手動斜眼）。

3.3 分布式 ID 生成器

分布式的產(chǎn)生唯一的 ID，比如 Twitter 有個成熟的開源項目，就是專門做這個的，Twitter Snowflake 。Snowflake 的核心算法如下：

最高位不用，永遠為 0，其余三組 bit 占位均可浮動，看具體的業(yè)務(wù)需求而定。默認情況下 41bit 的時間戳可以支持該算法使用到 2082 年，10bit 的工作機器 id 可以支持 1023 臺機器，序列號支持 1 毫秒產(chǎn)生 4095 個自增序列 id。

Instagram 用了類似的方案，41 位表示時間戳，13 位表示 shard Id(一個 shard Id 對應(yīng)一臺 PostgreSQL 機器)，最低 10 位表示自增 ID，怎么樣，跟 Snowflake 的設(shè)計非常類似吧。這個方案用一個 PostgreSQL 集群代替了 Twitter Snowflake 集群，優(yōu)點是利用了現(xiàn)成的 PostgreSQL，容易懂、維護方便。

因此，正確答案：分布式發(fā)號器，F(xiàn)lick、Twitter Snowflake 和 Instagram 的方案都是不錯的選擇。

四、如何存儲

如果存儲短網(wǎng)址和長網(wǎng)址的對應(yīng)關(guān)系？以短網(wǎng)址為 primary key，長網(wǎng)址為 value，可以用傳統(tǒng)的關(guān)系數(shù)據(jù)庫存起來，例如 MySQL、PostgreSQL，也可以用任意一個分布式 KV 數(shù)據(jù)庫，例如 Redis、LevelDB。

如果你手癢想要手工設(shè)計這個存儲，那就是另一個話題了，你需要完整地造一個 KV 存儲引擎輪子。流行的 KV 存儲引擎有 LevelDB 和 RockDB，去讀它們的源碼吧！

五、301 還是 302 重定向

這也是一個有意思的問題。這個問題主要是考察你對 301 和 302 的理解，以及瀏覽器緩存機制的理解。

301 是永久重定向，302 是臨時重定向。短地址一經(jīng)生成就不會變化，所以用 301 是符合 HTTP 語義的。但是如果用了 301，Google、百度等搜索引擎，搜索的時候會直接展示真實地址，那我們就無法統(tǒng)計到短地址被點擊的次數(shù)了，也無法收集用戶的 Cookie、User Agent 等信息，這些信息可以用來做很多有意思的大數(shù)據(jù)分析，也是短網(wǎng)址服務(wù)商的主要盈利來源。

所以，正確答案是 302 重定向。

可以抓包看看新浪微博的短網(wǎng)址是怎么做的，使用 Chrome 瀏覽器，訪問這個 URL http://t.cn/RX2VxjI，是我事先發(fā)微博自動生成的短網(wǎng)址。來抓包看看返回的結(jié)果是啥，

可見新浪微博用的就是 302 臨時重定向。

六、預(yù)防攻擊

如果一些別有用心的黑客，短時間內(nèi)向 TinyURL 服務(wù)器發(fā)送大量的請求，會迅速耗光 ID，怎么辦呢？

首先，限制 IP 的單日請求總數(shù)，超過閾值則直接拒絕服務(wù)。

光限制 IP 的請求數(shù)還不夠，因為黑客一般手里有上百萬臺肉雞的，IP 地址大大的有，所以光限制 IP 作用不大。

可以用一臺 Redis 作為緩存服務(wù)器，存儲的不是 ID->長網(wǎng)址，而是 長網(wǎng)址->ID，僅存儲一天以內(nèi)的數(shù)據(jù)，用 LRU 機制進行淘汰。這樣，如果黑客大量發(fā)同一個長網(wǎng)址過來，直接從緩存服務(wù)器里返回短網(wǎng)址即可，他就無法耗光我們的 ID 了。