设计一个类TinyURL的短网址服务
让我们来设计一个类似TinyURL的短网址服务。它可以把短网址重定向到原始长地址。
类似服务：bit.ly, goo.gl, 2020.fm etc.
难度级别：简单

1.我们为什么需要短网址服务？

短网址就是为原始长网址创建的别名，当点击短网址时，用户会被重定向到原始网址。当需要进行印刷或者输入有字数限制时，使用短网址非常有效。

2.系统需求和目标

我们的短网址服务需要满足下面的需求：
功能性需求：
1.给定一个URL，我们的服务能生成唯一对应的短网址
2.当用户访问原网址时，我们的服务能把它重定向到原始网址
3.用户可以自定义短网址的别名
4.短链接可以在指定的时间后自动过期，用户可以指定这个过期时间

非功能性需求：
1.服务必须高可用，因为一旦我们的服务宕机，所有的URL跳转都会失败
2.URL跳转必须是实时的，要在最短的时间内完成
3.短链接必须是随机的（不可预测的）

扩展需求：
1.数据统计，即短网址被跳转了多少次
2.我们的服务必须可以通过REST API进行访问

容量估计与约束

我们的系统应该是会被重度读取的；重定向的请求相对于创建短链接要多得多，我们假设读写比例是 100：1

流量估算：假设一个月有500 Million的新增短链接，我们可以预计在此期间有50 Billion（100 * 500M = 50 Billion）的重定向，那系统每秒钟的查询（QPS）是多少？

每秒钟创建短链接请求：500 million / (30 days * 24 hours * 3600 seconds) ~= 200 URLs/s
每秒钟重定向请求：50 billion / (30 days * 24 hours * 3600 sec) ~= 19K/s

存储估算：由于我们预计了每个月有50Million的新增短网址，假设我们会把这些数据对象保存5年，整个的存储对象数量会是30Billion
500 million * 5 years * 12 months = 30 billion

假设每个对象存储了500 bytes（仅仅是大致估算，后续会深入探讨），我们将需要 15TB的存储空间。
30 billion * 500 bytes = 15 TB

带宽估算：对于写请求，由于我们预期每秒有200个新增URL，总共的入站流量应该是100KB/s
200 * 500 bytes = 100 KB/s

对于读请求，由于我们预期每秒有19K 的URL进行重定向，总共的出站流量应该是9MB/s
19K * 500 bytes ~= 9 MB/s

内存估算：如果我们希望缓存经常访问的热点URL，那么需要多少内存来进行存储？如果我们遵循80–20原则，即20%的URL产生了80%的流量，我们应该要缓存20%的热点URL

由于我们每秒有19K的请求，那么1天就有1.7Billion的请求
19K * 3600 seconds * 24 hours ~= 1.7 billion

要缓存这些请求中的20%，我们应该需要170GB的内存。
0.2 * 1.7 billion * 500 bytes ~= 170GB

高层级评估：假设每个月有500million的新增URL， 读写比为100:1， 下面就是我们服务的高层级评估汇总
New URLs 200/s
URL redirections 19K/s
Incoming data 100KB/s
Outgoing data 9MB/s
Storage for 5 years 15TB
Memory for cache 170GB

系统API

一旦我们完成了需求分析，开始定义系统API通常是个好主意。这将明确我们的系统能做什么。

我们可以通过SOAP或者REST API对外暴露我们的功能服务。下面是创建和删除URL的API定义。

creatURL(api_dev_key,original_url,custom_alias=None,user_name=None,expire_date=None)

Parameters:
api_dev_key (string): The API developer key of a registered account. This will be used to, among other things, throttle users based on their allocated quota.
original_url (string): Original URL to be shortened.
custom_alias (string): Optional custom key for the URL.
user_name (string): Optional user name to be used in encoding.
expire_date (string): Optional expiration date for the shortened URL.

Returns: (string)
A successful insertion returns the shortened URL, otherwise, returns an error code.

deleteURL(api_dev_key,url_key)


Parameters：
url_key (string): A string representing the shortened URL to be retrieved

Returns: (string)
A successful deletion returns ‘URL Removed’.

如何检测并防止滥用？举例来说，以我们现在的设计来看，任何服务都能通过耗尽我们的Keys来使我们的短链接无法提供服务。要防止滥用，我们可以通过api_dev_key来限制用的在一定时间内创建URL的数量。

数据库Schema

在面试的早起阶段定义数据库Schema能帮助我们在各种组件间理解数据流转，并便于后续的数据分区

对需要存储的数据的一些本质观察：
1.我们需要存储billion级别的记录
2.每个存储的对象都很小（小于1k）
3.记录之间是没有关联的，除非我们想存储用户与URL的关联关系
4.我们的服务是读频繁的

数据库schema：
我们需要2个表，一个存储URL，一个存储User信息

我们需要什么类型的数据库？由于我们需要存储billion级别的记录，并且不需要在对象之间使用关联关系，NoSQL 的 key-value数据库Dynamo 或Cassandra是更好的选择，它们也更容易扩展。如果我们选择了NoSQL的key-value数据库， 我们不再能在URL表存储userID（因为它不支持外键），所以我们需要另外的第三个表来存储URL和User的映射关系。

基础的系统设计和算法

我们正在解决的问题是为给定的URL生成唯一的短链接。在之前提到的例子中，得到的短链接形如 https://tinyurl.com/jlg8zpc URL最后的几个随机字符就是我们想要生成的短链接，我们将会探索2个解决方案：

a.编码实际的URL
我们可以根据给定的URL计算出唯一Hash（例如使用Md5或者SHA256等），Hash可以编码后进行展示。编码可以使用base36[a-z,0-9]，base62[a-zA-Z,0-9]，如果增加 – 和. 符号，我们也可以使用base64编码。一个合理的疑问是：短链接的长度应该是多少？6个、8个还是10个字符？

使用base64编码，6个字符长度可以表示64^6 = 68.7 billion 个可能的URL字符串
使用base64编码，8个字符长度可以表示64^8 = 281 trillion 个可能的URL字符串

对于我们的系统，假设有68.7 billion 个唯一字符串可以使用，就已经足够了

如果我们使用Md5算法作为hash函数，它会生成128bit的hash值。base64编码之后，我们得到的字符串长度超过20。我们该如何选择key的长度？实际上，我们可以选择前6（或8）个字符作为key。但是这会导致key重复，此时，我们可以再多选几个字符，或者做一些字符交换。

我们的解决方案有哪些不同的问题？我们的编码模式存在以下一些问题：
1.如果多个用户输入相同的URL，他们会得到相同的短链接，这是不可接受的。
2.要是URL中有一部分的URL-encoded的要怎么办？例如，在忽略URL编码的情况下，http://www.educative.io/distributed.php?id=design, 和 http://www.educative.io/distributed.php%3Fid%3Ddesign 是相同的。

这些问题的变通方法：我们可以在每个输入的URL上先附加一个自增的序列号，再计算它的hash。虽然我们并不需要把这个序列号存储在数据库中，但是这种方式可能存在的问题是这个序列号有多大，会不会溢出？附加一个自增的序列号，也会影响服务的性能。

另一个解决方案是把user id(通常应该是唯一的)附加到输入的URL。但是，如果用户没有登录的话，我们需要用户去选择一个唯一key。即便用户这么做了，当遇到key冲突时，我们需要持续尝试，直到获取一个唯一的key。

b.离线生成Keys
我们可以拥有一个独立的Key Generation Service（KGS），它可以提前生成6个字符的随机串存储在数据库中（我们称它为key-DB）。当我们需要为一个URL生成短链接时，只需要从已经生成的Key中取一个出来使用即可。这种方式会把事件变得相当简单，因为我们不必对URL进行编码，也不需要担心重复和碰撞。KGS可以确保插入到key-DB中的key都是唯一的。

并发会导致问题吗？一旦一个Key被使用，在数据库中它就应该被标记，以便它不会被再次使用。如果多个服务器并发同时读取key，我们会遇到多个服务器同时从数据库读取到相同key的情况，我们改如何解决并发的问题？

服务器可以使用KGS来 读取/标记 数据库中的key。KGS可以使用2个表来存储key，1个表存储未使用的key，一个表存储已使用的key。当KGS为服务器提供了某个Key之后，它可以把该key移动到已使用的key表中。KGS可以把一些key保存在内存中，当服务器需要的时候，可以快速提供。简单来说， 一旦KGS加载了Key到内存中，它就应该把key移到已使用的表中。这样，我们可以确保服务器总能获取到唯一的key。如果服务器在把所有加载到内存中的key分配给服务器之前宕机了，我们会浪费一些key，但是相较于我们海量的key，这些浪费可以忽略。同时，KGS需要确保不会把同一个key分配给多个服务器。为了实现这个目标，它应该同步（或者获取锁）数据结构，在移除key之前保持持有这个key并分发给服务器。

key-DB的应该有多大？使用base64编码，我们可以生成68.7Billion个唯一的6字符key。如果每个alpha-numeric字符需要1个byte，我们需要这么大的空间来存储：
6 (characters per key) * 68.7B (unique keys) => 412 GB.

KGS难道不会单点失败吗？是的，它会。要解决这个问题，KGS需要一个备选的副本，主服务宕机时，它可以接管生成/提供 key的工作。

每个app服务器都能从Key-DB缓存一些key吗？是的，这肯定是能提升速度的。尽管在这种场景中，如果应用服务器在消费完key之前宕机了，我们会丢失一些key，但这点损失相对于68Billion唯一key的体量，是可以接受的。

我们如何执行查询？我们可以在数据库或key-value存储中查找key，来获取完整URL。如果找到了，发送一个“HTTP 302 Redirect”给浏览器，把储的URL传递到请求的Location字段即可。如果key不存在，发送一个“HTTP 404 Not Found” ，或者把用户重定向到首页即可。

我们是否需要限定自定义别名的长度？由于我们的系统支持自定义别名，用户可以选择他们喜欢的任何key，但是提供自定义别名并不是强制的。然而，限制别名长度是合理的，这样我们才能有一个一致的数据库（数据库字段长度限制）。让我们假设用户最多可以指定16个字符长度的自定义key（基于上面的数据库schema）。

数据分区和副本

要想水平扩展我们的数据库，我们需要对它进行分区，以便能存储billion级别的URL。我们需要想出一个分区方案，将我们的数据划分并存储到不同的DB服务器上。

a.基于区间分区：我们可以基于URL或hash值的首字母把URL存储到不同的分区。因此，我们把以A为首字母开头的所有URL存储在同一个分区，把以B为首字母开头的所有URL存储到另一个分区，诸如此类。这种方式成为基于区间的分区。我们甚至可以把一些较少出现的首字母放到同一分区。我们应该静态地提出这个分区方案，这样我们就可以始终以可预测的方式存储/查找记录。

这种方式主要的问题是会造成服务器的负载不均衡。几个例子，如果我们决定把全部以E为开头的URL放到一个DB分区，但是不久之后，我们发现以E为开头的URL实在太多了，一个分区根本存不下。

b.基于hash分区：在这种方案中，我们获取存储对象的hash，然后基于hash来决定对象应该存储在哪个分区。在我们的场景中，我们可以取实际URL的短链Key的hash只，来决定把它存储到哪个分区。我们的hash函数会随机的把URL分配到不同的分区。例如，我们的hash函数总是能把任意key映射到[1~256]之间，这个数字就代表了对象存储的分区。

这种方式还是会导致出现重载分区，我们可以通过“一致性hash”来解决。

缓存

我们可以缓存那些经常被访问的URL。我们可以使用一些现成的方案比如Memcache，来保存hash值对应的完整URL。应用服务器可以在访问后端存储前，通过缓存快速检测是否有需要的URL。

我们需要多大的缓存？我们可以从每日流量的20%开始，并基于客户端的使用情况，调整需要的服务器大小。正如前面估算的一样，我们需要170GB内存来缓存每日流量的20%。因为现代的服务器可以有256GB的内存，我们可以很容易地把所有的缓存放在一台机器上，或者我们可以选择使用一些更小的服务器来存储所有这些热点URL。

哪种缓存过期策略最符合我们的需求？当缓存满了的时候，我们需要使用更新的/更热的URL来替换旧的数据，我们该如何选择？最近最少使用(LRU)对于我们的系统来说是一个合理的策略。在这种策略之下，我们首先淘汰掉最少最近使用的URL。我们可以使用HashMap链表或者类似的数据结构来存储我们的URL和Hash，它同时会追踪那些URL最近被使用。

为了进一步提高效率，我们可以复制缓存服务器来在它们之间分配负载。

每个缓存副本如何更新？当缓存未命中时，我们的服务器需要访问后端数据库，此时，我们可以更新缓存，并且把新的条目传递给全部的缓存副本。每个副本可以通过新增这些条目，来更新缓存。如果某个副本已经有了该条目，直接忽略就行了。

负载均衡（LB）

我们可以在系统中的3个位置增加负载均衡层：
1.客户端与应用服务器之间
2.应用服务器与数据库之间
3.应用服务器与缓存之间

期初，可以采用简单的轮询（Round Robin）策略。它会把入站请求均衡的分配到后端服务器。这种LB实现起来很简单，并且不会带来任何开销。这种方法的另一个好处是，如果服务器宕机，LB将使它退出轮替，并停止向它发送任何流量。轮询 LB策略的一个问题是，它不会考虑服务器的负载。如果服务器负载过重或缓慢，LB不会停止向该服务器发送新的请求。为了处理这个问题，可以采用一个更智能的LB解决方案，该解决方案定期查询后端服务器的负载，并根据负载调整流量。

数据库清除或清理

条目应该永远保留还是应该被清除？如果达到用户指定的过期时间，该链接上会发生什么？如果我们积极主动的搜索过期链接来删除它们，将给我们的数据库带来很大的压力。我们可以慢慢地删除过期的链接，并且执行一个惰性清理。我们的服务将确保只有过期的链接将被删除，虽然一些过期的链接可以存活更长时间，但永远不会返回给用户。

• 当用户试图访问过期链接时，我们可以删除该链接并向用户返回一个错误。
• 一个单独的清理服务可以定期运行，从存储和缓存中删除过期的链接。这个服务应该是非常轻量级的，只能在用户流量预期较低时调度运行。
• 我们可以为每个链接设置一个默认的过期时间，例如两年。
• 在删除一个过期链接后，我们可以将key放回key- db中以便重用。
• 我们应该删除在一段时间内没有访问过的链接吗，比如六个月没访问?这可能很棘手。由于存储越来越便宜，我们可以决定永远保存链接。

遥测（Telemetry）

一个短链接被使用了多少次，用户位置在哪里等等？我们将如何存储这些统计数据？如果它是每个视图上更新的DB行的一部分，那么当一个流行的URL被大量并发请求冲击时会发生什么?

我们可以统计访问者的国家、访问日期和时间、网页的点击来源、浏览器或平台及更多数据。

安全和权限

用户是否可以创建私有URL或允许特定的一组用户访问URL?

我们可以在数据库中存储每个URL的权限级别(公共/私有)。我们还可以创建一个单独的表来存储具有查看特定URL权限的user id。如果一个无权限的用户尝试访问某个URL，我们可以返回一个错误（HTTP 401 Unauthorized）。鉴于此，我们将数据存储在一个NoSQL宽列数据库中，如Cassandra，表存储权限的key将是 Hash(或KGS生成的key)，列将存储那些有权限查看URL的用户的user id。