操作系统——webserver定时器的设计

数据结构：升序链表（我的项目使用的）、跳表、时间轮、红黑树、最小堆。

由于非活跃连接占用了连接资源，严重影响服务器的性能。

通过实现一个服务器定时器，处理这种非活跃连接，释放连接资源。

利用alarm函数周期性地触发SIGALRM信号，该信号的信号处理函数利用管道通知主循环执行定时器链表上的定时任务。

服务器的驱动逻辑：网络事件、定时事件、信号事件。

定时器在服务器端作用：

（1）多客户端连接服务器，需要通信发送数据包，有些客户端连接了长时间不干事，就需要断开。

（2）某些任务当前不想执行，需要一定时间之后执行。

如何实现定时器？

（1）单线程环境下：定时事件通常与网络事件协调处理。

举例：redix单线程，nginx多进程但是每个进程下都是单线程。

epoll_wait(epfd，用户态数组用于接收已经触发的事件，从网络协议栈最大取多少数据，没有事件到达时最长阻塞时间)。

epoll_wait和定时事件的绑定：定时时间是离散有序的一个链表上。最近要触发的定时器会作为epoll_wait的第四个参数。

    红黑树：平衡二叉搜索树   

平衡的规则：从根节点出发到任意叶子节点的黑节点数一定相等。

增加和删除的时候都会满足平衡规则，提供一个搜索稳定时间复杂度。

找最左侧的节点就可以找最小的节点，就可以找到最近要触发的定时器。 

O(logn)：100万个节点，比较20次；10亿个节点，比较30次。

（2）多线程环境下：

有一个单独的定时线程进行处理定时事件thread_timer。

采用时间轮结构实现定时器，跳表也可以，最小堆也可以。

时间轮知识：

时针、分针、秒针。时间精度是每一秒，时间范围是60。单层级时间轮是循环数组，使用取余来操作。(time%60)

插入任务时间复杂度永远是O(1)。不能执行删除任务。单层级中，数组的大小必须要大于 支持最大的定时任务。此外，0有任务，59有任务，中间没有，就会造成空推进的问题。

使用多层级的时间轮解决上述两个问题。分成秒层级（60）、分层级（60）、时层级（12）。

132解决数组太大的问题，接下来关注秒针运转。

跳表知识：

跳表是多层级有序链表。（有大量节点数据的时候才提高效率，本质还是二分查找，空间换时间）

 跳表可以通过加锁的方式，提供并发读写。每个节点都会存一个互斥锁。（值得做跳表KV存储引擎项目研究研究）

如果要插入8，先查找7到9之间，插入节点的时候分配三层1->8->20/1->7->8->20/...7->8->9....。

如果要删除节点7，加上原子变量，方便我们并发读。

跳表使用场景：rocksdb是kv数据库，有内存数据和磁盘数据，需要提供组织kv并提供并发读写。