专栏首页程序员宝库短网址(short URL)系统的原理及其实现

短网址(short URL)系统的原理及其实现

作者: 小猿大圣 https://segmentfault.com/a/1190000012088345

背景

提供一个短址服务。

你有没有发现,我们的任务中出现长 URL 就会比较麻烦?如果有一个短址生成器就好了。虽然市面上有很多,但是我们可以重复发明一个轮子,利用这个机会尝试一下简单的 Web 全栈开发。

任务

做一个短链接生成器,可以将一个长链接缩短成一个短链接。

要发车了 ?

发车前,和大家说一下

如果不想重复的造轮子,想开箱即用,可以使用基于 PHP 的开源软件 YOURLS。 YOURLS 还可以和 WordPress 整合到一起,功能强大,可扩展性高。

本文记录了开发短网址系统的整个过程,包括初期的算法调研、模块设计、数据库设计、功能扩展等。

什么是短链接 ?

就是把普通网址,转换成比较短的网址。比如:http://t.cn/RlB2PdD 这种,在微博这些限制字数的应用里。好处不言而喻。短、字符少、美观、便于发布、传播。

百度短网址:http://dwz.cn/

谷歌短网址服务:https://goo.gl/ (需访问外国网站)号称是最快的 ?

原理解析

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

  1. DNS首先解析获得 http://t.cn 的 IP 地址
  2. DNS 获得 IP 地址以后(比如:74.125.225.72),会向这个地址发送 HTTP GET 请求,查询短码 RlB2PdD
  3. http://t.cn 服务器会通过短码 RlB2PdD 获取对应的长 URL
  4. 请求通过 HTTP 301 转到对应的长 URL https://m.helijia.com 。

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

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

算法实现

网上比较流行的算法有两种 自增序列算法、 摘要算法

算法一

自增序列算法 也叫永不重复算法

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

如下图:十进制 10000,对应不同进制的字符表示。

短址的长度一般设为 6 位,而每一位是由 [a-z,A-Z,0-9] 总共 62 个字母组成的,所以 6 位的话,总共会有 62^6 ~= 568亿种组合,基本上够用了。

哈哈,这里附上一个进制转换工具 http://tool.lu/hexconvert/ 上图的数据就是用这个工具生成的。

具体的算法实现,自行谷歌。

算法二

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

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

两种算法对比

第一种算法的好处就是简单好理解,永不重复。但是短码的长度不固定,随着 id 变大从一位长度开始递增。如果非要让短码长度固定也可以就是让 id 从指定的数字开始递增就可以了。百度短网址用的这种算法。上文说的开源短网址项目 YOURLS 也是采用了这种算法。源码学习

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

我使用的算法一。有一个不太好的地方就是出现的短码是有序的,可能会不安全。我的处理方式是构造 62进制的字母不要按顺序排列。因为想实现自定义短码的功能,我又对算法一进行了优化,下文会介绍。

流程图

自增序列算法流程图

只实现长链接转化为短链接的功能,不是很麻烦。在调研的过程中我发现百度短网址可以自定义短码,我觉的这个功能挺不错,结果复杂度就是上图到下图的变化。?

自增序列算法 + 用户自定义短码 流程图

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

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

那么怎么实现自定义短码呐?

我是这样处理的:

数据库增加一个类型 type 字段,用来标记短码是用户自定义生成的,还是系统自动生成的。如果有用户自定义过短码,把它的类型标记自定义。每次根据 id 计算短码的时候,如果发现对应的短码被占用了,就从类型为自定义的记录里选取一条记录,用它的 id 去计算短码。这样既可以区分哪些长连接是用户自己定义还是系统自动生成的,还可以不浪费被自定义短码占用的 id。

我保留了 1 到 2 位的 短码,从三位的短码开始生成的。就像域名的保留域名一样,好的要自己预留 ?

位数

个数

区间

1位

62

0 - 61

2位

3844

62 - 3843

3位

约 23万

3844 - 238327

4位

约 1400万

238328 - 14776335

5位

约 9.1亿

14776336 - 916132831

6位

约 568亿

916132832 - 56800235583

数据表设计

links 表

字段

含义

id

link_id

url

长连接

keyword

短链接码

type

系统: "system" 自定义: "custom"

insert_at

插入时间

updated_at

更新时间

后期功能扩展

统计:点击量、访问的 ip 地域、用户使用的设备

管理后台:删除、数据量

登录:权限管理

设置密码:输入密码才可以继续访问

本文分享自微信公众号 - 程序员宝库(chengxuyuanbaoku),作者:小猿大圣

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 码农也要学算法

    当“人工智能”、“AlphaGo”、“无人驾驶”、“智能投顾”等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算机通过提供给人类每天要面临的...

    程序员宝库
  • 今日头条算法原理(全)

    ▲3分钟了解今日头条推荐算法原理 今天,算法分发已经是信息平台、搜索引擎、浏览器、社交软件等几乎所有软件的标配,但同时,算法也开始面临质疑、挑战和误解。今日头条...

    程序员宝库
  • 后端好书阅读与推荐(续四)

    这里依然记录一下每本书的亮点与自己读书心得和体会,分享并求拍砖。 Docker生产环境实践指南 Docker生产环境实践指南 (豆瓣:https://book....

    程序员宝库
  • 这个超牛算法+九轴传感器,将席卷整个无人机界

    目前制约智能运动手表/儿童手表的一个最大障碍是GPS的功耗,因为一旦开启GPS定位功能,手表的小型电池那点电能嗖嗖地就被吃完了,这是很多在做智能手表的公司最头痛...

    机器人网
  • 非算法工程师面试必问的算法面试理论 顶

    数据结构是算法的基础。大家需要对数据结构有个清晰的概念,因为大部分的算法题均需要带入数据结构的概念来处理。科班出身的程序员或多或少学习过数据结构。我们推荐大家可...

    个推君
  • GitHub 标星 2.4w+,这个开源项目让算法动起来!

    一门编程语言在入门之后,要想进阶,便必须得学好算法和数据结构,但一般的学习过程通常是枯燥无味的,今天在这里给大家分享个工具,兴许能解决你这个问题。

    GitHubDaily
  • Android:你要的WebView与 JS 交互方式 都在这里了

    对于Android调用JS代码的方法有2种: 1. 通过WebView的loadUrl() 2. 通过WebView的evaluateJavascrip...

    Carson.Ho
  • R语言系列第三期:②R语言多组汇总及图形展示

    A. 事实上,我们在实验中或者调查之后的分析往往希望通过分组比较来获得有统计学意义的结果,因此分组数据在我们平常的工作中更加常见,也更加科学严谨,那么我们就来了...

    微点
  • 学界 | 哈佛研究者推出新型优化算法,指数级提升计算速度

    这个算法由哈佛大学的研究人员开发,通过减少已有算法的迭代次数来快速解决优化问题。更出人意料的是,哈佛大学高级研究员Yaron Singer指出,这个方法并不以减...

    大数据文摘
  • 短小精悍的多源最短路径算法—Floyd算法

    在图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而两种算法还是有区别的,Floyd主要计算多源最短路径。

    bigsai

扫码关注云+社区

领取腾讯云代金券