WhatAKitty Daily

A Programmer's Daily Record

如何设计短域名系统

WhatAKitty   阅读次数loading...

背景

系统设计的整体方法论学习与尝试

方法论

系统设计的目的 -> 系统设计的目标 -> 围绕目标的核心设计 -> 围绕核心设计形成的设计原则 -> 各子系统

系统设计的目的

  • 设计一个易用、高可用、可支持大规模访问的短域名系统

系统设计的目标

  • 支持短域名领域TOP5的网站规模
  • 支持99%的可用性
  • 响应时间在100ms以内
  • 域名长度限制在10个字符以内

围绕目标的核心设计

对上述系统目标做技术性的一个拆分

  • 支持短域名领域TOP5的网站规模
    • 全球排名第二的Youtube月访问量:284.4亿(近6个月PV数据量) * 9.56 / 6 = 453.144亿
    • 按照二八原则,TOP5的月流量大概在90.63亿次
    • 假设15%的请求访问到短域名生成服务,生成短域名月访问量级别在13.59亿次
    • 假设30%的请求访问到短域名生成的短连接上,短域名转化服务月访问量级别在27.19亿
    • 生成短域名服务按照域名存储的量级计算
      • 假设按最长长度存储,即10字符,需要月存储的key量级在10 4 13.59亿 / 1024 / 1024 / 1024 = 50.63GB;年存储量级607.52GB
      • 假设转发网址长度平均在100字符,需要月存储的value量级在10 * 50.63GB = 506.3GB;年存储级6075.6GB
  • 支持99.9%的可用性
    • 自然年内服务中断时长不能超过8.76小时
  • 响应时间在100ms以内
    • 生成短域名请求为13.59亿次/月,TPS大概为525
    • 短域名代理跳转请求为27.19亿次/月,QPS大概为1049
  • 域名长度限制在10个字符以内
    • 目前互联网存在40.1M个网站
    • 10个字符按照大小写数字计算62^10 >> 40.1M

各子系统

根据单一职责设计原则,划分子系统:

  1. 短域名生成服务:将长链接转为短连接
  2. 短域名代理服务:根据短连接302跳转至目标地址

具体设计

围绕上述的核心设计,可以预知的挑战主要有如下几点:

  1. 5年内hash存储量级在3TB,原始url信息存储量级在30TB左右
  2. 每秒总请求 1600 左右
  3. 99.9%的可用性

接下来对于3个预知的挑战点做具体的分析探讨

存储问题

在不进行任何转化算法以及数据压缩之前,数据的存储量级是非常大的。
这会造成两个影响:

  1. 无法快速索引,即使使用KV数据库,也需要找到这个KEY的位置
  2. 过于庞大的数据库对于磁盘存在一定的水平扩展压力

所以,需要从以下几个点考虑上述两个问题:

  1. 如何构建快速查询的索引结构,尽可能在较少的时间复杂度下获取结果
    • 现有的不管是关系型数据库MySQL,还是NoSQL类型的MongoDB、HBase等,对于键的查询还是比较快的,时间复杂度在O(logn)级别。
      所以在索引查询上,可以直接使用现有的存储数据库。
  2. 如何处理数据存储的压缩,减少存储的压力
    • 在数据存储层面可以考虑使用变长字段,而不是固长字段减少数据占用
  3. 如何在磁盘容量不足的情况下,达到平滑扩容的效果,而不会影响现有的系统
    • 使用现成的可扩容数据存储来实现效果
    • 自己实现分布式存储,使用一致性hash算法来分发;但是如果新增了一个物理存储节点,需要进行数据重新分配操作

高并发问题

每秒总请求1600左右,其中写请求525,读请求1049;可以确认是读多写少的业务场景,可以从以下四个方面优化:

  1. 减少上游请求数
    • 使用布隆过滤器,不存在的必定不存在
      • 按照5年hash存储记录数来计算,需要存储480亿的key
      • 布隆过滤器1%误差率,一个key大概需要9.6bits空间,480亿的key大概需要53GB的内存量
  2. 路由分发,且对应读服务做缓存保证
    • 在网关层将key做一层hash,分散到一致性hash环上
    • 每个短域名代理转发服务器,都有一个LRU的本地缓存
  3. 抽离热点数据,对不同key的访问做分值统计,高分值数据到达一个阈值存入集中式缓存
    • 短域名代理转发服务器启动的时候预加载热点数据至本地缓存
    • 访问完成的时候,如果某个key达到一个阈值后,则异步将该值存入本地缓存,并广播完成后,存入至集中式缓存内;存储失败则最多3次重试
  4. 存储层面读写分离

高可用问题

可用性主要体现在以下几个方面:

  1. 服务的可用性
    • 注册中心本身使用多节点主备策略,保证自身高可用
    • 注册中心维护服务的负载均衡,服务调用通过注册中心调用目标服务器,可以选择负载均衡策略为WeightedResponseTimeRule
  2. 数据存储可用性
    • 主从备份机制
  3. 数据本身可用性
    • 异机replica机制,保证数据的可恢复性