短链系统设计

功能说明

短链算法

使用数据库主键（pk）一一映射到短链码（code），这个映射的过程使用的是FF3-1 保形加密算法。

Golang 加密算法开源：https://github.com/dusty-cjh/golang-fpe

• 为什么不使用雪花算法？

1. 我们的短链长度只有 6 位，如果使用雪花算法，8 字节的数据 base62 编码后会达到 11 位，不符合要求。
2. 去年全年的营销短信数量在 100 亿左右，其中用到短链的有 60 亿，而短信是以字数（每70字）计费的。
3. 6 位短链对应的 int 类型大小为 5 字节，对于 5 字节的雪花算法来说，不如直接用 sequenceID，即数据库 PK。

• 为什么不直接用 PK 加密成 code？
  • PK 是 int64 类型，加密成 code 以后会变成 11 位的字符串，带来额外成本。

系统设计

创建短链的流程是这样的：

发号器

在创建短链时，发号器用来给 “创建短链” API 提供唯一的、连续的数据库 pk。

如上图所示：

• 调用 getPk() 函数时，会先从本地缓存中获取 pk，
• 如果 pk 的范围超出 maxPk，则会从 redis 中 incrBy xxx 'concurrency' 批量获取 pk，更新到本地缓存中。
• 如果 redis 中的 pk 过期，则会从数据库中 SELECT MAX(pk)，

上图流程中的不足：

• 当本地 pk 耗尽时，需要等待从 Redis 获取 pk 的结果
• 当 Redis Key 过期时，需要等待从 DB 获取 pk 的结果

优化建议：

• 当 剩余本地缓存Pk量 < 当前并发量 时，主动并发拉取新的 Redis Pk
• Redis 使用自动续期：Redis Pk = Max(maxRedisPk, maxDBPk)

为什么当前不优化？

• 根据 pprof 分析，最大的耗时在DB 插入 和 RabbitMQ 统计数据 上，而 Redis 获取 pk 这部分的占比已经可以忽略不计了。
• 在下一节实现 “DB 批量插入” 后，最大的性能损失就只在 RabbitMQ 统计数据 上了。

DB 批量插入

在创建短链时，”DB批量插入“ 用来把单个创建批量化，减少数据库压力，同时能同步返回插入结果。思路就是缓存正在进行的插入操作，每间隔 50ms 启动用于批量插入的 goroutine 一次。

如图所示，每个队列中的 obj 都有一个 mutex 锁和 ch 对象。左边的 goroutine 会在批量插入操作开始前获取锁，批量插入操作结束后释放锁， 并将结果通过 ch 发送到右边的 goroutine。

可以使用 atomic.CompareAndSwap 函数保证同一时间只有一个批量插入的 goroutine 在运行。

func singleInsert() {
  ...

  //  仅当没有预备中的 goroutine 时，预备新的 gouroutine
  if atomic.CompareAndSwap(&BatchInsertPreparingFlag, 0, 1) {
    go time.AfterFunc(50ms, batchInsert)
  }

  ...
}

func batchInsert() {
    //  允许预备下一个 BatchInsert 操作
    isPrepared := atomic.CompareAndSwapInt32(&BatchInsertPreparingFlag, 1, 0)

    //  确保同一时刻只有一个 BatchInsert 正在运行
    if !atomic.CompareAndSwapInt32(&BatchInsertRunningFlag, 0, 1) {
        if isPrepared {
            isPrepared = atomic.CompareAndSwapInt32(&slBatchInsertPreparingFlag, 0, 1)
            if isPrepared {
                go time.AfterFunc(slTimeout, this.doCreate)
            }
        }
        return
    }
    defer func() {
        if !atomic.CompareAndSwapInt32(&BatchInsertRunningFlag, 1, 0) {
            panic(fmt.Errorf("short link manager unexpected 0"))  //  不可能触达
        }
    }()

  ...
}

通过添加 Prepare goroutine 的方法，可以避免因为竞态问题导致部分 SingleInsert 没被执行到。可以用反证法来证明这一点。

竞态问题 1：

当 A 插入并且 go BatchInsert 时，B 未 go BatchInsert，且 $BatchInsert_A$ 并未获取到 B 的数据。导致 B 永远不会被插入。

发生条件：

$BatchInsert_A$ 已启动未运行，B 走到了 atomic.CompareAndSwap(&BatchInsertPreparingFlag, 0, 1)，发现已有在预备的 goroutine，遂跳过。

$BatchInsert_A$ 开始正常运行，获取到 A，但未获取到 B 的数据。

但由于B 入队列操作在 atomic.CompareAndSwap(&BatchInsertPreparingFlag, 0, 1) 检查之前，所以此时 B 数据必然已入队列，可被成功发现。

证明完毕

竞态问题 2：

当 A 插入并且 go BatchInsert 时，B 也 go BatchInsert，但直到 $BatchInsert_B$ 协程超时，$BatchInsert_A$ 依然卡在插入DB这一步上，导致 $BatchInsert_B$ 取锁失败直接退出，B永远不会被插入。

解决方案： 当 $BatchInsert_B$ 运行时，探测是否有正在运行的 $BatchInsert$ 操作，如果有，则重新 Prepare goroutine。

最终的效果就是，当高负载时，总有一个 Prepare goroutine 在等待执行。当低负载时，不会有任何额外的 $BatchInsert$ 执行。

审核

其实在判定是否违法违规这方面，没法用算法来解决。 最好的方法就是 docker 运行 puppeteer，模拟浏览器访问短链，然后用 LLM 识别页面内容，给出各项的分值：

• spam
• phishing
• malware
• adult
• copyright
• violence
• hate speech
• gambling
• scam

最后，基于分值来判断是否违法违规。

数据统计

支持的维度：

• 时间（小时维度）：
  • PV / UV / IP / 地域 / 设备 / 渠道

比如用户可能想知道：

• 过去 24 小时内，某个短链的访问量（PV）和独立访客数（UV）？
• 过去 7 天内，主要是哪个地区的用户在访问这个短链？
• 过去 30 天内，主要用什么访问这个短链？微信？QQ？知乎？淘宝？
• 过去 90 天内，用户访问的 24 小时时间分布是什么样的？晚上 20:00 居多？
• 过去 180 天内，用户访问的设备分布是什么样的？手机？电脑？平板？

压力测试

• 机器：Mac Book Pro M1 (2020款)
• 数据库：MongoDB

支持每秒 2500+ 同时创建。

支持每秒 4000+ 同时访问。

例如，点击 hdcjh.xyz/mgex8 访问短链。

技术支持

• 您可直接发送邮件到 dusty-cjh@qq.com