第8章：设计URL缩短器
简介
本章将探讨类似 TinyURL 的 URL 短链服务的设计。该系统的主要目标包括URL 短链化, 重定向以及高可扩展性，以应对大规模的流量需求。
Requirements
•
缩短后的URL必须唯一且尽可能短.
•
每天处理1亿个URL生成，并具备10年的支持能力。
•
支持高效的读操作，读写比为10:1。
•
存储3650亿条记录，10年所需存储空间约为365 TB。
步骤1：概要设计
API Endpoints
URL缩短：
◦
端点：POST api/v1/data/shorten
◦
参数：{longUrl: longURLString}
◦
返回值：shortURL
URL重定向：
◦
Endpoint: GET api/v1/shortUrl
◦
Returns: longURL for redirection.
URL Redirection
•
301 重定向：301 重定向表示请求的 URL 已“永久”移动到长 URL。浏览器会缓存该响应，后续对同一 URL 的请求将不再发送至 URL 短链服务。
•
302 Redirect: Temporary; useful for analytics like tracking clicks.
URL Shortening
•
使用哈希函数生成短网址，将长网址映射为唯一的缩短版本。
•
哈希函数必须满足以下要求：
◦
每个长网址都必须哈希为一个哈希值。
◦
每个哈希值都可以映射回对应的长网址。
步骤2：深入设计
Data Model
将<shortURL, longURL>存储在关系型数据库中，以优化内存使用。表结构包括：
•
id(主键),
•
shortURL,
•
longURL.
Hash Function
基数62转换：
•
使用字符对数字进行编码[0-9, a-z, A-Z], 提供62个可用字符.
•
进制转换是URL缩短器中常用的另一种方法。
•
可以为短链接分配一个唯一ID，然后将该ID进行62进制转换，从而得到短URL。
•
一个7位字符的哈希值最多可支持3.5万亿个唯一URL,足以容纳3650亿个URL。
示例：
将ID2009215674938转换为Base 62：
•
这是一个名为“system-design-notes/01. Scaling at main · liquidslr/system-design-notes”的GitHub仓库页面。上下文。
哈希 + 冲突解决：
•
使用CRC32、MD5或SHA-1等哈希函数。
•
一种方法是取哈希值的前7个字符；然而，这种方法可能会导致哈希冲突。
•
为了解决冲突，可以递归地追加一个新的预定义字符串，直到不再发生冲突，但这样做可能代价高昂。
•
通过布隆过滤器解决冲突，实现高效查找。
Comparison
•
哈希 + 冲突解决：
◦
短网址长度固定
◦
无需唯一ID生成器
◦
可能发生冲突，需进行解决
•
采用Base62编码
◦
长度不固定，随ID增长
◦
需要唯一ID生成器
◦
不可能发生冲突
◦
如果ID按1递增，则很容易找到下一个短网址（可能存在安全风险）
URL Shortening Flow
检查是否longURL存在于数据库中。
如果找到，则返回已有shortURL.
否则：
◦
使用分布式ID生成器生成一个唯一ID。
◦
将ID转换为shortURL采用Base 62编码。
◦
将<id, shortURL, longURL>映射存储在数据库中。
URL Redirecting Flow
用户点击一个shortURL.
查询<shortURL, longURL>映射：
◦
首先检查缓存以获得更快的访问速度。
◦
如果不在缓存中，则查询数据库。
将用户重定向至longURL.
其他注意事项
Rate Limiter
•
通过为每个IP地址设置请求数量限制来防止滥用。
Scalability
Web层：无状态，可通过增减Web服务器实现扩展。
数据库层：采用复制与分片技术。
Analytics
•
收集点击率、来源及时间戳等数据，以获取业务洞察。
High Availability and Reliability
•
通过数据库复制与容错设计，确保服务的一致性和可靠性。