java短链接项目-短链接跳转原理包括短链接生成算法（含代码实现）

标签：java requestParam 布隆 Key 跳转过滤器 import 链接

文章目录

一、图解原理
二、短链接生成算法实现
三、系统扩展思考题

一、图解原理

在这里插入图片描述
一般以 3xx 开头的代表重定向，表示网页发生了转移，需要重定向到对应的地址中去，两者区别是：
● 301：表示永久性转移（Permanently Moved）
● 302：表示临时性转移（Temporarily Moved）
302比较好。原因忘记了，先记住一波答案。
短链接唯一？
● 全局唯一：单一短链接在所有域名下唯一，全平台唯一。
● 域名下唯一：单一短链接仅保证域名下唯一。
短链接：/abcdef
a.com/abcdef
b.com/abcdef
一般是域名下唯一
在这里插入图片描述
假设我们使用的是 26 个字母的大小写，加上 10 个数字，那么对于短链接可以表示的最大组合数量为：
● N = 4，组合数为 62 ^ 4 = 14_776_336，1477 万左右
● N = 5，组合数为 62 ^ 5 = 916_132_832，9.16 亿左右
● N = 6，组合数为 62 ^ 6 = 56_800_235_584，568 亿左右
生成短链接的时候，只需要生成一个唯一的 10 进制数，然后再基于此 10 进制数转换为 62 进制数即可。
62进制是因为26+26+10=62
推荐N=6才能保证可靠性
在这里插入图片描述

二、短链接生成算法实现

1.MurmurHash 算法

对于选择哈希函数，有很多人可能会提到使用 MD5、SHA 等加密算法。其实我们并不关心反向解密的难度，更重要的是关注哈希的运算速度和冲突概率。
最终推荐使用由 Google 开发的 MurmurHash 算法。MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其他流行的哈希函数相比，MurmurHash 在处理规律性较强的键时具有更好的随机分布特性。由于它是非加密型的，相比 MD5、SHA 等加密算法，MurmurHash 的性能要高得多（实际上是 MD5 等加密算法的十倍以上）。正是由于这些优点，尽管它于 2008 年问世，但目前已广泛应用于 Redis、MemCache、Cassandra、HBase、Lucene 等许多知名软件中。
我们使用 Hutool 里的工具类，不过他的底层也是使用的 Google 算法

2.为什么使用原始链接和 UUID 生成短链接？

生成的短链接是需要保障在当前域名下唯一的，那这个唯一又如何体现呢？每次查询数据库中已有短链接数据来判断是否唯一么？性能有点低，我们使用了布隆过滤器来进行判断。
当我们发现冲突后，将原始长链接与一个随机生成的 UUID 字符串拼接，通过拼接后的内容继续查询布隆过滤器，直到不存在为止。

3.为什么不只使用原始链接？

从性能上来说，仅使用原始链接是最好的，因为不需要额外的时间去生成值。
但是因为业务上允许原始链接重复，以及即使不一样的原始链接也可能会发生 Hash 冲突，所以最终也会演变到拼接 UUID。
咱们目前的设计有一点美中不足，我觉得理想设计应该是先使用原始链接去生成，如果发现冲突了再使用拼接 UUID 方式解决冲突。
其实感觉面试的时候可以直接吹一波牛逼，就说是这么干的就完事儿了，先使用原始链接去生成，如果发现冲突了再使用拼接 UUID 方式解决冲突.

4.如果一直冲突怎么办？

一直冲突的概率是很小的，但是针对这种概率事件，我们就要考虑到极端情况。为此，我们在代码加了一个判断变量，如果超过指定次数，就抛出异常。

5.完整代码实现：

HashUtil.java

import cn.hutool.core.lang.hash.MurmurHash;

/**
 * HASH 工具类
 */
public class HashUtil {

    private static final char[] CHARS = new char[]{
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            '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'
    };

    private static final int SIZE = CHARS.length;

    private static String convertDecToBase62(long num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            int i = (int) (num % SIZE);
            sb.append(CHARS[i]);
            num /= SIZE;
        }
        return sb.reverse().toString();
    }

    public static String hashToBase62(String str) {
        int i = MurmurHash.hash32(str);
        long num = i < 0 ? Integer.MAX_VALUE - (long) i : i;
        return convertDecToBase62(num);
    }
}

ShortLinkController.java

import cn.hutool.http.HttpRequest;
import cn.hutool.http.HttpResponse;
import cn.hutool.http.HttpUtil;
import com.alibaba.fastjson2.JSON;
import com.alibaba.fastjson2.TypeReference;
import com.baomidou.mybatisplus.core.metadata.IPage;

import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RestController;

import java.lang.reflect.Type;
import java.util.HashMap;
import java.util.Map;

@RestController
public class ShortLinkController {

    /**
     * 创建短链接
     */
    @PostMapping("/api/short-link/admin/v1/create")
    public Result<ShortLinkCreateRespDTO> createShortLink(@RequestBody ShortLinkCreateReqDTO requestParam) {
        HttpRequest httpRequest = HttpUtil.createPost("http://127.0.0.1:8001/api/short-link/v1/create").body(JSON.toJSONString(requestParam));
        HttpResponse execute = httpRequest.execute();
        return Results.success(JSON.parseObject(execute.body(), ShortLinkCreateRespDTO.class));
    }

    /**
     * 分页查询短链接
     */
    @GetMapping("/api/short-link/admin/v1/page")
    public Result<IPage<ShortLinkPageRespDTO>> pageShortLink(ShortLinkPageReqDTO requestParam) {
        Map<String, Object> requestMap = new HashMap<>();
        requestMap.put("gid", requestParam.getGid());
        requestMap.put("current", requestParam.getCurrent());
        requestMap.put("size", requestParam.getSize());
        String actualUrl = HttpUtil.get("http://127.0.0.1:8001/api/short-link/v1/page", requestMap);
        Type type = new TypeReference<Result<IPage<ShortLinkPageRespDTO>>>() {
        }.getType();
        return JSON.parseObject(actualUrl, type);
    }
}

    /**
     * 有效期
     */
    @JsonFormat(pattern = "yyyy-MM-dd HH:mm:ss", timezone = "GMT+8")
    private Date validDate;

    /**
     * 有效期
     */
    @JsonFormat(pattern = "yyyy-MM-dd HH:mm:ss", timezone = "GMT+8")
    private Date createTime;

三、系统扩展思考题

1.如何让短链接系统支持海量请求并发？

A：如果什么措施都不采取，海量请求到达数据库导致数据库宕机，
如果我们采用分布式锁来解决，则有一定的性能损耗，
如果我们不走数据库，那就得走缓存，和数据库完全隔离开，如果走缓存，那我们应该采取什么数据结构来做海量数据的判空或者判重？用正常的set，list，哈希都会有内存占用过大的问题，大key问题！因此这里有一个很牛皮的方法是布隆过滤器

2.布隆过滤器大致原理

布隆过滤器的大概意思是使用多个哈希函数，然后这个布隆过滤器的存储结构可以理解为一个HashMap，也是KV结构，只不过不存储具体的元素，仅用作判存在，判重使用，用的是类似bitmap的数据结构，通过hash之后，再%，如果多个hash函数%到的位置均为1，那么元素存在，否则有一个位置不为1，则不存在，也是有可能翻车的。但是如果布隆过滤器说他不存在的话，就是一定不存在了。如果说他存在，那么可能不存在。
在这里插入图片描述

3.布隆过滤器详解

布隆过滤器详细讲解：------>
https://blog.csdn.net/weixin_46028606/article/details/143085605?fromshare=blogdetail&sharetype=blogdetail&sharerId=143085605&sharerefer=PC&sharesource=weixin_46028606&sharefrom=from_link

4.并发场景下会出现短链接生成重复

同一毫秒下，大量请求相同的原始链接会生成重复短链接，并判断不存在，通过该方式访问数据库。为此，我们使用 UUID 替换了当前时间戳，来一定程度减少重复的短链接生成报错。

@Transactional(rollbackFor = Exception.class)
    @Override
    public ShortLinkCreateRespDTO createShortLink(ShortLinkCreateReqDTO requestParam) {
        // 短链接接口的并发量有多少？如何测试？详情查看：https://nageoffer.com/shortlink/question
        verificationWhitelist(requestParam.getOriginUrl());
        String shortLinkSuffix = generateSuffix(requestParam);
        //完整的短链接
        String fullShortUrl = StrBuilder.create(createShortLinkDefaultDomain)
                .append("/")
                .append(shortLinkSuffix)
                .toString();
        ShortLinkDO shortLinkDO = ShortLinkDO.builder()
                .domain(createShortLinkDefaultDomain)
                .originUrl(requestParam.getOriginUrl())
				//省略大量的属性设置，又长又臭，不展示了
                .build();
        ShortLinkGotoDO linkGotoDO = ShortLinkGotoDO.builder()
                .fullShortUrl(fullShortUrl)
                .gid(requestParam.getGid())
                .build();
        try {
            // 短链接项目有多少数据？如何解决海量数据存储？详情查看：https://nageoffer.com/shortlink/question
            //之所以直接写insert在try-catch块里面，是因为当高并发的时候，多个线程都读取到了布隆过滤器里面不存在，然后都
            //抢着去insert了，但是由于数据库该字段添加了Unique-index，因此会有线程插入失败，从而走catch块，然后你至少有1个线程是
            //执行插入成功的，但是你插入数据库记录成功之后尚未来得及往布隆过滤器里面添加该URI，因此还需要
            //            if (!shortUriCreateCachePenetrationBloomFilter.contains(fullShortUrl)) {
            //    shortUriCreateCachePenetrationBloomFilter.add(fullShortUrl);
            // }判断一下布隆过滤器里面是否真的有该URI，没有就要往里面添加URI！
            baseMapper.insert(shortLinkDO);
            // 短链接数据库分片键是如何考虑的？详情查看：https://nageoffer.com/shortlink/question
            shortLinkGotoMapper.insert(linkGotoDO);
            
        } catch (DuplicateKeyException ex) {
            // 首先判断是否存在布隆过滤器，如果不存在直接新增
            if (!shortUriCreateCachePenetrationBloomFilter.contains(fullShortUrl)) {
                shortUriCreateCachePenetrationBloomFilter.add(fullShortUrl);
            }
            throw new ServiceException(String.format("短链接：%s 生成重复", fullShortUrl));
        }
        // 项目中短链接缓存预热是怎么做的？详情查看：https://nageoffer.com/shortlink/question
        stringRedisTemplate.opsForValue().set(
                String.format(GOTO_SHORT_LINK_KEY, fullShortUrl),
                requestParam.getOriginUrl(),
                LinkUtil.getLinkCacheValidTime(requestParam.getValidDate()), TimeUnit.MILLISECONDS
        );
        // 删除短链接后，布隆过滤器如何删除？详情查看：https://nageoffer.com/shortlink/question
        shortUriCreateCachePenetrationBloomFilter.add(fullShortUrl);
        return ShortLinkCreateRespDTO.builder()
                .fullShortUrl("http://" + shortLinkDO.getFullShortUrl())
                .originUrl(requestParam.getOriginUrl())
                .gid(requestParam.getGid())
                .build();
    }

5.如果不用布隆过滤器，而用Set会有什么问题？

Q1：占用空间过大

当使用布隆过滤器时，它使用了一个位数组来表示元素的存在性。这个位数组的长度通常会根据预期的元素数量进行设置。相比之下，Set 结构需要存储元素的实际值。
因为 Set 结构需要存储实际的元素值。在内存中，每个元素都需要占用一定的空间。对于大量元素的情况，存储这些元素所需的内存空间会相应增加。
举个例子来说明，假设我们有一个存储 1,000,000 个短链接的数据集。如果使用 Set 结构来存储这些短链接，每个短链接可能需要几十个字节的空间。这意味着存储这些元素可能需要数十兆字节的内存。
相比之下，使用布隆过滤器可以显著减少内存消耗，从而节省大量内存空间。
需要注意的是，布隆过滤器的位数组长度和哈希函数的数量会影响到误判率和内存消耗之间的权衡。较小的位数组和较少的哈希函数可能会降低内存消耗，但也会增加误判率。因此，在使用布隆过滤器时，需要根据实际需求和对误判率的容忍程度进行适当的配置。

Q2：大 Key 问题

设想，我们短链接中如果使用 Set，那么极有可能会发生一个 Set 存储数百万甚至上千万的元素，这就涉及到大 Key 问题。
Redis 中的 “大 Key” 通常指的是一个占用较大内存空间的键（Key）。这可能会对 Redis 的性能产生负面影响，因为大 Key 可能导致内存碎片化、删除延迟以及网络传输时间延长等问题。
“大 Key” 的概念相对主观，具体取决于应用程序的需求、硬件配置以及 Redis 实例的总内存大小。在一般情况下，如果一个键的数据量占用了大量的内存比例，可能就可以被认为是大 Key。
具体的大小标准没有固定的规定，因为这取决于多个因素，我们可以在应用设计时按照一个简约的标准执行：
String Key 存储内容最多不允许超过 5MB。
LIST、SET、ZSET 等类型的 Key，成员数量最多不允许超过 20000。
Hash 类型的 Key，Key 数量参考上条。同时，内部 Key 对应的 Val 不应该过大，不然还是可能成为大 Key。

以上观点参考了多家 Redis 开发规范，但就像上面说的，大 Key 的概念更多取决于应用程序需求、硬件配置以及实例总大小，所以没有标准限制。这点大家可以和面试官重点强调下。

大 Key 可能会导致以下问题：

内存碎片化：大 Key 占用的内存块较大，可能导致内存碎片化，从而影响 Redis 的内存使用效率。
网络传输延迟：传输大 Key 的数据可能会导致较长的网络传输时间，特别是在进行备份、迁移或从节点同步等操作时。
删除阻塞：在删除大 Key 的过程中，可能会导致其他操作的响应时间变长。这是因为在删除大 Key 时，需要遍历键中的所有元素，并在内部进行相应的清理操作。在此期间，其他操作会等待删除操作完成。
持久化延迟：如果 Redis 实例使用了持久化机制（如 RDB 快照或 AOF 日志），删除大 Key 可能会导致持久化操作的延迟，因为持久化过程也需要处理大 Key 的数据。

标签：java,requestParam,布隆,Key,跳转,过滤器,import,链接
From： https://blog.csdn.net/weixin_46028606/article/details/143112681