博客

CHAPTER 8: 《DESIGN A URL SHORTENER》第8章 《设计一个url伸缩器》

  • Post author:
  • Post category:其他




CHAPTER 8: DESIGN A URL SHORTENER

在这一章中，我们将解决一个有趣而经典的系统设计面试问题:设计一个像tinyurl这样的网址缩短服务。



步骤1 -理解问题并确定设计范围

系统设计面试的问题是故意留下开放式的。精心设计系统中，提出澄清性问题是至关重要的。


候选人:你能举例说明网址缩短器是如何工作的吗?


采访者:假设URLhttps://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long是原版URL。您的服务创建了一个较短长度的别名:https://tinyurl.com/ y7keocwj。如果你单击别名，它会将您重定向到原始URL。


候选人:交通流量是多少?


采访者:每天产生1亿个url。


候选人:缩短后的URL有多长?


采访者:越短越好。


候选人:缩短后的URL中允许使用哪些字符?


采访者:缩短的URL可以是数字(0-9)和字符(a- Z, a Z)的组合。


候选人:短网址可以删除或更新吗?


采访者:为了简单起见，让我们假设缩短的url不能被删除或更新

以下是基本用例:

  1. URL缩短:给定一个长URL =>返回一个更短的URL
  2. URL重定向:给定较短的URL =>重定向到原始URL
  3. 高可用性、可伸缩性和容错考虑



信封的背面估计

  • 写操作:每天生成1亿个url。
  • 每秒写操作数:1亿/ 24 /3600 = 1160
  • 读操作:假设读操作与写操作的比例为10:1，读操作每秒操作数:1160 * 10 = 11,600
  • 假设网址缩短服务将运行10年，这意味着我们必须支持1亿* 365 * 10 = 3650亿条记录。
  • 假设平均URL长度为100。
  • 10年以上存储需求:3650亿* 100字节* 10年= 365tb

对于你来说，和面试官讨论这些假设和计算是很重要的，这样你们可以达成一致。



步骤2 -提出高层次的设计并获得支持

在本节中，我们将讨论API端点、URL重定向和URL缩短流。



API端点

API端点促进了客户机和服务器之间的通信。我们将设计api restful。如果您不熟悉restful API，可以参考外部资料，例如参考资料[1]中的一个。URL缩短器主要需要两个API端点。

  1. 网址缩短。要创建一个新的短URL，客户机发送一个POST请求，其中包含

    一个参数:原始的长URL。API是这样的:

    POST api / v1 /data/shorten

    • 请求参数:{longUrl: longURLString}
    • 返回shortURL
  2. URL重定向。为了将短URL重定向到相应的长URL，客户端发送一个GET请求。API是这样的:

    GET api / v1 /shortUrl

    • 返回longURL用于HTTP重定向



URL重定向

如figure8-1所示，在浏览器中输入一个tinyurl。一旦服务器接收到一个tinyurl请求，它将短URL更改为301重定向的长URL。

在这里插入图片描述
客户端和服务器之间的详细通信如figure8-2所示。

在这里插入图片描述

这里值得讨论的一件事是301重定向和302重定向。


301重定向

。301重定向显示所请求的URL被“永久”移动到长URL。由于它是永久重定向的，因此浏览器会缓存响应，并且对同一URL的后续请求将不会发送到URL缩短服务。相反，请求被直接重定向到长URL服务器。


302重定向

。302重定向意味着URL被“暂时”移动到长URL，这意味着对同一URL的后续请求将被发送到URL缩短服务第一。然后，它们被重定向到长URL服务器。

每种重定向方法都有其优缺点。如果优先考虑的是减少服务器负载，使用301重定向是有意义的，因为只有相同URL的第一个请求被发送到URL缩短服务器。然而，如果分析是重要的，302重定向是一个更好的选择更容易跟踪点击率和点击来源。

实现URL重定向最直观的方法是使用哈希表。假设哈希表存储<shortURL, longURL>对，URL重定向可以通过后:

  • GET longURL: longURL = hashTable.get(shortURL)
  • 获得长URL后，执行URL重定向。



网址缩短

让我们假设短URL是这样的:www.tinyurl.com/{hashValue}。为了支持URL缩短用例中，我们必须找到一个哈希函数fx，将长URL映射到hashValue，如figure8-3所示。

在这里插入图片描述

哈希函数必须满足以下要求:

  • 每个longURL必须散列到一个hashValue。
  • 每个hashValue都可以映射回longURL。

对哈希函数的详细设计进行了深入的讨论。



步骤3 -设计深度潜水

到目前为止，我们已经讨论了URL缩短和URL的高级设计重定向。在本节中，我们将深入探讨以下内容:数据模型、哈希函数、URL缩短和URL重定向。



数据模型

在高级设计中，所有内容都存储在散列表中。这是一个很好的起点;然而，由于内存资源有限，这种方法在实际系统中是不可行的和昂贵的。更好的选择是在关系中存储<shortURL, longURL>映射数据库。figure8-4展示了一个简单的数据库表设计。表的简化版本包含3列:id, shortURL, longURL。

在这里插入图片描述



哈希函数

哈希函数用于将长URL哈希为短URL，也称为hashValue



哈希值长度

hashValue由字符[0-9,a-z, a-z]组成，其中10 + 26 + 26 = 62可能的字符。要算出hashValue的长度，找到最小的n，使得62^n≥3650亿。系统必须支持最多3650亿个url信封的估计。hashValue的长度和对应的值如table8-1所示它可以支持的最大url数。

在这里插入图片描述

当n = 7,62 ^ n = ~3.5万亿时，3.5万亿足以容纳3650亿个url，所以hashValue的长度是7。

我们将探索URL缩短器的两种类型的哈希函数。第一个是“hash +”碰撞分辨率”，第二个是“62进制转换”。让我们逐一来看一下一个。



哈希+碰撞分辨率

为了缩短长URL，我们应该实现一个散列函数，将长URL散列到7-字符串。一个直接的解决方案是使用众所周知的哈希函数，比如CRC32，MD5或SHA-1。下表比较了应用不同哈希后的哈希结果此URL上的函数:https://en.wikipedia.org/wiki/Systems_design。

在这里插入图片描述

如table8-2所示，即使是最短的哈希值(来自CRC32)也太长(大于7)字符)。我们怎样才能缩短它?第一种方法是收集哈希值的前7个字符;然而，这种方法可能导致哈希冲突。为了解决哈希冲突，我们可以递归地附加一个new预定义的字符串，直到没有发现更多的冲突。figure8-5说明了这个过程

在这里插入图片描述
这种方法可以消除碰撞;但是，查询数据库进行检查的成本很高如果每个请求都存在一个shortURL。一种叫做bloom filters的技术可以改进的性能。布隆过滤器是一种节省空间的概率技术，用于测试元素是否存在集合中的一员有关更多细节，请参阅参考资料[2]。



62进制转换

基转换是URL缩短器常用的另一种方法。基地转换帮助在不同的数字表示系统之间转换相同的数字。基地使用62转换，因为hashValue有62个可能的字符。让我们用解释转换如何工作的示例:将1115710转换为62进制表示(1115710在10进制中表示11157)。

  • 从它的名字可以看出，base 62是一种使用62个字符进行编码的方法。这些映射是:0 – 0,…， 9- 9,10 -a, 11-b，…， 35-z, 36-A，…， 61-Z，其中“a”代表10，“Z”代表61，等。
  • 1115710 = 2 × 622+ 55 × 621 + 59 × 620= [2, 55, 59] -> [2, T, X] in base 62

    表示。对话过程如figure8-6所示。

    在这里插入图片描述
    因此，短URL是https://tinyurl.com /2TX



两种方法的比较

两种方法的区别如table8-3所示。

哈希+碰撞分辨率 62进制转换
固定短URL长度 短的URL长度不固定，他和ID一起上升
它不需要固定的ID生成器 此选项依赖于唯一的ID生成器
碰撞是可能的，必须解决 冲突是不可能的，因为ID是唯一的
不可能找出下一个可用的的短url,因为它不依赖于ID 如果新条目ID增加1，则很容易找出下一个可用的短的URL，这可能是一个安全问题



网址缩短深度挖掘

作为系统的核心部分之一，我们希望URL缩短流是合乎逻辑的简单和功能。在我们的设计中使用了Base 62转换。我们构建了以下内容流程如figure8-7所示。

在这里插入图片描述

  1. longURL是输入。
  2. 系统检查longURL是否在数据库中。
  3. 如果是，则表示之前将长url转换为短url。在本例中，获取从数据库中获取shortURL并将其返回给客户端。
  4. 如果不是，则longURL是新的。一个新的唯一ID(主键)由唯一生成身份证生成器。
  5. 使用base 62转换将ID转换为shortURL。
  6. 用ID、shortURL和longURL创建一个新的数据库行

为了使流程更容易理解，让我们看一个具体的例子。

  • 假设输入的longURL为:https://en.wikipedia.org/wiki/Systems_design
  • 唯一ID生成器返回ID: 2009215674938。
  • 使用base 62转换ID为shortURL。ID为2009215674938转换为“zn9edcu”。
  • 将ID、shortURL和longURL保存到数据库中，table8-4所示

    在这里插入图片描述

    分布式唯一ID生成器值得一提。它的主要功能是生成全局唯一的id，用于创建短url。在高度分布的环境中，实现唯一ID生成器是具有挑战性的。幸运的是，我们已经做到了在“第7章:设计一个分布式的唯一ID生成器”中讨论了一些解决方案系统”。你可以回过头来复习一下。



URL重定向

URL重定向的详细设计如figure8-8所示。因为有更多的阅读写入，<shortURL, longURL>映射存储在缓存中，以提高性能。

在这里插入图片描述

URL重定向的流程总结如下:

  1. 用户单击URL短链接https://tinyurl.com/zn9edcu
  2. 负载均衡器将请求转发给web服务器。
  3. 如果短url已经在缓存中，则直接返回长url。
  4. 如果短url不在缓存中，则从数据库中获取长url。如果不是在数据库中，很可能是用户输入了无效的shortURL。
  5. longURL返回给用户。



步骤4 -打包

在本章中，我们讨论了API设计，数据模型，哈希函数，URL缩短，和URL重定向。

如果在面试结束时有额外的时间，这里有一些额外的谈话要点。

  • 速率限制器:我们可能面临的一个潜在安全问题是，恶意用户发送数据包大量的URL缩短请求。速率限制器有助于过滤基于IP地址或其他过滤规则的请求。如果你想回忆一下关于速率限制，请参见“第四章:设计速率限制器”。
  • Web服务器扩展:由于Web层是无状态的，所以很容易扩展Web层添加或删除web服务器。
  • 数据库扩展:数据库复制和分片是常用的技术。
  • 分析:数据对商业成功越来越重要。集成分析URL缩短器的解决方案可以帮助回答一些重要的问题，比如有多少人们点击链接?他们什么时候点击链接?等。
  • 可用性、一致性和可靠性。这些概念是任何大型游戏的核心系统的成功。我们在第一章已经详细讨论过了，请大家复习一下关于这些话题。

    恭喜你走了这么远!现在给自己点鼓励吧。好工作!



Reference materials 参考资料

[1] A RESTful Tutorial: https://www.restapitutorial.com/index.html

[2] Bloom filter: https://en.wikipedia.org/wiki/Bloom_filter


版权声明：本文为weixin_43178103原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。