如何实现一个短链接服务

短链接,通俗来说,就是将长的URL网址,通过程序计算等方式,转换为简短的网址字符串。

大家经常会收到一些莫名的营销短信,里面有一个非常短的链接让你跳转。新浪微博因为限制字数,所以也会经常见到这种看着不像网址的网址。短链的兴起应该就是微博限制字数激起了大家的创造力。

如果创建一个短链系统,我们应该做什么呢?

  1. 将长链接变为短链;
  2. 用户访问短链接,会跳转到正确的长链接上去。

查找到对应的长网址,并跳转到对应的页面。

短链生成方法#

短码一般是由 [a - z, A - Z, 0 - 9] 这62 个字母或数字组成,短码的长度也可以自定义,但一般不超过8位。比较常用的都是6位,6位的短码已经能有568亿种的组合:(26+26+10)^6 = 56800235584,已满足绝大多数的使用场景。

目前比较流行的生成短码方法有:自增id摘要算法普通随机数

自增id

该方法是一种无碰撞的方法,原理是,每新增一个短码,就在上次添加的短码id基础上加1,然后将这个10进制的id值,转化成一个62进制的字符串。

一般利用数据表中的自增id来完成:每次先查询数据表中的自增id最大值max,那么需要插入的长网址对应自增id值就是 max+1,将max+1转成62进制即可得到短码。

但是短码 id 是从一位长度开始递增,短码的长度不固定,不过可以用 id 从指定的数字开始递增的方式来处理,确保所有的短码长度都一致。同时,生成的短码是有序的,可能会有安全的问题,可以将生成的短码id,结合长网址等其他关键字,进行md5运算生成最后的短码。

摘要算法

摘要算法又称哈希算法,它表示输入任意长度的数据,输出固定长度的数据。相同的输入数据始终得到相同的输出,不同的输入数据尽量得到不同的输出。

算法过程:

  1. 将长网址md5生成32位签名串,分为4段, 每段8个字节;
  2. 对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理;
  3. 这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串;
  4. 总的md5串可以获得4个6位串;取里面的任意一个就可作为这个长url的短url地址;

这种算法,虽然会生成4个,但是仍然存在重复几率。

虽然几率很小,但是该方法依然存在碰撞的可能性,解决冲突会比较麻烦。不过该方法生成的短码位数是固定的,也不存在连续生成的短码有序的情况。

普通随机数

该方法是从62个字符串中随机取出一个6位短码的组合,然后去数据库中查询该短码是否已存在。如果已存在,就继续循环该方法重新获取短码,否则就直接返回。

该方法是最简单的一种实现,不过由于 Math.round()方法生成的随机数属于伪随机数,碰撞的可能性也不小。在数据比较多的情况下,可能会循环很多次,才能生成一个不冲突的短码。

算法分析

以上算法利弊我们一个一个来分析。

如果使用自增id算法,会有一个问题就是不法分子是可以穷举你的短链地址的。原理就是将10进制数字转为62进制,那么别人也可以使用相同的方式遍历你的短链获取对应的原始链接。打个比方说:http://tinyurl.com/a3300和 http://bit.ly/a3300,这两个短链网站,分别从a3300 - a3399,能够试出来多次返回正确的url。所以这种方式生成的短链对于使用者来说其实是不安全的。

摘要算法,其实就是hash算法吧,一说hash大家可能觉得很low,但是事实上hash可能是最优解。比如:http://www.sina.lt/http://mrw.so/ 连续生成的url发现并没有规律,很有可能就是使用hash算法来实现。

普通随机数算法,这种算法生成的东西和摘要算法一样,但是碰撞的概率会大一些。因为摘要算法毕竟是对url进行hash生成,随机数算法就是简单的随机生成,数量一旦上来必然会导致重复。

综合以上,我选择最low的算法:摘要算法。

实现
存储方案

数据库存储方案

短网址基础数据采用域名和后缀分开存储的形式。另外域名需要区分 HTTP 和 HTTPS,hash方案针对整个链接进行hash而不是除了域名外的链接。域名单独保存可以用于分析当前域名下链接的使用情况。

增加当前链接有效期字段,一般有短链需求的可能是相关活动或者热点事件,这种短链在一段时间内会很活跃,过了一定时间热潮会持续衰退。所以没有必要将这种链接永久保存增加每次查询的负担。

对于过期数据的处理,可以在新增短链的时候判断当前短链的失效日期,将每天到达失效日期的数据在HBase单独建一张表,有新增的时候判断失效日期放到对应的HBase表中即可,每天只用处理当天HBase表中的失效数据。

数据库基础表如下:

base_urlsuffix_urlshot_codetotal_click_countfull_urlexpiration_date
http://www.aichacha.com/search/12345edfg3s http://www.aichacha.com//search/12345
http://www.aichacha.com/aiCheck/getResult/123Fe9dq http://www.aichacha.com//aiCheck/getResult/123
http://www.baidu.com/wenku/12354lcfr53 http://www.baidu.com/wenku/12354

字段释义:

base_url:域名

suffix_url:链接除了域名外的后缀

full_url:完整链接

shot_code:当前 suffix_url 链接的短码

expiration_date:失效日期

total_click_count:当前链接总点击次数

expiration_date:当前链接失效时间

缓存方案

  • 查询需求

个人认为对于几百个G的数据量都放在缓存肯定是不合适的,所以有个折中的方案:将最近3个月内有查询或者有新增的url放入缓存,使用LRU算法进行热更新。这样最近有使用的发概率会命中缓存,就不用走库。查不到的时候再走库更新缓存。

  • 新增需求

对于新增的链接就先查缓存是否存在,缓存不存在再查库,数据库已经分表了,查询的效率也不会很低。

  • 缓存的设计

查询的需求是用户拿着短链查询对应的真实地址,那么缓存的key只能是短链,可以使用 KV的形式存储。


番外

其实也可以考虑别的存储方案,比如HBase,HBase作为NOSQL数据库,性能上仅次于redis但是存储成本比redis低很多个数量级,存储基于HDFS,写数据的时候会先先写入内存中,只有内存满了会将数据刷入到HFile。读数据也会快,原因是因为它使用了LSM树型结构,而不是B或B+树。HBase会将最近读取的数据使用LRU算法放入缓存中,如果想增强读能力,可以调大blockCache。

其次,也可以使用ElasticSearch,合适的索引规则效果不输缓存方案。


是否有分库分表的需要?

对于单条数据10b以内,一亿条数据总容量大约为 953G,单表肯定无法撑住这么大的量,所以有分表的需要,如果你对服务很有信心2年内能达到这个规模,那么你可以从一开始设计就考虑分表的方案。

那么如何定义分表的规则呢?

如果按照单表500万条记录来算,总计可以分为20张表,那么单表容量就是47G,还是挺大,所以考虑分表的 key 和单表容量,如果分为100张表那么单表容量就是10G,并且通过数字后缀路由到表中也比较容易。可以对short_code 做encoding编码生成数字类型然后做路由。

如何转跳

当我们在浏览器里输入 http://bit.ly/a3300

  1. DNS首先解析获得http://bit.ly的IP 地址
  2. DNS 获得IP 地址以后(比如:12.34.5.32),会向这个地址发送HTTPGET 请求,查询短码a3300
  3. [http://bit.ly 服务器会通过短码a3300 获取对应的长 URL
  4. 请求通过HTTP301 转到对应的长 URLhttp://www.theaustralian.news.com.au/story/0,25197,26089617-5013871,00.html。

这里有个小的知识点,为什么要用 301 跳转而不是 302 呐?

知识点:为什么要使用302跳转,而不是301跳转呢?

301是永久重定向,302是临时重定向。短地址一经生成就不会变化,所以用301是符合http语义的。但是如果用了301, Google,百度等搜索引擎,搜索的时候会直接展示真实地址,那我们就无法统计到短地址被点击的次数了,也无法收集用户的Cookie, User Agent 等信息,这些信息可以用来做很多有意思的大数据分析,也是短网址服务商的主要盈利来源。

引自知乎-武林的回答,原文链接

附上两个算法:

摘要算法:

<div class="esa-clipboard-button" data-clipboard-target="#copy_target_0" title="复制代码">Copy</div>
<span class="hljs-keyword">import</span> org.apache.commons.lang3.StringUtils;

<span class="hljs-keyword">import</span> javax.xml.bind.DatatypeConverter;
<span class="hljs-keyword">import</span> java.security.MessageDigest;
<span class="hljs-keyword">import</span> java.security.NoSuchAlgorithmException;
<span class="hljs-keyword">import</span> java.util.concurrent.atomic.AtomicLong;

<span class="hljs-keyword">import</span> <span class="hljs-keyword">static</span> com.alibaba.fastjson.util.IOUtils.DIGITS;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@author</span> rickiyang
 * <span class="hljs-doctag">@date</span> 2020-01-07
 * <span class="hljs-doctag">@Desc</span> TODO
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ShortUrlGenerator</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
        String sLongUrl = <span class="hljs-string">"http://www.baidu.com/121244/ddd"</span>;
        <span class="hljs-keyword">for</span> (String shortUrl : shortUrl(sLongUrl)) {
            System.out.println(shortUrl);
        }
    }

    <span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String[] shortUrl(String url) {
        <span class="hljs-comment">// 可以自定义生成 MD5 加密字符传前的混合 KEY</span>
        String key = <span class="hljs-string">"dwz"</span>;
        <span class="hljs-comment">// 要使用生成 URL 的字符</span>
        String[] chars = <span class="hljs-keyword">new</span> String[]{<span class="hljs-string">"a"</span>, <span class="hljs-string">"b"</span>, <span class="hljs-string">"c"</span>, <span class="hljs-string">"d"</span>, <span class="hljs-string">"e"</span>, <span class="hljs-string">"f"</span>, <span class="hljs-string">"g"</span>, <span class="hljs-string">"h"</span>,
                <span class="hljs-string">"i"</span>, <span class="hljs-string">"j"</span>, <span class="hljs-string">"k"</span>, <span class="hljs-string">"l"</span>, <span class="hljs-string">"m"</span>, <span class="hljs-string">"n"</span>, <span class="hljs-string">"o"</span>, <span class="hljs-string">"p"</span>, <span class="hljs-string">"q"</span>, <span class="hljs-string">"r"</span>, <span class="hljs-string">"s"</span>, <span class="hljs-string">"t"</span>,
                <span class="hljs-string">"u"</span>, <span class="hljs-string">"v"</span>, <span class="hljs-string">"w"</span>, <span class="hljs-string">"x"</span>, <span class="hljs-string">"y"</span>, <span class="hljs-string">"z"</span>, <span class="hljs-string">"0"</span>, <span class="hljs-string">"1"</span>, <span class="hljs-string">"2"</span>, <span class="hljs-string">"3"</span>, <span class="hljs-string">"4"</span>, <span class="hljs-string">"5"</span>,
                <span class="hljs-string">"6"</span>, <span class="hljs-string">"7"</span>, <span class="hljs-string">"8"</span>, <span class="hljs-string">"9"</span>, <span class="hljs-string">"A"</span>, <span class="hljs-string">"B"</span>, <span class="hljs-string">"C"</span>, <span class="hljs-string">"D"</span>, <span class="hljs-string">"E"</span>, <span class="hljs-string">"F"</span>, <span class="hljs-string">"G"</span>, <span class="hljs-string">"H"</span>,
                <span class="hljs-string">"I"</span>, <span class="hljs-string">"J"</span>, <span class="hljs-string">"K"</span>, <span class="hljs-string">"L"</span>, <span class="hljs-string">"M"</span>, <span class="hljs-string">"N"</span>, <span class="hljs-string">"O"</span>, <span class="hljs-string">"P"</span>, <span class="hljs-string">"Q"</span>, <span class="hljs-string">"R"</span>, <span class="hljs-string">"S"</span>, <span class="hljs-string">"T"</span>,
                <span class="hljs-string">"U"</span>, <span class="hljs-string">"V"</span>, <span class="hljs-string">"W"</span>, <span class="hljs-string">"X"</span>, <span class="hljs-string">"Y"</span>, <span class="hljs-string">"Z"</span>
        };
        <span class="hljs-comment">// 对传入网址进行 MD5 加密</span>
        String sMD5EncryptResult = <span class="hljs-string">""</span>;
        <span class="hljs-keyword">try</span> {
            MessageDigest md = MessageDigest.getInstance(<span class="hljs-string">"MD5"</span>);
            md.update((key + url).getBytes());
            <span class="hljs-keyword">byte</span>[] digest = md.digest();
            sMD5EncryptResult = DatatypeConverter.printHexBinary(digest).toUpperCase();
        } <span class="hljs-keyword">catch</span> (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }

        String[] resUrl = <span class="hljs-keyword">new</span> String[<span class="hljs-number">4</span>];
        <span class="hljs-comment">//得到 4组短链接字符串</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < <span class="hljs-number">4</span>; i++) {
            <span class="hljs-comment">// 把加密字符按照 8 位一组 16 进制与 0x3FFFFFFF 进行位与运算</span>
            String sTempSubString = sMD5EncryptResult.substring(i  <span class="hljs-number">8</span>, i  <span class="hljs-number">8</span> + <span class="hljs-number">8</span>);
            <span class="hljs-comment">// 这里需要使用 long 型来转换,因为 Inteper .parseInt() 只能处理 31 位 , 首位为符号位 , 如果不用 long ,则会越界</span>
            <span class="hljs-keyword">long</span> lHexLong = <span class="hljs-number">0x3FFFFFFF</span> & Long.parseLong(sTempSubString, <span class="hljs-number">16</span>);
            String outChars = <span class="hljs-string">""</span>;
            <span class="hljs-comment">//循环获得每组6位的字符串</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j < <span class="hljs-number">6</span>; j++) {
                <span class="hljs-comment">// 把得到的值与 0x0000003D 进行位与运算,取得字符数组 chars 索引(具体需要看chars数组的长度   以防下标溢出,注意起点为0)</span>
                <span class="hljs-keyword">long</span> index = <span class="hljs-number">0x0000003D</span> & lHexLong;
                <span class="hljs-comment">// 把取得的字符相加</span>
                outChars += chars[(<span class="hljs-keyword">int</span>) index];
                <span class="hljs-comment">// 每次循环按位右移 5 位</span>
                lHexLong = lHexLong >> <span class="hljs-number">5</span>;
            }
            <span class="hljs-comment">// 把字符串存入对应索引的输出数组</span>
            resUrl[i] = outChars;
        }
        <span class="hljs-keyword">return</span> resUrl;
    }

}

数字转为base62算法:

<div class="esa-clipboard-button" data-clipboard-target="#copy_target_1" title="复制代码">Copy</div>
<span class="hljs-comment">/**
 * <span class="hljs-doctag">@author</span> rickiyang
 * <span class="hljs-doctag">@date</span> 2020-01-07
 * <span class="hljs-doctag">@Desc</span> TODO
 * <p>
 * 进制转换工具,最大支持十进制和62进制的转换
 * 1、将十进制的数字转换为指定进制的字符串;
 * 2、将其它进制的数字(字符串形式)转换为十进制的数字
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">NumericConvertUtils</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
        String str = toOtherNumberSystem(<span class="hljs-number">22</span>, <span class="hljs-number">62</span>);
        System.out.println(str);
    }


    <span class="hljs-comment">/**
     * 在进制表示中的字符集合,0-Z分别用于表示最大为62进制的符号表示
     */</span>
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">char</span>[] digits = {<span class="hljs-string">'0'</span>, <span class="hljs-string">'1'</span>, <span class="hljs-string">'2'</span>, <span class="hljs-string">'3'</span>, <span class="hljs-string">'4'</span>, <span class="hljs-string">'5'</span>, <span class="hljs-string">'6'</span>, <span class="hljs-string">'7'</span>, <span class="hljs-string">'8'</span>, <span class="hljs-string">'9'</span>,
            <span class="hljs-string">'a'</span>, <span class="hljs-string">'b'</span>, <span class="hljs-string">'c'</span>, <span class="hljs-string">'d'</span>, <span class="hljs-string">'e'</span>, <span class="hljs-string">'f'</span>, <span class="hljs-string">'g'</span>, <span class="hljs-string">'h'</span>, <span class="hljs-string">'i'</span>, <span class="hljs-string">'j'</span>, <span class="hljs-string">'k'</span>, <span class="hljs-string">'l'</span>, <span class="hljs-string">'m'</span>,
            <span class="hljs-string">'n'</span>, <span class="hljs-string">'o'</span>, <span class="hljs-string">'p'</span>, <span class="hljs-string">'q'</span>, <span class="hljs-string">'r'</span>, <span class="hljs-string">'s'</span>, <span class="hljs-string">'t'</span>, <span class="hljs-string">'u'</span>, <span class="hljs-string">'v'</span>, <span class="hljs-string">'w'</span>, <span class="hljs-string">'x'</span>, <span class="hljs-string">'y'</span>, <span class="hljs-string">'z'</span>,
            <span class="hljs-string">'A'</span>, <span class="hljs-string">'B'</span>, <span class="hljs-string">'C'</span>, <span class="hljs-string">'D'</span>, <span class="hljs-string">'E'</span>, <span class="hljs-string">'F'</span>, <span class="hljs-string">'G'</span>, <span class="hljs-string">'H'</span>, <span class="hljs-string">'I'</span>, <span class="hljs-string">'J'</span>, <span class="hljs-string">'K'</span>, <span class="hljs-string">'L'</span>, <span class="hljs-string">'M'</span>,
            <span class="hljs-string">'N'</span>, <span class="hljs-string">'O'</span>, <span class="hljs-string">'P'</span>, <span class="hljs-string">'Q'</span>, <span class="hljs-string">'R'</span>, <span class="hljs-string">'S'</span>, <span class="hljs-string">'T'</span>, <span class="hljs-string">'U'</span>, <span class="hljs-string">'V'</span>, <span class="hljs-string">'W'</span>, <span class="hljs-string">'X'</span>, <span class="hljs-string">'Y'</span>, <span class="hljs-string">'Z'</span>};

    <span class="hljs-comment">/**
     * 将十进制的数字转换为指定进制的字符串
     *
     * <span class="hljs-doctag">@param</span> number 十进制的数字
     * <span class="hljs-doctag">@param</span> seed   指定的进制
     * <span class="hljs-doctag">@return</span> 指定进制的字符串
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">toOtherNumberSystem</span><span class="hljs-params">(<span class="hljs-keyword">long</span> number, <span class="hljs-keyword">int</span> seed)</span> </span>{
        <span class="hljs-keyword">if</span> (number < <span class="hljs-number">0</span>) {
            number = ((<span class="hljs-keyword">long</span>) <span class="hljs-number">2</span> * <span class="hljs-number">0x7fffffff</span>) + number + <span class="hljs-number">2</span>;
        }
        <span class="hljs-keyword">char</span>[] buf = <span class="hljs-keyword">new</span> <span class="hljs-keyword">char</span>[<span class="hljs-number">32</span>];
        <span class="hljs-keyword">int</span> charPos = <span class="hljs-number">32</span>;
        <span class="hljs-keyword">while</span> ((number / seed) > <span class="hljs-number">0</span>) {
            buf[--charPos] = digits[(<span class="hljs-keyword">int</span>) (number % seed)];
            number /= seed;
        }
        buf[--charPos] = digits[(<span class="hljs-keyword">int</span>) (number % seed)];
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> String(buf, charPos, (<span class="hljs-number">32</span> - charPos));
    }

    <span class="hljs-comment">/**
     * 将其它进制的数字(字符串形式)转换为十进制的数字
     *
     * <span class="hljs-doctag">@param</span> number 其它进制的数字(字符串形式)
     * <span class="hljs-doctag">@param</span> seed   指定的进制,也就是参数str的原始进制
     * <span class="hljs-doctag">@return</span> 十进制的数字
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">long</span> <span class="hljs-title">toDecimalNumber</span><span class="hljs-params">(String number, <span class="hljs-keyword">int</span> seed)</span> </span>{
        <span class="hljs-keyword">char</span>[] charBuf = number.toCharArray();
        <span class="hljs-keyword">if</span> (seed == <span class="hljs-number">10</span>) {
            <span class="hljs-keyword">return</span> Long.parseLong(number);
        }

        <span class="hljs-keyword">long</span> result = <span class="hljs-number">0</span>, base = <span class="hljs-number">1</span>;

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = charBuf.length - <span class="hljs-number">1</span>; i >= <span class="hljs-number">0</span>; i--) {
            <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>, length = digits.length; j < length; j++) {
                <span class="hljs-comment">//找到对应字符的下标,对应的下标才是具体的数值</span>
                <span class="hljs-keyword">if</span> (digits[j] == charBuf[i]) {
                    index = j;
                }
            }
            result += index * base;
            base *= seed;
        }
        <span class="hljs-keyword">return</span> result;
    }
}
作者: rickiyang

出处:https://www.cnblogs.com/rickiyang/p/12178644.html

本站使用「CC BY 4.0」创作共享协议,转载请在文章明显位置注明作者及出处。
最后修改:2021 年 07 月 08 日
如果觉得我的文章对你有用,请随意赞赏