前言

前几天面试遇到的，感觉比较有趣。第一次面试遇到考架构设计相关的题目，挺新奇的，开始向国外大厂靠拢了，比天天问八股文好太多了，工作 5 年左右的，问八股文，纯纯的不负责任偷懒行为。

感觉此问题比较有趣，这几天简单的实现了一版本，和大家分享一下具体的细节，也欢迎大家交流讨论, 代码 github 链接 short-url。

短链生成的几种方法

业界实现短链的方式大概是有两种。

1. Hash 算法

由长 url 通过 hash 算法，生成短的 url，如果 hash 冲突，需要解决解决 hash 冲突。那么这个哈希函数该怎么取呢，相信肯定有很多人说用 MD5，SHA 等算法，其实这样做有点杀鸡用牛刀了，而且既然是加密就意味着性能上会有损失，我们其实不关心反向解密的难度，反而更关心的是哈希的运算速度和冲突概率。

能够满足这样的哈希算法有很多，这里推荐 Google 出品的 MurmurHash 算法，MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其它流行的哈希函数相比，对于规律性较强的 key，MurmurHash 的随机分布特征表现更良好。非加密意味着着相比 MD5，SHA 这些函数它的性能肯定更高（实际上性能是 MD5 等加密算法的十倍以上），也正是由于它的这些优点，所以虽然它出现于 2008，但目前已经广泛应用到 Redis、MemCache、Cassandra、HBase、Lucene 等众多著名的软件中。

1.1 如何缩短域名

MurmurHash32 会生成 32 位的十进制，MurmurHash64 会生成 64 位的十进制。那我们把它转为 62 进制可缩短它的长度，为什么是 62 进制，不是 64 呢？因为 62 进制表示 【a-z A-Z 0-9】字符之和。

1.2 如何解决 hash 冲突

在优秀的哈希函数，都不可避免地会产生哈希冲突（尽管概率很低），该怎么解决呢。我们设计如下 mysql 表

CREATE TABLE `short_url` (  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,  `lurl` varchar(150) NOT NULL,  `surl` varchar(10) NOT NULL,  `gmt_create` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',  PRIMARY KEY (`id`),  UNIQUE KEY `idx_surl` (`surl`),  KEY `idx_lurl` (`lurl`)) ENGINE=InnoDB AUTO_INCREMENT=15536 DEFAULT CHARSET=utf8;

1. 获取长 url，使用 murmur64 进行 hash，并且使用 Base62 encode 一下，取前 6 位

2. 根据短链去 short_url 表中查找看是否存在相关记录，如果不存在，将长链与短链对应关系插入数据库中，存储。

3. 如果存在，则 hash 冲突了。此时在长串上拼接一个随机字段（注意这块优化），再次 hash 即可，直到没有冲突为止。

以上步骤显然是要优化的，插入一条记录居然要经过两次 sql（根据短链查记录，将长短链对应关系插入数据库中），如果在高并发下，显然会成为瓶颈。

1. 我们需要给短链字段 surl 加上唯一索引

2. 我们 hash 之后插入数据库，如果插入失败，说明违反了唯一性索引，此时我们重新 hash 再插入即可，看起来在违反唯一性索引的情况下是多执行了步骤，但我们要知道 MurmurHash 发生冲突的概率是非常低的，基本上不太可能发生，所以这种方案是可以接受的。

3. 如果同一个 URL，频繁请求，这种会冲突多次，对此我们引入了 LRU Cache，进行判断，如果在 cache 里面，直接返回即可，不在生成之后，再加入到 cache 里面

也就是整一个流程我们只和数据库有一次交互，同时我们引入了 LRU 的缓存，极大了提高了性能。

2. 发号器

维护一个自增 id，比如 1，2，3 这样的整数递增 ID，当收到一个长链转短链的请求时，ID 生成器为其分配一个 ID，再将其转化为 62 进制，拼接到短链域名后面就得到了最终的短网址。但此方法需要全局维护一个自增 id，同时同一个长的 url 会生成不同的短的 url，并且短的 url 会有规律，比较容易猜测到。

常见的有以下几种：uuid，redis 计数，Snowflake 雪花算法，Mysql 自增主键。总和比较感觉雪花算法以及 redis 计数比较靠谱，可以尝试去使用。

Hash 函数

本次选择的 hash 映射方式，来生成短链。底层数据存储选择是 mysql，通过 mysql 的分库分表，读写分离，也可以有非常高效的效率。如果采用 redis，缓存会丢失数据，如果采用 hbase，效率不可控，故最后选择 mysql 作为底层存储数据。

先说下 hash 函数测试的结论，比较有说服力, 可以直接看 HashTest 类

100W 数据，murmur32 算法(产生一个 32 位的 hash 值)，100W 大概会有 121 个冲突

• i = 100000(10W), conflictSize = 1

• i = 200000(20W), conflictSize = 6

• i = 300000(30W), conflictSize = 12

• i = 400000(40W), conflictSize = 19

• i = 500000(50W), conflictSize = 32

• i = 600000(60W), conflictSize = 46

• i = 700000(70W), conflictSize = 54

• i = 800000(80W), conflictSize = 76

• i = 900000(90W), conflictSize = 94

• i = 1000000(100W), conflictSize = 121

修改为 murmur64 算法，100W 0 冲突，500W 0 冲突，建议使用 murmur64 算法

算法实现

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();}

可以看到生成短链只需要访问一次数据库，获取短链也只需要访问一次数据库，是非常的快的。

优化点(难点、亮点)

1. 生成短链只需要访问一次数据库。而不是传统的先查询，在判断插入，而是直接插入，用唯一索引来判断是否 hash 冲突

2. 利用 LRUCache，将最近生成的几千个 kv 放进 map 中，一段时间内，同一个长 url 会生成相同的短 url

3. hash 冲突后，给 hash 冲突值 加一个随机 url，降低冲突概率

4. 选择比较优秀的 murmur64 hash 算法

5. get 获取常链的时候，利用 LRU 识别热点数据，直接从 map 中读取，防止打挂数据库

最后

本文对短链设计方案作了详细地剖析，旨在给大家提供几种不同的短链设计思路，文中涉及到挺多的技术细节。比如 murmur64 hash 算法，base62，LRU，以及为什么选择 mysql，而不是 redis 等等。文中没有展开讲，建议大家回头可以去再详细了解一下，同时也希望大家有空，可以自己动手实现一套短链服务，一定会有不小的收获。

文章转载自：程序员博博

原文链接：https://www.cnblogs.com/wenbochang/p/18257385

体验地址：http://www.jnpfsoft.com/?from=infoq