fightclub

发表于 | 分类于

ntopng是什么？

ntopng是一个开源的网络流量分析平台。是传统的网络监控平台ntop的新一代产品。
通常我们使用wireshark抓包工具对特定的网络接口进行抓包来进行详细流量分析。
但是，这样操作会有以下几个问题：

  1. 前期准备十分麻烦。如果采取旁路抓包的方式，需要先在交换机做流镜像，并且需要在该端口进行抓包。
  2. wireshark需要耗费大量内存，导致程序不稳定。难以进行持久的抓包统计分析。
  3. 无法进行大范围统计，不能了解全网网络情况。

我们再来看ntopng是如何解决以上几个问题的。

  1. ntopng是一个B/S架构的平台。管理员只需要配置好采集部分就可以通过浏览器查看统计结果
  2. ntopng专门为大数据量采集进行设计。在不需要持续存储的情况下，采用rrd数据库进行数据保存。而且ntopng社区专门设计了一个高性能的持续存储方案n2disk进行大量数据包采集。
  3. ntopng使用配套的nprobe来支持sflow,netflow流量采集协议。能够以极小的成本进行大范围的流量分析。

部署

ntopng的部署有源码安装和二进制安装两种方式。
源码安装需要从社区官网下载源码编译，而二进制安装需要切换到互联网，把yum指向指定的软件安装源进行安装。
社区网站有下面几个产品：

  • ntopng —web平台
  • nprobe —一个可扩展的采集器。支持多种采集架构和插件，并且支持sflow协议和netflow协议采集。
  • n2disk —抓包数据存储库
  • pf_ring —高性能的抓包库，可以让普通pc也能进行大数据包采集
  • ndpi —跨平台的高层协议解析库
  • nbox —小型嵌入式采集系统

我都安装了，但实际使用起来只有ntopng和nprobe有用到。ndpi已经集成在ntopng内部。其他组件并没有用到。
另外，二进制安装默认安装的是企业试用版，如果一段时间不激活，会降成社区版。
企业版的dashboard界面和社区版有所不同，并且提供了报表功能。对，社区版不含报表功能。升级企业版需要150欧元。

配置

我把ntopng和nprobe装在同一台虚拟机上。nprobe做sflow采集，将结果发送到本地的zmq消息队列上，ntopng再从该队列读取信息。
nprobe启动参数如下:

1
/usr/local/bin/nprobe --zmq tcp://127.0.0.1:5556 -i none -n none --collector-port 6343 -b 2

由于ntopng参数较多，我把他们放入了配置文件中

1
2
3
4
5
-G=/var/tmp/ntopng.pid
-d=/storage/ntopng
-i=tcp://127.0.0.1:5556
-p=/etc/ntopng/protos
-F=es;ntopng;ntopng-%Y.%m.%d;http://169.24.2.96:9200/_bulk

配置文件中指定了pid文件位置，存储地点，需要采集的zmq队列接口，ndpi协议文件位置以及elasticsearch参数。
其中，比较主要的是ndpi协议文件，我们通过该文件进行协议自定义。

格式是 [tcp|udp]:端口号@自定义协议名。

我们的示例文件内容如下：

1
2
3
tcp:42966@HP-RGS
tcp:49152-49157@vmware-tools
udp:4172@vmware-view

历史信息统计

标准安装后，ntopng显示的是实时信息。官方提供两种方式来进行历史数据统计。

  • 安装mysql数据库
  • 使用elasticsearch

目前我配置的是elasticsearch，但是并没有做具体的字段优化。我还没有试验本地mysql的效果如何。
另外，elasticsearch提供一个packetbeat的数据包统计方案，我也没试过这两种方案的对比。

交换机上的sflow协议配置

我们使用的h3c交换机主要通过rmon,netstream,sflow三种协议实现流量采集。rmon是对snmp的增强，主要实现的是流量报警。netstream,sflow实现的是对报文的采样和统计。因为是采样分析，所以并不占用多少带宽而且性能也很不错。但是因为缺少了信息，采集精度上会打折扣。如果想要更大的精度可以再添加一个抓包模式的nprobe。

sflow配置样例:

配置sflow collector地址：

1
sflow collector 1 ip 169.24.2.200 description ntop

配置监控端口：

1
2
3
4
5
6
7
8
9
10
interface GigabitEthernet7/0/10
 port link-mode bridge
 description dell
 port link-type trunk
 port trunk permit vlan all
 broadcast-suppression 1
 sflow flow collector 1      #采集器编号
 sflow sampling-rate 4000    #采样频率，这里是1/4000.即每4000个包采一个
 sflow counter collector 1   #计数采集器编号
 sflow counter interval 120  #采集周期120秒

其他问题

ntopng只针对tcp,ip的流量、协议的分布进行统计。并没有细致到tcp的具体参数，比如包大小分布统计、tcp往返周期统计等等。好在这些需求并不常见。如果有这种需求，还得用wireshark

fightclub

发表于 | 分类于

标准的堆插入元素的算法很好理解，而且也很容易知道向堆中插入一个元素的代价是lgn。

按照最常规的想法，把一个数组中所有元素添加到一个堆中，依次压入即可。压入n个元素的代价就是

$\sum_{i=1}^N\log_2i$

结果等于$log_2n!$.根据斯特林公式，n!在n趋向于无穷大时可以近似看成$\sqrt{2\pi n} ({n\over e})^n$。

因此，总代价可以看成$n \log_2({n\over e})+o(n)$,比O(n)的阶要大一些。

直觉上，这个操作的复杂度应该是要比这个低的。因为将n个元素完整排序的代价不过是nlgn。而堆应该是一个半排序。不应该接近nlgn。

这个直觉是正确的，heapify操作正是一个线性时间的算法.

举个python的标准库heapq里面的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def cmp_lt(x, y):
    # Use __lt__ if available; otherwise, try __le__.
    # In Py3.x, only __lt__ will be called.
    return (x < y) if hasattr(x, '__lt__') else (not y <= x)
def heapify(x):
    """Transform list into a heap, in-place, in O(len(x)) time."""
    n = len(x)
    # Transform bottom-up.  The largest index there's any point to looking at
    # is the largest with a child index in-range, so must have 2*i + 1 < n,
    # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
    # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
    # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
    for i in reversed(xrange(n//2)):
        _siftup(x, i)
def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if cmp_lt(newitem, parent):
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem
def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not cmp_lt(heap[childpos], heap[rightpos]):
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

heapify操作主要有3个过程，heapify对一半的元素调用_siftup，而_siftup又调用了_siftdown。

这个过程作用的原理是什么？

_siftup(heap，pos)最开始部分的代码很明显，就是把pos处的元素沿着最小路径一路向下降到底。途中所比较的子节点依次上浮一层。而_siftdown(heap,startpos,ps)过程则是标准的堆插入动作，将pos处的元素上浮直到小于startpos时停止，也就是startpos的左兄弟节点或上一层节点。

这可以理解为一个从倒数第二层开始构建堆的过程。第一轮循环把最下面两层的3个节点的元素变成堆，再依次向上，通过插入一个上一层元素，将两个堆合并。因为每上一层，这层下面的两个元素分别都是这两棵子树的最小元素。

这个过程可以看成类似数学归纳法的原理。第一个元素成立，而n成立确保n+1成立，因此对所有元素就成立。逐个插入的问题规模是线性增长的，比如比n小的元素是n-1，而归并操作的问题规模是折半的。这就相当于在逐次插入元素的时候，当插到第四个元素的时候，停止向原堆插入，而向新堆插入。当两个堆平衡以后，再将两个堆合并。

因此，他的时间T(n)=2T(n/2)+2lg(n/2)

这刚好落入了主方法的第一种情况，因此他的复杂度是O(n)

举个7个元素的例子。x=[a,b,c,d,e,f,g]。单纯计算比较次数

在最坏情况下，逐个插入算法

  1. 插入a
  2. 插入b,a与b比较一次
  3. 插入c,a鱼c比较一次
  4. 插入d,d与b比较一次，再与a比较一次
  5. 插入e，e与b比较一次，再与a比较一次
  6. 插入f,f与c比较一次,在与a比较一次
  7. 插入g,g与c比较一次，再与a比较一次

共计比较10次。

而heapify算法：

  1. a与b、c各比较一次
  2. d与e、f各比较一次
  3. a与d比较一次
  4. g与a比较一次
  5. b与c比较一次
  6. g与b比较一次

共计比较8次。

fightclub

发表于 | 分类于

b树

这是在blog迁移后，将原blog的部分文章重新进行迁移。回头看以前写的东西，很多原来写的东西都变得理所当然，无需赘言;也有很多幼稚的错误,读起来感觉很傻。

btree的特点

btree最大的特点在于是一个绝对平衡的多路搜索树。能够保证所有叶子节点在同一层。同时由于每层的节点很多，所以树的深度很小。能够保证即使btree的下层节点不在内存里，也可以在最短的跳跃后找到。
btree能够保证这个特性的方法就是在保证树的度数超过阈值后，采用分裂的方法，而不是继续向下插入。

这个方法的具体描述就是。btree中对所有非根节点的所含的数据数量有这样一个要求，最少不能少于t-1,最大不能超过2t-1。根节点可以少于t-1但不能超过2t-1。t >=2
插入的时候一旦要超过这个数量，就把树分裂。删除的时候一旦要少于这个数量，要么从兄弟节点借一个节点来充数，如果兄弟节点也不够，就把子树合并。
这样，保证了btree节点最多数据的时候数据的数是一个奇数。因为2t-1==2(t-1)+1，所以一个满节点可以分裂成一个至少有一个数据的根，外加2个最小的节点。

多说无益，上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
#!/usr/bin/env python
from random import randint,choice
from bisect import bisect_left
from collections import deque
class InitError(Exception):
    pass
class ParaError(Exception):
    pass
class KeyValue(object):
    __slots__=('key','value')
    def __init__(self,key,value):
        self.key=key
        self.value=value
    def __str__(self):
        return str((self.key,self.value))
    def __cmp__(self,key):
        if self.key>key:
            return 1
        elif self.key==key:
            return 0
        else:
            return -1
class BtreeNode(object):
    def __init__(self,t,parent=None):
        if not isinstance(t,int):
            raise InitError,'degree of Btree must be int type'
        if t<2:
            raise InitError,'degree of Btree must be equal or greater then 2'
        else:
            self.vlist=[]
            self.clist=[]
            self.parent=parent
            self.__degree=t
    @property
    def degree(self):
        return self.__degree
    def isleaf(self):
        return len(self.clist)==0
    def traversal(self):
        result=[]
        def get_value(n):
            if n.clist==[]:
                result.extend(n.vlist)
            else:
                for i,v in enumerate(n.vlist):
                    get_value(n.clist[i])
                    result.append(v)
                get_value(n.clist[-1])
        get_value(self)
        return result
    def show(self):
        q=deque()
        h=0
        q.append([self,h])
        while True:
            try:
                w,hei=q.popleft()
            except IndexError:
                return
            else:
                print [v.key for v in w.vlist],'the height is',hei
                if w.clist==[]:
                    continue
                else:
                    if hei==h:
                        h+=1
                    q.extend([[v,h] for v in w.clist])
    def getmax(self):
        n=self
        while not n.isleaf():
            n=n.clist[-1]
        return (n.vlist[-1],n)
    def getmin(self):
        n=self
        while not n.isleaf():
            n=n.clist[0]
        return (n.vlist[0],n)
class IndexFile(object):
    def __init__(fname,cellsize):
        f=open(fname,'wb')
        f.close()
        self.name=fname
        self.cellsize=cellsize
    def write_obj(obj,pos):
           pass
    def read_obj(obj,pos):
        pass
class Btree(object):
    def __init__(self,t):
        self.__degree=t
        self.__root=BtreeNode(t)
    @property
    def degree(self):
        return self.__degree
    def traversal(self):
        """
        use dfs to search a btree's node
        """
        return self.__root.traversal()
    def show(self):
        """
        use bfs to show a btree's node and its height
        """
        return self.__root.show()
    def search(self,mi=None,ma=None):
        """
        search key-value pair within range mi<=key<=ma.
        if mi or ma is not specified,the searching range
        is key>=mi or key <=ma
        """
        result=[]
        node=self.__root
        if mi is None and ma is None:
            raise ParaError,'you need setup searching range'
        elif mi is not None and ma is not None and mi>ma:
            raise ParaError,'upper bound must be greater or equal than lower bound'
        def search_node(n):
            if mi is None:
                if not n.isleaf():
                    for i,v in enumerate(n.vlist):
                        if v<=ma:
                            result.extend(n.clist[i].traversal())
                            result.append(v)
                        else:
                            search_node(n.clist[i])
                            return
                    search_node(n.clist[-1])
                else:
                    for v in n.vlist:
                        if v<=ma:
                            result.append(v)
                        else:
                            break
            elif ma is None:
                if not n.isleaf():
                    for i,v in enumerate(n.vlist):
                        if v<mi:
                            continue
                        else:
                            search_node(n.clist[i])
                            while i<len(n.vlist):
                                result.append(n.vlist[i])
                                result.extend(n.clist[i+1].traversal())
                                i+=1
                            break
                    if v.key<mi:
                        search_node(n.clist[-1])
                else:
                    for v in n.vlist:
                        if v>=mi:
                            result.append(v)
            else:
                if not n.isleaf():
                    for i,v in enumerate(n.vlist):
                        if v<mi:
                            continue
                        elif mi<=v<=ma:
                            search_node(n.clist[i])
                            result.append(v)
                        elif v>ma:
                            search_node(n.clist[i])
                    if v<=ma:
                        search_node(n.clist[-1])
                else:
                    for v in n.vlist:
                        if mi<=v<=ma:
                            result.append(v)
                        elif v>ma:
                            break
        search_node(node)
        return result
    def insert(self,key_value):
        node=self.__root
        full=self.degree*2-1
        mid=full/2+1
        def split(n):
            new_node=BtreeNode(self.degree,parent=n.parent)
            new_node.vlist=n.vlist[mid:]
            new_node.clist=n.clist[mid:]
            for c in new_node.clist:
                c.parent=new_node
            if n.parent is None:
                newroot=BtreeNode(self.degree)
                newroot.vlist=[n.vlist[mid-1]]
                newroot.clist=[n,new_node]
                n.parent=new_node.parent=newroot
                self.__root=newroot
            else:
                i=n.parent.clist.index(n)
                n.parent.vlist.insert(i,n.vlist[mid-1])
                n.parent.clist.insert(i+1,new_node)
            n.vlist=n.vlist[:mid-1]
            n.clist=n.clist[:mid]
            return n.parent
        def insert_node(n):
            if len(n.vlist)==full:
                insert_node(split(n))
            else:
                if n.vlist==[]:
                    n.vlist.append(key_value)
                else:
                    if n.isleaf():
                        p=bisect_left(n.vlist,key_value)  #locate insert point in ordered list vlist
                        n.vlist.insert(p,key_value)
                    else:
                        p=bisect_left(n.vlist,key_value)
                        insert_node(n.clist[p])
        insert_node(node)
    def delete(self,key_value):
        node=self.__root
        mini=self.degree-1
        def merge(n,i):
            n.clist[i].vlist=n.clist[i].vlist+[n.vlist[i]]+n.clist[i+1].vlist
            n.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist
            n.clist.remove(n.clist[i+1])
            n.vlist.remove(n.vlist[i])
            if n.vlist==[]:
                n.clist[0].parent=None
                self.__root=n.clist[0]
                del n
                return self.__root
            else:
                return n
        def tran_l2r(n,i):
            left_max,left_node=n.clist[i].getmax()
            right_min,right_node=n.clist[i+1].getmin()
            right_node.vlist.insert(0,n.vlist[i])
            del_node(n.clist[i],left_max)
            n.vlist[i]=left_max
        def tran_r2l(n,i):
            left_max,left_node=n.clist[i].getmax()
            right_min,right_node=n.clist[i+1].getmin()
            left_node.vlist.append(n.vlist[i])
            del_node(n.clist[i+1],right_min)
            n.vlist[i]=right_min
        def del_node(n,kv):
            p=bisect_left(n.vlist,kv)
            if not n.isleaf():
                if p==len(n.vlist):
                    if len(n.clist[-1])>mini:
                        del_node(n.clise[p],kv)
                    elif len(n.clist[p-1])>mini:
                        tran_l2r(n,p-1)
                        del_node(n.clist[-1],kv)
                    else:
                        del_node(merge(n,p-1),kv)
                else:
                    if n.vlist[p]==kv:
                        left_max,left_node=n.clist[i].getmax()
                        if len(n.clist[p].vlist)>mini:
                            del_node(n.clist[p],left_max)
                            n.vlist[p]=left_max
                        else:
                            right_min,right_node=n.clist[i+1].getmin()
                            if len(n.clist[p+1].vlist)>mini:
                                del_node(n.clist[p+1],right_min)
                                n.vlist[p]=right_min
                            else:
                                del_node(merge(n,p),kv)
                    else:
                        if len(n.clist[p].vlist)>mini:
                            del_node(n.clist[p],kv)
                        elif len(n.clist[p+1].vlist)>mini:
                            tran_r2l(n,p)
                            del_node(n.clist[p],kv)
                        else:
                            del_node(merge(n,p),kv)
            else:
                try:
                    pp=n.vlist[p]
                except IndexError:
                    return -1
                else:
                    if pp!=kv:
                        return -1
                    else:
                        n.vlist.remove(kv)
                        return 0
        del_node(node,key_value)
def test():
    mini=50
    maxi=200
    testlist=[]
    for i in range(1,1001):
        key=randint(1,1000)
        #key=i
        value=choice('abcdefg')
        testlist.append(KeyValue(key,value))
    mybtree=Btree(5)
    for x in testlist:
        mybtree.insert(x)
    print 'my btree is:\n'
    mybtree.show()
    #mybtree.delete(testlist[0])
    #print '\n the newtree is:\n'
    #mybtree.show()
    print '\nnow we are searching item between %d and %d\n\n'%(mini,maxi)
    print [v.key for v in mybtree.search(mini,maxi)]
    #for x in mybtree.traversal():
    #    print x
if __name__=='__main__':
    test()

b+树

在之前，我一直只把b+tree当成是btree的一种变形，或者说是在某种情况下的一种优化，另外一些情况可能还是btree好些。但是做完之后才发现，b+tree在各种情况都可以完全取代btree，并能够让索引性能得到比btree更好的优化。因为b+tree设计的核心要点，是为了弥补btree最大的缺陷。

btree最大的缺陷是什么?

首先,我们知道对于btree和b+tree这种多路搜索树来说，一个很重要的特点就是树的度数非常大。因为只有这样才能够降低树的深度，减少磁盘读取的次数。而树的度数越大，叶子节点在树中的比例就越大。假设度数为1000，那么叶子节点比他上一层内部节点的数量至少要多1000倍，在上一层就更加可以忽略不计了。可以说树种99.9%的节点都是叶子节点。 但是对于btree来说，所有节点都是一样的结构，都含有一定数量的数据和指向节点的指针。这两项数据占据btree节点的几乎全部的空间。一个节点内的数据的数量比硬盘指针的数量少一，可以说和指针的数量几乎相等。对于python这种动态类型语言感觉不出来，但是对于C这种固定类型语言来说，即使这个children list数组为空，这个数组的空间也都是预留出去的。导致的结果就是占绝大多数的叶子节点的children list指针数组所占的磁盘空间完全浪费。

一个数据的大小和硬盘指针的大小取决于key-value中key和value大小的比值。假如说这个比值是2:1。那么btree浪费了几乎1/3的空间。

b+tree针对这个问题的，把叶子节点和内节点的数据结构分开设计，让叶子节点不存放指针。因此同样大小的叶子节点，b+tree所能包含数据数量要比btree大。按照上面的假设就是大1/2。数的深度很可能比btree矮，大范围搜索或遍历所需要的载入磁盘的次数也少。

另外，b+tree还有一个特点是所有数据都存放在叶子节点，这些叶子节点也可以组成一个链表，并把这个链表的表头拿出来，方便直访问数据。有些文章认为这对于范围搜索来说是个巨大的优化。但是就我的看法，这个特性最大的作用仅仅是让代码更容易一些，性能上，只会比树的遍历差，而不会比树的遍历好。因为不管是用指向叶子节点的指针搜，还是用树的遍历搜，所搜索的节点的数量都是几乎相同的。在相同大小的范围搜索的性能，只取决于访问顺序的连续性。从树根向下遍历，那么一次可以取得大量的子节点的范围，并针对这些节点做访问排序，得到更好的访问连续性。如果是沿着指向兄弟节点的指针搜索，一是兄弟节点也许是后插入的，存放并不一定和自己是连续的，二是只有每次从硬盘中将该节点载入到内存，才知道兄弟节点放在硬盘哪个位置，这又变成了对硬盘的一个随机的同步操作，性能的下降可想而知。
说b+tree因为有指向兄弟节点的指针方便数据库扫库这种结论，是不正确的。

老规矩，不废话

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#!/usr/bin/env python
from random import randint,choice
from bisect import bisect_right,bisect_left
from collections import deque
class InitError(Exception):
    pass
class ParaError(Exception):
    pass
class KeyValue(object):
    __slots__=('key','value')
    def __init__(self,key,value):
        self.key=key
        self.value=value
    def __str__(self):
        return str((self.key,self.value))
    def __cmp__(self,key):
        if self.key>key:
            return 1
        elif self.key==key:
            return 0
        else:
            return -1
class Bptree_InterNode(object):
    def __init__(self,M):
        if not isinstance(M,int):
            raise InitError,'M must be int'
        if M<=3:
            raise InitError,'M must be greater then 3'
        else:
            self.__M=M
            self.clist=[]
            self.ilist=[]
            self.par=None
    def isleaf(self):
        return False
    def isfull(self):
        return len(self.ilist)>=self.M-1
    def isempty(self):
        return len(self.ilist)<=(self.M+1)/2-1
    @property
    def M(self):
        return self.__M
class Bptree_Leaf(object):
    def __init__(self,L):
        if not isinstance(L,int):
            raise InitError,'L must be int'
        else:
            self.__L=L
            self.vlist=[]
            self.bro=None
            self.par=None
    def isleaf(self):
        return True
    def isfull(self):
        return len(self.vlist)>self.L
    def isempty(self):
        return len(self.vlist)<=(self.L+1)/2
    @property
    def L(self):
        return self.__L
class Bptree(object):
    def __init__(self,M,L):
        if L>M:
            raise InitError,'L must be less or equal then M'
        else:
            self.__M=M
            self.__L=L
            self.__root=Bptree_Leaf(L)
            self.__leaf=self.__root
    @property
    def M(self):
        return self.__M
    @property
    def L(self):
        return self.__L
    def insert(self,key_value):
        node=self.__root
        def split_node(n1):
            mid=self.M/2
            newnode=Bptree_InterNode(self.M)
            newnode.ilist=n1.ilist[mid:]
            newnode.clist=n1.clist[mid:]
            newnode.par=n1.par
            for c in newnode.clist:
                c.par=newnode
            if n1.par is None:
                newroot=Bptree_InterNode(self.M)
                newroot.ilist=[n1.ilist[mid-1]]
                newroot.clist=[n1,newnode]
                n1.par=newnode.par=newroot
                self.__root=newroot
            else:
                i=n1.par.clist.index(n1)
                n1.par.ilist.insert(i,n1.ilist[mid-1])
                n1.par.clist.insert(i+1,newnode)
            n1.ilist=n1.ilist[:mid-1]
            n1.clist=n1.clist[:mid]
            return n1.par
        def split_leaf(n2):
            mid=(self.L+1)/2
            newleaf=Bptree_Leaf(self.L)
            newleaf.vlist=n2.vlist[mid:]
            if n2.par==None:
                newroot=Bptree_InterNode(self.M)
                newroot.ilist=[n2.vlist[mid].key]
                newroot.clist=[n2,newleaf]
                n2.par=newleaf.par=newroot
                self.__root=newroot
            else:
                i=n2.par.clist.index(n2)
                n2.par.ilist.insert(i,n2.vlist[mid].key)
                n2.par.clist.insert(i+1,newleaf)
                newleaf.par=n2.par
            n2.vlist=n2.vlist[:mid]
            n2.bro=newleaf
        def insert_node(n):
            if not n.isleaf():
                if n.isfull():
                    insert_node(split_node(n))
                else:
                    p=bisect_right(n.ilist,key_value)
                    insert_node(n.clist[p])
            else:
                p=bisect_right(n.vlist,key_value)
                n.vlist.insert(p,key_value)
                if n.isfull():
                    split_leaf(n)
                else:
                    return
        insert_node(node)
    def search(self,mi=None,ma=None):
        result=[]
        node=self.__root
        leaf=self.__leaf
        if mi is None and ma is None:
            raise ParaError,'you need to setup searching range'
        elif mi is not None and ma is not None and mi>ma:
            raise ParaError,'upper bound must be greater or equal than lower bound'
        def search_key(n,k):
            if n.isleaf():
                p=bisect_left(n.vlist,k)
                return (p,n)
            else:
                p=bisect_right(n.ilist,k)
                return search_key(n.clist[p],k)
        if mi is None:
            while True:
                for kv in leaf.vlist:
                    if kv<=ma:
                        result.append(kv)
                    else:
                        return result
                if leaf.bro==None:
                    return result
                else:
                    leaf=leaf.bro
        elif ma is None:
            index,leaf=search_key(node,mi)
            result.extend(leaf.vlist[index:])
            while True:
                if leaf.bro==None:
                    return result
                else:
                    leaf=leaf.bro
                    result.extend(leaf.vlist)
        else:
            if mi==ma:
                i,l=search_key(node,mi)
                try:
                    if l.vlist[i]==mi:
                        result.append(l.vlist[i])
                        return result
                    else:
                        return result
                except IndexError:
                    return result
            else:
                i1,l1=search_key(node,mi)
                i2,l2=search_key(node,ma)
                if l1 is l2:
                    if i1==i2:
                        return result
                    else:
                        result.extend(l.vlist[i1:i2])
                        return result
                else:
                    result.extend(l1.vlist[i1:])
                    l=l1
                    while True:
                        if l.bro==l2:
                            result.extend(l2.vlist[:i2+1])
                            return result
                        else:
                            result.extend(l.bro.vlist)
                            l=l.bro
    def traversal(self):
        result=[]
        l=self.__leaf
        while True:
            result.extend(l.vlist)
            if l.bro==None:
                return result
            else:
                l=l.bro
    def show(self):
        print 'this b+tree is:\n'
        q=deque()
        h=0
        q.append([self.__root,h])
        while True:
            try:
                w,hei=q.popleft()
            except IndexError:
                return
            else:
                if not w.isleaf():
                    print w.ilist,'the height is',hei
                    if hei==h:
                        h+=1
                    q.extend([[i,h] for i in w.clist])
                else:
                    print [v.key for v in w.vlist],'the leaf is,',hei
    def delete(self,key_value):
        def merge(n,i):
            if n.clist[i].isleaf():
                n.clist[i].vlist=n.clist[i].vlist+n.clist[i+1].vlist
                n.clist[i].bro=n.clist[i+1].bro
            else:
                n.clist[i].ilist=n.clist[i].ilist+[n.ilist[i]]+n.clist[i+1].ilist
                n.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist
            n.clist.remove(n.clist[i+1])
            n.ilist.remove(n.ilist[i])
            if n.ilist==[]:
                n.clist[0].par=None
                self.__root=n.clist[0]
                del n
                return self.__root
            else:
                return n
        def tran_l2r(n,i):
            if not n.clist[i].isleaf():
                n.clist[i+1].clist.insert(0,n.clist[i].clist[-1])
                n.clist[i].clist[-1].par=n.clist[i+1]
                n.clist[i+1].ilist.insert(0,n.ilist[i])
                n.ilist[i]=n.clist[i].ilist[-1]
                n.clist[i].clist.pop()
                n.clist[i].ilist.pop()
            else:
                n.clist[i+1].vlist.insert(0,n.clist[i].vlist[-1])
                n.clist[i].vlist.pop()
                n.ilist[i]=n.clist[i+1].vlist[0].key
        def tran_r2l(n,i):
            if not n.clist[i].isleaf():
                n.clist[i].clist.append(n.clist[i+1].clist[0])
                n.clist[i+1].clist[0].par=n.clist[i]
                n.clist[i].ilist.append(n.ilist[i])
                n.ilist[i]=n.clist[i+1].ilist[0]
                n.clist[i+1].clist.remove(n.clist[i+1].clist[0])
                n.clist[i+1].ilist.remove(n.clist[i+1].ilist[0])
            else:
                n.clist[i].vlist.append(n.clist[i+1].vlist[0])
                n.clist[i+1].vlist.remove(n.clist[i+1].vlist[0])
                n.ilist[i]=n.clist[i+1].vlist[0].key
        def del_node(n,kv):
            if not n.isleaf():
                p=bisect_right(n.ilist,kv)
                if p==len(n.ilist):
                    if not n.clist[p].isempty():
                        return del_node(n.clist[p],kv)
                    elif not n.clist[p-1].isempty():
                        tran_l2r(n,p-1)
                        return del_node(n.clist[p],kv)
                    else:
                        return del_node(merge(n,p),kv)
                else:
                    if not n.clist[p].isempty():
                        return del_node(n.clist[p],kv)
                    elif not n.clist[p+1].isempty():
                        tran_r2l(n,p)
                        return del_node(n.clist[p],kv)
                    else:
                        return del_node(merge(n,p),kv)
            else:
                p=bisect_left(n.vlist,kv)
                try:
                    pp=n.vlist[p]
                except IndexError:
                    return -1
                else:
                    if pp!=kv:
                        return -1
                    else:
                        n.vlist.remove(kv)
                        return 0
        del_node(self.__root,key_value)
def test():
    mini=2
    maxi=60
    testlist=[]
    for i in range(1,10):
        key=i
        value=i
        testlist.append(KeyValue(key,value))
    mybptree=Bptree(4,4)
    for kv in testlist:
        mybptree.insert(kv)
    mybptree.delete(testlist[0])
    mybptree.show()
    print '\nkey of this b+tree is \n'
    print [kv.key for kv in mybptree.traversal()]
    #print [kv.key for kv in mybptree.search(mini,maxi)]
if __name__=='__main__':
    test()

总结

实现过程和btree很像，不过有几点显著不同。

  • 内节点不存储key-value，只存放key
  • 沿着内节点搜索的时候，查到索引相等的数要向树的右边走。所以二分查找要选择bisect_right
  • 在叶子节点满的时候，并不是先分裂再插入而是先插入再分裂。因为b+tree无法保证分裂的两个节点的大小都是相等的。在奇数大小的数据分裂的时候右边的子节点会比左边的大。如果先分裂再插入无法保证插入的节点一定会插在数量更少的子节点上，满足节点数量平衡的条件。
  • 在删除数据的时候，b+tree的左右子节点借数据的方式比btree更加简单有效，只把子节点的子树直接剪切过来，再把索引变一下就行了，而且叶子节点的兄弟指针也不用动。
fightclub

发表于 | 分类于

昨天zabbix conf首次来到中国。规模非常小，来的好像只有zabbix的作者alex一个人。
而且规模很小，也没什么宣传。我也是在浏览zabbix官方主页寻找有什么新东西的时候不小心发现的。于是就跑过去凑了个热闹。

会议的安排只有半天，其中有一半时间是alex个人讲ppt。 第一次见到alex真人，长得很帅，有些神似郑少秋。 但是讲的东西没什么新鲜的内容。

先说的他是怎么开始开发zabbix的。好像是在98年开始写第一行代码，那时候他在银行上班，做系统管理员，管些数据库之类的。觉得管起来特麻烦，就决定自己搞个平台。用下班和周末的时间弄弄，结果一不小心就越弄越大。最后干脆把工作辞了，专心写zabbix。一开始只有一个人，到后来周围也围绕了45个小伙伴。工作室也开到了日本和纽约。听起来和其他传奇故事差不多。

然后在介绍了下zabbix的大致功能。这其实也没啥好说的。

最后一帮子国内的几个做周边的厂商上来推广自己的产品后就结束。

会议中比较重要的信息就是alex明确表示会掌控zabbix所有的核心代码,以及产品方向。这也是为什么zabbix不参与资本运作，也不使用github接受其第三方提供的代码。这个想法很好理解,换我估计也会这样做。

期间我也问了几个问题。只是我对自己的英文比较没信心，让其他人帮忙翻译。
其中比较主要的就是我觉着很多时候二维的时间序列能够提供的信息是有限的。最好还能有类似es这种可以使用其他维度进行聚合的方法。以及act最好能有类似基于事件的交互机制。
其他也有人问到zabbix是否能够提供事务追踪以及更为丰富的api。
其实很多解决问题的关键点都差不多，就是history存储的设计太为简陋。如果要想有本质上的功能进步，必须操刀大改才行。