文档章节

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

A
 APEMESH
发布于 10/23 00:45
字数 1989
阅读 14
收藏 0

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

 

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

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

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

六、基本系统设计与算法

我们需要解决一个问题,如何为给定的URL生成一个较短且唯一的字符串。

在第一节的TinyURL示例中,缩短的URL是:http://tinyurl.com/jlg8zpc。这个短链接中的最后七个字符jlg8zpc就是我们想要生成的字符串。接下来,我们一起探讨两个解决方案:

a、编码实际的URL

通过哈希算法(例如MD5或SHA256算法等),我们计算给定URL的哈希值,然后对这个哈希值编码并显示,这种编码方式可以是Base36 ([a-z ,0-9]) 或者Base62 ([A-Z, a-z, 0-9]),如果我们希望添加“+”“/”符号类的字符,还可以使用Base64编码。那么,生成字符串的合理长度是多少呢?6个、8个或者10个字符是比较合适的。

如果我们使用Base64编码,那么一个6个字符长度的字符串有64^6≈687亿种可能的组合,一个8个字符长度的字符串有64^8≈281万亿种可能的组合。

对于我们将要设计的系统来说,6个字符长度、687亿种可能组合的字符串,就足够使用了。

如果我们使用MD5算法作为哈希函数,它将产生一个128bit的哈希值。通过Base64编码,将得到一个超过21字符的字符串(因为每个Base64字符编码6bit哈希值)。如果,我们生成字符串的长度只有8个字符的空间,那么对这超过21个字符的字符串将如何进行选取呢?一种方法,我们可以选取前6(或8)个字符。这种方法可能会导致最终生成的字符串重复,为了解决这个问题,我们可以从编码字符串中选择一些其他字符或交换一些字符。

除了刚刚说的生成字符串重复的问题,还会碰到以下两种问题:

1、当多个用户输入相同的URL时,将得到相同的缩短URL,这是不被允许的。

2、如果URL的一部分是URL编码的呢?例如http://www.educative.io/distributed.php?id=designhttp://www.educative.io/distribu.php%3fid%3ddesign,这两个URL除了URL编码之外其他都是相同的,但得到的缩短URL不相同。

解决上述问题的方法:向每个输入URL添加一个递增的序列号,使其唯一,然后生成它对应的哈希值。注意,这里我们不需要将这个序列号存储在数据库中。这种方法可能会导致序列号不断增加,甚至有可能溢出。并且,附加一个递增的序列号也会影响服务的性能。

另一种解决方法是:将用户id(这个应该是唯一的)附加到输入URL。但是,如果用户没有登录的话,则必须要求用户选择一个唯一的key。在这之后,如果用户选择的key有冲突,那系统必须继续生成其他的key,直到得到唯一的结果。

b、离线生成字符串

我们可以创建一个独立的密钥生成服务(KGS),它预先生成随机的6个字母长度的key,并将它们存储在数据库(我们称之为key-DB)中。无论何时,我们想要缩短一个URL,都将使用一个已经生成的key。这种方法使得缩短URL变得非常简单和快速。我们不仅不编码URL,而且不用担心生成的key重复或冲突。KGS将确保插入到key-DB中的所有key都是唯一的。

接下来,我们来考虑下并发的问题。key-DB中的key一旦被使用,那么它就应该在key-DB中进行标记,确保不会重复使用。如果多个服务器同时读取key-DB中的key的话,我们可能会碰到两个或者多个服务器试图从key-DB读取相同的key。针对这个问题,我们又要如何解决呢?

服务器可以使用KGS读取/标记数据库中的key。在KGS中创建两个表来存储key:一个用于未使用的,一个用于已使用的。只要KGS向其中一个服务器提供key,它就可以将这些已使用的key移动到used keys表里。KGS总是可以在缓存中保留一些key,以便能够在服务器需要时快速提供key。

为了简单一点,只要KGS在缓存中加载一些key,就可以将这些key移动到used keys表。这确保每个服务器都有唯一的key。如果KGS在将所有加载的key分配给某个服务器之前宕机了,那么这些未使用的key就浪费了。不过,这种情况是可以接受的,因为我们有大量的key以供使用。

KGS还必须确保不向多个服务器提供相同的key。为此,它必须同步(或锁定)保存key的数据结构,然后从其中删除该key并将其交给服务器。

key-DB的内存大小应该是多少呢?使用Base64编码,我们可以生成687亿个唯一的6个字母长度的key。如果我们需要一个字节来存储一个字符,那么我们存储这些key所需的内存大小为:

6 (字符/key)*687 亿 =412 GB

另外,KGS是单点失效的。为了解决这个问题,我们可以有一个KGS的备用副本,无论主服务器何时宕机,备用服务器都可以接管来生成和提供key。

每个应用服务器都可以从key-DB缓存一些key吗?是的,这肯定能加快运行速度。在这种场景下,如果应用服务器在使用所有key之前宕机了,导致我们丢失了这部分的key,这也是可以接受的。因为我们拥有687亿个唯一的key。

如何执行key查找呢?我们可以在数据库或key-value存储中查找key,以获得原始的URL。如果该key存在,则向浏览器发出“HTTP 302 Redirect”状态,将请求的“Location”字段中存储的URL传递回来。如果该key不在我们的系统中,发出“HTTP 404 not Found”状态或将用户重定向回主页。

我们应该对自定义的字符串施加大小长度限制吗?我们的服务支持自定义缩短URL。用户可以选择任何他们喜欢的key,但并不强制提供自定义功能。但是,对自定义key的大小长度进行限制是有必要的,这样可以确保我们拥有一致的URL数据库。假设用户可以为每个key指定最多16个字符(如前一篇中提到的数据库Schema所反映的)。

(未完待续)

未经同意,本文禁止转载或摘编。

© 著作权归作者所有

A
粉丝 0
博文 32
码字总数 54579
作品 0
闵行
部门经理
私信 提问
Java系列文章(全)

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

www19
2017/07/04
0
0
视频教程:Java七大外企经典面试套路之基础篇

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

一定听你
2017/06/14
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
【提升技能必备】这几本Android高级进阶的好书值得一看

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

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

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

架构之路
2017/12/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

前端的一些雕虫小技,从100%和滚动条说起

1、100%和滚动条 当我们在css中把html和body同时设为100%时,会出现滚动条 html, body { width: 100%; height: 100%; } 原因是html和b...

wphmoon
49分钟前
6
0
电力区块链应用案例【2019】

随着区块链技术的日益普及,出现了大量创业企业尝试使用区块链技术来解决能源与电力行业中存在的问题。在本文中,我们将介绍其中的三个能源区块链项目。 能源行业以价格不透明著称:消费者很...

汇智网教程
今天
7
0
聊聊rocketmq的adjustThreadPoolNumsThreshold

序 本文主要研究一下rocketmq的adjustThreadPoolNumsThreshold DefaultMQPushConsumer rocketmq-client-4.5.2-sources.jar!/org/apache/rocketmq/client/consumer/DefaultMQPushConsumer.ja......

go4it
今天
10
0
关于早起

早起是非常好的事情,但是像如果前一天睡得晚,或者第二天早上是非常冷的时候,那就不是很美好了。 但是本身早起是一件非常棒的事情,我记得我每次早起 如果不觉得困的话,世界是那么安静,脑...

T型人才追梦者
今天
7
0
Java输入输出

JDK中的InputStream/OutputStream构成了IO输入输出继承层次的基础。它们都是面向字节序列的,每次可以从序列中读入或者写出一个字节或者指定大小的字节数组。但是面向字节流的输入输出不便于...

ytuan996
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部