阅读 13

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

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

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

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

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

七、数据分区和复制

为了扩展DB,我们需要对它进行分区,以便它能够存储数十亿个URL的信息。那么,我们需要想出一个分区方案,将数据划分并存储到不同的DB服务器。

**a、范围分区:**我们可以根据哈希值的第一个字母将URL存储在单独的分区中。因此,我们在第一个分区中保存所有以字母“A”开头的URL,在另一个分区中保存以字母“B”开头的URL,以此类推。这种方法称为范围分区。我们甚至可以将某些不太频繁出现的字母组合到一个数据库分区中。我们需要一个静态分区方案,这样就可以始终以可预测的方式来存储/查找URL。

采用这种方法分区,主要的问题是它会导致DB服务器负载不均衡。例如,我们决定将所有以字母“E”开头的URL放在一个DB分区中,但是后来我们发现有太多URL以字母“E”开头。

**b、哈希分区:**在这个方案中,我们对存储的对象进行哈希计算。然后根据计算出的哈希值来进行分区。在我们的示例中,我们可以使用key或者短链接的哈希值来确定存储数据对象的分区。

通过哈希函数将URL随机分布到不同的分区中,例如,总是可以将任意的key映射到一个介于【1……256】之间的数字,这个数字代表存储对象的分区。

这种方法仍然会导致某些分区过载,这个问题可以通过使用 en.wikipedia.org来解决。

八、缓存

我们可以缓存经常访问的URL。通过使用一些现成的解决方案,如Memcached,可以存储完整的URL及其对应的哈希值。应用服务器在访问后端存储之前,可以快速检查缓存是否具有所需的URL。

我们应该有多少缓存?我们可以从每日流量的20%开始,并根据客户端的使用模式调整所需的缓存服务器数量。根据《如何设计一个类似于TinyURL的网址缩短系统(一)》中的内存估计,我们需要170GB的内存来缓存20%的日常流量。由于现在的服务器可以有256GB的内存,将所有170GB的数据缓存放入一台机器中是很容易的。或者,我们还可以使用多台较小的服务器来存储这些热门URL。

哪种缓存清除策略最适合我们的需要?当缓存满了,我们又希望替换一些更新或者更热门的URL时,需要如何选择呢?最近最少使用(Least Recently Used ,LRU)是一个合理的策略。在此策略下,我们首先丢弃最近最少使用的URL。我们可以使用Linked Hash Map或者其他相似的数据结构来存储URL和哈希值,它还将跟踪最近访问过的URL。

为了进一步提高效率,我们可以通过复制缓存服务器的方式在它们之间分配负载。

如何更新每个缓存副本?一旦出现缓存不命中,服务器都将访问后端数据库。无论何时发生这种情况,都可以更新缓存并将新条目传递给所有缓存副本。每个副本都可以通过添加新条目来更新其缓存。如果一个副本已经有这个条目,就可以忽略它。

(未完待续)

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

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