7

巨大なタグ付けシステム (digg やdelicious など) のデータ ストレージを設計するにはどうすればよいですか?

それについてはすでに議論がありますが、それは集中型データベースに関するものです。データは拡大することが想定されているため、データを複数のシャードに分割する必要があります。そこで、問題は次のようになります:パーティション化されたタグ付けシステム用のデータ ストレージを設計するにはどうすればよいでしょうか?

タグ付けシステムには、基本的に 3 つのテーブルがあります。

Item (item_id, item_content)

Tag (tag_id, tag_title)

TagMapping(map_id, tag_id, item_id)

テーブルが1つのデータベースインスタンスに格納されている場合、これは、特定のタグのすべてのアイテムを検索し、特定のアイテムのすべてのタグを検索するためにうまく機能します。データを複数のデータベース インスタンスに分割する必要がある場合、それはそれほど簡単ではありません。

テーブルItemの場合、そのコンテンツをそのキーitem_idで分割できます。テーブルTagの場合、そのコンテンツをそのキーtag_idで分割できます。たとえば、テーブルTagを K 個のデータベースに分割したいとします。特定のタグを格納するために、番号(tag_id % K)データベースを選択するだけです。

しかし、テーブルTagMappingを分割する方法は?

TagMappingテーブルは、多対多の関係を表します。重複するイメージしかありません。つまり、TagMapppingの同じコンテンツには 2 つのコピーがあります。1 つはtag_idで分割され、もう 1 つはitem_idで分割されます。特定のアイテムのタグを見つけるシナリオでは、tag_idでパーティションを使用します。特定のタグのアイテムを見つけるシナリオの場合、item_idでパーティションを使用します。

その結果、データの冗長性が生まれます。また、アプリケーション レベルでは、すべてのテーブルの一貫性を維持する必要があります。大変そうです。

この多対多パーティションの問題を解決するためのより良い解決策はありますか?

4

3 に答える 3

4

考えられるすべての使用シナリオを最適化する単一のアプローチがあるとは思えません。あなたが言ったように、TagMappingテーブルがサポートする主なシナリオは 2 つあります。特定のアイテムのタグを見つけることと、特定のタグを持つアイテムを見つけることです。TagMapping関心のあるシナリオごとに表をどのように使用するかについて、いくつかの違いがあると思います。私は典型的なタグ付けアプリケーションに基づいて合理的な仮定を立てることしかできないので、これがベースから外れている場合は許してください!

特定のアイテムのタグを見つける

A1. 特定のアイテムのすべてのタグを一度に表示します

A2. アイテムのすべてのタグが一意であることを確認します

特定のタグのアイテムを検索する

B1. 一度に特定のタグのいくつかのアイテムが必要になります (検索結果のページを埋めるため)。

B2. ユーザーが複数のタグを指定できるようにする場合があるため、複数のタグに一致するアイテムのいくつかを見つける必要があります

B3. 特定のタグ (または複数のタグ) のアイテムを人気度の尺度で並べ替えます。

上記を考えると、TagMappingアイテムごとに分割するのが良いアプローチだと思います。このようにして、特定のアイテムのすべてのタグが 1 つのパーティションに配置されます。タグよりもはるかに多くのアイテムが存在する可能性が高く、各アイテムにはほんの一握りのタグしかないため、パーティショニングはより細かくすることができます。これにより、取得が容易になり (A1)、1 つのパーティション内で一意性を確保できます (A2)。さらに、その 1 つのパーティションで、アイテムが複数のタグ (B2) に一致するかどうかがわかります。

一度に必要なのは特定のタグ (1 つまたは複数) の一部の項目のみであるため (B1)、結果のページを埋めるのに必要な数のレコードが得られるまで、ある順序で一度に 1 つずつパーティションを照会できます。クエリを実行する必要があるパーティションの数は、パーティションの数、表示する結果の数、タグの使用頻度によって異なります。このクエリに効率的に答えるために、各パーティションは tag_id に独自のインデックスを持ちます。

パーティションを選択する順序は、検索結果のグループ化方法に影響するため重要です。順序付けが重要でない場合 (つまり、B3 が重要でない場合)、パーティションをランダムに選択して、どのパーティションも過熱しないようにします。順序付けが重要な場合は、アイテム ID を作成して、結果を並べ替える順序に関連する情報をエンコードできます。適切なパーティショニング スキームでは、このエンコーディングに注意が必要です。たとえば、結果が人気順に並べ替えられた URL である場合、連続したアイテム ID をその URL の Google ページ ランク スコア (または類似のもの) と組み合わせることができます。パーティショニング スキームでは、特定のパーティション内のすべてのアイテムが同じスコアを持つようにする必要があります。クエリは、より人気のあるアイテムが最初に返されるように、スコア順にパーティションを選択します (B3)。明らかに、これは 1 種類の並べ替えのみを許可し、関連するプロパティはキーの一部になり、レコードのパーティションを決定するため、一定である必要があります。ただし、パーティション化されたデータを使用して、さまざまな並べ替えや揮発性プロパティの並べ替えをサポートするのは簡単ではないため、これは実際には新しい制限ではありません。

于 2010-04-24T04:47:07.727 に答える
1

ルールは、クエリを実行するフィールドごとに分割することです。そうしないと、すべてのパーティションを調べる必要があります。tag_id のみで Tag テーブルをクエリする必要がありますか? タグのタイトルでクエリを実行する必要もあります。Item テーブルについてはそれほど明白ではありませんが、他のユーザーがタグを割り当てるときに、URL のようなものでクエリして item_id を見つけたいと思うでしょう。

ただし、Tag テーブルと Item テーブルには不変のタイトルと URL があることに注意してください。つまり、次の手法を使用できます。

  1. タイトル (タグの場合) または URL (アイテムの場合) からパーティションを選択します。
  2. このパーティションのシーケンスを選択して ID を生成します。

パーティションとローカル ID のペアをグローバル識別子として使用するか、重複しない番号セットを使用します。とにかく、id フィールドと title/URL フィールドの両方からパーティションを計算できるようになりました。事前にパーティションの数がわからない、または将来変更される可能性があることを心配していますか? それらをさらに作成し、グループに参加して、後で再グループ化できるようにします。

確かに、TagMapping テーブルに対して同じことを行うことはできないため、複製する必要があります。map_id、tag_id、item_id でクエリする必要がありますよね? したがって、パーティション分割を行わなくても、3 つのインデックスを作成してデータを複製する必要があります。したがって、違いは、インデックスごとに (異なるフィールドによる) 異なるパーティショニングを使用することです。心配する必要はありません。

于 2010-04-23T11:47:33.587 に答える
1

ほとんどの場合、クエリはユーザーまたはトピックに関連しています。つまり、それらに関連するすべての情報を 1 か所にまとめる必要があります。

DB の配布について話しているのですが、通常、これは主に同期の問題です。通常、作業の約 90% を占める読み取りは、複製されたデータベースで実行できます。問題は、パフォーマンスを損なうことなく、1 つの DBを更新し、他のすべてのデータベースと一貫性を保つ方法です。これは、シナリオの詳細によって異なります。

もう1つの可能性は、あなたが尋ねたように、重複せずにすべてのデータを分割することです。おそらく、ユーザー ID またはトピック ID でパーティション化するでしょう。トピック ID で分割すると、1 つのデータベースがすべてのトピックを参照し、どの専用 DB がデータを保持しているかを示すだけになります。その後、正しいものを照会できます。ID でパーティション化するため、そのトピックに関連するすべての情報がその専用データベースにある可能性があります。国際的な Web サイトの場合は、言語または国ごとに分割することもできます。

大事なことを言い忘れましたが、おそらく 2 つを混在させることになるでしょう: 重複しないデータと、重複する (複製された) データがあります。最初に通常の操作を見つけてから、1 つの DB でそれらを最小限のクエリで作成する方法を見つけます。

PS: キャッシングを忘れないでください。分散 DB よりも節約できます。

于 2010-04-26T10:22:57.467 に答える