原文链接：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=design和http://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所反映的）。
（未完待续）
未经同意，本文禁止转载或摘编。