MurmurHash 算法生成短链接_短链接生成算法

生成短链接

参考

短链接设计和思考_新猿一马的博客-CSDN博客_短连接设计

https://mp.weixin.qq.com/s/dN7XZbyz5vyeJO2sd6tudA

网址大家都知道，很长的一串字符串，很多时候我们还会在后面添加非常多的参数，用来便于做数据统计。下面就是微信公众号一篇文章的地址，可以看到其特别长，估计将近有几百个字符。

https://blog.csdn.net/weixin_46685542/article/details/126924666
1

我们可以用CSDN的短网址功能，把上面的网址缩短成很少个字符的长度，如下所示。

http://t.csdn.cn/G7T9v
1

用短链代替长链，有下面几个常见的好处：

1. 更加简洁。 比起一长串无意义的问题，只有差不多 10 个字符的字符串显然更加简洁。
2. 便于使用。 第一，有些平台对内容长度有限制（微博只能发 140 个字），此时短网址就可以输入更多内容。第二，我们将链接转为二维码时，短链接生成的二维码更容易识别。第三，有些平台无法识别特殊的长链参数，转为短链就没这个问题。
3. 节省成本。 当我们需要发短信的时候，短信是按照长度计费的，短网址可以节省成本。

大致流程

[外
,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cFo48NCz-1664002536767)(p\1663988171009.png)]

1. 客户端首先使用短链接A，访问短网址服务器；
2. 短网址服务器将根据请求的短链接A，返回302跳转，链接跳转到指定的Location:B 长链接；
3. 然后客户端就变成访问B长链接了；

这过程中用户只知道短链接A就访问到长链接B的请求；

关键在于短链接网址和HTTP的重定向

首先重定向：

对http请求，301和302都是重定向，那有什么区别，应该选择哪个？

• 301 代表永久重定向。它表示第一次拿到长链接之后，下次浏览器如果再去请求短链的话，不会再向短链服务器请求了，而是直接从浏览器的缓存中获取。
• 302 代表临时重定向。它表示每次请求短链都会去请求短链服务器，不会从浏览器缓存中获取。

看得出来，301更省事，有缓存不会多次请求短网址服务器，缓解压力；

但是如果需要统计短链接的访问次数等信息，来分析活动的效果，或者根据请求次数来限制访问频率等；

就需要使用302了；这样获取每次请求做操作的业务；

于是整个流程再梳理一遍：

1. 用户访问短链生成页面，输入长链字符串，短链服务返回生成的短链。
2. 用户访问短链，短链服务返回 302 响应，用户浏览器跳转到长链地址。

实现思路

是不是很像一个什么token类似的令牌，用户第一次来请求，生成个token，保存在服务器，可以使redis也可以是session里面，然后返回token；

后面再携带token来请求，就是根据token去查找，看有没有保存这个token的信息；

查到了，就给正确页面响应，没查到就说你没登录或权限不够不能访问；

所以短链接服务也可以这样设计，将长链接作为value，短链接作为key，保存在服务器；

用户再根据这个短链接key来请求，获取返回长链接，返回302给他跳转长链接，就直接访问长链接去了；

那现在问题是如何生成一有唯一性的短链接key？

1. 使用哈希算法给长链接value来生成唯一值
2. 分布式的唯一ID作为短链接key

哈希算法生成唯一值

要生成一个唯一的短链接，可以对原来的长链接进行一次哈希，然后得到一个哈希值

http://localhost:8001/oaiherihoeifnosdionfeionfioencinionafioeanfioneiafnioeniovboe/oinioewnioniovnwionafiohfeionoienwff/hoafeboinionioeniznvionlioenionfioewnifniowneiofnioewnionwenviownvoivnoienw
  ↓
2799345918730369457
1
2
3

第一个问题：使用哪种哈希算法呢？

哈希算法也就是一种摘要算法，作用是将任意一组数据输入计算，得到一个固定长度的输出摘要；

常见的哈希算法有MD5、SHA-1、SHA-256、SHA-512 算法等

因为 MD5 和 SHA 哈希算法，它们都是加密的哈希算法，也就是说我们无法从哈希值反向推导出原文，从而保证了原文的保密性；

但是对于生成短链接，安全性要求不高，重要的运算速度和哈希冲突；

MurmurHash 算法是一个非加密哈希算法，所以它的速度回更快；

第二个问题：哈希冲突

哈希冲突是哈希算法不可避免的问题；

解决方法有两种：

1. 链表法
2. 重哈希法

我们知道的HashMap使用了链表法，而我们使用的 MurmurHash 使用的是重哈希法；

重哈希法

指的是当发生哈希冲突的时候，我们在原有长链后面加上固定的特殊字符，后续拿出长链时再将其去掉，如下所示

原有长链：https://blog.csdn.net/weixin_46685542/article/details/126924666
              ↓↓  
           发生哈希冲突
              ↓↓  
补上特殊字符：https://blog.csdn.net/weixin_46685542/article/details/126924666[SPECIAL-CHARACTER]
              ↓↓  
           再次进行哈希
1
2
3
4
5
6
7

通过这种办法，我们就可以解决哈希冲突的问题了。如果再次发生，那么就再进行哈希，一直到不冲突位置。一般来说，哈希冲突的可能性微乎其微。

于是，使用MurmurHash 后得到一个哈希值：2799345918730369457 (一串 long 类型的数字)

原来的链接       http://localhost:8001/oaiherihoeifnosdionfeionfioencinionafioeanfioneiafnioeniovboe/oinioewnioniovnwionafiohfeionoienwff/hoafeboinionioeniznvionlioenionfioewnifniowneiofnioewnionwenviownvoivnoienw

哈希后的哈希值：2799345918730369457
1
2
3

最后可以请求：

http://localhost:8001/doShortUrl/2799345918730369457

这么看来确实少了很多耶，可以收工啦！！！

但是相比较其他CSDN的短链接，可以发现还是很长；

想办法让网址变得更短

在网址 URL 中，常用的合法字符有 0～9、a～z、A～Z 这样 62 个字符。如果我们用哈希值与 62 取余，那么余数肯定是在 0-61 之间。

62进制只含数字+小写字母+大写字母；64进制会含有"/,+"这样的符号，不符合正常URL的字符。而且如果是6位62进制的话，能有560亿种组合，满足业务需求。

这 62 个数字刚好与 62 个合法网址字符一一对应。接着，我们再用除 62 得到的值，再次与 62 取余，一直到位 0 为止。通过这样的处理，我们就可以得到一个字符为 62 个字符、长度很短的字符串了。

假设我们得到的哈希值为 181338494，那么上面的处理流程为：

1. 将 181338494 除以 62，得到结果为 2924814，余数为 26，此时余数 26 对应字符为 q。
2. 将 2924814 除以 62，得到结果为 47174，余数为 26，此时余数 26 对应字符为 q。
3. 将 47174 除以 62，得到结果为 760，余数为 54，此时余数 54 对应字符为 S。
4. 省略剩余步骤

最后 把 181338494 这个十进制数，转成了由合法网址字符组成的「62 进制数」—— cgSqq。

解决方法

将得到的哈希值(一串很长的 10进制的 long类型的数据)进行62进制的换算；最后得到合法网址字符，

这样就缩短了网址的长度；

查看 Java 8 中文版 - 在线API中文手册 - 码工具 (matools.com)

可以使用 java.math.BigInteger 的方法 divideAndRemainder

例如

 @Test
    public void  test1(){
        BigInteger a=new BigInteger("100");

        BigInteger b=new BigInteger("3");

        BigInteger[] c=a.divideAndRemainder(b);

        System.out.print(a.toString()+"除以"+b.toString()+"的商是");

        System.out.println(c[0].toString()+",余数是"+c[1].toString());
    }
//结果
//100除以3的商是33,余数是1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分布式唯一ID方式

需要一个ID自增的生成器

数据库自增ID、
UUID生成、
redis生成、
snowflake雪花算法；

参考：分布式 id_新猿一马的博客-CSDN博客

1、数据库自增长ID

MySQL中的自增属性 auto_increment 来生成全局唯一 ID，来保证趋势递增。

【优缺点】
优点： 非常简单，有序递增，方便分页和排序；
缺点： 分库分表后，同一数据表的自增ID容易重复，无法直接使用(可以设置步长，但局限性很明显)；性能吞吐量整个较低；ID号码不够随机，能够泄露发号数量的信息，不太安全。

【使用场景】
单数据库实例的表ID(包含主从同步场景)，部分按天计数的流水号等；分库分表场景、全系统唯一性ID场景不适用

2、UUID生成

【生成原理】
UUID生成id需要用到以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字。其生成的id由当前日期和时间(UUID的第一个部分与时间有关，如果你在生成一个UUID之后，过几秒又生成一个UUID，则第一个部分不同，其余相同)，时钟序列，全局唯一的IEEE机器识别号。

标准型式包含32个16进制数字,以连字号分为五段，形式为8-4-4-4-12的36个字符

示例：550e8400-e29b-41d4-a716-446655440000

【优缺点】
优点： 不依赖任何数据源，自行计算，没有网络ID，速度超快，并且全球唯一；
缺点： 没有顺序性，并且比较长(128bit)，作为数据库主键、索引会导致索引效率下降，空间占用较多。

【使用场景】
只要对存储空间没有苛刻要求的都能够适用，比如各种链路追踪、日志存储等。

3、redis生成id

【生成原理】
依赖redis的数据源，通过redis的incr/incrby自增院子操作命令，能保证生成id肯定是唯一有序的，本质生成方式与数据库一致。

【优缺点】
优点： 整体吞吐量比数据库要高；
缺点：Redis是基于内存的数据库，其实例或集群宕机后，找回最新的ID值有点困难。由于使用自增，对外容易暴露业务数据总量

【应用场景】
比较适合计数场景，如用户访问量，订单流水号(日期+流水号)等。

4、雪花算法snowflake

【实现原理】
属于半依赖数据源方式，原理是使用Long类型(64位)，按照一定的规则进行填充：时间(毫秒级)+集群ID+机器ID+序列号，每部分占用的位数可以根据实际需要分配，其中集群ID和机器ID这两部分，在实际应用场景中要依赖外部参数配置或数据库记录。

41-bit的时间可以表示（1L<<41）/(1000L360024*365)=69年的时间

10-bit机器可以分别表示1024台机器,如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。

12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s，这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

【优缺点】
优点： 高性能、低延迟、去中心化、按时间有序；
缺点： 要求机器时钟同步(到秒级即可)，即时间回拨 会导致id重复。

【使用场景】
分布式应用环境的数据主键，大多数使用雪花算法来实现分布式id。

【如何解决时间回拨问题】
时间回拨是指，当机器出现问题,时间可能回到之前,此时雪花算法生成的id可能与之前的id值相同，从而导致id重复
【解决方式】
1、系统抛出异常，运维来手动调整时间；
2、延迟等待，对于偶然性的时间回拨，也许是机器出现了一次小故障，频繁出现的概率并不大，所以对于这种情况没必要中断业务，可以采用阻塞线程5ms，再获取时间，对比看时间是否比上一次请求的时间大，如果大了,说明恢复正常了,则不用管；如果还小,说明真出问题了,则抛出异常,呼唤程序员处理
3、备用机方式来解决，当前机器出现问题，迅速换一台机器，通过高可用解决

5、snowflake 算法优化

百度的 uid-generator 和美团的 Leaf 基本上是对 snowflake 的优化改进

• 百度的 uid-generator

​ https://github.com/baidu/uid-generator

• 美团 Leaf

​ https://github.com/zhuzhong/idleaf

使用分布式唯一ID方法也可以生成唯一的短链接key，生成的唯一id也比较长，

最后再同样转为62进制来缩短字符长度；

问题：

如果有相同的长链接请求两次，那会生成两个不同的短链接；

从用户的角度来看，是不影响用户使用的，因为不管是哪个短链接，最终都是一个长链接。

从存储的角度来看，如果请求N次，这块的数据存储压力是很大的，而且很多都是脏数据。需要添加唯一索引。

实战案例

使用MurmurHash 算法；使用谷歌的依赖包

          <!--MurmurHash    算法-->
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>31.1-jre</version>
        </dependency>
1
2
3
4
5
6

定义业务接口和方法

package com.ung.myUrl.service;

public interface ShortUrlService {

    String shortenUrl(String url,int expireSeconds);
}
1
2
3
4
5
6

实现类

package com.ung.myUrl.service.impl;

import com.google.common.hash.Hashing;
import com.ung.myUrl.service.ShortUrlService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;

import java.math.BigInteger;
import java.util.concurrent.TimeUnit;

/**
 * @author: wenyi
 * @create: 2022/9/23
 * @Description: 短链接业务实现类
 */
@Service
public class ShortUrlServiceImpl implements ShortUrlService {

    @Autowired
    private RedisTemplate redisTemplate;

    private static final String ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    private static final int BASE = ALPHABETS.length();

    @Override
    public String shortenUrl(String url, int expireSeconds) {
        System.out.println("********************originUrl:" + url);
        long murmur32 = Hashing.murmur3_128().hashUnencodedChars(url).padToLong();
        System.out.println("********************哈希值:" + murmur32);
        String encoded, value;
        do {
            encoded = encode(murmur32++);
            value = (String) redisTemplate.opsForValue().get(encoded);
        } while (value != null && !value.equals(url));
        redisTemplate.opsForValue().set(encoded, url, expireSeconds, TimeUnit.SECONDS);
        System.out.println("********************shortUrl:" + encoded);
        return encoded;
    }


    private String encode(long oct) {
        BigInteger octLong = BigInteger.valueOf(oct);
        StringBuilder builder = new StringBuilder(6);
        while (!octLong.equals(BigInteger.ZERO)) {
            /**
             * divideAndRemainder 二进制补码，参数是除数
             * A.divideAndRemainder(B)  ==== A%B
             * 结果是个 商和余数的数组   result[0] = 商，result[1] = 余数
             * 这里的while循环相当于一直取模求余数的算法，直到最后不能再除
             * 100/3 = 33 .....1
             * 33/3 = 11 .....0
             * 11/3 = 3 .....2
             * 3/3 = 1 ....0
             * 1/3 = 0 ..1
             */
            BigInteger[] divideAndReminder = octLong.divideAndRemainder(BigInteger.valueOf(BASE));
            //余数转为字符
            builder.append(ALPHABETS.charAt(divideAndReminder[1].intValue()));
            octLong = divideAndReminder[0];
        }
        //最后结果反向输出
        return builder.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

controller使用

package com.ung.myUrl.controller;

import com.ung.myUrl.service.ShortUrlService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.http.HttpStatus;
import org.springframework.util.StringUtils;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;

import javax.servlet.http.HttpServletResponse;
import java.io.Serializable;

/**
 * @author: wenyi
 * @create: 2022/9/24
 * @Description:
 */
@RestController
public class ShortUrlController {

    private ShortUrlService shortUrlService;

    @Autowired
    private RedisTemplate redisTemplate;

    @Autowired
    public ShortUrlController(ShortUrlService shortUrlService) {
        this.shortUrlService = shortUrlService;
    }

    @GetMapping("/doShortUrl/{shortPath}")
    public void doShortUrl(@PathVariable("shortPath") String shortPath, HttpServletResponse response) {

        //根据短链接从存缓存获取长链接
        String originalUrl = (String) redisTemplate.opsForValue().get(shortPath);
        if (StringUtils.isEmpty(originalUrl)) {
            response.setStatus(HttpStatus.NOT_FOUND.value());
            return;
        }
        System.out.println("查出来的url：" + originalUrl);
        //有值
        response.setHeader("Location", originalUrl);
        response.setStatus(302);//Moved Temporarily 302 跳转

    }

    @GetMapping("/toShortUrl")
    public String toShortUrl(String shortPath) {
        String shortenUrl = shortUrlService.shortenUrl(shortPath, 6000);
        return shortenUrl;
    }

    @GetMapping("/oaiherihoeifnosdionfeionfioencinionafioeanfioneiafnioeniovboe/oinioewnioniovnwionafiohfeionoienwff/hoafeboinionioeniznvionlioenionfioewnifniowneiofnioewnionwenviownvoivnoienw")
    public String doLongUrl() {
        return "success!!!";
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

现在有一个长链接，可以正常访问

http://localhost:8001/oaiherihoeifnosdionfeionfioencinionafioeanfioneiafnioeniovboe/oinioewnioniovnwionafiohfeionoienwff/hoafeboinionioeniznvionlioenionfioewnifniowneiofnioewnionwenviownvoivnoienw
1

现在把这个长链接作为参数，发送get请求，返回一个短链接的key

http://localhost:8001/toShortUrl?shortPath=http://localhost:8001/oaiherihoeifnosdionfeionfioencinionafioeanfioneiafnioeniovboe/oinioewnioniovnwionafiohfeionoienwff/hoafeboinionioeniznvionlioenionfioewnifniowneiofnioewnionwenviownvoivnoienw

在根据短链接统一处理的接口链接：携带短链接的key

http://localhost:8001/doShortUrl/DUxCGsuaKOV

也可以正常访问成功

性能优化

拿到长链地址后，可以用哈希算法或唯一 ID 分号器获取唯一字符串，从而建立长链与短链的映射关系。为了缩短短链长度，我们还可以将其用 62 进制数表示，整个短链生成过程如下图所示。

短链接生成好后，可以存到数据库保存，然后根据请求的短链接获取保存的长链接，再HTTP重定向返回；

索引优化

如果使用关系型数据库的话，对于短链字段需要创建唯一索引，从而加快查询速度。

增加缓存

并发量小的时候，我们都是直接访问数据库。但当并发量再次升高时，需要加上缓存抗住热点数据的访问。

读写分离

短链服务肯定是读远大于写的，因此对于短链服务，可以做好读写分离。

分库分表

如果是商用的短链服务，那么数据量上亿是很正常的，更不用说常年累月积累下的量了。这时候可以一开始就做好分库分表操作，避免后期再大动干戈。

对于分库分表来说，最关键的便是根据哪个字段去作为分库分表的依据了。对于短链服务来说，当然是用转化后的 62 进制数字做分表依据了，因为它是唯一的嘛。

至于怎么分库分表，就涉及到分库分表方面的知识，以及对于系统容量的预估了

防止恶意攻击

开放到公网的服务，什么事情都可能发生，其中一个可能的点就是被恶意攻击，不断循环调用。

一开始我们可以做一下简单地限流操作，例如：

1. 没有授权的用户，根据 IP 进行判断，1 分钟最多只能请求 10 次。
2. 没有授权的用户，所有用户 1 分钟最多只能请求 4000 次，防止更换 IP 进行攻击。

简单地说，就是要不断提高攻击的成本，使得最坏情况下系统依然可以正常提供服务。

最后代码 https://gitee.com/wenyi49/my-test.git