网络编程高频总结七
epoll 底层为什么用红黑树不用hash
epoll 底层选择使用 红黑树 而不是 哈希表 主要是基于以下几个原因：
1. 动态修改事件的效率
epoll支持动态地添加、删除或修改监听的文件描述符（FD）。- 红黑树是一个 自平衡二叉搜索树，可以在 O(logn) 的时间复杂度下完成插入、删除和查找操作。
- 如果使用哈希表，插入和删除操作的效率取决于哈希函数和冲突解决机制，最差情况下可能退化为 O(n)，特别是当哈希表需要扩容时，开销会更高。
2. 有序性
- 红黑树能够保持节点的有序性，便于高效地进行范围查询。
- 尽管
epoll的主要操作是根据文件描述符进行查找和修改，暂时不需要范围查询，但红黑树的有序性在某些特定场景中（比如批量操作时）可能会带来优势。 - 哈希表不具备天然的有序性，如果需要有序性，还需要额外的数据结构支持。
3. 内存管理
- 哈希表的性能依赖于负载因子。如果负载因子过高，可能会导致大量冲突，从而降低效率；如果负载因子过低，则会浪费大量内存。
- 红黑树的内存使用更加稳定，不需要扩容或缩容的操作。
4. 扩展性和线程安全
epoll的实现需要适应各种文件描述符的动态操作，并保证在多线程环境下的一致性。- 红黑树的结构在扩展性和线程安全的实现上相对更容易管理，而哈希表在高负载下容易出现锁竞争的问题。
5. 事件分发的公平性
- 红黑树的自平衡特性确保了插入和删除操作不会让某些操作长期延迟，从而保持系统的响应公平性。
- 哈希表的性能可能会因为冲突而受到影响，导致某些文件描述符的操作耗时变长。
6. 设计的灵活性
epoll采用红黑树来管理监听的文件描述符，同时配合一个链表来管理触发的事件。红黑树用于快速查找和修改文件描述符，而链表用于高效地分发事件。- 如果只用哈希表，可能会对这种分离的设计造成一定限制。
总结
红黑树在 性能稳定性、内存管理 和 动态操作支持 等方面相较于哈希表更具优势。而哈希表更适合用在静态查找场景，比如数据量固定且查找频繁时。epoll 的场景需要频繁动态修改监听的文件描述符，因此红黑树是更合适的选择。
ET和LT的区别、IO多路复用
ET 和 LT 模式的区别
epoll 提供了两种事件触发模式：ET（边沿触发，Edge Triggered） 和 LT（水平触发，Level Triggered）。它们的区别主要体现在触发机制上。
1. 水平触发（LT, Level Triggered）
- 工作机制： LT 是默认的触发模式，当
epoll监测到某个文件描述符上有事件发生时，会持续通知用户（只要数据未被完全读取或缓冲区未被完全处理）。 即使用户程序暂时没有处理，epoll仍会在下次调用时通知。 - 特点：
- 简单易用，行为类似于
select和poll。 - 程序无需特别注意状态变化，事件处理可能多次重复触发。
- 通常需要逐步读取或写入数据，直到没有数据可读或缓冲区已满。
- 简单易用，行为类似于
- 适用场景：
- 适合绝大多数 IO 应用场景。
- 易于编程和调试。
2. 边沿触发（ET, Edge Triggered）
- 工作机制： ET 仅在文件描述符状态从未就绪变为就绪时触发通知，并且只通知一次。 如果程序未能处理所有数据，
epoll不会再次通知，程序需要自行处理剩余数据。 - 特点：
- 高效，只在状态变化时触发，避免了频繁的事件通知。
- 要求用户程序确保将文件描述符的数据读取或写入到空（非阻塞模式下）。
- 编程复杂度较高，容易因未处理完数据而出现问题。
- 适用场景：
- 高性能、高吞吐量的网络服务器。
- 程序员可以控制非阻塞 IO，确保一次性读取或写入数据。
对比总结
| 特性 | 水平触发 (LT) | 边沿触发 (ET) |
|---|---|---|
| 触发机制 | 数据未处理完会重复通知 | 状态变化时仅通知一次 |
| 编程复杂度 | 简单 | 较高 |
| 性能 | 较低（可能重复通知） | 较高（避免重复通知） |
| 适用场景 | 普通网络 IO | 高性能网络服务 |
IO 多路复用
概念
IO 多路复用是一种允许单个线程或进程同时监听多个 IO 文件描述符（FD）的技术。当任何一个 FD 有事件发生时，程序会得到通知，从而避免阻塞在单一 IO 上。
常见的 IO 多路复用技术有：
selectpollepoll（Linux 专有）
常见的 IO 多路复用机制对比
| 特性 | select | poll | epoll |
|---|---|---|---|
| 引入时间 | 早期 UNIX 系统 | 后续改进 | Linux 2.6 |
| 文件描述符限制 | 有限制（通常 1024） | 无限制 | 无限制 |
| 文件描述符存储方式 | 位图（数组） | 链表 | 红黑树 + 链表 |
| 检测方式 | 线性遍历 | 线性遍历 | 事件驱动 |
| 性能 | 随文件描述符数增加而降低 | 随文件描述符数增加而降低 | 高性能，适合大并发 |
| 适用场景 | 小规模并发 | 中小规模并发 | 大规模并发 |
epoll 的核心机制
- epoll_create 创建一个 epoll 实例，返回一个 epoll 文件描述符。
- epoll_ctl 操作（增加、删除、修改）监听的文件描述符。
- epoll_wait 等待事件发生，并返回发生事件的文件描述符集合。
总结
- ET vs LT：ET 高效但复杂，适合高性能场景；LT 简单易用，适合大多数普通应用。
- IO 多路复用：
epoll是目前 Linux 下高效的多路复用机制，适用于大规模并发场景。
游戏中数据传输用啥协议（有没有改进的协议，基于UDP的可靠传输）
在游戏中，数据传输协议的选择通常取决于数据的实时性和可靠性要求。以下是常用协议以及改进的方案，尤其是基于 UDP 的可靠传输：
1. 常用协议的选择
TCP（Transmission Control Protocol）
- 优点：
- 提供可靠传输，数据包按顺序到达。
- 内置流量控制和拥塞控制，适合高可靠性需求的场景。
- 缺点：
- 延迟较高，连接建立和数据重传带来开销。
- 无法满足高实时性要求（如玩家位置更新或操作同步）。
- 适用场景：
- 游戏中的登录认证、商城交易、排行榜查询等非实时性操作。
UDP（User Datagram Protocol）
- 优点：
- 简单、高效，无连接性，无需重传或顺序保障。
- 低延迟，适合实时性要求高的场景。
- 缺点：
- 不可靠，可能丢包或乱序。
- 开发者需要自己实现可靠性机制（如确认、重传）。
- 适用场景：
- 实时性要求高的场景，如角色移动、状态广播、技能释放等。
2. 基于 UDP 的改进协议
为了弥补 UDP 不可靠传输的缺点，同时保留其低延迟优势，许多游戏引擎和网络库实现了自定义可靠传输协议，以下是几种常见改进方案：
a) QUIC（Quick UDP Internet Connections）
- 特性：
- Google 开发的一种基于 UDP 的传输协议。
- 提供可靠性、加密和多路复用，类似于 TCP，但性能更高。
- 适用于对安全性和性能要求较高的游戏场景。
- 优点：
- 内置可靠性和流量控制。
- 支持低延迟连接建立和加密通信。
- 适用场景：
- 游戏中的下载服务、语音聊天等需要可靠性和安全性的场景。
b) KCP
- 特性：
- 一种基于 UDP 的可靠传输协议，设计简单，开源。
- 提供重传、流控、丢包检测等功能。
- 优点：
- 延迟低，特别适合弱网络环境。
- 易于集成到游戏引擎中。
- 适用场景：
- 实时性和可靠性都有一定要求的游戏数据传输。
c) ENet
- 特性：
- 专为实时应用设计的轻量级网络协议库。
- 在 UDP 基础上实现了可靠传输和顺序控制。
- 优点：
- 支持可靠和不可靠的数据包传输。
- 开发简单，广泛用于游戏引擎。
- 适用场景：
- 游戏的实时网络通信，如多玩家同步。
d) RakNet
- 特性：
- 专为游戏设计的网络库，提供可靠 UDP 传输和多种功能（如 NAT 穿透）。
- 支持包排序、分片、重组等功能。
- 优点：
- 功能强大，支持游戏中的复杂网络需求。
- 适用场景：
- 中大型多人在线游戏。
e) 自定义协议
开发者也可以根据游戏的需求，在 UDP 的基础上实现自定义协议：
- 特性：
- 实现数据包确认、重传、超时检测。
- 根据场景选择可靠和不可靠的传输方式。
- 优点：
- 灵活性高，可以针对具体需求进行优化。
- 缺点：
- 开发复杂，需要自行处理网络的细节问题。
3. 协议选择的建议
分场景选择
- 高实时性数据（位置、动作）：
- 使用 UDP 或基于 UDP 的可靠传输（如 ENet、KCP）。
- 不可靠传输的丢包少量丢失不会显著影响游戏体验。
- 可靠性高的数据（状态同步、结果确认）：
- 使用改进的 UDP 协议（如 KCP、ENet）或 TCP。
- 混合协议架构：
- 游戏中同时使用 TCP 和 UDP，分别处理可靠和实时性数据。
基于网络环境的选择
- 低延迟、丢包率低的环境：
- 原生 UDP 或改进协议（如 ENet、KCP）。
- 高丢包率、弱网络环境：
- 优先考虑 KCP、QUIC 等改进协议。
4. 实际应用案例
- KCP：
- 常用于实时对战类游戏（如 MOBA 游戏）中，确保实时同步和较低丢包率。
- ENet：
- 被广泛应用于中小型多人在线游戏，平衡实时性和可靠性。
- QUIC：
- 多用于跨网络传输，特别是结合 WebRTC 的语音或视频数据传输。
- 自定义协议：
- 大型多人在线游戏（如《英雄联盟》、《绝地求生》）通常基于 UDP 自行开发传输层协议，优化特定场景的网络性能。
总结
对于游戏开发，基于 UDP 的改进协议（如 KCP 或 ENet）是一个常见且有效的选择，可以在保持低延迟的同时提供一定的可靠性和顺序保证。此外，根据游戏的需求，也可以灵活组合 TCP 和 UDP，或者设计自定义协议以实现最佳效果。
项目架构（webserver）两种高并发模式
在 Web 服务器的高并发架构设计中，常用的两种模式是 多线程/多进程模式 和 事件驱动模式。它们各有优缺点，适用于不同的场景。
1. 多线程/多进程模式
基本原理
- 每个请求由一个线程或进程处理。
- 主线程/进程负责监听请求，当有新的请求到来时，将其交给子线程/进程处理。
- 通过线程池或进程池限制线程/进程的数量，避免资源耗尽。
特点
- 优点：
- 编程模型简单直观，每个线程/进程独立处理一个请求，逻辑清晰。
- 利用多核 CPU，多个线程或进程可以并行执行。
- 隔离性好：进程间相互独立，一个进程的崩溃不会影响其他进程。
- 缺点：
- 线程/进程切换的开销较大，尤其是当请求数量远超系统承载能力时，性能会显著下降。
- 线程/进程的资源消耗较高（如栈内存、内核调度等）。
- 难以处理长连接场景，因为每个连接都会占用一个线程或进程。
实现方式
- 简单多线程/多进程：
- 每接收到一个请求，创建一个新的线程/进程处理。
- 缺点是频繁的创建和销毁线程/进程开销大。
- 线程池/进程池：
- 提前创建一定数量的线程或进程，减少频繁创建和销毁的开销。
- 主线程分发任务到线程池/进程池。
适用场景
- 请求数量适中，且每个请求的处理时间较长（如 CPU 密集型任务）。
- 系统资源（内存和 CPU）充足。
示例
- 传统的 Apache HTTP Server 使用多进程模式。
- 基于多线程的 Tomcat Web 服务器。
2. 事件驱动模式
基本原理
- 基于事件循环，主线程使用非阻塞 IO 和 IO 多路复用（如
epoll、kqueue）监听所有连接的事件（如读、写）。 - 主线程通过回调机制分发事件，而不需要为每个连接创建独立的线程。
特点
- 优点：
- 极低的线程/进程切换开销，因为通常只使用少量线程（甚至单线程）处理所有请求。
- 内存占用低，每个连接只需要一个小的状态对象。
- 极高的并发能力，可以支持数万甚至百万级的并发连接。
- 缺点：
- 编程复杂度较高，开发者需要处理异步回调和状态管理。
- 单线程模型在处理 CPU 密集型任务时可能会阻塞整个事件循环。
- 对长耗时操作（如磁盘 IO）需要额外设计机制（如线程池或协程）。
实现方式
- 单线程事件驱动：
- 单个线程处理所有连接，依赖异步 IO 和回调。
- 如 Node.js 的单线程事件循环。
- 多线程事件驱动：
- 使用多个线程，每个线程维护自己的事件循环，适用于多核系统。
- 如 Nginx 的 Worker 模型。
- 协程事件驱动：
- 基于协程的非阻塞编程模型，简化了状态管理，逻辑更接近同步代码。
- 如 Go 的 Goroutine 和基于协程的 Python 异步框架。
适用场景
- 高并发、长连接场景，如即时通信、实时游戏、WebSocket、在线直播。
- 请求处理简单、主要是网络 IO（如反向代理、静态资源分发）。
示例
- Nginx 使用多线程事件驱动模式。
- Node.js 使用单线程事件驱动模式。
对比总结
| 特性 | 多线程/多进程模式 | 事件驱动模式 |
|---|---|---|
| 资源消耗 | 较高，线程/进程需要更多内存 | 较低，仅需少量线程和状态管理 |
| 并发能力 | 中等，受线程/进程数限制 | 极高，支持数万甚至百万级连接 |
| 开发难度 | 简单，逻辑接近同步编程 | 较高，需要处理异步逻辑和状态管理 |
| 适用场景 | 请求量中等，任务复杂的场景 | 高并发、轻量 IO 场景 |
| 性能瓶颈 | 线程/进程切换开销 | 单线程可能成为瓶颈，需配合协程 |
混合模式
为了兼顾多线程和事件驱动的优点，许多现代 Web 服务器采用了
混合模式：
- 使用主线程的事件驱动模型处理网络 IO。
- 使用线程池/协程池处理 CPU 密集型或长耗时任务。
示例架构
- 主线程使用
epoll或类似机制监听网络事件。 - 收到请求后，根据请求类型：
- 短任务直接处理（如简单的状态查询）。
- 长任务或 CPU 密集型任务分发到线程池处理。
- 处理结果通过回调写回客户端。
示例
- Nginx + Lua：使用事件驱动处理网络请求，结合 Lua 脚本进行灵活扩展。
- Go Web 框架：使用协程并发处理网络和业务逻辑。
总结
- 多线程/多进程模式适合简单项目或传统架构，易于理解和实现，但扩展性有限。
- 事件驱动模式是现代高并发 Web 服务器的主流架构，性能优异，尤其适合高并发场景。
- 对于复杂项目，可以结合两种模式的优势，采用混合架构以提高并发能力和灵活性。
除了Reactor模型，还有什么模型
除了 Reactor 模型，在高并发服务端设计中，还有一些其他经典的模型，比如 Proactor 模型、线程池模型、事件驱动模型 等。这些模型的选择和使用依赖于应用场景和系统需求。
1. Proactor 模型
概念
- 与 Reactor 模型不同，Proactor 模型将主要的事件处理工作交给操作系统完成。应用程序只需定义完成事件的回调逻辑。
- 操作系统完成异步 IO 操作后，会通知应用程序，触发相应的事件处理。
工作流程
- 应用程序发起异步 IO 操作，并提供一个完成回调函数。
- 操作系统负责监控 IO 操作的完成情况。
- 当 IO 操作完成后，操作系统通知应用程序，由应用程序执行回调逻辑处理结果。
优点
- 异步 IO 操作由操作系统完成，减少了应用层的复杂性。
- 减少了 IO 操作的阻塞，提高了资源利用率。
缺点
- 依赖操作系统的异步 IO 支持，跨平台适配可能存在问题。
- 开发复杂度较高，需要深入理解异步编程。
应用场景
- Windows 中的 IOCP（Input/Output Completion Port）。
- Boost.Asio 提供了 Proactor 风格的接口。
2. 多线程模型
概念
- 使用多个线程处理不同的请求。
- 每个线程独立完成 IO 和业务逻辑处理。
实现方式
- 单线程每连接：
- 为每个连接创建一个线程。
- 简单但资源浪费严重，线程切换开销大。
- 线程池：
- 通过线程池复用固定数量的线程，避免频繁创建和销毁线程的开销。
- 比每连接一个线程更高效，但仍需处理线程间的数据同步问题。
优点
- 模型直观，逻辑清晰，编程难度低。
- 能够充分利用多核 CPU。
缺点
- 线程切换开销大。
- 内存占用高，每个线程需要独立的栈空间。
- 同步和锁机制可能导致性能瓶颈。
应用场景
- 多数传统 Web 服务器（如 Apache）。
- 适合任务量较重、并发量中等的场景。
3. 事件驱动模型
概念
- 基于事件循环，通过 IO 多路复用（如
epoll、kqueue）处理多个连接的 IO 事件。 - 主线程处理所有事件，异步分发任务到回调函数。
优点
- 高效，避免了线程切换和阻塞操作。
- 资源占用少，适合高并发场景。
缺点
- 编程复杂，需处理异步回调和状态管理。
- 单线程可能成为瓶颈，尤其是 CPU 密集型任务。
应用场景
- 高并发网络服务，如 Nginx、Redis。
- Node.js 也是基于事件驱动模型。
4. Actor 模型
概念
- Actor 是一种轻量级并发单元，每个 Actor 有独立的状态和行为，通过消息传递进行交互。
- Actor 模型强调无共享内存，完全通过消息通信。
工作方式
- 每个 Actor 有自己的私有状态。
- Actor 之间通过异步消息传递进行通信。
- Actor 的处理逻辑由接收到的消息驱动。
优点
- 消息通信机制使得 Actor 模型天然支持并发，减少了锁和同步问题。
- 扩展性强，适合分布式系统。
缺点
- 需要设计高效的消息传递机制。
- Actor 之间通信的延迟可能导致性能下降。
应用场景
- 分布式系统，如 Akka 框架。
- 高并发聊天系统、实时处理系统。
5. 半同步半异步（Half-Sync/Half-Async）模型
概念
- 结合同步和异步两种处理方式：
- IO 操作采用异步模型。
- 业务逻辑处理采用同步模型。
工作流程
- 异步线程负责处理 IO 事件。
- IO 事件触发后，将请求交给同步线程池处理。
- 同步线程处理完业务逻辑后，返回结果给异步线程。
优点
- 将复杂的 IO 异步操作与简单的业务同步处理分开，开发简单。
- 能够同时兼顾高并发和复杂任务处理。
缺点
- 线程池的性能瓶颈可能限制系统扩展性。
应用场景
- 混合场景，既需要高并发也需要复杂逻辑的处理。
- 常用于现代 Web 服务器。
6. Leader-Follower 模型
概念
- 多线程协作模型，线程池中的线程分为 Leader 和 Follower。
- Leader 线程负责监听事件。
- 当事件触发时，Leader 线程处理该事件，Follower 线程接替成为新的 Leader。
优点
- 提高线程利用率，避免线程闲置。
- 线程间的协作减少了线程切换开销。
缺点
- 实现复杂，需要管理线程角色的转换。
- 不适合 CPU 密集型任务。
应用场景
- 高性能服务器中，需要优化线程利用率的场景。
总结对比
| 模型 | 优点 | 缺点 | 应用场景 |
|---|---|---|---|
| Reactor | 高效，适合高并发 | 编程复杂，需手动处理状态和异步 | 网络服务器，如 Nginx、Redis |
| Proactor | 简化异步操作，性能高 | 依赖操作系统支持，复杂性高 | IO 密集型应用，如 Windows IOCP |
| 多线程/多进程 | 模型简单，易于实现 | 高资源消耗，线程/进程切换开销大 | Apache、传统 Web 服务器 |
| 事件驱动 | 极高并发能力，资源占用低 | 编程复杂，单线程可能成为瓶颈 | 高并发场景，如 Nginx、Node.js |
| Actor | 天然并发，无共享状态 | 通信延迟可能影响性能 | 分布式系统，如 Akka、Erlang |
| Half-Sync/Half-Async | 结合同步与异步，兼顾效率和复杂逻辑 | 线程池可能成为瓶颈 | 混合需求场景 |
| Leader-Follower | 优化线程利用率 | 实现复杂，线程协作成本高 | 高性能服务器 |
实际选择建议
- 高并发、低延迟场景：选择 Reactor 或 事件驱动模型。
- IO 密集型任务：选择 Proactor 模型。
- 复杂业务逻辑、多核 CPU 任务：选择 多线程模型 或 半同步半异步模型。
- 分布式系统：选择 Actor 模型。
- 多线程优化：选择 Leader-Follower 模型。
本文由作者按照 CC BY 4.0 进行授权