设计一个短链服务

让我们设计一个类似TinyURL的URL缩短服务。此服务将提供短别名重定向到长url。类似的服务:bit.ly, goo.gl, qlink.me等等。难度:简单

1. 为什么我们需要URL缩短?

    URL缩短用于为长URL创建更短的别名。我们称这些缩短的别名为“短链接”。当用户点击这些短链接时，会被重定向到原始URL。短链接在显示、打印、发送或推特时节省了大量空间。此外，用户不太可能键入较短的url。例如微博这种,这种字数有限制的,需要短链接这种服务.

缩短后的URL几乎是实际URL大小的三分之一。
URL缩短用于优化跨设备链接，跟踪单个链接以分析受众和活动表现，并隐藏关联的原始URL。
    如果你以前没有使用过tinyurl.com，请尝试创建一个新的缩短的URL，并花一些时间浏览他们提供的各种服务选项。这将对你理解本章有很大帮助。

在一些场景下,我们希望将长链接转变为短链接,进行发布.例如微博这种.我们可以通过发布的短链接访问到长链接指向的资源.
我们希望最终各种url访问的链路情况,例如广告投放的场景,这个时候,我们也可以通过短链接服务,来监控长链接指向资源的访问情况.

2.系统需求和目标

在面试开始的时候,一定需要和面试官进行沟通清楚他希望的系统是什么样子的.
    我们的网址缩短系统应符合下列要求:

功能需求:
给定一个URL，我们的服务应该生成一个更短和唯一的别名。这就是所谓的短链接。
当用户访问短链接时，我们的服务应该将他们重定向到原始链接。
用户应该有选择地为他们的URL选择一个自定义短链接。
链接将在标准的默认时间范围后过期。用户应该能够指定
过期时间。
非功能需求
系统应该具有高可用性。这是必需的，因为如果我们的服务关闭，所有的URL重定向都将开始失败.
URL重定向应该实时发生，延迟最小.
缩短的链接不应该是可猜测的(不可预测的).
扩展要求:
分析;例如，重定向发生了多少次?
其他服务也应该可以通过REST api访问我们的服务。

3.容量估计和约束条件

    我们的系统将需要大量的读操作。与新URL缩短相比，将会有很多重定向请求。让我们假设读和写的比例为100:1。
    流量估算:假设我们每个月将有5亿个新URL缩短，读/写比率为100:1，我们预计在同一时期会有500亿重定向:

100 * 5亿 = 500 亿 对于我们的系统，每秒查询(QPS)是多少?每秒缩短的新url: 500亿 /(30 * 14 * 60 * 60) = ~200URL/s 考虑到100:1的读/写比率，每秒url重定向将是: 100 * 200URL/s = 20K/s

    存储估计:假设我们将每个URL缩短请求(以及相关的缩短链接)存储5年。因为我们预计每个月将有5亿个新url，所以我们预计存储的对象总数将达到300亿:

5亿 * 5年 * 12月 = 300亿

    让我们假设每个存储的对象大约为500字节(这只是一个大概的估计，稍后我们将深入研究)。我们总共需要15TB的存储空间:

300亿 * 500byte = 15TB

    带宽估计:对于写请求，由于我们预计每秒200个新url，我们的服务的总数据将是每秒100KB:

200 * 500B = 100KB     对于读请求，由于我们期望每秒钟有20K的url重定向，所以我们的服务的总输出数据将是每秒10MB: 20K/s*500B = 10M

    缓存估计:如果我们想缓存一些经常被访问的热url，我们需要多少内存来存储它们?如果我们遵循80-20规则，即20%的url产生80%的流量，我们希望缓存这20%的热url。

    由于我们每秒有20K个请求，我们每天将收到17亿个请求: