最終課題の詳細

最終課題の詳細#

はじめに#

最終課題は，Webシステムの超高性能化に関する課題です．

具体的には，1000万行程の大きなデータ（CSV形式）を2つ用意しましたので，Webブラウザで検索キーワードを入力すると，これら2ファイルを統合的に検索し結果をソートして表示するWebアプリケーションを実装してもらいます．何も工夫せず安直に実装すると検索結果が表示されるまで数分かかってしまうこともありますので，三層クライアントサーバ型のWebシステムにおいて，どこにボトルネックが生じうるのか，どのようにボトルネックの箇所が遷移していくのか，グループ内で議論や試行錯誤し，できるだけ多くのリクエストに耐えられる超高性能なWebシステムを実現できるようグループ間で競ってもらいます．様々なアプローチが考えられますが，大きくオンメモリ型か非オンメモリ型かでそれぞれ超高性能なWebシステムを目指してほしいと思います（どちらか一方のみでも構いません）．

第三部最後のグループ発表会では，各グループの実現した超高性能なWebシステムについて特徴を紹介してもらい，その性能測定結果をアピールしてもらいます．どのような工夫で性能向上させるかは，世の中で実際に使用されうる手法であれば何でも構いません（もし実運用に耐えられないような小手先の仕組みの場合は，参考という形でアピールしてください．実施した内容や検討した内容はポジティブに受け取りますので）．

最終課題も，グループ発表会と個別レポートで評価しますので，チームワークだけでなく主体性，独自性も養ってください．また，これまでのグループワークを通し，実装の得意な人，計測や考察の得意な人，自由な発想で取り組みたい人，などそれぞれ何となく自身を分析できるようになってきたと思います．まずは，下記の 基礎課題（必須） 全てをグループ内で議論しながら実施してください．さらに，以下に示す 応用課題（分担で①は必須，②は任意） については各自の興味関心，得意分野に応じて，それぞれ複数人になるよう相談して決めてください（半々で実施する必要はありませんし，重複していても構いませんが「二兎を追う者は一兎をも得ず」にならないようご注意ください）．

基礎課題（必須）
応用課題（分担で①は必須，②は任意）
- ①必須：Webシステムの超高性能化に重点的に取り組む人(①超高性能化（ハイパフォーマンス）チーム)
- ②任意：超興味深いWebシステムの自由課題に重点的に取り組む人(②自由課題（イマジネーション）チーム)

もちろん両方に取り組んでもらってもよいですが，限られた時間内で達成感を得られる方に専念した方がよいと思います．また，それぞれ開発したプログラムのソースコード最終版も個別レポートと一緒に提出してもらいます．第三者が眺めて理解しやすいような構造やコメントを意識してください．

使用機材について#

最終課題には「基礎課題」および「応用課題」の二種類の課題があります．基礎課題にはRaspberry Piを使用して取り組んでください．応用課題（超高性能化および自由課題）では，Raspberry Pi以外の機材（例えば，以前の実験で利用していたNUCが何台かあります）も利用可能とします．また，一台だけでなく複数台Raspberry Piを組み合わせた構成も利用可とします．皆さんの自由な発想による課題へのチャレンジを期待しています．

ただし，複雑なシステム構成においてはパフォーマンスの計測も困難になることには十分に注意してください．パフォーマンスに影響する要件を抽出し，それぞれが何故，どの程度影響を与えたのかを，公平に評価・レポートすることが重要です．

データセットのダウンロード#

PHPのエラー表示設定と確認#

デフォルト設定では，PHPでWebアプリケーションを実装した場合，PHP実行時のエラー内容が画面に表示されず正常に動作しているのかしていないのか良く分かりません．また，裏で検索処理に時間を要しているだけなのにPHP実行時間が重たく30秒を超えてしまうような場合，自動的にPHPの実行を停止してしまいます．Webシステムの本番運用ではこのようなデフォルト設定が望ましいですが，Webシステムの開発中は設定を変更した方が便利ですので以下のようにPHPの設定ファイルを修正してください（よく使う Vim のコマンドまとめ）．

$ sudo vi /etc/php.ini

Note

phpのバージョンによっては /etc/php/X.X/apache2/php.ini などにあるかもしれませんが，置き換えてください．

# ブログラムのタイムアウト設定を30 -> 300秒へ変更
max_execution_time = 300

# .................
# 画面へのエラー表示設定をOff -> Onへ変更
display_errors = On

データセットのダウンロード#

最終課題用の２つのデータセットをダウンロードしてください．それぞれダウンロードするのにそこそこ時間を要しますので余裕をもって事前に，ダウンロードしておくとよいでしょう．

\\fs.inf.in.shizuoka.ac.jp\\share\\class\\情報科学実験A\\第三部サンプルデータ\\geotag.zip（静大のネットワーク内からはWindowsファイル共有にて．外部からはVPNを利用してアクセス可能）

どちらも同じファイルなので，可能な方法でダウンロードしてください．解凍するとgeotag.csv (約1.1GB)とtag.csv (約445MB)の2つのファイルが入っています．

※ パケット容量制限等でどうしてもダウンロードが難しい方はUSBメモリ等でお渡ししますのでMattermostにてご相談ください

geotag.csvの概要#

Flickrで共有されている撮影位置の緯度経度の付いた写真1000万枚のリストになります．

Table 5 geotagの概要#
列名	概要	例
ID	各写真で一意の識別子	4532230686
撮影時刻	TIMESTAMP形式	2010-04-18 12:14:07
緯度	撮影位置の緯度(倍精度)	40.744769
経度	撮影位置の経度(倍精度)	-73.958823
画像のURL	Flickrサーバ上の画像URL	http://farm5.staticflickr.com/40～略～m.jpg

tag.csvの概要#

geotag.csvに含まれる画像へ付与されているタグのリストになります．IDの重複は許しており，タグ毎に一行となっています．

Table 6 tagの概要#
列名	概要	例
ID	各写真で一意の識別子	4532230686
タグ	Varchar形式	dog

テーブルの作成#

テーブルを作成し，ダウンロードしたCSVファイル（データセット）からデータをテーブルへ流し込んでみましょう．参考まで標準的なスキーマを以下に記しておきます．もちろんもっと賢い格納方法についてグループ内で試行錯誤してくれて構いませんので，ぜひ取り組んでみてください（ただし，ここはまだ本質ではありません）．

--mysqlの設定変更（該当箇所を以下のように変更するか，なければ追記）
$ sudo vi /etc/mysql/mariadb.conf.d/50-server.cnf
default-storage-engine=Aria
character-set-server=utf8
collation-server=utf8_general_ci

--必要なら既存のテーブルを削除
DROP TABLE tag,geotag;

--テーブルの作成
CREATE TABLE geotag(
  id BIGINT UNSIGNED PRIMARY KEY,
  time DATETIME,
  latitude DOUBLE,
  longitude DOUBLE,
  url VARCHAR(100)
);

CREATE TABLE tag(
  id BIGINT UNSIGNED,
  tag VARCHAR(300)
);

--CSVファイルの流し込み
LOAD DATA LOCAL INFILE "/data/geotag.csv" INTO TABLE geotag FIELDS TERMINATED BY ',' ENCLOSED BY '"';
LOAD DATA LOCAL INFILE "/data/tag.csv" INTO TABLE tag FIELDS TERMINATED BY ',' ENCLOSED BY '"';

約1,000万件のデータセット（約1.1GB）ですから，データベースへの流し込みにはそこそこ時間を要します．事前に実験した結果ではgeotagのLOADに45分程度，tagのLOADに10分程度の実行時間になります．これと比べて著しく時間がかかる場合は何らかの原因で失敗している可能性がありますので，下記のテーブル作成がうまくいかない人用の手順を見ながら再度試してみてください．

CSVファイルを読み込む命令: http://dev.mysql.com/doc/refman/4.1/ja/load-data.html

上記のCREATE文では，キーに指定されたID以外のインデックスを作成しません．インデックスの効果を実感するために，以下のSQLで問い合わせしてみましょう．

--インデックスを作成しているフィールドで検索
SELECT * FROM geotag WHERE id = 7738073352;
--  すぐに結果が返ってきます

--インデックスを作成していないフィールドで検索
SELECT * FROM geotag WHERE latitude = 38.9466;
--  しばらく時間を要します

前者はインデックスを作成しているため，高速に結果が返ってきたはずです．一方，インデックスを作成していない後者はしばらく時間を要したと思います．これがインデックスの効果です．ちなみにMariaDBはデフォルトで，主キーに対してB-treeを用いたインデックスを作成しています．A&Dで勉強したように，B-treeを用いて探索するため高速に結果が返ってきます（もちろん様々な特性に応じた工夫が施されていると思います）．

ここで，一般的にインデックスが作成されているフィールドを検索する場合，特に何も指定しなければ自動的にインデックスを使用して検索されますが，SELECT文にIGNORE INDEX句を加えることで，敢えて強制的にインデックスを使用しないという指定もできます．

--インデックスを強制的に使用しないで問い合わせをする方法

SELECT * FROM geotag IGNORE INDEX (PRIMARY) WHERE id = 7738073352;
--PRIMARYは主キーに自動で付けられるインデックスの名前

--インデックスがあるのにインデックスを使用しないため検索に時間を要します

インデックス使用の有無に関するMySQLリファレンスへの関連リンク

テーブル作成がうまくいかない人用の手順#

下記手順を試してみてください

--mysqlを止める
$ sudo service mysql stop
--（一度失敗等して動作が重くなっている人のみ！）一度mysqlデータベースを全削除
$ sudo rm -rf /var/lib/mysql（必要ならバックアップとっておいてください．残り容量注意）
--mysqlの初期化
$ sudo mysql_install_db
--mysqlを再起動
$ sudo service mysql start
--必要なら既存のテーブルを削除
DROP TABLE tag,geotag;
-- 再度テーブルの作成からチャレンジ

インデックスの作成#

緯度経度や撮影時刻，タグなどを条件とした検索を効率良く行うため，必要なフィールド用のインデックスを作成してみましょう．ただし，インデックスを作成すると検索は速くなりますが，インデックスの分だけディスク容量を消費しますので注意しましょう（インデックスの作成に必要な容量は計算で見積もることができますので調べてみるとよいでしょう）．

具体的に，皆さんの環境でインデックスの作成によってどの程度ディスク容量を使用するか試してみましょう．以下のようにコマンドを入力し，インデックスを作成する前のテーブルが消費しているデータ容量をチェックしてみましょう．テーブルが消費しているデータ容量などの詳細は，information_schemaと呼ばれるDBのpartitionsテーブルへ保存されています．

data_lengthがテーブルの大きさ，index_lengthがインデックスの大きさ，単位はbyteで確認できます．

--メタデータを保持しているinformation_schmeと呼ばれるDBへ移動
use information_schema;
select table_name,data_length,index_length from partitions where table_name='geotag' or table_name='tag';

--実験で使用している実験用DB（例：CSexp1DB，皆さんの作成したDB名へ適宜読み替え）へ戻る
use CSexp1DB;

+------------+-------------+--------------+
| table_name | data_length | index_length |
+------------+-------------+--------------+
| geotag     |  1180311552 |    183001088 |
| tag        |  1002242048 |    297779200 |
+------------+-------------+--------------+

それでは，次に必要な項目のインデックスを作成してみましょう．端末のハードウェア性能にもよりますが，1,000万件のB-treeを作成する訳ですからインデックスを一つ作成するだけで5分程度の時間を要します．

ここで「i_xxxx」はインデックス名です．インデックス名は自由に設定できますが，インデックス名であることが一目瞭然になるよう対象フィールド名の前に「i_」を付けたものをインデックス名とすることにしました．例えば，tagフィールド用のインデックス名は「i_tag」としています．

CREATE INDEX i_lat USING BTREE ON geotag(latitude);
CREATE INDEX i_log USING BTREE ON geotag(longitude);
CREATE INDEX i_time USING BTREE ON geotag(time);

CREATE INDEX i_tag USING BTREE ON tag(tag);

ここで，最後の CREATE INDEX i_tag USING BTREE ON tag(tag); を実行すると「ERROR 1238 (HY000): Variable ‘innodb_large_prefix’ is a read only variable」というエラーが発生するかもしれません．皆さんに最初に設定してもらったデフォルトストレージエンジン Aria の制約となります．ストレージエンジンを InnoDBに変更すれば，innodb_large_prefix を設定できるようになりますので興味ある方は試してみてください（ストレージエンジンの変更にはそこそこ時間を要しますので）．

mysql > show enginescreate table テーブル名;                 # ストレージエンジン（Engine）を確認
mysql > alter table テーブル名 engine=任意のエンジン;        # ストレージエンジンの変更
（そこそこ時間がかかります）
mysql > CREATE INDEX i_カラム名 USING BTREE ON テーブル名(カラム名)

最後に，上記のインデックス作成によってテーブルが消費しているデータ容量がどの程度増加したか確認してみましょう．

--メタデータを保持しているinformation_schmeと呼ばれるDBへ移動
use information_schema;
select table_name,data_length,index_length from partitions where table_name='geotag' or table_name='tag';

--実験で使用している実験用DB（例：CSexp1DB，皆さんの作成したDB名へ適宜読み替え）へ戻る
use CSexp1DB;

+------------+-------------+--------------+
| table_name | data_length | index_length |
+------------+-------------+--------------+
| geotag     |  2111832064 |    707444736 |
+------------+-------------+--------------+

上記のインデックス作成によって，テーブルが消費しているデータ容量が約183MBから約707MBへ増加したことが分かります．

ディスク容量は潤沢にある場合は良いですが，闇雲にインデックスを作成しすぎるとディスク容量不足に陥るので注意しましょう．今回のような大容量のデータセットを扱う場合，インデックスを作成しないと実用的な応答速度が得られませんが，性能とコストのバランスが重要となりますので，インデックスの作成方法や構造など試行錯誤してみてください．

インデックス作成に関するMySQLリファレンス

基礎課題1（全員必須）#

任意のタグを持つ写真の撮影時刻・緯度・経度・URLの一覧を，撮影時刻順で出力するプログラムを様々な方針で実装してもらいます．

ここで，任意のタグは静的にハードコーティングするのではなく，Webブラウザの検索フォームからユーザが指定できるよう実装してください．

イメージを掴みやすくなるようこれから実装するprogA（実装A）～C（実装C）を呼び出すための共通のindex.htmlを用意しました．以下のgitリポジトリからサンプルプログラム（index.html, progA.php, progB.php, progC.phpの４つ）をcloneしてください．これらprogA.php（実装A）, progB.php（実装B）, progC.php（実装C）の内容を変更することで基礎課題の内容を実施してください．cloneしたら，Webブラウザでindex.htmlを表示し，どのような構造になっているか動作を確認してみてください．

ohkilab/SU-CSexpA-Last

以下の項目は，実装A～Cの全てに対し共通で実装してもらいたい仕様ですので必ず実装してください．

【追加実装する共通仕様】

ユーザの入力した任意のタグに合致する写真を表示すること
各写真に対し，写真，緯度・経度，撮影時刻の情報を表示すること
撮影時刻の降順で写真を表示すること
結果が100件を超える場合，最新のもの100件を表示すること

実装A#

実装Aは，データベースを使用せずにCSVファイルを開いて検索するようなプログラムを実装してください．

実装Aの仕様を以下に示します．

【仕様】

progA.phpとして実装すること

Hint

ユーザが入力したタグは，$_REQUEST[“tag”]に入っています（index.htmlでその設定はすでにされています）．
インデックスのような機能を独自実装してくれて構いません．
PHPのみで全ての機能を実装する必要はありません．以下の関数を用いるとPHPから実行形式のファイルを実行できます．

ロジカルな仮説を立てて様々な工夫を試行錯誤をしてみてください．その内容を個別レポートで適切にアピールしてあると高評価になると思います．

実装B#

実装Bは，実装Aと同仕様のプログラムを，データベースを使用して，ただし「i_tag」インデックスは使用しないで検索するようなプログラムを実装してください．

実装Bの仕様を以下に示します．

【仕様】

progB.phpとして実装すること
データベースを使用すること（ただしi_tagインデックスを使用してはいけない）

Hint

「i_tag」インデックスを使用しない設定は，SELECT * FROM tag IGNORE INDEX(i_tag) WHERE tag like ‘beach’;
ユーザが入力したタグは，$_REQUEST[“tag”]に入っています（index.htmlでその設定はすでにされています）．
「任意のタグに合致する写真のリスト」は，SELECT文1文で実現できますが，インデックスを使用しない場合，クエリを分割したり，一部をSQLではなくプログラム側で処理するというような構造も効果的かもしれません．

ロジカルな仮説を立てて様々な工夫を試行錯誤をしてみてください．その内容を個別レポートで適切にアピールしてあると高評価になると思います．

実装C#

実装Cは，実装Bのプログラムを，インデックスを使用して検索するプログラムを実装してください．

【仕様】

progC.phpとして実装すること
データベースならびにインデックスを使用すること

Hint

SELECT文から「IGNORE INDEX」を削除するだけで構いません．
ユーザが入力したタグは，$_REQUEST[“tag”]に入っています（index.htmlでその設定はすでにされています）．

性能比較#

上記，実装A～Cの性能を，abコマンドを使って性能比較し結果を分析してください．グループ内全員の各実装の性能をグラフ化して比較し，グループ内で一番高性能な各実装を代表としてグループ発表で紹介してください．

上記3実装の性能は恐らく「実装B＜実装A＜実装C」なりそうですが，実装Aの工夫によって「実装B＜実装C＜実装A」も可能かもしれません．特に，この後の応用課題の結果などを反映して，実装Aで超高性能なプログラムになるよう頑張ってください．

【補足】

もしAjax等の非同期実行でクエリを発行するような高度な実装をした人は，そのクエリの実行時間が測れるようurlを設定してください．

クライアントサイドのみや主メモリ内のみで完結するような，本質的に異なる次元の工夫による実装の性能結果は， オンメモリ型であることなど明記し，参考値として性能結果を示してください（全体アーキテクチャや本質的な違いなど明確に説明してください）．

いずれにせよロジカルな仮説を立てて様々な工夫を試行錯誤をしてみてください．その内容を個別レポートで適切にアピールしてあると高評価になると思います．

上記abコマンドの引数（各班の性能差を際立たせるために重めの負荷になるよう設定）で各実装を複数回性能比較するとかなりの時間を要しますので，普段のデバッグ時は軽めの負荷で検証を進めてください．グループ発表や個別レポートに掲載する値は，上記abコマンドの引数の結果でお願いします．もし上記設定値での計測でも時間がかかりすぎて困難な場合は，cの値を下げていき，最終的には-n 1，-c 1での計測でも構いません．ただし，abのパラメータ値は，発表時も個別レポートでも必ず気付きやすいよう強調して明記しておいてください．

応用課題（一部必須）#

分担で①は必須，②は任意でやれるところまで，③は任意で実施してください．

①検索サーバ高性能化コンテスト#

①はprogAの独自仕様による超高性能化をコンテスト形式で実施します．全員必須課題です．

チケット予約サイトのようなWebシステムでは，不特定多数の膨大な同時アクセスに耐えられなければなりません．スケールアップやスケールアウトといった様々なアプローチがありますが，ここでは実装Aをさらに改良して，実装Cの速度を上回る検索パフォーマンスを目指してもらいます．

検索パフォーマンスはベンチマークサーバを使用して計測し，みなさんの成績を公開しながら進めます．最終的に上位のチームを表彰したいと思いますので頑張ってください！

検索パフォーマンスの向上には，

CSVファイルを前処理して，独自のデータ構造で保存する
Raspberry Piを複数利用しクラスタ化して検索する

等，色々な方法があると思います．ここで，皆さんの使用しているサーバ機やクライアント機におけるCPUのコア数やスレッド数（ハードウェア的制約），Linuxにおけるファイルディスクリプタ数の上限（ソフトウェア的制約）についてもご注意ください．またCPUによっては，高負荷になってCPU温度が高くなると動作周波数を落として性能を抑えるものもあります．何度も連続で負荷試験を行うと計測値が不安定になっていくことがありますのでご注意ください（CPUにヒートシンクを付けたり，CPUファンを付けたりすると多少効果あるかもしれません）．

皆さんの独創的なアプローチを期待しています！

＜補足＞最終課題の発表資料では，実装Aの結果として発表してください．

②Apache MPMによる高速化結果との比較#

②は任意でやれるところまでの実施としてください．

Webサーバとして世界的にデファクトとなっているApacheに搭載されているマルチプロセス機能(Apache MPM)の性能を用いた高速化を試し，独自実装による高速化結果と比較を行いましょう． Apacheのデフォルト設定では，Preforkと呼ばれる手法が指定されてますが，他にもWorkerやEventといった手法も指定できます．

第二部で自作したWebサーバとの違いも考慮しながら，これらの設定がどのようなものか調査し理解すると共に，実際にどのように性能に違いが出るのか，どうしてそうなるのか論理的な分析をしてください．

ここで，皆さんの使用しているサーバ機やクライアント機におけるCPUのコア数やスレッド数（ハードウェア的制約），Linuxにおけるファイルディスクリプタ数の上限（ソフトウェア的制約）についてもご注意ください．必須ではありませんが，以下の項目等について評価を行い，独自実装との差を検証してみるとよいでしょう．

実装Cについて，Apache設定変更の影響を分析する
Apache MPMの各方式について要点を整理し，どのような結果になるか論理的な仮説を立てる
MPM各計測結果を箱ひげ図などで可視化する
MPM各計測結果について，なぜそうなったのか，どうして仮説通りにならなかったのか（なったのか），など論理的な考察をまとめる
KeepAliveのON/OFFで性能差が出るようなabコマンドの設定を考え，性能計測を実施する
KeepAlive各計測結果について，なぜそうなったのか，どうして仮説通りにならなかったのか（なったのか），など論理的な考察をまとめる
第三者が再現できるよう実験条件を明記する

【補足】

Apacheの設定を変更するとグループ全員の測定に影響を与えますので，必ずグループのメンバーの了解を取って，あるいはグループのメンバー全員で協力して実施しましょう．計測対象のホームページは，最終課題の実装でなくても構いません．もし第二部でKeepAlive対応のWebサーバを実装したなら，そのWebサーバで性能計測しても構いません．重要なのは，各自で「仮説」を立てて検証することです．「この設定をこう変更したら，このような性能変化が計測できるかもしれない」というような仮設を立ててから実際に検証しましょう．

③自由課題（イマジネーション）チーム#

③は余裕がある方向けの任意課題です．自由に面白いWebシステムを実装してみましょう．

「Flickrの写真データを用いたシステム」を基本課題としますが，これ以外に面白いWebシステムを思いついた方は自由な発想で取り組んでくれてOKです．

例えば，写真の撮影位置の緯度経度情報が含まれていますので，検索機能をつけたり，地図へ表示する機能をつけたり，自由な発想で超興味深いWebシステムを実装してみましょう．

【仕様】

ネタがかぶらないよう，自由課題を実施する人達と十分意識合わせをし，それぞれ違う超興味深いWebシステムを実装すること

【補足】

以下を意識して工夫すると超興味深いものになると思います．

これまでの実装プログラムや，Node.js，WebSocket等の発展課題と絡めたWebシステム
たとえば，RDBのデータの代わりにFlickr Webサービスを直接利用するようなWebシステム
- Flickrの写真を使用する場合，写真の枚数は実験用データの1,000万件とはいいませんが，10万件以上の写真を対象としてみてください
世の中には様々なWeb APIが公開されてますので，Amazon，Google，IBM，Microsoft等が公開しているAI系のAPIも活用してみると面白くなりそうです

おわりに#

指示されたことを実施して報告するだけの「ふ～ん．だからどうした？」という報告書ではなく，実施した結果に対して「なぜ？」「どうして？」を考えて仮説を立てて検証してその結果どうなったか，「どうしてそのような結果になったのか？」「へーなるほどね」と感じさせるグループ発表や個別レポートを期待してます．

最終課題の詳細

Contents

最終課題の詳細#

はじめに#

使用機材について#

データセットのダウンロード#

PHPのエラー表示設定と確認#

データセットのダウンロード#

geotag.csvの概要#

tag.csvの概要#

テーブルの作成#

テーブル作成がうまくいかない人用の手順#

インデックスの作成#

基礎課題1（全員必須）#

実装A#

実装B#

実装C#

性能比較#

応用課題（一部必須）#

①検索サーバ高性能化コンテスト#

②Apache MPMによる高速化結果との比較#

③自由課題（イマジネーション）チーム#

おわりに#