乐趣区

关于后端:从-Kafka-看时间轮算法设计

jiezi

原创不易，转载请注明出处

前言

Kafka 中有很多延时操作，比方对于耗时的网络申请（比方 Produce 时期待 ISR 正本复制胜利）会被封装成 DelayOperation 进行提早解决操作，避免阻塞 Kafka 申请解决线程。

Kafka 没有应用 JDK 自带的 Timer 和 DelayQueue 实现。因为工夫复杂度上这两者插入和删除操作都是 O(logn)，不能满足 Kafka 的高性能要求。

冷常识：JDK Timer 和 DelayQueue 底层都是个优先队列，即采纳了 minHeap 的数据结构，最快须要执行的工作排在队列第一个，不一样的是 Timer 中有个线程去拉取工作执行，DelayQueue 其实就是个容器，须要配合其余线程工作。ScheduledThreadPoolExecutor 是 JDK 的定时工作实现的一种形式，其实也就是 DelayQueue + 池化线程的一个实现。

Kafka 基于工夫轮实现了延时操作，工夫轮算法的插入删除操作都是 O(1) 的工夫复杂度，满足了 Kafka 对于性能的要求。除了 Kafka 以外，像 Netty、ZooKeepr、Dubbo 这样的开源我的项目都有应用到工夫轮的实现。

那么工夫轮算法是怎么样的，算法思维是什么？Kafka 中又是怎么实现它的。

Kafka 工夫轮算法

工夫轮的算法思维能够通过咱们日常生活中的钟表来了解。

Kafka 中的工夫轮（TimingWheel）是一个存储定时工作的环形队列，底层采纳数组实现，数组中的每个元素能够寄存一个定时工作列表（TimerTaskList）。TimerTaskList 是一个环形的双向链表，链表中的每一项示意的都是定时工作项（TimerTaskEntry），其中封装了真正的定时工作（TimerTask）。

图中的几个参数：

  • tickMs: 时间跨度
  • wheelSize: 工夫轮中 bucket 的个数
  • startMs: 开始工夫
  • interval：工夫轮的整体时间跨度 = tickMs * wheelSize

  • currentTime: tickMs 的整数倍，代表工夫轮以后所处的工夫

    • currentTime 能够将整个工夫轮划分为到期局部和未到期局部，currentTime 以后指向的工夫格也属于到期局部，示意刚好到期，须要解决此工夫格所对应的 TimerTaskList 中的所有工作

整个工夫轮的总体跨度是不变的，随着指针 currentTime 的一直推动，以后工夫轮所能解决的时间段也在一直后移，总体工夫范畴在 currentTime 和 currentTime+interval 之间。

当初你可能会有疑难，这个形象的 currentTime 怎么推动呢，别急看下文

那么如何反对大跨度的定时工作呢？

如果要反对几十万毫秒的定时工作，难不成要扩容工夫轮的那个数组？实际上这里有两种解决方案：

  • 应用减少轮次 / 圈数的概念（Netty 的 HashedWheelTimer）

    • 举例来说，比方目前是 “0-7” 8 个槽，41 % 8 + 1 = 2，即应该放在槽位是 2，下标是 1 的地位。而后 (41 – 1) / 8 = 5，即轮数记为 5。也就是说当循环 5 轮之后扫到下标的 1 的这个槽位会触发这个工作。
    • 具体实现细节这里不详述

  • 应用多层工夫轮的概念（Kafka 的 TimingWheel）

    • 相较于上个计划，层级工夫轮能更好管制工夫粒度，能够应答更加简单的定时工作解决场景，实用的范畴更广；

多层工夫轮就更像咱们钟表的概念了。秒针走的一圈、分针走的一圈和时针走的一圈就造成了一个多层工夫轮的关系。

第 N 层工夫轮走了一圈，等于 N+1 层工夫轮走一格。即高一层工夫轮的时间跨度等于以后工夫轮的整体跨度。

在工作插入时，如果第一层工夫轮不满足条件，就尝试插入到高一层的工夫轮，以此类推。

随着工夫推动，也会有一个工夫轮降级的操作，本来延时较长的工作会从高一层工夫轮从新提交到工夫轮中，而后会被放在适合的低层次的工夫轮当中期待解决；

在 Kafka 中工夫轮之间如何关联呢，如何展示这种高一层的工夫轮关系？

其实很简略就是一个外部对象的指针，指向本人高一层的工夫轮对象。

另外还有一个问题，如何推动工夫轮的后退，让工夫轮的工夫往前走。

  • Netty 中的工夫轮是通过工作线程依照固定的工夫距离 tickDuration 推动的

    • 如果长时间没有到期工作，这种计划会带来空推动的问题，从而造成肯定的性能损耗；

  • Kafka 则是通过 DelayQueue 来推动，是一种空间换工夫的思维；

    • DelayQueue 中保留着所有的 TimerTaskList 对象，依据工夫来排序，这样延时越小的工作排在越后面。
    • 内部通过一个线程（叫做 ExpiredOperationReaper）从 DelayQueue 中获取超时的工作列表 TimerTaskList，而后依据 TimerTaskList 的 过期工夫来准确推动工夫轮的工夫 ，这样就不会存在空推动的问题啦。

其实 Kafka 采纳的是一种衡量的策略，把 DelayQueue 用在了适合的中央。DelayQueue 只寄存了 TimerTaskList，并不是所有的 TimerTask，数量并不多，相比空推动带来的影响是利大于弊的 。

总结

  • Kafka 应用工夫轮来实现延时队列，因为其底层是工作的增加和删除是基于链表实现的，是 O(1) 的工夫复杂度，满足高性能的要求；
  • 对于时间跨度大的延时工作，Kafka 引入了层级工夫轮，能更好管制工夫粒度，能够应答更加简单的定时工作解决场景；
  • 对于如何实现工夫轮的推动和防止空推动影响性能，Kafka 采纳空间换工夫的思维，通过 DelayQueue 来推动工夫轮，算是一个经典的 trade off。

本文通过 Kafka 来讲述了工夫轮的算法设计思维，其中还提到了 Netty 工夫轮算法的实现，可能会比拟偏差实践，举荐去浏览一下 Kafka 和 Netty 工夫轮实现的源码，并不是特地难，比照起来看会更有播种。

参考

  • 《深刻了解 Kafka》
  • 《Netty 外围原理分析与 RPC 实际》专栏
退出移动版