短链是什么原理?怎么实现呢?

时间:2022-12-15 20:55:28

一、为什么需要短链

内容营销中给用户推送营销消息最常见的方式就是发短信,比如三大运营商移动、联通、电信平时会发送一些诸如套餐办理、消费查询、话费充值这些短信,还有像银行、云服务厂商等等推送的各种包含查询服务的短信等等。

我们都知道单条短信发送的内容长度是有限制的,而如果要推送包含URL的消息,如果URL太长,不仅影响用户观感,而且会占用太多无用字数。

这时,我们需要将长的URL转换为短URL,也就是接下来我们要说的短链(短域名 + 短请求路径)。



二、短链跳转访问原理

原理还是很简单的,其实就是在后台保存有短链和长链的映射关系,然后进行重定向,让浏览器跳转到对应的长链接。
短链是什么原理?怎么实现呢?
举个栗子,原始长链接为:https://www.baidu.com,通过某平台我生成了一个短链接:https://suo.nz/378IQe
短链是什么原理?怎么实现呢?
我们可以看到当访问https://suo.nz/378IQe时,后端返回了302,同时多了一个Location响应头,值就是原始链接https://www.baidu.com.

这里有个小问题,关于重定向使用301还是302

编码 含义 备注
301 Moved Permanently 永久重定向,表示原 URL 不再被使用,而应该优先选用新的 URL,搜索引擎会直接更新与该资源相关的URL,一般用于网站重构。
302 Found 临时重定向,搜索引擎不会记录该资源对应的临时链接,一般用于由于不可预见的原因导致该页面暂不可用。
  • 301其实是比较符合HTTP协议语义的,但浏览器会缓存目标网址,下次访问时会直接跳过短链,跳转到目标网址,无法做一些统计,比如短链访问次数等。
    短链是什么原理?怎么实现呢?

  • 302:浏览器访问时,会先后访问短链代理服务和目标服务,对服务器的压力也就相应大些,但可以做一些统计。

备注:很多短链生成平台其实都是走的302重定向。



三、短链生成实现方案

1、自增序列算法

常用的自增序列算法有雪花算法、Redis自增、MySQL主键自增等,生成唯一ID后,再转换为62进制字符串,转换后的62进制字符串可用作短链。

问题:为什么需要转换为62进制字符串呢?
因为自增ID会越来越长,经过62进制转换后可以变得更短。

现在说下关于自增序列生成短链的优缺点:

  • 优点:ID唯一,生成的短链不会重复和冲突。
  • 缺点:随着ID越来越大,短链长度也会随之变化,长度不固定。

再说下各种自增序列算法的优缺点:

算法 优点 缺点
雪花算法 高性能,不依赖任何中间件 存在系统时钟回拨问题,原始雪花算法长度为64位,生成的ID比较长。
Redis自增 高性能,高并发 既然是中间件,有维护成本,同时要考虑持久化、灾难恢复等。
MySQL主键自增 使用简单,易于扩展 高并发下有性能瓶颈 。
  • 301其实是比较符合HTTP协议语义的,但浏览器会缓存目标网址,下次访问时会直接跳过短链,跳转到目标网址,无法做一些统计,比如短链访问次数等。
  • 302:浏览器访问时,会先后访问短链代理服务和目标服务,对服务器的压力也就相应大些,但可以做一些统计。

2、Hash算法

简单来说就是对目标长链接进行hash,然后再对hash值进行62进制编码转换为短链接。Hash算法我们熟知的有MD5SHA等算法。

这两种算法为加密型hash算法,性能相对比较低,这里我们一般采用Google Guava中实现的Murmurhash算法,该算法为非加密型hash算法,相比MD5优点如下:

  1. 速度比MD5快。
  2. 哈希冲突的概率低,该算法支持32位和128位哈希值,MD5也是128位哈希值,基本不用担心哈希冲突。
  3. 离散度高,散列值比较均匀。

关于Murmurhash示例如下:

String url = "https://www.baidu.com/";

// 输出:e9ac4fbdc398e8c104d1b8415f42cbf8
System.out.println(Hashing.murmur3_128().hashString(url, StandardCharsets.UTF_8));
// 输出:06105412
System.out.println(Hashing.murmur3_32_fixed().hashString(url, StandardCharsets.UTF_8));
// 输出:bf447182
System.out.println(Hashing.murmur3_32_fixed().hashLong(Long.MAX_VALUE));

// 转成Long型

// 输出:307499014
System.out.println(Hashing.murmur3_32_fixed().hashString(url, StandardCharsets.UTF_8).padToLong());
// 输出:2188461247
System.out.println(Hashing.murmur3_32_fixed().hashLong(Long.MAX_VALUE).padToLong());

这里说下通过Hash算法生成短链的优缺点:

  • 优点:去中心化,哈希后生成的短链长度基本固定。
  • 缺点:有概率会发生哈希冲突,解决哈希冲突的方法主要有拉链法重新哈希。由于短链是通过哈希值转62进制字符串生成,如果发生哈希冲突,得重新哈希生成。如果存库的话,每次生成短链至少会有一次查询和一次保存操作,有性能损耗。


四、代码示例

接下来的示例我们主要用Hash算法 + Base62 编码生成短链,流程图如下:
短链是什么原理?怎么实现呢?

1、表结构及索引

# 短链信息表
create table `t_short_link`
(
    `id`             bigint primary key auto_increment comment '主键ID',
    `short_link`     varchar(32)  not null default '' comment '短链接',
    `long_link_hash` bigint       not null default 0 comment 'hash值',
    `long_link`      varchar(128) not null default '' comment '长链接',
    `status`         tinyint      not null default 1 comment '状态:1-可用,0-不可用',
    `expiry_time`    datetime     null comment '过期时间',
    `create_time`    datetime     not null default current_timestamp comment '创建时间'
) comment '短链信息表';
create index idx_sl_hash_long_link on t_short_link (long_link_hash, long_link);
create index idx_sl_short_link on t_short_link (short_link);

2、外部依赖

<!--Google Guava-->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

3、Base62Utils

public abstract class Base62Utils {

	private static final int SCALE = 62;

	private static final char[] BASE_62_ARRAY = {
		'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
		'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
		'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
		'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
		'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
	};

	private static final String BASE_62_CHARACTERS = String.valueOf(BASE_62_ARRAY);

	/**
	 * 将long类型编码成Base62字符串
	 * @param num
	 * @return
	 */
	public static String encodeToBase62String(long num) {
		StringBuilder sb = new StringBuilder();
		while (num > 0) {
			sb.insert(0, BASE_62_ARRAY[(int) (num % SCALE)]);
			num /= SCALE;
		}
		return sb.toString();
	}

	/**
	 * 将Base62字符串解码成long类型
	 * @param base62Str
	 * @return
	 */
	public static long decodeToLong(String base62Str) {
		long num = 0, coefficient = 1;
		String reversedBase62Str = new StringBuilder(base62Str).reverse().toString();
		for (char base62Character : reversedBase62Str.toCharArray()) {
			num += BASE_62_CHARACTERS.indexOf(base62Character) * coefficient;
			coefficient *= SCALE;
		}
		return num;
	}
}

备注:BASE_62_ARRAY中的字符顺序可以随便打乱,不一定要按顺序排列,打乱安全性更高。

问题:能不能用Base64编码生成短链呢?

JDK8中Base64.getEncoder()获取到的编码器对应的编码字符会包含'+''/'等URL不允许包含的特殊字符,但Base64.getUrlEncoder()获取到的编码器对应的编码字符会把'+''/'分别替换成'-''_',所以其实也是可以的。如下:
短链是什么原理?怎么实现呢?

4、DAO层

@Repository
public class ShortLinkManagerImpl implements ShortLinkManager {

	@Autowired
	private ShortLinkMapper shortLinkMapper;

	@Override
	public void saveShortLink(String shortLink, long longLinkHash, String longLink) {
		ShortLinkDO shortLinkDO = ShortLinkDO.builder()
			.shortLink(shortLink)
			.longLinkHash(longLinkHash)
			.longLink(longLink)
			.status(true)
			.build();
		shortLinkMapper.insert(shortLinkDO);
	}

	@Override
	public String getShortLink(long longLinkHash, String longLink) {
		Wrapper<ShortLinkDO> wrapper = Wrappers.lambdaQuery(ShortLinkDO.class)
			.select(ShortLinkDO::getShortLink)
			.eq(ShortLinkDO::getLongLinkHash, longLinkHash)
			.eq(ShortLinkDO::getLongLink, longLink)
			.last(CommonConst.LIMIT_SQL);
		ShortLinkDO shortLinkDO = shortLinkMapper.selectOne(wrapper);
		return Optional.ofNullable(shortLinkDO).map(ShortLinkDO::getShortLink).orElse(null);
	}

	@Override
	public boolean isShortLinkRepeated(String shortLink) {
		Wrapper<ShortLinkDO> wrapper = Wrappers.lambdaQuery(ShortLinkDO.class).eq(ShortLinkDO::getShortLink, shortLink);
		return shortLinkMapper.selectCount(wrapper) > 0;
	}
}

5、业务层

@Service
public class ShortLinkServiceImpl implements ShortLinkService {

	@Autowired
	private ShortLinkManager shortLinkManager;

	@Override
	public String generateShortLink(String longLink) {
		long longLinkHash = Hashing.murmur3_32_fixed().hashString(longLink, StandardCharsets.UTF_8).padToLong();
		// 通过长链接Hash值和长链接检索
		String shortLink = shortLinkManager.getShortLink(longLinkHash, longLink);
		if (StringUtils.isNotBlank(shortLink)) {
			return shortLink;
		}
		// 如果Hash冲突则加随机盐重新Hash
		return regenerateOnHashConflict(longLink, longLinkHash);
	}

	private String regenerateOnHashConflict(String longLink, long longLinkHash) {
		// 自增序列作随机盐
		long uniqueIdHash = Hashing.murmur3_32_fixed().hashLong(SnowFlakeUtils.nextId()).padToLong();
		// 相减主要是为了让哈希值更小
		String shortLink = Base62Utils.encodeToBase62String(Math.abs(longLinkHash - uniqueIdHash));
		if (!shortLinkManager.isShortLinkRepeated(shortLink)) {
			shortLinkManager.saveShortLink(shortLink, longLinkHash, longLink);
			return shortLink;
		}
		return regenerateOnHashConflict(longLink, longLinkHash);
	}

}


五、测试用例

@SpringBootTest(classes = Application.class)
public class ApplicationTest {

	@Autowired
	private ShortLinkService shortLinkService;

	@Test
	public void generateShortLinkTest() {
		String shortLink = shortLinkService.generateShortLink("https://www.baidu.com/");
		System.err.println("生成的短链为:" + shortLink);
	}
}

控制台输出:

生成的短链为:D4PTSU

备注:生成的短链长度基本为6位字符串,还有记得短链代理服务选一个短域名

短链是什么原理?怎么实现呢?