系统背景

本系统的开发目的源于一道经典的开发面试题——设计一个短链接系统。本文将从多维度、多角度对其进行剖析。

短链接系统几乎是每个互联网公司营销业务线必备的跳转平台，其核心优势在于能最大限度压缩链接长度，对于营销短信、邮件而言，不仅具备良好的匿名性，还能提升视觉友好度。例如以下这条短链接：

y4pY9e.jpeg

单从短信中的链接来看，其 URI 看似一段乱码，但仔细分析会发现，这段 URI 由 8 个字符组成。若按每个字符占 8bit 计算，整个 URI 的信息容量恰好为 64bit，这绝非巧合。

从现象反推原理

访问上述短链接会发现，浏览器会执行一次跳转操作：

y4pN0c.png

也就是说，当用户访问短链接时，短链接服务的后端会根据 URI 末尾那段看似乱码的字符串，查询对应的原始长链接，随后返回 302 状态码，引导浏览器跳转到目标地址。从表面上看，其原理与普通互联网项目并无太大差异，核心都是“查询数据库 → 返回结果”，但这段“乱码”真的是后端随机生成的吗？如何确保这个随机字符串的唯一性？

永不重复的 ID

在 MySQL 等传统数据库中，通常会使用主键 ID 唯一标识一条数据，其核心优势如下：

  1. ID 通常由数据库自动生成，借助事务机制可确保其唯一性；

  2. ID 呈线性增长，当需要通过 ID 进行游标查询时（表述可能不够精准），游标可快速定位到指定位置，进而查询后续数据（即具备可排序性）；

  3. 可基于 ID 对数据进行排序操作。

对于 MySQL 而言，常用的最大数字类型是 bigint，其最大值为 9223372036854775807，占用空间恰好为 64bit，与前文提到的短链接 URI 信息容量完全对应。但如果直接将 bigint 作为短链接的编码，会给业务带来诸多瓶颈：

  1. ID 生成完全依赖数据库，在分布式、高并发场景下，数据库会直接承受巨大压力；

  2. ID 线性增长的特性，可能导致黑客通过起始 ID 遍历所有短链接，存在安全隐患。

眼光投向 MongoDB

我们知道，MongoDB 是一款分布式 NoSQL 数据库，其分布式特性决定了它在高并发场景下的稳定性与可扩展性。MongoDB 中数据的主键是 ObjectID，查阅官方文档可知，该 ID 具有明确的结构特性：

  • 时间戳（4 字节）：记录 ObjectID 的创建时间，单位为秒；

  • 机器标识符（3 字节）：标识生成 ObjectID 的机器，前两字节为网络字节序的机器 ID，后一字节为进程 ID；

  • 计数器（2 字节）：在同一台机器、同一进程中生成新 ObjectID 时，计数器会自动递增；

  • 随机数（3 字节）：增加随机性，降低 ID 冲突的概率。

本质上，ObjectID 是一段字符串的拼接。从结构不难看出，该 ID 由分片节点（shard）生成——相较于 MySQL，MongoDB 将 ID 生成的工作转移到了 shard 节点，有效降低了单节点的压力。从理论上来说，短链接系统完全可以基于 MongoDB 实现。

但在工业级实践中，短链接系统很少使用 MongoDB 存储数据，核心原因如下：

  1. ObjectID 长度过长，相较于对 bigint 进行编码的方式，MongoDB 会占用更多存储空间，增加成本；

  2. MongoDB 的核心优势在于表扩展、集群扩展等全方位可扩展性，但短链接系统通常只需要集群扩展能力，无需过度依赖其全量扩展特性。

综合以上分析，我们可以借鉴 ObjectID 的生成思路，设计一种适配分布式场景的 ID 生成方案。

SnowFlake（雪花算法）

雪花算法的 ID 结构与 ObjectID 类似，具体结构如下：

y4GJFO.png

雪花算法的经典之处在于，其 ID 结构可根据实际业务需求灵活定制；同时，雪花 ID 的生成过程通常由分布式业务节点自行完成，这就保证了高并发场景下 ID 生成的性能。

雪花算法的原理可类比于令牌桶算法：例如某业务系统使用令牌桶算法对单节点进行限流，令牌桶算法会在每个时间窗口的第一次调用时，向桶中存入对应数量的令牌；该时间窗口内的所有请求，需从桶中获取令牌后才能访问后端服务。当桶中令牌耗尽时，后续请求要么排队等待下一个时间窗口，要么直接被拒绝。

雪花算法的原理与之类似：每台机器可看作通过自身的机器 ID，维护一个专属令牌桶；以时间戳作为时间窗口，雪花 ID 中的“序号”可理解为令牌桶中的令牌。当服务生成雪花 ID 时，在同一个时间窗口内每生成一个 ID，序号就会加 1（此处需注意线程安全问题——序号的递增操作需引入线程锁，防止高并发场景下出现序号复用。对于 Go、C++等语言而言，线程锁的耗时基本在微秒级，通常不会影响业务基线性能）。当时间窗口累加溢出时，生成 ID 的请求会暂时挂起，等待下一个时间窗口再继续获取。

使用雪花算法的核心优势如下：

  1. ID 具有结构化特性，结合算法本身的设计，基本不会出现 ID 冲突的情况；

  2. ID 本质是一个 int64 类型的数据，整体呈线性增长，但并非连续增长——这就避免了黑客通过起始 ID 遍历所有短链接的风险，同时数据库也可基于该 ID 对数据进行排序操作。

那段乱码怎么解释

雪花算法生成的是一个 int64 类型的长整数，这种结构化生成的 ID 通常长度较长。因此，在短链接系统中，通常会使用 base62 等编码算法，将 int64 类型的 ID 转换为 8 位字符串（需注意：转换后的字符串长度缩短，但存储空间并未减少，该字符串的大小仍为 8×8=64bit）。这就是短链接 URI 的最终形态。

直接上代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

package snowflake



import (

        "errors"

        "shoturl/config"

        "sync"

"time"

)



const (

        timestampBits = 41

        machineIdBits = 10

        sequenceBits  = 12



        maxMachineId   = -1 ^ (-1 << machineIdBits)

        maxSequence    = -1 ^ (-1 << sequenceBits)

        timestampShift = sequenceBits + machineIdBits

        machineIdShift = sequenceBits

)



type Snowflake struct {

        mutex         sync.Mutex

        lastTimestamp int64

        machineId     int64

        sequence      int64

}



var (

        ErrInvalidMachineId      = errors.New("invalid machine id")

        ErrorClockMovedBackwards = errors.New("clock moved backwards")

)



func New() (*Snowflake, error) {

        if config.Cfg.MachineID < 0 || config.Cfg.MachineID > maxMachineId {

                return nil, ErrInvalidMachineId

        }



        return &Snowflake{

  lastTimestamp: -1,

                machineId:     config.Cfg.MachineID,

                sequence:      0,

        }, nil

}



func (s *Snowflake) NextId() (int64, error) {

        s.mutex.Lock()

        defer s.mutex.Unlock()

        timestamp := time.Now().UnixMilli()

        if timestamp < s.lastTimestamp {

                return 0, ErrorClockMovedBackwards

        }



        if timestamp == s.lastTimestamp {

  s.sequence = (s.sequence + 1) & maxSequence

                if s.sequence == 0 {

                        for timestamp <= s.lastTimestamp {

                                timestamp = time.Now().UnixMilli()

                        }

                }

 } else {

                s.sequence = 0

        }

        s.lastTimestamp = timestamp

        return (timestamp << timestampShift) | (s.machineId << machineIdShift) | s.sequence, nil

}



const base62Chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const Base62Length = 62



func (s *Snowflake) NextBase62Id() (string, error) {

        id, err := s.NextId()

        if err != nil {

                return "", err

        }



        var buf []byte



        num := id



        for num > 0 {

                index := num % Base62Length

                buf = append(buf, base62Chars[index])

                num = num / Base62Length

        }



        for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {

                buf[i], buf[j] = buf[j], buf[i]

 }



        return string(buf), nil

}

大流量访问

在短链接系统中，访问短链接的请求量通常远高于创建短链接的请求量。因此，若用户每次访问短链接都直接查询数据库，无疑是一种低效且不合理的做法。此时，我们很容易想到在数据库前增加一层缓存，但换个角度思考：这种缓存方案真的可靠吗？

例如，当黑客漫无目的地扫描短链接系统漏洞时，可能会发现：访问不存在的短链接时，请求响应速度明显慢于访问正常短链接。由此可轻易推断出，系统存在缓存击穿的情况——即不存在的短链接会直接穿透缓存，查询数据库。基于这一漏洞，黑客可通过批量请求不存在的短链接，发起攻击，最终导致数据库崩溃。

怎么快速拦截不存在的短链接

提到“快速拦截”，我们首先想到的依然是缓存。最基础的解决方案如下：

在生成短链接时，直接将短链接的 ID 存入缓存（无论是使用 set 类型还是 string 类型均可）；当有访问请求时，先查询缓存，若缓存中不存在该 ID，则直接返回错误，拒绝跳转。

这种方案虽能解决缓存击穿问题，但在用户量庞大、短链接数量极多的场景下，会占用大量内存空间，显然不符合实际应用需求。

布隆过滤器

布隆过滤器最初由 Java 通过 bitmap 实现，其核心原理是：将所有可能存在的短链接 ID 存入一个 bitmap 中；当用户访问某个短链接时，先检查该 ID 是否存在于 bitmap 中，若不存在则直接返回错误，若存在则继续查询数据库。

关于布隆过滤器的详细实现原理，可参考此处（不想重复造轮子，就偷懒一下啦）。

值得一提的是，Redis 8.0 及以上版本中，官方已原生支持 BloomFilter（布隆过滤器）功能。开发者可直接通过bf.add命令向布隆过滤器中添加元素，通过bf.exists命令检查元素是否存在，开发友好度大幅提升。