LinuxEye - Linux系统教程

LinuxEye - Linux系统教程

当前位置: 主页 > Linux教程 >

HAProxy的独门武器:ebtree

时间:2013-05-31 21:51来源:UC技术博客 编辑:UC技术博客 点击:
1.HAProxy 和 ebtree 简介 HAProxy 是法国人 WillyTarreau 个人开发的一个开源软件,目标是应对客户端 10000 以上的同时连接,为后端应用服务器、数据库服务器提供高性能的负载均衡服务。 在底

1. HAProxyebtree简介

HAProxy是法国人Willy Tarreau个人开发的一个开源软件,目标是应对客户端10000以上的同时连接,为后端应用服务器、数据库服务器提供高性能的负载均衡服务。

在底层数据结构方面,旧版本HAProxy曾经使用过红黑树,用于任务调度、负载均衡等方面。但是Willy Tarreau认为,在事件响应非常频繁的情况下,任务插入、删除的频率非常高,这时候使用红黑树存在性能瓶颈,尤其不能接受红黑树删除节点的时间复杂度为O(log n)。因此,他发明了一种新的数据结构,叫做弹性二叉树elastic binary tree,简称ebtree

目前新版本的HAProxy(本文编写时最新版本为1.4.23)已使用ebtree,而除了HAProxy之外,还没有其它著名的开源软件使用ebtree。可以这么说,HAProxy最有特色的地方就是ebtreeebtree名符其实是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

 

3. 各个指针的附加属性

32位平台中,一个指针占用4个字节,例如,地址值0xaabbcc00的下一个地址值是0xaabbcc04,再下一个是0xaabbcc08,也就是说,指针的值的最后两个比特不能表示一个合法地址。因此,Willy Tarreau充分利用这一点,来保存上述几个指针的特殊属性。这是一个很重要的优化,每个ebnode可以节省几个成员,整个ebtree就节省大量存储空间。
1) LR既可以指向其它ebnode的树干,也可以指向其它ebnode的叶子,还可以指向自己的叶子。在ebtree的遍历过程中,对树干和叶子有不同的处理逻辑,LR有必要知道自己所指向的是树干还是叶子。
2) 可以知道node_pleaf_p究竟挂在其它ebnode的左分支下面,还是挂在其右分支下面。
3) 根节点右分支不挂任何树干和叶子,可以把它也利用上,指示该ebtree是否允许重复键值。

熟悉红黑树的读者都知道,红黑树也有同样的优化方法,表示红黑树节点颜色的属性并不占用内存空间。
 

4. bit的定义

引入bit就是为了限制树的高度,避免极端不平衡。在一棵不允许重复键值的ebtree中,key32位的情况下,bit的取值范围是从031,此时,它的定义是:子树所有的键中,第一个不同的二进制位的位置。允许重复键值的ebtree稍后再详细介绍。

例如,下图的右下角子树中只有两个键,左边叶子节点的键值为300,右边叶子节点的键值为400300的二进制是100101100400的二进制是110010000,从右边数起第7位起(注意,程序员都是从0开始数数的),300400左边的位都相同,所以,bit等于7

bit

这时候,读者可能会问,这样定义bit为什么能够限制树的高度呢?不用着急,马上隆重介绍bit的两个重要意义!
 

5. bit的第一个重要意义

这里只讨论键值大于等于零的情况,事实上,ebtree可以支持键值为负数,不过,我还没有仔细研究过这种情况,应该是对符号位进行某些转换处理。

bit的第一个重要意义:同一个ebnode中的bitkey,联合决定该ebnode属下的子树内,所有key的取值范围

先看下图挂在根节点下面,key = 300的那个ebnodebit = 8300的二进制为100101100,从右边数起第8位是最高位那个1,参考bit的定义,也就是说,该子树所有的键,第8位左边都是0,所以,它们的取值范围是从0511(二进制111111111)。

再看最下面那个ebnodebit = 5250的二进制为11111010,从右边数起第5位是第三个1,再对照bit的定义,该子树的键,第5位左边都是11,所以,它们的取值范围是从192(二进制11000000)到255(二进制11111111)。

同理,最右边那个ebnodebit = 7key = 400,取值范围是256-511

bit1
 

6. bit的第二个重要意义和查找过程

bit的第二个重要意义:如果要查找的数据x在该子树的取值范围内,bit可以指示其可能会在左分支下面还是右分支下面

ebtree具体查找过程是,遍历到某个ebnode时,如果key = x,返回查找结果;如果x已经超出bit规定的取值范围,返回查找失败;否则,取x的第bit位,如果bit = 0,那么从该ebnode的左分支查找,反之,从右分支查找;如果已到达叶子还是没有匹配,返回查找失败。

还是上一节那个图,假如要找的键x = 249,二进制为11111001,从根节点左分支开始查找,bit = 8右边数起第8位为0,于是从它的左分支继续查找,bit = 5249右边数起第5位为1,于是从它的右分支继续查找,此时已到达叶子,且250 != 249,本次查找失败。

假如要找的键x = 300,因为就在查找路径的节点上,直接返回结果。

假如要找的键x = 600,已经超出该子树中bit规定的取值范围,返回查找失败。
 

7. 插入不可重复的键值

首先,要介绍的是空树的情况。由前面的叙述可以得知,一棵ebtree为空树当且仅当它的根节点的左分支为空。所以,此时插入的ebnode就直接挂在根节点的左分支下面,由于新插入的ebnode不存在左右分支,也没有父节点(上层ebnode),显然也不需要bit来控制树的高度,因此,该ebnode的树干都没有使用。

insert0

其次,介绍ebtree只有一个ebnode时,再插入一个ebnode的情况。此时,新的ebnode必定插入在根节点与旧的ebnode之间,如果新的键值大于原来的键值,旧的ebnode挂在新的ebnode的左分支下面,新的ebnode的叶子挂在自己的右分支下面,再计算bit;反之,则左右相反,再计算bit。

下图的例子,是已有key = 200,再插入key = 300的情形。读者可以根据上面的描述画出已有key = 200,再插入key = 100的情形。

insert1

然后,就可以介绍在ebtree中插入新的ebnode的五种基本情形。在这里,都以上图为初始状态。任何具有更多ebnode的情形,都可以通过对ebtree的遍历,递推到其中一种情形。

1) 新的键值可以插入子树中,而且小于子树中的最小键值
假如新插入ebnodekey100,根据bit的第二个重要意义,100应该在该子树的左分支下面,而且,100小于200,于是,该ebnode插入在原图的左分支上,自己的左分支指向自己的叶子,自己的右分支指向原来子树的左分支。如下图所示。

insert2_1

键值范围[0, 200)都属于这种情形。

2) 新的键值可以插入子树中,该键值在确定要插入的两个ebnode的键值之间,且应该在该子树的左分支下面
假如新插入ebnodekey225,根据bit的第二个重要意义,225应该在该子树的左分支下面,而且,225大于200,于是,该ebnode插入在原图的左分支上,自己的左分支指向原来子树的左分支,自己的右分支指向自己的叶子。如下图所示。

insert2_2

键值范围(200, 255]都属于这种情形。

3) 新的键值可以插入子树中,该键值在确定要插入的两个ebnode的键值之间,且应该在该子树的右分支下面
假如新插入ebnodekey275,根据bit的第二个重要意义,275应该在该子树的右分支下面,而且,275小于300,于是,该ebnode插入在原图的右分支上,自己的左分支指向自己的叶子,自己的右分支指向原来子树的右分支。如下图所示。

insert2_3

键值范围(255, 300)都属于这种情形。

4) 新的键值可以插入子树中,而且大于子树中的最大键值
假如新插入ebnodekey400,根据bit的第二个重要意义,400应该在该子树的右分支下面,而且,400大于300,于是,该ebnode插入在原图的右分支上,自己的左分支指向原来子树的右分支,自己的右分支指向自己的叶子。如下图所示。

insert2_4

键值范围(300, 511]都属于这种情形。

5) 新的键值不可以插入子树中
假如新插入ebnodekey600,根据bit的第一个重要意义,600不可插入到子树中,于是,该ebnode插入在原图的子树之上,自己的左分支指向原来的子树,自己的右分支指向自己的叶子。如下图所示。

insert2_5

键值范围(511, +)都属于这种情形。
 

8. bit的第三个重要意义和插入重复的键值

ebtree是专门为任务调度而生的,同样的优先级,必须保证能够按照任务触发的次序来进行访问。所以,ebtree支持存储重复的键值,这一点并不是所有的BST都支持,可以说是ebtree的优点。而且,解决键值冲突不会退化成链表。

bit的第三个重要意义:bit为负值表示该子树下所有的键都是重复的,而且,该值表示重复子树的层次。当然,必须要在根节点右指针允许的情况下。

插入第一个重复键值,例如300ebnode底纹为点点),可以参考上一节的第二种和第四种基本情形,不同的是,bit-1

insert_dup1

如果再插入一个重复键值300ebnode底纹为方格),应该在重复键值子树上插入,而且是向上生长。

上图已经有四个ebnode,信息量较大,为了后续叙述方便,把它简化,去掉几个指针域,保留bitkey,得到下图。

insert_dup2s

再插入一个300ebnode底纹为斜方格),得到下面的ebtree

insert_dup3s

再插入两个300ebnode底纹分别为左斜线和右斜线),得到下面的ebtree

insert_dup5s

读者可以思考一下,如果再来一个、两个、三个300,应该在哪里插入?如果插入不同于300的其它键值,应该在哪里插入?

从上面几张图,大家可以看到,一个ebnode的树干和叶子会随着树的增长而拉长到不同的层次上,好像很有弹性的样子,这就是弹性二叉树名字的由来。
 

9. 删除节点

删除一个ebnode,概括起来比较简单,就是把要删除的叶子和该叶子的父亲(树干部分)删除,然后把兄弟挂到祖父下面。因为不需要对树进行平衡化,不需要访问其它ebnode,效率很高。

具体操作,分为两种情况:
1)被删除的叶子直连自己的树干,可直接删除该ebnode,然后对它的兄弟重新指派原来的祖父为父亲。
2)被删除的叶子不是直连自己的树干,以该叶子的父亲(其它ebnode的树干)替换该ebnode的树干,然后删除该ebnode,再把它的兄弟重新指派原来的祖父为父亲。
 

10. 总结

没有最好的数据结构,只有最合适的数据结构。ebtree有它的优点:
1)支持存储重复的键值,而且,在此情况下,也不会退化成线性操作。
2)删除节点时,不需要对树进行平衡化。
3)插入键值时,很可能不需要深入到树的叶子,当然,很多BST都这样。
4)查询键值时,可以预知子树的取值范围,从而可以选择访问还是不访问该子树。

缺点也很明显:
1)逻辑比较复杂,熟悉的人不多(希望读者看完本文之后都有茅塞顿开的感觉)。
2)ebnode占用空间比较多,如果把bit也算一个指针,相当于花了5个指针才携带1个数据。
3)键值严重依赖于可以进行位运算的数据类型。
总而言之,ebtree适合有高频率插入、删除操作(例如50万次/秒)的使用场合,不适合查询较多、插入、删除较少的场合,非常不适合用于缓存。

转载请保留固定链接: http://www.linuxeye.com/Linux/1690.html

------分隔线----------------------------
标签:HAproxyebtree
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
栏目列表
推荐内容