链接/内推码]生成系统设计"/>
[短链接/内推码]生成系统设计
背景和目标
长URL转换成短URL
-
用户输入长url获取短url
-
用户点击短url可以跳转到长url
需求分析
-
要完成上面2个功能
-
需要实现短链接生成器
-
长链接转换成短链接(持久化存储)
-
-
存储容量
-
每月生成URL 5亿条,端URL有效期两年 ⇒ 2*12*5亿 = 120亿
-
-
存储空间
-
每条端URL数据库记录大约1KB ⇒ 120亿 * 1KB = 12TB
-
-
吞吐量QPS
-
每条短URL,每天平均读取次数100次,那么总的访问量 = 5亿 * 100 = 500亿
-
每秒的平均访问量 = QPS = 500亿 / (30 * 24 * 60 * 60) ≈ 20000
-
一般高峰期,访问量是平均访问量的2倍 ⇒ 系统架构应该支撑的QPS≈4W
-
-
网络带宽
-
短URL的重定向响应包含:长URL地址,约500B
-
HTTP响应头其他内容大约500B
-
-
耗时:请求响应时间
-
P80 < 5ms
-
P99 < 20ms
-
概要设计
短URL生成器设计:长URL,通过某种函数,计算得到一个6个字符串的端URL
1.方案对比
实现细节 | 优缺点 | |
方案1 | 1、长URL利用MD5/sha1(哈希)计算 2、执行base64编码,截取前6位 | 存在哈希冲突 |
方案2 | 1、自增自然数 2、base64编码 | 优点:唯一,无冲突 缺点:不安全,有规律可循 |
方案3 | 预生成短URL 1、预先生成没有冲突的短URL 2、外部请求时,直接从短URL池中获取一个 | 优点:唯一,无冲突,安全 |
最终方案:方案3
2.预生成短URL
-
预生成端URL算法:采用随机数来实现,转base62,生成6位的字符串作为短URL
-
避免短URL冲突
-
bloom过滤器
-
-
短URL存储
步骤
-
先把已经生成的HDFS存放的短URL,全部加载到Bloom过滤器中
-
预生成器服务,循环生成短URL
-
判断Bloom过滤器中是否存在短URL
-
若不存在,说明一定不存在,就更新写Bloom过滤器&&插入HDFS
-
若存在,说明可能存在or可能不存在,(认为重复了)直接跳过
-
-
3.输入长URL返回短URL
-
向HDFS申请一批短URL段
-
短链接服务访问HDFS文件的流程:写打开偏移量文件 -> 读偏移量 -> 读打开短 URL 文件 -> 从偏移量开始读取 60K 数据 -> 关闭短 URL 文件 -> 修改偏移量文件 -> 关闭偏移量文件
-
分析:系统除了需要一个在 HDFS 记录预生成短 URL 的文件外,还需要一个记录偏移量的文件,记录偏移量的文件也存储在 HDFS 中
-
每次读写偏移量文件时,都采用读写锁控制,保证:第一个预加载短 URL 服务器写打开偏移量文件以后,其他预加载短 URL 服务器无法再写打开该文件,也就无法完成读 60K 短 URL 数据及修改偏移量的操作,这样就能保证这两个操作是并发安全的
-
-
减少GC的压力
-
短链接分发服务需要保存申请的1w个待分发的短URL,采用的数据结构最好是“环形队列”,消除频繁的内存释放和分配
-
-
减少请求抖动
-
问题场景:当size=0时,需要同步请求HDFS,申请size个短URL
-
解决方案:环形队列保存定长的buffer,当使用量减少到20%时,开启协程异步去HDFS重新获取(保证环形队里的size不会被消耗殆尽,最少保持20%的buffer)
-
更多推荐
[短链接/内推码]生成系统设计
发布评论