为调度器设计可用的 HAProxy EBtree

在2019年纽约QCon大会上，HAProxy Technologies公司的工程总监 Andjelko Iharos 做了个主题演讲，演讲的内容是 HAProxy Technologies 的 CTO Willy Tarreau 和团队如何实现EBtree数据结构以优化 HAProxy 负载平衡器调度器的性能和内存使用。

HAProxy 是开源负载平衡器，它提供一系列负载平衡方法、自定义路由、ACL 支持和 Lua 脚本。HAProxy 旨在处理高流量网站，它的开发一直致力于提高负载平衡性能和功能。

HAProxy 负载平衡器的关键组成部分是调度器，它负责处理维护任务队列的运行和挂起，以维持活动连接。 调度器还负责管理任务的插入及删除，并允许相同的到期时间，同时基于任务到期时间和优先级对任务读取进行排序。

HAProxy 调度程序，来自 Andjelko Iharos 在 QCon 大会上演讲的幻灯片

由于 HAProxy 设计用于处理高流量的环境，Andjelko Iharos 强调需要调度器来处理高频事件、大量队列条目、频繁查找和条目更改率的大范围变化。 在设计调度器时，Andjelko Iharos 注意到了所需的特性，包括速度、可预测性和简单性。

有了这些要求后， 通过审查常见数据结构针对所需特征的执行情况，Tarreau 开始实施。由于链表提供快速迭代和常数插入时间，早期的调度器使用https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/linked lists.html">链表构建。然而，当调度器需要根据到期时间确定任务的优先级时，链表的优势就失去了。在每次插入后，优先级要求任务列表进行排序，因此，常数插入时间的优势就失去了。

为了更好地满足优先级要求，评估了更好地支持排序事件的树数据结构。前缀树(其中节点共享一个公共前缀)提供了调度程序可以利用的几个特性。前缀树提供了对节点的快速比较(即使是长键)，并且自然地支持前缀匹配。然而，相对于其他树形结构，其内存管理更为复杂，前缀树会更容易变得不平衡。

为了弥补这些缺点，Tarreau 设计了弹性二叉树（Elastic Binary tree，简称 EBtree）数据结构。EBtree 针对频繁的插入和删除进行了优化，不需要额外的内存管理。EBtree 的元素是节点和叶子，其中节点维持上下节点和叶子之间的关系，而叶子存储关键数据和指向其上层节点的指针。当插入新数据时，分配一个节点和叶子的组合，并调整节点和叶子的指针，新的节点可以插入到现有节点和叶子对中。由于指针重新调整算法的性质，为节点分配的内存不需要单独考虑，并且与叶子内存同时释放。这消除了对插入和删除操作进行额外内存分配和清理的需要。

EBTree 数据结构，来自 Andjelko Iharos 在QCon演讲的幻灯片

实施 EBtree 以在 HAProxy 调度器中管理挂起和活动的任务，并已经针对包括定时器、ACL、LRU 缓存在内的用例进行了扩展。HAProxy 调度器中的 EBtree 的性能支持低至 100 纳秒的插入、每秒 20 多万个 TCP 连接和每秒 35 万个 HTTP， 而与此同时，只用到 3-5%的 CUP 性能。

在Tarreau的博文中有关于 EBtree 实现的细节。您可以在 QCon 网站上查看Iharos演讲的幻灯片。

原文链接：

HAProxy EBtree: Design for a Scheduler, and Use (Almost) Everywhere