写了一个支持千万级别的短链生成器，欢迎大家交流沟通

[bigbigeggs]

写了一个支持千万级别的短链生成器，个人感觉比网上的都优秀不少，甚至是最优秀的，优化做到了极致，欢迎大家沟通交流。 如果哪位大佬有比较好的机器，欢迎压测一波，看看性能能到哪里去

代码 github 链接 short-url。

优化点(难点、亮点)

1. 生成短链只需要访问一次数据库。而不是传统的先查询，在判断插入，而是直接插入，用唯一索引来判断是否 hash 冲突
2. 利用 LRUCache ，将最近生成的几千个 kv 放进 map 中，一段时间内，同一个长 url 会生成相同的短 url
3. hash 冲突后，给 hash 冲突值 加一个随机 url ，降低冲突概率
4. 选择比较优秀的 murmur64 hash 算法
5. get 获取常链的时候，利用 LRU 识别热点数据，直接从 map 中读取，防止打挂数据库

核心代码如下

1. 生成 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);  // 解决冲突多的问题，随机字符串
}

1. 获取 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<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();
}

[eluotao]

已 Start

[drymonfidelia]

优化做到极致 至少也得用 C++写吧
C#都比 Java 快

[tianheg]

你的项目初始化时间怎么是：1970-01-01

[Radiation]

@tianheg 55 年前，6~

[byte10]

base62 原来还有这个玩意，解决了我 URL 遇到的问题，给力👍🏻

[laobobo]

我擦，55 年前的项目，肯定是个优秀的项目

[13240284671]

这玩意很难合规，容易被墙

[SkyHighR]

@tianheg #3 git 提交时间可以改的啊

[lansg]

@laobobo 哈哈哈怎么回事这个

[kuanat]

假设 URL 的最大长度是 2KB ，一千万（ 10M ）条数据占用的内存不过 20GB 而已。

[bigbigeggs]

@drymonfidelia 语言这个可以先不关心，整个算法流程，基本已经做到了极致。语言这玩意还真不好说

[bigbigeggs]

@tianheg @Radiation @laobobo @lansg 哈哈哈，spring initializer 生成的就是 55 年之前的项目

[bigbigeggs]

@kuanat 应用是推特，微博这种。比如最长 140 个字，我的 url 就占用 50 多个字符了，很浪费，有了短链的存在

[kuanat]

@bigbigeggs #11

你没有理解我的意思，我是说当你的设计目标是千万级的时候，这些优化一点都不重要。

当你考虑做成比如说十亿级别服务的时候，瓶颈就不在什么 hash 算法这些你关注的细节了。

过早优化是万恶之源。

[blankmiss]

"用 MD5 ，SHA 等算法，其实这样做有点杀鸡用牛刀了，而且既然是加密就意味着性能上会有损失
实际上性能是 MD5 等加密算法的十倍以上 " 这不是摘要算法吗

[mosliu]

1. 碰撞 这个的几率随着量的增加，不是平滑的。 所以没测到 1000w 不好说 1000w 的概率是多少。
2. 既然数据库慢 为什么非要访问数据库 开个 bloomfilter 初始化参数预估 2kw 的量 预计碰撞概率降到千万分之一 内存占用也不到 100m 吧

[nicoljiang]

一直没有 get 到短链接的技术含量（分析流量不算）：

[nicoljiang]

按你这种说法，我也可以试着提出一个 10 亿级别的短链生成器，看是不是合理：
1. 不使用任何第三方数据库，leveldb 单机轻松支持 10 亿条记录的增删点查；
2. 使用 leveldb 的话，似乎也用不着特地做什么 Cache 了；
3. 抛弃 hash ，使用计数器，从 0 轮询到 10 亿个数字，然后转成 36 进制（ 10 亿变成 36 进制也就是 6 位）；
4. 不用 hash ，再优秀的 hash 速度也会比进制转换慢；
5. leveldb 普通情况下应该没有“打挂”这个概念了。

[oiYuer]

我也没明白为什么非要 hash ，进制转换+openresty 热缓存就能实现绝大多数公司自建短链接服务的基本需求了（数据量、吞吐量、更短的链接、永久的时效）
丐版一点的实现方案甚至都不需要用 java/go 之类语言去专门编写服务，openresty+lua 一把梭🐶

[bigbigeggs]

@mosliu 1. 机器性能不够，500W murmur64 0 冲突，1000W 不好说 2. 数据库慢，其实可以通过分库分表，读写分离，依然可以得到很好的性能，微博底层就是数据库。如果不选择数据库，选择 hbase ，es 等，反而有更多的其他问题需要解决。3. bloomfilter 过滤器我感觉这里用处不大，如果存在不一定真的不存在，如果不存在才是真的一定不存在，这个存在还是去查数据库，感觉用处有限

[bigbigeggs]

@nicoljiang 感谢分享，刚才简单 google 了下 leveldb ，有点像 mongdb ？如果效率高，可以考虑使用，至于为什么我没有选择计数器，使用计数器还需要单独维护一个全局变量，使用中间件的话，反而降低了短链的稳定性

[bigbigeggs]

@oiYuer 如果单说性能的话，要求非常非常高。openresty+lua 是一个很好的解决方案，但它的稳定性感觉有待商榷

[emartcn]

最流行的高性能数据库用上：sqlite

[nicoljiang]

@bigbigeggs 不像 mongodb ；你已经维护一个巨大的 map ，但却不想多维护一个纯数字的定时器么。