阅读 133

经典系统设计面试题解析:如何设计TinyURL(一)

原文链接: www.educative.io/cour...

编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助读者更深入地了解在系统需求分析和设计中,需要考虑的各个方面的细节。

本文将为大家详细讲解如何设计一个类似于TinyURL的URL缩短服务。URL缩短服务提供一个非常短小的URL以代替原来的可能较长的URL,将长的URL地址缩短。

**类似的服务有:**bit.ly,goo.gl,qlink.me,等等。

一、为什么需要URL缩短服务?

URL缩短服务是用来为长URL创建简短别名的。我们称这些缩短的别名为“短网址”。当用户点击这些短网址时,能够重定向到原始的URL。相较于原始URL,短网址在显示、打印、发送消息或微博时能够节省大量空间。另外,用户输错短网址的可能性也比较小。

举个例子,如果我们通过TinyURL来缩短下面这个网址:

www.educative.io/coll...

我们可以得到以下的短网址:

tinyurl.com/jlg8zpc

上面这个短网址的长度几乎只有实际URL的三分之一。

URL缩短用于优化跨设备的链接,通过跟踪单个链接来分析受众和活动性能,并隐藏关联的原始URL。

如果你以前没有使用过http://tinyurl.com/这个网站,请尝试设计并创建一个新的网址缩短系统,然后,花一些时间浏览它们提供的各种服务选项。这会帮助你更好地理解本章节的内容。

二、系统的需求和目标

设计的URL缩短系统应符合以下需求:

功能性需求:

1、给定一个原始URL,该系统能够生成一个较短且唯一的短网址。这个短网址的长度应该足够短,以便轻松复制和粘贴到应用程序中。

2、当用户访问一个短网址时,该系统应该将它们重定向到原始链接。

3、用户可以为他们的URL选择一个自定义的短网址。

4、在标准的默认时间间隔后,对应的短网址过期。过期时间允许用户设置。

非功能性需求:

1、该系统必须是高度可用的。因为一旦我们的服务宕机,那么所有的URL重定向都会失败。

2、URL重定向应该在最小延迟的情况下实时进行。

3、短网址应该是不可预测

扩展需求:

1、能够进行分析;例如,重定向发生了多少次。

2、其他系统可以通过REST API访问我们的服务。

三、容量估计及限制

设计的系统将包含大量读取操作。与新的URL缩短相比,将会有大量的重定向请求。假设读和写的比率为100:1。

流量估计:

假设每个月将有5亿个新的短网址产生,读/写比率为100:1的话,预计在同一时期将有500亿个重定向请求:

100 * 5 亿 ≥ 500 亿

对于我们设计的系统,每秒查询数(QPS)又是多少呢?每秒新的短网址数:

5 亿 / (30 天 24 小时 3600 秒 ) ≌ 200 URLs/s

考虑到100:1的读/写比例,每秒URL重定向请求数将是:

100 * 200 URLs/s = 20 K/s

存储估计:

假设将每个短网址请求存储5年,每个月将有5 亿个新的短网址产生,由此可以得出,预计存储的对象总数将达到300亿个:

5 亿 5 年 12 月 = 300 亿

假设每个存储对象的大小大约是500 字节(这只是一个大致的估计——我们稍后将深入研究它)。那我们需要15 TB 的总存储:

300 亿 * 500 字节 = 15 TB

带宽估计:

对于写请求,前面我们计算出,预计每秒有200个新短网址产生,由此得出,总输入数据将为100 KB/s:

200 * 500 字节 ≌ 100 KB/s

对于读请求,前面我们计算出,预计每秒URL重定向请求是2 万个,由此得出,总输出数据为10MB/s:

2 万 * 500 字节 ≌10 MB/s

内存估计:

如果想缓存一些经常访问的热门URL,那需要多少内存来存储它们呢?

这里,我们遵循80-20规则,也就是说20%的URL产生80%的流量,我们想要缓存这20%的热门URL。

由于每秒有2万个重定向请求,那么每天收到的重定向请求有17亿个:

2 万 3600 秒 24 小时 ≌ 17 亿

缓存其中20%的请求所需要的内存则为170 GB:

0.2 17 亿 500 字节 ≌ 170GB

这里需要注意一点,由于会有许多重复的请求(也就是相同的URL),因此,实际内存使用量将少于170 GB。

高级别估计:

假设每月有5亿个新URL,读/写比例100:1,下面是对此服务的估计概要:

四、系统API

一旦确定了系统的需求,那么定义系统API总是一个好主意。它应该明确地说明我们对系统的期望。

我们可以使用SOAP或REST API来公开服务的功能。以下是用于创建和删除URL的API的定义:

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

相关参数:

api_dev_key(字符串):注册账户的API开发人员密钥。除此之外,它还将用于根据分配的配额限制用户。

original_url(字符串):要缩短的原始URL。

custom_alias(字符串):URL的可选自定义键。

user_name(字符串):可选的用户名,用于编码。

expire_date(字符串):可选过期日期的缩短URL。

返回:(字符串)

成功插入将返回短网址;否则,将返回错误代码。

deleteURL(api_dev_key, url_key)

其中“url_key”表示的是要检索的缩短URL的字符串。成功删除将返回“URL Removed”。

**那我们要如何发现和防止滥用呢?**恶意用户可以通过使用当前设计中的所有URL密钥让我们失去业务。为了防止滥用,我们可以通过api_dev_key来限制用户。每个api_dev_key可以在某个时间段内限制URL创建和重定向的数量(每个开发人员密钥可以设置为不同的持续时间)。

五、数据库设计

对于我们将要存储的数据,对其性质做一些观察:

1、需要存储数十亿的记录。

2、存储的每个对象都很小(小于1K)。

3、除了存储创建URL的用户之外,记录之间没有任何关系。

4、需要大量的读取操作。

数据库架构:

我们需要两个表:一个用于存储有关URL映射的信息,另一个用于存储创建短网址的用户数据。

**那我们应该使用什么样的数据库呢?**因为我们预计存储数十亿的数据,而且我们不需要使用对象之间的关系,所以像DynamoDB,Cassandra或者Riak这样的通过key-value形式存储的NoSQL是更好的选择。选择NoSQL也更容易进行扩展。

(未完待续)

关注下面的标签,发现更多相似文章
评论