面试场景题系列：设计URL短链
1.场景需求界定
1.缩短URL：提供一个长URL，返回一个短很多的URL。2.重定向URL：提供一个缩短了的URL，重定向到原URL。
3.高可用、可扩展性和容错性考量。
•写操作：每天生成1亿个URL。
•每秒的写操作数：1亿÷24÷3600≈1160。
•每秒的读操作数：假设读操作与写操作的比例是10∶1，那么每秒的读操作数是1160×10=11，600。
•假设URL缩短器会运行10年，这意味着我们必须支持1亿×365×10=3650亿条记录。
•假设URL的平均长度是100个字符，那么10年的存储容量需求是：3650亿×100字节≈36.5TB。
2.顶层设计
在这一节，我们将讨论API端点、URL重定向和URL缩短的相关流程。2.1 API端点
API端点有利于客户端和服务器之间的通信。我们会把API设计成REST风格。如果你不熟悉REST风格的API，可以参阅一些文章，比如RestapiTutorial网站上的文章。一个URL缩短器主要需要两个API端点。1.缩短URL。为了创建一个短URL，客户端会发送一个POST请求，它包含一个参数——原始的长URL。API看起来像下面这样：
POST api/v1/data/shorten
•请求参数：{longUrl：longURLString}。
•返回短URL。
2.重定向URL。为了把短URL重定向到对应的长URL，客户端会发送GET请求。API看起来像下面这样：
POST api/v1/shorturl
返回长URL以进行HTTP重定向。
2.2 URL重定向
图-1展示了当你在浏览器中输入一个经过缩短的TinyURL网址时会发生什么。一旦服务器收到一个TinyURL请求，就会通过301重定向把短URL换成长URL。
客户端和服务器之间的详细通信信息如图-2所示。
图-2
**301重定向：**意味着所请求的URL“永久”移动到长URL。因为是永久重定向，所以浏览器会缓存该响应，以后对同一个URL的请求就不会发给URL缩短服务器了，而会将其直接重定向到长URL服务器。
**302重定向：**意味着URL“暂时”移动到长URL，这也意味着对于同一个URL的后续请求会先发给URL缩短服务器，然后它们才会被重定向到长URL服务器。
每种重定向方法都有自己的优缺点。如果降低服务器的负载是需要优先考虑的事项，使用301重定向就是合适的，因为对于同一个URL只有第一次请求会被发到URL缩短服务器上。但是如果数据分析很重要，那么302重定向就是更好的选择，因为它可以更轻松地跟踪点击率和点击来源。
实现URL重定向的最直观的方法就是使用哈希表。假设哈希表存储了<shortURL，longURL＞键值对，可以通过以下步骤实现URL重定向。
•获取长URL：longURL=hashTable.get(shortURL)。
•一旦获取了长URL，就实施URL重定向。
2.3 缩短URL
我们假设短URL的格式为：www.tinyurl.com/{hashValue}。为了支持URL缩短的使用场景，我们必须找到一个哈希函数fx，它可以把长URL(longURL)映射成哈希值，如图-3所示。
图-3
这个哈希函数必须满足下面的要求：
•每个长URL必须可以通过哈希函数转换成一个哈希值(hashValue)。
•每个哈希值可以被映射回原始的长URL。
我们将在第3节探讨哈希函数的详细设计。
3. 设计继续深入
到目前为止，我们讨论了URL缩短和URL重定向的高层级设计。在本节中，我们会深入探讨以下内容：数据模型、哈希函数、URL缩短和URL重定向。3.1 数据模型
在高层级设计中，所有的数据都被存储在哈希表中。这是一个很好的起点，但是在现实世界中内存资源是有限且昂贵的，因此这个方法并不可行。更好的选择是在关系型数据库中存储
图-4
3.2 哈希函数
哈希函数用于将长URL哈希成短URL，这个短URL也叫作哈希值(hashValue)。哈希值的长度
哈希值由数字(0～9)和字母(a～z、A～Z)组成，包含62种可能的字符（10个数字+26个小写字母+26个大写字母=62）。为了确定合适的哈希值长度，我们需要找到最小的n，使得62的n次幂小于或等于3650亿。根据之前的估算，系统需要支持高达3650亿个URL。表8-1展示了随n的变化其对应支持的最大URL数量。
表-1
当n=7时，627≈3.5万亿，足够支持3650亿个URL，所以哈希值的长度应该是7位。
我们会探讨两种用于URL缩短器的哈希函数。第一种是“哈希+解决冲突”，第二种是“Base 62转换”。下面我们逐一来看一下。
为了缩短一个长URL，我们需要实现一个哈希函数将长URL哈希成7个字符的字符串。最直接的解决方案是使用那些有名的哈希函数，比如CRC32、MD5或者SHA-1等。下面的表8-2比较了对长URL“https://en.wikipedia.org/wiki/Systems_design”使用不同哈希函数的结果。
表-2
如表-2所示，即使是最短的哈希值（通过CRC32算法得到）都太长了（超过7个字符）。怎么能让它变得短一些呢？第一个方法是取哈希值的前7个字符，但是这个方法会导致哈希冲突(Hash Collision)。
为了解决哈希冲突，我们可以递归地添加一个新的预先设定好的字符串，直到不再发现冲突为止。图-5解释了这个过程。
图-5
这个方法可以消除哈希冲突，但是对每一个请求都要查询数据库以检查是否存在对应的短URL，这个成本是很高的。一种叫作布隆过滤器的技术可以提升性能。布隆过滤器是一种高效利用空间的概率性技术，可以用来检测一个元素是否属于某个集合。参考维基百科中“Bloom Filter”词条的相关介绍，可以了解更多细节。
Base 62转换
基数转换(Base Conversion)是被广泛用于URL缩短器的另一种方法。基数转换可以将同一个数字在不同的数值表示系统之间进行转换。用Base 62转换是因为一个哈希值中有62种可能的字符。下面用一个例子来解释如何进行转换：把1115710转换成Base 62的表示（1115710表示的是十进制数11，157）。
•从名字可以看出，Base 62是一种使用62个字符来进行编码的方式。其映射关系为：0→0，…，9→9，10→a，11→b，…，35→z，36→A，…，61→Z，其中“a”代表10，“Z”代表61，依此类推。
•1115710=2×622+55×621+59×620=[2，55，59]，转换为Base 62的表示就是[2，T，X]。图-6展示了转换过程。•因此，短URL就是https://tinyurl.com/2TX。
图-6
表-3展示了两种方法的不同点。
表-3
3.3 深入探讨URL缩短流程
作为系统的核心组成部分之一，UR L缩短流程应该是逻辑简单的，而且能提供我们想要的功能。在我们的设计里使用了Base 62转换。图-7展现了这个流程。
1.长URL是输入。
2.系统检查数据库中是否有这个长URL。
3.如果有，则意味着这个长URL此前曾经被转换为短URL。在这种情况下，从数据库中获取短URL并返回给客户端。
4.如果没有，则说明这是一个新的长URL。系统通过唯一ID生成器生成新的唯一ID（主键）。5.采用Base 62转换把这个ID转换成短URL。
6.创建一个新的数据库记录，其中包含ID、短URL和长URL。
为了更好地理解这个流程，我们来看一个具体的示例。
•假设输入的长URL是https://en.wikipedia.org/wiki/Systems_design。
•唯一ID生成器返回的ID为2009215674938。
•用Base 62转换把ID转成短URL，即ID(2009215674938)被转换成“zn9edcu”。
•将ID、短URL和长URL保存到数据库，如表-4所示。
这里，分布式唯一ID生成器值得一提。它主要的功能是生成全局唯一的ID，这个ID被用来创建短URL。在高度分布式的环境中，实现唯一ID生成器是很有挑战性的。
3.4 深入探讨URL重定向流程
图-8展示了URL重定向的详细设计。因为读操作远多于写操作，所以
图-8
URL重定向的流程总结如下：
1.用户点击一个短URL“https://tinyurl.com/zn9edcu”。
2.负载均衡器将请求转发给Web服务器。
3.如果短URL已经在缓存中，则直接返回对应的长URL。
4.如果短URL不在缓存中，则从数据库中获取对应的长URL；如果这个短URL不在数据库中，那么有可能用户输入了无效的短URL。
5.将长URL返回给用户。
4 总结
在本文中，我们讨论了API设计、数据模型、哈希函数、URL缩短和URL重定向。如果在面试的最后还有多余的时间，以下是一些可以讨论的议题。•限流器：恶意用户发送海量的URL缩短请求是系统可能遇到的一个安全问题。限流器可以帮助我们基于IP地址或者其他过滤条件来拦截请求。如果你想回顾关于流量限制的知识，可以参考第4章。
•Web服务器伸缩：因为网络层是无状态的，所以很容易通过添加或移除Web服务器来对网络层进行伸缩。
•数据库扩展：数据库复制和分片是常用的技术。
•数据分析：对于业务而言，数据变得越来越重要。将数据分析解决方案整合到URL缩短器中可以帮助我们回答一些重要问题，比如“有多少用户点击了一个链接？”“他们是什么时候点击的？”。•可用性、一致性和可靠性。这些概念是所有大型系统成功的关键。我们在第1章中详细讨论过它们，请回顾这些内容。