设计一个网址缩短器

设计一个系统，将用户提供的网址转换为缩短的网址，并重定向回原始网址。描述系统的工作原理。你将如何分配缩短的网址？你将如何存储缩短网址与原始网址的映射？你将如何实现重定向服务器？你将如何存储点击统计数据？

假设：我通常不会在初始问题陈述中包含这些假设。优秀的候选人会在提出设计时询问规模。

• 注册重定向网址的独特域名总数大约在数万左右
• 新网址注册量约为 10,000,000/天（100/秒）
• 重定向请求量约为 10B/天（100,000/秒）
• 提醒候选人这些是平均数字 - 在高峰流量时（例如“人们下班回家时”或“超级碗期间”）可能会高得多。
• 最近的统计数据（在当前日期内）应聚合并在 5 分钟延迟后可用
• 长期回顾统计数据可以每天计算

假设

每天 1B 新网址，总共 100B 条目 越短越好 显示统计数据（实时和每日/月度/年度）

编码网址

http://blog.codinghorror.com/url-shortening-hashes-in-practice/

选择 1. md5（128 位，16 个十六进制数字，碰撞，生日悖论，2^(n/2) = 2^64）截断？（64 位，8 个十六进制数字，碰撞 2^32），Base64。

• 优点：哈希简单且水平可扩展。
• 缺点：太长，如何清理过期网址？

选择 2. 分布式序列 ID 生成器。（Base62：az，AZ，0~9，62 个字符，62^7），分片：每个节点维护一部分 ID。

• 优点：易于淘汰过期条目，更短
• 缺点：协调（zookeeper）

KV 存储

MySQL（10k qps，慢，无关系），KV（100k qps，Redis，Memcached）

优秀的候选人会询问别名的生命周期，并设计一个系统来清理过期的别名。

后续问题

问：如何生成缩短的网址？

• 一个差的候选人会提出一个使用单一 ID 生成器的解决方案（单点故障）或一个在每个请求中需要协调 ID 生成器服务器的解决方案。例如，使用自增主键的单一数据库服务器。
• 一个可接受的候选人会提出使用网址的 md5，或某种形式的 UUID 生成器，可以在任何节点独立完成。虽然这允许分布式生成不冲突的 ID，但会产生较大的“缩短”网址。
• 一个优秀的候选人会设计一个解决方案，利用一组 ID 生成器，从中央协调器（例如 ZooKeeper）保留 ID 空间的块，并独立从其块中分配 ID，必要时刷新。

问：如何存储映射？

• 一个差的候选人会建议使用单体数据库。这个存储没有关系方面。它是一个纯粹的键值存储。
• 一个优秀的候选人会建议使用任何轻量级的分布式存储。MongoDB/HBase/Voldemort 等等。
• 一个优秀的候选人会询问别名的生命周期，并设计一个系统来==清理过期的别名==。

问：如何实现重定向服务器？

• 一个差的候选人会从头开始设计某种东西来解决一个已经解决的问题。
• 一个优秀的候选人会建议使用现成的 HTTP 服务器，配备一个插件，解析缩短的网址键，在数据库中查找别名，更新点击统计并返回 303 到原始网址。Apache/Jetty/Netty/tomcat 等等都可以。

问：点击统计数据如何存储？

• 一个差的候选人会建议在每次点击时写回数据存储。
• 一个优秀的候选人会建议某种形式的==聚合层，接受点击流数据，聚合并定期写回持久数据存储==。

问：如何对聚合层进行分区？

• 一个优秀的候选人会建议使用低延迟消息系统来缓冲点击数据并将其传输到聚合层。
• 一个候选人可能会询问统计数据需要多频繁更新。如果是每日更新，将其存储在 HDFS 中并运行 map/reduce 作业来计算统计数据是一个合理的方法。如果是近实时的，聚合逻辑应计算统计数据。

问：如何防止访问受限网站？

• 一个优秀的候选人可以回答通过在 KV 存储中维护一个主机名黑名单。
• 一个优秀的候选人可能会提出一些高级扩展技术，如布隆过滤器。