阿里面試:如何設(shè)計(jì)與實(shí)現(xiàn)短URL服務(wù)?

??Java大聯(lián)盟

? 幫助萬千Java學(xué)習(xí)者持續(xù)成長(zhǎng)

作者｜呼延十

juejin.im/post/6844903873950269454

B 站搜索：楠哥教你學(xué)Java

獲取更多優(yōu)質(zhì)視頻教程

想必大家也經(jīng)常收到垃圾短信吧...短信中的鏈接一般都是短鏈接,類似于下圖這樣:

為什么這里面的URL都是短的呢?有什么好處呢?怎么做到的呢?

短URL的好處

1、短信和許多平臺(tái)(微博)有字?jǐn)?shù)限制?，太長(zhǎng)的鏈接加進(jìn)去都沒有辦法寫正文了。

2、好看，比起一大堆不知所以的參數(shù),短鏈接更加簡(jiǎn)潔友好。

3、方便做一些統(tǒng)計(jì)，你點(diǎn)了鏈接會(huì)有人記錄然后分析的。

4、安全，不暴露訪問參數(shù)。

這就是為什么我們現(xiàn)在收到的垃圾短信大多數(shù)都是短URL的原因了，那么短URL是怎么做到的呢?

短URL基礎(chǔ)原理

短URL從生成到使用分為以下幾步.

1、有一個(gè)服務(wù),將要發(fā)送給你的長(zhǎng)URL對(duì)應(yīng)到一個(gè)短URL上，例如www.baidu.com -> www.t.cn/1

2、把短URL拼接到短信等的內(nèi)容上發(fā)送。

3、用戶點(diǎn)擊短URL,瀏覽器用301/302進(jìn)行重定向,訪問到對(duì)應(yīng)的長(zhǎng)URL。

4、展示對(duì)應(yīng)的內(nèi)容。

本文主要集中于第一步,即如何將一個(gè)長(zhǎng)URL對(duì)應(yīng)到短URL上。

服務(wù)設(shè)計(jì)

如果你在往長(zhǎng)短URL真實(shí)的對(duì)應(yīng)關(guān)系上想,那么就走遠(yuǎn)了，最理想的情況是: 我們用一種算法,對(duì)每一個(gè)長(zhǎng)URL,唯一的轉(zhuǎn)換成短URL.還能保持反向轉(zhuǎn)換的能力。

但是這是不可能的,如果有這樣的算法,世界上的所有壓縮算法都可以原地去世了。

正確的思路是建立一個(gè)發(fā)號(hào)器,每次有一個(gè)新的長(zhǎng)URL進(jìn)來,我們就增加一,并且將新的數(shù)值返回.第一個(gè)來的URL返回"www.x.cn/0",第二個(gè)返回"www.x.cn/1"。

接下來以QA形式寫幾個(gè)小問題:

對(duì)應(yīng)關(guān)系如何存儲(chǔ)?

這個(gè)對(duì)應(yīng)數(shù)據(jù)肯定是要落盤的，不能每次系統(tǒng)重啟就重新排號(hào)，所以可以采用mysql等數(shù)據(jù)庫(kù)來存儲(chǔ)。而且如果數(shù)據(jù)量小且qps低,直接使用數(shù)據(jù)庫(kù)的自增主鍵就可以實(shí)現(xiàn)。

如何保證長(zhǎng)短鏈接一一對(duì)應(yīng)?

按照上面的發(fā)號(hào)器策略，是不能保證長(zhǎng)短鏈接的一一對(duì)應(yīng)的，你連續(xù)用同一個(gè)URL請(qǐng)求兩次,結(jié)果值都是不一樣的。

為了實(shí)現(xiàn)長(zhǎng)短鏈接一一對(duì)應(yīng)，我們需要付出很大的空間代價(jià)，尤其是為了快速響應(yīng),我們可以需要在內(nèi)存中做一層緩存，這樣子太浪費(fèi)了。

但是可以實(shí)現(xiàn)一些變種的，來實(shí)現(xiàn)部分的一一對(duì)應(yīng)，比如將最近/最熱門的對(duì)應(yīng)關(guān)系存儲(chǔ)在K-V數(shù)據(jù)庫(kù)中，這樣子可以節(jié)省空間的同時(shí)，加快響應(yīng)速度。

短URL的存儲(chǔ)

我們返回的短URL一般是將數(shù)字轉(zhuǎn)換成32進(jìn)制，這樣子可以更加有效的縮短URL長(zhǎng)度，那么32進(jìn)制的數(shù)字對(duì)計(jì)算機(jī)來說只是字符串，怎么存儲(chǔ)呢？直接存儲(chǔ)字符串對(duì)等值查找好找，對(duì)范圍查找等太不友好了。

其實(shí)可以直接存儲(chǔ)10進(jìn)制的數(shù)字，這樣不僅占用空間少，對(duì)查找的支持較好，同時(shí)還可以更加方便的轉(zhuǎn)換到更多/更少的進(jìn)制來進(jìn)一步縮短URL。

高并發(fā)

如果直接存儲(chǔ)在MySQL中，當(dāng)并發(fā)請(qǐng)求增大，對(duì)數(shù)據(jù)庫(kù)的壓力太大，可能會(huì)造成瓶頸,這時(shí)候是可以有一些優(yōu)化的。

緩存

上面保證長(zhǎng)短鏈接一一對(duì)應(yīng)中也提到過緩存，這里我們是為了加快程序處理速度。可以將熱門的長(zhǎng)鏈接(需要對(duì)長(zhǎng)鏈接進(jìn)來的次數(shù)進(jìn)行計(jì)數(shù))，最近的長(zhǎng)鏈接(可以使用redis保存最近一個(gè)小時(shí)的)等等進(jìn)行一個(gè)緩存，保存在內(nèi)存中或者類似redis的內(nèi)存數(shù)據(jù)庫(kù)中，如果請(qǐng)求的長(zhǎng)URL命中了緩存，那么直接獲取對(duì)應(yīng)的短URL進(jìn)行返回，不需要再進(jìn)行生成操作。

批量發(fā)號(hào)

每一次發(fā)號(hào)都需要訪問一次MySQL來獲取當(dāng)前的最大號(hào)碼，并且在獲取之后更新最大號(hào)碼，這個(gè)壓力是比較大的。

我們可以每次從數(shù)據(jù)庫(kù)獲取10000個(gè)號(hào)碼,然后在內(nèi)存中進(jìn)行發(fā)放,當(dāng)剩余的號(hào)碼不足1000時(shí)，重新向MySQL請(qǐng)求下10000個(gè)號(hào)碼。在上一批號(hào)碼發(fā)放完了之后，批量進(jìn)行寫入。

這樣可以將對(duì)數(shù)據(jù)庫(kù)持續(xù)的操作移到代碼中進(jìn)行，并且異步進(jìn)行獲取和寫入操作，保證服務(wù)的持續(xù)高并發(fā)。

分布式

上面設(shè)計(jì)的系統(tǒng)是有單點(diǎn)的，那就是發(fā)號(hào)器是個(gè)單點(diǎn)，容易掛掉。

可以采用分布式服務(wù)，分布式的話，如果每一個(gè)發(fā)號(hào)器進(jìn)行發(fā)號(hào)之后都需要同步給其他發(fā)號(hào)器，那未必也太麻煩了。

換一種思路，可以有兩個(gè)發(fā)號(hào)器，一個(gè)發(fā)單號(hào)，一個(gè)發(fā)雙號(hào)，發(fā)號(hào)之后不再是遞增1，而是遞增2。

類比可得，我們可以用1000個(gè)服務(wù)，分別發(fā)放0-999尾號(hào)的數(shù)字，每次發(fā)號(hào)之后遞增1000。這樣做很簡(jiǎn)單，服務(wù)互相之間基本都不用通信，做好自己的事情就好了。

實(shí)現(xiàn)

由于我懶得寫JDBC代碼，更懶得弄Mybatis，所以代碼中使用到MySQL的地方都使用了Redis。

package util;
import redis.clients.jedis.Jedis;
/** * Created by pfliu on 2019/06/23. */public class ShortURLUtil {

    private static final String SHORT_URL_KEY = "SHORT_URL_KEY";    private static final String LOCALHOST = "http://localhost:4444/";    private static final String SHORT_LONG_PREFIX = "short_long_prefix_";    private static final String CACHE_KEY_PREFIX = "cache_key_prefix_";    private static final int CACHE_SECONDS = 1 * 60 * 60;
    private final String redisConfig;    private final Jedis jedis;
    public ShortURLUtil(String redisConfig) {        this.redisConfig = redisConfig;        this.jedis = new Jedis(this.redisConfig);    }
    public String getShortURL(String longURL, Decimal decimal) {        // 查詢緩存        String cache = jedis.get(CACHE_KEY_PREFIX + longURL);        if (cache != null) {            return LOCALHOST + toOtherBaseString(Long.valueOf(cache), decimal.x);        }
        // 自增        long num = jedis.incr(SHORT_URL_KEY);        // 在數(shù)據(jù)庫(kù)中保存短-長(zhǎng)URL的映射關(guān)系,可以保存在MySQL中        jedis.set(SHORT_LONG_PREFIX + num, longURL);        // 寫入緩存        jedis.setex(CACHE_KEY_PREFIX + longURL, CACHE_SECONDS, String.valueOf(num));        return LOCALHOST + toOtherBaseString(num, decimal.x);    }
    /**     * 在進(jìn)制表示中的字符集合     */    final static char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8',            '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',            'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',            'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    /**     * 由10進(jìn)制的數(shù)字轉(zhuǎn)換到其他進(jìn)制     */    private String toOtherBaseString(long n, int base) {        long num = 0;        if (n < 0) {            num = ((long) 2 * 0x7fffffff) + n + 2;        } else {            num = n;        }        char[] buf = new char[32];        int charPos = 32;        while ((num / base) > 0) {            buf[--charPos] = digits[(int) (num % base)];            num /= base;        }        buf[--charPos] = digits[(int) (num % base)];        return new String(buf, charPos, (32 - charPos));    }
    enum Decimal {        D32(32),        D64(64);
        int x;
        Decimal(int x) {            this.x = x;        }    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {            System.out.println(new ShortURLUtil("localhost").getShortURL("www.baidudu.com", Decimal.D32));            System.out.println(new ShortURLUtil("localhost").getShortURL("www.baidu.com", Decimal.D64));        }    }}

1、Spring Boot+Vue項(xiàng)目實(shí)戰(zhàn)

2、B站：4小時(shí)上手MyBatis Plus

3、一文搞懂前后端分離

4、快速上手Spring Boot+Vue前后端分離

楠哥簡(jiǎn)介

資深 Java 工程師，微信號(hào)?southwindss

《Java零基礎(chǔ)實(shí)戰(zhàn)》一書作者

騰訊課程官方 Java 面試官，今日頭條認(rèn)證大V

GitChat認(rèn)證作者，B站認(rèn)證UP主（楠哥教你學(xué)Java）

致力于幫助萬千 Java 學(xué)習(xí)者持續(xù)成長(zhǎng)。