乐趣区

关于qps:100Wqps短链系统怎么设计

jiezi

这段时间，在整顿常识星球中面试专栏时看到这么一个字节跳动的二面真题：100Wqps 短链零碎，怎么设计？

这道题，看上去业务简略，其实，笼罩的知识点十分多：

  • 高并发、高性能分布式 ID
  • Redis Bloom Filter 高并发、低内存损耗的 过滤组件常识
  • 分库、分表海量数据存储
  • 多级缓存的常识
  • HTTP 传输常识
  • 二进制、十六进制、六十二进制常识

总体来说，高并发、高性能零碎的外围畛域，都笼罩了。所以，陈某剖析下来，失去一个论断：是一个超级好的问题。

1、短 URL 零碎的背景

短网址代替长 URL，在互联网网上流传和援用。

例如 QQ 微博的 url.cn，新郎的 sinaurl.cn 等。

在 QQ、微博上公布网址的时候，会主动判断网址，并将其转换，例如：url.cn/2hytQx

为什么要这样做的，无外乎几点：

  1. 缩短地址长度，留足更多空间的给 有意义的内容

    URL 是没有意义的，有的原始 URL 很长，占用无效的屏幕空间。

    微博限度字数为 140 字一条，那么如果这个连贯十分的长，以至于将近要占用咱们内容的一半篇幅，这必定是不能被容许的，链接变短，对于有长度限度的平台发文，可编辑的文字就变多了，所以短网址应运而生了。

  2. 能够很好的对原始 URL 内容管控。

    有一部分网址能够会涵盖 XX，暴力，广告等信息，这样咱们能够通过用户的举报，齐全治理这个连贯将不呈现在咱们的利用中，应为同样的 URL 通过加密算法之后，失去的地址是一样的。

  3. 能够很好的对原始 URL 进行行为剖析

    咱们能够对一系列的网址进行流量，点击等统计，挖掘出大多数用户的关注点，这样有利于咱们对我的项目的后续工作更好的作出决策。

  4. 短网址和短 ID 相当于间接进步了带宽的利用率、节约老本
  5. 链接太长在有些平台上无奈自动识别为超链接
  6. 短链接更加简洁难看且平安，不裸露拜访参数。而且，能躲避关键词、域名屏蔽等伎俩

2、短 URL 零碎的原理

短 URL 零碎的外围：将长的 URL 转化成短的 URL。

客户端在拜访零碎时，短 URL 的工作流程如下：

  • 先应用短地址 A 拜访 短链 Java 服务
  • 短链 Java 服务 进行 地址转换和映射，将 短 URL 零碎映射到对应的长地址 URL
  • 短链 Java 服务 返回 302 重定向 给客户端
  • 而后客户端再重定向到原始服务

如下图所示：

那么，原始 URL 如何变短呢？简略来说，能够将原始的地址，应用编号进行代替

编号如何进一步变短呢？能够应用更大的进制来示意

六十二进制表示法

顾名思义短网址就是十分短的网址，比方 xxx.cn/EYyCO9T，其中核… EYyCO9T 只有 7 位长度。

其实这里的 7 位长度是应用 62 进制来示意的，就是罕用的 0 -9、a-z、A-Z，也就是 10 个数字 +26 个小写 +26 个大写 =62 位。

那么 7 位长度 62 进制能够示意多大范畴呢?

62^7 = 3,521,614,606,208 (共计 3.5 万亿)，阐明：10 进制 最大只能生成 10 ^ 6 - 1 =999999 个
16 进制 最大只能生成 16 ^ 6 - 1 =16777215 个
16 进制外面曾经蕴含了 A B C D E F 这几个字母
62 进制 最大竟能生成 62 ^ 6 - 1 =56800235583 个 基本上够了。A-Z a-z 0-9 刚好等于 62 位

留神：int(4 个字节)，存储的范畴是 -21 亿到 21 亿
long(8 个字节)，存储的范畴是 -900 万万亿 到 900 万万亿

至于短网址的长度，能够依据本人须要来调整，如果须要更多，能够减少位数，

即便 6 位长度 62^6 也能达到 568 亿的范畴，

这样的话只有算法切当，能够笼罩很大的数据范畴。

在编码的过程中，能够依照本人的需要来调整 62 进制各位代表的含意。

一个典型的场景是，在编码的过程中，如果不想让人明确晓得转换前是什么，能够进行弱加密，

比方 A 站点将字母 c 示意 32、B 站点将字母 c 示意 60，就相当于密码本了。

128 进制表示法

规范 ASCII 码也叫根底 ASCII 码，应用 7 位二进制数（剩下的 1 位二进制为 0）, 蕴含 128 个字符，

看到这里你或者会说，应用 128 进制 (如果有的话) 岂不是网址更短，

是的，

7 位二进制数（剩下的 1 位二进制为 0）示意所有的大写和小写字母，数字 0 到 9、标点符号，以及在美式英语中应用的非凡控制字符 [1]。

留神：128 个进制就可能会呈现大量的不罕用字符

比方 # % & * 这些，这样的话，对于短链接而言，通用性和记忆性就变差了，所以，62 进制是个衡量折中。

3、短 URL 零碎的功能分析

假如短地址长度为 8 位，62 的 8 次方足够个别零碎应用了

系统核心实现，蕴含三个大的性能

  • 发号
  • 存储
  • 映射

能够分为两个模块：发号与存储模块、映射模块

发号与存储模块

  • 发号：应用发号器发号，为每个长地址调配一个号码 ID，并且须要避免地址二义，也就是避免同一个长址屡次申请失去的短址不一样
  • 存储：将号码与长地址寄存在 DB 中，将号码转化成 62 进制，用于示意最终的短地址，并返回给用户

映射模块

用户应用 62 进制的短地址申请服务，

  • 转换：将 62 进制的数转化成 10 进制，因为咱们零碎外部是 long 类型的 10 进制的数字 ID
  • 映射：在 DB 中寻找对应的长地址
  • 通过 302 重定向，将用户申请重定向到对应的地址上

4、发号器的高并发架构

回顾一下发号器的性能：

  • 为每个长地址调配一个号码 ID
  • 并且须要避免地址歧义

以下对目前风行的分布式 ID 计划做简略介绍

计划 1：应用地址的 hash 编码作为 ID

能够通过 原始 Url 的 hash 编码，失去一个 整数，作为 短链的 ID

哈希算法简略来说就是将一个元素映射成另一个元素，

哈希算法能够简略分类两类，

  • 加密哈希，如 MD5，SHA256 等，
  • 非加密哈希，如 MurMurHash，CRC32，DJB 等。

MD5 算法

MD5 音讯摘要算法（MD5 Message-Digest Algorithm），一种被宽泛应用的明码散列函数，

能够产生出一个 128 位（16 字节）的散列值（hash value），

MD5 算法将数据（如一段文字）运算变为另一固定长度值，是散列算法的根底原理。

由美国明码学家 Ronald Linn Rivest 设计，于 1992 年公开并在 RFC 1321 中被加以标准。

CRC 算法

循环冗余校验（Cyclic Redundancy Check）是一种依据网络数据包或电脑文件等数据，

产生简短固定位数校验码的一种散列函数，由 W. Wesley Peterson 于 1961 年发表。

生成的数字在传输或者存储之前计算出来并且附加到数据前面，而后接管方进行测验确定数据是否发生变化。

因为本函数易于用二进制的电脑硬件应用、容易进行数学分析并且尤其长于检测传输通道烦扰引起的谬误，因而取得广泛应用。

MurmurHash

MurmurHash 是一种非加密型哈希函数，实用于个别的哈希检索操作。

由 Austin Appleby 在 2008 年创造，并呈现了多个变种，与其它风行的哈希函数相比，对于规律性较强的键，MurmurHash 的随机散布特色体现更良好。

这个算法曾经被很多开源我的项目应用，比方 libstdc++ (4.6 版)、Perl、nginx (不早于 1.0.1 版)、Rubinius、libmemcached、maatkit、Hadoop、Redis，Memcached，Cassandra，HBase，Lucene 等。

MurmurHash 计算能够是 128 位、64 位、32 位，位数越多，碰撞概率越少。

所以，能够把长链做 MurmurHash 计算，能够失去的一个整数哈希值，

所失去的短链，相似于上面的模式

固定短链域名 + 哈希值 = www.weibo.com/888888888

如何缩短域名？传输的时候，能够把 MurmurHash 之后的数字为 10 进制，能够把数字转成 62 进制

www.weibo.com/abcdef

那么，应用地址的 hash 编码作为 ID 的问题是啥呢？

会呈现碰撞，所以这种计划不适宜。

计划 2：数据库自增长 ID

属于齐全依赖数据源的形式，所有的 ID 存储在数据库里，是最罕用的 ID 生成方法，在单体利用期间失去了最宽泛的应用，建设数据表时利用数据库自带的 auto_increment 作主键，或是应用序列实现其余场景的一些自增长 ID 的需要。

然而这种形式存在在高并发状况下性能问题，要解决该问题，能够通过批量发号来解决，

提前为每台机器发放一个 ID 区间 [low,high]，而后由机器在本人内存中应用 AtomicLong 原子类去保障自增，缩小对 DB 的依赖，

每台机器，等到本人的区间行将满了，再向 DB 申请下一个区段的号码，

为了实现写入的高并发，能够引入 队列缓冲 + 批量写入架构，

等区间满了，再一次性将记录保留到 DB 中，并且异步进行获取和写入操作, 保障服务的继续高并发。

比方能够每次从数据库获取 10000 个号码，而后在内存中进行发放，当残余的号码有余 1000 时，从新向 MySQL 申请下 10000 个号码，在上一批号码发放完了之后，批量进行写入数据库。

然而这种计划，更适宜于单体的 DB 场景，在分布式 DB 场景下，应用 MySQL 的自增主键，会存在不同 DB 库之间的 ID 抵触，又要应用各种方法去解决，

总结一下，MySQL 的自增主键生成 ID 的优缺点和应用场景：

  • 长处：

    非常简单，有序递增，不便分页和排序。

  • 毛病：

    分库分表后，同一数据表的自增 ID 容易反复，无奈间接应用（能够设置步长，但局限性很显著）；

    性能吞吐量整个较低，如果设计一个独自的数据库来实现 分布式应用的数据唯一性，

    即便应用预生成计划，也会因为事务锁的问题，高并发场景容易呈现单点瓶颈。

  • 实用场景：

    单数据库实例的表 ID（蕴含主从同步场景），局部按天计数的流水号等；

    分库分表场景、全零碎唯一性 ID 场景不实用。

所以，高并发场景，MySQL 的自增主键，很少用。

计划 3：分布式、高性能的中间件生成 ID

Mysql 不行，能够思考分布式、高性能的中间件实现。

比方 Redis、MongoDB 的自增主键，或者其余 分布式存储的自增主键，然而这就会引入额定的两头组件。

如果应用 Redis，则通过 Redis 的 INCR/INCRBY 自增原子操作命令，能保障生成的 ID 必定是惟一有序的，实质上实现形式与数据库统一。

然而，超高并发场景，分布式自增主键的生产性能，没有本地生产 ID 的性能高。

总结一下，分布式、高性能的中间件生成 ID 的优缺点和应用场景：

  • 长处：

    整体吞吐量比数据库要高。

  • 毛病：

    Redis 实例或集群宕机后，找回最新的 ID 值有点艰难。

  • 实用场景：

    比拟适宜计数场景，如用户访问量，订单流水号（日期 + 流水号）等。

计划 4：UUID、GUID 生成 ID

UUID：

依照 OSF 制订的规范计算，用到了以太网卡地址、纳秒级工夫、芯片 ID 码和许多可能的数字。由以下几局部的组合：以后日期和工夫(UUID 的第一个局部与工夫无关，如果你在生成一个 UUID 之后，过几秒又生成一个 UUID，则第一个局部不同，其余雷同)，时钟序列，全局惟一的 IEEE 机器辨认号（如果有网卡，从网卡取得，没有网卡以其余形式取得）

GUID：

微软对 UUID 这个规范的实现。UUID 还有其它各种实现，不止 GUID 一种，不一一列举了。

这两种属于不依赖数据源形式，真正的寰球唯一性 ID

总结一下，UUID、GUID 生成 ID 的优缺点和应用场景：

  • 长处：

    不依赖任何数据源，自行计算，没有网络 ID，速度超快，并且寰球惟一。

  • 毛病：

    没有程序性，并且比拟长（128bit），作为数据库主键、索引会导致索引效率降落，空间占用较多。

  • 实用场景：

    只有对存储空间没有刻薄要求的都可能实用，比方各种链路追踪、日志存储等。

形式 5：snowflake 算法（雪花算法）生成 ID

snowflake ID 严格来说，属于 本地生产 ID，这点和 Redis ID、MongoDB ID 不同，后者属于近程生产的 ID。

本地生产 ID 性能高，近程生产的 ID 性能低。

snowflake ID 原理是应用 Long 类型（64 位），依照肯定的规定进行分段填充：工夫（毫秒级）+ 集群 ID+ 机器 ID+ 序列号，每段占用的位数能够依据理论须要调配，其中集群 ID 和机器 ID 这两局部，在理论利用场景中要依赖内部参数配置或数据库记录。

总结一下，snowflake ID 的优缺点和应用场景：

  • 长处：

    高性能、低提早、去中心化、按工夫总体有序

  • 毛病：

    要求机器时钟同步（到秒级即可），须要解决 时钟回拨问题

    如果某台机器的零碎时钟回拨，有可能造成 ID 抵触，或者 ID 乱序。

  • 实用场景：

    分布式应用环境的数据主键

高并发 ID 的技术选型

这里，不必地址的 hash 编码作为 ID

这里，不必数据库的自增长 ID

这里，不必 redis、mongdb 的分布式 ID

最终，

这里，从发号性能、整体有序（B+ 树索引构造更加敌对）的角度登程，最终抉择的 snowflake 算法

snowflake 算法的吞吐量在 100W ops +

然而 snowflake 算法 问题是啥呢？须要解决时钟回拨的问题。

如何解决时钟回拨的问题，能够参考 推特官网的 代码、百度 ID 的代码、Shardingjdbc ID 的源码，综合存储方案设计解决。

5、数据存储的高并发架构

这个数据，十分的结构化，能够应用结构化数据库 MYSQL 存储。

构造非常简单，咱们会有二列：1. ID，int,   // 分布式雪花 id；2. SURL，varchar,  // 原始 URL；

接下来，开始高并发、海量数据场景，须要进行 MYSQL 存储 的分库分表架构。

陈某提醒，这里能够说说本人的分库分表 操作教训，操作案例。

而后进行 互动式作答。

也就是，首先是进行 输出条件 询问，并且进行确认。

而后依照分治模式，进行两大维度的剖析架构：

  • 数据容量（存储规模）的 分治架构、
  • 拜访流量（吞吐量规模）的 分治架构。

这块内容涉的计划，不同的我的项目，根本是相通的。

6、二义性查看的高并发架构

所谓的地址二义性，就行同一个长址屡次申请失去的短址不一样。

在生产地址的时候，须要进行二义性查看，避免每次都会从新为该长址生成一个短址，一个个长址屡次申请失去的短址是不一样。

通过二义性查看，实现长短链接真正意义上的一对一。

怎么进行 二义性查看？

最简略，最为粗犷的计划是：间接去数据库中查看。

然而，这就须要付出很大的性能代价。

要晓得：

数据库主键不是 原始 url，而是 短链 url。

如果依据 原始 url 去进行存在性查看，还须要额定建设索引。

问题的要害是，数据库性能特低，没有方法撑持超高并发 二义性查看

所以，这里必定不能每次用数据库去查看。

这里很多同学可能会想到另一种计划，就是 redis 的布隆过滤，把曾经生成过了的 原始 url，

大抵的计划是，能够把曾经生成过的 原始 url，在 redis 布隆过滤器中进行记录。

每次进行二义性查看，走 redis 布隆过滤器。

布隆过滤器就是 bitset+ 屡次 hash 的架构，宏观上是空间换工夫，不对所有的 surl（原始 url）进行内容存储，只对 surl 进行存在性存储，这样就节俭大家大量的内存空间。

在数据量比拟大的状况下，既满足工夫要求，又满足空间的要求。

布隆过滤器的微小用途就是，可能迅速判断一个元素是否在一个汇合中。

布隆过滤器的罕用应用场景如下：

  1. 黑名单 : 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）
  2. URL 去重 : 网页爬虫对 URL 的去重，防止爬取雷同的 URL 地址
  3. 单词拼写查看
  4. Key-Value 缓存零碎的 Key 校验 (缓存穿透) : 缓存穿透，将所有可能存在的数据缓存放到布隆过滤器中，当黑客拜访不存在的缓存时迅速返回防止缓存及 DB 挂掉。
  5. ID 校验，比方订单零碎查问某个订单 ID 是否存在，如果不存在就间接返回。

Bloom Filter 专门用来解决咱们下面所说的去重问题的，应用 Bloom Filter 不会像应用缓存那么节约空间。

当然，他也存在一个小小问题，就是不太准确。

规定是：存在不肯定存在，说不存在肯定不存在

Bloom Filter 相当于是一个不太准确的 set 汇合，咱们能够利用它里边的 contains 办法去判断某一个对象是否存在，然而须要留神，这个判断不是特地准确。

一般来说，通过 contains 判断某个值不存在，那就肯定不存在，然而判断某个值存在的话，则他可能不存在。

那么对于 surl，解决的计划是：

  • 如果 redis bloom filter 不存在，间接生成
  • 否则，如果 redis bloom filter 判断为存在，可能是误判，还须要进行 db 的查看。

然而，redis bloom filter 误判的概率很低，正当优化之后，也就在 1% 以下。

可能有小伙伴说，如果 100Wqps，1% 也是 10W1ps，DB 还是扛不住，怎么办？

能够应用缓存架构，甚至多级缓存架构

具体来说，能够应用 Redis 缓存进行 热门 url 的缓存，实现局部地址的一对一缓存

比方将最近 / 最热门的对应关系存储在 K - V 数据库中，比方在本地缓存 Caffeine 中存储 最近生成 的长对短的对应关系，并采纳过期机制实现 LRU 淘汰，从而保障频繁应用的 URL 的总是对应同一个短址的，然而不保障不频繁应用的 URL 的对应关系，从而大大减少了空间上的耗费。

7、映射模块 (/ 转换模块) 高并发架构

这里，次要是介绍本人对 多级缓存的 把握和理解。

能够应用了缓存，二级缓存、三级缓存，放慢 id 到 surl 的转换。

简略的缓存计划

将热门的长链接（须要对长链接进来的次数进行计数）、最近的长链接（能够应用 Redis 保留最近一个小时的数据）等等进行一个缓存，如果申请的长 URL 命中了缓存，那么间接获取对应的短 URL 进行返回，不须要再进行生成操作

补充服务间的重定向 301 和 302 的不同

301 永恒重定向和 302 长期重定向。

  • 301 永恒重定向：第一次申请拿到长链接后，下次浏览器再去申请短链的话，不会向短网址服务器申请了，而是间接从浏览器的缓存里拿，缩小对服务器的压力。
  • 302 长期重定向：每次去申请短链都会去申请短网址服务器（除非响应中用 Cache-Control 或 Expired 暗示浏览器进行缓存）

应用 301 尽管能够缩小服务器的压力，然而无奈在 server 层获取到短网址的拜访次数了，如果链接刚好是某个流动的链接，就无奈剖析此流动的成果以及用于大数据分析了。

而 302 尽管会减少服务器压力，但便于在 server 层统计拜访数，所以如果对这些数据有需要，能够采纳 302，因为这点代价是值得的，然而具体采纳哪种跳转形式，还是要结合实际状况进行选型。

8、架构的魅力

架构魅力，在于没有最好的计划，只有更好的计划，大家如果有疑难，或者更好的计划，能够多多交换。

退出移动版