写了一个支持千万级别的短链生成器,个人感觉比网上的都优秀不少,甚至是最优秀的,优化做到了极致,欢迎大家沟通交流。 如果哪位大佬有比较好的机器,欢迎压测一波,看看性能能到哪里去
代码 github 链接 short-url。
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); // 解决冲突多的问题,随机字符串
}
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<ShortUrl> wrapper = new QueryWrapper<ShortUrl>().lambda().eq(ShortUrl::getSUrl, shortUrl);
ShortUrl url = shortUrlDAO.selectOne(wrapper);
CacheUtils.put(MapConstants.shortCache, shortUrl, url.getLUrl());
return url.getLUrl();
}
1
eluotao 188 天前
已 Start
|
2
drymonfidelia 188 天前 via iPhone
优化做到极致 至少也得用 C++写吧
C#都比 Java 快 |
3
tianheg 188 天前 via Android
你的项目初始化时间怎么是:1970-01-01
|
5
byte10 188 天前
base62 原来还有这个玩意,解决了我 URL 遇到的问题,给力👍🏻
|
6
laobobo 188 天前
我擦,55 年前的项目,肯定是个优秀的项目
|
7
13240284671 188 天前
这玩意很难合规,容易被墙
|
10
kuanat 187 天前
假设 URL 的最大长度是 2KB ,一千万( 10M )条数据占用的内存不过 20GB 而已。
|
11
bigbigeggs OP @drymonfidelia 语言这个可以先不关心,整个算法流程,基本已经做到了极致。语言这玩意还真不好说
|
12
bigbigeggs OP |
13
bigbigeggs OP @kuanat 应用是推特,微博这种。比如最长 140 个字,我的 url 就占用 50 多个字符了,很浪费,有了短链的存在
|
14
kuanat 187 天前 via Android
@bigbigeggs #11
你没有理解我的意思,我是说当你的设计目标是千万级的时候,这些优化一点都不重要。 当你考虑做成比如说十亿级别服务的时候,瓶颈就不在什么 hash 算法这些你关注的细节了。 过早优化是万恶之源。 |
15
blankmiss 187 天前 1
"用 MD5 ,SHA 等算法,其实这样做有点杀鸡用牛刀了,而且既然是加密就意味着性能上会有损失
实际上性能是 MD5 等加密算法的十倍以上 " 这不是摘要算法吗 |
16
mosliu 186 天前 1
1. 碰撞 这个的几率随着量的增加,不是平滑的。 所以没测到 1000w 不好说 1000w 的概率是多少。
2. 既然数据库慢 为什么非要访问数据库 开个 bloomfilter 初始化参数预估 2kw 的量 预计碰撞概率降到千万分之一 内存占用也不到 100m 吧 |
17
nicoljiang 186 天前
一直没有 get 到短链接的技术含量(分析流量不算):
|
18
nicoljiang 186 天前
按你这种说法,我也可以试着提出一个 10 亿级别的短链生成器,看是不是合理:
1. 不使用任何第三方数据库,leveldb 单机轻松支持 10 亿条记录的增删点查; 2. 使用 leveldb 的话,似乎也用不着特地做什么 Cache 了; 3. 抛弃 hash ,使用计数器,从 0 轮询到 10 亿个数字,然后转成 36 进制( 10 亿变成 36 进制也就是 6 位); 4. 不用 hash ,再优秀的 hash 速度也会比进制转换慢; 5. leveldb 普通情况下应该没有“打挂”这个概念了。 |
19
oiYuer 185 天前 1
我也没明白为什么非要 hash ,进制转换+openresty 热缓存就能实现绝大多数公司自建短链接服务的基本需求了(数据量、吞吐量、更短的链接、永久的时效)
丐版一点的实现方案甚至都不需要用 java/go 之类语言去专门编写服务,openresty+lua 一把梭🐶 |
20
bigbigeggs OP @mosliu 1. 机器性能不够,500W murmur64 0 冲突,1000W 不好说 2. 数据库慢,其实可以通过分库分表,读写分离,依然可以得到很好的性能,微博底层就是数据库。如果不选择数据库,选择 hbase ,es 等,反而有更多的其他问题需要解决。3. bloomfilter 过滤器我感觉这里用处不大,如果存在不一定真的不存在,如果不存在才是真的一定不存在,这个存在还是去查数据库,感觉用处有限
|
21
bigbigeggs OP @nicoljiang 感谢分享,刚才简单 google 了下 leveldb ,有点像 mongdb ?如果效率高,可以考虑使用,至于为什么我没有选择计数器,使用计数器还需要单独维护一个全局变量,使用中间件的话,反而降低了短链的稳定性
|
22
bigbigeggs OP @oiYuer 如果单说性能的话,要求非常非常高。openresty+lua 是一个很好的解决方案,但它的稳定性感觉有待商榷
|
23
emartcn 183 天前
最流行的高性能数据库用上:sqlite
|
24
nicoljiang 183 天前
@bigbigeggs 不像 mongodb ;你已经维护一个巨大的 map ,但却不想多维护一个纯数字的定时器么。
|