经典系统设计面试题解析：如何设计TinyURL（三）
原文链接：
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,等等。
七、数据分区和复制
为了扩展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。为了进一步提高效率，我们可以通过复制缓存服务器的方式在它们之间分配负载。
如何更新每个缓存副本？一旦出现缓存不命中，服务器都将访问后端数据库。无论何时发生这种情况，都可以更新缓存并将新条目传递给所有缓存副本。每个副本都可以通过添加新条目来更新其缓存。如果一个副本已经有这个条目，就可以忽略它。
（未完待续）
关于系统设计的内容今天就分享到这里，第三部分的内容小编将在下期为您呈现。如您对小编分享的文章感兴趣，您可以搜索关注知乎专栏《微服务应用开发和API管理》，也可以扫描下方二维码关注灵长科技官方公众号，获取最新更新动态。
-
-
未经同意，本文禁止转载或摘编。