首页
论坛
专栏
课程

[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别

2019-11-29 09:44 696

[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别

2019-11-29 09:44
696

    上一篇文章我们详细介绍了红黑树,但初学者往往云里雾里,不知道实战项目该用谁,今天笔者就从结合himqtt的源码,从物联网安全角度来对比一下哈希数据结构和红黑树的应用场景。 哈希和红黑树的详细教程很多,本文就不重复了,

一、哈希和红黑树基本原理

    哈希(hash)也称散列,通过散列算法变成固定的输出到数组,所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。


 

    红黑树的自旋是天才的设计,是一种特殊的平衡二叉树数据结构,特点也是从几十万的数据里面几步就能查找到,速度快。


 

二、物联网安全使用场景

    首先github上下载源码,https://github.com/qq4108863/himqtt ,在src\waf目录有hashmap.c和mqtt_rbtree.c ,分别是哈希和红黑树算法。

1、速度对比

    物联网可能是数百万设备联网,对高并发要求很大,所以,对网络安全产品第一要求的是性能和速度。总体来说,哈希查找速度会比红黑树快,而且查找速度基本和数据量大小无关,属于常数级别;而RB树的查找速度是log(n)级别。

    红黑树查找和删除的时间复杂度都是O(logn),Hash查找和删除的时间复杂度都是O(1)。 如果红黑树的树高度不深如小于8,采用的是整形数字查找,两者性能没有太多的差异。

    也就是并非所有的场景,哈希都比红黑树快,要看代码的优化程度。himqtt使用的linux高并发EPOLL模式事件管理,就是红黑树。

2、数据预知

    静态数据,可以基本预知大小,用哈希。如himqtt初始化的攻击规则就几百条在可控范围内,另外TOPIC黑白名单、URL地址等也不会太多,也是用的哈希就可以了。

    动态数据,如统计IP地址、任务调度、epoll高并发事件管理,无法判断多少,可能很少,也可能巨多,用红黑树更佳。当然,如果大概知道设备IP地址数量在一定范围,如只有几千,完全也可以用哈希。

3、内存消耗

    对内存要求严格的地方,如嵌入式系统,用红黑树。红黑树占用的内存更小(仅需要为其存在的节点分配内存),而哈希事先就应该分配足够的内存存储散列表,浪费内存。

    对内存消耗无所谓的地方,如服务器有巨大的内存,用哈希。哈希最大的缺点是内存分配得小,可能元素就会冲突,冲突的元素大于8个成链表,效率还不如红黑树。 Java 的hashmap就是把哈希和红黑树结合在以前的。当同一个hash值的节点数不小于8时,不再采用单链表形式存储,而是采用红黑树。

4 复杂程度

    哈希更简单,红黑树算法复杂一点,不过这都不是事,大神早开源了很多稳定的版本。

三、应用场景总结

    红黑树是有序的,哈希是无序的,根据项目需求来选择,阿里巴巴的很多项目用红黑树更多,笔者认为主要还是和内存有关,如果内存要求苛刻的项目,就用红黑树;如果内存足够大,牺牲内存换取更快的速度,哈希完全适合。

    himqtt开源版大量采用哈希算法,可能和速度并发要求有关。总之,数据结构是物联网安全最基础的学科。



[公告]安全测试和项目外包请将项目需求发到看雪企服平台:https://qifu.kanxue.com

最新回复 (5)
xinpoo 1 2019-11-29 10:26
2
1
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 17层才能达到10万级别的容量,从这个树里查找一个字符串,通常情况估计要10次左右的字符串比较,有另外一个算法,性能和内存都碾压红黑树:https://linux.thai.net/~thep/datrie/datrie.html
库尔 2019-11-29 11:25
3
0
看了楼主产品介绍感觉对ai有兴趣,想问一些楼主关于研究ai流量检测一些问题:1.用什么中间语言去填写矩阵数据。看了几篇文章,目前我是想采用cws的log行为监控或者翻译成十六进制字符串去建立中间语言,问题是如果是oday的话,那些log日志行为监控输出的信息可能不可靠,因为有些函数是你监控不到。如果翻译成十六进制字符串,那么怎么截取才好呢。2.因数据少目前用的是DPCNN瘦身版防止过拟合,但也最多也只能到9成准确率。
xiaoduoduo 2019-11-29 17:01
4
0
是的,我一直在研究AI,就目前来说, AI就像大猩猩,智力很低,比如识别一些图片都很费力。 而黑客攻击和0day漏洞,即使是人类,不是学这个专业的,怎么教也教不会,何况是机器。 AI最不可能取代的就是网络安全行业, 至于中间语言更不能复杂,否则安全专家一眼就知道是攻击,转换成中间语言了,人类也识别不了。 网络安全,坚持最小化原则 + 异常检测 是正道,人工智能在网络安全上,还有很长的路要走。 
xiaoduoduo 2019-11-29 17:08
5
0
trie树,实际上是hash树的一种变种,其特点是快,但内存消耗很大。 我个人在服务器上,不严格要求内存的地方很喜欢用hash, 但是嵌入式设备 就不行了。
xinpoo 1 2019-11-29 18:34
6
0
xiaoduoduo trie树,实际上是hash树的一种变种,其特点是快,但内存消耗很大。 我个人在服务器上,不严格要求内存的地方很喜欢用hash, 但是嵌入式设备 就不行了。
LZ不仔细看看就下结论啦。。Double-Array Trie,它是通过2个数组保存trie树,所以又叫"双数组",可以"见缝插针",避免了普通trie树中容易存在大量空闲结点的问题,而且比如"1234567AAA"、"1234567BBB"这2个字符串,由于公共的"1234566"只占一份内存,所以假设用一个.txt文件保存了10万条url,大小为S,用这10万条url构造成的双数组trie,大小往往比S还小。性能的话,不管树中有多少条url,查询1条url永远只需要1次匹配。感兴趣的话,可以花时间看看,顺便看看别人是怎么描述算法的。另外还有个你不喜欢听的建议,红黑树本身就很复杂了,你没描述清楚也就算了,就别再搞个标题吓人了。。
游客
登录 | 注册 方可回帖
返回