成为架构师系列五：如何设计一个支持3.5万亿短URL的URL缩短服务？（公司倒闭了系统还能跑）
成为架构师系列这个系列很难，但是它是程序员走向架构师所必备的知识，既能助你在面试中脱颖而出，也能让你在日常工作中游刃有余。从基础到深入，从理论到实践，一切你所需的都在这里。收藏本文，点击关注
在这一章中，我们将解决一个有趣且经典的系统设计面试问题：设计一个像tinyurl这样的URL缩短服务。
第一步 - 理解问题并确定设计范围
很多面试官会故意把系统设计面试问题的开放性设置的比较大。为了设计一个精良的系统，提问澄清问题至关重要。
候选人 ：你能给一个URL缩短器如何工作的例子吗？
面试官 ：假设URL https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 是原始URL。你的服务创建了一个长度更短的别名：https://tinyurl.com/y7keocwj。如果你点击这个别名，它会将你重定向到原始URL。
候选人 ：流量是多少？
面试官 ：每天生成1亿个URL。
候选人 ：缩短后的URL有多长？
面试官 ：尽可能短。
候选人 ：缩短的URL中允许使用哪些字符？
面试官 ：缩短的URL可以是数字（0-9）和字符（a-z，A-Z）的组合。
候选人 ：可以删除或更新缩短的URL吗？
面试官 ：为了简单起见，让我们假设缩短的URL不能被删除或更新。
以下是基本用例：
简易估算
• 写操作：每天生成1亿个URL。
• 每秒的写操作：100 million / 24 /3600 = 1160
• 读操作：假设读操作与写操作的比例是10:1，每秒的读操作：1160 * 10 = 11,600
• 假设URL缩短服务将运行10年，这意味着我们必须支持100 million * 365 * 10 = 3650亿条记录。
• 假设平均URL长度是100。10年的存储需求：3650亿 * 100字节 * 10年 = 365 TB
向面试官详细说明假设和计算的过程是非常重要的，以便你们都能明白对方的想法。
第二步 - 提出高级设计并获得认可
在这一节中，我们将讨论API端点、URL重定向和URL缩短流程。
API
API用于客户端和服务器之间的通信。我们将设计REST风格的API。如果你不熟悉restful API，你可以查阅其他资料，例如参考资料[1]，由于篇幅限制，本文不对restful API做更多的解释。URL缩短器主要需要两个API。
1.URL缩短。为了创建一个新的短URL，客户端发送一个POST请求，其中包含一个参数：原始的长URL。API如下：
POST api/v1/data/shorten
• 请求参数：{longUrl: longURLString}
• 返回shortURL
2.URL重定向。为了将短URL重定向到相应的长URL，客户端发送一个GET请求。API如下：
GET api/v1/shortUrl
• 返回longURL进行HTTP重定向
URL重定向
图8-1展示了当你在浏览器上输入tinyurl时会发生什么。一旦服务器收到一个tinyurl请求，它就会通过301重定向将短URL更改为长URL。
图8-2展示了客户端和服务器之间的详细通信。
在此值得讨论的一点是301重定向与302重定向。
301重定向。301重定向表示请求的URL被“永久性”地移动到了长URL。由于它是永久重定向，浏览器会缓存该响应，同一个URL的后续请求将不会发送到URL缩短服务。相反，请求将直接重定向到长URL服务器。
302重定向。302重定向意味着URL被“暂时性”地移动到了长URL，这意味着同一个URL的后续请求首先会发送到URL缩短服务。然后，它们被重定向到长URL服务器。
每种重定向方法都有其优点和缺点。如果优先考虑减少服务器负载，使用301重定向是更好的，因为只有同一URL的第一个请求会发送到URL缩短服务器。然而，如果对于你的系统分析用户行为是更重要的，302重定向则是更好的选择，因为它可以更容易地跟踪点击率和点击源。
实现URL重定向的最直观的方式是使用哈希表。假设哈希表存储*<shortURL, longURL>*对，URL重定向可以通过以下方式实现：
• 获取longURL：longURL = hashTable.get(shortURL)
• 一旦你获取到longURL，就执行URL重定向。
URL缩短
让我们假设短URL看起来像这样：http://www.tinyurl.com/ **{hashValue}*。为了支持URL缩短的用例，我们必须找到一个哈希函数fx，它将长URL映射到hashValue*，如图8-3所示。
哈希函数必须满足以下要求：
• 每个longURL必须被哈希到一个hashValue。
• 每个hashValue可以被映射回longURL。
第三步 - 深入设计
到目前为止，我们已经讨论了URL缩短和URL重定向的高级设计。在本节中，我们深入研究以下内容：数据模型，哈希函数，URL缩短和URL重定向。
数据模型
在高级设计中，所有内容都存储在哈希表中。这是一个好的想法；然而，这种方法对于真实世界的系统来说是不可行的，因为内存资源是有限的和昂贵的。更好的选择是将*<shortURL, longURL>映射存储在关系数据库中。图8-4显示了一个简单的数据库表设计。简化版的表包含3列：id*, shortURL, longURL。
哈希函数
哈希函数用于将长URL哈希为短URL，也称为hashValue。
哈希值长度
hashValue由[0-9，a-z，A-Z]的字符组成，包含10 + 26 + 26 = 62个可能的字符。为了找出hashValue的长度，找到最小的n使得62^n ≥ 3650亿。根据建议估算，系统必须支持最多3650亿个URL。表8-1显示了hashValue的长度和它可以支持的最大URL数量。
当n = 7, 62 ^ n = ~3.5万亿时，3.5万亿足以容纳3650亿个URL，所以hashValue的长度是7。
我们将探讨URL缩短器的两种类型的哈希函数。第一种是“哈希+冲突解决”，第二种是“Base62转换”。让我们依次介绍。
哈希+冲突解决
为了缩短一个长URL，我们应该实现一个哈希函数，将长URL哈希为7个字符的字符串。一个直接的解决方案是使用像CRC32、MD5或SHA-1这样的知名哈希函数。下表比较了在此URL上应用不同哈希函数后的哈希结果：https://en.wikipedia.org/wiki/Systems_design。
如表8-2所示，即使是最短的哈希值（来自CRC32）也太长（超过7个字符）。我们如何使它更短？
第一种方法是收集哈希值的前7个字符；然而，这种方法可能导致哈希冲突。为了解决哈希冲突，我们可以递归地附加一个新的预定义字符串，直到不再发现冲突。这个过程在图8-5中解释。
这种方法可以消除冲突；然而，对每个请求查询数据库检查是否存在shortURL是很消耗系统资源的。我们可以使用布隆过滤器[2]以提高性能。布隆过滤器是一种空间效率高的概率性技术，用于测试一个元素是否是一个集合的成员。更多详细信息请参考参考材料[2]。
Base62转换
Base转换是URL缩短器常用的另一种方法。Base转换有助于用不同的数字表示系统之间转换相同的数字。由于有62个可能的字符用于hashValue，所以使用Base62转换。让我们用一个例子来解释转换是如何工作的：将11157 10转换为Base62表示法（11157 10代表十进制系统中的11157）。
• 从它的名字可以看出，Base62是一种使用62个字符进行编码的方式。映射关系是： 0-0，...，9-9，10-a，11-b，...，35-z，36-A，...，61-Z，其中 'a'代表10，'Z'代表61，等等。
• 1115710 = 2 x 62^2 + 55 x 62^1 + 59 x 62^0 = [2, 55, 59] -> [2, T, X] in base 62表示法。图8-6显示了会话过程。
URL缩短深度探讨
作为系统的核心部分之一，我们希望URL缩短流程在逻辑上简单且功能完备。在我们的设计中使用了Base62转换。我们构建了以下图表（图8-7）来展示这个流程。
1. longURL作为输入。
2. 系统检查数据库中是否存在longURL。
3. 如果存在，说明longURL之前已经转换为shortURL。在这种情况下，从数据库中获取shortURL并返回给客户端。
4. 如果不存在，说明longURL是新的。由唯一ID生成器生成一个新的唯一ID（主键）。
5. 通过Base62转换，将ID转换为shortURL。
6. 使用ID，shortURL和longURL插入数据库。
为了让流程更易于理解，让我们看一个具体的例子。
• 假设输入的longURL是：https://en.wikipedia.org/wiki/Systems_design
• 唯一ID生成器返回ID：2009215674938。
• 使用Base62转换，将ID转换为shortURL。ID（2009215674938）被转换为“zn9edcu”。
• 将ID，shortURL和longURL保存到数据库中，如表8-4所示。
分布式唯一ID生成器值得一提。它的主要功能是生成全球唯一的ID，这些ID用于创建shortURL。在高度分布式的环境中，实现一个唯一的ID生成器是具有挑战性的。我们在上一篇：设计分布式系统中的唯一ID生成器”中讨论过一些解决方案。忘了的小伙伴可以返回去再复习下。
URL重定向深度探讨
图8-8展示了URL重定向的详细设计。由于读取操作多于写入操作，因此将*<shortURL, longURL>* 映射存储在缓存中以提高性能。
URL重定向的流程如下：
1. 用户点击一个短URL链接：https://tinyurl.com/zn9edcu
2. 负载均衡器将请求转发到web服务器。
3. 如果shortURL已经在缓存中，则直接返回longURL。
4. 如果shortURL不在缓存中，则从数据库中获取longURL。如果它不在数据库中，那可能是用户输入了一个无效的shortURL。
5. 将longURL返回给用户。
第四步 - 总结
在本章中，我们讨论了API设计、数据模型、哈希函数、URL缩短和URL重定向。
如果面试结束时还有额外的时间，以下是一些额外的讨论点。
• 速率限制器：我们可能面临的一个潜在的安全问题是恶意用户发送了过多的URL缩短请求。速率限制器可以根据IP地址或其他过滤规则来过滤请求。如果你想复习一下速率限制，参考“前面的文章：如何设计一个速率限制器”。
• Web服务器扩展：由于web层是无状态的，所以通过添加或移除web服务器很容易对web层进行扩展。
• 数据库扩展：数据库复制和分片是常见的技术。
• 分析：数据对于业务成功日益重要。将分析解决方案集成到URL缩短器中，可以帮助回答诸如有多少人点击了链接？他们何时点击链接？等重要问题。
• 可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。我们在第一章详细讨论了这些主题，忘了的小伙伴也可以回去复习下。
参考资料
[1] 一个RESTful教程：https://www.restapitutorial.com/index.html
[2] 布隆过滤器：https://en.wikipedia.org/wiki/Bloom_filter
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。