一致性哈希算法&设计短网址系统

一、短网址系统的需求分析

短网址服务（URL Shortener）将冗长的原始URL映射为短小精悍的短链，典型场景包括：Twitter的140字限制（现为280字）下分享链接、短信营销中节省字符、生成二维码时减少数据密度以降低识别难度。

核心功能需求：给定一个长URL，生成一个全局唯一的短链。用户访问短链时，HTTP 302重定向到原始长URL。可选功能：自定义短链别名、链接有效期设置、访问统计（点击次数、来源、地域分布）。

非功能需求：短链生成延迟低于100毫秒，重定向延迟低于50毫秒，系统可用性99.99%，支持日均十亿级别的短链生成。

容量估算：假设每日生成一亿条短链，年均365亿条。短链的读取远多于写入（假设读写比100:1），即每日读取量约100亿次，平均读QPS = 100亿 / 86400 ≈ 115740，峰值约50万QPS。写QPS = 1亿 / 86400 ≈ 1157。存储：每条短链映射记录约500字节（短链、长URL、创建时间、过期时间等），一年约18.25TB。

短网址系统的扩展需求分析

除了核心的短链生成和重定向，企业级短网址系统通常还需要：

自定义别名：用户指定自定义短链后缀（如t.cn/my-brand），需要校验唯一性
域名管理：支持多个自定义域名（企业用户用自己的域名）
链接有效期：支持设置过期时间，过期后自动失效
访问控制：支持密码保护、地区限制（如仅中国可用）、设备限制
A/B测试：同一短链根据条件跳转到不同的目标URL
UTM参数自动追加：自动在目标URL后追加追踪参数
API限流：免费用户100次/分钟，付费用户10000次/分钟

二、短链的生成算法

短链的核心是将任意长度URL映射为一个短的标识符（通常5到8个字符）。三种主流方案：

方案一：哈希函数 + Base62编码。对原始URL计算哈希值（如MD5、SHA-1或MurmurHash），取哈希值的前N个字节，转换为Base62编码（字符集为[0-9, a-z, A-Z]，共62个字符）。MD5产生128位哈希值，取其前6个字节（48位）进行Base62编码，得到约8个字符的短链。哈希方案的问题是哈希冲突——不同URL可能产生相同的哈希值。处理冲突的方式是：如果生成的短链已存在（查数据库），则在原始URL后追加预定义的字符串（如递增的计数器）重新计算哈希，直到生成唯一的短链。

方案二：分布式ID生成器 + Base62编码。使用Snowflake或数据库自增ID生成全局唯一的整数ID，然后将该整数转换为Base62编码。例如，ID=12345，Base62编码后为3dF。这种方案天然避免了冲突问题（ID唯一则短链唯一），但短链长度随ID增长——ID较小时短链很短，ID达到万亿级别时短链变长。可以通过固定短链长度来保证用户体验一致性：所有短链固定为7位，不足7位的前面补0（Base62的0即字符0），超出范围的通过循环使用或定期回收过期短链来处理。

方案三：预生成短链池。提前批量生成一批短链存入内存池，用户请求时直接从池中取出一个分配。这消除了生成短链的实时开销，但也引入了额外的复杂度（池耗尽时的补充策略、池中短链的持久化状态管理等）。

工业界（如Bitly、TinyURL）通常使用方案一或方案二。方案二（发号器）因其简单可靠而被广泛推荐。

Base62编码的示例代码（Java）：

public class Base62 {
    private static final String CHARS = 
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
    public static String encode(long num) {
        if (num == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.append(CHARS.charAt((int) (num % 62)));
            num /= 62;
        }
        return sb.reverse().toString();
    }
    
    public static long decode(String str) {
        long result = 0;
        for (char c : str.toCharArray()) {
            result = result * 62 + CHARS.indexOf(c);
        }
        return result;
    }
}

以Base62编码8位为例，可表示62^8 ≈ 2.18 × 10^14条短链，足够使用数百年。

发号器方案中的ID预分配与批量获取

发号器方案的核心瓶颈在于每次生成短链都需要获取一个全局唯一ID。如果每次都访问一个集中式的ID生成服务（如Redis INCR），Redis会成为性能瓶颈。优化策略：批量预取（Batch Pre-allocation）。每个应用服务器节点向ID生成服务一次性申请一个ID号段（如1000个ID），在本地内存中分配，消耗完后再申请下一批。这样将ID生成的Redis调用频率从每请求一次降低到每1000请求一次。

向ID生成服务申请号段: "请给我1000个ID"
ID生成服务返回: start_id = 1000000, end_id = 1000999
应用服务器本地使用: 1000000 → 转换为Base62短链 → 分配给用户
                   1000001 → 转换为Base62短链 → 分配给用户
                   ...
                   1000999 → 转换为Base62短链 → 分配给用户
                   号段耗尽, 再次申请: start_id = 1001000, ...

哈希方案中的冲突处理算法

function generateShortCode(longUrl):
    counter = 0
    while true:
        seed = longUrl + (counter == 0 ? "" : toString(counter))
        hash = murmurHash128(seed)
        shortCode = base62Encode(first6Bytes(hash))
        if not existsInDB(shortCode):
            return shortCode
        counter++

平均冲突次数：对于长度为k的Base62编码（k通常取7到8），编码空间大小为62^k。当已生成N个短链时，新短链发生冲突的概率约为 N / 62^k。以7位短链为例，62^7 ≈ 3.5万亿。即使已生成3650亿条短链（10年的量），冲突概率仅约0.01%。因此哈希方案的冲突重试次数极低（绝大多数情况一次成功）。

三、系统架构总览

短网址系统的高层架构包含以下组件：

用户服务：处理用户的注册、登录和API Key管理。用户使用短网址服务前需要注册，获得API Key用于请求限流和配额管理。

短链生成服务：核心业务逻辑。接收长URL和可选参数（自定义别名、有效期），调用ID生成器获取全局唯一ID，Base62编码为短链，将映射关系写入存储层，返回完整的短链URL。

重定向服务：接收短链访问请求，根据短链查询原始URL，返回HTTP 302（临时重定向）或301（永久重定向）响应。由于读取量极大，重定向服务高度依赖缓存。如果短链已过期或不存在，返回404。

分析服务：记录每次短链访问的元数据（时间戳、来源IP、User-Agent、Referer），异步写入数据分析流水线（Kafka → Flink/Spark Streaming → ClickHouse），提供实时和离线访问统计。

缓存层：使用Redis缓存热门短链的映射关系，减少数据库读压力。缓存采用LRU/TTL双重淘汰策略。

存储层：MySQL分片存储短链映射关系，分片键使用短链的哈希值（以保证均匀分布）。

系统架构的ASCII示意图

用户                 CDN边缘节点               核心服务                  存储层
┌──────┐          ┌─────────────┐       ┌──────────────┐       ┌──────────────┐
│      │──短链──▶│  CDN Edge   │───▶  │  重定向服务   │──▶   │ Redis Cluster│
│ 用户 │         │ (边缘重定向) │       │              │       │ (短链缓存)    │
│      │◀─302───│             │       │ 1.查缓存     │       └──────┬───────┘
└──────┘         └─────────────┘       │ 2.查MySQL    │              │
                                        │ 3.返回302    │       ┌──────▼───────┐
┌──────┐                               │              │       │ MySQL分片集群 │
│      │──创建短链──▶                  │ 短链生成服务  │──▶   │ (短链映射)    │
│API调用│                              │              │       └──────────────┘
│      │◀──短链────                    │ ID生成+Base62 │
└──────┘                               └──────┬───────┘
                                               │
                                        ┌──────▼───────┐
                                        │    Kafka     │
                                        │ (点击事件)    │
                                        └──────┬───────┘
                                               │
                                        ┌──────▼───────┐
                                        │ Flink/Spark  │
                                        │ (实时聚合)    │
                                        └──────┬───────┘
                                               │
                                        ┌──────▼───────┐
                                        │  ClickHouse  │
                                        │  (分析存储)   │
                                        └──────────────┘

四、短链读取与重定向流程

用户点击短链 https://t.cn/abc123 的完整处理流程：

第一步，请求到达DNS解析→CDN→负载均衡→API网关。如果CDN层已缓存了该短链的重定向规则（通过Edge Workers或边缘函数），直接在CDN节点返回302，延迟仅为几毫秒。

第二步，API网关查询本地缓存（如Caffeine），如果有命中，直接返回302。本地缓存命中率通常在80%以上（热门短链占大部分访问量）。

第三步，本地缓存未命中时，查询Redis分布式缓存。Redis中key为短链标识符abc123，value为JSON格式的{long_url, expires_at, status}。如果命中，返回长URL，同时写入本地缓存。

第四步，Redis未命中时，查询MySQL。找到记录后，回写Redis缓存，返回302。如果记录不存在或已过期，返回404并设置较短的负缓存（防止缓存穿透攻击）。

302 vs 301的选择：302表示临时重定向，浏览器不会缓存重定向结果，每次都会再次请求短链服务。这对于需要统计点击次数的场景是必需的。301表示永久重定向，浏览器会缓存重定向结果，下次点击直接跳转，不再经过短链服务器，适合不需要统计的场景（如静态资源）。

CDN边缘重定向的实现

Cloudflare Workers / AWS Lambda@Edge / Akamai EdgeWorkers 可以在CDN边缘节点执行代码逻辑。短网址系统利用这个能力，在CDN边缘节点部署重定向逻辑：

// Cloudflare Worker 示例
addEventListener('fetch', event => {
  event.respondWith(handleRequest(event.request))
})

async function handleRequest(request) {
  const url = new URL(request.url)
  const shortCode = url.pathname.slice(1)  // 提取 /abc123
  
  // 尝试从 Edge KV (边缘键值存储) 读取
  const longUrl = await EDGE_KV.get(shortCode)
  if (longUrl) {
    // 同时异步记录点击事件（非阻塞）
    event.waitUntil(logClick(shortCode, request))
    return Response.redirect(longUrl, 302)
  }
  
  // Edge未命中，回源到核心服务
  return fetch(request)
}

边缘KV存储（如Cloudflare Workers KV）以最终一致性模型在全球200+边缘节点同步数据（通常60秒内全球一致）。对于热门短链（通过分析服务识别），主动将映射关系写入边缘KV。这样80%以上的读取直接在CDN边缘节点完成，延迟不足10毫秒。

重定向的容错与降级

当Redis和MySQL都无法访问时（极端的级联故障），重定向服务处于降级状态。此时有两种选择：

使用本地磁盘上的持久化缓存（如RocksDB存储最近被访问的热门短链映射）提供有限的降级服务
直接返回503 Service Unavailable

优先使用方案1——提前通过异步任务将热门短链（访问量Top 100万）的映射关系同步到每个重定向服务节点的本地RocksDB中作为兜底。

五、一致性哈希算法详解

当单台MySQL无法承载短链数据时，需要分库分表。传统的取模分片（hash(key) % N）在N发生变化时（扩容或缩容），几乎所有数据都需要重新分配。一致性哈希（Consistent Hashing）优雅地解决了这个问题。

哈希环：一致性哈希将整个哈希值空间组织成一个环，取值在[0, 2^32 - 1]之间。将每个存储节点通过哈希函数映射到环上的某个点。当需要查找某个key属于哪个节点时，计算key的哈希值，在环上顺时针找到第一个节点，该节点即为key的归属节点。

节点的添加与删除：假设有4个节点均匀分布在哈希环上。当添加第5个节点时，只有哈希值落在新节点逆时针方向直到前一个节点之间的key需要迁移，其他key不受影响。这部分数据量约为总量的1/4（理想情况下）。同理，删除节点时，只需将该节点上的数据迁移到顺时针的下一个节点。这与取模分片需要全量迁移形成鲜明对比。

虚拟节点：实际环境中，节点数量少（如3到5台），哈希函数无法保证节点在环上均匀分布，可能导致数据倾斜——某些节点承载了远超平均值的数据量。虚拟节点（Virtual Node）解决这个问题：每个物理节点在哈希环上映射为多个虚拟节点（如150个）。例如，节点A映射为A#1, A#2, ..., A#150，节点B映射为B#1, B#2, ..., B#150。物理节点数量越多，虚拟节点比例可相应降低。当虚拟节点数量足够大时（如总虚拟节点数超过1000），数据分布趋于均匀，标准方差可以控制在10%以内。

一致性哈希的Java实现示例：

public class ConsistentHashing {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int virtualNodeCount;
    private final HashFunction hash;
    
    public ConsistentHashing(int virtualNodeCount, List<String> physicalNodes) {
        this.virtualNodeCount = virtualNodeCount;
        this.hash = key -> { /* MurmurHash3 或其他哈希函数 */ };
        for (String node : physicalNodes) {
            addNode(node);
        }
    }
    
    public void addNode(String node) {
        for (int i = 0; i < virtualNodeCount; i++) {
            int hashVal = hash.hash(node + "#" + i);
            ring.put(hashVal, node);
        }
    }
    
    public void removeNode(String node) {
        for (int i = 0; i < virtualNodeCount; i++) {
            int hashVal = hash.hash(node + "#" + i);
            ring.remove(hashVal);
        }
    }
    
    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        int hashVal = hash.hash(key);
        Map.Entry<Integer, String> entry = ring.ceilingEntry(hashVal);
        if (entry == null) {
            entry = ring.firstEntry(); // 超出环最大值，回到环起点
        }
        return entry.getValue();
    }
}

TreeMap的ceilingEntry方法在O(log N)时间内找到环上的下一个节点，其中N为虚拟节点总数。如果N=1500（10个物理节点 × 150个虚拟节点），每次查找仅需约11次比较。

一致性哈希的数学分析

设哈希值空间大小为H（通常H=2^32）。有N个物理节点，每个节点M个虚拟节点。数据在虚拟节点之间均匀分布的概率可以通过Chernoff Bound分析：

对于任意key，它落在某个物理节点上的概率为1/N（虚拟节点均匀分布前提下）。任意物理节点承载的数据量X的期望E[X] = DataSize/N。根据Chernoff Bound：

P(|X - E[X]| > ε*E[X]) ≤ 2 * exp(-ε² * E[X] / 3)

当虚拟节点数M足够大时（如M=150, N=5，总虚拟节点750个），实际分布与均匀分布的偏差可以控制在5%以内。

一致性哈希的数据迁移量

添加节点的数据迁移量：在均匀分布条件下，添加第K个节点时，需要迁移的数据量约占总量的1/K。例如从4个节点扩展到5个节点，迁移量约为总量的1/5 = 20%。对比取模分片（从4到5需要迁移约4/5 = 80%的数据），一致性哈希的迁移成本降低了4倍。

删除节点的数据迁移量：同样条件下，删除一个节点（从5到4），迁移量约为总量的1/5 = 20%，数据迁移到顺时针的下一个物理节点。

一致性哈希的变体：Jump Consistent Hash

Google在2014年提出了Jump Consistent Hash算法，提供了与一致性哈希相同的重新映射最小化特性，但实现更加简洁。核心公式：

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return (int32_t)b;
}

该算法的时间复杂度为O(log N)，不需要存储虚拟节点的数据结构，内存开销为O(1)。但其限制是只能用于bucket编号为连续整数（0到N-1）的场景，且不支持自定义的节点权重。适用于简单的分布式缓存路由，不适合需要根据节点容量加权的场景。

六、短链系统的存储设计

短链映射表的核心字段：

CREATE TABLE url_mapping (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_code VARCHAR(10) NOT NULL,
    long_url TEXT NOT NULL,
    user_id BIGINT,
    created_at DATETIME NOT NULL,
    expires_at DATETIME,
    status TINYINT DEFAULT 1,  -- 1:有效 2:过期 3:删除
    UNIQUE INDEX idx_short_code (short_code)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

分片策略：以short_code为分片键，使用一致性哈希分配到1024个分片（每个分片是一个MySQL实例或数据库）。短链只有6到8个字符，直接用其Base62值取模也可以实现较均匀的分布。由于短链的读取远多于写入，每个分片前面都部署Redis缓存，热点短链被缓存在内存中。

缓存设计：Redis Cluster的key为url:{short_code}，value为长URL，TTL设置为7天（匹配热门短链的平均生命周期）。对于超高热度短链（如某明星在Twitter分享的链接），可能单分片的Redis也不够，可以使用多级缓存：在API网关层增加本地缓存（Guava/Caffeine），配置短TTL（如5分钟），过滤掉重复读取。

短链映射的分片路由算法

function getShard(shortCode):
    hashValue = hash(shortCode)  // 如 MurmurHash3
    shardIndex = consistentHashing.getNode(hashValue)
    return shardIndex

function getRedisKey(shortCode):
    shardIndex = getShard(shortCode)
    return "url:" + shardIndex + ":" + shortCode

在一致性哈希的分片方案中，短链的分片归属由其哈希值决定。当扩容时（添加新的MySQL分片），仅一致性哈希环上相邻节点间的数据需要迁移。迁移过程：扫描源分片中的所有短链记录，重新计算其在新哈希环上的归属，将需要迁移的记录导出到增量数据文件，在目标分片上导入。迁移期间，源分片保留数据，正常提供服务；导入完成后，逐步将读取流量切换到目标分片（通过修改一致性哈希配置）。

七、分析系统的设计

点击分析是短网址服务的重要附加值。每次短链被访问时，重定向服务异步发送一条事件到Kafka，包含：短链标识符、访问时间戳、来源IP、User-Agent、Referer HTTP头、地理位置（根据IP解析）。

数据分析流水线：Kafka → Flink实时聚合 → ClickHouse存储 → Grafana可视化。Flink作业执行窗口聚合（如每分钟、每小时统计每个短链的点击量、UV、国家/地区分布）。ClickHouse列式存储适合OLAP查询，支持秒级响应的聚合分析。用户可以在Dashboard上查看每个短链的实时访问数据。

为避免分析流量影响核心重定向路径，分析事件的发送必须是异步且非阻塞的——重定向服务将事件写入本地内存缓冲区，后台线程批量发送到Kafka。即使Kafka暂时不可用，也不影响重定向的正常工作（事件会丢失，但这是可接受的权衡）。

实时分析的具体实现

Flink作业的窗口聚合逻辑：

数据源: Kafka topic "url_click_events"
  → 解析事件 (short_code, timestamp, ip, ua, referer, geo)
  → KeyBy short_code
  → Tumbling Window (1分钟)
  → 聚合:
      count: COUNT(*)
      unique_ips: APPROX_COUNT_DISTINCT(ip)  -- HyperLogLog
      geo_distribution: MAP<country, count>
      referer_top: TOP_K(referer, 10)
  → Sink: ClickHouse表 url_clicks_minute

使用HyperLogLog进行近似UV去重（在1-2%误差范围内大幅节省内存）。一个拥有100万条短链的服务，每分钟的聚合状态内存约需几百MB。

八、限流与安全

短网址服务需要防范恶意滥用（如用短链传播钓鱼链接、短链轰炸等）。安全措施包括：

用户级别限流：每个API Key每分钟最多生成100个短链，超出返回429。限流实现在API网关层，使用Redis滑动窗口计数器。

恶意链接检测：对长URL进行安全检查。接入第三方URL安全API（如Google Safe Browsing）或者自建黑名单，检查是否为已知的钓鱼/恶意网站。如果判定为恶意URL，拒绝生成短链。

短链预览：对于某些敏感场景，可以在重定向前提供一个中间页面，显示目标URL的摘要信息，让用户确认后再跳转。Facebook和Twitter都采用此策略。

访问频率限制：对单个短链的访问频率进行限制（如每IP每分钟最多10次），防止被用作CC攻击的跳板。

内容安全的分层检测

第一层: 域名黑白名单 (O(1) 内存查询)
  - 白名单: 知名域名 (apple.com, google.com, github.com ...)
  - 黑名单: 已知钓鱼域名 (通过PhishTank/Google Safe Browsing同步)
  
第二层: URL特征检测 (基于规则, 毫秒级)
  - URL长度异常 (>2000字符)
  - 包含可疑关键词
  - IP地址作为域名 (如 http://192.168.1.1/...)
  - 多个重定向链 (短链指向另一个短链)
  
第三层: 异步深度检测 (基于机器学习, 秒级)
  - URL内容抓取与页面分析
  - 图片/文件病毒扫描
  - 行为分析 (生成的短链是否被密集点击等)
  
如果第三层检测结果为恶意:
  - 将短链标记为"已封禁" (status=3)
  - 重定向时显示安全警告页面
  - 通知用户 (邮件/站内信)

九、一致性哈希在P2P网络与分布式存储中的广泛应用

一致性哈希不仅用于数据库分片和缓存路由，它几乎是所有去中心化分布式系统的基石。

Chord协议与DHT（分布式哈希表）

Chord是MIT在2001年提出的一种P2P查找协议，是一致性哈希在P2P网络中的直接应用。在Chord环中，每个节点和每个数据项都通过一致性哈希映射到环上的一个位置。数据项存储在其后继节点（顺时针第一个节点）上。

Chord的创新在于其Finger Table（路由表）：

每个节点维护O(log N)个Finger，指向环上距离2^i位置的节点（i = 0, 1, …, log N - 1）
查找任意key只需要O(log N)跳（而非朴素一致性哈希的O(N)跳）
节点加入/离开只需要O(log² N)的维护开销

Chord之后，CAN（Content Addressable Network，使用d维笛卡尔空间）、Pastry（使用前缀路由）、Kademlia（使用XOR度量）等DHT协议都在一致性哈希的思想上做了改进。Kademlia被BitTorrent、以太坊（节点发现）等系统广泛采用。

Amazon Dynamo的一致性哈希实践

Amazon Dynamo（2007年发表）将一致性哈希推广到了分布式键值存储领域。Dynamo的主要增强：

虚拟节点：每个物理节点负责哈希环上的多个位置（而不是一个），改善了负载均衡
Sloppy Quorum + Hinted Handoff：写入和读取不严格要求落在”正确的”节点上。如果主节点临时不可达，数据写入备用节点（Hinted Handoff），待主节点恢复后回传
Merkle Tree反熵：使用Merkle Tree（默克尔哈希树）高效检测副本之间的数据不一致，只同步有差异的部分（而非全量对比）
Gossip协议：使用Gossip协议传播集群成员信息（哪些节点加入/离开了哈希环），替代中心化的成员管理

Dynamo不追求强一致性，而是使用可调的一致性级别（R + W > N实现Quorum）。Dynamo的架构被Cassandra和Riak直接继承，也被Redis Cluster和MongoDB部分借鉴。

一致性哈希 vs 范围分区（Range Partitioning）

范围分区是另一个常见的分布式数据分布策略：

维度	一致性哈希	范围分区
数据分布	哈希值均匀分布，但破坏键的顺序性	按键有序存储，支持高效范围扫描
范围查询	不支持（相邻key散落到不同节点）	天然支持（相邻key在同一或相邻节点）
扩容影响	仅影响最小比例的key	需要分裂当前分区，影响有限
热点处理	容易（虚拟节点 + 哈希均匀分布）	需要动态分裂热点分区
适用场景	缓存、键值存储（Cassandra, Redis）	有序存储、时序数据库（HBase, Bigtable）

在实际系统中，两者经常结合。例如HBase使用范围分区（Region按RowKey范围排序），但在Region内部可能使用一致性哈希分布到不同的RegionServer。Cassandra使用一致性哈希（通过MurmurHash分区），但也支持范围扫描（通过Partition Key内的Clustering Column）。

十、面试常见追问

问题一：一致性哈希中，物理节点宕机后数据如何恢复？

如果物理节点宕机，该节点上的数据暂时不可用。在其恢复之前，请求会按照哈希环的顺时针查找，落到下一个节点，但下一个节点没有数据，返回缓存未命中。解决方案是数据冗余存储——每个key写入哈希环上的多个顺时针节点（如本节点和下一个节点），形成副本。读取时优先从主节点读，主节点不可用时从备用节点读。写入时如果主节点不可用，写入备用节点并标记该数据需要后续迁移。

问题二：短链的过期处理如何设计？

过期短链在生成时设置expires_at字段。在重定向流程中，每次查询短链映射时检查expires_at是否已过，如过期返回410 Gone页面。数据库中的过期记录通过两种方式清理：（1）定时任务每天扫描即将过期的短链，将其标记为过期状态；（2）延迟队列——在短链生成时，向延迟队列（如Redis的Sorted Set或RocketMQ的延迟消息）发送一条到期事件，24小时后触发清理。注意过期短链的短码可以（但不是必须）回收利用。如果回收，需要保证已投放的旧短链（如印刷在传单上）不会被新映射覆盖，常见做法是回收后等待足够长的冷却期（如90天）再重新分配。

问题三：为什么用Base62而不是Base64？

Base62使用[0-9a-zA-Z]共62个字符，全部是URL安全字符，不需要任何百分号编码。Base64包含+、/和=字符，在URL中需要进行百分号编码，增加长度且不美观。Base62的缺点是不能按完整字节对齐（62不是2的幂），编码和解码的计算量略大于Base64（Base64可以按6位直接查表，Base62需要除法和取模）。但在短链生成场景中，编码解码的计算量远小于网络IO，因此选择更具兼容性的Base62。

问题四：一致性哈希在Redis Cluster中是如何应用的？

Redis Cluster没有使用传统的一致性哈希，而是使用了16384个哈希槽（Hash Slot）的方案。每个key通过CRC16(key) % 16384映射到哈希槽，每个Redis节点负责一部分槽。当节点数量变化时，只迁移槽（hash slot）而非重新哈希所有key。这与一致性哈希的核心思想一致（最小化重新映射），但实现更简单——16384个槽的映射表非常紧凑（每个节点只需知道每个槽的归属）。客户端缓存槽映射表，如果key不在缓存的节点上，节点返回MOVED重定向，客户端更新本地映射表。

问题五：如何设计短链接的访问限制（如限制每个短链的总访问次数）？

可以在短链映射中加入max_clicks字段。重定向时使用Redis的原子递减操作：

-- Lua脚本
local count = redis.call('DECR', 'click_limit:' .. short_code)
if count >= 0 then
    return {1, count}  -- 允许访问，返回剩余次数
else
    redis.call('INCR', 'click_limit:' .. short_code)  -- 恢复计数
    return {0, 0}  -- 拒绝访问
end

在创建短链时设置click_limit:{short_code}为允许的最大访问次数。每次访问原子递减，到0时拒绝后续访问。这个方案需要Redis中的计数器永远存活（不设TTL），如果担心内存泄漏，可以在递减到0后延长TTL（如保留30天）再删除。

面试中的量化分析技巧

系统设计面试中的量化分析是评分的关键维度。以短网址系统为例，展示如何快速估算：

存储估算的快速方法：

短链映射: 每条约500字节（短码+长URL+时间戳+用户ID）
日增1亿条 → 50GB/天 → 18.25TB/年
5年规划 → ~100TB (加上余量)

分片需求:
单MySQL实例有效容量约2TB (SSD, 考虑备份和余量)
需要 100TB / 2TB = 50个分片
加上读写分离(1主2从) → 150个MySQL实例

Redis缓存需求:
热门短链: 每日100亿次读取
假设80%的读命中本地/Redis缓存
Redis需要承载80亿次/天 ≈ 9259 QPS (平均)
热门短链(占80%流量)约需缓存Top 5000万条
每条约1KB in Redis → 约50GB (可放入单个大内存Redis或Redis Cluster)

网络带宽估算：

短链重定向: 100亿次/天
每次重定向HTTP响应约500字节
总出站带宽: 100亿 × 500B / 86400s ≈ 57.9 MB/s (平均)
峰值(3x) ≈ 174 MB/s
CDN承担80%的流量后，源站带宽: 174 × 0.2 = 34.8 MB/s (轻松handle)

这类估算展示了你的工程直觉——不需要精确数字，但需要在合理数量级内。

本篇文章从短网址系统的需求出发，深入剖析了短链生成算法（哈希 vs 发号器）、系统架构、重定向流程，重点解析了一致性哈希的数学原理和工程实现，并对标了Redis Cluster的哈希槽方案、Jump Consistent Hash等变体。这些知识不仅适用于短网址系统，更是所有分布式存储系统分片策略的核心理论基础。

扩展阅读：短网址服务的工业界实现参考

TinyURL（2002年至今）：最早的短网址服务之一。早期使用Perl脚本+MySQL，短链为固定长度5-7个字符，使用MD5哈希+Base62编码。21年累计生成超过50亿条短链。

Bitly（2008年至今）：当前最大的短网址服务。迁移到了Go语言微服务架构。使用自研的NSQ消息队列处理分析事件的异步写入。Bitly独特的特性是支持自定义短链域名（Branded Short Domain）——企业用户可以将品牌域名配置为短链域名。

Twitter的t.co（2010年至今）：Twitter的核心基础设施。所有Tweet中的链接（即使不是通过Twitter的短网址服务创建）都会经过t.co包装——目的是链接安全检查（防钓鱼）和点击追踪。t.co每天处理数百亿次重定向请求。重定向延迟<5ms（通过遍布全球的CDN边缘节点）。

短网址系统的安全挑战：

短链使得恶意链接更隐蔽——用户无法从URL判断目标网站。Google Safe Browsing集成已成为标配。
短链的不可预测性既是特性也是bug——攻击者可以枚举短链空间发现未公开的链接。解决方法是使用不可猜测的随机短码（大编码空间），并对敏感链接增加密码保护。
短链服务是天然的CC攻击放大器——攻击者创建短链指向受害者服务器，然后大量传播短链，短网址服务本身的高速重定向能力变成攻击者的”免费CDN”。防护措施：每个短链的访问频率限制、异常流量检测。