[短链接/内推码]生成系统设计

背景和目标

长URL转换成短URL

1. 用户输入长url获取短url

2. 用户点击短url可以跳转到长url

需求分析

1. 要完成上面2个功能

   1. 需要实现短链接生成器

   2. 长链接转换成短链接（持久化存储）

2. 存储容量

   1. 每月生成URL 5亿条，端URL有效期两年 ⇒ 2*12*5亿 = 120亿

3. 存储空间

   1. 每条端URL数据库记录大约1KB ⇒ 120亿 * 1KB = 12TB

4. 吞吐量QPS

   1. 每条短URL，每天平均读取次数100次，那么总的访问量 = 5亿 * 100 = 500亿

   2. 每秒的平均访问量 = QPS = 500亿 / (30 * 24 * 60 * 60) ≈ 20000

   3. 一般高峰期，访问量是平均访问量的2倍 ⇒ 系统架构应该支撑的QPS≈4W

5. 网络带宽

   1. 短URL的重定向响应包含：长URL地址，约500B

   2. HTTP响应头其他内容大约500B

6. 耗时：请求响应时间

   1. P80 < 5ms

   2. P99 < 20ms

概要设计

短URL生成器设计：长URL，通过某种函数，计算得到一个6个字符串的端URL

1.方案对比

最终方案：方案3

2.预生成短URL

1. 预生成端URL算法：采用随机数来实现，转base62，生成6位的字符串作为短URL

2. 避免短URL冲突

   1. bloom过滤器

3. 短URL存储

步骤

1. 先把已经生成的HDFS存放的短URL，全部加载到Bloom过滤器中

2. 预生成器服务，循环生成短URL

   1. 判断Bloom过滤器中是否存在短URL

      1. 若不存在，说明一定不存在，就更新写Bloom过滤器&&插入HDFS

      2. 若存在，说明可能存在or可能不存在，（认为重复了）直接跳过

3.输入长URL返回短URL

1. 向HDFS申请一批短URL段

   1. 短链接服务访问HDFS文件的流程：写打开偏移量文件 -> 读偏移量 -> 读打开短 URL 文件 -> 从偏移量开始读取 60K 数据 -> 关闭短 URL 文件 -> 修改偏移量文件 -> 关闭偏移量文件

   2. 分析：系统除了需要一个在 HDFS 记录预生成短 URL 的文件外，还需要一个记录偏移量的文件，记录偏移量的文件也存储在 HDFS 中

   3. 每次读写偏移量文件时，都采用读写锁控制，保证：第一个预加载短 URL 服务器写打开偏移量文件以后，其他预加载短 URL 服务器无法再写打开该文件，也就无法完成读 60K 短 URL 数据及修改偏移量的操作，这样就能保证这两个操作是并发安全的

2. 减少GC的压力

   1. 短链接分发服务需要保存申请的1w个待分发的短URL，采用的数据结构最好是“环形队列”，消除频繁的内存释放和分配

3. 减少请求抖动

   1. 问题场景：当size=0时，需要同步请求HDFS，申请size个短URL

   2. 解决方案：环形队列保存定长的buffer，当使用量减少到20%时，开启协程异步去HDFS重新获取（保证环形队里的size不会被消耗殆尽，最少保持20%的buffer）