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

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

Building Scalable Web Apps with App Engineを見たメモ

メモ GAE

Google I/O 2008 - Building Scalable Web Apps with App Engine を見たメモ

  • 書き込みはコストが高い 0:06
    • アプリケーションのパフォーマンスを決めるのは、書き込み処理の実装方法
    • 読み込み処理は桁違いに速いので、あまり重要ではない
  • Entity Groupを使わずにID生成しよう 0:40
    • 書き込み処理が少なければID採番用のBlogIndexを親entityにしてEntityGroup(EG)を形成
    • 書き込み処理の集中するCommentsは、BlogIndexのEGに入れない
      • UserIndexのEGに入れて、timestampとUserIndexを組み合わせてGUIDを作る→txの競合をなくせる
  • スケールするアプリのコツ 0:42
    • Pythonランタイムのオーバーヘッドを最小に
      • リクエストごとにモジュールをロードしない。大きなモジュールは遅延ロードする
    • GetできるならQueryしない
    • 負荷に合わせたデータ構造を作る
      • 書き込み競合を低くする
      • EGの構成をよく考える
    • Memcacheはすごいので、どんどん使おう
  • テキスト検索の方法は（全文検索など）？ 0:48
    • （google検索のような）全文検索の手段はない
      • （注：やろうとしたら形態素解析してキーワードインデックス作る必要あるだろうな）
    • List Propertyを使う：1つのプロパティにキーワードのリストを入れておき、==で検索
  • バックグラウンドジョブは？
    • まだないが、検討中
  • EGはどう使う？ 0:52
    • 複数のentityを同じtxに入れたい場合に使う。txの単位を表す。
  • pagingしている間のrepeatable readはどう確保される？ 0:56
    • pagingしている間は確保されない。pagingの都度に最新のページ内容を取得している
    • 当初内容でrepeatable readを確保したければ、アプリ側で別テーブルを作るなどの対処が必要

Working with Google App Engine Modelsを見たメモ

メモ GAE

Working with Google App Engine Modelsを見たメモ

Bigtableにできないこと

  • 集約関数がない（group byできない）
    • count()やmax()も使えない（全件カウントできない）
    • しかし毎回対象データをすべて取得してループで集計するのは効率がよくない
      • （そもそも最大1000件の制限がある）
    • そこで集約したい値は、カウンターとなるオブジェクトで集計する 00:34
      • （書き込みが集中しないように複数オブジェクトに分散させるsharding counter）
  • 関数やストアドプロシージャはない

  • 比較演算子が限られている
    • LIKE使えない
      • （前方一致ならできる）
  • （ORも使えない）
  • Many to Manyの表現方法
    • List Propertyを使い、キーのリストを持たせる

From Spark Plug to Drive Train: Life of an App Engine Requestを見たメモ

メモ GAE

From Spark Plug to Drive Train: Life of an App Engine Request


＜Google App Engine Stackの構成（引用元）＞

Life of a request

  • リクエストの受信 0:15
    • リクエストはクライアントから最も近いGoogleデータセンターに到着
    • Google内部ネットワークを経由してFront Endに到着
  • Staticコンテンツへのリクエスト
    • Staticコンテンツ：appengine-web.xmlでstatic要素に指定したコンテンツ
    • アプリケーションコード等とは物理的に分離され配置されている
    • Front Endが直接処理し、App Serverは関与しない
  • Dynamicコンテンツへのリクエスト 0:17
    • App Server
      • Dynamicリクエストを処理。アプリコードが動作する
      • 多数のアプリを同時に収容し、アプリ間の隔離性を確保
      • アプリはステートレス。アプリが異なるAppserverに移動する場合でも状態を引き継いだりしない。負荷分散とフェイルオーバーが簡単になる
      • 状態はAPI（datastoreなど）で保存する
      • （HttpSessionはDatastoreで管理？）
    • App Master
      • アプリを管理してスケジュール
      • Front Endにアプリの情報を伝える
    • 処理の流れ
      • Front EndがApp Serverにリクエストを転送
      • App Serverは
        • 初回アクセス時はランタイムのメモリ上にアプリのキャッシュがないため初期化が実行され、処理が遅い
        • 次回以降アクセス時はメモリ上のアプリによりすぐにリクエストを処理
  • リクエストによるAPIアクセス 0:21
    • APIアクセスの流れ
      • アプリがAPIを呼ぶ
      • App Serverはそれを受けてアプリの実行をブロック、APIを実行
      • API実行結果を返し、実行を再開
    • API
      • XMPP
      • Task Queue（オフライン処理）
      • Datastore
        • Entity Groupはデータをパーティショニングする手段
        • コミットされたデータは地理的に分散した3台以上のサーバーに書き込まれる
        • 個々のentityにはGUIDが割り振られる
  • Design Motivations 0:27
  • The Numbers 0:36
    • 現状
      • 8万以上のアプリを収容
      • 140M PV/day
      • 20万人以上の開発者が利用
    • GAEのスケール事例：ホワイトハウスの"Open For Questions"
      • 2日間だけ提供された投票サイト
      • 10万件の質問と360万件の投票を受け付けた
      • その結果を受けてオバマ大統領が記者会見を行った
      • ピーク時には毎秒700回のクエリを実行した
      • Google Moderatorのソースをベースに、ホワイトハウス側の開発者がチューンしてデプロイした
      • GAE上の他のアプリケーションには一切影響がなかった


＜"Open For Questions"のトラフィック推移（引用元）＞

  • Questions 0:39
    • Datastore上のデータの物理的（地理的）位置を制御できるか？
      • できない。
    • アプリが受けられる負荷に上限はあるか？
      • 現状、safety limitが設けられている。それを超える負荷を扱いたい場合は、app engineチームに連絡してほしい。案件ごとにsafety limitを解除できる。

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をハッシュテーブルで直接取得する。個別のクエリは実行されず、高速に処理される。