实现高并发短链接服务

2024-07-06 约 7190 字预计阅读 15 分钟

最近在用 Golang 语言实现一个短链接服务Tiny-URL，这期间了解了一些关于短链接服务的设计思路，以及分布式系统中 ID 生成、缓存、限流、负载均衡等方面的知识，这篇文章将会对短链接服务的设计思路进行总结。

概述

在社交媒体、用户增长、广告投放等场景中，经常会遇到长链接转短链接的需求，提高用户点击率更高，同时能规避原始链接中一些关键词、域名屏蔽等。常见微博、微信等社交软件中，比如微博限制字数为140，如果包含的链接过长，会占用很多字数，所以需要将长链接转换为短链接，以节省字数。

短链接除了具有美观清爽的特性外，利用短链每次跳转都需要经过后端的特性，可以在跳转过程中做异步埋点，用于效果数据统计，常见的应用场景如下：

注册、收藏、加购、下单、支付效果统计；
用户分享效果追踪；
减少字符占用。

本文将会介绍短链接服务的设计思路，以及在实现过程中遇到的问题与解决方案。

需求与预算评估

功能需求

短链接生成：给定一个长链接，能够生成一个唯一的短链接，即使多次输入同一个长链接，也能够得到唯一的短链接；
短链接重定向：通过短链接能够访问到原始的长链接，通过 302 临时重定向的方式，将用户重定向到原始的长链接，临时重定向的方式可以保证搜索引擎不会抓取短链接，而是抓取原始的长链接，并且便于统计短链接的访问次数。
访问限流：对短链接的生成与访问进行限流，防止恶意刷短链接，保证服务的稳定性。
短链接删除：短链接可以删除，删除之后，短链接将失效，无法再访问到原始的长链接。
过期时间：短链接可以设置过期时间，过期时间到了之后，短链接将失效，无法再访问到原始的长链接。

非功能需求

高可用：短链接服务需要保证高可用，即使某个节点宕机，也不影响整个服务的正常使用。
高性能：短链接服务需要保证高性能，能够支撑每秒十万 QPS 的访问量。
低延迟：短链接服务需要保证低延迟，用户访问短链接时，能够快速的重定向到原始的长链接。
高可扩展性：短链接服务需要保证高可扩展性，能够支持大量的短链接生成和访问。
高可靠性：短链接服务需要保证高可靠性，能够保证短链接的生成和访问的正确性。

资源预算

假设我们的系统每天有 100M 用户在线，即 1亿日活；
每天平均每10个用户写 1 个帖子，为每个帖子生成一个对应的短链接，即每天总共生成 10M 个短链接：
- 平均每个短链接-长链接映射关系占用 500Bytes 空间，即每天总共需要 5GB 的存储空间；
- 每日 10,000,000 次写入操作，1kw/86400s ≈ 116，即平均每秒需要处理 116qps 的写入操作；
- 假设峰值写入量约平均写入量的 10 倍，即 1160qps，为便于估算，可理解写峰值 qps 为 1k；
平均每个用户每天访问 10 个帖子，即每天总共访问 10亿次短链接，读写比例为 100:1：
- 平均每秒需要处理 11600 的读取操作，即约为 10k/s；
- 假设峰值读取量约平均读取量的 10 倍，即约为 100k/s；
缓存资源预算：
- 由于短链服务具有明显的热点数据特征，因此需要使用缓存来提高访问性能，我们假设 20% 的数据贡献了 99% 的访问量
- 每日 10亿次的访问量中，我们假设 99% 的访问量是固定在 10% 的热点数据上，即需要缓存 2亿条数据，缓存服务器需要 100GB 内存空间；
- 再进一步，我们利用本地缓存来缓存最热的 1% 的数据，即需要缓存 2M 条数据，每台 Server 节点需要 1GB 内存空间用于本地缓存；
- 缓存命中率为 99%，即每日 10亿次的访问量中，有 1% 的访问量需要访问数据库，即 10M 次/日，即每秒需要处理 116 次数据库读取操作，即约为 100qps；

综上所述：

数据库存储空间：每日消耗 5GB 磁盘，三年时间需要约 5.5TB；
数据库读写请求数：平均每秒 116qps 的写入操作与读取操作，峰值 1k/qps 的写入操作与读取操作；
缓存服务器内存空间：总共需要 50GB 内存空间，缓存约 1亿条数据；
本地缓存存储空间：每台 Server 节点需要 500MB 内存空间用于本地缓存，缓存约 1M 条数据；

时序流程

短链接服务的写数据时序流程如下：

用户发起创建短链接请求，服务端接收到请求，将会生成一个唯一的短链接，并尝试将短链接-长链接映射关系写入数据库中；
数据存储端需要保证短链接-长链接映射关系的一致性，即使多次为同一个长链接生成短链接，也能保证生成的短链接是唯一的，因此可以在数据库中为 original URL 设置唯一索引；
当插入的长链接已经存在时，可以直接返回已经存在的短链接，无需再次生成短链接；
当插入的长链接不存在时，需要生成一个唯一的短链接，可以使用分布式 ID 生成器生成唯一的短链接 ID，然后将短链接 ID 转换为 Base58 编码，即可生成短链接；
长链接写入数据库成功后，服务端将短链接-长链接映射关系写入分布式缓存与本地缓存中，以提高访问性能；

短链接服务的读数据时序流程如下：

用户访问短链接时，服务端接收到请求，将会有限从本地缓存中获取短链接-长链接映射关系，如果本地缓存中不存在，则从分布式缓存中获取，如果分布式缓存中不存在，则从数据库中获取；
如果本地缓存不存在，分布式缓存中存在，则将接映射关系写入本地缓存中，以提高访问性能；如果缓存中不存在，数据库中存在，则将映射关系写入缓存中；
如果数据库中也不存在，则返回 404 错误，表示短链接不存在，同时可以设置黑名单，对恶意访问进行限制；
如果获取短链接成功，通过 302 临时重定向的方式，将用户重定向到原始的长链接；
访问短链接成功后，可以统计短链接的访问次数，以便后续分析短链接的访问情况；

模块设计

短链接服务涉及分布书 ID 生成器、数据库存储、缓存系统、访问限流等模块，下面将会对这些模块进行详细设计。

分布式 ID 生成器

短链接发号器需要保证生成的短链接是唯一的，可以使用分布式 ID 生成器，如 Twitter 的 Snowflake 算法，或者使用数据库自增 ID 生成器等等，下面将描述不同方案的优缺点：

数据库自增 ID

数据库的主键是唯一且自增的，可以保证生成的 ID 是唯一的。将数据库自增 ID 作为短链接 ID，然后将 UID 转换为 Base58 编码，即可生成短链接。

优点：简单易用，生成的 ID 是唯一的；缺点：依赖于数据库，数据库的性能将成为瓶颈，不适合高并发场景，如果采用数据库集群，需要避免 ID 重复；并且数据库自增 ID 是有序的，可能会暴露业务规模；

Redis 自增序列

Redis 的自增序列可以使用 INCR 命令，每次调用 INCR 命令，Redis 会将自增序列加 1，并返回自增后的值。因此可以将 Redis 的自增序列作为短链接 ID，然后将 UID 转换为 Base58 编码，即可生成短链接。

优点：高性能，生成的 ID 是唯一的；缺点：Redis 是基于内存的，如果 Redis 宕机，可能会导致 ID 重复，需要保证 Redis 的高可用；ID 自增是有序的，可能会暴露业务规模；

UUID

UUID 是由一组 16 个字节（128 位）组成的标识符，可以用于唯一标识信息。UUID 的生成方式有多种，其中最为常用的是基于算法的 UUID 生成方式和基于硬件的 UUID 生成方式。基于时间戳的 UUID 生成方式，可以保证生成的 UUID 是唯一的，并且是有序的，但是如果多台机器的时钟存在差异，或时钟回拨或闰秒，可能会导致 ID 重复。基于硬件的 UUID 生成方式，可以保证生成的 UUID 是唯一的，且随机性更强。但是 UUID 是 128 位的，转换为 Base58 编码后，短链接长度过长，不适合短链接服务；且 UUID 是无序的，插入数据时可能会导致数据库的性能问题；

优点：生成的 ID 是唯一的，不依赖于数据库；缺点：UUID 是 128 位的，转换为 Base58 编码后，短链接长度过长，不适合短链接服务；且 UUID 是无序的，插入数据时可能会导致数据库的性能问题；

Snowflake 算法

雪花算法（Snowflake）是 Twitter 开源的分布式 ID 生成算法，可以生成 64 位的唯一 ID，结构如下：

1 位符号位，始终为 0；
41 位时间戳，精确到毫秒级，可以使用 69 年；
10 位机器 ID，可以部署 1024 台机器；
12 位序列号，每毫秒可以生成 4096 个 ID。

Snowflake 算法生成的 ID 是有序的，可以保证 ID 的唯一性，但是需要依赖于时钟，时钟回拨会导致 ID 重复，需要保证时钟的稳定性。同时，Snowflake 算法存在较大的序列号浪费问题，因为每毫秒只能生成 4096 个 ID，即使不使用完，也会浪费掉。

优点：高性能，高可用，生成的 ID 是唯一的；缺点：需要依赖于时钟，时钟回拨或闰秒调整会导致 ID 重复，需要保证时钟的稳定性；存在较大的序列号浪费。

目前也出现了一些基于雪花算法的改进版本，其中时间戳不依赖于系统时钟，而是使用逻辑时钟，服务启动后，每次生成 ID 时，都会从逻辑时钟中获取时间戳，这样可以避免时钟回拨导致 ID 重复的问题，但仍然无法避免较大的序列号浪费问题。

TDDL 序列

TDDL 序列是指在数据库中创建一个序列表，用于存储序列的当前值，然后通过数据库的 CAS 原子操作来获取下一个序列区间，然后在内存中递增序列值，当序列值用尽时，再次获取下一个序列区间。

优点：生成的 ID 是唯一的，避免了数据库自增 ID 的性能瓶颈；同时减小了序列号浪费；
缺点：具有一定的维护成本；

表结构

综上所述，我们可以选择 TDDL 序列算法作为短链接发号器，保证生成的短链接是唯一的，同时 TDDL 序列算法也便于根据 short ID 进行分库分表，适合高并发场景。

可以选择关系型数据库、NoSQL 数据库等维护 TDDL 的序列表，Tiny-URL 首要支持 MySQL 等关系型数据库，未来考虑支持 MongoDB 等 NoSQL 数据库。

MySQL 数据库表结构可参考 sequences.sql。

数据库存储

短链接服务需要存储短链接-长链接映射关系，可以使用关系型数据库、NoSQL 数据库等存储短链接-长链接映射关系，下面将介绍使用 MySQL 数据库存储短链接-长链接映射关系的设计。

tiny_urls 表的几个关键字段：

id：数据库自增 ID，作为主键，保证新插入的 record 是顺序写入的；
long_url：原始的长链接，作为唯一索引，保证长链接是唯一的；
short：短链接 ID，作为唯一索引，保证短链接是唯一的；
deleted_at：删除时间，用于标记短链接是否删除；

对应表结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


create table tiny_urls
(
  id         bigint unsigned auto_increment
    primary key,
  created_at datetime(3)  null,
  updated_at datetime(3)  null,
  deleted_at datetime(3)  null,
  long_url   varchar(500) not null,
  short      bigint       not null,
  constraint idx_tiny_urls_long_url
    unique (long_url),
  constraint idx_tiny_urls_short
    unique (short)
);

create index idx_tiny_urls_deleted_at
  on tiny_urls (deleted_at);

在表结构中，我们对长链接与短链接分别建立了唯一索引，保证了长链接与短链接的唯一性。但我们并没有将 short ID 作为主键，因为 short ID 具有一定的离散性，将其作为主键会影响写入性能。

分布式缓存

短链接服务具有明显的热点数据特征，因此需要使用缓存来提高访问性能，我们可以使用 Redis、Memcached 等缓存服务器，将热点数据缓存到缓存服务器中，以提高访问性能。

分布式缓存需要考虑缓存的一致性、缓存的命中率、缓存的淘汰策略、缓存的预热、缓存的雪崩、缓存的击穿等问题。

缓存命中率：缓存命中率是衡量缓存性能的重要指标，可以通过缓存命中率来评估缓存的有效性，缓存命中率越高，说明缓存的有效性越好，缓存的性能越高。
缓存淘汰策略：缓存淘汰策略是指当缓存空间不足时，如何选择淘汰哪些缓存数据，常见的缓存淘汰策略有：FIFO（先进先出）、LRU（最近最少使用）、LFU（最少使用频率）等。
缓存预热：缓存预热是指在系统启动时，将热点数据加载到缓存中，以提高系统的访问性能，缓存预热可以通过定时任务、异步加载等方式来实现。
缓存雪崩：缓存雪崩是指缓存中的大量数据同时失效，导致大量请求直接访问数据库，从而导致数据库的性能问题，为了避免缓存雪崩，可以采用多级缓存、缓存预热、缓存失效时间随机等方式来避免。
缓存击穿：缓存击穿是指缓存中的某个数据失效，导致大量请求直接访问数据库，从而导致数据库的性能问题，为了避免缓存击穿，可以采用分布式锁、热点数据永不过期等方式来避免。

Tiny URL 使用 Redis 作为缓存服务器，将热点数据缓存到 Redis 中，以提高访问性能。同时将淘汰策略设置为volatile-lfu，根据短链接的访问频率来淘汰缓存数据，以提高缓存的命中率。缓存更新与访问流程如下：

用户发起创建短链接请求，服务端在数据库中成功插入短链接-长链接映射关系；
服务端将短链接-长链接映射关系写入 Redis 缓存中，假设配置的过期时间为 t，服务端会生成 [t,2t] 时间内的随机值，作为缓存的过期时间；
用户访问短链接时，服务端会先从 Redis 缓存中获取短链接-长链接映射关系，如果缓存中不存在，则从数据库中获取，并写入 Redis 缓存中，同时更新缓存的过期时间；

本地缓存

单机 Redis 能够支持 3W～4W QPS 的访问量，同时我们也可以使用 Redis Proxy 来负载均衡，以支撑更大的缓存容量和访问量。当如果某个热点 key 的访问量过大，可能会导致 Redis 的性能问题，此时可以使用本地缓存来缓存热点数据，以提高访问性能。

本地缓存可以使用 bigcache、freecache 等内存缓存库，将热点数据缓存到本地内存中，以提高访问性能。本地缓存的更新与访问流程如下：

用户访问短链接时，服务端会先从本地缓存中获取短链接-长链接映射关系，如果本地缓存中不存在，则从 Redis 缓存中获取，如果 Redis 缓存中不存在，则从数据库中获取；
如果本地缓存中不存在，Redis 缓存或数据库中存在，则更新本地缓存，并设置缓存的过期时间；

本地缓存能够解决热点 Key 问题，单机支撑上万 QPS 的访问量，同时也可以使用本地缓存来缓存最热的 1% 的数据，以降低访问延迟。

本地缓存与分布式缓存作为一个独立的模块，可以定义统一的Cache接口，然后实现RedisCache、LocalCache、混合缓存器等多种具体实现，在不同的场景下选择更合适的缓存器。

1
2
3
4
5
6
7
8
9


// Interface cache interface
type Interface interface {
	// Set the key value to cache
	Set(ctx context.Context, k string, v []byte, ttl time.Duration) error
	// Get the key value from cache
	Get(ctx context.Context, k string) ([]byte, error)
	// Close the cache
	Close() error
}

访问限流

短链接服务需要对短链接的生成与访问进行限流，防止恶意刷短链接，保证服务的稳定性。可以使用令牌桶算法、漏桶算法等限流算法，对短链接的生成与访问进行限流。

令牌桶算法是一种固定容量的令牌桶，按照固定速率往桶中放入令牌，如果桶中令牌已满，则不再放入令牌，当请求到来时，如果桶中有令牌，则允许通过，否则拒绝请求。令牌桶算法能够对单位时间内的请求进行限流，保证服务的稳定性，同时又可以平滑处理突发流量，保证服务的稳定性。

Tiny-URL 采用了 Redis 分布式令牌桶与单机令牌桶两种实现，对短链接的生成与访问进行全局限流，如果 Redis 故障，则会回退到单机令牌桶限流。

限流器的实现通过定义统一的RateLimiter接口，然后实现RedisRateLimiter、LocalRateLimiter、混合限流器等多种具体实现，在不同的场景下选择更合适的限流器。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// RateLimiter is an interface that knows how to limit the rate at which something is processed
// It provides methods to decide how long an item should wait, to stop tracking an item, and to get the number of failures an item has had.
type RateLimiter[T comparable] interface {
	// Take gets an item and gets to decide whether it should run now or not,
	// use this method if you intend to drop / skip events that exceed the rate.
	Take(ctx context.Context, item T) bool
	// When gets an item and gets to decide how long that item should wait,
	// use this method if you wish to wait and slow down in accordance with the rate limit without dropping events.
	When(ctx context.Context, item T) time.Duration
	// Forget indicates that an item is finished being retried. Doesn't matter whether it's for failing
	// or for success, we'll stop tracking it
	Forget(ctx context.Context, item T)
	// Retries returns back how many failures the item has had
	Retries(ctx context.Context, item T) int
}

小结

本章节介绍了 Tiny URL 主要模块的设计思路与技术选型，包括分布式 ID 生成器、数据库存储、缓存系统、访问限流等模块，以及实现这些模块的接口定义与实现。在编码过程中，我们要尽可能将模块的能力抽象出来，定义统一的接口，然后提供多种具体的实现，以便在不同的场景下选择更合适的实现。

部署方案

Tiny URL 服务依赖 MySQL8 与 Redis 作为存储与缓存，Tiny URL 服务本身是无状态的，可以通过 Docker 镜像部署到 Kubernetes 集群中，以提高服务的可用性与可扩展性。

Tiny URL 服务支持读写分离模式，可以将读请求与写请求分发到不同的服务节点，以提高服务的性能。默认情况下，Server 会以读写模式运行，添加启动参数--readonly可以将 Server 设置为只读模式。

快速体验

在 Git Repo 中提供了 docker compose all in one 方案，确保本地已经安装了 Docker 与 Docker Compose，然后执行以下命令：

1

make deploy

终端输出turl service containers start successfully后，说明服务已经启动成功。该模式会部署 MySQL 与 Redis 服务，作为本地存储与缓存服务器。同时会启动两个服务节点，一个用于读写操作，另一个用于只读操作。

读写服务：http://localhost:8080，用于生成短链接、更新远程缓存、更新数据库等；
只读服务：http://localhost:80，只用于访问短链接，不支持生成短链接，生产环境中可以部署多个只读服务节点，用于分流读取请求。

生成短链接

1

curl -X POST http://localhost:8080/api/shorten -H 'Content-Type: application/json' -d '{"long_url": "https://google.com"}'

返回结果：

1

{"short_url":"http://localhost/24rgcX","long_url":"https://google.com","created_at":"2024-07-08T15:06:26.434Z","deleted_at":null,"error":""}

访问短链接

访问短链接 http://localhost/24rgcX，将会被重定向到原始的长链接 https://google.com。

1

curl -L http://localhost/24rgcX

性能测试

上面一小节介绍了如果通过 Docker Compose 部署 Tiny URL 服务，下面将对 Tiny URL 服务进行性能测试，以验证服务的性能表现。

服务器：Apple MacBook Pro 14 M1Pro 2021, 16G Memory 512G SSD

测试数据：获取全球访问量前 10k 的域名，每个域名添加 10 个 API 后缀，共计 100k 条无重复数据。使用 100 个协程并发请求，统计写入耗时。

写入性能测试代码可参考：api_benchmark_test

测试结果如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


Benchmark_Create
api_benchmark_test.go:93: send requests: 4550
api_benchmark_test.go:93: send requests: 10040
api_benchmark_test.go:93: send requests: 15422
api_benchmark_test.go:93: send requests: 20977
api_benchmark_test.go:93: send requests: 26532
api_benchmark_test.go:93: send requests: 32452
api_benchmark_test.go:93: send requests: 38095
api_benchmark_test.go:93: send requests: 42921
api_benchmark_test.go:93: send requests: 47579
api_benchmark_test.go:93: send requests: 52629
api_benchmark_test.go:93: send requests: 58464
api_benchmark_test.go:93: send requests: 63961
api_benchmark_test.go:93: send requests: 69651
api_benchmark_test.go:93: send requests: 75325
api_benchmark_test.go:93: send requests: 80952
api_benchmark_test.go:93: send requests: 87016
api_benchmark_test.go:93: send requests: 92535
api_benchmark_test.go:93: send requests: 98344
api_benchmark_test.go:111: success requests:  100000 costs 18.365219458s

读取性能测试的情况比较复杂，涉及到分布式缓存命中率、本地缓存命中率、数据库读取性能等多个因素，因此需要综合实际应用场景，才能得出准确的性能测试结果。

下面是使用wrk 针对单个短链接的 API 性能测试，即所有流量都命中本地缓存的情况下，测试结果如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


 wrk -t4 -c100 -d30s --latency http://localhost/24rgcY
Running 30s test @ http://localhost/24rgcY
  4 threads and 100 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     2.12ms    1.75ms  63.13ms   98.39%
    Req/Sec    12.18k     1.27k   15.10k    70.17%
  Latency Distribution
     50%    1.96ms
     75%    2.36ms
     90%    2.78ms
     99%    4.56ms
  1454811 requests in 30.01s, 260.83MB read
Requests/sec:  48481.30
Transfer/sec:      8.69MB

综合来看，API 的性能表现良好，理想条件下写操作能够达到 5000+ QPS。在单一测试场景下（命中本地缓存），极限读取性能能够达到 50000 QPS，p99 延迟在 5ms 内。

总结

本文介绍了短链接服务的设计思路与实现，包括需求与预算评估、时序流程、模块设计、部署方案、性能测试等内容。短链接服务是一个典型的高并发、低延迟、高可用的服务，需要考虑到短链接的生成与访问的性能、可用性、可扩展性等方面的问题，以保证服务的稳定性与可靠性。

短链接服务可以足够简单，最核心的接口只有两个：生成短链接与访问短链接，但是在实现过程中，有足够复杂，需要考虑到短链接的生成与访问的性能、可用性、可扩展性等方面的问题，涉及到数据库、缓存、限流、分布式 ID 生成器等多个模块，需要综合考虑这些模块的设计与实现。

目录