伤豆丁文库网站开发,课程推广,东莞房价2021最新价格走势,化工设计网站主题匹配核心算法就是字符串匹配#xff0c;在字符串匹配基础上#xff0c;会加入分段匹配需求#xff0c;类似URL的点分式字符串。这个算法在几个场景中十分普遍。
1、应用层的路由寻址。比如反向代理中#xff0c;根据请求中的URL#xff0c;转发到对应的后台服务。
2…主题匹配核心算法就是字符串匹配在字符串匹配基础上会加入分段匹配需求类似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提供并发度仍然是个不错的降低延迟的优化措施。
还有更多的优化措施但性价比低只有极少数更加苛刻的场景才需要考虑。
