Skip to main content

6. Design TinyURL

info

设计一个像 TinyURL 这样的生成 URL 短链的服务 This service will provide short aliases redirecting to long URLs. Similar services: bit.ly, goo.gl, qlink.me, etc.

Interview Signals​

System Design 考察的四方面

  1. Work solution: 能否提出一个可以 work 的方案，是否熟悉常见的场景与设计模式.
  2. Analysis and communication: 与面试官保持交流，对 Storage 与 Bandwidth 的分析.
  3. Tradeoff Pros/Cons: 是否能够提出不同的解决方法并评估不同解决方案的优缺点，根据需求做取舍.
  4. Knowledge Base: 知识面深度和广度.

Overview​

  • Step1. Clarify the requirements
  • Step2. Capacity Estimation
  • Step3. System APIs
  • Step4. Basic System Design and Algorithm
  • Step5. Storage
  • Step6. Scalability

0. Why do we need URL shortening?​

  • URL shortening is used to create shorter aliases for long URLs. 我们用于为长URL创建较短的别名
  • We call these shortened aliases short links. Users are redirected to the original URL when they hit these short links. 短链接将被 301=Redirect Permanently永久重定向到原 URL
  • Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs. 可以节省空间

E.g., 例如，如果我们通过 TinyURL 缩短此这个链接： https://www.educative.io/collection/page/5668639101419520/564905025344512/5668600916475904/ 会得到: http://tinyurl.com/jlg8zpc

缩短的 URL 大小几乎是实际 URL 大小的三分之一。 URL 短链服务用于优化跨设备的链接，追踪特定链接以分析受众和活动情况，以及隐藏附属的原始 URL。

Step 1: Clarify the requirements​

You should always clarify requirements at the beginning of the interview. Be sure to ask questions to find the exact scope of the system that the interviewer has in mind. 你应该在面试开始的时候明确需求。一定要提问，找出面试官心目中的系统的边界

Type 1: Functional Requirement​

  • Given a URL, our service should generate a shorter and unique alias of it. This is called a short link. 短且保证唯一性
  • When users access a short link, our service should redirect them to the original link. 永久重定向
  • Users should optionally be able to pick a custom short link for their URL. 用户可以有自定义的选项
  • Links will expire after a standard default timespan. Users should be able to specify the expiration time. 设置过期时间或者永久不过期。推荐后者，因为如果用户在某个 pdf 或 doc 中使用到了该short link，在很多年以后也可以打开正确的网页

Type 2: Non-Functional Requirement​

  • Availability 可用性
    • The system should be highly available. This is required because, if our service is down, all the URL redirections will start failing. 99.999%
    • Performance: Low latency. <20ms
  • Security 安全性
    • Shortened links should not be guessable (not predictable). 短链接是不可以被预测的

Extended Requirements​

  • Analytics; e.g., how many times a redirection happened?
  • Our service should also be called through REST APIs by other services.

Step 2: Capacity Estimation​

Assumption​

  • 100M DAU
  • Each user: post 0.1 tweet with Tiny URL per day
    • Average Write QPS = 100M * 0.1 / 86400 = 100
    • Peak Write QPS = 100 * 2 = 200
  • Each user: view 1 Tiny URL per day
    • Average Read QPS = 100M * 1 / 86400 = 1k
    • Peak Read QPS = 1k * 2 = 2k
  • Each Tiny URL = 100B
    • 100M * 0.1 * 100KB = 10^9B = 1GB/day
    • 在这个存储需求下，1TB 的硬盘可以用 3 年

Read heavy system 2k QPS: 1 台 SSD 支持的 MySQL 就可以搞定，不需要分布式架构

如果不想计算，可以直接假设 Our system will be read-heavy. There will be lots of redirection requests compared to new URL shortenings. Let’s assume a 100:1 ratio between read and write.

Step3. System APIs​

Once we've finalized the requirements, it's always a good idea to define the system APIs. This should explicitly state what is expected from the system.

APIs​

We can have SOAP or REST APIs to expose the functionality of our service. Following could be the definitions of the APIs for creating and deleting URLs:

  • createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None
    • api_dev_key (string): 注册帐户的 api 开发人员密钥。除其他外，这将用于根据分配的配额限制用户
    • original_url (string): 原始 URL 链接
    • custom_alias (string): 自定义别名
    • user_name (string): 用于编码的用户名
    • expire_date (string):过期时间
    • Returns: (string): A successful insertion returns the shortened URL; otherwise, it returns an error code.
  • deleteURL(api_dev_key, url_key)
    • url_key表示要检索删除的 URL

访问端口设计​

  • GET /<short_url>
    • return a HTTP redirect response
  • POST /data/shorten
    • Data = {url: http://xxxx}
    • Return short url

How do we detect and prevent abuse?

  • A malicious user can put us out of business by consuming all URL keys in the current design. 恶意用户可以通过使用当前设计中的所有 URL 使我们瘫痪
  • To prevent abuse, we can limit users via their api_dev_key. 我们通过用户的api_dev_key来限制滥用
  • Each api_dev_key can be limited to a certain number of URL creations and redirections per some time period (which may be set to a different duration per developer key). 每个api_dev_key可以在某个时间段内限制为一定数量的 URL 创建和重定向

Step4. Basic System Design and Algorithm​

4.1 Base62 Algorithm​

随机生成 ShortURL + 数据库去重 随机生成一个 6 位的 ShortURL，如果没有被用过，就绑定到该 LongURL

  • Pros: 实现简单
  • Cons: 生成短网址的速度随着短网址越来越多变得越来越慢
  • 常用场景: Book a flight/hotel Confirmation Code
public String longToShort(String url) {
  while (true) {
    String shortURL = randomSHortURL();
    if (! database.filter(shortURL=shortURL).exists()) {
      database.create(shortURL=shortURL, longURL=url);
      return shortURL;
    }
  }
}

进制转换 Base62

新浪微博采用的方案

  • Base62
    • 将 6 位的 short url 看做一个 62 进制数 (0-9, a-z, A-Z)
    • 每个 short url 对应到一个整数
    • 该整数对应数据库表的 Primary Key - Sequential ID
  • 6 位可以表示的不同 URL 数量
    • 5 位 = 62^5 = 0.9B = 9 亿
    • 6 位 = 62^6 = 57B = 570 亿
    • 7 位 = 62^7 = 3.5T = 35000 亿
  • Pros: 效率高
  • Cons: 依赖于全局的自增 ID
int shortURLtoID(String shortURL) {
  int id = 0;
  for (int i = 0; i < shortURL.length(); i++) {
    id = id * 62 + toBase62(shortURL.charAt(i));
  }
  return id;
}

String idToShortURL(int id) {
  String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
  String short_url = "";
  while (id > 0) {
    short_url - chars.charAt(id % 62) + short_url;
    id = id / 62;
  }
  while (short_url.length() < 6) {
    short_url = "0" + short_url;
  }
  return short_url;
}

Step5. Storage​

  • SQL
  • NoSQL
  • Cache

是否需要 Sequential ID? 取决于你用什么算法

  • SQL 提供了 auto-increment 的 Sequential ID, like 1,2,3,4...
  • NoSQL 的 ID 并不是 Sequential 因为是分布式架构

5.1 基于随机生成的方法​

需要根据 Long url 查询 Short url，也需要根据 Short url 查询 Long url。并且需要对 shortKey 和 lonhUrl 分别建 Index

shortKeylongUrl
a0B4Lb'www.xxx.com'
Df523p'www.yyy.com'
test12'www.zzz.com'

也可以选用 NoSQL 数据库，但是需要建立两张表(大多数 NoSQL 不支持多重索引 Multi-index) 第一张表: 根据 Long 查询 Short row_key=longURL, column_key=ShortURL, value=null or timestamp

第二张表: 根据 Short 查询 Long row_key=shortURL, column_key=LongURL, value=null or timestamp

Work Solution

5.2 基于进制转化的方法​

因为需要用到 Sequential ID，因此只能选择使用 SQL 型数据库。 表单结构如下，shortURL 可以不存储在表单里，因为可以根据 id 来换算

idlongUrl (index=true)
1"www.baidu.com"
2"www.leetcode.com"
3"www.google.com"

Work Solution

与上面类似，return id

Step6. Scalability​

6.1 Sharding​

  • 什么时候需要多台数据库服务器?
    • Cache 资源不够
    • Write heavy
    • 越来越多的请求无法通过 Cache 满足
  • 增加多台数据库服务器可以优化什么？
    • 解决存不下的问题 - Storage
    • 解决 overload 的问题 - QPS
    • The bottleneck of Tiny URL will be QPS

Sharding 方案

  • Vertical Sharding
    • 将多张数据表分别分配各多台机器
    • Tiny URL 不适用，只有 two columns 无法再拆分
  • Horizontal Sharding
    • 如果用 ID / ShortURL 做 Sharing key
      • 做 long to short 查询的时候，只能广播给 N 台数据库查询
      • 为什么需要查 Long to short? 创建的时候避免重复创建
      • 如果不需要避免重复创建，则这样可行
    • 如果 Long Url 做 Sharding key
      • 绝大部分的 request 都是查询 short to long
      • 做 short to long 查询的时候，只能广播给 N 台数据库查询

选 Sharding Key

  • 如果一个 Long 可以对应多个 Short:
    • 使用 Cache 缓存所有的 Long to Short
    • 在为一个 Long Url 创建 Short Url 的时候，如果 cache miss 则去直接创建新的 short url 即可
  • 如果一个 Long 只能对应一个 Short:
    • 如果使用随机生成 Short Url 的算法
      • 两张表单，一张存储 Long to Short，一张存储 Short to Long
      • 每个映射关系存两份，则可以同时支持 long to short 和 short to long 的查询
    • 如果使用 base62 的进制转换法
      • 这里有一个很严重的问题是，多台机器之间如何维护一个全局自增的 ID？
      • 一般关系型数据库只支持在一台机器上实现这台机器上全局自增的 ID

全局 Auto-increment ID

  • 如何获得在 N 台服务器中全局共享的一个自增 ID 是难点
  • 一种解决办法是，专门用一台数据库来做自增 ID 服务
    • 该数据库不存储真实数据，也不负责其他查询
    • 为了避免单点失效 (Single Point Failure) 可能需要多台数据库
  • 另外一种解决办法是用 Zookeeper
    • 但是使用全局自增 ID 的方法并不是解决 Tiny URL 的最佳方法
    • 不推荐

基于 base62 的方法下的 Sharding key 策略

  • 使用 Hash(long_url) % 62 作为 Sharding key. 并将 Hash(long_url) % 62 直接放到 short url 里
    • 如果原来的 short key 是 AB1234 的话，现在的 short key 是
      • hash(long_url) % 62 + AB1234
      • 如果 hash(long_url) % 62 = 0 那就是 0AB1234
  • 这样我们就可以同时通过 short_url 和 long_url 得到 Sharding Key
  • 缺点：数据库的机器数目不能超过 62

Step7. Deep Dive​

7.1 How can we ensure short urls are unique?​

如何保证短网址的唯一性?

One way to guarantee we don't have collisions is to simply increment a counter for each new url. We can then take the output of the counter and encode it using base62 encoding to ensure it's a compacted representation.

  • 保证不发生冲突的一种方法是简单地为每个新 URL 增加一个计数器。
  • 我们获取计数器的输出，并使用 base62 编码对其进行编码。

Redis is particularly well-suited for managing this counter because it's single-threaded and supports atomic operations. Being single-threaded means Redis processes one command at a time, eliminating race conditions. Its INCR command is atomic, meaning the increment operation is guaranteed to execute completely without interference from other operations. This is crucial for our counter - we need absolute certainty that each URL gets a unique number, with no duplicates or gaps.

  • Redis 特别适合管理这个计数器，因为它是单线程的，并且支持原子操作。
  • 单线程意味着 Redis 一次只处理一个命令，从而消除了竞争条件。它的 INCR 命令是原子的，这意味着增量操作可以保证完全执行，而不会受到其他操作的干扰。
  • 这对于我们的计数器至关重要——我们需要绝对确保每个 URL 都获得唯一的编号，并且没有重复或空白。

Each counter value is unique, eliminating the risk of collisions without the need for additional checks. Incrementing a counter and encoding it is computationally efficient, supporting high throughput. With proper counter management, the system can scale horizontally to handle massive numbers of URLs. The short code can be easily decoded back to the original ID if needed, aiding in database lookups.

  • 每个计数器值都是唯一的。
  • 增加计数器并进行编码计算效率高，支持高吞吐量。
  • 通过适当的计数器管理，系统可以水平扩展以处理大量 URL。如有需要，短代码可以轻松解码回原始 ID，从而有助于数据库查找。
挑战1 - 全局计数器的一致性与可用性
  • 在分布式环境下，所有应用实例都需要依赖同一个全局计数器来生成短码。如果计数器所在的节点宕机、主从切换、网络分区或者复制延迟，就可能出现 重复 ID 或 服务停滞的情况。
  • 这会直接导致短链接冲突，或者在高并发场景下吞吐量骤降。
  • 难点 -> 如何保证计数器严格单调递增，同时还能在故障或扩展时保持高可用。
挑战2 - 计数器的性能瓶颈与热点问题
  • 随着系统规模扩大，一个单点的 Redis INCR 操作会成为热点。所有请求都要访问同一个计数键，容易造成 写入瓶颈，并带来延迟抖动。
  • 在高 QPS 场景 (如每秒数十万请求)下，这个单点性能限制会成为系统扩展的最大障碍。
  • 难点 -> 如何在保证唯一性的前提下，支持水平扩展，避免全局热点。

tip

Solution1 - 单写者 ID 发号器 KGS+ 租约与围栏 etcd/ZK

  • KGS (Key Generation Service 发号器)
    • 唯一能“加一、发号”的小服务。业务服务不能自己加号，必须问它要。
  • 租约 (Lease)
    • 像停车位的“临时使用权”。拿到租约的一台 KGS 才能对外发号
    • 租约有 TTL (例如 10 秒 )，要不断 续约 (心跳 ) 才能保持有效。
  • 围栏 (Fencing) 令牌
    • 一串 单调递增 的“代号/世代号 (epoch )”。每次新的主 KGS 上任，都会拿到更大的令牌。所有关键写操作都要携带并校验“我手里这个令牌是不是最新的”。这样即使旧主没死透，也会因为令牌小而被拒绝 (防脑裂 )。
  • etcd/ZK 用来 发放租约 + 生成围栏令牌 + 做主备选举。
  • Redis/DB 用来 存计数器 或 持久化发号状态。

核心流程

  • 1.选主与保活
    • 多台 KGS 同时尝试在 etcd/ZK 里 CAS 抢“/kgs/leader”这把锁：
      • 成功者成为主，拿到一个 lease_id 和一个 fencing_token (epoch ) (可用 etcd 的 revision 或自增版本号实现 )。
      • 失败者当备，只监听主的状态变化。
    • 主 KGS 每隔 N 秒 (如 3 秒 )向 etcd 续租 (把 TTL 继续延长 )。
    • 心跳失败或租约过期：主身份立刻失效 → 备机开始抢主。新的主会拿到更大的 fencing_token。
  • 2. 区间批量发号 - 类似美团号段模式
    • Server 向 主 KGS 请求一段 ID 区间 (比如 10,000 个号 )。
    • 主 KGS 用一个 原子操作 从 Redis/DB 一次性把计数器加 10,000，得到:
      • range_start = old_counter + 1
      • range_end = old_counter + 10,000
    • 主 KGS 把 [range_start, range_end] 连同当前 fencing_token 一起返回给 Server。
    • Server 把这段区间保存在本地内存池里，本地递增 使用 (关键路径不打远程 )。
  • 续约 & 故障切换 (切主)
    • 续约/心跳: 主 KGS 不断向 etcd 续租。
    • 切主 (主挂了或断网): 旧主租约过期，备机抢到主，拿到更大的 fencing_token。
    • 旧主即使“死而复活”，它手里的令牌更小，后续任何关键写都要带令牌 → 会被拒绝 (见“围栏校验” )。

tip

Solution2 - Hi/Lo 区间批量发号 + 本地内存池

一次性向 Redis 批量要一段 ID 号码段，然后在本地自己发。“本地内存池” = 你拿到的这一段号，直接存进内存，像一个数组。 取号的时候，只要做一次 原子自增（CAS 操作），非常快。

  • 水位线策略
    • 本地池里的号码快用完（比如剩 20%）-> 异步去 Redis 申请下一批
    • 高峰期 → 批量调大（比如 1 万 → 10 万）
    • 低谷期 → 批量调小，减少浪费
  • 幂等键 + 两阶段 + 墓碑化: 这是防止“失败重试导致重复短码”的机制。
    • 幂等键
      • 每个写请求带一个唯一 ID req_id
      • 如果请求重试，系统能识别这是同一个请求 → 返回同一个短码，而不是生成新短码。
    • 两阶段
      • 1.预留号：先把分配到的 ID 标记为“已占用”。
      • 2.落库映射：再写入数据库，完成短链和长链的绑定。
    • 墓碑化
      • 如果第 2 步失败了，这个 ID 也不能再回收利用。要打个标记（墓碑），保证不会以后又分配给别人。
      • 👉 这样保证了 “只会缺号，不会重号”。

7.2 How can we ensure that redirects are fast?​

我们如何确保重定向速度快?

7.2.1 Caching 使用缓存​

  • use Cache, Cache Aside
  • Cache 里需要存两类数据:
    • long to short (生成新 short url 时需要)
    • short to long (查询 short url 时需要)

7.2.2 Content Delivery Networks (CDNs) and Edge Computing​

重定向慢的本质原因是 “请求链路长” 和 “处理节点远” -> 传统模式下，用户点击短链接后，请求需跨地域到达远端的 “源服务器”，查询短码→长 URL 的映射后再返回重定向响应，往返延迟高。

CDN + 边缘计算的设计核心是 “将重定向的‘决策逻辑’和‘数据’推到离用户最近的地方”，从根源上缩短链路。

基础架构: CDN 节点作为 前端接入层
  • 域名解析层:
    • 将短链接的域名 (如 t.cn)通过 DNS 解析指向 CDN 的全球分布式接入点 PoP，Points of Presence
    • 用户的请求会自动路由到地理上最近的 PoP 节点 (比如北京用户连接北京 CDN 节点，纽约用户连接纽约 CDN 节点)。
  • 缓存层部署:
    • CDN 节点会缓存 “高频访问的短码→长 URL 映射关系”。
    • 这些映射数据来自源服务器 (首次请求未命中时拉取，或源服务器主动同步更新)。
核心链路: 边缘计算执行 重定向决策
  • 边缘函数部署：
    • 通过 Cloudflare Workers、AWS Lambda@Edge 等平台，将 “重定向核心逻辑” (如 查询缓存→命中则返回 302 重定向、未命中则轻量处理)打包成无服务器函数，部署在 CDN 的 PoP 节点上。
  • 请求处理流程 - 用户点击短链接后
    • 用户请求到达最近的 CDN PoP 节点；
    • 边缘函数先查询本地 CDN 缓存，看是否有该短码对应的长 URL；
    • 缓存命中 -> 直接在 CDN 节点返回 302 重定向响应，请求不触达源服务器，延迟极低 (通常几十毫秒)；
    • 缓存未命中 -> 边缘函数可选择性地 “轻量回源” (向源服务器查询映射)，拿到结果后返回重定向，并将映射缓存到 CDN 节点 (供后续请求复用)。

  • Bottleneck 是 Web Server 与 Shared DB 之间的通信速度
  • 如果大量请求都需要查询 Shared DB，速度会很慢

7.3 How can we scale to support 1B shortened urls and 100M DAU?​

我们如何扩展以支持 10 亿个缩短的 URL 和 1 亿个 DAU？

Write Flow 高吞吐
  • App -> Write API
    • 校验输入 URL、风控 (可异步)。
  • 本地发号 (来自本地内存池)
    • 用之前从 Redis 取到的 [start,end] 区间做本地自增；低水位异步续租 (再向 Redis 申请新批次)。
  • 持久化到DB
    • 把 {short_id, long_url, ttl/owner/flags...} UPSERT 到 DB
    • 强一致写 -> 幂等键用 req_id 或 (user_id,url_hash))
  • 异步出站 Outbox/Event
    • 写成功后发布事件 (更新搜索、统计、缓存等)。

Redis 侧只在“续租批次”时被访问：一次 INCRBY(batch_size) + 返回 [start,end]。 用 Lua + fencing 校验 (见前文“围栏令牌”)确保不会出现旧主/并发导致的区间重叠。

tip

短链接系统 风控事件

  • 目标 URL 安全性 (内容/信誉)
    • ((恶意/钓鱼/恶意软件域名))
      • 信号：Google Safe Browsing/URLhaus/PhishTank 命中；恶意词典 (login-verify、wallet-recovery 等)；证书异常。
      • 处置：拦截或隔离 (创建成功但跳转前插入安全警示页)。
    • 新生/低信誉域名 (域名年龄短、无 MX/SPF/DMARC)
      • 信号：WHOIS 创建 < 7/30 天；无常见 DNS 记录；ASN 信誉低。
      • 处置：限速 + 人机校验，可降级到隔离。
    • 成人/涉政/赌博等黑词
      • 信号：URL/路径/查询参数命中词库；落地页标题抽样命中 (异步抓取)。
      • 处置：隔离或拦截 (按合规策略)。
  • 行为与速率 (反滥用)
    • 创建速率异常
      • 信号：单账号/单 IP/单设备在窗口内创建数超阈值；成功/失败比异常；深夜突增。
      • 处置：动态限流、滑动验证码、冻结 5-30 分钟。
Read Flow 高吞吐
  • 边缘缓存优先
    • CDN/边缘 KV (Cloudflare KV/Redis Edge/Akamai EdgeKV)；热点短链命中率高。
  • 多级缓存
    • L1：进程内 LRU (几万条，TTL 秒级)
    • L2：集群 Redis (分片)
    • Miss 再打 读库/只读副本 (或 LSM 类分布式存储，如 DynamoDB/Cassandra)。
  • 防击穿/穿透
    • 对不存在短链做阴性缓存 (短 TTL)，配合限流。
  • 301 Moved Permanently (永久重定向)
    • 表示这个短链以后一直指向同一个长链。浏览器和搜索引擎会长期缓存这个关系。
    • 适合：那种“绝对不会变”的短链，比如公司的主页短链。
  • 302 Found (临时重定向)
    • 表示短链当前指向某个长链，但未来可能会变。浏览器/CDN通常会短期缓存，但还是会经常回来问。
    • 适合：大多数业务短链 (营销活动、内容链接等)，因为可能随时更换或失效。
    • 更灵活：万一需要换目标，不会被浏览器/搜索引擎死记住。
    • CDN 也能缓存 302 响应 (可配置 TTL)，性能上没问题。
    • 避免 SEO 被污染 (301 会把权重转给目标页面)
tip

防击穿/穿透 - 阴性缓存

  • 背景
    • 短链服务里，用户点一个短码 -> 系统查数据库，看看有没有对应的长链。
    • 如果这个短码根本不存在，就会查库一次。攻击者或爬虫可能疯狂请求随机短码，大部分都不存在，就会导致所有请求都打到数据库，把库压垮。
  • 解决办法：阴性缓存 (Negative Cache)
    • 当发现某个短码不存在时，不要每次都去查库，可以把“这个短码不存在”的结果也放到缓存里。
    • 给它设置一个 短 TTL (比如 30 秒/1 分钟)，这样短时间内相同的短码再查，就直接命中缓存，避免反复查库。
    • 配合 限流：如果发现某个 IP/用户疯狂请求不存在的短码，可以限速或封禁，进一步保护系统。