Step 1 - 理解需求，确定设置范围
沟通并确定以下问题：
- 系统负载多大？=> 每天生成1亿条短地址
- 短网址长度有什么要求？=> 越短越好
- 短网址字符有什么要求？=> 字母加数字
- 已生成的短网址可更新或删除吗？=> 不允许
基本需求：
- URL压缩：给定长URL => 压缩成短URl
- URL重定向：给定短URL => 重定向到原始URL
- 高可用性，扩展性，以及容错能力
规模预估：
- 写操作：每天生成1亿条短地址
- 每秒写操作：1亿 / 24 / 3600 = 1160
- 读操作：假设读写比例是10:1，那么每秒的读操作是11600
- 假设服务持续运行10年，意味着必须记录 1亿*365*10 = 3650亿 条记录
- 存储需求：3650亿*100字节/条*10年= 365TB
Step 2 - 高阶设计
讨论API接口，URL重定向，以及URL压缩流程。
API接口
设计REST风格的API接口，以提供短网址服务，一共有以下两个接口：
1. URL压缩，使用POST方法，客户端在请求中附带原始的URL参数，服务器返回经过压缩的短URL，这个方法的示例如下：
POST /api/v1/data/shorten
POST参数:{longURL: longURLString}
返回：短URL
2. URL重定向，使用GET方法，客户端提供短URL，服务器提供301永久重定向到原始URL，如下：
两种重定向：
301永久重定向：用于告知浏览器该地址被永久重定向到另一个地址，浏览器会缓存该信息，下次再访问相同的地址时，浏览器不再请求服务器，而是直接按缓存中的信息直接将链接重定向到新地址。只有在浏览器端清除缓存，才有可能改变对地址的重定向。
302临时重定向：用于告知浏览器该地址被临时重定向到另一个地址，浏览器不会缓存该信息，下次再访问相同的地址时，浏览器仍然会向服务器发起请求。
以上两种重定向方式，301永久重定向有助于降低服务器端的负载，因为只有第一次请示会发送到服务器，后续的重定向都由浏览器负责完成。但如果想在服务器端做流量统计，则必须使用302临时重定向。
URL压缩
整体来看，URL压缩可看成一个哈希操作，需要找到一个哈希函数fx，使得原始URL经过fx后变成短URL，如下：
哈希函数fx必须满足以下特性：
- 长地址必须唯一地被映射到短地址
- 短地址可以被唯一地映射回长地址
Step 3 - 详细设计
讨论数据模型，哈希函数，URL压缩以及URL重定向。
数据模型
使用关系型数据库来存储短地址与原始地址的关系，数据库可以简单到只包含三列：id，shortURL, long URL，如下：
哈希函数
用于将长地址映射到一个短地址，也称为哈希值。
哈希值长度
按上面的讨论，短网址只能包含[0-9, a-z, A-Z]以内的字符，一共有10+26+26=62个可选字符。由于总共要3650亿条记录，在确定哈希值长度时，必须要保证长度n对应的65^n > 3650亿。经过一点点的计算可确定n=7时满足需求，所以哈希值长度为7，也就是短地址只需要使用7位字符来表示。
哈希+冲突检测算法
先使用一些知名的哈希算法对长网址计算哈希值，以下是分别使用CRC32, MD5, SHA-1对https://en.wikipedia.org/wiki/Systems_design进行计算的结果：
在这些算法结果的基础上，选出7位