77

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

 7 years ago
source link: https://hufangyun.com/2017/short-url/?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

本文仅授权过： segmentfault 转载

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

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

由 Gigalixir 提供免费部署服务，该地址只用于体验，⚠️ 不提供数据维护存储。

体验地址

要发车了 🚌

发车前，和大家说一下

如果不想重复的造轮子，想开箱即用，可以使用基于 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，对应不同进制的字符表示。

300

短址的长度一般设为 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进制的字母不要按顺序排列。因为想实现自定义短码的功能，我又对算法一进行了优化，下文会介绍。

自增序列算法流程图

Created with Raphaël 2.2.0开始输入网址查询数据库是否存在对应的短码返回对应的短码返回短网址结束保存输入的网址到数据库根据id计算对应的短码更新短码到数据库yesno

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

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

Created with Raphaël 2.2.0开始输入网址用户输入的是短链接提示用户不能输入短链接结束查询数据库是否存在该URL返回短码返回短网址用户选择自定义短码短码是否存在提示用户该短码已存在更新短码到数据库根据id计算对应的短码短码是否存在查询数据库获得一条自定义短码的url对应的id记录yesnoyesnoyesnoyesnoyesno

百度短网址还允许用户自定义短码，算法二 摘要算法，不和 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 地域、用户使用的设备

管理后台：删除、数据量

登录：权限管理

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

使用 Elixir + phoenix 技术栈 short_url


report

Recommend

  • 88
    • blog.51cto.com 7 years ago
    • Cache

    智能指针的原理及其应用-Dream

    所谓智能指针就是自动化管理指针所指向的动态资源的释放。那么智能指针的引用是为了解决哪些问题呢？代码中经常会忘掉释放动态开辟的资源，引用智能指针可用于动态资源管理，资源分配即初始化，定义一个类来封装资源的分配和释放，在构造函数中完成资源的分配和初...

  • 17
    • 微信 mp.weixin.qq.com 5 years ago
    • Cache

    URL短网址系统的算法设计及实践

    在通常情况下，URL是由系统生成的，通常包括URI路径，多个查询参数，可以对参数进行加密和解密。 当人们要分享...

  • 26
    • tech.meituan.com 5 years ago
    • Cache

    Java线程池实现原理及其在美团业务中的实践

    随着计算机行业的飞速发展，摩尔定律逐渐失效，多核CPU成为主流。使用多线程并行计算逐渐成为开发人员提升服务器性能的基本武器。J.U.C提供的线程池：ThreadPoolExecutor类，帮助开发人员管理线程并方便地执行并行任务。了解并合理使用线...

  • 13
    • www.wangchaochao.top 4 years ago
    • Cache

    CRC校验原理及其实现

    电子...

  • 12
    • blogread.cn 4 years ago
    • Cache

    四位计算机的原理及其实现

    四位计算机的原理及其实现 浏览:4844次  出处信息     你是否想过，计算机为什么...

  • 3
    • my.oschina.net 3 years ago
    • Cache

    Java并发编程：Synchronized及其实现原理

    一、Synchronized的基本使用     Synchronized是Java中解决并发问题的一种最常用的方法，也是最简单的一种方式。结合上篇《Java并发编程：核心理论》的论述Synchronized的主要作用分为...

  • 30
    • allenwind.github.io 3 years ago
    • Cache

    strcpy原理及其实现思路

    Mr.Feng BlogNLP、深度学习、机器学习、Python、Gostrcpy原理及其实现思路C语言中的strcpy原理及其实现方法，这里提供三种思路。 下面给出几种实现方法

  • 7
    • www.leftpocket.cn 2 years ago
    • Cache

    后端面试之系统设计-短网址（Short URL）服务怎么设计？

    后端面试之系统设计-短网址（Short URL）服务怎么设计？ 2021-12-23 约 2833 字 预计阅读 6 分钟 41 次阅读 ​ 原文地址：...

  • 9
    • www.fly63.com 2 years ago
    • Cache

    如何去掉vue的url地址中的#号?及其原理？

    如何去掉vue的url地址中的#号?import Vue from 'vue'; import VueRouter from 'vue-router'; Vue.use(VueRouter) // 1. 定义一些路由 // 每个路...

  • 7
    • www.jdon.com 1 year ago
    • Cache

    url-shortner：URL网址长度缩短服务

    url-shortner：URL网址长度缩短服务 - 极道 此 URL 缩短服务简化了生成、管理和重定向短 URL 的过程。它提供了一个

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK