在社交媒体上，人们经常需要分享一些URL，但是有些URL 可能会很长，比如：https://geek.qq.org/hybrid/pvip?utm_source=geek-pc-discover-banner&utm_term=geek-pc-discover-banner这样长的URL 显然体验并不友好。我们期望分享的是一些更短、更易于阅读的短URL，比如像http://1.cn/ScW4dt这样的。当用户点击这个短URL 的时候，可以重定向访问到原始的链接地址。为此我们将设计开发一个短URL生成器，产品名称是“Fuxi（ 伏羲）”。
我们预计Fuxi 需要管理的短URL 规模在百亿级别，并发吞吐量达到数万级别。这个量级的数据对应的存储方案是什么样的？用传统的关系数据库存储，还是有其他更简单的办法？此外，如何提升系统的并发处理能力呢？这些是我们今天要重点考虑的问题。
需求分析
短URL 生成器，也称作短链接生成器，就是将一个比较长的URL 生成一个比较短的URL，当浏览器通过短URL 生成器访问这个短URL 的时候，重定向访问到原始的长URL 目标服务器，访问时序图如下。
对于需要展示短URL 的应用程序，由该应用调用短URL 生成器生成短URL，并将该短URL 展示给用户，用户在浏览器中点击该短URL 的时候，请求发送到短URL 生成器（短URL 生成器以HTTP 服务器的方式对外提供服务，短URL 域名指向短URL 生成器），短URL 生成器返回HTTP 重定向响应，将用户请求重定向到最初的原始长URL，浏览器访问长URL 服务器，完成请求服务。
短URL 生成器的用例图
- 用户client 程序可以使用短URL 生成器Fuxi 为每个长URL 生成唯一的短URL，并存储起来。
- 用户可以访问这个短URL，Fuxi 将请求重定向到原始长URL。
- 生成的短URL 可以是Fuxi 自动生成的，也可以是用户自定义的。用户可以指定一个长URL 对应的短URL 内容，只要这个短URL 还没有被使用。
- 管理员可以通过web 后台检索、查看Fuxi 的使用情况。
- 短URL 有有效期（2 年），后台定时任务会清理超过有效期的URL，以节省存储资源，同时回收短URL 地址链接资源。
性能指标估算
Fuxi 的存储容量和并发量估算如下：
预计每月新生成短URL 5 亿条，短URL 有效期2 年，那么总URL 数量120 亿。$5 x 12 x 2 = 120亿$
- 存储空间：每条短URL 数据库记录大约1KB，那么需要总存储空间12 TB（不含数据冗余备份）。$120亿 / 1kB = 12TB $
- 吞吐量：每条短URL 平均读取次数100 次，那么平均访问吞吐量（每秒访问次数）2 万：5亿 x 100 / ( 30 x 24 x 60 x 60) = 2W。一般系统高峰期访问量是平均访问量的2 倍，因此系统架构需要支持的吞吐能力应为4万。
- 网络带宽：短URL 的重定向响应包含长URL 地址内容，长URL 地址大约500B，HTTP 响应头其他内容大约500B，所以每个响应1KB，高峰期需要的响应网络带宽320Mb。 4 万次请求(每秒) / 1KB = 40MB\times8bit = 320Mb
- Fuxi 的短URL 长度估算如下。短URL 采用Base64 编码，如果短URL 长度是7 个字符的话，大约可以编码4 万亿个短URL：$64^{7}$ = 4 万亿。如果短URL 长度是6 个字符的话，大约可以编码680 亿个短URL。$64^{6}$ / 680 亿
按我们前面评估，总URL 数120 亿，6 个字符的编码就可以满足需求。因此Fuxi 的短URL 编码长度6 个字符，形如http://l.cn/ScW4dt 。
非功能需求
- 系统需要保持高可用，不因为服务器、数据库宕机而引起服务失效。
- 系统需要保持高性能，服务端80%请求响应时间应小于5ms，99%请求响应时间小于20ms，平均响应时间小于10ms。
- 短URL 应该是不可猜测的，即不能猜测某个短URL 是否存在，也不能猜测短URL可能对应的长URL 地址内容。
概要设计
短URL 生成器的设计核心就是短URL 的生成，即长URL 通过某种函数，计算得到一个6 个字符的短URL。短URL 有几种不同的生成算法。
单项散列函数生成短URL
通常的设计方案是，将长URL 利用MD5 或者SHA256 等单项散列算法，进行Hash计算，得到128bit 或者256bit 的Hash 值。然后对该Hash 值进行Base64 编码，得到22 个或者43 个Base64 字符，再截取前面的6 个字符，就得到短URL 了，如图。
但是这样得到的短URL，可能会发生Hash 冲突，即不同的长URL，计算得到的短URL是相同的（MD5 或者SHA256 计算得到的Hash 值几乎不会冲突，但是Base64 编码后再截断的6 个字符有可能会冲突）。所以在生成的时候，需要先校验该短URL 是否已经映射为其他的长URL，如果是，那么需要重新计算（换单向散列算法，或者换Base64编码截断位置）。重新计算得到的短URL 依然可能冲突，需要再重新计算。但是这样的冲突处理需要多次到存储中查找URL，无法保证Fuxi 的性能要求。
自增长短URL
一种免冲突的算法是用自增长自然数来实现，即维持一个自增长的二进制自然数，然后将该自然数进行Base64 编码即可得到一系列的短URL。这样生成的的短URL 必然唯一，而且还可以生成小于6 个字符的短URL，比如自然数0 的Base64 编码是字符“A”，就可以用http://1.cn/A作为短URL。
但是这种算法将导致短URL 是可猜测的，如果某个应用在某个时间段内生成了一批短URL，那么这批短URL 就会集中在一个自然数区间内。只要知道了其中一个短URL，就可以通过自增（以及自减）的方式请求访问其他URL。Fuxi 的需求是不允许短URL可预测。
预生成短URL
因此，Fuxi 采用预生成短URL 的方案。即预先生成一批没有冲突的短URL 字符串，当外部请求输入长URL 需要生成短URL 的时候，直接从预先生成好的短URL 字符串池中获取一个即可。
预生成短URL 的算法可以采用随机数来实现，6 个字符，每个字符都用随机数产生（用0~63 的随机数产生一个Base64 编码字符）。为了避免随机数产生的短URL 冲突，需要在预生成的时候检查该URL 是否已经存在（用布隆过滤器检查）。因为预生成短URL是离线的，所以这时不会有性能方面的问题。事实上，Fuxi 在上线之前就已经生成全部需要的144 亿条短URL 并存储在文件系统中（预估需要短URL120 亿，Fuxi 预生成的时候进行了20%的冗余，即144 亿。）
Fuxi 的整体部署模型
Fuxi 的业务逻辑比较简单，相对比较有挑战的就是高并发的读请求如何处理、预生成的短URL 如何存储以及访问。高并发访问主要通过负载均衡与分布式缓存解决，而海量数据存储则通过HDFS 以及HBase 来完成。具体架构图如下。
系统调用可以分成两种情况，一种是用户请求生成短URL 的过程；另一种是用户访问短URL，通过Fuxi 跳转到长URL 的过程。
对于用户请求生成短URL 的过程，在短URL 系统Fuxi 上线前，已经通过随机数算法预生成144 亿条短URL 并将其存储在HDFS 文件系统中。系统上线运行后，应用程序请求生成短URL 的时候（即输入长URL，请求返回短URL），请求通过负载均衡服务器被发送到短URL 服务器集群，短URL 服务器再通过负载均衡服务器调用短URL 预加载服务器集群。
短URL 预加载服务器此前已经从短URL 预生成文件服务器（HDFS）中加载了一批短URL 存放在自己的内存中，这时，只需要从内存中返回一个短URL 即可，同时将短URL与长URL 的映射关系存储在HBase 数据库中，时序图如下。
对于用户通过客户端请求访问短URL 的过程（即输入短URL，请求返回长URL），请求通过负载均衡服务器发送到短URL 服务器集群，短URL 服务器首先到缓存服务器中查找是否有该短URL，如果有，立即返回对应的长URL，短URL 生成服务器构造重定向响应返回给客户端应用。
如果缓存没有用户请求访问的短URL，短URL 服务器将访问HBase 短URL 数据库服务器集群。如果数据库中存在该短URL，短URL 服务器会将该短URL 写入缓存服务器集群，并构造重定向响应返回给客户端应用。如果HBase 中没有该短URL，短URL 服务器将构造404 响应返回给客户端应用，时序图如下。
过期短URL 清理服务器会每个月启动一次，将已经超过有效期（2 年）的URL 数据删除，并将这些短URL 追加写入到短URL 预生成文件中。
为了保证系统高可用，Fuxi 的应用服务器、文件服务器、数据库服务器都采用集群部署方案，单个服务器故障不会影响Fuxi 短URL 的可用性。
对于Fuxi 的高性能要求，80%以上的访问请求将被设计为通过缓存返回。Redis 的缓存响应时间1ms 左右，服务器端请求响应时间小于3ms，满足80%请求小于5ms 的性能目标。对于缓存没有命中的数据，通过HBase 获取，HBase 平均响应时间10ms，也可以满足设计目标中的性能指标。
对于Redis 缓存内存空间估算，业界一般认为，超过80%请求集中在最近6 天生成的短URL 上，Fuxi 主要缓存最近六天生成的短URL 即可。根据需求容量估计，最近6 天生成的短URL 数量约1 亿条，因此需要Redis 缓存服务器内存空间：1 亿 / 1KB = 100GB)。
详细设计
详细设计关注重定向响应码、短URL 预生成文件及加载、用户自定义短URL 等几个关键设计点。
重定向响应码
满足短URL 重定向要求的HTTP 重定向响应码有301 和302 两种，其中301 表示永久重定向，即浏览器一旦访问过该短URL，就将重定向的原始长URL 缓存在本地，此后不再请求短URL 生成器，直接根据缓存在浏览器（HTTP 客户端）的长URL 路径进行访问。
302 表示临时重定向，每次访问短URL 都需要访问短URL 生成器。
一般说来，使用301 状态码可以降低Fuxi 服务器的负载压力，但无法统计短URL 的使用情况，而Fuxi 的架构设计完全可以承受这些负载压力，因此Fuxi 使用302状态码构造重定向响应。
短URL 预生成文件及预加载
Fuxi 的短URL 是在系统上线前全部预生成的，并存储在HDFS 文件中。共144 亿个短URL，每个短URL 6 个字符，文件大小：144 亿 / 6B=86.4GB。文件格式就是直接将144 亿个短URL 的ASC 码无分割地存储在文件中，如下是存储了3 个短URL 的文件示例：
Wdj4FbOxTw9CHtvPM1所以如果短URL 预加载服务器第一次启动的时候加载1 万个短URL，那么就从文件头读取60K 数据，并标记当前文件偏移量60K。下次再加载1 万个短URL 的时候，再从文件60K 偏移位置继续读取60K 数据即可。
因此，Fuxi 除了需要一个在HDFS 记录预生成短URL 的文件外，还需要一个记录偏移量的文件，记录偏移量的文件也存储在HDFS 中。同时，由于预加载短URL 服务器集群部署多台服务器，会出现多台服务器同时加载相同短URL 的情况，所以还需要利用偏移量文件对多个服务器进行互斥操作，即利用文件系统写操作锁的互斥性实现多服务器访问互斥。
应用程序的文件访问流程应该是：写打开偏移量文件-> 读偏移量-> 读打开短URL文件-> 从偏移量开始读取60K 数据-> 关闭短URL 文件-> 修改偏移量文件->关闭偏移量文件。
由于写打开偏移量文件是一个互斥操作，所以第一个预加载短URL 服务器写打开偏移量文件以后，其他预加载短URL 服务器无法再写打开该文件，也就无法完成读60K 短URL 数据及修改偏移量的操作，这样就能保证这两个操作是并发安全的。加载到预加载短URL 服务器的1 万个短URL 会以链表的方式存储，每使用一个短URL，链表头指针就向后移动一位，并设置前一个链表元素的next 对象为null。这样用过的短URL 对象可以被垃圾回收。当剩余链表长度不足2000 的时候，触发一个异步线程，从文件中加载1 万个新的短URL，并链接到链表的尾部。与之对应的URL 链表类图如下。
- URLNode：URL 链表元素类，成员变量uRL 即短URL 字符串，next 指向下一个链表元素。
- LinkedURL：URL 链表主类，成员变量head 指向链表头指针元素，uRLAmount 表示当前链表剩余元素个数。acquireURL()方法从链表头指针指向的元素中取出短URL字符串，并执行urlAmount– 操作。当urlAmount < 2000 的时候，调用私有方法loadURL()，该方法调用一个线程从文件中加载1 万个短URL 并构造成链表添加到当前链表的尾部，并重置uRLAmount。
用户自定义短URL
Fuxi 允许用户自己定义短URL，即在生成短URL 的时候，由用户指定短URL 的内容。为了避免预生成的短URL 和用户指定的短URL 冲突，Fuxi 限制用户自定义短URL 的字符个数，不允许用户使用6 个字符的自定义短URL，且URL 长度不得超过20 个字符。
但是用户自定义短URL 依然可能和其他用户自定义短URL 冲突，所以Fuxi 生成自定义短URL 的时候需要到数据库中检查冲突，是否指定的URL 已经被使用，如果发生冲突，要求用户重新指定。
URL Base64 编码
标准Base64 编码表如下。
其中“+”和“/”在URL 中会被编码为“%2B”以及“%2F”，而“%”在写入数据库的时候又和SQL 编码规则冲突，需要进行再编码，因此直接使用标准Base64 编码
进行短URL 编码并不合适。URL 保留字符编码表如下。
所以，我们需要针对URL 场景对Base64 编码进行改造，使用URL 保留字符表以外的字符对Base64 编码表中的62，63 进行编码：将“+”改为“-”，将“/”改为“_”，
Fuxi 最终采用的URL Base64 编码表如下。
