twitter-like なシステムにおけるデータベースのスキーマ定義と抽出アルゴリズム
ちゃんとした設計の話を Kazuho@Cybozu Labs: フレンド・タイムライン処理の原理と実践に書きましたので、そちらをご参照ください。
飲み会までの時間、ちょっと考えたんだけど、結局、twitter の home のような、「follower 全員のポストから最新 n 件を取得」というオペレーションは、最悪 n^2 件 *1 へのアクセスで抽出可能ということを理解した。しかも、follower 毎に SQL 発行ができる *2 ので、memcached との相性が良さそう。また、全ユーザー数が式に出てこないってことは、すなわちスケールアウトできるってこと。
実質的に n の二乗の平均のルートは 100 以下 (最初のページだけなら n=20) だろうし、つまり、ちゃんと書けば負荷は低いんじゃないか、ということ。
追記： ただ、「最新 n 件」じゃなくて、自分の timeline を全件取れるようにしたい、って話になると、全 follower へ message_id をプッシュする実装にせざるを得ないのかなぁ。おもしろくない。もちろん、そういう高速なデータ構造をどうやって実現するかってところは、腕の見せ所にはなるんだろう *3 けど、正規形が崩れるしなぁ。
