高性能服务系列【十一】主题匹配

主题匹配核心算法就是字符串匹配，在字符串匹配基础上，会加入分段匹配需求，类似URL的点分式字符串。这个算法在几个场景中十分普遍。

1、应用层的路由寻址。比如反向代理中，根据请求中的URL，转发到对应的后台服务。

2、消息总线的队列匹配。这个场景非常有意思，在传统的消息队列中，主题的数量比较少，几百个主题已经算多了。但在某些应用中，会存在很夸张的主题数量，比如行情订阅和高频交易，这个后面再细说。

3、行情订阅，这个跟消息总线很像。一些专业消息总线，如TIBCO和UM，两者具有重叠区域。

大部分主题匹配的应用场景比较简单，性能需求没有那么苛刻。我们就以类似行情发布和订阅场景为例，假设有100W只股票代码随时都可能发布行情，而消费者会随机订阅其中的1W只股票行情。

我们不考虑行情压缩，减少每条行情的字节数，这个不在主题匹配考虑范围内。如果采用组播技术，有一个很有效的方法，对于同一个组播地址，可以指定1W个端口号，每个端口绑定100只股票代码。于是，即使100W只股票代码，每个端口也只需要承担100只股票的行情量。而消费者根据订阅请求，监听对应端口号，就能拿到所需要的行情数据。

在采用前面技术之后，对于每个节点，需要处理的数据量大幅下降，但仍然高于实际需要的数据量。我们继续假设，需要发布10W只股票的行情，而消费者订阅其中的1W只股票行情。

股票或者主题来说，通常会采用类似URL那样的点分式来表示，比如EXHG.123456.SECT,而消费者会采用EXHG.*,或者EXHG.1234__.SECT。这两种模式匹配的算法，除了采用字典树，貌似没有其他办法。当然字典树是可以继续优化的，具体参考前面CPU和内存章节。

更多场景下，订阅的1W只股票，是随机指定的。因此，发布的股票和订阅的股票之间，需要进行精确匹配。普通做法是，1W只股票先构建一个索引，比如C++的std::map。每收到一条消息，就去匹配索引。则时间复杂度为：10W * LOG2(1W) > 100W。

进一步升级，消费者锁订阅的1W只股票，以哈希表构建索引，则时间复杂度为：10W * 常数C > 10W。我们知道，时间复杂度的常数C，最小为1，因为10W只股票的行情，不管有没有消费者，都是要发布的。将10W只股票分散到多个CPU，提供并发度，仍然是个不错的降低延迟的优化措施。

还有更多的优化措施，但性价比低，只有极少数更加苛刻的场景才需要考虑。