短链接核心3：创建短链接

1. 生成短链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private String generateSuffix(ShortLinkCreateReqDTO requestParam) {
    int customGenerateCount = 0;
    String shorUri;
    String originUrl = requestParam.getOriginUrl();
    while (true) {
        if (customGenerateCount > 10) {
            throw new ServiceException("短链接频繁生成，请稍后再试");
        }
        shorUri = HashUtil.hashToBase62(originUrl);
        if (!shortUriCreateCachePenetrationBloomFilter.contains(createShortLinkDefaultDomain + "/" + shorUri)) {
            break;
        }
        originUrl += UUID.randomUUID().toString();
        customGenerateCount++;
    }
    return shorUri;
}

生成短链接
短链接唯一性是当前域名下的短链接唯一，所以生成短链接时，首先通过HashUtil.hashToBase62(originUrl)生成短链接，如果生成的短链接已经存在，则进行重试，通过UUID.randomUUID().toString()拼接到原链接上，再次生成短链接。

通过 Hash 算法将原始连接转换成一个 Hash 码，这里使用了 Google 出品的 MurmurHash 算法。
因为生成的 Hash 码是十进制的，整体较长不利于短链接传播。为此，我们将十进制转换为 62 进制，也就是最终的短链接。

短链接生成算法 
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
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);
    }
}

短链接重复判断
为了防止并发场景下海量请求查询数据库，判断短链接是否存在通过布隆过滤器shortUriCreateCachePenetrationBloomFilter。
且如果短链接一直重复，超过指定次数，就抛出异常。

为什么不用 Set 结构

为什么不使用Set结构？性能又高，又不会有误判率。

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

2. 插入数据库

1
2
3
4
5
6
7
8
9
10
11
12
try {
    // 短链接项目有多少数据？如何解决海量数据存储？
    baseMapper.insert(shortLinkDO);
    // 短链接数据库分片键是如何考虑的？
    shortLinkGotoMapper.insert(linkGotoDO);
} catch (DuplicateKeyException ex) {
    // 首先判断是否存在布隆过滤器，如果不存在直接新增
    if (!shortUriCreateCachePenetrationBloomFilter.contains(fullShortUrl)) {
        shortUriCreateCachePenetrationBloomFilter.add(fullShortUrl);
    }
    throw new ServiceException(String.format("短链接：%s 生成重复", fullShortUrl));
}

由于并发场景下存在两个相同的短链接生成，数据库中fullShortUrl为唯一索引，需要捕获插入数据库时重复主键异常，并判断布隆过滤器中不存在，则新增到布隆过滤器。
同时这里有两次数据库操作，需要加上事务注解@Transactional(rollbackFor = Exception.class)。

由于短链接分表通过gid分片，并发场景下存在生成相同的短链接，但是请求的gid不同，那么此时插入短链接表则可能插入不同的表，唯一索引fullShortUrl失效。
因此这里给跳转表中的fullShortUrl加上唯一索引，保证fullShortUrl唯一。因为跳转表分表通过fullShortUrl分片，所以相同的fullShortUrl会插入到同一张表中，可以通过唯一索引重复捕获异常。

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
@Transactional(rollbackFor = Exception.class)
    @Override
    public ShortLinkCreateRespDTO createShortLink(ShortLinkCreateReqDTO requestParam) {
        // 短链接接口的并发量有多少？如何测试？
        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())
                .gid(requestParam.getGid())
                .createdType(requestParam.getCreatedType())
                .validDateType(requestParam.getValidDateType())
                .validDate(requestParam.getValidDate())
                .describe(requestParam.getDescribe())
                .shortUri(shortLinkSuffix)
                .enableStatus(0)
                .totalPv(0)
                .totalUv(0)
                .totalUip(0)
                .delTime(0L)
                .fullShortUrl(fullShortUrl)
                .favicon(getFavicon(requestParam.getOriginUrl()))
                .build();
        ShortLinkGotoDO linkGotoDO = ShortLinkGotoDO.builder()
                .fullShortUrl(fullShortUrl)
                .gid(requestParam.getGid())
                .build();
        try {
            // 短链接项目有多少数据？如何解决海量数据存储？
            baseMapper.insert(shortLinkDO);
            // 短链接数据库分片键是如何考虑的？
            shortLinkGotoMapper.insert(linkGotoDO);
        } catch (DuplicateKeyException ex) {
            // 首先判断是否存在布隆过滤器，如果不存在直接新增
            if (!shortUriCreateCachePenetrationBloomFilter.contains(fullShortUrl)) {
                shortUriCreateCachePenetrationBloomFilter.add(fullShortUrl);
            }
            throw new ServiceException(String.format("短链接：%s 生成重复", fullShortUrl));
        }
        // 项目中短链接缓存预热是怎么做的？
        stringRedisTemplate.opsForValue().set(
                String.format(GOTO_SHORT_LINK_KEY, fullShortUrl),
                requestParam.getOriginUrl(),
                LinkUtil.getLinkCacheValidTime(requestParam.getValidDate()), TimeUnit.MILLISECONDS
        );
        // 删除短链接后，布隆过滤器如何删除？
        shortUriCreateCachePenetrationBloomFilter.add(fullShortUrl);
        return ShortLinkCreateRespDTO.builder()
                .fullShortUrl("http://" + shortLinkDO.getFullShortUrl())
                .originUrl(requestParam.getOriginUrl())
                .gid(requestParam.getGid())
                .build();
    }

3. 常见问题

1. 为什么不用分布式锁

因为分布式锁是串行的，而布隆过滤器可以做到并行。通过在本地进行两种方式的压测，大概评估布隆过滤器是分布式锁的 6 倍性能。理论上说，当并发越高，这个性能差距就越明显。其次，通过分布式锁查询的是 MySQL 数据库，这里还要算上数据库的性能和缓存的差距。
而且，因为我们访问短链接跳转原始链接接口处理缓存穿透场景，需要使用布隆过滤器完成。所以在这里直接使用是刚好的。

分布式锁代码 
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
66
67
68
69
70
71
72
73
74
75
76
77
78
@Override
public ShortLinkCreateRespDTO createShortLinkByLock(ShortLinkCreateReqDTO requestParam) {
    verificationWhitelist(requestParam.getOriginUrl());
    String fullShortUrl;
    // 为什么说布隆过滤器性能远胜于分布式锁？详情查看：https://nageoffer.com/shortlink/question
    RLock lock = redissonClient.getLock(SHORT_LINK_CREATE_LOCK_KEY);
    lock.lock();
    try {
        String shortLinkSuffix = generateSuffixByLock(requestParam);
        fullShortUrl = StrBuilder.create(createShortLinkDefaultDomain)
                .append("/")
                .append(shortLinkSuffix)
                .toString();
        ShortLinkDO shortLinkDO = ShortLinkDO.builder()
                .domain(createShortLinkDefaultDomain)
                .originUrl(requestParam.getOriginUrl())
                .gid(requestParam.getGid())
                .createdType(requestParam.getCreatedType())
                .validDateType(requestParam.getValidDateType())
                .validDate(requestParam.getValidDate())
                .describe(requestParam.getDescribe())
                .shortUri(shortLinkSuffix)
                .enableStatus(0)
                .totalPv(0)
                .totalUv(0)
                .totalUip(0)
                .delTime(0L)
                .fullShortUrl(fullShortUrl)
                .favicon(getFavicon(requestParam.getOriginUrl()))
                .build();
        ShortLinkGotoDO linkGotoDO = ShortLinkGotoDO.builder()
                .fullShortUrl(fullShortUrl)
                .gid(requestParam.getGid())
                .build();
        try {
            baseMapper.insert(shortLinkDO);
            shortLinkGotoMapper.insert(linkGotoDO);
        } catch (DuplicateKeyException ex) {
            throw new ServiceException(String.format("短链接：%s 生成重复", fullShortUrl));
        }
        stringRedisTemplate.opsForValue().set(
                String.format(GOTO_SHORT_LINK_KEY, fullShortUrl),
                requestParam.getOriginUrl(),
                LinkUtil.getLinkCacheValidTime(requestParam.getValidDate()), TimeUnit.MILLISECONDS
        );
    } finally {
        lock.unlock();
    }
    return ShortLinkCreateRespDTO.builder()
            .fullShortUrl("http://" + fullShortUrl)
            .originUrl(requestParam.getOriginUrl())
            .gid(requestParam.getGid())
            .build();
}

private String generateSuffixByLock(ShortLinkCreateReqDTO requestParam) {
    int customGenerateCount = 0;
    String shorUri;
    while (true) {
        if (customGenerateCount > 10) {
            throw new ServiceException("短链接频繁生成，请稍后再试");
        }
        String originUrl = requestParam.getOriginUrl();
        originUrl += UUID.randomUUID().toString();
        // 短链接哈希算法生成冲突问题如何解决？详情查看：https://nageoffer.com/shortlink/question
        shorUri = HashUtil.hashToBase62(originUrl);
        LambdaQueryWrapper<ShortLinkDO> queryWrapper = Wrappers.lambdaQuery(ShortLinkDO.class)
                .eq(ShortLinkDO::getGid, requestParam.getGid())
                .eq(ShortLinkDO::getFullShortUrl, createShortLinkDefaultDomain + "/" + shorUri)
                .eq(ShortLinkDO::getDelFlag, 0);
        ShortLinkDO shortLinkDO = baseMapper.selectOne(queryWrapper);
        if (shortLinkDO == null) {
            break;
        }
        customGenerateCount++;
    }
    return shorUri;
}

可以不可以不用分布式锁或者布隆过滤器，直接查询数据库？

一旦并发创建短链接的请求过高，那么数据库的压力就会很大。
测试腾讯云的 4C8G云数据库，TPS 应该能到 5000 左右。也就是说，如果靠数据库抗，每秒能承受这些压力。这还只是算创建接口，如果有用户查询统计等场景查询数据库，那么又得分配出去一些资源，整体来说，性能会进一步下降。
针对数据库这个点，想要支撑更高的压力，只能说分库处理，通过多个库水平拆分，假设分为 4 个，那么并发能力就是 5000 * 4。但是这个架构方案整体来说就比较复杂了。
所以说，针对于分布式锁这个问题，就是在并发场景下，我们为了防止大量查询和新增冲突以及保护数据库资源被频繁访问。

2. 删除短链接后，布隆过滤器如何删除？

布隆过滤器是不支持删除的，因为删除一个元素会影响到其他元素的判断。

删除短链接后加入到 Reids Set

  1. 短链接 “nurl.ink/qweoid” 成功注册后，将其添加至布隆过滤器。
  2. 当其他用户查询”nurl.ink/qweoid”是否已被使用时，首先检查布隆过滤器是否包含该短链接。
  3. 如果布隆过滤器中不存在该短链接，根据布隆过滤器的特点，可以确认该短链接一定没有被使用过，因此返回成功，证明该短链接可用。
  4. 如果布隆过滤器中存在该短链接，进一步检查Redis Set结构中是否包含该短链接。如果存在，表示该短链接已被删除，同样可被再次使用。
  5. 如果布隆过滤器中存在该短链接，但 Redis Set 结构中不存在，说明该短链接已被使用且尚未被删除或者发生布隆过滤器误判，因此不可用。

3. Redis 返回成功，但布隆过滤器持久化指令失败了，会生成重复短链接么？

创建时成功插入数据库，但没有成功插入布隆过滤器。
由于短链接是唯一索引，所以会抛出异常，不会生成重复短链接，同时往布隆过滤器插入。