19

これが私が解決しようとしている問題です：

複数のデータベース シャードにまたがって保存されている、ページ化され、並べ替えられたデータのテーブルを表示できる必要があります。

ページングと並べ替えはよく知られた問題であり、データが単一のソースから取得された場合、ほとんどの人がさまざまな方法で解決できます。しかし、データを複数のシャードに分割したり、DHT や分散ドキュメント データベース、または任意の種類の NoSQL を使用したりする場合、事態はさらに複雑になります。

以下は、非常に小さなデータ セットの簡単な図です。

シャード | データ
1 | 1
| D
1 | G
2 | B2
| E
2 | H
3 | C
3 | F
3 | 私

ページに並べ替え (ページ サイズ = 3):

ページ | データ
1 | 1
| B1
| C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | 私

ユーザーのページ 2 を表示したい場合は、次のように返します。

D
E
F

問題のテーブルのサイズが 1,000 万行または 1 億行の場合、すべてのデータを Web/アプリケーション サーバーにプルダウンして並べ替え、正しいページを返すことはできません。また、シャードはお互いを認識していないため、個々のシャードにデータの独自のスライスを並べ替えてページングさせることは明らかにできません。

さらに複雑なことに、提示する必要のあるデータがそれほど古いものであってはならないため、事前に一連の有用な並べ替えを事前に計算し、後で取得できるように結果を保存することは現実的ではありません。

4

1 に答える 1

15

いくつかの解決策があり、そのうちのいくつかは実行できない場合がありますが、そのうちの 1 つが固執する可能性があります。

  1. この値の入力範囲によってシャーディングを実行します (たとえば、シャード 1 には AC が含まれ、シャード 2 DF など)。または、このテーブルへの外部キーを持つ別のテーブルをインデックスとして使用し、このシステムを使用してインデックス テーブルを分割します。そうすれば、指定した範囲を簡単に見つけて取得できます。このソリューションは、実行できる場合、おそらくパフォーマンスの点で最適です (シャードの数が静的であり、シャードが信頼できると想定しています)。
  2. 二分探索によってページ アイテムを特定します。たとえば、アイテム 100 から 110 が必要だとします。各シャードについて、「M」以下の値の数を辞書式に数えます。数値の合計が 100 を超える場合は、ピボット ポイントを減らします。それ以外の場合は、ピボット ポイントを増やします (二分探索を使用)。100 番目のアイテム (ページの最初のアイテム) を特定した後、すべてのシャードからそのアイテムよりも大きい上位 9 (10 - 1) のアイテムを取得し、それらをフェッチし、リスト全体を並べ替え、リストから上位 9 を取得し、最初のアイテムとあなたのページがあります! このアプローチは実装がより難しく、O(log(n))クエリが必要になるため、(1) よりも遅くなりますが、負荷がそれほど重くない場合は、それでもかなり高速になる可能性があります。
  3. ページ番号を各値とともに保存します。これにより、非常に高速な読み取りが可能になりますが、書き込みは非常に遅くなるため、書き込みがほとんどないシナリオでのみ機能します (または、順序付けられた変数に関してのみ追加されます)。
于 2010-10-13T21:03:04.860 に答える