短網址服務設計
背景
短網址服務，用來將輸入的一個長網址轉換為一個短網址（比如附錄中的案例），當用戶請求這個短網址時，服務查詢出真實的url;
設計這么一個短網址服務，需要考慮哪些點？
數據結構
首先，需要考慮短網址應該如何存儲，使用一個key-value結構就可以；
key是生成的短網址，具有唯一性；
value為原始真實網址；
算法
計算短網址的算法可以很簡單，短網址與原始網址就只存在一個映射關系。
從1開始遞增來映射每一個網址；
1個位上可以使用26位字母+10個數字，即36進制； 而如果也用上大寫字母，就是62進制；
當然，在計算前需要通過value來查一遍，確定是否有重復鍵，如果有重復，直接返回；
那通過value如何快速定位是否有重復？再使用一個STL set來解決判重是個方法，有沒有更好的方式？
使用一個hash表或STL set保存所有的長url會消耗很大的空間；而如果不保存這個映射關系，用戶針對同一個長url的多次請求都返回的是不同的短url，體驗不好，也消耗短url資源；
好的做法：保存最近一段時間（比如6小時）的長url記錄，這段時間內，對同一長url的轉換，返回的是同一個短url；而過期之后再做轉換，返回另一個新的URL;
?
確定key的長度和value的長度
value長度可以設置在500，一般的網址不會超過這個數；
key: t.cn/**
key的長度決定了能夠支持多少個短網址；
如果是5位長度,能夠支持6000多萬的網址，6位長度就是21億;
數據容量
預估數據容量
會占用多大的空間；對于這類服務，基于效率考慮，一般是全內存操作；
如果單機能夠裝下，使用單機；
如果單機無法裝下，需要分片；分片策略可以根據key的遞增范圍來定，也可以根據取模來確定；
分片策略
根據key的遞增范圍分片
優點： 擴容簡單，超過1個服務器的容量后就增加一臺機器；
缺點：負載可能不均衡；一般后生成的短網址訪問比較頻繁，造成裝載早期短網址的服務器空閑；
根據key的取模來分片
優點：用戶的負載比較均衡；
缺點：難以擴容
取舍：可以先預估數據容量，確定使用的服務器數，使用第二種分片方法；當數據超出預估的容量，對于超出的key再使用第一種分片方法路由到新的服務器上（打補丁）
接口設計
確定用戶傳入的接口協議,用戶的輸入和輸出
并發讀寫和數據存儲
使用什么來存放這些key-value數據？
貌似一個STL hash map容器就可以，但map不是線程安全的，考慮加鎖？
如果實時性要求不高，可以使用AB兩塊內存操作，一塊內存線上讀，一塊線下寫，定期更新；
由于用戶輸入了長的網址之后，需要在終端上能夠顯示出被轉換的短網址，所有對寫的實時性也是有要求的；
要求實時，針對map可能得用上鎖，或者直接使用第三方內存產品，如redis，memcache等；
對redis的讀寫使用異步進一步提高并發效率；
網絡
對于用戶請求量，如果是千兆網能夠滿足，使用一個單線程事件循環來處理；（IO non-blocking + io multiplexing）
如果用戶請求更大，使用多個Reactor事件循環來處理，接入的reactor只負責事件的監聽，連接建立后，將用戶請求的處理轉到后續的計算reactor中處理；
查詢和更新邏輯簡單，可以直接在IO事件循環中處理（類似ngnix架構）
如果更新邏輯復雜，考慮后臺增加額外的進程/線程池，處理異步寫操作；
安全
（可選）考慮有惡意用戶，構造不存在的網址來連續觸發請求，以此來占滿短網址的id；
可對網址進行合法性校驗（直接訪問那個網址太耗時間，不太顯示）
對同一來源用戶限制請求數；
案例
http://t.im/ 這個短網址生成器上使用的就是36進制遞增來做的：
例如，多次輸入不同的長網址，得到的短網址：
http://t.im/vgu8
http://t.im/vgu9
http://t.im/vgu0
http://t.im/vgua
從這也可看出這個網站的并發并不大，我這幾次請求都是相隔幾秒的；
這個網站也沒有做特殊的網址校驗規則，比如輸入a.bb.ccc之類的網址，都為合法；
?
后記
以上是自己的一些想看，看過網上的一些文章后，發現有不少改進的地方：
1. 短url的存儲
設計時使用的是字母和數字的組合，使用36進制或62進制是為了讓url盡可能的短；在后臺存儲的時候，使用整型更為合適，
整型比較比字符串比較要高效，像redis等第三方產品對整型的查找都有專門的優化；后臺整型存儲，返回給用戶時，進行10進制到36進制的轉換即可；
?
2. 分布式發號器
自增的發號器是單點。如果流量大了，涉及到拆分，分成多個服務器來處理；發號器同樣可以擴容到多個，擴到2臺，分別發單雙號；第一臺發單號，第二天發雙號，不會重復；而擴容到10臺，則分別發0~9尾號的號；
?
Posted by: 大CC | 06NOV,2015
博客：blog.me115.com [訂閱]
Github：大CC
)
