スティルハウスの書庫の書庫

はてなダイアリーで書いてた「スティルハウスの書庫」を移転してきました。

Building Scalable, Complex Apps on App Engineを見たメモ

メモ GAE

Building Scalable, Complex Apps on App Engine

List properties 01:40

  • List propertyとは何か？
    • 複数の値を持てるプロパティ
    • 順序付きリスト
  • LPのメリット
    • one-to-many関係にあるデータをコンパクトに扱える
    • tupleやlistのようなデータを簡単に保存できる
    • 子entityを扱う必要がない。entityより軽い。
    • ただしcomposite indexで使う場合はindex explosionに注意
      • サイズが1000のLPを2つ使ってcomposite indexを作ると100万件のindexエントリができあがる
  • Microbloggingの例
    • たくさんのエントリを多数のユーザーに配布する必要があり、スケーラビリティが要求される
    • データ自体はコピーせず、fan-outさせる方が効率的
    • RDB的実装：UsersテーブルとMessagesテーブル、およびN:N関連を表すUsersMessagesテーブル間でjoinする
SELECT * FROM Messages
INNER JOIN UserMessages USING (message_id)
WHERE UserMessages.user_id = 'X';
    • app engine的実装：メッセージ受信ユーザーのリストを入れたreceiversというLPをMessageに定義する。あとは「receivers = ＜ユーザー＞」で、あるユーザーが受信したメッセージをすべて取得できる
results = db.GqlQuery(
"SELECT * FROM Message "
"WHERE receivers = :1", me)
  • LPのパフォーマンス
    • LPの更新は遅くない：複数行のLP更新を並列に実行できるから
    • LPのコスト：RDBのjoin tableと変わらない
    • シリアライゼーションのコストは注意する必要がある
      • クエリ時には該当するすべてのentityのLPをデシリアライズする必要がある
      • LPのアイテム数が100を超えると重くなる
      • Relation index entities（join tableのようなもの）を使って解決する：
        • Message（親）: メッセージ内容のみ保持。LPを持たないので軽い
        • MessageIndex（子）: LPを保持。LPによるクエリのために用意する
      • MessageIndexに対してクエリを実行し、キー一覧のみ取得、そこからMessage一覧を取得する
        • LPのデシリアライゼーションが発生しない。10倍以上速くなることもある
indexes = db.GqlQuery(
"SELECT __key__ FROM MessageIndex "
"WHERE receivers = :1", me)
keys = [k.parent() for k in indexes]
messages = db.get(keys)

Merge-join 23:10

  • app engineはmerge-joinはサポートしている
    • Bigtableではサポートしていない。Datastoreが実行時に処理する
    • 1つのentity内でのjoin
    • indexが不要
    • 例：たくさんのAND条件での検索
    • "zig zag"アルゴリズムでmergeしている
  • Social graphの例
    • UsersとFriends
    • 「XさんとYさんに共通の友達は？」
    • RDB的実装：UsersとFriendsをjoinする
SELECT * FROM Users
INNER JOIN Friends f1, Friends f2
ON Users.user_id = f1.user_b_id AND
Users.user_id = f2.user_b_id
WHERE f1.user_a_id = 'X' AND
f2.user_a_id = 'Y' AND
f1.user_b_id = f2.user_b_id
    • app engine的実装：merge joinとLPを組み合わせる
db.GqlQuery(
"""SELECT * FROM Person WHERE
friends = :1 AND
friends = :2 AND
location = 'San Francisco'""",
me, otherguy)
  • merge joinのパフォーマンス
    • 条件数と結果数に比例。結果が100件以下の場合に最適
    • LPと同様のパフォーマンス
    • ストレージのオーバーヘッドなし
  • 注意点
    • 条件間でオーバーラップが多すぎると、zig-zag処理に時間がかかる
    • composite indexと組み合わせて使えない：ソートできない
      • メモリ上でソートすべし（キーだけでソートするなど）

まとめ

  • LPとmerge joinが適している用途
    • fan-out（1つのメッセージを多数のユーザーに送る、など）
    • 地理情報処理
    • relationship graphs（entityのグラフ）
    • fuzzy value
  • クエリを「範囲指定」から「set membership」テストで置き換えられるか考える
    • データの書き込み時にmembershipの値を計算しておき、クエリは「=」だけで実施→速い

Questions

  • 各equality filterを書く位置はzig-zag処理の性能に影響するか？
    • あまり影響しない。
  • 頻繁に変更されるデータに対し、範囲指定検索するにはどうすればよいか？　変更のたびにたくさんのindexを更新したくない。
    • 検索用のデータを適宜計算して持たせる。
    • オークションサイトの例：価格帯ごとのオークション一覧を表示したい。あるオークションの価格が変化したら、「0〜1000円のオークション」のフラグをそのオークションのLPに追加しておく。範囲指定検索が不要になり、LPに対するequality filterですばやく検索できる
  • 以下のクエリの例では、N+1検索の問題が起きないか？
indexes = db.GqlQuery("SELECT __key__ FROM MessageIndex WHERE receivers = :1", me)
keys = [k.parent() for k in indexes]
messages = db.get(keys)
    • 起きない。indexesを取得する際には1回のクエリが走るが、messagesの取得は個々のキーからentityをハッシュテーブルで直接取得する。個別のクエリは実行されず、高速に処理される。