algorithm - 发布-订阅系统的设计/代码调度程序

Question

我的一个 friend 在面试中被问到这个问题。我想在这里讨论这个问题

这个问题的有效实现是什么？

我想到的一个简单想法是普通 memqueue，使用 Memcache 机器来扩展多个请求，并运行一个消费者作业，它将内容从 memcache 写入数据库。 稍后在第二部分中，我们可以运行一个 sql 查询来查找匹配订阅者的列表。

问题:-

事件被发布到这个系统。每个事件都可以被认为包含固定数量 (N) 的字符串列，称为 C1、C2、... CN。因此，每个事件都可以作为字符串数组传递(C1 是数组中的第 0 个元素，C2 是第一个，依此类推)。

有 M 个订阅者 – S1, … SM

每个订阅者注册一个谓词，指定它感兴趣的事件子集。每个谓词可以包含:

Equality clause on columns, for example: (C1 == “US”)
Conjunctions of such clauses, example: 
    (C1 == “IN”) && (C2 == “home.php”) 
    (C1 == “IN”) && (C2 == “search.php”) && (C3 == “nytimes.com”)

(在上面的示例中，C1 代表事件的国家/地区代码，C2 代表网站的网页，C3 代表推荐人代码。)

即。 – 每个谓词都是一些相等条件的结合。请注意，谓词不一定具有针对所有列的相等子句(即 - 谓词可能不关心某些或所有列的值)。 (在上面的示例中:#a 不关心列 C3，... CN)。

我们必须设计和编写一个 Dispatcher，它可以将传入事件与注册订阅者相匹配。传入事件速率以每秒数百万计。订户数量以千计。所以这个调度员必须非常高效。通俗地说:

When the system boots, all the subscribers register their predicates to the dispatcher
After this events start coming to the dispatcher
For each event, the dispatcher has to emit the id of the matching subscribers.

就接口(interface)规范而言，大致可以这样拼写(用Java):

Class Dispatcher {

    public Dispatcher(int N /* number of columns in each event – fixed up front */);

    public void registerSubscriber( String subscriberId /* assume no conflicts */,
                                    String predicate /* predicate for this subscriberid */);

    public List<String> findMatchingIds(String[] event /* assume each event has N Strings */);

}

即:构建了调度程序，然后进行了一堆 registerSubscriber 调用。此后，我们不断调用 findMatchingIds() 方法，本练习的目标是使该函数尽可能高效。

Answer 1

正如 Hanno Binder 所暗示的，问题显然是为了允许对订阅进行预处理以获得高效的查找结构。 Hanno 说查找应该是 map

(N, K) -> set of subscribers who specified K in field N     
(N, "") -> set of subscribers who omitted a predicate for field N

当一个事件到来时，只需查找所有适用的集合并找到它们的交集。查找失败返回空集。我只是重述 Hanno 的精彩回答，指出哈希表是 O(1) 并且在此应用程序中可能比树更快。另一方面，交叉树可以更快，O(S + log N)，其中 S 是交集大小。所以这取决于集合的性质。

备选

这是我的替代查找结构，同样只在预处理期间创建一次。从编译 map 开始

(N, K) -> unique token T (small integer)

还有一个独特的标记 0 代表“不关心”。

现在每个谓词都可以被认为是具有 N 个标记的类似正则表达式的模式，代表特定的事件字符串键或“不关心”。

我们现在可以提前构建决策树。您也可以将此树视为用于识别模式的确定性有限自动机 (DFA)。边缘标有标记，包括“不关心”。如果没有其他边匹配，则采用无关边。接受状态包含相应的订阅者集。

处理事件从将键转换为 token 模式开始。如果由于缺少映射条目而失败，则没有订阅者。否则将模式提供给 DFA。如果 DFA 使用该模式而没有崩溃，则最终状态包含订阅者集。退回这个。

例如，我们有 map :

(1, "IN") -> 1
(2, "home.php") -> 2
(2, "search.php") -> 3
(3, "nytimes.com") -> 4

对于 N=4，DFA 将如下所示:

o --1--> o --2--> o --0--> o --0--> o
          \
            -3--> o --4--> o --0--> o

请注意，因为没有订阅者不关心例如C1，起始状态没有无关转换。 C1 中任何没有“IN”的事件都会导致崩溃，并且会正确返回 null 集。

只有数千个订阅者，此 DFA 的大小应该是合理的。

这里的处理时间当然是 O(N) 并且在实践中可能会非常快。为了真正的速度，预处理可以生成并编译一组 C switch 语句。以这种方式，您实际上可能每秒通过少量处理器获得数百万个事件。

您甚至可以使用像 the flex scanner generator 这样的标准工具为您完成大部分工作。