本文参考自:
https://hufangyun.com/2017/short-url/

https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR

什么是短链接

就是把普通网址,转换成比较短的网址。比如:http://t.cn/RlB2PdD 这种,在微博这些限制字数的应用里。好处不言而喻。短、字符少、美观、便于发布、传播。
百度短网址 http://dwz.cn/
谷歌短网址服务 https://goo.gl/ 号称是最快的

原理解析:浏览器怎么访问短URL?

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

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

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

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

第一步:需求与目标

功能需求

1.给定网址,系统应将其转换为短链接,这个链接应该是唯一且不冲突的。
2.用户访问短链接的时候,应将其导向原始链接。
3.用户应可以在短连接中自由选择一个作为长网址的替代。
4.短连接经过一段时间之后会失效,用户应可以指定有效时间。

非功能需求

1.服务应具有高可用性(high availability)。
2.网址跳转(URL redirecting)应该具有低延迟(low latency)
3.短网址不应该被看出与原网址的关系(not guessable/predictable

额外需求

1.一些分析,例如:一分钟会有多少次跳转链接访问?
2.此服务应该可以被其他服务通过API访问。

第二步:容量估计与约束

此服务应该是频繁读操作。相比起加入新的URL而言,访问已有URL的短链接将会频繁很多。

我们可以假设读写操作的数量比为100:1。

流量估计

1.每月生成500M个新的短URL,每秒~200
2.读写操作数量比100:1
3.每月重定向(读)为500Mx100=50B, 每秒~20K

存储估计

1.假设每个短URL以及原始链接会被保存5年,5年内生成的短URL总量为500Mx5x12=30B
2.假设每个URL需要500B,总共需要的存储空间为500Bx30B=15TB

带宽估计

1.每秒会有~200写操作(新URL),所以总共上传数据带宽为100KB/s
2.对于读操作,~20K/s,下载带宽为~10MB/s

内存估计

我们打算对一些高访问的热门URL做cache操作,这些URL会存在于内存里面,而不是硬盘上,便于快速访问。

假设URL也遵从80-20 Rule,那么20%的URL产生了80%的流量,我们将对top20%的URL做cache。

每个月生成的新URL为500M,top20%~100M, 总共需要100Mx500B=500MB。

如果我们想cache更长时段的URL,则需要更大的空间。

第三步:系统API

我们可以以如下API生成/删除短URL:

createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)
deleteURL(api_dev_key, url_key)

Parameters:
api_dev_key (string): The API developer key of a registered account. This will be used to, among other things, throttle users based on their allocated quota.
original_url (string): Original URL to be shortened.
custom_alias (string): Optional custom key for the URL.
user_name (string): Optional user name to be used in the encoding.
expire_date (string): Optional expiration date for the shortened URL.

Returns: (string)
A successful insertion returns the shortened URL; otherwise, it returns an error code.

第四步:数据库设计

需要存储的数据的性质:

1.会有30B条记录
2.每条记录所占空间很小
3.记录与记录之间没有关系(relation)
4.服务是频繁读

数据库架构

我们需要两个表:

1.URL mapping表
2.用户信息表

数据库选择

既然我们需要存储三百亿条记录,而且记录与记录之间又没有关系,NoSQL的数据库是我们的最佳选择:DynamoDB, Cassandra 或者 Riak

第五步:算法

这一部分我们解决如何把一个长链接映射成短链接的算法问题。

一般来说生成的短链接有如下格式:http://tinyurl.com/jlg8zpc

最后斜杠后面的那几位随机乱码是我们这一步要生成的对象。

Hash编码

利用Hash编码软件,例如MD5或者SHA256,对原始长链接进行编码。

一个必须考虑的问题是,生成多长的Hash码,才能满足我们系统的需求?

编码的base可以是base36 ([a-z ,0-9])或者base62 ([A-Z, a-z, 0-9]),如果再加上+和/,我们可以使用base64的编码。

  • 使用base64的编码, 6字母编码有 64^6 = ~68.7 billion 不同的字符串。
  • 使用base64的编码, 8字母编码有 64^8 = ~281 billion 不同的字符串。
    因为我们的系统只需要存储30B条记录,6字母编码就足够了。

采取此算法应注意Hash collision问题。

离线生成键

我们也可以使用独立的键生成服务(Key Generation Service)。它提前生成随机的6位字符串,然后存储在键数据库里,需要产生短链接的时候,就从里面拿一个来用。这会使得整个事情变得非常简单便捷:我们不仅不需要为长链接编码,而且也不需要担心重复或者Hash collision这样的事情。

并发问题

一个键被使用之后,数据库应该把它标记为已经被使用。但是,如果有多个服务器同时试图读写数据库里的键,并发问题就产生了。

一种解决办法是用唯一的KGS,而且KGS保证不会将同一个key分配给不同的服务器请求,这需要KGS有某种lock。

额外估计

  • KGS大小 :6 x 68.7B = 412 GB
  • KGS Failure: 备份KGS服务器,当主服务器failure的时候,上线备份服务器。
  • 每个服务器都可以cache一些key以加快访问速度

    第六步:数据分区和副本

    为了适用于大规模场景,我们可能需要将数据库进行分区或者增加副本。

    根据首字母分区

    根据Hash key的首字母对数据库进行分区。更进一步,我们可以把更少访问的首字母分到一个区,更频繁访问的字母分成单独的区,以此来平衡分区大小。

美中不足的是无法严格控制分区大小,比如以e开头的字母会很多,远超过其他字母。

根据Hash分区

根据Hash编码来分区,这样分区大小是可预计且可控的,会更加均衡一些。

第七步:缓存

应该对经常被访问到的链接进行cache,可以提高访问速度。

缓存大小

和前面估计的一样,我们会cache top20%的链接。这部分估计很小,很容易放进内存里。

什么时候清理缓存?

当cache满了之后,我们要删除一些链接并放入新的,怎么选择呢?可以使用LRU。

更新副本缓存

第八步:负载均衡器

我们可以在系统的三个地方添加负载均衡器(load balancer):

1.在用户层与代理层之间
2.在应用服务器与数据库之间
3.在应用服务器与缓存之间
一开始,我们可以使用最简单的round-robin方式,将访问请求平均分配到各个服务器上面。这个方法的优点是没有overhead,而且容易实现。如果一个服务器坏了,就把它从负载均衡器里面拿掉。

这个方法的缺点是没有考虑到每个服务器的负载问题。

第九步:清理数据库

数据库累积太多数据的时候就应该被清理一下以腾出空间。当链接失效或者过时了,我们也应该清理掉相关数据。

我们应该做lazy cleanup来缓解数据库压力, 具体表现为:

1.当用户试图访问过时链接的时候,清理掉它并给用户返回错误信息。
2.建立一个单独的清理服务。这个服务定时周期运行,而且应该非常轻量。
3.我们可以给每个链接设置失效时限,过时自动清理。
4.清理掉的链接使用的key可以放回备用key库里面。
5.我们也可以清理长期没人访问的链接。

第十步:遥测系统

利用遥测系统可以获得更多数据并作出分析,以提高系统性能,比如:

1.用户地理位置分布?用户国别?用户访问时间?浏览器?平台?
2.什么是流行的URL?如果忽然获得大量访问,数据库能不能支持?

第十一步:安全与权限

我们可以创立私密链接,或者只给一部分用户访问的链接吗?

为了达到此需求,我们需要给链接加上额外的permission级别。我们也可以创建单独的表存储允许被访问的用户信息。

转自:https://zhuanlan.zhihu.com/p/91947139

最后修改:2020 年 05 月 20 日
如果觉得我的文章对你有用,请随意赞赏