待ち時間の少ない、常に更新されているグラフを処理するにはどうすればよいですか？

Question

多くのクライアントが、必要な場合にはサーバーに接続し、一連のグラフ情報（ノード属性とエッジ）を含むプロジェクトに取り組んでいます。彼らはいつでも新しいノードやエッジを導入し、グラフ全体からいくつかの情報を要求することができます（2ノード間の最短距離、グラフの色付けなど）。

これは簡単なアルゴリズムを開発するのは非常に簡単ですが、グラフを同時に更新している多くのユーザー、グラフから情報を要求している多くのユーザーを処理できるように、非常に大きな（500k +）ノードや場合によっては非常に多くのエッジも扱う可能性があります。私は予見でき

課題：常に更新するグラフで

• は、私はかなりの計算時間が増加し、待ち時間になるたびに、誰かが情報を要求グラフ全体...を処理する必要が
• 非常に大きなグラフでは、計算時間と待ち時間が明らかにかなり高くなります（これは、大量の結果をバッチ処理して後で使用するためにインデックスに格納することによって解決されましたが、グラフは常に更新されており、ユーザーは最新の情報を必要としますが、これは実行可能な解決策ではありません）
• 何度もグラフを処理する必要があるため、多数のユーザーが情報を要求しています。

どのようにこれらの課題に直面しますか？私はハープとスパークを見ましたが、グラフが絶えず変化していない問題に対処する高遅延ソリューション（バッチ処理あり）や解決策があるようです。

グラフの異なる部分を処理してインデックスを作成し、グラフの更新箇所を把握してグラフのその部分（分散型動的プログラミングアプローチの一種）を再処理することを考えましたが、それがどれほど実現可能かはわかりません。

ありがとうございます！

Answer 1

どのようにこれらの課題に直面しますか？

私はと答えるつもりです。これは重要なので、です。あなたはいくつかの正当な懸念事項を列挙しましたが、そのすべてを対処する必要がありますが、どちらも直接対処しません。

開始するには、セマンティクスの定義を完了する必要があります。あなたは終わったと思うかもしれませんが、そうではありません。グラフに各トランザクションの合計直列化につながるあなたは「ユーザーは、最新の情報にしたい」と言うとき、「最新の」

1. を意味し、「過去のすべて」、答えが反映されるように情報のすべての可能な部分？
2. 「すべてがX秒以上前に処理されました」これは部分的なシリアライズにつながりますが、これは現在の複数のデータベース状態が徐々に過去にシリアル化されていますか？

1.が必要な場合は、アプリケーションによっては、コードに避けられないホットスポットがある可能性があります。矛盾のためにトランザクションをいつロールバックするかについての即時の情報があります。

2.が許容範囲内であれば、パフォーマンスが向上する可能性があります。しかし、トレードオフがあります。最初の受諾後にトランザクションをロールバックする必要がある場合があります。

この質問に答えると、あなたの課題に直面し始めました。私はさらに質問があると思います。

Answer 2

グラフについてはあまりよく分かりませんが、ネットワーキングについては分かります。

私が心に留めておきたいのは、クライアントに手を差し伸べることができれば、サーバー側で作業をしないことです。

サーバーでは、生データを維持し、生データをクライアントに提供し、データが変更されたときに接続クライアントに通知するだけです。

クライアントは、独自の生データのコピーを作成し、既知の内容と受け取った更新内容に基づいて計算/視覚化を生成することができます。

クライアントは、新しいレコードがあるかどうか、または古いレコードが変更されているかどうかを知る必要があります。

何らかの理由でデータサーバー側を処理してクライアントに送信する必要がある場合（たとえば、クライアントはサードパーティのソフトウェアであり、管理しているものではなく、未加工データではなく処理済みデータが必要です）それでは、ちょっとした問題があるので、悪いお尻のサーバーを入手してください... 3、または30です。この場合、データが何であるか、どのように処理されているかを正確に知る必要がありますスケーリングされた設定に関する提案。