短鏈很常見，在互聯(lián)網(wǎng)營銷場景以及移動(dòng)端信息傳播等場景下起著重要的作用。同時(shí)，也是經(jīng)常被來拿考察選手系統(tǒng)設(shè)計(jì)水平的一個(gè)場景。

對(duì)于服務(wù)端研發(fā)，關(guān)于前端訪問時(shí)的長短轉(zhuǎn)換，其實(shí)只要知道有30X重定向基本也就可以了。

相較于重定向，我更關(guān)注的，是短鏈生成方式選型、存儲(chǔ)選型、系統(tǒng)性能應(yīng)對(duì)等方面的方案和設(shè)計(jì)。

Part one 短鏈系統(tǒng)分析

短鏈系統(tǒng)的最根本能力:是可以根據(jù)長鏈計(jì)算得到短鏈，以方便外部訪問:

• 判斷對(duì)應(yīng)短鏈已存在，則直接返回
• 判斷對(duì)應(yīng)短鏈不存在，則生成短鏈，并存儲(chǔ) 長鏈->短鏈 的映射關(guān)系

也可以根據(jù)短鏈映射到長鏈，尋找真實(shí)服務(wù)地址提供服務(wù):

• 根據(jù)短鏈->長鏈 查詢存儲(chǔ)，獲取對(duì)應(yīng)的長鏈

條條大路通羅馬，系統(tǒng)方案有很多，但采取哪種最合適，還需要和存儲(chǔ)策略以及訪問性能聯(lián)合起來一起看~

Part two 實(shí)現(xiàn)方案分析

Hash是最容易想到的實(shí)現(xiàn)策略之一，那么，Hash方式有哪些優(yōu)缺點(diǎn)，我們又該怎么改進(jìn)呢?

Hash策略關(guān)鍵點(diǎn)解析

首先，如果用hash方式來生成短鏈，那么短鏈?zhǔn)菦]法通過hash碼反解出長鏈的，因此，必須存儲(chǔ)短鏈和長鏈的關(guān)聯(lián)關(guān)系;

其次，長鏈的長度一般又很長，不便于索引的構(gòu)建，需要再生成一個(gè)長鏈的固定唯一短串來輔助存儲(chǔ)和查詢。( 如32位MD5壓縮，加密算法一般不利于壓縮，而壓縮算法一般不可逆);

再次，hash難免會(huì)有沖突，需要對(duì)原始長鏈尾部拼接一個(gè)或多個(gè)固定串來消除沖突，因此，在訪問長鏈時(shí)同樣需要裁剪固定串。

Hash策略的存儲(chǔ)設(shè)計(jì)

如果用mysql進(jìn)行結(jié)構(gòu)化存儲(chǔ)比較簡單:

id | 短鏈 | 長鏈MD5 | 長鏈 | 時(shí)間戳

并且需要給 短鏈 和 長鏈MD5 構(gòu)建索引，供查詢時(shí)使用。

• 優(yōu)點(diǎn)是結(jié)構(gòu)化查詢、結(jié)構(gòu)清晰，可以設(shè)置索引提升效率;
• 缺點(diǎn)是高并發(fā)下性能需要額外關(guān)注，保存的數(shù)據(jù)要過期，理論上得進(jìn)行額外處理;

如果用redis等非結(jié)構(gòu)化kv存儲(chǔ)，則需要存儲(chǔ)多個(gè)關(guān)系用于查詢:

長鏈MD5 -> 短鏈 |

短鏈 -> 長鏈MD5 |

長鏈MD5 -> 長鏈

• 優(yōu)點(diǎn)是查詢性能高，可以抗量，且自帶過期機(jī)制;
• 缺點(diǎn)是需要維護(hù)多個(gè)KV關(guān)系，稍顯繁瑣。

改進(jìn)-- 自增ID+高位進(jìn)制法

如果說長鏈的MD5標(biāo)識(shí)的生成和存儲(chǔ)是不可缺少的，那么，可優(yōu)化的點(diǎn)，就只能從短鏈 -> 長鏈MD5的轉(zhuǎn)化這里來下手了。

有沒有辦法既可以省掉短鏈 -> 長鏈MD5的存儲(chǔ)呢?

如果我們讓唯一標(biāo)識(shí)和短鏈之間可以通過計(jì)算相互編碼解碼，是不是就可以了!?既省了一部分存儲(chǔ)，而且也省掉了查詢存儲(chǔ)的時(shí)間耗時(shí)，本地簡單計(jì)算總歸要比查詢外部存儲(chǔ)要快的多。

經(jīng)常使用進(jìn)制轉(zhuǎn)換，可以知道，進(jìn)制越高所占位數(shù)越少。

16進(jìn)制轉(zhuǎn)換示例

這個(gè)時(shí)候，用MD5應(yīng)該就不太合適了，不好參與計(jì)算，因此，我們改用純數(shù)字的分布式ID來代替MD5串(一般公司應(yīng)該都有現(xiàn)成的分布式ID生成服務(wù)吧)。

利用進(jìn)制轉(zhuǎn)換雖然可以很方便編碼成短鏈，但有時(shí)候，我們不希望出現(xiàn) 短鏈被輕松解碼，導(dǎo)致服務(wù)端可被遍歷，因此，需要考慮對(duì)進(jìn)制轉(zhuǎn)換進(jìn)行加密處理。

編碼實(shí)現(xiàn)帶加密的進(jìn)制轉(zhuǎn)換

首先，需要選擇高位進(jìn)制：我們啟用 0-9 a-z A-Z 全部的數(shù)字和字母，一共62位，即支持62進(jìn)制轉(zhuǎn)換

private static final String DIGITAL_STRING = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
//byte數(shù)組 
private static final byte[] DIGITAL;
static {
    DIGITAL = DIGITAL_STRING.getBytes(StandardCharsets.US_ASCII);
}

從10進(jìn)制向62進(jìn)制轉(zhuǎn)換的編碼實(shí)現(xiàn)：

public static String encode(long 分布式id) {
    //內(nèi)部復(fù)制
    long value = id; 
    //創(chuàng)建短鏈所需長度的空間，這里可以限制短鏈長度為最多12位，最少6位 
    ByteBuffer buf = ByteBuffer.allocate(12);
    //最多執(zhí)行12次轉(zhuǎn)換
    for (int i = 0; i < 12; i++) {
        //分布式ID對(duì)62取模
        int mod = (int) (value % 62);
        //加密， 再取模
        int pos = (mod + (OFFSET << i)) % 62;
        //根據(jù)模值從數(shù)組中獲取對(duì)應(yīng)的值，加入結(jié)果集中
        buf.put(DIGITAL[pos]);
        //求余數(shù)，用余數(shù)繼續(xù)參加后續(xù)模操作，直到余數(shù)為0 或 短鏈長度達(dá)到要求
        value = value / 62;
        if (value==0 && i >= 6) {
            break;
        }
    }
    //從ByteBuffer中獲取結(jié)果集合
    byte[] result=new byte[buf.position()];
    buf.rewind();
    buf.get(result);
    //反轉(zhuǎn)順序
    ArrayUtils.reverse(result);
    return new String(result);
}

重點(diǎn)關(guān)注(mod + (OFFSET << i)) % 62 這個(gè)操作，其目的是在模值上加上一個(gè)偏移量(偏移大小和所處位置有關(guān)，非固定偏移) ，用來防止被直接解碼。

//將短鏈串解碼為分布式ID
public static long decode(String code) {
    long value = 0;
    byte[] buf = code.getBytes();
    int length = buf.length;
    //循環(huán)次數(shù)為短鏈字符串長度
    for (int i = 0; i < length; i++) {
        byte digital = buf[i];
        //當(dāng)前字符對(duì)應(yīng)的下標(biāo)
        int index = Arrays.binarySearch(DIGITAL, digital);
        //當(dāng)前下標(biāo)需要減掉加密時(shí)增加的部分(同樣和所處位置有關(guān))
        index = index - (OFFSET << (length - i - 1));
        //因?yàn)闇p掉的有可能是一個(gè)非常大的值，再把index對(duì)62取余，如果任然小于0 ，就加上62(62進(jìn)制內(nèi)負(fù)變正)
        index = index % 62;
        if (index < 0) {
            index = index + 62;
        }
        //10進(jìn)制復(fù)原原值
        value = value * 62 + index;
    }
    return value;
}

Part three 總結(jié)

每一種技術(shù)方案，都是通過不斷論證和嘗試才可以最終決定的。我們?cè)趯W(xué)習(xí)一個(gè)技術(shù)架構(gòu)時(shí)，最好可以從它的發(fā)展歷程，每個(gè)瓶頸點(diǎn)的解決來進(jìn)行整體把握，會(huì)對(duì)我們處理問題時(shí)候的入手角度和思考方式的鍛煉起到很好的作用。

本文轉(zhuǎn)載自微信公眾號(hào)「Coder的技術(shù)之路」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Coder的技術(shù)之路公眾號(hào)。