什么是短URL
把URL縮短，用于為長URL創建更短的別名，我們稱這些縮短的別名為「短鏈接」
當用戶點擊這些短鏈接時，會被重定向到原始URL，短鏈接在顯示、打印、發送消息或發推時可以節省大量空間；此外，用戶也不太可能輸入錯誤的短url。
例如，如果我們通過縮短這個頁面:
可以得到:
縮短URL的大小接近實際URL的三分之一。
URL縮短用于優化跨設備的鏈接，跟蹤單個鏈接以分析受眾和活動表現，以及隱藏關聯的原始URL。
那么我們應該如何設計這樣的服務呢？像
需求和目標
首先我們應該從一開始就明確要求，考慮系統的具體范圍。
我們的網址縮短系統應符合一些規定。
功能需求:給定一個URL，我們的服務應該生成一個更短且唯一的URL別名，這被稱為短鏈接。這個鏈接應該足夠短，便于復制和粘貼到應用程序中。當用戶訪問短鏈接時，我們的服務應該將他們重定向到原始鏈接。用戶應該能夠選擇一個定制的短鏈接為他們的URL。鏈接將在一個默認時間間隔之后過期，用戶應該能夠指定過期時間。非功能性需求:系統應該是高可用的。因為如果我們的服務停止，所有的URL重定向都將開始失敗。URL重定向應該以最小的延遲實時發生。縮短的鏈接不應該是可猜測的(不可預測的)。擴展要求:分析；例如，發生了多少次重定向?我們的服務也應該可以被其他服務通過REST api訪問。容量估算與約束
我們的系統將會有大量的讀取，與新的URL縮短相比，將會有大量的重定向請求。讓我們假設讀和寫的比率是100:1。
流量估計:假設，我們每個月將有5億個新的URL縮短，以100:1的讀/寫比率，我們可以預期在同一時期有50B的重定向:
「100 * 500 => 50b」
每秒新增url縮短:
5億/(30天 * 24小時 * 3600秒) = ~200個url /s
考慮到100:1的讀寫比率，每秒url重定向為:
100 * 200 url /s = 20K/s
存儲估計：假設我們將每個URL縮短請求(以及相關的縮短鏈接)存儲5年，由于我們預計每個月有5億個新url，我們預計存儲的對象總數將是300億個:
5億 * 5年 * 12個月 = 300億
讓我們假設每個存儲的對象大約為500字節(這只是一個粗略的估計——我們將在后面深入研究)。我們將需要15TB的總存儲空間:
300億 * 500字節 = 15tb
帶寬估計：對于寫請求，因為我們預計每秒鐘有200個新的url，所以我們服務的總傳入數據將是每秒100KB:
200 * 500字節 = 100kb /s
對于讀請求，由于我們預計每秒鐘有20K個url重定向，我們服務的總輸出數據將是每秒10MB:
20K * 500字節 = ~ 10mb /s
內存估計：如果我們想緩存一些經常被訪問的熱門url，我們需要多少內存來存儲它們?如果我們遵循2-8原則，即20%的url產生80%的流量，我們希望緩存這20%的熱url。
由于我們每秒有2萬次請求，我們每天將收到17億次請求:
20K * 3600秒 * 24小時 = ~ 17億
為了緩存這些請求的20%，我們將需要170GB的內存。
0.2 * 17億 * 500字節 = ~170GB
這里需要注意的一點是，由于會有很多重復的請求(相同的URL)，因此，我們的實際內存使用將小于170GB。
高水平估計：假設每月新增5億url，讀寫比例為100:1，以下是我們服務的高水平估計總結:
系統api設計
一旦我們確定了需求，定義系統api總是一個好主意，明確聲明系統所期望的內容。
我們可以使用SOAP或REST api來公開服務的功能。下面是創建和刪除url的api的定義:
(, , =無，=無，=無)
參數:
():注冊帳戶的API開發人員密鑰。這將用于根據用戶分配的配額限制用戶；
():需要縮短的原始URL；
(): URL的可選自定義鍵。
():可選用于編碼的用戶名。
():可選的縮短URL的過期日期。
返回:()一個成功的插入返回縮短的URL；否則最新版短網址程序，它返回一個錯誤代碼。
( )
其中“”是表示要檢索的縮短URL的字符串，成功刪除將返回“URL已刪除”。
我們如何發現和防止濫用?惡意用戶可以通過消耗當前設計中的所有URL鍵來讓我們用盡？
為了防止濫用，我們可以通過限制用戶。每個可以被限制在一定數量的URL創建和重定向每一段時間(可以為每個用戶的鍵設置不同的持續時間)。
數據庫設計
在面試的早期階段定義DB模式將有助于理解不同組件之間的數據流，并在隨后指導數據分區。
關于我們將要存儲的數據的性質的幾點觀察:
我們需要存儲數十億條記錄。我們存儲的每個對象都很小(小于1K)。記錄之間沒有關系——除了存儲哪個用戶創建了URL之外。我們的服務是讀多的。數據庫結構
我們需要兩個表，一個用于存儲關于URL映射的信息，另一個用于存儲創建短鏈接的用戶數據：
我們應該使用什么樣的數據庫?因為我們預期存儲數十億行，而且我們不需要使用對象之間的關系——像這樣的NoSQL存儲，或Riak是更好的選擇。
NoSQL選擇也更容易擴展。詳情請參閱SQL vs NoSQL。
系統設計和算法
這里我們要解決的問題是，如何為給定的URL生成一個簡短且唯一的鍵。
在第1節的示例中，縮寫URL是“”。這個URL的最后七個字符是我們想要生成的短鍵，我們將在這里探索兩種解決方案:
a.編碼實際URL
我們可以計算給定URL的唯一哈希值(例如，MD5或等)，然后可以對散列進行編碼以顯示。
這種編碼可以是 ([a-z,0-9])或 ([a-z, a-z, 0-9])，如果我們加上' + '和' / '，我們可以使用編碼。
一個合理的問題是，短鍵的長度是多少?6個、8個還是10個字符?
使用編碼，一個6個字母長的鍵將產生64^6 = ~ 687億可用字符串，一個8個字母長的鍵將產生64^8 = ~281萬億可用字符串。
對于68.7B唯一的字符串，讓我們假設六個字母的鍵就足以滿足我們的系統。
如果我們使用MD5算法作為我們的哈希函數，它將產生一個128位的哈希值。在編碼之后，我們將得到一個超過21個字符的字符串(因為每個字符編碼了6位的哈希值)。
現在我們每個短鍵只有8個字符的空間，那么我們如何選擇我們的鍵呢?我們可以取前6(或8)個字母作為密鑰。這可能導致鍵重復，為了解決這個問題，我們可以從編碼字符串中選擇一些其他字符或交換一些字符。
我們的解決方案有哪些不同的問題?我們的編碼方案有以下幾個問題:
如果多個用戶輸入相同的URL，他們可以得到相同的縮短URL，這是不可接受的。如果部分URL是URL編碼的呢?例如，和%3Fid%除了URL編碼之外都是相同的。
問題的解決方法:
我們可以在每個輸入URL后面附加一個遞增的序列號，使其惟一，然后生成它的哈希值。
不過，我們不需要將這個序列號存儲在數據庫中，這種方法的可能問題可能是不斷增加的序列號。能溢出嗎?增加序列號也會影響服務的性能。
另一種解決方案是將用戶id(應該是唯一的)附加到輸入URL后面，但如果用戶沒有登錄，我們就必須要求用戶選擇惟一鍵。即使在這之后，如果有沖突，我們必須不斷生成一個鍵，直到我們得到一個唯一的。
b.離線生成密鑰
我們可以有一個獨立的密鑰生成服務(KGS)，它預先生成隨機的六個字母的字符串，并將它們存儲在數據庫中(我們稱之為Key - db)，每當我們想要縮短一個URL時，我們只需要獲取一個已經生成的鍵并使用它。
這種方法將使事情變得非常簡單和快速。我們不僅不用對URL進行編碼，而且不必擔心重復或沖突。KGS將確保插入key-DB的所有密鑰是唯一的。
并發性會導致問題嗎?一旦使用了一個鍵，就應該在數據庫中標記它，以確保它不會得到重用。如果有多個服務器同時讀取鍵值，我們可能會遇到這樣的情況：
兩個或多個服務器試圖從數據庫讀取相同的鍵值，我們如何解決這個并發問題?
服務器可以使用KGS讀取/標記數據庫中的密鑰，KGS可以使用兩個表來存儲鍵：
一個用于尚未使用的鍵，另一個用于所有已使用的鍵。只要KGS向其中一個服務器提供密鑰，它就可以將密鑰移動到使用的密鑰表中。KGS總是可以在內存中保存一些密鑰，以便在服務器需要時快速提供它們。
為了簡單起見，只要KGS將一些鍵加載到內存中，它就可以將它們移動到使用的鍵表中。這確保每個服務器獲得唯一的密鑰。如果KGS在將所有加載的鍵分配給某個服務器之前死亡，我們將浪費這些鍵——考慮到我們擁有的鍵的數量巨大最新版短網址程序，這是可以接受的。
KGS還必須確保不會向多個服務器提供相同的密鑰。為此，它必須同步(或鎖定)保存鍵的數據結構，然后從該結構中刪除鍵并將它們交給服務器。
key-DB的大小是多少?使用編碼，我們可以生成68.7B唯一的6個字母的密鑰。如果我們需要一個字節來存儲一個字母數字字符，我們可以將所有這些鍵存儲在：
6個字符(每個鍵) * 68.7B(唯一鍵) = 412 GB。
KGS不是單點故障嗎？是的。
為了解決這個問題，我們可以建立一個備用的KGS副本，當主服務器失效時，備用服務器可以接管生成并提供密鑰。
每個應用服務器可以緩存key-DB中的一些鍵嗎?是的，這肯定能加快速度。盡管在本例中，如果應用程序服務器在使用所有鍵之前死亡，我們最終將失去這些鍵。這是可以接受的，因為我們有68B唯一的六個字母的鑰匙。
如何執行鍵查找?我們可以在數據庫中查找鍵來獲得完整的URL。如果它出現在數據庫中，發出一個“HTTP 302重定向”狀態回傳給瀏覽器，在請求的“位置”字段中傳遞存儲的URL。如果該密鑰在我們的系統中不存在，則發出“HTTP 404 not Found”狀態或將用戶重定向回主頁。
我們應該對自定義別名施加大小限制嗎?我們的服務支持自定義別名。用戶可以選擇任何他們喜歡的“鍵”，但提供自定義別名不是強制性的。
然而，對自定義別名施加大小限制是合理的(而且通常是可取的)，以確保我們擁有一致的URL數據庫。讓我們假設用戶可以為每個客戶鍵指定最多16個字符(如上面的數據庫模式所示)：
數據分區和復制
為了擴展我們的數據庫，我們需要對它進行分區，以便它能夠存儲關于數十億個url的信息。我們需要提出一種分區方案，將我們的數據劃分并存儲到不同的DB服務器中。
a.基于范圍的分區
我們可以根據哈希鍵的首字母將url存儲在單獨的分區中。因此，我們將所有以字母“A”(和“A”)開頭的url保存在一個分區中，將那些以字母“B”開頭的url保存在另一個分區中，以此類推。這種方法稱為基于范圍的分區。
我們甚至可以將某些不太經常出現的字母組合到一個數據庫分區中。我們應該提出一個靜態分區方案，這樣我們就可以始終以一種可預測的方式存儲/查找URL。
這種方法的主要問題是：它可能導致不平衡的DB服務器。
例如，我們決定將所有以字母' E '開頭的url放入一個DB分區中，但是后來我們意識到我們有太多以字母' E '開頭的url。
b.基于哈希的分區
在這個方案中，我們獲取存儲對象的哈希值，然后根據哈希值計算要使用哪個分區。
在本例中，我們可以采用“鍵”或短鏈接的哈希值來確定存儲數據對象的分區。
我們的哈希函數將隨機地將url分配到不同的分區中(例如，我們的哈希函數總是可以將任何“鍵”映射到[1…256]之間的一個數字)，而這個數字將代表我們存儲對象的分區。
這種方法仍然會導致分區的重載，這可以通過使用一致的哈希來解決。
緩存
我們可以緩存經常被訪問的url。我們可以使用一些現成的解決方案，比如：
，它可以用它們各自的哈希值存儲完整的url。應用服務器在訪問后端存儲之前，可以快速檢查緩存是否具有所需的URL。
我們應該有多少緩存內存?我們可以從每天流量的20%開始，根據客戶的使用模式，我們可以調整需要多少緩存服務器。
如上所述，我們需要170GB的內存來緩存20%的日常流量。由于現在的服務器可以擁有256GB的內存，我們可以很容易地將所有緩存放入一臺機器中。或者，我們可以使用幾個較小的服務器來存儲所有這些熱url。
哪種cache逐出策略最適合我們的需求?當緩存是滿的，我們想用一個更新/更熱的URL替換一個鏈接，我們應該如何選擇?最近最少使用(Least Used, LRU)對于我們的系統來說是一個合理的策略。
在此策略下，我們首先丟棄最近最少使用的URL。我們可以使用一個鏈接哈希圖或類似的數據結構來存儲我們的url和哈希表，它也會跟蹤最近被訪問的url。
為了進一步提高效率，我們可以復制緩存服務器來在它們之間分配負載。
如何更新每個緩存副本?每當緩存丟失時，我們的服務器就會碰到后端數據庫，每當發生這種情況時，我們可以更新緩存并將新條目傳遞到所有緩存副本，每個副本都可以通過添加新條目來更新其緩存。
如果副本已經擁有該條目，則可以忽略它。
負載均衡
我們可以在系統的三個地方添加一個負載均衡層:
客戶端和應用服務器之間在應用程序服務器和數據庫服務器之間應用服務器和緩存服務器之間
最初，我們可以使用簡單的輪詢方法，在后端服務器之間平均分配傳入的請求。這個LB實現起來很簡單，而且不引入任何開銷。這種方法的另一個好處是，如果服務器死亡，LB將把它從輪換中取出，并停止向它發送任何流量。
Round Robin LB的一個問題是我們沒有考慮服務器負載。如果服務器負載過重或運行緩慢，LB將不會停止向該服務器發送新請求。
要處理這個問題，可以放置一個更智能的LB解決方案，它可以周期性地查詢后端服務器的負載，并據此調整流量。
清除或DB清理
條目應該永遠存在還是應該被清除?如果達到了用戶指定的過期時間，該鏈接會發生什么?
如果我們選擇主動搜索過期鏈接并刪除它們，這將給我們的數據庫帶來很大的壓力。相反，我們可以慢慢地刪除過期的鏈接，并進行惰性清理。我們的服務將確保只有過期的鏈接將被刪除，盡管一些過期的鏈接可以存活更長時間，但永遠不會返回給用戶。
當用戶試圖訪問一個過期的鏈接時，我們可以刪除該鏈接并返回一個錯誤給用戶。一個單獨的清理服務可以定期運行，從我們的存儲和緩存中刪除過期的鏈接。此服務應該是非常輕量級的，并且只能在預期用戶流量較低時調度運行。
我們可以為每個鏈接設置一個默認過期時間(例如，兩年)。
在移除一個過期的鏈接后，我們可以把key放回key- db中以進行重用。
我們是否應該刪除一段時間內(比如6個月)未被訪問的鏈接?這可能很棘手。由于存儲變得越來越便宜，我們可以決定永遠保持鏈接。
特殊場景考慮
短URL被使用了多少次，用戶位置是什么，等等?我們如何存儲這些統計數據?如果它是每個視圖上更新的DB行的一部分，當一個流行的URL被大量并發請求攻擊時會發生什么?
一些值得跟蹤的統計數據:訪問者的國家，訪問的日期和時間，點擊的網頁，瀏覽器，或頁面被訪問的平臺。
安全與權限
用戶是否可以創建私有URL或允許特定的一組用戶訪問URL?
我們可以將權限級別(公有/私有)與每個URL存儲在數據庫中。我們還可以創建一個單獨的表來存儲具有查看特定URL權限的。如果用戶沒有權限并試圖訪問URL，我們可以返回一個錯誤(HTTP 401)。
假設我們將數據存儲在一個像這樣的NoSQL寬列數據庫中，表存儲權限的鍵將是“Hash”(或KGS生成的“鍵”)。這些列將存儲那些有權限查看URL的用戶的。