0%

框架简介

nanomsgzeromq作者Martin Sustrik用C重写的一套具有可扩展协议的一套通信框架,具体nanomsg与zeromq的不同与改进之处及为什么要用C重写在这里有详细的描述,个人感觉C的代码风格和目录结构组织都看着舒服多了,:),另外Martin Sustrik博客(http://250bpm.com/ )里面的每篇文章感觉都挺不错的,推荐关注订阅!

因为nanomsg还处于开发测试阶段,代码量还不是十分庞大,文档和注释也不够全面,于是想通过这一系列博客,一方面记录下我对nanomsg当前源码(https://github.com/250bpm/nanomsg)的阅读过程,同时也学习下一个好的开源项目的代码组织及开发过程。

源码组织

首先看下nanomsg的src目录:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
nn.h*                 // nanomsg对外暴露的接口api
transport.h* // 通信层定义,,目的应该是想暴露给用户以实现可扩展,但目前还包含utils下头文件……
inproc.h* // 一种transport,安装到include/nanomsg下
ipc.h* // 一种transport,安装到include/nanomsg下
tcp.h* // 一种transport,安装到include/nanomsg下
protocol.h* // 协议层定义,目的应该是想暴露给用户以实现可扩展,但目前还包含utils下头文件……
reqrep.h* // 一种protocol,安装到include/nanomsg下
pubsub.h* // 一种protocol,安装到include/nanomsg下
bus.h* // 一种protocol,安装到include/nanomsg下
pair.h* // 一种protocol,安装到include/nanomsg下
pipeline.h* // 一种protocol,安装到include/nanomsg下
survey.h* // 一种protocol,安装到include/nanomsg下
utils/ // 实用工具包,包含基本数据结构(list,queue,hash)互斥及原子操作(mutex,atomic)等
transports/ // 通信层实现,包括(inproc:进程内通信;ipc:进程间通信;tcp:tcp通信)
protocols/ // 协议层实现,包括(REQ/REP:请求/应答;PUB/SUB:发布订阅等.)
core/ // generic code,glue between the pieces
aio/ // 线程池模拟的异步操作,带状态机的事件驱动
CMakeLists.txt* // cmake编译文件
pkgconfig.in* // pkconfig工具配置文件
README* // readme

其中nanomsg对外暴露的接口api定义在nn.h中:

阅读全文 »

算法简介

在规则世界里,RETE算法应该是无人不晓了,许多有名的规则引擎或者专家系统都是基于RETE算法实现的,包括Jess,JRules,Drools,CLIPS等。

引用下wiki上关于RETE算法的定义:

RETE(/‘ri:ti:/ or /‘reiti:/)算法是个高效的可用于实现规则产生式系统(一种计算机程式,一般用于提供某种形式的人工智能,主要由基于行为的一系列规则构成)的模式匹配算法。

简而言之就是一套规则匹配优化算法。这个算法最早出现在1974年Dr Charles L. Forgy的一篇工作报告中,随后在1979年他的博士论文中完善,然后是1982年在《人工智能》杂志上的一篇文章

原理简介

现实中,如果要实现一个由若干规则组成的系统?最原始的做法大致应该是(类似krrules,囧):匹配第一条规则,再匹配下一条规则,直到所有规则匹配完毕。这样的规则匹配时间就应该是与规则数量呈线性关系:即随着规则数目的增多,规则的匹配时间线性增长。而在一些由大量规则构成的专家系统(Expert System)中,这样的规则匹配效率达不到要求,这促使了RETE的诞生。

名词解释

有几个名词在描述RETE时会用到,他们大致是这些:

  1. facts:指RETE网络中的输入项,数据元祖(data tuples)。
  2. rule:指用于对facts进行模式匹配的条件设置。
  3. action:指满足规则匹配后的动作处理。
  4. production:由一个或多个规则加上一系列动作构成。
  5. WME:当facts被插入引擎,即为它们创立(working memory elements)。

匹配流程

参考上图,一个完整的RETE规则匹配流程大致是这样的:

  1. 一个或多个事实facts被assert进RETE规则网络,
  2. 网络根据配置的规则rules进行模式匹配,并为facts创建WMEs,
  3. 对于触发规则的facts创建activitions并放入agenda中,
  4. agenda根据触发规则优先级salience确立触发次序,
  5. 最后执行action。

节点分类

最初Dr Charles L. Forgy提出的RETE网络是由四种节点构成,分别为:

  • root node(输入起始节点)
  • one-input node(单fact的条件匹配)
  • two-input node(多facts的联合join)
  • terminal node(走到此节点,则规则匹配)

人们在算法实现时又常常将one-input node再细分为:

  • Type Node:定位事实属性,确定fact的class,在krrules实现时将此步称为确定所属数据源,这为后续的节点定义和操作做好了铺垫;
  • Alpha Node:对fact的属性进行匹配判断,比如对一个person的fact,判断其age是否大于18,gender是否为male等;
  • Beta Node:则相对更为复杂一些,需要实现了两个fact的关联与匹配(比如一个person是否出现在一次party人员名单中)。
    具体的节点和功能作用,此处不再赘述了,想要更详细的了解rete算法的同学,除了阅读上面的原作者论文,还可参考这篇文章:《Production Matching For Large Learning Systems》,有好几十页的篇幅详细的介绍了RETE算法。

算法总结

以上,可以发现RETE的优点在于:

  1. 通过节点共享(node sharing)减少了规则中重复模式(pattern)的计算;
  2. 存储了部分匹配fact联合join匹配的结果,这样当facts少量变化时,免去未变化的计算量。

了解优点后,我们也很容易总结发现RETE相对于传统的线性匹配的优势点或优化场景在于:
** 大量规则(规则间具有某些重复pattern的情况),少量变化(规则判定的facts不是每次都重新assert) **
在这样的场景下RETE规则匹配算法会得到更好的效果,这对规则的设计与开发者是有些指导意义的。

应用案例

RETE在诞生以后,被广泛的用于专家系统和规则引擎的构建中,其中著名的有:

以上文字基本是我对RETE的初步认识,理解还很肤浅,错误或不准确之处还请大家指正!

这段时间暂停了下playweibo的开发,花了些时间在krproject的自身完善上,修改的几个大点如下:

  1. 共享内存改为动态内存。遗留原因,之前将数据库等相关配置信息放在共享内存中,这样可以方便的查看. 更新,但目前以引擎的方式打包,这样的共享内存方式俨然给引擎调用者带来了一些额外的麻烦。于是便考虑将共享内存中的内容放至动态内存中,提供接口供引擎修改和查看,这样一方面让引擎更加纯粹,另一方面参数的配置也会更加灵活一些。

  2. swig生成绑定接口。swig确实是个还蛮不错的工具,几个月前还不知道有这工具的时候,自己写了krengine的python绑定,虽然不难,但改起来还是挺麻烦的。在看到他的社区参与度挺活跃的时候,决定尝试一下,发现确实挺好用的。目前生成了python和java的两个接口,并都做了验证,让krengine作为小的library灵活的嵌入到不同语言中,相信会赋予它更强的生命力。

  3. 增加运算器的表达格式。krproject的一个很重要构成即是他的计算引擎,最早时我尝试了flex+bison写了它的规则语法,参考:krproject开发进展(二),后来为了方便web的编辑使用,我将计算引擎的表达式换成了json格式,参考:krproject开发进展(七),最近因为一些需要,我在考虑使用smartgwt的filter作为规则编辑界面,将它的json表达式作为计算引擎的表达式。于是我想到干脆将这三种表达方式都支持起来,各有各的特点:第一种原生的flex+bison表达式:简洁直观;第二种json格式表达式:web编辑操作方便;第三种gwt格式表达式:特殊需要。

还有些细枝末叶的调整修改,就不再赘述了,接下来考虑做的事情有:

阅读全文 »