私の友人がインタビューでこの問題を尋ねられました。ここでこの問題について議論したいと思います
この問題の効率的な実装は何ですか?
私に思い浮かぶ簡単なアイデアは、通常の memqueue で、Memcache マシンを使用して複数のリクエストをスケーリングし、memcache から DB に書き込みを行うコンシューマー ジョブを実行します。2 番目の部分では、SQL クエリを実行して、一致するサブスクライバーのリストを見つけることができます。
問題：-
イベントはこのシステムに発行されます。各イベントは、C1、C2、… CN と呼ばれる固定数 (N) の文字列列を含むと考えることができます。したがって、各イベントは文字列の配列として渡すことができます (C1 は配列の 0 番目の要素、C2 は 1 番目など)。
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 はサイトの Web ページを表し、C3 はリファラー コードを表します。)
すなわち。– 各述語は、いくつかの等価条件の結合です。述語には必ずしもすべての列の等価句があるとは限らないことに注意してください (つまり、述語は一部またはすべての列の値を気にしない場合があります)。(上記の例では、#a は列 C3、… CN を気にしません)。
着信イベントと登録済みサブスクライバーを照合できる Dispatcher を設計およびコーディングする必要があります。着信イベント レートの単位は 1 秒あたり 100 万です。加入者数は数千人です。したがって、このディスパッチャーは非常に効率的でなければなりません。平易な言葉で：
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.
インターフェイスの仕様に関しては、次のように大まかに記述できます (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() を呼び出します。この演習の目標は、この関数を可能な限り効率的にすることです。