intro

• 发布订阅系统中存在着大量的订阅和事件匹配问题，我们的目的是设计优良的数据结构和匹配算法，从而达到订阅数据的快速分发的效果。在现实中，我们举个例子，在股票市场中，股民会有一些订阅条件，从而能够收到满足这些订阅条件的事件，这些订阅比如（price>25 & 换手率>10% &市场交易总额>=10亿)，当股市的行情事件(比如一支股票的分钟bar数据(比如price=26))满足订阅时，我们就会将事件发给用户。
• 算法和数据结构方面，我们之前主要是读了几篇论文(OpIndex, TAMA, REIN, SIENA)，里面的背景介绍可以让你了解这方面。简单来讲，OpIndex适合高维度数据的匹配，TAMA通过对数值区间不同粒度的划分和分层来快速匹配，REIN是通过反向排除的方式来进行匹配，SIENA是早期的匹配算法的文章。
• 系统方面，我们假设在分布式的数据分发系统中存在着三类Object，发出事件的服务器publisher,　订阅者subscriber，运行匹配算法的服务器Broker。

MY MAIN JOB

• 在数据分发系统中，每个用户收到事件的时间其实是不一样的，在不考虑网络延迟的情况下，这个时间是由匹配算法决定的，在OpIndex中，我们匹配到一个订阅就可以将正在匹配的事件发给用户，在REIN中，由于我们使用的是排除不符合订阅的方式，所以我要等到匹配基本结束后check布尔bitset的时候再发给用户。
• 从而我们可以将一个事件的匹配过程分成几个时间点。事件开始匹配的时间t_b, 匹配到第一个满足的订阅的时间t_1,匹配到最后一个订阅的时间t_n,　实践匹配结束的时间t_e。
• 现有的课题主要集中设计新的数据结构和匹配算法降低匹配的时间。而我的课题主要是在让整个匹配算法的总时间t_e - t_b不增长或者只增长一点点的情况下，将用户收到订阅的时间点提前，从而更快的获取市场的事件信息做出自己的决策。
• 现有的工作主要集中在REIN的数据结构上，未来设想拓展到OpIndex上。现有的**是采用数据结构分级和数据分级的方式来进行匹配。具体来说，就是我们将原来REIN的数据结构作为一个level的基本结构，做多个level，同时将订阅根据一定的规则划分到这几个level中。
• 这种**的出发点有这几个。
  • REIN的算法中匹配算法主要集中在匹配过程的前面，而事件的分发主要集中在后面的check布尔bitset中，所以用户收到事件的时间点是滞后的，而我们将数据结构分级之后，这样我们匹配一部分订阅之后就可将事件发给符合的订阅，而不必等到最后。
  • 分级之后我们的匹配过程就可以分为不同level阶段的匹配过程，每个小过程就是一个匹配算法的过程，只不过数据结构有微妙差别，数据量变少了。我们假设每个匹配过程分配同等比例的数据，匹配总时间是差不多的，只不过我们尽可能希望越早匹配的level，匹配到的订阅数最多，极端就是在第一个level的时候符合事件的订阅基本匹配到了，后面的level匹配没有符合的订阅了，那么我们就相当于将t1...tn前移了。
  • 那么如何让前面Level的匹配订阅数目变多呢，就是要增大这些订阅的匹配概率。这样一种情况，每个订阅中属性和值的分布差不多的时候（如均匀分布），订阅中的约束条件越少，他的匹配率越高，这样我们可以把约束条件Constraints数目为１的放在第一个level，为n的放在第n个level。

Tricks

• 其实在实际的过程中我们需要思考几个方面
  • 怎么让数据结构的分级不让整个匹配时间增长很多，因为分级会带来数据结构切换的开销。这里我的做法是对每个级别的数据结构进行精细调优，比如bucket的数量等，让每个Level的时间尽可能做到最好，我们可以仔细查看匹配算法中的时间花费在了哪里，是匹配单个bucket还是bucket的切换还是check数组。
  • 怎么去分配数据。我之前是按照constraints的数目来分配的，如果数据的分布不同，那么我们是否可以采取其他的方式，比如根据历史记录的缓存?来选择匹配概率更高的。
  • 怎么去衡量效果的提升。目前我们的想法是，我们统计每个事件匹配过程的t1到tn的分位点，然后对所有事件做一个平均，来统计前百分之几的订阅在多久就已经匹配结束了，比如(1%, 10%, 20%, 25%, 50%, 75%, 90%, 99%等等)，我们还可以用时间点的平均值来衡量。
  • 怎么进行现实网络中的实况测试。
    • 数据方面，我们有已经爬取和归一化处理过的股票数据(由毛威超毛神处理的)
    • 网络测试平台方面，我们基于Siena的平台改整成了我们现有的测试版本。１个EventSender，1个broker，几十个Subscriber。
• 目前存在的问题
  • 分发出一个事件给相应订阅的网络延迟过高(尽管之前我们已经由tcp协议转换到udp协议了)。我们假设两个相邻匹配订阅的时间点之间的间隔为dt，那么在同步发送的过程中，如果发送延时大于dt，就会影响后面一个订阅的匹配时间点和过程。我之前试过异步发送的，效果不是很好(可能我线程池的代码优化的不是很好）
• 未来可能的方向
  • 能否通过机器学习的方式，训练出模型从而判断每个订阅的匹配概率，将匹配率高的前移。

Code and websites

• 关于几篇论文的算法毛神的代码: https://github.com/xizeroplus/matching-algorithm
• 关于我这个课题的代码
  • 单机版本: https://github.com/mg2015started/offline_pub_sub_algorithm
  • 网络版本: https://github.com/mg2015started/pub_sub_system，因为我一个多月没改进了，毛神在跟进网络版本，可能会有一些改进网络的地方。
  • 原来Siena平台的链接: 暂时找不到了，问问钱老师吧。
• 论文合集
  • https://github.com/mg2015started/offline_pub_sub_algorithm/tree/master/%E8%AE%BA%E6%96%87%E5%90%88%E9%9B%86