5

cs.stackexchangeでこれを尋ねました..反対票を獲得しました..私はあまり明確ではなかったので..だから私はここでより具体的にしようとします..

Q - 過去 1 分間の Web サーバーへの接続数を返すデータ構造を設計してください。

仮定 -

  1. サーバーには大量の着信接続があります..インドの鉄道予約やソーシャルネットワークサイトなど..
  2. これがビッグデータの問題であるとします..ビッグデータジョブを実行するためのインフラがあります..

を探しています：

  1. 効率 - O(1) でこれを行うことは可能ですか? たとえば、O（n）でそれを行うと、問題は、答えを計算するのにNミリ秒かかる場合..そのNミリ秒でキューに入れられた接続がさらにあるということです..これにどのように取り組むべきですか. . または、わずかな遅延しか無視できず、O(n) は問題ないパフォーマンスです

  2. 推論/アプローチ - 本番環境にある無数の展開で、これと同様のことを行いますか? 同様の問題はありますか..？

  3. これが「ビッグデータ」ですか？注文の最後の N (N は 10 のオーダー) 分の接続を保存するためのデータはビッグデータの問題ですか?

私の努力: 私はそれを知っています -

  1. Web サーバーへの接続は、スレッドによって処理される前にキューに入れられます
  2. 各接続にはタイムスタンプがあります

アプローチ -

  1. 接続がキューに入れられるとすぐに、それをファイルに書き込みます.. (少なくともそのタイムスタンプと接続へのハンドル/一意の識別子)
  2. クライアントが「過去 1 分間の接続数を教えてください」と要求するとすぐに..ファイルを処理して接続数を調べます..現在の時刻がミリ秒単位でわかり、タイムスタンプが currentTime に収まる接続を見つける必要があることがわかります - 60秒
  3. このジョブは map reduce を使用して実行できます。また、ファイルのデータが (タイムスタンプで) ソートされていることもわかっています。

また、不要なデータを保存しないように、10 分以上経過したエントリ/ファイルを削除するデーモンも実行します。

4

1 に答える 1

12

キューアプローチ

  • キューを使用します。

  • 新しいリクエストが来るたびに、キューに入れます。

  • 過去 1 分間のリクエスト数を取得する必要があるときはいつでも、最初に 1 分以上前に発生したすべてのエントリをキューから取り出します (これは、キュー内のエントリが順番に挿入され、キューがソートされるため機能します)。次に、キューのサイズを返します (サイズは、O(1)これを格納する変数を持つことで返すことができます)。

  • 毎秒多くのリクエストがあると言うので、新しいリクエストを取得するたびに古いエントリをデキューすることもできます。これにより、キューが適切なサイズに近くなり、カウント操作にかかる時間が最小限に抑えられます。

    これはO(k)、エンキューと取得カウントの両方に適用されます。ここで、kは length の任意の期間に発生したリクエストの最大数、 は任意の 2 つのリクエスト間の最大期間です (例として、次のミリ秒でリクエストを取得した場合: 、最大期間はで、ミリ秒単位で発生するリクエストの最大数はです(つまり、期間内に発生します)。tt1,2,3,5,15,2020-15 = 5541,2,3,51-5

  • 別の方法は、古いエントリをデキューするタイマーを実行することです。

    これのパフォーマンスはO(1)、エンキューとO(m)タイマーの実行および取得カウントに対して行われます。ここmで、 はタイマーの頻度に等しい長さの任意の期間に対する要求の最大数です。例として、ミリ秒1,2,3,5,15,20のタイマー間隔で再度使用します。ミリ秒単位6で発生するリクエストの最大数はです(つまり、期間内に発生します)。641,2,3,51-6

これが「ビッグデータ」ですか？

それは、1 秒あたりに取得するリクエストの数に大きく依存します。通常、ビッグ データのデータは何テラバイトにもなります (コンピュータがより強力になるにつれて増加します) が、最後の 1 分間の要求だけがこれらの数値に近づくとは思いません。

カウントベースのアプローチ

小さなエラーに満足している場合は、次のことができます。

固定サイズのキューを用意します (60 としましょう。各要素は特定の秒の要求を示します - 単純な整数値です)。これは、円形配列として実装できます。

Let count= 0 に初期化された最後の 1 秒間のリクエスト数を示す変数。

最後のリクエストの 2 番目の値を格納する変数を用意します (キュー内の要素が何秒間のものかを判断できるようにするため)。

新しいリクエストを受け取ると、1 分前よりも長い秒数を示すすべての要素をデキューcountし、デキューされた値をデクリメントし、キューの後ろ (最後に挿入された値) をcount.

最後の 1 秒間のリクエスト数を取得する必要がある場合は、1 分前よりも長い秒数を示すすべての要素をcountキューから取り出し、キューから取り出した値をデクリメントして、 を返しcountます。

キューが固定サイズであることを考えると、各操作は最大でもかかりO(1)ます (または、必要に応じてO(m)、mはキューのサイズです)。

これにより、最大で 1 秒のエラーが発生します。もちろん、エラーをいじることができます。たとえば、0.5 秒のエラーが必要な場合は、単純にキューのサイズを 2 倍にして、0.5 秒ごとに次の要素に移動します。

于 2013-08-23T07:10:48.003 に答える