让我们设计一个像TinyURL这样的URL缩短服务。此服务将提供短别名重定向到长URL。类似服务：bit.ly、goo.gl、qlink.me等。难度等级：轻松
1.为什么我们需要将URL缩短？
URL缩短用于为长URL创建较短的别名。我们称这些缩短的别名为“短链接”。当用户点击这些短链接时，会重定向到原始URL。显示、打印、发送消息或推特时，短链接可节省大量空间。此外，用户不太可能错误键入较短的URL。
例如，如果我们通过TinyURL缩短此页面：
- https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600 916475904/
我们可以获得结果：
- http://tinyurl.com/jlg8zpc
缩短后的URL几乎是实际URL大小的三分之一。
URL缩短用于跨设备优化链接、跟踪单个链接以分析受众和活动绩效，以及隐藏关联的原始URL。如果您以前没有使用过tinyurl.com，请尝试创建一个新的缩短URL，并花一些时间浏览他们提供的各种服务选项。
2.系统的要求和目标
你应该在面试开始时明确要求。一定要问问题，找出面试官心目中的系统的确切范围。
我们的URL缩短系统应满足以下要求：
功能要求：
- 1.给定一个URL，我们的服务应该生成一个更短且唯一的别名。这称为短链接。
- 2.当用户访问短链接时，我们的服务应将其重定向到原始链接。
- 3.用户可以选择为其URL选择自定义短链接。
- 4.链接将在标准默认时间间隔后过期。用户应该能够指定有效期。
非功能性要求：
- 1.系统应具有高可用性。这是必需的，因为如果我们的服务关闭，所有URL重定向将开始失败。
- 2.URL重定向应以最小延迟实时发生。
- 3.缩短的链接不应是可猜测的（不可预测的）。
扩展要求：
- 1.分析；e、 例如，重定向发生了多少次？
- 2.我们的服务也应该可以通过REST API被其他服务访问。
3.容量估算和限制条件
我们的系统将被大量阅读。与新的URL缩短相比，将有大量重定向请求。假设读写比为100:1。
流量估计：
假设每月有5亿个新的URL缩短，读/写比率为100:1，我们预计在同一时期会有50B的重定向：
100*500M=>50B
我们系统的每秒查询（QPS）是多少？每秒新URL缩短数：
5亿/（30天*24小时*3600秒）=~200个URL/s
考虑到100:1的读/写比率，每秒URL重定向将为：
100*200 URL/s=20K/s
存储估计：
假设我们将每个URL缩短请求（以及相关的缩短链接）存储5年。由于我们预计每月有5亿个新URL，因此我们预计存储的对象总数将达到300亿：
5亿*5年*12个月=300亿
让我们假设每个存储的对象大约有500字节（这只是一个大概的估计——我们将在后面深入研究）。我们需要15 TB的总存储容量：
300亿*500字节=15 TB
带宽估计：
对于写请求，由于我们预计每秒有200个新URL，因此我们服务的总传入数据将为每秒100KB：
200*500字节=100 KB/s
对于读取请求，由于我们预计每秒会有约20K个URL重定向，因此我们服务的总传出数据将为每秒10MB：
20K*500字节=~10 MB/s
内存估计：
如果我们想缓存一些经常访问的热门URL，我们需要多少内存来存储它们？如果我们遵循80-20规则，即20%的URL生成80%的流量，那么我们希望缓存这些20%的热门URL。
由于每秒有2万个请求，我们每天将收到17亿个请求：
20K*3600秒*24小时=~17亿
要缓存20%的请求，我们需要170GB的内存。
0.2*17亿*500字节=~170GB
这里需要注意的一点是，由于会有很多重复的请求（相同的URL），因此，我们的实际内存使用量将小于170GB。
高层评估：
假设每月新增5亿个URL，读写比为100:1，下面是我们服务的高层评估摘要：
新网址 URL重定向传入数据传出数据存储5年缓存内存
4.系统API
新的URL 200/s
URL重定向 20K/s
进入数据 100KB/s
出数据 10MB/s
存储5年 15TB
内存估计 170GB
一旦我们确定了需求，定义系统API总是一个好主意。这应该明确说明系统的期望值。
我们可以使用SOAP或RESTAPI来公开服务的功能。以下可能是用于创建和删除URL的API的定义：
createURL（api_dev_key、原始_url、自定义_别名=None、用户名=None、过期日期=None）
参数：
api_dev_key（string）：注册帐户的api开发者密钥。除其他外，这将用于根据分配的配额限制用户。
original_url（string）：要缩短的原始url。
custom_alias (string）：URL的可选自定义键。
user_name (string) ：用于编码的可选用户名。expire_date（字符串）：缩短URL的可选过期日期。
expire_date (string)
returns:(String)
成功插入将返回缩短的URL；否则，它将返回一个错误代码。
deleteURL（api_dev_key，url_key）
其中“url_key”是表示要检索的缩短url的字符串。成功删除返回“URL已删除”。
我们如何发现和防止虐待？恶意用户可以通过使用当前设计中的所有URL密钥使我们破产。为了防止滥用，我们可以通过api_dev_密钥限制用户。每个api_dev_密钥可以在某个时间段内限制一定数量的URL创建和重定向（每个开发人员密钥可以设置不同的持续时间）。
5. 数据库设计
在访谈的早期阶段定义DB模式将有助于理解各个组件之间的数据流，并在以后指导数据分区。
关于我们将存储的数据性质的一些观察结果：
1.我们需要存储数十亿条记录。
2.我们存储的每个对象都很小（小于1K）。
3.记录之间没有关系，只存储哪个用户创建了URL。
4.我们的服务质量很高
数据库架构：
我们需要两个表：一个用于存储有关URL映射的信息，另一个用于创建短链接的用户数据。
我们应该使用什么样的数据库？因为我们预期存储数十亿行，并且不需要使用对象之间的关系——像DynamoDB、Cassandra或Riak这样的NoSQL键值存储是更好的选择。NoSQL选择也更容易扩展。有关更多详细信息，请参见SQL vs NoSQL。
6.基本系统设计和算法
我们在这里要解决的问题是，如何为给定的URL生成一个简短且唯一的密钥。
在第1节的TinyURL示例中，缩短的URL为“http://tinyurl.com/jlg8zpc”. 此URL的最后六个字符是我们要生成的短键。我们将在这里探讨两种解决方案：
A.编码实际URL
我们可以计算给定URL的唯一散列（例如MD5或SHA256等）。然后可以对散列进行编码以显示。这种编码可以是base36（[a-z，0-9]）或base62（[a-z，a-z，0-9]），如果我们添加“-”和“.”，我们可以使用base64编码。一个合理的问题是，短键的长度应该是多少？6、8或10个字符。
使用base64编码，6个字母长的密钥将产生64^6=~687亿个可能的字符串使用base64编码，8个字母长的密钥将产生64^8=~281万亿个可能的字符串
对于68.7B唯一字符串，我们假设六个字母键就足以满足我们的系统。
如果我们使用MD5算法作为散列函数，它将生成一个128位的散列值。在base64编码之后，我们将得到一个超过21个字符的字符串（因为每个base64字符编码哈希值的6位）。既然我们每个短键只有8个字符的空间，那么我们将如何选择我们的键呢？我们可以用前6（或8）个字母作为钥匙。但这可能会导致密钥重复，在此基础上，我们可以从编码字符串中选择一些其他字符或交换一些字符。
我们的解决方案有哪些不同的问题？我们的编码方案存在以下几个问题：
1.如果多个用户输入相同的URL，他们可以得到相同的缩短URL，这是不可接受的。
2.如果URL的某些部分是URL编码的呢？例如。，http://www.educative.io/distributed.php? id=设计，以及http://www.educative.io/distributed.php?id=design 除了URL编码之外，其他的都是相同的。
解决问题的方法：我们可以向每个输入URL添加一个递增的序列号，使其唯一，然后生成一个哈希。不过，我们不需要将这个序列号存储在数据库中。这种方法可能存在的问题是序列号不断增加。它会溢出吗？增加序列号也会影响服务的性能。
另一个解决方案是将用户id（应该是唯一的）附加到输入URL。但是，如果用户尚未登录，则必须要求用户选择唯一性密钥。即使在这之后，如果我们有冲突，我们必须不断地生成一个密钥，直到我们得到一个唯一的密钥。
生成短链URL步骤
我们可以有一个独立的密钥生成服务（KGS），它可以预先生成随机的六个字母字符串，并将它们存储在数据库中（我们称之为密钥数据库）。每当我们想要缩短一个URL时，我们将只获取一个已经生成的键并使用它。这种方法将使事情变得非常简单和快速。我们不仅没有对URL进行编码，而且不必担心重复或冲突。KGS将确保插入密钥数据库的所有密钥都是唯一的
并发会导致问题吗？一旦使用了密钥，就应该在数据库中对其进行标记，以确保不再使用该密钥。如果有多个服务器同时读取密钥，则可能会出现两个或多个服务器尝试从数据库读取相同密钥的情况。我们如何解决这个并发问题？
服务器可以使用KG读取/标记数据库中的密钥。KGS可以使用两个表来存储密钥：一个用于尚未使用的密钥，另一个用于所有已使用的密钥。一旦KGS向其中一台服务器提供密钥，它就可以将它们移动到used keys表中。KG可以始终在内存中保留一些密钥，以便在服务器需要时快速提供这些密钥。
为简单起见，只要KGS在内存中加载一些键，它就可以将它们移动到used keys表中。这确保每个服务器都获得唯一的密钥。如果KGS在将所有加载的密钥分配给某个服务器之前死亡，我们将浪费这些密钥——这是可以接受的，因为我们拥有大量密钥。
KGS还必须确保不对多个服务器提供相同的密钥。为此，它必须同步（或锁定）持有密钥的数据结构，然后再从中移除密钥并将其提供给服务器
关键数据库大小是多少？使用base64编码，我们可以生成68.7B唯一的六字母密钥。如果我们需要一个字节来存储一个字母数字字符，我们可以将所有这些键存储在：
6（每个键的字符数）*68.7B（唯一键）=412 GB。
KGS不是单点故障吗？是的。为了解决这个问题，我们可以有一个KGS的备用副本。只要主服务器死亡，备用服务器就可以接管以生成和提供密钥。
每个应用服务器能否缓存密钥数据库中的一些密钥？是的，这肯定能加快速度。尽管在这种情况下，如果应用程序服务器在使用所有密钥之前死亡，我们最终将丢失这些密钥。这是可以接受的，因为我们有68B唯一的六字母钥匙。
我们将如何执行密钥查找？我们可以在数据库或键值存储中查找键，以获得完整的URL。如果存在，则将“HTTP 302重定向”状态发回浏览器，并将存储的URL传递到请求的“位置”字段中。如果我们的系统中不存在该密钥，则发出“HTTP 404未找到”状态或将用户重定向回主页。
我们应该对自定义别名施加大小限制吗？我们的服务支持自定义别名。用户可以选择任何他们喜欢的“密钥”，但提供自定义别名不是强制性的。但是，对自定义别名施加大小限制是合理的（通常也是可取的），以确保我们拥有一致的URL数据库。假设用户可以为每个客户密钥指定最多16个字符（如上面的数据库模式所示）。
URL缩短的高级系统设计
7.数据分区和复制
为了扩展数据库，我们需要对其进行分区，以便它能够存储数十亿个URL的信息。我们需要提出一种分区方案，将数据划分并存储到不同的DB服务器。
A.基于范围的分区：我们可以根据URL的第一个字母或哈希键将URL存储在单独的分区中。因此，我们将所有以字母“A”开头的URL保存在一个分区中，将以字母“B”开头的URL保存在另一个分区中，依此类推。这种方法称为基于范围的分区。我们甚至可以将某些不太常见的字母组合到一个数据库分区中。我们应该提出一个静态分区方案，这样我们就可以始终以可预测的方式存储/查找文件。
这种方法的主要问题是，它可能导致服务器不平衡。例如：我们决定将所有以字母“E”开头的URL放在DB分区中，但后来我们意识到，我们有太多以字母“E”开头的URL。
B基于散列的分区：在这个方案中，我们对存储的对象进行散列。然后根据散列计算要使用的分区。在我们的例子中，我们可以使用“key”或实际URL的散列来确定存储数据对象的分区。
我们的散列函数将把URL随机分配到不同的分区（例如，我们的散列函数总是可以将任何键映射到[1…256]之间的数字），这个数字将代表我们存储对象的分区。
这种方法仍然会导致分区过载，这可以通过使用一致性哈希算法来解决。
8.缓存
我们可以缓存经常访问的URL。我们可以使用一些现成的解决方案，比如Memcache，它可以用各自的散列存储完整的url。应用服务器在访问后端存储之前，可以快速检查缓存是否具有所需的URL。
我们应该有多少缓存？我们可以从每天流量的20%开始，并根据客户端的使用模式，调整需要的缓存服务器数量。如上所述，我们需要170GB的内存来缓存20%的日常流量。因为现代的服务器可以有256GB的内存，所以我们可以很容易地将所有缓存放在一台机器上。或者，我们可以使用几个较小的服务器来存储所有这些热URL。
哪种缓存逐出策略最适合我们的需要？当缓存已满，并且我们希望用更新/更热的URL替换链接时，我们将如何选择？对于我们的系统来说，最近最少使用（LRU）是一个合理的策略。在此策略下，我们首先放弃最近使用最少的URL。我们可以使用链接的散列图或类似的数据结构来存储URL和散列，这也将跟踪最近访问的URL。
为了进一步提高效率，我们可以复制缓存服务器以在它们之间分配负载。
如何更新每个缓存副本？每当出现缓存丢失时，我们的服务器都会访问后端数据库。无论何时，我们都可以更新缓存并将新条目传递给所有缓存副本。每个复制副本都可以通过添加新条目来更新其缓存。如果复制副本已经有该条目，它可以忽略它。
9.负载平衡器（LB）
我们可以在系统的三个位置添加负载平衡层：
1.在客户端和应用服务器之间
2.应用服务器和数据库服务器之间3.应用服务器和缓存服务器之间
最初，我们可以使用一种简单的循环方法，在后端服务器之间平均分配传入的请求。此LB易于实现，不会引入任何开销。这种方法的另一个好处是，如果服务器死机，LB将使其退出循环，并停止向其发送任何流量。
循环LB的一个问题是没有考虑服务器负载。如果服务器过载或速度较慢，LB不会停止向该服务器发送新请求。为了解决这个问题，可以放置一个更智能的LB解决方案，定期向后端服务器查询其负载，并基于此调整流量。
10.DB数据
条目应该永久保留还是应该清除？如果达到用户指定的过期时间，链接会发生什么情况？
如果我们选择主动搜索过期链接来删除它们，这将给我们的数据库带来很大的压力。相反，我们可以慢慢地删除过期的链接并进行惰性清理。我们的服务将确保只有过期的链接将被删除，虽然一些过期的链接可以活得更长，但永远不会返回给用户。
•当用户试图访问过期链接时，我们可以删除该链接并向用户返回错误。
•可以定期运行单独的清理服务，从存储和缓存中删除过期的链接。此服务应该是非常轻量级的，并且只能计划在预期用户流量较低时运行。
•我们可以为每个链接设置默认过期时间（例如，两年）。
•删除过期链接后，我们可以将密钥放回密钥数据库中以重新使用。
•我们是否应该删除在一段时间内（比如六个月）没有访问过的链接？这这可能很棘手。由于存储越来越便宜，我们可以决定永远保持链接
11.统计
短URL被使用了多少次，用户位置是什么，等等。？我们将如何存储这些统计数据？如果它是在每个视图上更新的DB行的一部分，那么当一个流行URL被大量并发请求猛击时会发生什么？
一些值得追踪的统计数据：访问者的国家、访问日期和时间、引用点击的网页、浏览器或访问页面的平台。
12.安全和权限
用户可以创建私有URL或允许特定用户集访问URL吗？
我们可以使用数据库中的每个URL存储权限级别（公共/私有）。我们还可以创建一个单独的表来存储有权查看特定URL的用户ID。如果用户没有权限并试图访问URL，我们可以发回一个错误（HTTP 401）。假设我们将数据存储在NoSQL宽列数据库（如Cassandra）中，存储权限的表的键将是“哈希”（或KGS生成的“键”）。这些列将存储那些有权查看URL的用户的用户名。
题者补充
从上面的步骤来看，其实该案例详细的解读了，产生URL短链的背景是什么？收益是什么？我们应该如何设计URL短链设计？关注的点短链和长链如何维护映射关系，根据现状情况如何进行API设计，大量的调用是否会涉及缓存，负载均衡，数据库存储，统计审计，如何保证信息安全，那么换个其他设计问题，也应该同样采用如上思路。
参考资料
grok_system_design_interview.pdf
