短鏈系統設計（design tiny url）
如脈脈，不會縱容你發太長的網址，會給你轉成短鏈。
1.Scenario 場景
根據一個 long url 生成一個short url。
(資料圖)
如 http://www.javaedge.com => http://bit.ly/1ULoQB6
根據 short url 還原 long url，并跳轉：
需和面試官確認的問題：
long url和short url必須一一對應嗎？
Short url長時間沒人用，需要釋放嗎？
1.1 QPS 分析問日活，如微博100M推算產生一條 tiny url 的 qps
假設每個用戶平均每天 0.1（發10 條，有一條有鏈接） 條帶 URL 的微博
平均寫 QPS = 100M * 0.1 / 86400 = 100
峰值寫 qps = 100 * 2 = 200
推算點擊一條tiny url的 qps
假設每個用戶平均點 1 個tiny url
平均寫 QPS = 100M * 1 / 86400 = 1k
峰值讀 qps = 1k * 2 = 2k
deduce 每天產生的新 URL 所占存儲
100M * 0.1 = 10M 條
每條 URL 長度平均按 100 算，共 1G
1T 硬盤能用 3 年
由2、3 分析可知，并不需要分布式或者 sharding，支持 2k QPS，一臺 SSD MySQL 即可。
2.Service 服務 - 邏輯塊聚類與接口設計
該系統其實很簡單，只需要有一個 service即可：URL Service。由于 tiny url只有一個 UrlService：
本身其實就是個小的獨立應用也無需關心其他任何業務功能
方法設計：
UrlService.encode(long_url)：編碼方法
UrlService.decode(long_url)：解碼方法
訪問端口設計，當前有如下兩種常用主流風格：
GET /REST 風格Return a http redirect resonseREST 風格Return a http redirect resonsePOST /data/shorten（不太推薦，不符合 REST 設計風格，但也有人在用） returh a short url
那么，你們公司的短鏈系統是選擇哪種服務設計呢？
3.Storage 數據存?。ㄗ钅荏w現實踐經驗）select 選存儲結構scheme 細化數據表3.1 SQL V.S NoSQL
需要事務嗎？No，nosql+1
需要豐富的 sql query 嗎？no，nosql+1
想偷懶嗎?tiny url需要寫的代碼不復雜，nosql+1
qps高嗎？2k，不高。sql+1
scalability 要求多高？存儲和 qps 都不高，單機都能搞定。sql+1
- sql 需要自己寫代碼來 scale- nosql，這些都幫你做了
是否需要 sequential ID？取決于你的算法
sql 提供 auto_increment 的 sequencetial ID，即 1,2,3nosql 的 ID 不是 sequential3.2 算法
long ur 轉成一個 6 位的 short url。給出一個長網址，返回一個短網址。
實現兩個方法：
longToShort(url)?把一個長網址轉換成一個以http://tiny.url/開頭的短網址shortToLong(url)把一個短網址轉換成一個長網址shortToLong(url)把一個短網址轉換成一個長網址
標準：
短網址的key的長度應為6 （不算域名和反斜杠）?？捎米址挥衃a-zA-Z0-9]?. 比如:abcD9E[a-zA-Z0-9]?. 比如:abcD9E任意兩個長的url不會對應成同一個短url，反之亦然。
用兩個哈希表：
一個是短網址映射到長網址一個是長網址映射到短網址
短網址是固定的格式: "http://tiny.url/" + 6個字符, 字符可任意。
為避免重復, 我們可以按照字典序依次使用, 或者在隨機生成的基礎上用一個集合來記錄是否使用過。
使用哈希函數（不可行）
如取 long url的 MD5 的最后 6 位：
快難以設計一個無哈希沖突的哈希算法
隨機生成 shortURL+DB去重
隨機取一個 6 位的 shortURL，若沒使用過，就綁定到改 long url。
public String long2Short(String url) { while(true) { String shortURL = randomShortURL(); if (!databse.filter(shortURL=shortURL).exists()) { database.create(shortURL=shortURL, longURL=url); return shortURL; } } }public class TinyUrl { public TinyUrl() { long2Short = new HashMap(); short2Long = new HashMap(); } /** * @param url a long url * @return a short url starts with http://tiny.url/ */ public String longToShort(String url) { if (long2Short.containsKey(url)) { return long2Short.get(url); } while (true) { String shortURL = generateShortURL(); if (!short2Long.containsKey(shortURL)) { short2Long.put(shortURL, url); long2Short.put(url, shortURL); return shortURL; } } } /** * @param url a short url starts with http://tiny.url/ * @return a long url */ public String shortToLong(String url) { if (!short2Long.containsKey(url)) { return null; } return short2Long.get(url); } private String generateShortURL() { String allowedChars = "0123456789" + "abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; Random rand = new Random(); String shortURL = "http://tiny.url/"; for (int i = 0; i < 6; i++) { int index = rand.nextInt(62); shortURL += allowedChars.charAt(index); } return shortURL; }}優點：實現簡單
缺點：生成短鏈接的速度，隨著短鏈接越多而越慢
關系型數據庫表：只需Short key和 long url兩列，并分別建立索引
也可使用 nosql，但需要建立兩張表：
根據 long 查詢 short key=longurl 列=shorturl value=null or timestamp根據 short 查詢 long key=shorturl 列=longurl value=null or timestamp進制轉換 Base32(微博實現方案)
Base62：
將 6 位 short url 看做一個 62 進制數（0-9,a-z,A-Z）每個 short url 對應到一個整數該整數對應 DB 表的主鍵6 位可表示的不同 URL：
5 位 = 62^5=0.9B= 9億6 位 = 62^6=57B= 570億7 位 = 62^7=3.5T= 35000億優點：效率高
缺點：強依賴于全局的自增 id
public class TinyUrl { public static int GLOBAL_ID = 0; private HashMap id2url = new HashMap(); private HashMap url2id = new HashMap(); private String getShortKey(String url) { return url.substring("http://tiny.url/".length()); } private int toBase62(char c) { if (c >= "0" && c <= "9") { return c - "0"; } if (c >= "a" && c <= "z") { return c - "a" + 10; } return c - "A" + 36; } private int shortKeytoID(String short_key) { int id = 0; for (int i = 0; i < short_key.length(); ++i) { id = id * 62 + toBase62(short_key.charAt(i)); } return id; } private String idToShortKey(int id) { String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; String short_url = ""; while (id > 0) { short_url = chars.charAt(id % 62) + short_url; id = id / 62; } while (short_url.length() < 6) { short_url = "0" + short_url; } return short_url; } /** * @param url a long url * @return a short url starts with http://tiny.url/ */ public String longToShort(String url) { if (url2id.containsKey(url)) { return "http://tiny.url/" + idToShortKey(url2id.get(url)); } GLOBAL_ID++; url2id.put(url, GLOBAL_ID); id2url.put(GLOBAL_ID, url); return "http://tiny.url/" + idToShortKey(GLOBAL_ID); } /** * @param url a short url starts with http://tiny.url/ * @return a long url */ public String shortToLong(String url) { String short_key = getShortKey(url); int id = shortKeytoID(short_key); return id2url.get(id); }}因為要用到自增 id，所以只能用關系型 DB 表：
id主鍵、long url（索引）
4.Scale如何提高響應速度，和直接打開原鏈接一樣的效率。
明確，這是個讀多寫少業務。
4.1 緩存提速（Cache Aside）緩存需存儲兩類數據：
long2short（生成新 short url 需要）short2long（查詢 short url 時需要）4.2 CDN利用地理位置信息提速。
優化服務器訪問速度：
不同地區，使用通不同 web 服務器通過 dns 解析不同地區用戶到不同服務器優化數據訪問速度
使用中心化的 MySQL+分布式的 Redis一個 MySQL 配多個 Redis，Redis 跨地區分布4.3 何時需要多臺 DB 服務器cache 資源不夠或命中率低
寫操作過多
越來越多請求無法通過 cache 滿足
多臺DB服務器可以優化什么?
?解決存不下：存儲
?解決忙不過：qps
那么 tiny url 的主要問題是啥？存儲是沒問題的，重點是 qps。那么，如何 sharding 呢?
垂直拆分：將多張表分別分配給多臺機器。對此不適用，只有兩列，無法再拆分。
橫向拆分：
若id、shortURL 做分片鍵：
?long2short 查詢時，只能廣播給 N 臺 db 都去查詢
?為何要查 long2short？避免重復創建呀
?若不需要避免重復創建，則這樣可行
用 long url 做分片鍵：
short2long 查詢時，只能廣播給 N 臺 DB 查詢。
4.3.1 分片鍵選擇
若一個 long 可對應多個 short
?使用 cache 緩存所有 long2short
?在為一個 long url 創建 short url 時，若 cache miss，則創建新 short
若一個 long 只能對應一個 short
?若使用隨機生成算法
?兩張表，一張存儲 long2short，一張存儲short2long
?每個映射關系存兩份，則能同時支持 long2short short2long 查詢
?若使用 base62 進制轉換法
?有個嚴重問題，多臺機器之間如何維護一個全局自增的 id？
?一般關系型DB只支持在一臺機器上實現這臺機器上全局自增的 id
4.4 全局自增 id4.4.1 專用一臺 DB 做自增服務
該 DB不存儲真實數據，也不負責其他查詢。
為避免單點故障，可能需要多臺 DB。
4.4.2 使用 zk
但使用全局自增 id 不是解決 tiny url最佳方案。Generating a Distributed Sequence Number
4.5 基于 base62 的分片策略Hash(long_url)%62作為分片鍵
并將 hash(long_url)%62直接放到 short url
若原來的 short key 是 AB1234，則現在的 short key 是
hash(long_url) % 62 + AB1234若 hash(long_url)%62=0，那就是0AB1234這樣，就能同時通過 short、long 得到分片鍵。
缺點：DB 的機器數目不能超過 62。
所以，最后最佳架構：
4.6 還能優化嗎？web server 和 database 之間的通信。
中心化的服務器集群和跨地域的 web server 之間通信較慢：如中國的 Server 需訪問美國的 DB。
為何不讓中國的 Server 訪問中國的 DB 呢?
若數據重復寫到中國 DB，如何解決一致性問題？很難解決！
思考用戶的習慣：
中國用戶訪問時，會被 DNS 分配中國的服務器中國用戶訪問的網站一般都是中國的網站所以可按網站的地域信息來 sharding如何獲得網站的地域信息？只需將用戶常訪問的網站匯總在一張表。中國用戶訪問美國網站咋辦?就中國 server 訪問美國 db，也不會慢太多中訪中是用戶主流，優化系統就是針對主要需求于是，得到最終架構：
還可以維護一份域名白名單，訪問對應地域的 DB。
5.用戶自定義短鏈接實現一個顧客短網址，使得顧客能創立他們自己的短網址。即你需要在前文基礎上再實現一個createCustom。createCustom。
需實現三個方法：
long2Short(url)把一個長網址轉換成一個以http://tiny.url/開頭的短網址long2Short(url)把一個長網址轉換成一個以http://tiny.url/開頭的短網址short2Long(url)把一個短網址轉換成一個長網址short2Long(url)把一個短網址轉換成一個長網址createCustom(url, key)設定一個長網址的短網址為http://tiny.url/+keycreateCustom(url, key)設定一個長網址的短網址為http://tiny.url/+key注意：
long2Short生成的短網址的key的長度應該等于6 （不算域名和反斜杠）?？梢允褂玫淖址挥衃a-zA-Z0-9]。如:abcD9Elong2Short生成的短網址的key的長度應該等于6 （不算域名和反斜杠）?？梢允褂玫淖址挥衃a-zA-Z0-9]。如:abcD9E任意兩個長的url不會對應成同一個短url，反之亦然如果createCustom不能完成用戶期望的設定, 那么應該返回"error", 反之如果成功將長網址與短網址對應，應該返回這個短網址createCustom不能完成用戶期望的設定, 那么應該返回"error", 反之如果成功將長網址與短網址對應，應該返回這個短網址5.1 基于 Base62在URLTable里，直接新增一列custom_url記錄對應的custom url是否可行？
不可行！對于大部分數據，該列其實都為空，就會浪費存儲空間。
新增一個表，存儲自定義 URL：CustomURLTable。
創建自定義短鏈接：在 CustomURLTable 中查詢和插入
根據長鏈接創建普通短鏈接：
先查詢CustomURLTable是否存在再在URLTable查詢和插入同前文一樣，用兩個哈希表處理長網址和短網址之間的相互映射關系。需額外處理的是用戶設定的網址與已有沖突時，需返回 "error"。注意：若用戶設定的和已有恰好相同，則同樣應該返回短網址。
public class TinyUrl2 { private HashMap s2l = new HashMap(); private HashMap l2s = new HashMap(); private int cnt = 0; private final StringBuffer tinyUrl = new StringBuffer("http://tiny.url/"); private final String charset = "qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM"; private String newShortUrl() { StringBuffer res = new StringBuffer(); for (int i = 0, j = cnt; i < 6; i++, j /= 62) res.append(charset.charAt(j % 62)); cnt++; return tinyUrl + res.toString(); } /* * @param long_url: a long url * @param key: a short key * @return: a short url starts with http://tiny.url/ */ public String createCustom(String long_url, String key) { String short_url = tinyUrl + key; if (l2s.containsKey(long_url)) { if (l2s.get(long_url).equals(short_url)) return short_url; else return "error"; } if (s2l.containsKey(short_url)) return "error"; l2s.put(long_url, short_url); s2l.put(short_url, long_url); return short_url; } /* * @param long_url: a long url * @return: a short url starts with http://tiny.url/ */ public String longToShort(String long_url) { if (l2s.containsKey(long_url)) return l2s.get(long_url); String short_url = newShortUrl(); l2s.put(long_url, short_url); s2l.put(short_url, long_url); return short_url; } /* * @param short_url: a short url starts with http://tiny.url/ * @return: a long url */ public String shortToLong(String short_url) { if (s2l.containsKey(short_url)) return s2l.get(short_url); return "error"; }}5.2 基于隨機生成算法無需做任何改動，直接把custom url當short url創建即可！
參考：https://www.zhihu.com/question/29270034
關鍵詞：
系統設計
可以使用
實踐經驗
一般都是
