在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

创作场景

为调度器设计可用的 HAProxy EBtree