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

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

短网址服务（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。

二、短链的生成算法

短链的核心是将任意长度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条短链，足够使用数百年。

三、系统架构总览

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

用户服务：处理用户的注册、登录和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分片存储短链映射关系，分片键使用短链的哈希值（以保证均匀分布）。

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

用户点击短链 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表示永久重定向，浏览器会缓存重定向结果，下次点击直接跳转，不再经过短链服务器，适合不需要统计的场景（如静态资源）。

五、一致性哈希算法详解

当单台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次比较。

六、短链系统的存储设计

短链映射表的核心字段：

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分钟），过滤掉重复读取。

七、分析系统的设计

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

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

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

八、限流与安全

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

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

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

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

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

九、面试常见追问

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

如果物理节点宕机，该节点上的数据暂时不可用。在其恢复之前，请求会按照哈希环的顺时针查找，落到下一个节点，但下一个节点没有数据，返回缓存未命中。解决方案是数据冗余存储——每个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。