jemmyh / gogoredis Goto Github PK

eventfd 是一种linux上的线程通信方式，和信号量等其他线程通信不同的是，eventfd 可以用于进程间的通信，还可以用于内核发信号给用户态的进程，eventfd 是linux上的系统调用，本质上是用于事件通知。这种文件 fd 无法传输数据，只能用来传输事件，通常用于生产者消费者模式的事件实现。

本 issue 旨在明确 eventfd 的用法，为说明原理会对对其实现细节作简要描述。

文件描述符(file descriptor) 在 Linux编程 里随处可见，设备读写、网络通信、进程通信，fd 可谓是关键中的关键。
深入理解可以增加我们使用它的信心。

进程没活干的时候让它“睡眠”，等有活干的时候再“唤醒”它。怎么找到这个已经睡着的进程让它醒来？

这一切，都是通过一个叫 等待队列 的数据结构实现的。

在 Redis 单线程事件循环 中我们提到，Redis 自己实现了一个高性能事件库：aeEventLoop，本次借助 Allenxuxu/gev 的开源实现，希望能明确一个事件库的工作流程，并通过源码分析的方式理解其原理。

延迟队列是管理延时任务的一种方式。你可以往里面添加定时任务(Offer)，它会一直轮训等待(Poll)同时将指定时间点到期的任务告诉调用方。
它的实现依赖于优先级队列，关于优先级队列的实现，可以看 最小堆 以及 优先级队列的 Golang 实现。

本 issue 的目的是使用 Golang 实现一个 DelayQueen，为后续的 时间轮 的实现做准备。

看源码，fd_set 这个结构体实际上是一个 long 型的数组，但是数组的长度依赖于系统中 typedef long int __fd_mask 的长度。当我去调试的时候，经常打印出一些很奇怪的值，有时候还会溢出。

此 issue 旨在抛开 select 相关的功能，彻底搞明白 fd_set 的存储原理、FD_SET() 等函数到底实现了什么效果。

The reactor design_pattern is an event_handling pattern for handling service requests delivered concurrently to a service handler by one or more inputs. The service handler then demultiplexes the incoming requests and dispatches them synchronously to the associated request handlers. ----Wili--Reactor_pattern

Reator 是一种事件处理模型，并发处理请求，然后对请求进行多路分解，并将它们同步分派给关联的请求处理程序。本 issue 旨在搞清楚此模型的运作方式、高效的原因 以及 有哪些对其进行的相关改进措施。

为什么会有 时间轮 这个概念？先看一个场景：在商品抢购项目中，短时间内会创建几百万个定时任务，创建的时候更新某个参数，一段时间以后再去核对，将与逻辑不符合的任务处理。

Golang 内置的 Timer 是采用最小堆来实现的，创建和删除的时间复杂度都为 O(log n)。如果有上万的连接，每个连接都会有很多超时任务，比如发送超时、心跳检测等，如果每个超时任务都对应一个 Timer，性能会比较低下。

论文 Hashed and Hierarchical Timing Wheels 提出了一种用于实现 Timer 的高效数据结构：时间轮。采用时间轮实现的 Timer，创建和删除的时间复杂度为 O(1)。

本次借助已有的实现 RussellLuo/timingwheel: Golang implementation of Hierarchical Timing Wheels. 说明原理。该作者的实现中并没有按照常规的使用类似钟表那样的环形数组，而是参考了 kafka 的实现，在这个实现中，需要用到两个组件：

• 优先级队列
• DelayQueen

本 issue 的目标是明白层级时间轮的运作原理以及从源码层面上理解上述项目实现的细节。

堆，是计算机科学中的一种特别的完全二叉树。若父节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作 根节点（root node），根节点本身没有 父节点（parent node）。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

优先级队列 是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

在关注 redis 单线程/多线程 时，有几个重要的时间节点：

1. Before Redis v4.0，真正的单线程；
2. Redis v4.0，引入多线程处理 AOF 等任务，但核心的网络模型中依旧使用单线程；
3. Redis v6.0，正式在网络模型中实现 I/O 多线程。

从 Redis v1.0 到 Redis v6.0以前，Redis 的核心网络模型一直都是一个典型的 单Reactor模型，所有的事件都在这个线程内处理完成。本 issue 旨在解释清楚这个 单Reactor模型 的所有运作细节，为以后更好地理解新的 Multi-Reactors/Master-Workers 模型做准备。

注：本文基于 Redis v5.0.0 版本分析。