短鏈系統(tǒng)設(shè)計(jì)（design tiny url）

如脈脈，不會(huì)縱容你發(fā)太長(zhǎng)的網(wǎng)址，會(huì)給你轉(zhuǎn)成短鏈。

1.Scenario 場(chǎng)景

根據(jù)一個(gè) long url 生成一個(gè)short url。

【資料圖】

如 http://www.javaedge.com => http://bit.ly/1ULoQB6

根據(jù) short url 還原 long url，并跳轉(zhuǎn)：

需和面試官確認(rèn)的問題：

long url和short url必須一一對(duì)應(yīng)嗎？

Short url長(zhǎng)時(shí)間沒人用，需要釋放嗎？

1.1 QPS 分析問日活，如微博100M推算產(chǎn)生一條 tiny url 的 qps

假設(shè)每個(gè)用戶平均每天 0.1（發(fā)10 條，有一條有鏈接） 條帶 URL 的微博

平均寫 QPS = 100M * 0.1 / 86400 = 100

峰值寫 qps = 100 * 2 = 200

推算點(diǎn)擊一條tiny url的 qps

假設(shè)每個(gè)用戶平均點(diǎn) 1 個(gè)tiny url

平均寫 QPS = 100M * 1 / 86400 = 1k

峰值讀 qps = 1k * 2 = 2k

deduce 每天產(chǎn)生的新 URL 所占存儲(chǔ)

100M * 0.1 = 10M 條

每條 URL 長(zhǎng)度平均按 100 算，共 1G

1T 硬盤能用 3 年

由2、3 分析可知，并不需要分布式或者 sharding，支持 2k QPS，一臺(tái) SSD MySQL 即可。

2.Service 服務(wù) - 邏輯塊聚類與接口設(shè)計(jì)

該系統(tǒng)其實(shí)很簡(jiǎn)單，只需要有一個(gè) service即可：URL Service。由于 tiny url只有一個(gè) UrlService：

本身其實(shí)就是個(gè)小的獨(dú)立應(yīng)用也無(wú)需關(guān)心其他任何業(yè)務(wù)功能

方法設(shè)計(jì)：

UrlService.encode(long_url)：編碼方法

UrlService.decode(long_url)：解碼方法

訪問端口設(shè)計(jì)，當(dāng)前有如下兩種常用主流風(fēng)格：

GET /REST 風(fēng)格Return a http redirect resonseREST 風(fēng)格Return a http redirect resonsePOST /data/shorten（不太推薦，不符合 REST 設(shè)計(jì)風(fēng)格，但也有人在用） returh a short url

那么，你們公司的短鏈系統(tǒng)是選擇哪種服務(wù)設(shè)計(jì)呢？

3.Storage 數(shù)據(jù)存?。ㄗ钅荏w現(xiàn)實(shí)踐經(jīng)驗(yàn)）select 選存儲(chǔ)結(jié)構(gòu)scheme 細(xì)化數(shù)據(jù)表3.1 SQL V.S NoSQL

需要事務(wù)嗎？No，nosql+1

需要豐富的 sql query 嗎？no，nosql+1

想偷懶嗎?tiny url需要寫的代碼不復(fù)雜，nosql+1

qps高嗎？2k，不高。sql+1

scalability 要求多高？存儲(chǔ)和 qps 都不高，單機(jī)都能搞定。sql+1

- sql 需要自己寫代碼來 scale- nosql，這些都幫你做了

是否需要 sequential ID？取決于你的算法

sql 提供 auto_increment 的 sequencetial ID，即 1,2,3nosql 的 ID 不是 sequential3.2 算法

long ur 轉(zhuǎn)成一個(gè) 6 位的 short url。給出一個(gè)長(zhǎng)網(wǎng)址，返回一個(gè)短網(wǎng)址。

實(shí)現(xiàn)兩個(gè)方法：

longToShort(url)?把一個(gè)長(zhǎng)網(wǎng)址轉(zhuǎn)換成一個(gè)以http://tiny.url/開頭的短網(wǎng)址shortToLong(url)把一個(gè)短網(wǎng)址轉(zhuǎn)換成一個(gè)長(zhǎng)網(wǎng)址shortToLong(url)把一個(gè)短網(wǎng)址轉(zhuǎn)換成一個(gè)長(zhǎng)網(wǎng)址

標(biāo)準(zhǔn)：

短網(wǎng)址的key的長(zhǎng)度應(yīng)為6 （不算域名和反斜杠）?？捎米址挥衃a-zA-Z0-9]?. 比如:abcD9E[a-zA-Z0-9]?. 比如:abcD9E任意兩個(gè)長(zhǎng)的url不會(huì)對(duì)應(yīng)成同一個(gè)短url，反之亦然。

用兩個(gè)哈希表：

一個(gè)是短網(wǎng)址映射到長(zhǎng)網(wǎng)址一個(gè)是長(zhǎng)網(wǎng)址映射到短網(wǎng)址

短網(wǎng)址是固定的格式: "http://tiny.url/" + 6個(gè)字符, 字符可任意。

為避免重復(fù), 我們可以按照字典序依次使用, 或者在隨機(jī)生成的基礎(chǔ)上用一個(gè)集合來記錄是否使用過。

使用哈希函數(shù)（不可行）

如取 long url的 MD5 的最后 6 位：

快難以設(shè)計(jì)一個(gè)無(wú)哈希沖突的哈希算法

隨機(jī)生成 shortURL+DB去重

隨機(jī)取一個(gè) 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; }}

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單

缺點(diǎn)：生成短鏈接的速度，隨著短鏈接越多而越慢

關(guān)系型數(shù)據(jù)庫(kù)表：只需Short key和 long url兩列，并分別建立索引

也可使用 nosql，但需要建立兩張表：

根據(jù) long 查詢 short key=longurl 列=shorturl value=null or timestamp根據(jù) short 查詢 long key=shorturl 列=longurl value=null or timestamp

進(jìn)制轉(zhuǎn)換 Base32(微博實(shí)現(xiàn)方案)

Base62：

將 6 位 short url 看做一個(gè) 62 進(jìn)制數(shù)（0-9,a-z,A-Z）每個(gè) short url 對(duì)應(yīng)到一個(gè)整數(shù)該整數(shù)對(duì)應(yīng) DB 表的主鍵

6 位可表示的不同 URL：

5 位 = 62^5=0.9B= 9億6 位 = 62^6=57B= 570億7 位 = 62^7=3.5T= 35000億

優(yōu)點(diǎn)：效率高

缺點(diǎn)：強(qiáng)依賴于全局的自增 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); }}

因?yàn)橐玫阶栽?id，所以只能用關(guān)系型 DB 表：

id主鍵、long url（索引）

4.Scale

如何提高響應(yīng)速度，和直接打開原鏈接一樣的效率。

明確，這是個(gè)讀多寫少業(yè)務(wù)。

4.1 緩存提速（Cache Aside）

緩存需存儲(chǔ)兩類數(shù)據(jù)：

long2short（生成新 short url 需要）short2long（查詢 short url 時(shí)需要）4.2 CDN

利用地理位置信息提速。

優(yōu)化服務(wù)器訪問速度：

不同地區(qū)，使用通不同 web 服務(wù)器通過 dns 解析不同地區(qū)用戶到不同服務(wù)器

優(yōu)化數(shù)據(jù)訪問速度

使用中心化的 MySQL+分布式的 Redis一個(gè) MySQL 配多個(gè) Redis，Redis 跨地區(qū)分布4.3 何時(shí)需要多臺(tái) DB 服務(wù)器

cache 資源不夠或命中率低

寫操作過多

越來越多請(qǐng)求無(wú)法通過 cache 滿足

多臺(tái)DB服務(wù)器可以優(yōu)化什么?

?解決存不下：存儲(chǔ)

?解決忙不過：qps

那么 tiny url 的主要問題是啥？存儲(chǔ)是沒問題的，重點(diǎn)是 qps。那么，如何 sharding 呢?

垂直拆分：將多張表分別分配給多臺(tái)機(jī)器。對(duì)此不適用，只有兩列，無(wú)法再拆分。

橫向拆分：

若id、shortURL 做分片鍵：

?long2short 查詢時(shí)，只能廣播給 N 臺(tái) db 都去查詢

?為何要查 long2short？避免重復(fù)創(chuàng)建呀

?若不需要避免重復(fù)創(chuàng)建，則這樣可行

用 long url 做分片鍵：

short2long 查詢時(shí)，只能廣播給 N 臺(tái) DB 查詢。

4.3.1 分片鍵選擇

若一個(gè) long 可對(duì)應(yīng)多個(gè) short

?使用 cache 緩存所有 long2short

?在為一個(gè) long url 創(chuàng)建 short url 時(shí)，若 cache miss，則創(chuàng)建新 short

若一個(gè) long 只能對(duì)應(yīng)一個(gè) short

?若使用隨機(jī)生成算法

?兩張表，一張存儲(chǔ) long2short，一張存儲(chǔ)short2long

?每個(gè)映射關(guān)系存兩份，則能同時(shí)支持 long2short short2long 查詢

?若使用 base62 進(jìn)制轉(zhuǎn)換法

?有個(gè)嚴(yán)重問題，多臺(tái)機(jī)器之間如何維護(hù)一個(gè)全局自增的 id？

?一般關(guān)系型DB只支持在一臺(tái)機(jī)器上實(shí)現(xiàn)這臺(tái)機(jī)器上全局自增的 id

4.4 全局自增 id

4.4.1 專用一臺(tái) DB 做自增服務(wù)

該 DB不存儲(chǔ)真實(shí)數(shù)據(jù)，也不負(fù)責(zé)其他查詢。

為避免單點(diǎn)故障，可能需要多臺(tái) 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，則現(xiàn)在的 short key 是

hash(long_url) % 62 + AB1234若 hash(long_url)%62=0，那就是0AB1234

這樣，就能同時(shí)通過 short、long 得到分片鍵。

缺點(diǎn)：DB 的機(jī)器數(shù)目不能超過 62。

所以，最后最佳架構(gòu)：

4.6 還能優(yōu)化嗎？

web server 和 database 之間的通信。

中心化的服務(wù)器集群和跨地域的 web server 之間通信較慢：如中國(guó)的 Server 需訪問美國(guó)的 DB。

為何不讓中國(guó)的 Server 訪問中國(guó)的 DB 呢?

若數(shù)據(jù)重復(fù)寫到中國(guó) DB，如何解決一致性問題？很難解決！

思考用戶的習(xí)慣：

中國(guó)用戶訪問時(shí)，會(huì)被 DNS 分配中國(guó)的服務(wù)器中國(guó)用戶訪問的網(wǎng)站一般都是中國(guó)的網(wǎng)站所以可按網(wǎng)站的地域信息來 sharding如何獲得網(wǎng)站的地域信息？只需將用戶常訪問的網(wǎng)站匯總在一張表。中國(guó)用戶訪問美國(guó)網(wǎng)站咋辦?就中國(guó) server 訪問美國(guó) db，也不會(huì)慢太多中訪中是用戶主流，優(yōu)化系統(tǒng)就是針對(duì)主要需求

于是，得到最終架構(gòu)：

還可以維護(hù)一份域名白名單，訪問對(duì)應(yīng)地域的 DB。

5.用戶自定義短鏈接

實(shí)現(xiàn)一個(gè)顧客短網(wǎng)址，使得顧客能創(chuàng)立他們自己的短網(wǎng)址。即你需要在前文基礎(chǔ)上再實(shí)現(xiàn)一個(gè)createCustom。createCustom。

需實(shí)現(xiàn)三個(gè)方法：

long2Short(url)把一個(gè)長(zhǎng)網(wǎng)址轉(zhuǎn)換成一個(gè)以http://tiny.url/開頭的短網(wǎng)址long2Short(url)把一個(gè)長(zhǎng)網(wǎng)址轉(zhuǎn)換成一個(gè)以http://tiny.url/開頭的短網(wǎng)址short2Long(url)把一個(gè)短網(wǎng)址轉(zhuǎn)換成一個(gè)長(zhǎng)網(wǎng)址short2Long(url)把一個(gè)短網(wǎng)址轉(zhuǎn)換成一個(gè)長(zhǎng)網(wǎng)址createCustom(url, key)設(shè)定一個(gè)長(zhǎng)網(wǎng)址的短網(wǎng)址為http://tiny.url/+keycreateCustom(url, key)設(shè)定一個(gè)長(zhǎng)網(wǎng)址的短網(wǎng)址為http://tiny.url/+key

注意：

long2Short生成的短網(wǎng)址的key的長(zhǎng)度應(yīng)該等于6 （不算域名和反斜杠）。可以使用的字符只有[a-zA-Z0-9]。如:abcD9Elong2Short生成的短網(wǎng)址的key的長(zhǎng)度應(yīng)該等于6 （不算域名和反斜杠）?？梢允褂玫淖址挥衃a-zA-Z0-9]。如:abcD9E任意兩個(gè)長(zhǎng)的url不會(huì)對(duì)應(yīng)成同一個(gè)短url，反之亦然如果createCustom不能完成用戶期望的設(shè)定, 那么應(yīng)該返回"error", 反之如果成功將長(zhǎng)網(wǎng)址與短網(wǎng)址對(duì)應(yīng)，應(yīng)該返回這個(gè)短網(wǎng)址createCustom不能完成用戶期望的設(shè)定, 那么應(yīng)該返回"error", 反之如果成功將長(zhǎng)網(wǎng)址與短網(wǎng)址對(duì)應(yīng)，應(yīng)該返回這個(gè)短網(wǎng)址5.1 基于 Base62

在URLTable里，直接新增一列custom_url記錄對(duì)應(yīng)的custom url是否可行？

不可行！對(duì)于大部分?jǐn)?shù)據(jù)，該列其實(shí)都為空，就會(huì)浪費(fèi)存儲(chǔ)空間。

新增一個(gè)表，存儲(chǔ)自定義 URL：CustomURLTable。

創(chuàng)建自定義短鏈接：在 CustomURLTable 中查詢和插入

根據(jù)長(zhǎng)鏈接創(chuàng)建普通短鏈接：

先查詢CustomURLTable是否存在再在URLTable查詢和插入

同前文一樣，用兩個(gè)哈希表處理長(zhǎng)網(wǎng)址和短網(wǎng)址之間的相互映射關(guān)系。需額外處理的是用戶設(shè)定的網(wǎng)址與已有沖突時(shí)，需返回 "error"。注意：若用戶設(shè)定的和已有恰好相同，則同樣應(yīng)該返回短網(wǎng)址。

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 基于隨機(jī)生成算法

無(wú)需做任何改動(dòng)，直接把custom url當(dāng)short url創(chuàng)建即可！

參考：https://www.zhihu.com/question/29270034

標(biāo)簽：