layout	title	date	comments	categories	abstract	language
post	设计一个短网址系统	2018-11-01 02:32	true	system design	设计一个系统，可以将用户给的网址变成短网址，用户使用这些短网址可以访问他们原来给的长网址。系统是怎么运作的，需包括但不限于下面的问题：如何分配短网址；如何存储短网址和长网址的映射关系；如何实现跳转服务；如何存储访问数据。	zh-cn

设计一个系统，可以将用户给的网址变成短网址，用户使用这些短网址可以访问他们原来给的网址（下面简称长网址）。描述这个系统是怎么运作的，需包括但不限于下面的问题：怎么分配短网址？怎么存储短网址和长网址的映射关系？怎么实现跳转服务？怎么存储访问数据？

假设：在一开始的问题描述中不包含这些假设。一个优秀的面试者在得到一个具体设计的时候会问关于系统规模的问题。

长网址的域名大概有上万个
新的长网址流量大概是 10,000,000/天（100/秒）
使用短网址访问长网址的跳转服务的流量大概是 10B/天（100,000/秒）
提醒面试者这些是平均数字 - 在一些高峰期的时候这些数字会大很多（一种时间导致的高峰期，比如用户刚工作完回家的时候，另一种是事件导致的高峰期，比如春节联欢晚会的时候）
最近的数据（比如今天的数据）应该被提前收集好，并且在用户想要看的时候可以在五分钟内得到。
每天计算历史数据

假设

每天有1B新网址，100B的短网址访问短网址越短越好数据的展示（实时/每天/每个月/每年）

网址编码

方法1. md5(128位，16个16进制数字，冲突，生日悖论，2^(n/2) = 2^64) 再短一些？（64位，8个16进制数字，冲突 2^32）, 64进制。

方法2. 分布式的序号生成器。(62进制: a~~z, A~~Z, 0~9, 62种字符, 62^7), 分区：每个节点包含一些序号。

MySQL(10k 每秒访问量，慢，没有关系不需要关系型数据库)，键值（100k 每秒访问量，Redis, Memcached）

一个优秀的面试者会问关于短网址的预期使用期限，设计一套系统可以自动清理已经过期的短网址。

问题：怎么生成短网址？

一个差的面试者会提议用一个id生成器（单点故障）或者要在每个id生成的时候需要id生成器之间协同合作。举例，使用自动增值的主键（auto-increment primary key）的数据库。
一个可以接受的面试者会提议用md5，或者一些UUID生成器可以在一些结点上自己生成id的。这些方法可以在分布式系统上生成不冲突的ID，所以可以生产大量的短网址。
一个优秀的面试者会设计一个方法利用一些id生成器，每个生成器先从中央协调器（例如ZooKeeper）保留一块id序列，这些id生成器可以单独从他们的id序列中分配id，有必要的时候在自己的id序列中做一些清理。

问题：怎么存储长网址和短网址之间的映射关系？

问题：怎么实现跳转服务？

一个差的面试者会从头开始设计这套系统来解决已经被解决的问题
一个优秀的面试者会建议使用一个现成的HTTP服务器加上一个插件，用这个插件来翻译这个短网址的id，在数据库中找这个id，更新访问数据，返回303，跳转到长网址。现成HTTP服务器比如 Apache/Jetty/Netty/tomcat 等。

问题：怎么存储访问数据？

问题：怎么分上一个问题优秀面试者提出的存储访问数据的不同部分？

一个优秀的面试者会建议用一个延迟较低的信息系统去暂时存储访问数据，然后将数据交给收集整理部分
面试者可能会问访问数据多久需要被更新一次。如果每天更新，一个比较合理的方法是存储在HDFS，用map/reduce去计算数据。如果是要近乎实时的数据，收集整理的部分就要计算出所需的数据

问题：怎么阻止访问受限的网站？