勉強日記

チラ裏

理論から学ぶデータベース実践入門 ch12 Webアプリケーションのためのデータ構造 (2/2)

gihyo.jp


タグ

  • RDBにとって頭の痛いデータ
  • データ構造(スキーマ)に問題はない
  • データ自体に問題がある
    • タグのデータはとても大きい
    • クエリ結果も大量の行となる
    • 複数タグを指定すると、大量の行の積集合演算となる(高コスト)
  • キャッシュテーブルを作ろう
    • {tag1, tag2, item_name, score} みたいな
      • score: 人気度
    • PK: {tag1, tag2, item_name}
    • 正規形でない
      • 繰り返しパターンなので1NFでない
      • {item_name} -> {score} なる関数従属性がある
    • が、キャッシュなので問題ない
    • 重複をなくすために、 tag1 < tag2といった条件をつけること
    • インデックス{tag1, tag2, score}なるインデックスがあれば上位のアイテムを高速に取得できる
      • {tag1, tag2, score, item_name}としてカヴァリングインデックスを狙うのも良い
  • メリット
    • 上位コンテンツの取得が速い
  • デメリット
    • 行数が多い
      • アイテムにn個のタグがついていて、うちm個で検索する組み合わせはnCm通り
        • 階乗オーダー
      • 要件として検索可能なタグ数を制限できない場合は諦めよう

コラム: 転置インデックスを使用して検索を高速化する

  • RDB製品によっては、配列型カラムがサポートされる
  • タグ配列に対して転値インデックスをつけることでタグ検索高速化
  • ただし、本質は巨大な集合同士の結合のままであることに注意
    • 通常のB+木インデックスよりもデータがコンパクトなだけ

スケールアウト

レプリケーション

  • 参照処理性能の物理的な限界を突破
  • 参照負荷を複数のDBサーバへ分散

スレーブへの問い合わせ方式

データの論理的整合性と非同期レプリケーション

  • データの論理的整合性
    • スレーブに対して問い合わせをする場合、マスタに対して行うのと全く同じクエリを記述できる
    • マスタの完全なコピーを持っているため
  • 非同期レプリケーション
    • 完全コピーはオーバヘッドが大きいため、同期レプリケーションは使用不可
    • スレーブ上のデータはマスタのものと比べて古い可能性がある
      • もっとも、1秒未満になることがほとんど
    • 少しの時間差も許されない場合はレプリケーションによるスケールアウトは使用できないことに注意する

シャーディング

  • 更新処理性能の物理的な限界を突破
  • 別々のDBサーバにデータを水平分割
    • cf. パーティショニングは同一DBサーバ
    • 典型的には別々マシン
  • アプリケーションのロジックは複雑化する
    • どのデータがどのシャードに格納されるべきかの判別
  • 参照処理性能もスケールさせたい場合、レプリケーションと組み合わせるのが一般的

問題点

  • シャードをまたいだクエリを実行できない
    • DBサーバをまたいでJOINできない
  • 管理のオーバヘッド増える
    • スキーマ構造のシャード間同期は管理者が行う必要がある

NoSQLのシャーディング

  • 自動的にシャーディングできるNoSQL製品が人気を博している
  • が、RDBの代わりにはならない
    • データモデルの違いは重大
    • 整合性を保証する道具がない
  • 内部的なシャーディングに対応したRDB製品もあり、そちらを先に検討すべき