在几点几分做某件事是 RPC 框架的基本需求，这件事比看上去难。
让我们先来看看系统提供了些什么：posix 系统能以 signal 方式告知 timer 触发，不过 signal 逼迫我们使用全局变量，写 async-signal-safe 的函数，在面向用户的编程框架中，我们应当尽力避免使用 signal。linux 自 2.6.27 后能以 fd 方式通知 timer 触发，这个 fd 可以放到 epoll 中和传输数据的 fd 统一管理。唯一问题是：这是个系统调用，且我们不清楚它在多线程下的表现。
为什么这么关注 timer 的开销？让我们先来看一下 RPC 场景下一般是怎么使用 timer 的：
- 在发起 RPC 过程中设定一个 timer，在超时时间后取消还在等待中的 RPC。几乎所有的 RPC 调用都有超时限制，都会设置这个 timer。
- RPC 结束前删除 timer。大部分 RPC 都由正常返回的 response 导致结束，timer 很少触发。
你注意到了么，在 RPC 中 timer 更像是”保险机制”，在大部分情况下都不会发挥作用，自然地我们希望它的开销越小越好。一个几乎不触发的功能需要两次系统调用似乎并不理想。那在应用框架中一般是如何实现 timer 的呢？谈论这个问题需要区分”单线程”和”多线程”：
- 在单线程框架中，比如以 libevent、libev 为代表的 eventloop 类库，或以 GNU Pth、StateThreads 为代表的 coroutine / fiber 类库中，一般是以小顶堆记录触发时间。
epoll_wait前以堆顶的时间计算出参数 timeout 的值，如果在该时间内没有其他事件，epoll_wait也会醒来，从堆中弹出已超时的元素，调用相应的回调函数。整个框架周而复始地这么运转，timer 的建立，等待，删除都发生在一个线程中。只要所有的回调都是非阻塞的，且逻辑不复杂，这套机制就能提供基本准确的 timer。不过正如 Threading Overview 一文所说，这不是 RPC 的场景。 - 在多线程框架中，任何线程都可能被用户逻辑阻塞较长的时间，我们需要独立的线程实现 timer，这种线程我们叫它
TimerThread。一个非常自然的做法，就是使用用锁保护的小顶堆。当一个线程需要创建 timer 时，它先获得锁，然后把对应的时间插入堆，如果插入的元素成为了最早的，唤醒TimerThread。TimerThread中的逻辑和单线程类似，就是等着堆顶的元素超时，如果在等待过程中有更早的时间插入了，自己会被插入线程唤醒，而不会睡过头。这个方法的问题在于每个 timer 都需要竞争一把全局锁，操作一个全局小顶堆，就像在其他文章中反复谈到的那样，这会触发 cache bouncing。同样数量的 timer 操作比单线程下的慢 10 倍是非常正常的，尴尬的是这些 timer 基本不触发。
多线程下 TimerThread 的三个难点
我们重点谈怎么解决多线程下的问题。
一个惯例思路是把 timer 的需求散列到多个 TimerThread，但这对 TimerThread 效果不好。注意我们上面提及到了那个”制约因素”：一旦插入的元素是最早的，要唤醒 TimerThread。假设 TimerThread 足够多，以至于每个 timer 都散列到独立的 TimerThread，那么每次它都要唤醒那个 TimerThread。”唤醒”意味着触发 linux 的调度函数，触发上下文切换。在非常流畅的系统中，这个开销大约是 3-5 微秒，这可比抢锁和同步 cache 还慢。这个因素是提高 TimerThread 扩展性的一个难点。多个 TimerThread 减少了对单个小顶堆的竞争压力，但同时也引入了更多唤醒。
另一个难点是删除。一般用 id 指代一个 Timer。通过这个 id 删除 Timer 有两种方式：1. 抢锁，通过一个 map 查到对应 timer 在小顶堆中的位置，定点删除，这个 map 要和堆同步维护。2. 通过 id 找到 Timer 的内存结构，做个标记，留待 TimerThread 自行发现和删除。第一种方法让插入逻辑更复杂了，删除也要抢锁，线程竞争更激烈。第二种方法在小顶堆内留了一大堆已删除的元素，让堆明显变大，插入和删除都变慢。
第三个难点是 TimerThread 不应该经常醒。一个极端是 TimerThread 永远醒着或以较高频率醒过来（比如每 1ms 醒一次），这样插入 timer 的线程就不用负责唤醒了，然后我们把插入请求散列到多个堆降低竞争，问题看似解决了。但事实上这个方案提供的 timer 精度较差，一般高于 2ms。你得想这个 TimerThread 怎么写逻辑，它是没法按堆顶元素的时间等待的，由于插入线程不唤醒，一旦有更早的元素插入，TimerThread 就会睡过头。它唯一能做的是睡眠固定的时间，但这和现代 OS scheduler 的假设冲突：频繁 sleep 的线程的优先级最低。在 linux 下的结果就是，即使只 sleep 很短的时间，最终醒过来也可能超过 2ms，因为在 OS 看来，这个线程不重要。一个高精度的 TimerThread 有唤醒机制，而不是定期醒。
另外，更并发的数据结构也难以奏效，感兴趣的同学可以去搜索 “concurrent priority queue” 或 “concurrent skip list”，这些数据结构一般假设插入的数值较为散开，所以可以同时修改结构内的不同部分。但这在 RPC 场景中也不成立，相互竞争的线程设定的时间往往聚集在同一个区域，因为程序的超时大都是一个值，加上当前时间后都差不多。
这些因素让 TimerThread 的设计相当棘手。由于大部分用户的 qps 较低，不足以明显暴露这个扩展性问题，在 r31791 前我们一直沿用”用一把锁保护的 TimerThread”。TimerThread 是 brpc 在默认配置下唯一的高频竞争点，这个问题是我们一直清楚的技术债。随着 brpc 在高 qps 系统中应用越来越多，是时候解决这个问题了。r31791 后的 TimerThread 解决了上述三个难点，timer 操作几乎对 RPC 性能没有影响，我们先看下性能差异。
提示：在示例程序 example/multi_threaded_echo_c++ 中，r31791 后的
TimerThread相比老TimerThread，在 24 核 E5-2620 上（超线程），以 50 个 bthread 同步发送时，节省 4% cpu（差不多 1 个核），qps 提升 10% 左右；在 400 个 bthread 同步发送时，qps 从 30 万上升到 60 万。新TimerThread的表现和完全关闭超时时接近。
新 TimerThread 的设计
那新 TimerThread 是如何做到的？
- 一个
TimerThread而不是多个。 - 创建的 timer 散列到多个 Bucket 以降低线程间的竞争，默认 13 个 Bucket。
- Bucket 内不使用小顶堆管理时间，而是链表 +
nearest_run_time字段，当插入的时间早于nearest_run_time时覆盖这个字段，之后去和全局nearest_run_time（和 Bucket 的nearest_run_time不同）比较，如果也早于这个时间，修改并唤醒TimerThread。链表节点在锁外使用ResourcePool分配。 - 删除时通过 id 直接定位到 timer 内存结构，修改一个标志，timer 结构总是由
TimerThread释放。 TimerThread被唤醒后首先把全局nearest_run_time设置为几乎无限大（max of int64），然后取出所有 Bucket 内的链表，并把 Bucket 的nearest_run_time设置为几乎无限大（max of int64）。TimerThread把未删除的 timer 插入小顶堆中维护，这个堆就它一个线程用。在每次运行回调或准备睡眠前都会检查全局nearest_run_time，如果全局更早，说明有更早的时间加入了，重复这个过程。
这里勾勒了 TimerThread 的大致工作原理，工程实现中还有不少细节问题，具体请阅读 timer_thread.h 和 timer_thread.cpp。
这个方法之所以有效：
- Bucket 锁内的操作是 O(1) 的，就是插入一个链表节点，临界区很小。节点本身的内存分配是在锁外的。
- 由于大部分插入的时间是递增的，早于
Bucket::nearest_run_time而参与全局竞争的 timer 很少。 - 参与全局竞争的 timer 也就是和全局
nearest_run_time比一下，临界区很小。 - 和 Bucket 内类似，极少数 Timer 会早于全局
nearest_run_time并去唤醒TimerThread。唤醒也在全局锁外。 - 删除不参与全局竞争。
TimerThread自己维护小顶堆，没有任何 cache bouncing，效率很高。TimerThread醒来的频率大约是 RPC 超时的倒数，比如超时 = 100ms，TimerThread一秒内大约醒 10 次，已经最优。
至此 brpc 在默认配置下不再有全局竞争点，在 400 个线程同时运行时，profiling 也显示几乎没有对锁的等待。
Linux 时间管理补充
下面是一些和 linux 下时间管理相关的知识：
epoll_wait的超时精度是毫秒，较差。pthread_cond_timedwait的超时使用 timespec，精度到纳秒，一般是 60 微秒左右的延时。- 出于性能考虑，
TimerThread使用 wall-time，而不是单调时间，可能受到系统时间调整的影响。具体来说，如果在测试中把系统时间往前或往后调一个小时，程序行为将完全 undefined。未来可能会让用户选择单调时间。 - 在 cpu 支持 nonstop_tsc 和 constant_tsc 的机器上，brpc 和 bthread 会优先使用基于 rdtsc 的
cpuwide_time_us。那两个 flag 表示 rdtsc 可作为 wall-time 使用，不支持的机器上会转而使用较慢的内核时间。我们的机器（Intel Xeon 系列）大都有那两个 flag。rdtsc 作为 wall-time 使用时是否会受到系统调整时间的影响，未测试不清楚。
