# xinshortlink

**Repository Path**: eric_go/xinshortlink

## Basic Information

- **Project Name**: xinshortlink
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2025-03-21
- **Last Updated**: 2025-04-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 短链接

![link.jpg](doc/link.jpg)

短链接是一种将原始的长URL通过特定的算法或服务转换为更短、易于记忆和分享的URL的形式。它的好处包括短、字符少、美观、便于发布和传播。短链接在多种场景中都有应用，比如短信营销、电子邮件促销、社交网络分享、渠道推广、广告网络推广和搜索引擎优化等

## 数据库表结构

![短链接表结构.png](doc/link_db.png)

## 实现细节

### 账户注册

账户注册功能的核心逻辑是判断账户名是否存在，若不存在则将其插入数据库。然而，在高并发场景下，直接操作数据库会带来巨大压力，具体应对策略如下：

#### 正常情况（大量真实用户同时注册）

- 布隆过滤器预判断：先使用布隆过滤器快速判断账户名是否存在。布隆过滤器判断存在误判可能，但影响有限，无非是提示用户换账户名，可接受。
- 分布式锁限流：对同一个账户名的多次注册请求，利用分布式锁确保只有一个请求能操作数据库，减少数据库压力。

#### 非正常情况（恶意随机注册攻击）
面对恶意攻击，技术手段相对有限，主要依赖以下策略：

- 限流：当检测到异常流量时，限制单位时间内的请求量，超出部分直接拒绝，从而保护系统资源，避免被恶意请求耗尽。
- 封禁IP：识别并记录发送恶意请求的IP地址，必要时直接封禁，阻止其继续发送请求。
- 验证码验证：要求用户完成验证码验证，增加攻击成本。


### 生成短链接

![创建短链接流程图.png](doc/create_link.png)

短链接与长链接之间是一种对应关系，例如：“abc”可对应“https://gitee.com/eric_go/xinshortlink”。生成短链接的方案多样，包括 uuid、数据库自增 id、hash 算法、base62 等，但各有优缺点：

1. uuid：生成的 id 过长，不符合短链接追求简洁的要求。
2. 自增 id：存在可推测性，安全性欠佳，恶意者可能借此推测其他短链接。
3. hash 算法：存在一定的 hash 碰撞概率，影响稳定性。
4. base62 算法：能有效缩短字符串且可逆向解码，但因可逆向性导致安全性不足。

没有一种完美的实现方案。我选择的方案是：使用雪花算法生成唯一 id，经 fnv32 算法哈希后，再通过 base62 转为短字符串，最后与长链接绑定。这一方案虽能大幅降低冲突概率，但仍无法完全避免冲突，因此采用布隆过滤器进行冲突检测，一旦发现冲突则重新生成短链接。

### 访问短链接

![短链接跳转流程图.png](doc/goto_link.png)

短链接的访问逻辑看似简单，主要涉及根据请求的短链接找到原始链接并进行重定向，同时记录访问日志。然而，在高并发场景下，这一过程可能会面临诸多挑战。以下是针对这些问题的优化建议：
#### 缓存数据结构
直接采用 Redis 的 String 数据结构进行缓存，因为其他类型如 Hash、List/Set、Sorted Set 等并不适合此类场景。Hash 适用于多字段存储，List/Set 适用于集合操作，Sorted Set 则用于排序场景。
#### 布隆过滤器
利用布隆过滤器快速判断短链接是否存在。若不存在，直接终止请求处理，避免无效操作。
#### 防止缓存穿透
当大量不存在的短链接被访问时，由于这些短链接未被缓存，将直接导致对数据库的频繁查询，可能使数据库不堪重负。为避免这种情况，可缓存空跳转信息，防止不存在的短链接直接访问数据库。
#### singleflight 与分布式锁
对于存在但未缓存的短链接，在流量洪峰时可能导致大量请求直接查询数据库，增加数据库压力。此时，可选择使用分布式锁或 singleflight 来优化：
- 分布式锁：确保同一时刻只有一个请求能够到达数据库，从而减轻数据库压力。但若锁内逻辑复杂，可能会导致大量请求堆积和超时。
- singleflight：实现请求合并，使最终到达数据库的请求只有一个。与分布式锁不同，singleflight 仅保证单机内的请求合并。例如，假设有 1000 个请求平均分配到 10 台机器上，最终到达数据库的请求将只有 10 次。该方案在很大程度上减轻了数据库压力，但在强一致性要求的场景下不适用。

鉴于短链接访问通常无需强一致性，使用 singleflight 方案以优化性能。

#### 热点短链接
在短时间内大量请求短链接时，即使使用 Redis 缓存，也可能因网络开销导致性能瓶颈。本地缓存虽能缓解此问题，但因资源有限，需仅缓存热点短链接。

滑动窗口算法能有效识别这些热点短链接。该算法通过维护一个固定大小的时间窗口，记录每个短链接的访问频率。窗口滑动时，会丢弃最早的数据，确保只保留最近的访问记录。这使我们能精准识别高频访问的热点短链接，并将其缓存于本地，从而减少对 Redis 的依赖，提升系统性能。


### 访问记录

短链接的访问记录主要用于帮助运营人员分析访问数据，其核心逻辑是每次访问时记录一条记录。然而，在高并发场景下，直接记录到数据库会导致性能瓶颈。为解决这一问题，采用以下优化策略：
逻辑是很清晰的，难点在于如果高并发场景下如何高效的保存访问记录。

1. 使用消息队列（MQ）削峰
   将每次访问的记录推送到消息队列（MQ），由后台异步消费处理。这种方式既能提升短链接的重定向速度，又能减少数据库的直接访问压力。
2. 批量推送，减少网络开销
   通过缓冲机制，将多条访问记录攒成一批后再推送到MQ。这种方式可以显著降低与MQ的网络交互次数，同时减少数据库的写入频率
3. 压缩消息体积
   - 使用 Protocol Buffers（protobuf） 替代JSON进行二进制序列化，大幅减少消息体积。
   - 在此基础上，结合 Snappy 等压缩算法对消息体进一步压缩，进一步降低网络传输成本。

### 分表

**t_link 短链接表现状** ：t_link 短链接表字段较为简单，当单表数据量达到上千万时，访问性能尚可。但随着数据量持续增加，性能将急剧下降，因此采用分表策略势在必行。

#### 选择分片键的考量

- **按分组分片的优势与场景** ：在管理端查询短链接时，通常依据分组和原始链接后缀作为筛选条件。此时，若以分组作为分片键，查询时便能直接定位到特定分表获取结果，避免了全表扫描，可显著提升查询效率。。
- **按短链接 id 分片的优势与场景** ：短链接访问跳转时，筛选条件为短链接 id。以短链接 id 作为分片键，可快速精准地找到对应短链接所在分表，加快跳转速度。


综合考虑不同业务场景下的查询需求，最终选择分组作为分片键，以此解决管理端查询短链接时的性能问题，避免出现通过多表联合查询（如使用 union all 实现多表查询后排序再分页）导致性能不佳且实现复杂的情况。

- 短链接跳转时快速定位分表的解决方案
  - **方案一：短链接携带分表信息** ：生成短链接时，将短链接 id 通过分片算法确定分表后，将分表信息附加在短链接上。例如，短链接 id 为 ABCDE 的数据存储于 t_link_0 表，则最终短链接为 ABCDE1。该方案直观简洁，但缺点是短链接存在一定的可猜测性。
  - **方案二：增设跳转表** ：创建一个包含分组和短链接 id 字段的跳转表。查询短链接时，先依据短链接 id 在跳转表中查询出分组，再结合分组与短链接 id 一同查询短链接信息。 ：创建一个包含分组和短链接 id 字段的跳转表。查询短链接时，先依据短链接 id 在跳转表中查询出分组，再结合分组与短链接 id 一同查询短链接信息。