基于哈希的分布式短网址系统设计

题目描述：
设计一个基于哈希算法的分布式短网址系统。系统需要支持以下核心功能：

1. 将任意长度的原始URL（如数百字符的长链接）通过哈希算法映射为固定长度（如6-8字符）的短码。
2. 通过短码可准确还原原始URL（重定向访问）。
3. 系统需具备高可用性、可扩展性，能够应对海量URL转换请求（分布式特性）。
4. 短码需尽可能避免碰撞（不同原始URL生成相同短码）。
5. 短码应尽可能简短，字符集可自定义（如[a-zA-Z0-9]共62个字符）。

解题过程循序渐进讲解：

步骤1：理解核心问题与约束
短网址系统的核心是单向映射：原始URL → 短码。当用户访问短码时，系统需快速查找到原始URL并重定向。
关键点：

• 短码空间：若用6位62进制字符，总数为62^6≈568亿，足够应对一般场景。
• 哈希碰撞：需有策略处理不同URL生成相同短码的情况。
• 分布式生成：多个服务器同时生成短码时，需保证短码唯一性。

步骤2：基础哈希方案设计
最直观的方案是使用密码学哈希函数（如MD5、SHA-256）对原始URL计算哈希值，然后转换为短码。

1. 对原始URL计算哈希值（如SHA-256得到256位十六进制串）。
2. 取哈希值前若干位（如8个十六进制字符）作为短码。
   • 但这样短码长度固定为8个十六进制字符（0-9a-f），字符集仅16种，不够紧凑。
3. 改进：将哈希值转换为62进制（0-9a-zA-Z），取前6位作为短码。
   • 例如，将128位MD5结果分成4段，每段32位，转换为62进制后取前6字符。

潜在问题：

• 哈希碰撞概率：虽然极低，但仍需处理。
• 同一URL多次生成：应返回相同短码（幂等性）。

步骤3：解决哈希碰撞与幂等性

1. 存储逻辑：
   • 维护两个哈希表：
     • long2short：键为原始URL的哈希值（或直接为原始URL），值为短码。用于实现幂等性（同一URL返回相同短码）。
     • short2long：键为短码，值为原始URL。用于重定向查找。
2. 碰撞处理流程：
   • 生成短码后，先查short2long：
     • 若不存在，直接存储映射。
     • 若存在且对应的原始URL与当前相同，说明是同一URL重复提交，返回已有短码。
     • 若存在但原始URL不同，说明发生碰撞，需重新生成短码（例如在原URL后添加随机盐值再哈希，或使用哈希值的下一段）。

步骤4：分布式场景下的唯一ID生成
在分布式系统中，多台服务器同时生成短码，需保证短码全局唯一。常用方案：

1. 使用分布式唯一ID生成器（如雪花算法）产生唯一整数ID，再将整数ID转换为62进制短码。
   • 优点：绝对唯一，无碰撞。
   • 缺点：短码与URL无直接关联，同一URL在不同服务器可能生成不同短码（需额外维护long2short映射）。
2. 结合哈希与唯一ID：
   • 对URL哈希得到62进制串（如10位）。
   • 在该串后追加服务器ID（2位）和序列号（2位），组成最终短码（共14位，可裁剪为8位）。
   • 通过服务器ID避免多机冲突，序列号避免同机冲突。

步骤5：系统架构与存储设计

1. 请求流程：
   • 短码生成：

     1. 用户提交长URL → 负载均衡器分发到某应用服务器。
     2. 服务器计算短码（如用哈希+唯一ID组合）。
     3. 写数据库前先查`long2short`表，若存在则返回已有短码。
     4. 若不存在，将`long2short`和`short2long`记录写入数据库（事务保证一致性）。
     

   • 重定向访问：

     1. 用户访问短链 → 短码解析服务查询`short2long`表。
     2. 若找到原始URL，返回302重定向；否则返回404。
     

2. 存储优化：
   • 使用分布式缓存（如Redis）存储热点短码映射，加速重定向。
   • 数据库可按短码分片（如取短码前2位作为分片键），支持水平扩展。

步骤6：短码生成算法示例（62进制转换）
假设我们用8位62进制短码，字符集为[0-9a-zA-Z]共62字符。

1. 对原始URL计算MD5，得到128位哈希值，转为大整数H。
2. 将H转换为62进制：

   chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
   short_code = ""
   while H > 0 and len(short_code) < 8:
       short_code = chars[H % 62] + short_code
       H //= 62
   

3. 若长度不足8位，前面补0（用字符'0'填充）。

步骤7：优化与扩展

1. 自定义短码：允许用户自选短码后缀，系统需检查是否已被占用。
2. 过期与清理：可为短码设置TTL，定期清理过期映射。
3. 防攻击：对恶意刷URL进行限流；短码字符集避免使用易混淆字符（如0/O、1/l）。
4. 监控：统计短码访问频次，用于缓存优化和业务分析。

总结：
设计分布式短网址系统的核心在于短码唯一性和快速查找。通过哈希算法结合唯一ID，可在分布式环境下生成紧凑、唯一的短码；通过两层哈希表（long2short、short2long）保证幂等性与重定向效率。存储上结合缓存与分片数据库，可支撑高并发访问。