最近在调研消息队列，看到N多的开源消息队列，都号称支持百万级别的queue，每秒转发也要到百万级别，那么这些路由规则是怎么实现的呢？
谈到消息队列的路由规则，这里先简单的介绍一下，消息队列中只要的两个角色是exchange和queue。RabbitMQ中的Exchanger包括：direct exchanger实现点对点传输；fanout exchanger实现一对多的广播传输；topic exchanger实现pub/sub传输。
1. fanout exchanger
典型的广播模式，一对全部。
2. direct exchanger
典型的点对点模式，一对一，转发目的地唯一。
3. topic exchanger
一对多模式，支持正则表达式。例如有3个queue绑定在一个topic exchanger上，queue a123,a234,a345。其实他们可以是3个具体的queue，也可以用正则表达式表示。
a123|a234|a345，或者是a[0-9]{3}。
基本上来看，海量路由规则的实现，是一个支持正则表达式的多模式匹配算法。多模式匹配算法，大家所熟悉的AC算法、WM算法、Trie树算法。
参考中RabbitMQ中路由转发规则实现部分，有一点比较好，就是NFA的运行时构建DFA，并对构建的DFA进行Cache，实现Lazy Computing，进行DFA方式的多模式匹配加速。不过最终，文中测试表明DFA优化余地有限，还是比采用回退方式Trie树算法要慢，大跌眼镜啊。
参考文献中的结论，DFA内存占用太大，没有太多优化空间；即使优化，也需要占用巨大的内存空间。NFA到DFA转换比较负载，尤其是运行时动态添加新规则，如果每次都重建DFA的话，时间开销太大，一般是NFA直接挂接在DFA上，遇到NFA的时候，实时进行转换，对转换得到的DFA进行Cache。这样依然比采用回退的Trie树差。Trie树算法简单，采用回退方式实现正则表达式，处理器Cache利用率高。
参考3中提出回退方式实现的正则，容易导致搜索到指数时间，并且栈调用深度增加。不过大致扫了一眼，基本的思路也是用DFA Cache的。
BTW： re2很强大啊，google出品必属精品。
参考：
阅读(3980) | 评论(0) | 转发(0) |
