少し遅くなってしまいましたが、インターン講義Ustreamの最終回です。最終回はうごメモエンジニア
id:birdie7による「データ構造」です。データ構造の概要から、B-Treeについてまでを解説しています。
インターン自体は、既に後半に入っており、実際のサービスのコードに機能追加を行っています。ちゃくちゃくと実装が進んでおり、来週にはリリースができそうです。
講義#8: データ構造
自己紹介
うごメモエンジニア
- 動画像処理
- 業務で使っている言語 C/C++、perl
- 今までやった主な仕事
- うごメモ作品・コメント変換部 (C++等)
- うごメモ写真検出、高速点滅検出 (C++、XS)
- 直線検出、位置推定 (C++、XS)
- うごメモ検索 (Solr)
- ランキング (Hadoop)他、集計的業務
- その他エンジニアリングディレクター的仕事
うごメモとは
- メモで繋がるコミュニケーション：世界でサービス展開
- DSiから作品・手書きコメントを投稿、スター
- PCからもコメント・スター
- 作品の発表場、作品によるコミュニケーション(メモのリレー等)、子供のチャット場
Webアプリに要求されるパフォーマンス
- リクエストに対するレスポンス 80% 〜 90% を 1秒以内
- 1ページを返却する時の所要コスト
- アプリケーションのコスト：インプットを受けてWebアプリでデータを入出力して処理
- IOコスト、CPUコスト
- ネットワークコスト：(明日の講義)
- アプリケーションのコスト：インプットを受けてWebアプリでデータを入出力して処理
効率的なWebアプリケーションの考え方 (1/2)
- IOコスト高
- 同期処理不要：非同期処理 (AJAX, schwartz worker)、長期間のキャッシュ (squid, memcachedなど)、大量にあれば分散処理(hadoop等)
- 例) 人気作品一覧、ランキング、各種ユーザ設定
- (☆) 同期処理必要：インデクスを効かせてMySQL、(可能であれば)短時間のキャッシュ (memcached等)、並列化
- 例) 新着作品一覧、コメント一覧のレコード
- 同期処理不要：非同期処理 (AJAX, schwartz worker)、長期間のキャッシュ (squid, memcachedなど)、大量にあれば分散処理(hadoop等)
効率的なWebアプリケーションの考え方 (2/2)
- CPUコスト高
- 同期処理不要：非同期処理 (worker job)
- 例：動画像変換 (作品、コメント)
- 同期処理必要：高速モジュール作成 (XS, C++)、負荷分散 (サーバ台数を増強)
- 例：処理の重めのオンラインゲーム
- 同期処理は最小限に
- なるべく非同期にしていい部分 & キャッシュしていい部分を分離して
- 同期処理不要：非同期処理 (worker job)
なぜIOに着目するか？
うごメモでの処理対象の規模
レコード数
- 作品：約1000万 レコード (累積値)
- コメント：約7000万 レコード
- スター：約6000万 レコード
容量 (DBのみ)
- 作品：5GB
- コメント：30GB超
- スター：13GB超
(データ全体がメモリに載りきりませんね…)
インデクスが効いていない(線形探索)と…
- 帰ってこない。。。
- O(n)
インデクス探索だと…
- 素早いレスポンス!
- BTree Index
- O(log(n))
- オーダ O(n)：線形時間。n=10000で処理1つ0.1msecなら1秒オーダ
- オーダ O(log(n))：対数時間。n=10000で処理1つ0.1msecならlog(10000) * 0.1msec ≒ 0.92 msec !
処理のオーダを意識することが大事!!
- 要求されるパフォーマンス：総リクエストの80〜90%を1秒以内にレスポンス返す
- 大量のデータをうまく扱えるデータ構造・アルゴリズムが必須!
- 問題としているデータ規模・処理オーダを常に意識し、うまく捌けるアルゴリズムを考慮すべし
蛇足
しかしいずれにせよ、探索対象のデータ(インデクス)がメモリに載ってないとダメ
- 役割毎にサーバを用意 (DBやmodperl(WebApp)、Proxy、Storage (MogileFS, S3)、Worker、検索等)
- DBサーバを更に役割毎に分割 (作品、コメント、ユーザ系)、インデクスはメモリに載るように設計
- サーバ構成の詳細は明日の講義
MySQLのインデクス構造
- Btree
- データ構造：n分木 (データ & Nの参照)
- 操作 (アルゴリズム)
- 挿入、削除、探索、リスト取得
- 常にバランスするように再構成
課題
- Btreeの探索・リスト取得・最大値・最小値取得を実装してください。また木の高さを測る関数を作成してください。
- Btreeの挿入・削除を実装してください。また挿入・削除操作があったとしても高さが常に一定であることを確認してください
- 2のBtreeでmultiple indexによる探索を可能にしてください。また10万オーダーのキーを挿入し、ベンチマークしてください。
- Multiple indexを実装するとMySQLのwhere、order byの組み合わせがあるとき、どういうインデクスが必要か、実感で分かります)
(今回、キー値はとりあえず数値が入るようにして、ユニークになるようにしてください)
採点
各機能が動作すること、実装がきれいなこと(それぞれ半分づつの点)
- 1: Btreeの実装1：4点(探索 1点、リスト取得 1点、最大値・最小値取得 各1点)
- 2: Btreeの実装2：4点(挿入 1.5点、削除 1.5点、高さの確認(挿入/削除でそれぞれ 0.5点)
- 3: multiple indexの実装：1点、ベンチマーク：1点
テストその1
このテストが通るようなAPIにしてください
もっといいAPIの案があれば、その良い理由を添えてもらえばそちらを採用してもらってもいいです。
package Test::Btree; use strict; use warnings; use base qw(Test::Class); use Btree::Node; use Btree; use Test::More; # $Btree::Node::DEBUG = 1; # 定義したい人はどうぞ # $Btree::KEY_CLASS = 'Btree::MNode'; # Multiple Index用 sub _use : Test(startup => 1) { use_ok 'Btree'; } sub add : Test(34) { my $tr = Btree->new(2); ok $tr->insert(113), 'first insert'; is $tr->key_count, 1, 'key count'; # 木に存在する全キー数 ok $tr->insert(23), 'insert'; is $tr->key_count, 2, 'key count'; ok $tr->insert(32), 'insert'; ok $tr->insert(56), 'insert'; is $tr->key_count, 4, 'key count'; ok $tr->insert(83), 'insert'; is $tr->key_count, 5, 'key count'; ok $tr->insert(13423), 'insert'; is $tr->key_count, 6, 'key count'; ok $tr->insert(20), 'insert'; is $tr->key_count, 7, 'key count'; ok $tr->insert(18), 'insert'; is $tr->insert(18), undef, 'insert duplicate key'; is $tr->key_count, 8, 'key count'; ok $tr->insert(1), 'insert'; is $tr->key_count, 9, 'key count'; ok $tr->insert(3), 'insert'; is $tr->key_count, 10, 'key count'; ok $tr->insert(8), 'insert'; is $tr->key_count, 11, 'key count'; ok $tr->insert(2), 'insert'; is $tr->key_count, 12, 'key count'; ok $tr->insert(4), 'insert'; is $tr->key_count, 13, 'key count'; is $tr->insert("abc"), undef, 'insert'; is $tr->key_count, 13, 'key count'; is $tr->insert("bd"), undef, 'insert'; is $tr->key_count, 13, 'key count'; is_deeply $tr->list_keys, [1,2,3,4,8,18,20,23,32,56,83,113,13423], 'list keys'; my $e = $tr->search(83); # 探索成功 # searchの結果は [$node, $idx] ：$node:検索対象が見つかったノード参照、$idx: 見つかった$node内のキー位置 is $e->[0]->key_at($e->[1]), 83, 'search exist key'; # このAPIはおまけ is $tr->search(21), undef, 'search unexist key'; # 探索失敗 ok $tr->same_depth ; #全部の葉が同じ高さにあることの確認 $tr->show; # 深さをインデントで表現して標準出力に表示する } # ざっくり通す sub seq_add_delete : Test(113) { my $tr = Btree->new(2); for (1..18) { ok $tr->insert($_), 'first insert'; } $tr->show; $tr->same_depth ; ok $tr->delete(12); is $tr->search(12), undef, 'should fail search'; is $tr->key_count, 17, 'key count'; is_deeply $tr->list_keys, [1,2,3,4,5,6,7,8,9,10,11,13,14,15,16,17,18], "key list"; for (1..18) { if ($_ == 12) { is $tr->delete($_), undef, 'delete non existant key'; } else { ok $tr->delete($_), "delete $_"; } if ($_ < 12) { is $tr->key_count, 17 - $_, 'key count'; } else { is $tr->key_count, 18 - $_, 'key count'; } is $tr->search($_), undef, 'should fail search'; is_deeply $tr->list_keys, [ grep { $_ != 12 } (($_+1)..18) ], "key list match"; ok $tr->same_depth ; } $tr->show; } # 上記で抜けてるdeleteのパタンをテスト(2a, 2c, 3a) sub seq_add_delete2 : Test(34) { my $tr = Btree->new(2); for (1..18) { ok $tr->insert($_), 'first insert'; } $tr->show; # 2c ok $tr->delete(14); is $tr->search(14), undef, 'should fail search'; is $tr->key_count, 17, 'key count'; is_deeply $tr->list_keys, [1,2,3,4,5,6,7,8,9,10,11,12,13,15,16,17,18], "key list"; # 2a ok $tr->delete(16); is $tr->search(16), undef, 'should fail search'; is $tr->key_count, 16, 'key count'; is_deeply $tr->list_keys, [1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,18], "key list"; ok $tr->delete(2); is $tr->search(2), undef, 'should fail search'; is $tr->key_count, 15, 'key count'; is_deeply $tr->list_keys, [1,3,4,5,6,7,8,9,10,11,12,13,15,17,18], "key list"; # 3a ok $tr->delete(5); is $tr->search(5), undef, 'should fail search'; is $tr->key_count, 14, 'key count'; is_deeply $tr->list_keys, [1,3,4,6,7,8,9,10,11,12,13,15,17,18], "key list"; $tr->show; } # 課題3のベンチマーク (挿入・検索・削除) sub large_tree : Test(1) { require Benchmark::Timer; $Btree::Node::DEBUG = 0; my $t = Benchmark::Timer->new; my $tr = Btree->new(80); my $rnd_range = 10000000; my $size = 100000; for (1..$size) { my $k = int rand($size) + 1; $t->start('insert'); $tr->insert($k); $t->stop('insert'); } warn $tr->show; warn $t->report; my $stored = $tr->key_count; warn "KEY SIZE: $stored"; for (1..$size) { my $k = int rand($size) + 1; $t->start('search'); $tr->search($k); $t->stop('search'); } warn $t->report; is $stored, $tr->key_count; for (1..$size) { my $k = int rand($size) + 1; $t->start('delete'); $tr->delete($k); $t->stop('delete'); } warn $tr->show; warn "KEY SIZE: $stored"; warn $t->report; # $tr->show; } __PACKAGE__->runtests;
参考
こちらは内部テストの一部なので、参考にしてください
package Test::Btree::Node; use strict; use warnings; use base qw(Test::Class); use Btree::Node; use Btree; use Test::More; use Data::Dumper; sub setup: Test(setup) { my $self = shift; my $c1 = [ Btree::Node->new({ level => 2, _keys => [5, 7], _is_leaf => 1, }), Btree::Node->new({ level => 2, _keys => [13, 16], _is_leaf => 1, }), ]; my $c2 = [ Btree::Node->new({ level => 2, _keys => [22, 25], _is_leaf => 1, }), Btree::Node->new({ level => 2, _keys => [33, ], _is_leaf => 1, }), ]; my $m1 = Btree::Node->new({ level => 2, _keys => [10, ], _is_leaf => 0, _children => $c1, }); my $m2 = Btree::Node->new({ level => 2, _keys => [28, ], _is_leaf => 0, _children => $c2, }); my $r = Btree::Node->new({ level => 2, _keys => [18,], _is_leaf => 0, _children => [ $m1, $m2 ], }); $self->{fixtures}->{root} = $r; } sub _use : Test(startup => 1) { use_ok 'Btree::Node'; } sub find_location : Test(3) { my $self = shift; my $root = $self->{fixtures}->{root}; is $root->find_location(17), 0; is $root->find_location(18), 0; is $root->find_location(19), 1; } sub search : Test(5) { my $self = shift; my $root = $self->{fixtures}->{root}; my $e = $root->search(22); warn Dumper $e; is $e->[0]->key_at($e->[1]), 22; is $root->search(111038), undef; $e = $root->search(5), 5; is $e->[0]->key_at($e->[1]), 5; $e = $root->search(10), 10; is $e->[0]->key_at($e->[1]), 10; is $root->search(11), undef; } # XXX split_childとかもテストした方がいいですね __PACKAGE__->runtests; 1;
(以下参考) 2分木の探索・リスト取得
探索
- ルートから探索を開始する
- 探索キーを各ノードのキーと比較して、小さければ左、大きければ右を選択
- 再帰的に実行する
- 葉まで来て見つからなかったら存在しない
- バランスの取れた木なら探索オーダ O(log(n))
# BinaryTree::Node型 ： key (scalar) と left,right_child (BinaryTree::Node型)を持つ # ルートから呼び出せば全体の探索になる sub search { my ($self, $k) = @_; return $self if $self->{key} == $k; # left_child, right_childは同じ型 return $self->left_child->search($k) if $self->{key} > $k; return $self->right_child->search($k);
(参考) 2分木の探索・挿入
探索
- 探索キーを着目しているノードのキーと比較して、小さければ左の子、大きければ右の子を選択
- 再帰的に実行する
- 葉まで来て見つからなかったら存在しない
- バランスの取れた木なら探索オーダ O(log(n))
# BinaryTree::Node型 ： key (scalar) と left,right_child (BinaryTree::Node型)を持つ # ルートから呼び出せば全体の探索になる sub search { my ($self, $k) = @_; return $self if $self->{key} == $k; # left_child, right_childは同じ型 return $self->left_child->search($k) if $self->{key} > $k; return $self->right_child->search($k);
挿入：
- 手順は探索とほぼ同様
- 最後の探索失敗位置に挿入する
- 最後かどうかを判定するためis_leaf (自身が葉ノードかどうか)で場合分け
sub insert { my ($self, $k) = @_; if ($self->{key} > $k) { if ($self->is_leaf) { $self->left_child = BinaryTree::Node->new; $self->left_child->{key} = $k; return $self->left_child; } elsif ($self->{key} == $k) { return ; # ユニークなキーの場合は同じキーは挿入しない } else { return $self->left_child->insert($k); } } else { return $self->right_child->insert($k); }
2分木の削除 (コードは省略)
削除対象のキーの位置、子の状況によって下記場合分け
- ルートから手順を開始する。
- 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次に着目するノードとなる。
- 着目ノードが削除する対象（以下、削除ノード）の場合
- 削除ノードが子どもを持たないなら、そのノードをそのまま削除する。
- 削除ノードが子どもを一つしかもっていない場合は、削除ノードを削除してその子どもと置き換える。
- 削除ノードが子どもを二つ持つ場合
- 削除ノードの左の子から最大の値を探索する。
- a. で探索してきたノード（以下、探索ノード）を削除対象のノードと置き換えて、削除対象のノードを削除する。このとき探索ノードの左の子を探索ノードの元位置に置き換える（2分探索木の性質上、探索ノードには右の子は無い）。
