共计 2052 个字符,预计需要花费 6 分钟才能阅读完成。
写了一个支持千万级别的短链生成器,个人感觉比网上的都优秀不少,甚至是最优秀的,优化做到了极致,欢迎大家沟通交流。
如果哪位大佬有比较好的机器,欢迎压测一波,看看性能能到哪里去
代码 github 链接 short-url。
优化点 (难点、亮点)
- 生成短链只需要访问一次数据库。而不是传统的先查询,在判断插入,而是直接插入,用唯一索引来判断是否 hash 冲突
- 利用 LRUCache,将最近生成的几千个 kv 放进 map 中,一段时间内,同一个长 url 会生成相同的短 url
- hash 冲突后,给 hash 冲突值 加一个随机 url,降低冲突概率
- 选择比较优秀的 murmur64 hash 算法
- get 获取常链的时候,利用 LRU 识别热点数据,直接从 map 中读取,防止打挂数据库
核心代码如下
- 生成 url 核心算法(着重看下 hash 冲突解决方法 && LRU 的 cache 也需要关注)
public String generateShortUrl(String longUrl) {if (StringUtils.isEmpty(longUrl)) {throw new RuntimeException("longUrl 不能为空");
}
String shortUrl = CacheUtils.get(MapConstants.longCache, longUrl);
if (StringUtils.isNotEmpty(shortUrl)) {return shortUrl;}
return getShortUrl(longUrl, getLongUrlRandom(longUrl));
}
private String getShortUrl(String rawUrl, String longUrl) {long hash = HashUtil.murmur64(longUrl.getBytes());
String base62 = Base62.encode(hash + "");
log.info("longUrl = {}, hash = {}, base62 = {}", longUrl, hash, base62);
if (StringUtils.isEmpty(base62)) {throw new RuntimeException("hash 算法有误");
}
String shortUrl = StringUtils.substring(base62, 6);
ShortUrl url = new ShortUrl(rawUrl, shortUrl);
try {int insert = shortUrlDAO.insert(url); // 这里进行分库分表 提高性能
if (insert == 1) {CacheUtils.put(MapConstants.longCache, rawUrl, shortUrl);
}
} catch (DuplicateKeyException e) {
// Hash 冲突
log.warn("hash 冲突 触发唯一索引 rawUrl = {}, longUrl = {}, shortUrl = {}, e = {}", rawUrl, longUrl, shortUrl, e.getMessage(), e);
CacheUtils.put(MapConstants.hashFailMap, rawUrl, shortUrl);
return getShortUrl(rawUrl, getLongUrlRandom(shortUrl));
} catch (Exception e) {log.error("未知错误 e = {}", e.getMessage(), e);
throw new RuntimeException("msg =" + e.getMessage());
}
return shortUrl;
}
private String getLongUrlRandom(String longUrl) {return longUrl + RandomUtil.randomString(6); // 解决冲突多的问题,随机字符串
}
- 获取 url 核心算法
public String getLongUrl(String shortUrl) {if (StringUtils.isEmpty(shortUrl)) {throw new RuntimeException("shortUrl 不能为空");
}
String longUrl = CacheUtils.get(MapConstants.shortCache, shortUrl);
if (StringUtils.isNotEmpty(longUrl)) {return longUrl;}
LambdaQueryWrapper wrapper = new QueryWrapper().lambda().eq(ShortUrl::getSUrl, shortUrl);
ShortUrl url = shortUrlDAO.selectOne(wrapper);
CacheUtils.put(MapConstants.shortCache, shortUrl, url.getLUrl());
return url.getLUrl();}
正文完