尧图网站建设 
把https://mp.weixin.qq.com/s?__biz...120 字符压缩成t.cn/A7f3kQ6位看起来只是“省几个字”。它真正要达到的是可发布、可传播、可统计——短信限字、二维码复杂度、以及最重要的每一次点击都要能被记录下来。这道题在面试里地位特殊它没有标准答案但能一次性把你“算法 数据库 缓存 高并发”的底子全翻一遍。今天讲清四件事①两大发号方案怎么选②Base62为什么不是Base64③布隆过滤器怎么挡住无效短码④301和302到底怎么选。 题目速览30秒读懂设计短链服务支持POST /shorten→ 返回短链https://t.cn/{code}GET /{code}→重定向到原始长URL可选统计点击数、自定义短码、过期时间面试官给的估算假设必须自己算参数假设值每日新增短链1000万条读写比100 : 1保留时长3~5年单条记录大小约500B由此推出指标计算过程结果写QPS1000万 / 86400≈116/s峰值 ≈350/s读QPS1000万 × 100 / 86400≈11,600/s峰值 ≈3.5万/s5年总条数1000万 × 365 × 5≈182.5亿条存储量182.5亿 × 500B≈9TB必须分库分表短码容量6位Base62 568亿 182.5亿 ✅ 够用 核心思路四大关键决策① 发号方案自增ID Base62主流 vs 哈希补充方案优点缺点自增ID Base62绝对无冲突、可反解、实现简单短码连续可预测哈希MD5/CRC32取前6位无规律、不可枚举、幂等有冲突、需重试、反查需额外索引结论主流工业方案选自增ID Base62唯一缺陷可被遍历用“ID混淆”廉价补上。② ID混淆异或 循环移位双射且可逆defmix(uid):returnrotl31(uid^SALT,17)defunmix(x):returnrotr31(x,17)^SALT效果uid1 → wI7Fhuid2 → wGtn5连续ID被搅成完全无规律。无冲突、可逆、O(1)。③ 为什么是Base62而不是Base64Base64含和/URL里有特殊含义解码为空格/是路径分隔符。Base62 [0-9a-zA-Z]全是URL安全字符双击可选中整串。④ 读链路三层拦截布隆 → LRU → DBGET /{code} │ ├─① 布隆过滤器不存在 → 直接404连缓存都不查 │ ├─② LRU热点缓存命中 → 直接302 │ └─③ DB回源并写回LRU布隆挡住缓存穿透打错的、恶意遍历的100万key仅2.5MB误判率0.1%LRU热点访问极度集中命中率90%3.5万QPS根本不碰DB⑤ 发号器不能每次打DB——号段Segment模式一次领一段[start, startstep)到内存本地发用完才回源领下一段把DB压力降低step倍。⑥ 301还是302——商业短链一律302301永久302临时浏览器行为缓存后续不再请求服务器不缓存每次回源能否统计PV/UV❌ 不能✅ 能能否动态改目标❌✅结论要统计、要运营、要随时改跳转就用302。301只适合固定连接、不需要任何数据的场景。可用Cache-Control: private, max-age3600折中。️ 图解算法Base62编码uid 12345678字符集0-9 a-z A-Z下标0-61轮nn÷62商余数字符112,345,678199,12352Q2199,1233,21141F33,2115149N451051P倒序读余数 →PNFQ即https://t.cn/PNFQ。短码长度与容量长度容量按 1000 万/天够用6位568亿约15.6年7位35.2万亿约9600年6位就够5年182.5亿 568亿。整体架构【写】POST /shorten 长URL → 查重 → 号段发号 → mix(uid) → Base62 → 补6位 → 写DB 写布隆 预热LRU 【读】GET /{code} code → ①布隆不存在→404 → ②LRU命中→302 → ③DB回源→回填LRU→302 → 异步埋点PV/UV/渠道/地域 代码实现Python核心模块importhashlibfromcollectionsimportOrderedDict ALPHABET0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZBASE62_MASK31(131)-1_SALT0x5DEECE66# ① Base62 编解码defbase62_encode(n):ifn0:returnALPHABET[0]chars[]whilen:chars.append(ALPHABET[n%BASE])n//BASEreturn.join(reversed(chars))# ★ 记得倒序defbase62_decode(s):n0forchins:nn*BASEALPHABET.index(ch)returnn# ② ID 混淆def_rotl31(x,r):return((xr)|(x(31-r)))_MASK31def_rotr31(x,r):return((xr)|(x(31-r)))_MASK31defmix(uid):return_rotl31(uid^_SALT,17)defunmix(x):return_rotr31(x,17)^_SALT# ③ 号段发号器classSegmentAllocator:def__init__(self,step1000):self.stepstep;self.cur0;self.end0;self._db0defnext_id(self):ifself.curself.end:self._dbself.step self.cur,self.endself._db-self.step,self._db self.cur1returnself.cur# ④ 布隆过滤器classBloomFilter:def__init__(self,capacity,bits_per_key20,k4):self.sizecapacity*bits_per_key self.bitsbytearray((self.size7)//8)self.kkdef_positions(self,s):dhashlib.md5(s.encode()).digest()h1int.from_bytes(d[:8],big);h2int.from_bytes(d[8:],big)foriinrange(self.k):yield(h1i*h2)%self.sizedefadd(self,s):forpinself._positions(s):self.bits[p3]|1(p7)defcontains(self,s):returnall(self.bits[p3](1(p7))forpinself._positions(s))# ⑤ LRUclassLRUCache:def__init__(self,capacity):self.capcapacity;self.dataOrderedDict()defget(self,key):ifkeynotinself.data:returnNoneself.data.move_to_end(key,lastFalse)returnself.data[key]defput(self,key,value):self.data[key]value self.data.move_to_end(key,lastFalse)iflen(self.data)self.cap:self.data.popitem(lastTrue)# ⑥ 短链服务主体classShortLinkService:def__init__(self,domainhttps://t.cn/):self.domaindomain self.seqSegmentAllocator(1000)self.db{};self.reverse{}self.bloomBloomFilter(1_000_000)self.cacheLRUCache(100_000)defshorten(self,long_url):iflong_urlinself.reverse:returnself.domainself.reverse[long_url]uidself.seq.next_id()codebase62_encode(mix(uid)).rjust(6,0)self.db[code]long_url self.reverse[long_url]code self.bloom.add(code)self.cache.put(code,long_url)returnself.domaincodedefredirect(self,code):ifnotself.bloom.contains(code):raiseKeyError(404)hitself.cache.get(code)ifhitisnotNone:returnhit long_urlself.db.get(code)iflong_urlisNone:raiseKeyError(404)self.cache.put(code,long_url)returnlong_url⚠️防坑提醒base62_encode最后必须reversed。_SALT必须 2³¹否则混淆溢出不再是双射会撞号。布隆假阳性不需要额外处理404前查一次DB兜底即可。redirect三层顺序不能变布隆 → LRU → DB。⏱️ 复杂度分析面试必问模块时间空间Base62编解码O(log₆₂ n) ≈ O(1)O(1)ID混淆O(1)O(1)布隆 add/containsO(k) ≈ O(1)20 bit/keyLRU get/putO(1)O(capacity)重定向缓存命中O(1)不碰DB—写O(1)号段发号 一次INSERT读O(1)平均缓存命中率90%。这就是扛住3.5万QPS的原因。 举一反三相关设计题题目共用模块短链服务今天发号器 Base62 布隆 LRU 301/302分布式ID生成器SegmentAllocator的升级版Snowflake网页去重爬虫布隆过滤器是主角缓存穿透防控布隆 空值缓存 面试追问模拟提前准备惊艳全场Q1自增ID生成的短码会被遍历怎么防三层①混淆mix rotl(uid ^ SALT, 17)无冲突且可逆成本几乎为零②随机后缀破坏规律③限流对IP/UA频率限制。短码不是安全凭据敏感资源必须叠加鉴权。Q2301和302怎么选要统计PV/UV、要随时改跳转目标就用302商业短链几乎都选它。只在固定连接、不需要数据时用301。可用Cache-Control: private, max-age3600折中。Q3过期短链怎么清理①惰性删除访问时发现过期返回404并异步删②定时任务低峰批量DELETE③滚动归档按时间分表过期直接DROP TABLE。记得同步清理布隆普通布隆不能删用Counting Bloom。Q4如何防止恶意批量刷短码四道防线限流IP/用户/全局三级、验证码、配额、内容风控URL安全扫描合规红线。Q5容量估算和高可用怎么做容量182.5亿条 × 500B ≈ 9TB必须分库分表按code取模或一致性哈希 冷热分离。高可用无状态服务水平扩容发号器多机房独立号段DB主从 自动切换缓存Redis集群。关键指标重定向P99 50ms可用性99.99%。 实战小技巧刷题党必备口诀自增发号Base62混淆防遍历布隆挡穿透LRU扛热点商业短链必选302。模板短链 发号器 Base62 混淆 布隆 LRU 302。防坑Base62记得倒序SALT 2³¹布隆假阳性兜底。 实际应用场景不止是刷题微博/Twitter 短分享t.cn / bit.ly营销推广每渠道一个短码离线统计短信长链接降级节省字数二维码压缩内容更短码更简单Base62本身YouTube视频ID、内部单据号 今日思考题你的项目里用短链吗如果给内部系统做短链你会选301还是302动手题把布隆过滤器换成支持删除的Counting Bloom Filter需要改哪几处 系统设计必考！短链系统：一个`t.cn/xxxxx` 背后藏着多少算法？
把https://mp.weixin.qq.com/s?__biz...120 字符压缩成t.cn/A7f3kQ6位看起来只是“省几个字”。它真正要达到的是可发布、可传播、可统计——短信限字、二维码复杂度、以及最重要的每一次点击都要能被记录下来。这道题在面试里地位特殊它没有标准答案但能一次性把你“算法 数据库 缓存 高并发”的底子全翻一遍。今天讲清四件事①两大发号方案怎么选②Base62为什么不是Base64③布隆过滤器怎么挡住无效短码④301和302到底怎么选。 题目速览30秒读懂设计短链服务支持POST /shorten→ 返回短链https://t.cn/{code}GET /{code}→重定向到原始长URL可选统计点击数、自定义短码、过期时间面试官给的估算假设必须自己算参数假设值每日新增短链1000万条读写比100 : 1保留时长3~5年单条记录大小约500B由此推出指标计算过程结果写QPS1000万 / 86400≈116/s峰值 ≈350/s读QPS1000万 × 100 / 86400≈11,600/s峰值 ≈3.5万/s5年总条数1000万 × 365 × 5≈182.5亿条存储量182.5亿 × 500B≈9TB必须分库分表短码容量6位Base62 568亿 182.5亿 ✅ 够用 核心思路四大关键决策① 发号方案自增ID Base62主流 vs 哈希补充方案优点缺点自增ID Base62绝对无冲突、可反解、实现简单短码连续可预测哈希MD5/CRC32取前6位无规律、不可枚举、幂等有冲突、需重试、反查需额外索引结论主流工业方案选自增ID Base62唯一缺陷可被遍历用“ID混淆”廉价补上。② ID混淆异或 循环移位双射且可逆defmix(uid):returnrotl31(uid^SALT,17)defunmix(x):returnrotr31(x,17)^SALT效果uid1 → wI7Fhuid2 → wGtn5连续ID被搅成完全无规律。无冲突、可逆、O(1)。③ 为什么是Base62而不是Base64Base64含和/URL里有特殊含义解码为空格/是路径分隔符。Base62 [0-9a-zA-Z]全是URL安全字符双击可选中整串。④ 读链路三层拦截布隆 → LRU → DBGET /{code} │ ├─① 布隆过滤器不存在 → 直接404连缓存都不查 │ ├─② LRU热点缓存命中 → 直接302 │ └─③ DB回源并写回LRU布隆挡住缓存穿透打错的、恶意遍历的100万key仅2.5MB误判率0.1%LRU热点访问极度集中命中率90%3.5万QPS根本不碰DB⑤ 发号器不能每次打DB——号段Segment模式一次领一段[start, startstep)到内存本地发用完才回源领下一段把DB压力降低step倍。⑥ 301还是302——商业短链一律302301永久302临时浏览器行为缓存后续不再请求服务器不缓存每次回源能否统计PV/UV❌ 不能✅ 能能否动态改目标❌✅结论要统计、要运营、要随时改跳转就用302。301只适合固定连接、不需要任何数据的场景。可用Cache-Control: private, max-age3600折中。️ 图解算法Base62编码uid 12345678字符集0-9 a-z A-Z下标0-61轮nn÷62商余数字符112,345,678199,12352Q2199,1233,21141F33,2115149N451051P倒序读余数 →PNFQ即https://t.cn/PNFQ。短码长度与容量长度容量按 1000 万/天够用6位568亿约15.6年7位35.2万亿约9600年6位就够5年182.5亿 568亿。整体架构【写】POST /shorten 长URL → 查重 → 号段发号 → mix(uid) → Base62 → 补6位 → 写DB 写布隆 预热LRU 【读】GET /{code} code → ①布隆不存在→404 → ②LRU命中→302 → ③DB回源→回填LRU→302 → 异步埋点PV/UV/渠道/地域 代码实现Python核心模块importhashlibfromcollectionsimportOrderedDict ALPHABET0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZBASE62_MASK31(131)-1_SALT0x5DEECE66# ① Base62 编解码defbase62_encode(n):ifn0:returnALPHABET[0]chars[]whilen:chars.append(ALPHABET[n%BASE])n//BASEreturn.join(reversed(chars))# ★ 记得倒序defbase62_decode(s):n0forchins:nn*BASEALPHABET.index(ch)returnn# ② ID 混淆def_rotl31(x,r):return((xr)|(x(31-r)))_MASK31def_rotr31(x,r):return((xr)|(x(31-r)))_MASK31defmix(uid):return_rotl31(uid^_SALT,17)defunmix(x):return_rotr31(x,17)^_SALT# ③ 号段发号器classSegmentAllocator:def__init__(self,step1000):self.stepstep;self.cur0;self.end0;self._db0defnext_id(self):ifself.curself.end:self._dbself.step self.cur,self.endself._db-self.step,self._db self.cur1returnself.cur# ④ 布隆过滤器classBloomFilter:def__init__(self,capacity,bits_per_key20,k4):self.sizecapacity*bits_per_key self.bitsbytearray((self.size7)//8)self.kkdef_positions(self,s):dhashlib.md5(s.encode()).digest()h1int.from_bytes(d[:8],big);h2int.from_bytes(d[8:],big)foriinrange(self.k):yield(h1i*h2)%self.sizedefadd(self,s):forpinself._positions(s):self.bits[p3]|1(p7)defcontains(self,s):returnall(self.bits[p3](1(p7))forpinself._positions(s))# ⑤ LRUclassLRUCache:def__init__(self,capacity):self.capcapacity;self.dataOrderedDict()defget(self,key):ifkeynotinself.data:returnNoneself.data.move_to_end(key,lastFalse)returnself.data[key]defput(self,key,value):self.data[key]value self.data.move_to_end(key,lastFalse)iflen(self.data)self.cap:self.data.popitem(lastTrue)# ⑥ 短链服务主体classShortLinkService:def__init__(self,domainhttps://t.cn/):self.domaindomain self.seqSegmentAllocator(1000)self.db{};self.reverse{}self.bloomBloomFilter(1_000_000)self.cacheLRUCache(100_000)defshorten(self,long_url):iflong_urlinself.reverse:returnself.domainself.reverse[long_url]uidself.seq.next_id()codebase62_encode(mix(uid)).rjust(6,0)self.db[code]long_url self.reverse[long_url]code self.bloom.add(code)self.cache.put(code,long_url)returnself.domaincodedefredirect(self,code):ifnotself.bloom.contains(code):raiseKeyError(404)hitself.cache.get(code)ifhitisnotNone:returnhit long_urlself.db.get(code)iflong_urlisNone:raiseKeyError(404)self.cache.put(code,long_url)returnlong_url⚠️防坑提醒base62_encode最后必须reversed。_SALT必须 2³¹否则混淆溢出不再是双射会撞号。布隆假阳性不需要额外处理404前查一次DB兜底即可。redirect三层顺序不能变布隆 → LRU → DB。⏱️ 复杂度分析面试必问模块时间空间Base62编解码O(log₆₂ n) ≈ O(1)O(1)ID混淆O(1)O(1)布隆 add/containsO(k) ≈ O(1)20 bit/keyLRU get/putO(1)O(capacity)重定向缓存命中O(1)不碰DB—写O(1)号段发号 一次INSERT读O(1)平均缓存命中率90%。这就是扛住3.5万QPS的原因。 举一反三相关设计题题目共用模块短链服务今天发号器 Base62 布隆 LRU 301/302分布式ID生成器SegmentAllocator的升级版Snowflake网页去重爬虫布隆过滤器是主角缓存穿透防控布隆 空值缓存 面试追问模拟提前准备惊艳全场Q1自增ID生成的短码会被遍历怎么防三层①混淆mix rotl(uid ^ SALT, 17)无冲突且可逆成本几乎为零②随机后缀破坏规律③限流对IP/UA频率限制。短码不是安全凭据敏感资源必须叠加鉴权。Q2301和302怎么选要统计PV/UV、要随时改跳转目标就用302商业短链几乎都选它。只在固定连接、不需要数据时用301。可用Cache-Control: private, max-age3600折中。Q3过期短链怎么清理①惰性删除访问时发现过期返回404并异步删②定时任务低峰批量DELETE③滚动归档按时间分表过期直接DROP TABLE。记得同步清理布隆普通布隆不能删用Counting Bloom。Q4如何防止恶意批量刷短码四道防线限流IP/用户/全局三级、验证码、配额、内容风控URL安全扫描合规红线。Q5容量估算和高可用怎么做容量182.5亿条 × 500B ≈ 9TB必须分库分表按code取模或一致性哈希 冷热分离。高可用无状态服务水平扩容发号器多机房独立号段DB主从 自动切换缓存Redis集群。关键指标重定向P99 50ms可用性99.99%。 实战小技巧刷题党必备口诀自增发号Base62混淆防遍历布隆挡穿透LRU扛热点商业短链必选302。模板短链 发号器 Base62 混淆 布隆 LRU 302。防坑Base62记得倒序SALT 2³¹布隆假阳性兜底。 实际应用场景不止是刷题微博/Twitter 短分享t.cn / bit.ly营销推广每渠道一个短码离线统计短信长链接降级节省字数二维码压缩内容更短码更简单Base62本身YouTube视频ID、内部单据号 今日思考题你的项目里用短链吗如果给内部系统做短链你会选301还是302动手题把布隆过滤器换成支持删除的Counting Bloom Filter需要改哪几处