面试官：如何设计支持千万级别短链的方案

概述

• 面试中遇到的架构设计问题，对比传统问题，认为此问题更具挑战性。

短链生成方法

1. Hash算法

   • 使用非加密型哈希函数，推荐MurmurHash，因其性能高，冲突概率低。
   • 哈希函数选择：避免使用MD5、SHA等加密算法，因为它们性能较低。

2. 缩短域名

   • 使用MurmurHash64生成64位十进制数，然后转换为62进制（包含小写字母、大写字母和数字）以缩短长度。

3. 解决Hash冲突

   • 设计MySQL表short_url，包含id、lurl（长URL）、surl（短URL）和时间戳。
   • 使用MurmurHash64和Base62编码生成短链，如果冲突，通过添加随机字段解决。

4. 发号器

   • 使用自增ID，如UUID、Redis计数、Snowflake算法或MySQL自增主键，转化为62进制生成短链。

算法实现

• 使用MurmurHash64作为哈希函数，测试显示在大量数据下冲突概率极低。
• 核心算法包括：
  • generateShortUrl：生成短链。
  • getShortUrl：根据长链和哈希值生成短链。
  • getLongUrl：根据短链获取长链。

优化点

• 数据库访问：生成和获取短链都只需访问一次数据库，通过唯一索引处理冲突。
• LRU Cache：使用最近最少使用（LRU）缓存，减少数据库访问，提高性能。
• 随机字符串：在哈希冲突时添加随机字符串，降低再次冲突的概率。
• MurmurHash64：选择性能优秀的哈希算法。

技术选择

• 选择MySQL作为底层存储，考虑数据持久性和效率。
• 避免使用Redis或HBase，因为它们可能存在数据丢失或效率不可控的问题。

总结

设计支持千万级别短链的系统需要考虑哈希算法的选择、数据库设计、缓存策略和性能优化。通过合理设计，可以实现高效、稳定的短链服务。