为调度器设计可用的 HAProxy EBtree

阅读数:1541 2019 年 7 月 27 日

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

收藏

评论

微博

发表评论

注册/登录 InfoQ 发表评论