1

これは私が先週受けたインタビューの質問で、クリフハンガーで終わった. 質問は単純でした。渡された「メッセージ」 (1 行の文字列、異なる言語の可能性があります) の頻度を追跡するサービスを設計してください。submitMsg(String msg) と getFrequency(String msg) の 2 つの広範な API があります。私の即時の反応は、文字列をキー (この場合はメッセージ) として使用し、整数を値 (カウント/頻度を追跡するため) として使用する as hashMap を使用することでした。

submitMsg API は、hashMap にメッセージが存在するかどうかを確認するだけです。そうでない場合は、メッセージを入れて頻度を 1 に設定します。そうであれば、現在のカウントを取得し、それを 1 ずつ増やします。インタビュアーは、複数のスレッドが同じ時間に同じキーにアクセスする場合、これは惨めに失敗するだろうと指摘しました。

例: 12:00:00:000 で Thread1 は「submitMsg」を試行し、それによって私のメソッドは (1) hashMap を取得し、値が null ではないことを確認します。実際には 100 (2 ) キーの値が 101 になるように、頻度を 1 ずつ増やして put を実行します。一方で、Thread2 も正確に At 12:00:00:000 に submitMsg を実行しようとしたことを考慮し、メソッドは再び内部的に get を実行しました。 hashMap (これは 100 を返しました - これは競合状態です)。その後、hashMap は頻度を 101 に増やします。残念ながら、実際の頻度は 101 ではなく 102 である必要があり、これは主にマルチスレッド環境における主要な設計上の欠陥です。 . これを防ぐ方法がわかりませんでした。単純に書き込みをロックするだけでは十分ではなく、読み取りをロックしても意味がありませんでした。get が submitMsg API を介して内部的に呼び出された場合、要素を「ロック」するのが理想的でした。頻度が更新されるとロックは解放されますが、誰かが純粋なロックを持つ getFrequency() API を使用する場合、意味がありません。私は分散システムに強いバックグラウンドを持っていないので、ここでミューテックスが役立つかどうかはわかりません。

このような問題を解決する最善の方法について、SO コミュニティに助けを求めています。使用するデータ構造の魔法ですか、それとも API 自体で行う必要があるある種の同期ですか? サービスのスケーラビリティを維持しながら、「頻度」の整合性を維持するにはどうすればよいでしょうか。

4

3 に答える 3

2

最も簡単な解決策は、Guava の com.google.common.collect.ConcurrentHashMultiset を使用することです。

private final ConcurrentHashMultiset<String> multiset = ConcurrentHashMultiset.create();

public void submitMsg(String msg) {
    multiset.add(msg);
}

public int count(String msg) {
    return multiset.count(msg);
}

しかし、これは基本的に Aurand のソリューションと同じですが、カウンターがまだ存在しない場合にカウンターを作成するなどの退屈な詳細を誰かが既に実装しているだけです。

于 2013-10-01T14:46:06.187 に答える