文档章节

HAProxy的独门武器:ebtree[转]

强子大叔的码田
 强子大叔的码田
发布于 2016/05/31 09:33
字数 719
阅读 184
收藏 0

1. HAProxy和ebtree简介

HAProxy是法国人Willy Tarreau个人开发的一个开源软件,目标是应对客户端10000以上的同时连接,为后端应用服务器、数据库服务器提供高性能的负载均衡服务。
在底层数据结构方面,旧版本HAProxy曾经使用过红黑树,用于任务调度、负载均衡等方面。但是Willy Tarreau认为,在事件响应非常频繁的情况下,任务插入、删除的频率非常高,这时候使用红黑树存在性能瓶颈,尤其不能接受红黑树删除节点的时间复杂度为O(log n)。因此,他发明了一种新的数据结构,叫做弹性二叉树(elastic binary tree),简称ebtree。
目前新版本的HAProxy(本文编写时最新版本为1.4.23)已使用ebtree,而除了HAProxy之外,还没有其它著名的开源软件使用ebtree。可以这么说,HAProxy最有特色的地方就是ebtree,ebtree名符其实是HAProxy的独门武器。
ebtree是不平衡的二叉搜索树(BST),而红黑树、AVL树等都是平衡的BST。传统的BST最怕的就是退化成线性搜索,因此,红黑树等BST插入、删除时都需要对树进行平衡化,而平衡化是一个从叶子节点开始,向根节点方向递归向上的过程,时间复杂度是O(log n)。
有鉴于此,ebtree为了实现删除节点时O(1)的时间复杂度,必然放弃保持树的平衡,为了拒绝由此而来的副作用——退化成线性搜索(或者更准确地说,退化成不受限制的线性搜索),不可避免地引入了一些新的成员和新的思路,且待我慢慢道来。

2. ebtree节点的组成

一个ebtree的节点(以下简称ebnode)分为node部分和leaf部分(Willy Tarreau是这样描述的,但我觉得称为树干部分和叶子部分更合适一些,以下就按我的理解来叙述)。树干负责关联其它ebnode,由父指针(node_p)和分支(Willy Tarreau称之为root,包括左分支L和右分支R),以及一个控制树的高度的特殊成员(bit)组成,叶子负责携带数据(data,一般是数据的键值,所以下文都称为key),另外包含一个指向上层的指针(leaf_p)。
一棵ebtree只有一个根节点(root),包含两个左右分支的指针(L、R)。所有的ebnode总是挂在根节点的左分支下面,根节点的右分支总是为空。在ebtree的遍历过程中,判断当前节点是否根节点就是判断其右指针是否为空。

Ebnode

 

READ THE REST OF THIS ENTRY

© 著作权归作者所有

强子大叔的码田

强子大叔的码田

粉丝 910
博文 1439
码字总数 1221048
作品 9
南京
架构师
私信 提问
烂泥:haproxy学习之https配置

在前一段时间,我写了几篇有关学习haproxy的文章。今天我们再来介绍下haproxy的https配置,https协议的好处在此,我们就不就作介绍了。 我们只介绍如何配置https,以及https在实际生产环境中...

烂泥行天下
2015/11/05
177
2
Linux Haproxy详细配置教程

1 Linux Haproxy 负载均衡 v1.8 ★★★ 类似于ningx的反向代理 1.1 Haproxy 概述 Haproxy是一个开源的高性能的反向代理或者说是负载均衡服务软件之一,它支持双机热备、虚拟主机、基于TCP和H...

小小子之家
2018/07/31
0
0
负载均衡工具haproxy安装,配置,使用

一,什么是haproxy HAProxy提供高可用性、负载均衡以及基于TCP和HTTP应用的代 理,支持虚拟主机,它是免费、快速并且可靠的一种解决方案。HAProxy特别适用于那些负载特大的web站点,这些站点...

晨曦之光
2012/03/09
208
1
我在VPS上安装haproxy成功,换另外一台VPS同样的步骤安装就无法访问,且无错误信息

我本身想安装一个haproxy测试一下转发,因为前阵子公司的服务器被人DD+CC打的生活不能自理,所以准备做一些跳板,但是我本身不懂LINUX加上没有系统的学习过这些所以只有经人介绍知道了hapro...

量产废柴刚
2015/05/09
468
0
安装 HAproxy 实现负载均衡

HAProxy 可以做负载均衡,同时还可对服务器健康检测,有 down 机的自动停止分发,当服务器正常后,又自动均衡到刚死过的服务器。之前用 nginx ,现试用下 haproxy 。 下载:HAproxy 1.3.15 ...

小编辑
2010/02/27
3.4K
0

没有更多内容

加载失败,请刷新页面

加载更多

视频如何加水印?

很多视频制作者的视频都被他人盗用过,为了防止自己的劳动成果被他人窃取,给视频加水印对于视频制作者来说,是一件非常重要的事情。那么下面分享一个手机给视频加水印的方法,一起来看看吧!...

白米稀饭2019
33分钟前
5
0
004-Envelop-基于Blockstack的文件传输dapp

本篇文章主要介绍基于Blockstack的文件传输工具; ####A-链接地址 官网地址:https://envelop.app/ Github地址:https://github.com/envelop-app ####B-特性: 1: Share private files easil...

Riverzhou
36分钟前
7
0
SpringCloud——声明式调用Feign

Feign声明式调用 一、Feign简介 使用Ribbon和RestTemplate消费服务的时候,有一个最麻烦的点在于,每次都要拼接URL,组织参数,所以有了Feign声明式调用,Feign的首要目标是将Java HTTP客户端...

devils_os
41分钟前
7
0
《JAVA核心知识》学习笔记 (22. 数据结构)

22.1.1. 栈(stack) 栈( stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶 (top)。它是后进先出(LIFO)的。对栈的基本操作只有 push(进栈)和 pop(出栈...

Shingfi
47分钟前
6
0
你对AJAX认知有多少(1)?

AJAX(一) AJAX技术对于前段或者后端工程师来说,都是必不可缺的 那我们这几期都来细细品味一下AJAX的相关知识,直接上干货喽~ 1、什么是AJAX,为什么要使用Ajax(请谈一下你对Ajax的认识) 什么...

理性思考
55分钟前
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部