短链接服务TinyURL系统设计
场景
短链接服务,可以通过将一个普通的冗长的网址缩短成一个新的较短的网址,便于分享传播。短链接服务的主要应用场景有短信发送、社群推广等。短链接服务TinyURL需要实现的基本功能有:
- 根据长URL生成一个短URL
- 根据短URL还原长URL,并跳转
服务
TinyURL是一个比较简单的服务,本身就是一个小的应用。
函数设计:
public String getLongUrl(String shortUrl)
public String createShortUrl(String longUrl)
接口设计:
GET /{shortUrl}
跳转到长URL
POST /shorten
{
"url": "http://xxx"
}
返回短URL
存储
只需要存储短URL与长URL的映射即可。
库表设计:
字段 | 类型 | 含义 | 说明 |
---|---|---|---|
id | gitint | 主键ID | |
short_url | varchar(12) | 短URL | 唯一索引 |
long_url | varchar(1024) | 长URL | |
ctime | bigint | 创建时间 |
短URL不能重复,且经常需要根据短URL进行查询,故为短URL添加唯一索引。
对于短URL,一般采用Base62编码,6位能表示约568亿个URL,足够用了。
实现
核心问题是:如何为每个长URL分配一个短URL,并且短URL是唯一的。
基于全局唯一ID
基于全局唯一ID的实现方案流程如下:
有很多分布式唯一ID生成服务,如美团的Leaf:Meituan-Dianping/Leaf: Distributed ID Generate Service
基于Hash
基于Hash的实现方案流程如下:
对于Hash算法的选取,主要考虑碰撞率、运算性能等。对于短链接服务,可以使用Murmur哈希算法。
Murmur哈希算法并不关心安全性,是一种非加密型哈希函数,适用于一般的哈希检索操作。Murmur哈希算法有着低碰撞率与高运算性能,在Redis、HBase、Lucene等有所应用。
可以使用布隆过滤器来判断短URL是否重复,如果短URL不存在则一定不存在。对于布隆过滤器的参数选取,可以参考:Bloom filter calculator
扩展
HTTP重定向使用301还是302跳转?
301代表永久重定向,302代表临时重定向。对于301跳转,浏览器会缓存重定向地址,这样可以降低短链接服务的负载,但因此无法获取真实的点击量。而302跳转,浏览器每次都会获取重定向地址,方便统计点击量。因此,短链接服务一般采用302跳转。
根据短URL查询长URL如何优化?
1、使用布隆过滤器判断短URL是否存在,如果不存在,直接返回,这样可以避免缓存穿透。
2、缓存短URL到长URL的映射,先查缓存,如果缓存中没有查到再到数据库进行查询。
3、为了避免在缓存失效时大量请求同时打到数据库(也就是缓存击穿),使用短URL粒度的分布式锁,只有持有锁的线程才能查询数据库并写入缓存,之后的线程便能直接查缓存了。
代码
我实现了一个简单的短链接服务:demo-projects/tiny-url at master · straicat/demo-projects
核心代码位于com.example.tinyurl.service.TinyUrlService
。
提供了两种生成短URL的方法,可以通过application.properties
中的shorten.method
来控制:1
表示基于全局唯一ID,此时依赖Leaf服务,需要配置leaf.url
;2
表示基于Hash,不需要leaf.url
。