泽民博客 ☰ Menu

shortUrl

我们在新浪微博上公布网址的时候。微博会自己主动判别网址。并将其转换。比如：http://t.cn/hrYnr0。
为什么要这样做的，原因我想有这样几点：
1、微博限制字数为140字一条，那么假设我们须要发一些连接上去，可是这个连接很的长。以至于将近要占用我们内容的一半篇幅。这肯定是不能被同意的。所以短网址应运而生了。
2、短网址能够在我们项目里能够非常好的对开放级URL进行管理。
有一部分网址能够会涵盖性、暴力、广告等信息。这样我们能够通过用户的举报，全然管理这个连接将不出如今我们的应用中，应为相同的URL通过加密算法之后，得到的地址是一样的。
3、我们能够对一系列的网址进行流量，点击等统计，挖掘出大多数用户的关注点。这样有利于我们对项目的兴许工作更好的作出决策。

1.压缩
实现一种算法，将长地址转换成短地址。然后再实现一种逆运算，将短地址转换成原来的地址。
问题，复杂场景无法覆盖，只能对简单的url可行
2.Hash算法
将一个长URL进行Hash运算，然后将Hash值作为这个长链接的唯一标示。但是通常容易想到的不一定是最优的，我们知道Hash有可能产生碰撞，Hash碰撞的解决，会增强短链接系统的复杂度。



短网址映射算法的理论：
① 将长网址用md5算法生成32位签名串，分为4段,，每段8个字符；
② 对这4段循环处理，取每段的8个字符, 将他看成16进制字符串与0x3fffffff(30位1)的位与操作。超过30位的忽略处理。
③ 将每段得到的这30位又分成6段，每5位的数字作为字母表的索引取得特定字符，依次进行获得6位字符串；
④ 这样一个md5字符串能够获得4个6位串。取里面的随意一个就可作为这个长url的短url地址。



我们并不一定说得到的URL是唯一的。可是我们可以取出4组URL，这样差点儿不会出现太大的反复。



3.自增id法
短链接系统的第一个请求我们可以给变为t.cn/0，第二个t.cn/1等等；
实现的方式也会很简单
发号器发出的10进制号需要转换成62进制，这样可以大大缩短号码转换成字符串后的长度。比如发号器发出 10,000,000,000 这个号码，如果不转换成62进制，直接拼接在域名后面，得到这样一个链接 xx.xxx/10000000000。将上面的号码转换成62进制，结果为AOYKUa，长度只有6位，拼接得到的链接为 xx.xxx/AOYKUa。可以看得出，进制转换后得到的短链接长度变短了一些。6位62进制数，对应的号码空间为626，约等于568亿，所以基本上不用担心发号器无号可发的情况。
1、小型的系统用MySQL的自增索引就可以满足。
2、大型系统可以考虑分布式key-value系统。
问题，长链到短链的映射无法实现



短址的长度一般设为 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 总共 62 个字母组成的，所以 6 位的话，总共会有 62^6 ~= 568亿种组合，基本上够用了。
这里附上一个进制转换工具 http://tool.lu/hexconvert/



php有个开源的库：https://github.com/YOURLS/YOURLS



比如：http://t.cn/RlB2PdD 这种，在微博这些限制字数的应用里。好处不言而喻。短、字符少、美观、便于发布、传播。
百度短网址 http://dwz.cn/
谷歌短网址服务 https://goo.gl/



原理解析
当我们在浏览器里输入 http://t.cn/RlB2PdD 时



DNS首先解析获得 http://t.cn 的 IP 地址
当 DNS 获得 IP 地址以后（比如：74.125.225.72），会向这个地址发送 HTTP GET 请求，查询短码 RlB2PdD
http://t.cn 服务器会通过短码 RlB2PdD 获取对应的长 URL
请求通过 HTTP 301 转到对应的长 URL https://m.helijia.com 。
这里有个小的知识点，为什么要用 301 跳转而不是 302 呐？



301 是永久重定向，302 是临时重定向。短地址一经生成就不会变化，所以用 301 是符合 http 语义的。同时对服务器压力也会有一定减少。
但是如果使用了 301，我们就无法统计到短地址被点击的次数了。而这个点击次数是一个非常有意思的大数据分析数据源。能够分析出的东西非常非常多。所以选择302虽然会增加服务器压力，但是我想是一个更好的选择。



第三种算法的好处就是简单好理解，永不重复。但是短码的长度不固定，随着 id 变大从一位长度开始递增。如果非要让短码长度固定也可以就是让 id 从指定的数字开始递增就可以了。百度短网址用的这种算法。上文说的开源短网址项目 YOURLS 也是采用了这种算法。https://github.com/YOURLS/YOURLS/blob/master/includes/functions.php



第二种算法，存在碰撞（重复）的可能性，虽然几率很小。短码位数是比较固定的。不会从一位长度递增到多位的。据说微博使用的这种算法。



百度短网址还允许用户自定义短码，算法二 摘要算法，不和 id 绑定，好像挺好实现这个功能的。



但是自增序列算法是和 id 绑定的，如果允许自定义短码就会占用之后的短码，之后的 id 要生成短码的时候就发现短码已经被用了，那么 id 自增一对一不冲突的优势就体现不出来了。



数据表设计
links 表



字段 含义
id link_id
url 长连接
keyword 短链接码
type 系统: “system” 自定义: “custom”
insert_at 插入时间
updated_at 更新时间



算法本质上就是一个长短链接的映射过程，那么一个简单的想法是用递增的序号来表示短链接，每次进来一个长链接时，把它映射成当前的序号，同时把序号递增以供下一个链接使用。因为链接地址同时使用的是a-z、A-Z和0-9这62个字符，把10进制的序号值转化为这个62进制的表示即可得到对应的短链接。



这个直接的想法非常简单粗暴，另外一个直观的想法是使用随机的方法生成长短链接的映射关系。每次进来一个长链接时就随机一个短链接来进行映射，如果通过数据库查询发现此短链接已经使用过，则重新进行随机直到产生一个未曾使用过的短链接为止。



网上流传较广的是另外一种利用MD5进行哈希的算法，其具体过程为：





  1. 将原始长链接进行MD5加密，为了避免防止算法泄漏，可以在原链接上添加自定义的字符串作为密钥。




  2. 把128位的MD分成四组，每组32位，对应一个候选短链接。




  3. 对于每个32位的数，将它与0x3FFFFFFF进行位与运算，取其低30位的数据。把得到的值与0x0000003D进行位与运算，再把得到的结果作为下标在字符表中选取字符，再把原数字右移5位进行相同操作，重复进行6次得到6个字符，即组成一个候选短链接地址。




  4. 在4个候选短链接中随机选择一个作为最终的短链接，把长短链接映射关系存入数据库中。





服务器收到一个短链接请求时，需要把从http地址中解析出短链接，然后将得到的短链接在数据库中进行查询，找到其对应的长连接，进而重定向到该长长链接对应的地址。另外，服务器在此时可以随意进行一些需要的统计工作。


Category web