文档章节

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

A
 APEMESH
发布于 10/15 21:58
字数 1936
阅读 43
收藏 0

原文链接:
https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR

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

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

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

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

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

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

https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904/

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

http://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的定义:

<section style="margin-top: 10px;margin-bottom: 20px;"><code class=""><span style="font-size: 15px;">createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)</span></code></section>

相关参数:

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

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

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

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

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

返回:(字符串)

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

<section style="margin-top: 10px;margin-bottom: 20px;"><code class=""><span style="font-size: 15px;">deleteURL(api_dev_key, url_key)</span></code></section>

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

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

五、数据库设计

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

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

 

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

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

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

数据库架构:

 

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

previewpreview

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

(未完待续)

© 著作权归作者所有

A
粉丝 0
博文 33
码字总数 56316
作品 0
闵行
部门经理
私信 提问
视频教程:Java七大外企经典面试套路之基础篇

Java是Sun公司推出的一种编程语言。它是一种通过解释方式来执行的语言,语法规则和C++类似。同时,Java也是一种跨平台的程序设计语言。 本教程主要给大家讲解了Java七大外企经典面试套路,精...

一定听你
2017/06/14
0
0
Java系列文章(全)

JVM JVM系列:类装载器的体系结构 JVM系列:Class文件检验器 JVM系列:安全管理器 JVM系列:策略文件 Java垃圾回收机制 深入剖析Classloader(一)--类的主动使用与被动使用 深入剖析Classloader(二...

www19
2017/07/04
0
0
【提升技能必备】这几本Android高级进阶的好书值得一看

Android开发的书籍有很多,下面简单的就我看过的感觉写的很全面,很深入,很有启示意义的几本书推荐给大家,希望大家在闲暇之时也能买来看看。(只是介绍书籍,想买的自己百度书名。别误会。...

AWeiLoveAndroid
2018/01/02
0
0
年末干货!Java技术栈2017年度精选干货总结

Java技术栈2017年总结 2017年即将收尾了 这一年,满满的都是干货 这一年,我们的更新不曾停歇 这一年,你装逼内功应已有所成 我是小猿,下面是本年度的分享知识图谱 看完是不是有点蒙逼了?没...

架构之路
2017/12/24
0
0
Java面试越来越难怎么办?80% 应聘者不知道的面试加分项

     “你懂算法吗?服务器这块咋样?项目经验有吗?软件开发这块呢?懂分布式吗……”   假如恰好你涉猎广泛,以上都懂。但也极有可能会在手写红黑树上掉坑。      [事件援引:H...

java进阶架构师
09/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

83、Mybatis和Hibernate重要区别

Mybatis;入门简单,程序容易上手开发,节省开发成本。Mybatis需要程序猿自己编写sql语句,是一个不完全的ORM框架,对sql修改和优化非常容易实现。 Mybatis适合开发需求变更频繁的系统,比如...

lianbang_W
今天
5
0
设计模式之状态模式

定义 Allow an object to alter its behavior when its internal state changes.The object will appear to change its class.(当一个对象内在状态改变时允许其改变行为,这个对象看起来像改...

陈年之后是青葱
今天
6
0
Python常用模块之os.path

os.path.abspath(path) 输入相对路径,返回绝对路径 Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit (AMD64)] on win32Type "copyright", "credits" or "lic......

松鼠大帝
今天
11
0
001. JAVA程序运行原理分析

1. 先来看看JVM运行时数据区的结构 线程独占: 每个线程都有它独立的空间,随线程生命周期而创建和销毁。 线程共享: 所有线程能访问这块内存数据,随虚拟机GC 而创建和销毁。 JVM 用来存储加载...

紫穹
今天
24
0
SDN核心思想&Mininet

2.1ONF定义的SDN基本架构: 应用层:实现网络流量的灵活控制,使网络作为管道智能 控制层:网络虚拟化实现方式,核心技术OpenFlow 转发层新型创新架构,实现网络设备控制与转发分离 2与3之间...

Firefly-
昨天
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部