短链接服务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 。