12306 秒杀系统

date
May 23, 2023
slug
12306-spike-system
status
Published
tags
Code
summary
使用单机模拟高并发抢票的核心逻辑
type
Post
Created Time
Oct 28, 2023 01:45 PM
Updated Time
Oct 28, 2023 01:45 PM
AI summary
Status
12306 的秒杀系统，一直以来，都被誉为是比双十一更有技术含量的秒杀系统，这篇文章用简单的方式，本地模拟了这一系统的运作过程，今天，梳理一下文章中提到的技术。

三层负载均衡

高并发的系统都会采用分布式集群部署，从用户请求到服务器，会经历三层的负载均衡，依次分别是：OSPF（Open Shortest Path Fisrt）负载均衡 → LVS（Linux Virtual Server）负载均衡 → Nginx 负载均衡。

OSPF（Open Shortest Path First）开放式最短路径优先

OSPF 是广泛使用的，基于 IP 协议的路由协议，它采用戴克斯特拉算法（ Dijkstra's algorithm）来计算最短路径树，使用“开销（Cost）”作为路由度量指标，开销由 OSPF 自动计算（也可以手动指定，手动指定的优先级高于自动计算的结果），对于开销相同的目标路径，会执行负载均衡（最多 6 条）。

运行机制

  1. 从所有启动 OSPF 协议的接口上发送 Hello 报文，形成邻居关系；
  1. 形成邻接关系的路由器之间“交流” LSA（Link State Advertisement，链路信息，包含链路、接口、邻居及链路状态等信息）；
  1. 路由器将收集到的 LSA 汇总记录在 LSDB （Link State DataBase，链路状态数据库）中，形成带权有向图；
  1. 每一个路由器都以其自身为根，使用戴克斯特拉算法（ Dijkstra's algorithm）计算出它到达每一个目的地的最短路径（所有路由器计算所形成的无环路拓扑图就是最短路径树）；
  1. 邻居之间继续发送 Hello 报文进行保活，周期性的重传 LSA（Link State Advertisement，链路信息），进行数据的实时更新。

支持的网络类型

  • 广播类型（Broadcast）；
  • 非广播-多路访问网络（Non-Broadcast Multiple Access，NBMA）；
  • 点到点的 P2P 类型（Point-to-Point）
  • 点到多点的 P2MP 类型（Point-to-Multipoint）

优点

  • OSPF 具有完整的网络拓扑知识，允许路由器根据传入的请求计算路由。
  • OSPF 没有跳数限制，不像 RIP (Routing Information Protocol，路由信息协议）最多只有 15 跳，所以 OSPF 的收敛速度比 RIP 快，并且具有更好的负载均衡。
  • OSPF 多播链路状态更新并仅在网络发生变化时发送更新。

缺点

  • OSPF 需要有关复杂网络的高级知识，因此不像其他一些协议那样容易学习。
  • 当有更多路由器添加到网络时，OSPF 路由不会扩展。OSPF 协议缺乏可扩展性使其不适合跨 Internet 路由。
  • OSPF 协议维护路由信息的多个副本，增加了所需的内存量。

Linux 虚拟服务器 Linux Virtual Server，LVS）

Linux 虚拟服务器（Linux Virtual Server，LVS）是一个虚拟的服务器集群系统，1998 年 5 月由章文嵩发起，是中国国内最早出现的开源项目之一，目前已经被集成到 Linux 内核模块中。该项目在 Linux 内核中实现了基于 TCP 层的 IP 数据负载均衡分发，因为其工作在内核空间，且只做负载均衡分发处理这一件事，所以稳定性较好，性能较强，对内存及 CPU 资源的消耗也比较低。

iptables 的四表五链

如下图：
图片来自 TinyChen
图片来自 TinyChen
图中使用箭头展示了用户访问使用 iptables 的机器的过程。
iptables 的四个表：
  • filter 表（默认表）：用来对数据包进行过滤，决定如何处理一个数据包。对应的内核模块为：iptable_filter，表内包括三个链：INPUT、FORWARD、OUTPUT；
  • nat 表：全称为 network address translation 网络地址转换，主要用来修改数据包的 IP 地址、端口号信息。对应的内核模块为：iptable_nat，表内包括三个链：PREROUTING、POSTROUTING、OUTPUT；
  • mangle 表：主要用来修改数据包的服务类型，生存周期，为数据包设置标记，实现流量整形、策略路由等。对应的内核模块为：iptable_mangle，表内包括五个链：PREROUTING、postrouting、INPUT、OUTPUT、FORWARD；
  • raw 表：主要用来决定是否对数据包进行状态跟踪。对应的内核模块为：iptable_raw，表内包括两个链：OUTPUT、PREROUTING；
如图所示，raw 表是 PREROUTING 链和 OUTPUT 链的第一个环节，利用这个特点，raw 的一个应用场景就是跳过地址转换和数据包的链接跟踪，提高性能，即在不需要做 nat 的时候直接跳过 nat 表和 ip_conntrack 处理。
iptables 的五个链：
  • INPUT 链：当收到访问防火墙本机地址的数据包时，将应用此链中的规则；
  • OUTPUT 链：当防火墙本机向外发送数据包时，将应用此链中的规则；
  • FORWARD 链：当收到需要通过防火中转发给其他地址的数据包时，将应用此链中的规则，注意如果需要实现 forward 转发需要开启 Linux 内核中的 ip_forward 功能；
  • PREROUTING 链：在对数据包做路由选择之前，将应用此链中的规则；
  • POSTROUTING 链：• 在对数据包做路由选择之后，将应用此链中的规则；

基本工作原理

Director 服务器：直接接收用户请求的服务器，是 LVS 的入口。 Real Server 服务器：真实服务器，用于处理用户请求的服务器。 虚拟 IP（VIP）：对外网暴露的 IP 地址，客户端可以通过 VIP 访问 LVS 集群。
LVS 的 IP 负载均衡技术是通过 IPVS 模块来实现的，IPVS 是 LVS 集群系统的核心软件，它的主要作用是：在 Director Server上虚拟出一个 IP 地址，用户通过这个虚拟的 IP 地址访问服务器。访问的请求首先经过 VIP 到达负载调度器，然后由负载调度器从 Real Server 列表中选取一个服务节点响应用户的请求。

lVS 的三种工作模式

  • NAT 模式（网络地址转换）
    • 原理：负载均衡器修改请求、响应报文中的目标 IP。
    • 优点：物理服务器可以使用任何 TCP/IP 协议进行数据传输，只有负载均衡器需要一个合法的 IP 地址。
    • 缺点：扩展性较差，因为所有的请求包和应答包都经过负载均衡器，当服务节点过多时，负载均衡器可能成为瓶颈。
  • DR 模式（直接路由）
    • 原理：操纵封装新的 MAC 地址，把目的 MAC 地址改为 Real Server 的 MAC（因为 IP 一致）并将请求分发给这台 Real Server。
    • 优点：不需要隧道结构，且负载均衡器只用于分发，不会成为瓶颈（应答包能够通过单独的路由方式返回给客户端）。
    • 缺点：要求负载均衡器的网卡必须与物理网卡在同一个物理段上。
  • TUN 模式（IP 隧道）
    • 原理：在原请求 IP 报文中封装处理新的 IP 头。
    • 优点：减少了负载均衡器的数据流量，一台负载均衡器能够为多个 Real Server 处理分发，而且可以在公网上进行地域分发。
    • 缺点：每一个 Real Server 都需要合法 IP，且所有服务器都需要支持隧道协议（Tunneling Protocol）。

ipvsadm（IPVS Administration）

ipvsadm 主要用于管理 Linux 虚拟服务器的集群服务，对真实服务进行增、删、改、查。

Nginx

Nginx（发音同“engine X”）是异步框架的网页服务器，也可以用作反向代理、负载平衡器和HTTP缓存。Nginx 实现负载均衡的方式主要有三种：轮询模式、加权轮询、ip hash 轮询。

轮询模式（默认）

在轮询模式中，请求按时间顺序，逐一分配到 Web 层服务，然后周而复始，如果 Web 层服务挂掉，自动将其剔除。
由于该算法中每个请求按时间顺序逐一分配到不同的服务器处理，因此适用于服务器性能相近的集群情况，使每个服务器承载相同的负载。但对于服务器性能不同的集群而言，该算法容易引发资源分配不合理等问题。

加权轮询

在加权轮询中，每个服务器会有各自的权重。一般情况下，weight 的值越大意味着该服务器的性能越好，可以承载更多的请求。该模式中，客户端的请求按权重比例进行分配，当一个请求到达时，优先为其分配权重较大的服务器。
加权轮询可以应用于服务器性能不等的集群中，使资源分配更加合理化。其核心思想是，遍历各服务器节点，并计算节点权值，计算规则为 current_weight 与其对应的 effective_weight 之和，每轮遍历中选出权值最大的节点作为最优服务器节点。其中 effective_weight 会在算法的执行过程中随资源情况和响应情况而改变。
源码在这里，源码分析可参考这篇文章。

ip hash 轮询

在 ip hash 轮询中，依据发出请求的客户端 IP 的 hash 值来分配服务器，该算法可以保证同一个 IP 发出的请求能够映射至同一服务器，或者具有相同 hash 值的不同 IP 映射到同一服务器。
该算法在一定程度上解决了集群部署环境下 Session 不共享的问题。
Session 不共享问题是说，假设用户已经登录过，此时发出的请求被分配到了 A 服务器，但 A 服务器突然宕机，用户的请求则会被转发到 B 服务器。但由于 Session 不共享，B 无法直接读取用户的登录信息来继续执行其他操作。

分层、异步业务处理

秒杀系统在真实业务中的实现是非常复杂的，这里只是简单用单机模拟了一下场景，我自己实现的代码在这里，原作者烟花易冷 DarkPrince 实现的代码在这里。
总的思路如下：
  • 使用 Nginx 加权平衡策略将所有用户的请求均衡分配到多台机器上，这样单机承受的并发量就小了很多。
  • 在进行抢票时，服务器不仅要在本地减库存，还要在远程统一减库存。这样设计的目的是为了更好的保护远程仓库，将一部分流量在过滤。
  • 每个机器上都会多预留一部分余票，避免某个机器宕机导致余票卖不出去。
  • 本地仓库和远程仓库的减库存需要确保是一个原子性操作，因此，远端仓库需要使用分布式锁，并且用事务的方式进行减库存。

© 孙东辉 2022 - 2024