短網址服務設計
背景
短網址服務，用來将輸入的一個長網址轉換為一個短網址（比如附錄中的案例），當使用者請求這個短網址時，服務查詢出真實的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