浅谈短链的设计

语言: CN / TW / HK

       

背景

目前在很多场景下,都需要短链,尤其是涉及到一些 URL 下发的逻辑。之前做小马 AI 课的业务时,销售通过短信下发的链接就是一个短链。为什么需要短链呢?考虑到一个 URL 上有 path、query 等参数,各种参数拼接在一起就成了一个长不拉几的字符串。

在很多社交平台上,对于发送的文本是有长度限制,过长的 URL 很容易被截断,然后触达就无效了。当用户收到一个短链,心情可能更加愉悦:

短链组成

知己知彼百战百胜,先来看看一个短链有哪些信息。

协议 + 域名 + path,协议可以直接忽略。域名是必须的(废话),并且足够短,否则的话就变成了长的短链(挺傻的)。最后 path 的部分才是关键,看起来是一个由 6 个字符组成的字符串,并且字符的范围是大小写字母+数字。

足够短的域名需要什么条件?大概率钱够就行。涉及到钱的部分,这里就不深入探究了。所以来研究一下这个 path 的生成。

Path 的生成

获取一个序号

哈希算法

Path 的其中一种方式就是通过哈希算法计算得到。常见的哈希函数有 MD5、SHA1 等大家常见的加密型哈希算法,也有 HighwayHash、MurmurHash 等非加密型哈希函数。以 MurmurHash 为例,目前已经迭代到 MurmurHash 3,能够产生 32bit 和 128 bit 的哈希值,并且对于规律性较强的 key,随机分布的特征表现的很不错。

不过哈希冲突是不可控的,我们虽然有 N 种解决哈希冲突的方式,但是会增加整个系统的整体复杂度。

自增 ID

也可以维护一个 ID 自增生成器,对于每一个长链生成1、2、3等自增的序号,然后把长链和序号的映射保存在数据库里面,然后得到如 http://fake.short/1、http://fake.short/2 等短链。考虑到单机容易造成单点故障,所以一般都是分布式的 ID 生成器。

Mysql 自增

假设有 10 台 Mysql 服务器,每一台初始值分别为 0……9,然后每生成一个需要就递增 10,这样确保这 10 台 Mysql 服务器产生的 ID 不重复。但这个方案缺点比较明显,就是 ID 是有迹可循的,爬虫的可以顺着顺序依次请求得到;水平扩展不容易,如之前约定 10 台机器,每台机器生产的步长是 10,如果需要增加一台机器,比较困难;数据库压力还是很大,每次获取ID都得读写一次数据库,只能靠堆机器来提高性能。

基于雪花算法

SnowFlake 是 Twitter 公司采用的一种算法,目的是在分布式系统中产生全局唯一且趋势递增的ID。

第一位占用 1bit,其值始终是0,没有实际作用。2.时间戳 占用 41bit,精确到毫秒,总共可以容纳约 69 年的时间。3.工作机器id 占用10bit,其中高位 5bit 是数据中心ID,低位 5bit 是工作节点ID,做多可以容纳 1024 个节点。4.序列号 占用12bit,每个节点每毫秒0开始不断累加,最多可以累加到4095,一共可以产生 4096 个ID。

SnowFlake算法在同一毫秒内最多可以生成 1024 X 4096 = 4194304 个全局唯一ID。

国内也有不少基于(类)雪花算法的开源分布式唯一ID生成器:

  1. UidGenerator

由百度开源的分布式 UID 生成器。http://github.com/baidu/uid-generator

  1. Leaf

Leaf 是美团开源的分布式ID生成器,能保证全局唯一,趋势递增,但需要依赖关系数据库、Zookeeper等中间件。http://tech.meituan.com/2017/04/21/mt-leaf.html

进一步缩短

如果我们得到『1536389934』这个序号的话,看起来还是有点长,如果想进一步缩短,可以把十进制数转换成62进制数。然后就得到一个比原序号更短的 ID 了。

为什么要用62进制转换?

  • 62进制转换是因为62进制转换后只含数字+小写+大写字母。而64进制转换会含有 / , + 这样的符号(不符合正常URL的字符)encodeURIComponent('+') => %xx
  • 10进制转62进制可以缩短字符,如果我们要6位字符的话,已经有560亿个组合了。

重定向是 301 还是 302

众所周知,301 是永久重定向,浏览器会把重定向后的地址缓存下来,下次访问的时候,就不会向原地址发起请求;按理来说通过 301 的重定向性能会更好,对服务的压力也更小。

但是,正因为 301 会在浏览器中有缓存,所以服务端就没办法知道有多少用户是通过这个短链访问的,在现如今什么数据都可以分析一波的时代,这些数据的缺失,就失去了分析活动的能力。所以一般都通过 302 进行重定向,便于记录使用的数据,稍微增加点 Server 的压力。(没有什么是不能通过加机器解决的

参考资料

http://juejin.cn/post/6990275533057556494

http://tech.meituan.com/2017/04/21/mt-leaf.html

http://zhuanlan.zhihu.com/p/85837641

http://www.zhihu.com/question/29270034

http://www.zhihu.com/question/20103344

:heart: 谢谢支持

以上便是本次分享的全部内容,希望对你有所帮助^_^

喜欢的话别忘了 分享、点赞、收藏 三连哦~。

欢迎关注公众号 ELab团队 收货大厂一手好文章~

我们来自字节跳动,是旗下大力教育前端部门,负责字节跳动教育全线产品前端开发工作。

我们围绕产品品质提升、开发效率、创意与前沿技术等方向沉淀与传播专业知识及案例,为业界贡献经验价值。包括但不限于性能监控、组件库、多端技术、Serverless、可视化搭建、音视频、人工智能、产品设计与营销等内容。

欢迎感兴趣的同学在评论区或使用内推码内推到作者部门拍砖哦

字节跳动校/社招投递链接: http://job.toutia o.com/

内推码: FD72CWA