ebtree介绍

2013年2月26日 | 分类: 操作系统, 编程技术 | 标签:

haproxy中使用了ebtree(Elastic Binary Trees)弹性二叉树作为任务，计时器，server的存储数据结构，代替之前版本中的rbtree。本文试着介绍一下这种数据结构，主要是翻译http://1wt.eu/articles/ebtree/的内容，由于ebtree的资料较少，基本上是自己看完之后的理解，不准确的地方，还请指正。

Willy Tarreau上来就吐槽维基百科的系统，说2008年发表的文章被无故删除，甚至连一个备份版本都没有，整个摘要都在吐槽这个事，看来怨念非常重，好在2011年作者花了一个周末把这篇文章重写了一遍。

言归正传，首先是弹性二叉树的出现背景：

简介

计算机科学中，弹性二叉树（EB tree或者EBtree）是一个二叉搜索树，通过对常见的插入，查找，删除操作进行了优化，对象可以是随机整型数据，或者其它不需要内存分配的元数据。ebtree特别适合对时间顺序或优先级要求较高的系统，如操作系统中的调度器。这种数据结构的插入和查找的时间复杂度是O(log n)，删除操作时间复杂度是O(1)，ebtree并不是平衡树，但是树的高度和存储的数据类型有关，对于重复的数据ebtree也能支持。

ebtree是Willy Tarreau在2002-2007年间提出的，当时是用来作为一个用户态的网络程序的任务事件调度系统。这个调度需要操作一批时间有序的未来事件，插入和删除都非常频繁，因此需要优化这些基础操作。早先的实现是原生的链表，后来替换成更快的基数树。但基数树的缺点是它必须经常分配内存给新的元素，删除的时候需要执行gc操作，删除不必要的内部节点。在极端情况下，这种实现基本不可行。替换的方式是使用一个平衡树如红黑树，但是删除操作需要平衡树，时间复杂度O(log n)也比较高。

解决方案就是找到介于基数树和平衡树中间的混合类型树，每次插入的元素包含内部节点和叶子两部分。这两部分随着树的增长和删除可能会被拉伸开来，因此这种新的树命名为弹性二叉树。

使用许可

该数据结构的内容和算法已经公开发表，Willy的实现最开始是GPL协议，后来采用更开放的LGPL，算法因为很简明，因此可以为了特殊的需求做些定制改动。

基础定义

Ebnode

在EBtree中，数据存储在EB的节点中，一个EB节点包含两部分内容：

  • 节点部分：负责将其它节点或叶子关联在一起，是EB树的框架构成部分
  • 叶子部分：负责携带数据如一个整形key，并且包含一个指向上一层节点的指针(leaf_p)

节点部分由父指针node_p、当前位置(bit)、根(root)组成；根包含指向下一层的两个指针，root也可以认为是一个子树，当前位置bit表示整形数据key的最低二进制位置，该node的子树中所有的元素拥有共同的二进制前缀。

node中的根root只包含二个分支指针branches，每一个node都应该有左右分支，分别代表bit位置为0和为1的两个子树，左0右1。

分支指针是有类型的，这意味着一个node知道它的root部分的左右分支指向的内容类型，能够通过该指针就能判定下面对象是node还是leaf，同样的每个EB节点的父指针node_p,leaf_p也是有类型的，能够知道它是挂在上一个节点root的左子树还是右子树下面。

一个经典的EBtree由一个root结构开始，包含包含2个子分支，下面的部分每一个元素都包含一个node和leaf。根的root的右子树一般都是空的。

EBtree的特性

EBtree提供了丰富的有用的数据操作特性：

  • 查找
  1. 查找第一个或者最后一个元素
  2. 精确匹配：查找特定的元素（整形，指针，字符串，内存块）
  3. 最长匹配：查找长匹配的元素（如网路地址匹配）
  4. 查找第一个匹配的前缀：查找第一个前缀匹配成功的元素
  5. 查找小于等于的元素
  6. 查找大于等于的元素
  7. 查找上一个或者下一个不同的元素，能够快速跳过重复的元素
  8. 查找重复的元素时，会按照插入的顺序依次返回
  • 插入
  1. 标准元素插入：如果元素存在，创建一个重复的对象
  2. 唯一元素插入：如果元素存在，返回存在的那个元素

时间复杂度

EBtree的时间复杂度由三个元素决定：

  • 树中能够存储的不同元素的总数目：P
  • 树中的当期元素个数：N
  • 树中的一个元素的重复个数：D

EBtree的设计中，并不是一个平衡树。由于这个原因，最坏的情况是一个32个元素的树，每个元素对应二进制的一位。不过这种情况下的增删查操作并不复杂。在一个平衡树中，可能需要6层来存储32个数据，ebtree需要32层，如果每层的操作能够节省5倍，那么ebtree则总体更省。

最小最大平均时间复杂度用来描述数据结构在不同情况下的时间开销，一般最小是最好的情况，最大是最坏情况，平均代表随机元素操作情况下。ebtree最主要的操作是从一个节点跳到另外一个节点。

复杂度：

  • 查找： min=1, max=log(P), avg=log(N)
  • 从root插入：min=1, max=log(P), avg=log(N)
  • 从重复数据的节点插入：min=1, max=log(D), avg=log(D)/2 after lookup
  • 删除：min=1, max=1, avg=1
  • 上一个/下一个 min=1, max=log(P), avg=2 :
 N/2 nodes need 1 hop  => 1*N/2
 N/4 nodes need 2 hops => 2*N/4
 N/8 nodes need 3 hops => 3*N/8
 ...
 N/x nodes need log(x) hops => log2(x)*N/x
 Total cost for all N nodes : sum[i=1..N](log2(i)*N/i) = N*sum[i=1..N](log2(i)/i)
 Average cost across N nodes = total / N = sum[i=1..N](log2(i)/i) = 2

当前的ebtree每一个节点只有2个分支，很多现代的树可能支持更多的分支，从而降低层数，但是这样对EBtree会带来更多的复杂度，并且删除会出现问题，因此暂时不支持更多的分支。

属性

EBtree的一些有用的属性：

  • 在一个EB节点中，node通常会在leaf部分的上层，绝对不会在leaf的下面，或者在与leaf平行的另外一个分支内，这表明直接附在根root下面的节点的node部分是空，node_p = NULL，这种node和leaf层次设计的好处是当向下遍历树的时候，当到达leaf时，它对应的node部分一定已经访问过（除非是树的第一个叶子），这样可以比较高效的使用cache。
  • 指向下层的node或者leaf的指针保存在branch中，只有根root才可能拥有两个NULL的branch，其它的节点都不会有两个NULL的branch，由于node是挂在根root的左分支下面，因此向上访问树元素的时候不会碰见左分支是NULL的情况，也就是说当一个根root的左分支是NULL时，才可能是一个空树。同样的，判断一个node是否是根root的方式是检查其右分支是否为NULL。
  • 如果node连接到自己的leaf时，它只有一个branch指向自己的leaf，leaf的leaf_p也指向自己。
  • node部分绝不对有node_p指向自己，一定是另外一个node或者根root
  • 一个node在一个树中当且仅当它的leaf_p不是空
  • 一个node不可能有两个相等的branch，除非是根root的两个分支都是NULL
  • 删除只会对leaf有影响，当一个leaf被删除时，它的父节点也必须要释放（除非父节点是根root），它的兄弟分支需要挂在祖父node下代替父节点。同时，当leaf被删除时，它对应的node部分也要从树上删除和释放，如果这个node部分和leaf的父节点不同，刚刚释放的父节点需要替换leaf对应的node部分，一个释放的node节点再也不会被树用到，没有任何指针再指向它。
  • node部分的bit索引表明元素key数据的二进制位置，branch的左右分别代表0和1。这意味着，一个node的bit是0的话，它的两个子分支都是叶子，因为bit等于0意味着key倒着从1开始以上的位置的二进制都相同，只要第0位不同，左子树是公共的prefix部分+0,右子树是prefix+1，bit如果是负值的话，表明它下面的子树存储的是相同元素。第一个拥有两个leaf的node它的bit=-1，这个数值随着重复的元素对数减少，重复元素插入时，node被插入在右侧查找最高的bit，如果没有bit=-1，我们在最后一个叶子上插入，否则我们在某一个node它的bit！=父节点的bit+1的上面插入。
  • eb_next操作从左到右遍历元素，也就是从key的低进制到高进制，如果是重复元素，则会按照插入顺序返回，eb_first操作返回最左侧的元素。
  • eb_prev操作从右到左遍历元素，也就是从key的高进制到低进制，如果是是重复元素，则会按照插入的反顺序翻译，eb_last操作返回最右边的元素。
  • 如果一个node的右分支等于1，则不允许存储重复元素，当一个重复的元素被插入时，会返回之前被插入的相同元素。

操作原则

插入

Ebnode-ins

初始时，树是空的，只包含一个根root，它的两个子分支都是NULL

当第一个EB元素被插入式，它的leaf部分直接挂在根root的左分支上，因此它的node部分没有被使用，这是唯一的node部分不使用的情况。之后，再插入一个新的EB元素时，node部分会插入在根root和上一个元素的leaf部分之间，用来连接新的元素的leaf部分，新插入的元素的node部分的两个分支分别指向第一个元素的leaf和新插入的元素的leaf部分。因此，在node之下不可能有空的分支。

当第三个EB元素被插入时，它可能被插入在第二个元素的node和leaf部分之间，第二个元素的这两部分被拉伸分开了。需要注意的是，这个元素的node部分必定存在于它的leaf部分和根root之间的某个路径上。这个规则也适用于后来的元素插入，下面是一个保存了1-5,21-25十个元素的ebtree结构（这个图的bit表示的并不太准确，不要被误导）：Ebtree-1

插入重复数据

EBtree支持重复数据，并且保存了他们的顺序。这是一个特别重要的属性，特别是对于一个公平的调度系统，因为调度的事件可能具有相同的时间戳，但是需要按照它们被唤醒的顺序来执行，否则可能导致某些任务饿死。

为了存储相同的元素，我们在重复的那个元素的leaf部分向下生成一个子树，生成的方式和正向的一样，只不过bit位置翻了过来，这样就能使得在没有额外开销的情况下支持重复数据，使用相同的方法。并且操作节点的顺序和他们被偏离的顺序一致。

删除

当一个元素被删除，也就是leaf部分删除时，它的父节点必须也要释放，除非父节点是根root，它的兄弟节点需要重新挂在祖父节点上，同时一个叶子被释放时，它对应的node部分也要被删除，如果这个node部分不是leaf部分的父节点时，刚才释放的父节点可以用来替换这个需要删除的node部分，EBtree在删除之后并不需要平衡，因此删除的操作的时间复杂度是O(1)，释放后的元素不会再被使用，因此没有任何指针再跟踪它。

遍历树

树的遍历可以从左到右，或者从右到左，通常是按照key的数字大小顺序，或者相同元素的插入顺序，可用的遍历有：

  • eb_first(root):返回从root下面子树的第一个元素
  • eb_last(root):返回从root下面子树的最后一个元素
  • eb_next(node)：返回某个元素之后的下一个元素
  • eb_prev(node):返回某个元素之前的第一个元素

这些操作会返回一个node，或者NULL如果找到最后还没有查到符合条件的元素，同时还提供了2种针对重复数据的操作：

  • eb_next_unique(node):返回下一个不重复key值的node
  • eb_prev_unique(node):返回上一个不重复key值的node

实现细节

现在唯一可知的实现版本是作者Willy的，它在32和64位的平台上工作良好，并且利用了指针占用4字节空间，最低的2位地址并没有被使用，因此可以利用这个特性，使得节点的指针带上一些额外的属性：

  • branch如果指向一个node，最低位bit=0
  • branch如果指向一个leaf，最低位bit=1
  • node_p如果在branch的左分支，则最低位bit=0
  • leaf_p如果在branch的右分支，最低位bit=1

这是一个非常重要的优化，可以减少内存的引用和使用，不需要访问元素的上下层就可以知道其所处的位置。

根root的右分支一直是NULL，但是按照上面的一些原则，我们可以在这个位置上设置一些标志，目前EB_ROOT_UNIQUE表明，这棵树不支持重复元素，当插入一个已经存在的元素，只会返回已经存在的元素的node指针。

当前版本的实现分成共用部分代码和特定类型代码，这使得后续增加类型变得简单，目前，指针，无符号/有符号真行，字符串，内存块类型可以保存在EBtree中。

第六版的实现增加支持内存块的前缀匹配，并且支持前缀插入，最长匹配，并且和现有的一些特性兼容（遍历，重复，删除，……），这种特性适用于地址匹配，路由选择场景，有些更新还没有在这个文档体现。

第七版作者增加了ebtree的变种rebtree，目前还比慢，不推荐使用

当前版本中，为了区分不同类型的实现，名称规则是ebXX_node，代表类型XX的节点，理论上，一个eb_node可以包含除了key之外的任何数据除了，只有插入和查找需要key，其他操作只需要更改树结构即可。这种特性使得一些操作可以不受类型限制：

/* generic types */
typedef void eb_troot_t;

struct eb_root {
	eb_troot_t    *b[EB_NODE_BRANCHES]; /* left and right branches */
};

struct eb_node {
	struct eb_root branches; /* branches, must be at the beginning */
	eb_troot_t    *node_p;   /* link node's parent */
	eb_troot_t    *leaf_p;   /* leaf node's parent */
	int           bit;       /* link's bit position. */
};

/* 32-bit specific types */
typedef unsigned int u32;

struct eb32_node {
	struct eb_node node; /* the tree node, must be at the beginning */
	u32 key;
};

eb_node处在ebXX_node的最开始，这对于cache使用和内存访问特别有效，因为前四个指针是最重要的结构，cpu会在第一时间加载。

参考

http://1wt.eu/articles/ebtree/

http://1wt.eu/tools/ebtree/

这篇介绍非常到位，HAProxy的独门武器：ebtree

发表评论
本文的评论功能被关闭了.