当前位置：首页 > news >正文

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

news 来源：原创 2024/4/26 14:16:56

背景和目标

长URL转换成短URL

要完成上面2个功能
1. 需要实现短链接生成器
2. 长链接转换成短链接（持久化存储）
存储容量
1. 每月生成URL 5亿条，端URL有效期两年 ⇒ 2*12*5亿 = 120亿
存储空间
1. 每条端URL数据库记录大约1KB ⇒ 120亿 * 1KB = 12TB
吞吐量QPS
1. 每条短URL，每天平均读取次数100次，那么总的访问量 = 5亿 * 100 = 500亿
2. 每秒的平均访问量 = QPS = 500亿 / (30 * 24 * 60 * 60) ≈ 20000
3. 一般高峰期，访问量是平均访问量的2倍 ⇒ 系统架构应该支撑的QPS≈4W
网络带宽
1. 短URL的重定向响应包含：长URL地址，约500B
2. HTTP响应头其他内容大约500B
耗时：请求响应时间
1. P80 < 5ms
2. P99 < 20ms

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

	实现细节	优缺点
方案1	1、长URL利用MD5/sha1（哈希）计算 2、执行base64编码，截取前6位	存在哈希冲突
方案2	1、自增自然数 2、base64编码	优点：唯一，无冲突缺点：不安全，有规律可循
方案3	预生成短URL 1、预先生成没有冲突的短URL 2、外部请求时，直接从短URL池中获取一个	优点：唯一，无冲突，安全

最终方案：方案3

步骤

先把已经生成的HDFS存放的短URL，全部加载到Bloom过滤器中
预生成器服务，循环生成短URL
1. 判断Bloom过滤器中是否存在短URL
  1. 若不存在，说明一定不存在，就更新写Bloom过滤器&&插入HDFS
  2. 若存在，说明可能存在or可能不存在，（认为重复了）直接跳过

向HDFS申请一批短URL段
1. 短链接服务访问HDFS文件的流程：写打开偏移量文件 -> 读偏移量 -> 读打开短 URL 文件 -> 从偏移量开始读取 60K 数据 -> 关闭短 URL 文件 -> 修改偏移量文件 -> 关闭偏移量文件
2. 分析：系统除了需要一个在 HDFS 记录预生成短 URL 的文件外，还需要一个记录偏移量的文件，记录偏移量的文件也存储在 HDFS 中
3. 每次读写偏移量文件时，都采用读写锁控制，保证：第一个预加载短 URL 服务器写打开偏移量文件以后，其他预加载短 URL 服务器无法再写打开该文件，也就无法完成读 60K 短 URL 数据及修改偏移量的操作，这样就能保证这两个操作是并发安全的
减少GC的压力
1. 短链接分发服务需要保存申请的1w个待分发的短URL，采用的数据结构最好是“环形队列”，消除频繁的内存释放和分配
减少请求抖动
1. 问题场景：当size=0时，需要同步请求HDFS，申请size个短URL
2. 解决方案：环形队列保存定长的buffer，当使用量减少到20%时，开启协程异步去HDFS重新获取（保证环形队里的size不会被消耗殆尽，最少保持20%的buffer）