【面试题及我做的答案】如何将长URL转换为短URL？

服务器接收数据

服务器响应请求/MVC

服务器返回数据

客户端接收数据

浏览器加载/渲染页面

打印绘制输出

关于DNS部分需要补充的知识如下，DNS的域名解析是递归的：

根域名服务器是用来查顶域权威服务器用的，作为全球因特网DNS体系的固定统一入口。全球13组根域名服务器中有 10 组在美国。

拓展阅读：DNS层面是可以进行DNS劫持的，DNS劫持又称域名劫持，是指在劫持的网络范围内拦截域名解析的请求，分析请求的域名，把审查范围以外的请求放行，否则返回假的IP地址或者什么都不做使请求失去响应，其效果就是对特定的网络不能访问或访问的是假网址。

DNS劫持(DNS钓鱼攻击)十分凶猛且不容易被用户感知，曾导致巴西最大银行巴西银行近1%客户受到攻击而导致账户被盗。黑客利用宽带路由器的缺陷对用户DNS进行篡改——用户只要浏览一下黑客所掌控的WEB页面，其宽带路由器的DNS就会被黑客篡改，因为该WEB页面设有特别的恶意代码，所以可以成功躲过安全软件检测，导致大量用户被DNS钓鱼诈骗。

参考资料

短链接的思路

短链接的实现有些人提出了压缩算法和Hash映射等等，有人也在知乎进行了讨论（下一节会提出），其实这些的方向都错了会钻到牛角尖里。

正确的思路，是做一个发号器，通过长短链接的一一映射关系进行统一的管理。每过来一个长地址，就让发号器发一个号即可，长地址和短地址的映射关系甚至可以放在mysql。

为例，我们再简化一下，哪怕是最简单的id自增都是简单实用的，根据长地址依次生成 、 、 、 ……

短地址的生成是一个读多写少的情况，技术上可以思考更全面一些，比如：

发号器的实现最核心的方式之一是多进制的使用。

我们上篇文章介绍的UUID，以及之前介绍过的Snowflake雪花算法，还有百度开源的基于Snowflake的Uidgenerator、美团开源的leaf都是发号器。

目前业界使用Apache亮哥的sharding-jdbc，一般都会采取其内置的Snowflake算法，关于二次改造我这里列举一个58沈剑在《架构师之路》系列中提出的例子。

更多资料大家可以参考我写的原创文章：

《》

《》

发号器的设计思路

在设计发号器之初，必须要做的是评估发号器的容量。

自增序列算法

自增序列算法也叫永不重复算法，通过据id自增和based62来实现长短转换。

这是一种设置 id 自增，一个 10进制 id 对应一个 62进制的数值，1对1，也就不会出现重复的情况。这个利用的就是低进制转化为高进制时，字符数会减少的特性。

进制转换工具

以新浪微博微为例，如果新浪微博日活用户量是1亿，如果每个人每天发0.1条带URL的新浪微博，那么转换为短地址我们要考虑总量和读写的压力，微博场景下是读多写少的。

对于写来说，每天产生一千万微博数量，那么每年大概是0.1亿*365=36.5亿，如果采用based62上生成6位， 短址的长度一般设为 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 总共 62 个字母组成的，所以 6 位的话，总共会有 62^6 ~= 568亿种组合，够用15年。在google URL shortener 服务中，短址长度为 5，大概有9亿多种组合。

如果按照秒来算的话，一天86400秒，每天写的平均QPS大概在 0.1亿 /86400秒=115QPS，我们可以把峰值设置为500QPS。所以500QPS就是发号器设置的QPS写峰值，也是这个系统设计之初需要达到的QPS。

对于读来说，读比写要多，比如一亿人一天只有十分之一的人发微博，但是每个人都会点击10条别人的微博。点击这个URL的峰值我们可以初步计算为 1亿*10/86400 = 11万5000 QPS。这么大的QPS最好使用分布式缓存Redis去存储。

对于存储来说，如果一个URL是100bytes（字节），那么每天产生一千万的微博总量是 100bytes * 1千万 / 1024/1024/1024 = 0.93G，每年产生0.93G*365=339G=0.3T。所以准备1T的硬盘，没有特殊情况，可以用3年。

在stackoverflow上也有老外提出了自增序列算法的解答（ ）

于每一个长地址，我们可以根据它的ID，得到一个6位的 62 进制数，这个6位的 62 进制数就是我们的短址:

public ArrayList base62(int id) {

    ArrayList value = new ArrayList();
    while (id > 0) {
        int remainder = id % 62;
        value.add(remainder);
        id = id / 62;
    }

    return value;
}

举个例子，对于 ID = 138，通过 base62(138), 我们得到 value = [14, 2]。根据上面的对应规则表长网址转换为短网址的软件，我们可以得到其对应的短址为：aaaabn

通过短址找到所对应的长地址，方法也很简单，就是把62进制数转成10进制数即可，这样我们就可以得到长地址的ID了。

public static int base10(ArrayList base62) {
    //make sure the size of base62 is 6
    for (int i = 1; i <= 6 - base62.size(); i++) {
        base62.add(0, 0);
    }

    int id = 0;
    int size = base62.size();
    for (int i = 0; i < size; i++) {
        int value = base62.get(i);
        id += (int) (value * Math.pow(62, size - i - 1));
    }

    return id;
}

举个例子，对于短址aaae9a，其62进制为[0, 0, 0, 4,61,0] ，则其长地址的ID 为[0, 0, 0, 4,61,0] = 0×62^5+ 0×62^4 + 0×62^3 + 4×62^2 + 61×62^1 + 0×62^0 = 1915810。有了ID，我们自然就可以得到长地址了。

这个做法可能会有短码长度不固定的问题，(rand(1,9) * pow(10, 9) + id).toString() 可以尝试让短码定长，而且看起来更随机，不至于出现同一用户连续生成短网址地址有序的。

MD5进制算法

这个算法来自于 ，据说微博使用的这种算法，算法如下所示：

这种算法存在碰撞（重复）的可能性，短码位数固定，生成之前需要进行防碰撞的检测。

知乎关于生成短地址的讨论

写到这里长网址转换为短网址的软件，如果你还没看够，那就看看知乎的激烈讨论吧：

欢迎加入我的知识星球，一起探讨架构，交流源码。加入方式，长按下方二维码噢：

知识星球是 公众号 工匠人生 忠实读者私密进阶学习圈。这里会有很多超越公众号技术深度的架构原创实战经验，也有私密微信群，分享行业深度洞见，交流碰撞，沉淀优质内容。

我的星球开通了分销功能，邀请一位朋友进入星球，他能打折，你还可以获得41.79元。这也算给星球原始居民的福利哈，分享星球已经升级为橙色了，分享有赏分享可以赚钱赚佣金。