セキュリティキャンプ2018 応募用紙
はいどうも，しゅういちです．何か世界線を間違えてしまったのか，バグが生じてセキュキャン データベースゼミ(定員2名)に通りました．
そのため，毎年恒例らしい(？)応募用紙晒しをしていきたいと思います．あまり参考にならないと思いますが，自分みたいに技術的に強くないけど面白そうだし申し込むか悩んでいる...という人の背中を押せると嬉しいです．
きっかけ
以前よりセキュリティや低レイヤには興味があり様々な本(ハリネズミ，OS本，ハッカーの学校など)を買っていて，1年前にTwitterで募集を見かけたのが参加のきっかけでした．
興味が沸いた理由として，セキュリティや低レイヤって名前だけですでにかっこいいと思いませんか？僕は思います．ハッカーかっこいい(ホワイトじゃないとだめ)
だがしかし競プロ(の沼)にハマっていったりしていてあまり勉強できていません...
こんな感じに面白そうだと思った分野を色々とふらふらしていますが，面白いって思えることに対して懸命になれるってのはいいことじゃないかなって思います．
今年も開催されることを知り，コースで面白そうなものがないかな...って調べていた時に目が惹かれたのがこのデータベースゼミでした． アルゴリズムやデータ構造が大切というワード+トランザクション処理がすごいと興味が沸いたのが理由でした．
応募用紙を書く上での方針
そんなこんなで興味を持ったはいいものの，「自分なんて弱いしどうせ...」と思いながら問題を見ていくと，
たくさん時間をかけて完璧な答えを作る必要はありません．
調べる過程で分かったことだけでなく，分からなかったことや疑問に思ったことも書いてください．
また，参考にした書籍や Web ページについては全てリンク等を書いてください．
とのことでした．
このときの僕「これもしやワンチャンあるのでは...？」
いろんな情報を参考にしてもいいのなら，実力のない自分でも応募用紙を書きつつインプットをしていけば，受かる可能性があるのでは...？と思いました．
こうしたことから，応募用紙を書く際，
知識など大まかなものは一定度信頼できるネット記事から引用(内容を噛み砕きながら)．
自分の中で噛み砕いた内容を文章に反映させて，それに関する自分なりの考えを示す．
自分に技術や知識が足りないことは自明なので，代わりに熱意や興味の強さが伝わるよう文章を工夫する．
講師の先生のメッセージからどのようなことを期待しているのか想定し，それに沿うような文章を作る．
ということに気をつけました． というわけで，ここまでがどうでもよくて，ここからが本編．
問題1
問題文
ACID (atomicity, consistency, isolation, durability) について説明してください．
解答
ACIDとは，信頼性があるトランザクションシステムの持つべき性質として定義されたもので，Atomicity(原子性)，Consistency(一貫性)，Isolation(独立性)，Durability(永続性)の略称である． まず，トランザクションとはデータに対する１つの一連の操作のことである． 原子性は，トランザクションに含まれるタスクが全て実行されるかあるいは全く実行されないという性質である．ある1つだけ実行されると矛盾が生じる危険性があるからだ． 一貫性は，そのデータベース内で一貫したルールをトランザクション開始と終了時に満たしているという性質である．現実に存在しない値があると矛盾が生じてしまうからである．例えば口座残高がマイナスになることはありえない． 独立性は，トランザクション中の操作の過程が外部から隠蔽されていることである．他の操作と分離することでセキュリティを高めていると思われる．ところが並列処理をすると独立性から外れてしまうが，そうしないと処理速度が遅くなるので実用性と独立性をいい塩梅で実装することが大事である． 永続性は，トランザクション終了時点でその操作が永続的となりその後結果が失われないことである． https://ja.wikipedia.org/wiki/ACID_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E7%A7%91%E5%AD%A6) https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3%E5%88%86%E9%9B%A2%E3%83%AC%E3%83%99%E3%83%AB
補足
Wikipediaからの引用は信頼度が高いとは言えないので，あくまでアイデアの参考程度にして引用は避けた方が良いと思います．少々自分らしく書き直していますけどだいたいそのままです． トランザクションを実生活で全く気にしていなかったので，概念を知ったときはすごく感動しました．
問題2
問題文
Python の threading と multiprocessing パッケージの違いについて説明してください．
その違いが分かるような簡単なプログラムを書いて動かしてみて,結果を教えてください．
解答
Threadingは今あるプロセス内で複数のスレッドを立ち上げるが，Multiprocessingは今あるプロセスとはまた別のプロセスを新たに立ち上げて処理を行わせる．それぞれスレッドとプロセス単位で並列処理をしているという違いがある．以下にそれぞれの簡単なコードとその実行結果を示す．
(Threadingの場合)
import os import threading MAX_COUNT = 100000 ITERATION = 50000 def whoami(what): # 単純な加算 count = 0 for n in range(MAX_COUNT): if count % ITERATION == 0: # 実行中のプロセスIDと,現在のcount数とスレッドナンバーを表示 print("{} Process {} thread= {} count {}".format( what, os.getpid(), threading.current_thread(), count)) count += 1 # どのスレッドが終了したかを表示 print("end {} Thread {}".format(what, threading.current_thread())) # 現在のプロセスのidを表示 print("Main Process ID is {}".format(os.getpid())) # メインのプロセスで実行 whoami("main program") for n in range(5): p = threading.Thread(target=whoami, args=("Thread {}".format(n),)) p.start() P.join() print("end of program")
(Multiprocessingの場合)
import os import multiprocessing MAX_COUNT = 100000 ITERATION = 50000 def whoami(what): # 単純な加算 count = 0 for n in range(MAX_COUNT): if count % ITERATION == 0: # 実行中のプロセスIDと,現在のcount数を表示 print("{} Process {} count {}".format(what, os.getpid(), count)) count += 1 # どのIDのプロセスが終了したかを表示 print("end {} Process {}".format(what, os.getpid())) # 現在のプロセスのidを表示 print("Main Process ID is {}".format(os.getpid())) # メインのプロセスで実行 whoami("main program") print("-----------------------------------------------------") # プロセスを5作りスタートさせる. for n in range(5): p = multiprocessing.Process(target=whoami, args=("Process {}".format(n),)) p.start() print("end of program")
(Threadingの実行結果)
Main Process ID is 47452 main program Process 47452 thread= <_MainThread(MainThread, started 140736268198784)> count 0 main program Process 47452 thread= <_MainThread(MainThread, started 140736268198784)> count 50000 end main program Thread <_MainThread(MainThread, started 140736268198784)> Thread 0 Process 47452 thread= <Thread(Thread-1, started 123145442807808)> count 0 Thread 0 Process 47452 thread= <Thread(Thread-1, started 123145442807808)> count 50000 end Thread 0 Thread <Thread(Thread-1, started 123145442807808)> Thread 1 Process 47452 thread= <Thread(Thread-2, started 123145442807808)> count 0 Thread 1 Process 47452 thread= <Thread(Thread-2, started 123145442807808)> count 50000 end Thread 1 Thread <Thread(Thread-2, started 123145442807808)> Thread 2 Process 47452 thread= <Thread(Thread-3, started 123145442807808)> count 0 Thread 2 Process 47452 thread= <Thread(Thread-3, started 123145442807808)> count 50000 end Thread 2 Thread <Thread(Thread-3, started 123145442807808)> Thread 3 Process 47452 thread= <Thread(Thread-4, started 123145442807808)> count 0 Thread 3 Process 47452 thread= <Thread(Thread-4, started 123145442807808)> count 50000 end Thread 3 Thread <Thread(Thread-4, started 123145442807808)> Thread 4 Process 47452 thread= <Thread(Thread-5, started 123145442807808)> count 0 Thread 4 Process 47452 thread= <Thread(Thread-5, started 123145442807808)> count 50000 end Thread 4 Thread <Thread(Thread-5, started 123145442807808)> end of program
(Thread(p.join()なしの場合)の実行結果)
Main Process ID is 47410 main program Process 47410 thread= <_MainThread(MainThread, started 140736268198784)> count 0 main program Process 47410 thread= <_MainThread(MainThread, started 140736268198784)> count 50000 end main program Thread <_MainThread(MainThread, started 140736268198784)> Thread 0 Process 47410 thread= <Thread(Thread-1, started 123145563901952)> count 0 Thread 0 Process 47410 thread= <Thread(Thread-1, started 123145563901952)> count 50000 Thread 1 Process 47410 thread= <Thread(Thread-2, started 123145569157120)> count 0 end Thread 0 Thread <Thread(Thread-1, started 123145563901952)> Thread 3 Process 47410 thread= <Thread(Thread-4, started 123145579667456)> count 0 Thread 1 Process 47410 thread= <Thread(Thread-2, started 123145569157120)> count 50000 Thread 4 Process 47410 thread= <Thread(Thread-5, started 123145584922624)> count 0 Thread 2 Process 47410 thread= <Thread(Thread-3, started 123145574412288)> count 0 Thread 4 Process 47410 thread= <Thread(Thread-5, started 123145584922624)> count 50000 end of program end Thread 1 Thread <Thread(Thread-2, started 123145569157120)> Thread 2 Process 47410 thread= <Thread(Thread-3, started 123145574412288)> count 50000 Thread 3 Process 47410 thread= <Thread(Thread-4, started 123145579667456)> count 50000 end Thread 4 Thread <Thread(Thread-5, started 123145584922624)> end Thread 2 Thread <Thread(Thread-3, started 123145574412288)> end Thread 3 Thread <Thread(Thread-4, started 123145579667456)>
(Multiprocessingの実行結果)
Main Process ID is 47403 main program Process 47403 count 0 main program Process 47403 count 50000 end main program Process 47403 ----------------------------------------------------- Process 0 Process 47404 count 0 Process 1 Process 47405 count 0 Process 2 Process 47406 count 0 end of program Process 0 Process 47404 count 50000 Process 1 Process 47405 count 50000 Process 2 Process 47406 count 50000 Process 3 Process 47407 count 0 Process 4 Process 47408 count 0 end Process 0 Process 47404 end Process 1 Process 47405 Process 3 Process 47407 count 50000 Process 4 Process 47408 count 50000 end Process 2 Process 47406 end Process 3 Process 47407 end Process 4 Process 47408
実行時間はそれぞれ0.167s, 0.159s, 0.183sであった． Threadingの場合，processは1つのみ立ち上がっており，その中で5つのthreadが立ち上がっているのが確認できた． p.join()がない場合，end of programが途中に出力された．ある場合はそれぞれ順番にスレッドが立ち上がり，その処理が終了すると次のスレッドに移行していく様子が確認できた． Multiprocessingの場合，processは5つ立ち上がっているのが確認できた．プロセスは同時に最大３つ立ち上がり，3つが並行で処理されていく様子が確認できた． Multi processingだとそれぞれのプロセスで処理が同時に行われていく様子から，処理を分散できているのが確認できたが，Threadingだと終了の出力のみ並列してそれ以外は順に行われていて，いまいち高速化されたのか今回のコードではわかりにくかった． また，MAX_COUNT = 100000000，ITERATION = 50000000かつrangeを20，つまりプロセスやスレッドを20にしてローカルで実行した結果，Threadingでは4m24.323s，Multi processingでは2m44.896sとMulti processingの方が効率が倍以上異なった．これより，大きな処理の場合はMulti processingの方を選択すべきだと考えられる．しかし，Multi ProcessingだとPCのファンがかなり音を立てていたので，エネルギーを急激に消費しているのではないかと考えられる．
https://qiita.com/ogihara/items/1b7f002b7d14a2710bce http://d.hatena.ne.jp/torasenriwohashiru/20110528/1306594075
補足
ここはかなり難しかった記憶があります． コードそのものは完全に引用で，考察もこれらのサイトに頼りきりになっていました．
この問題を通して，これまでより一段スレッドとプロセスの違いがわかった気がします． 上記の詳細やコードの意味がわからない場合は，リンク先に飛びましょう．
問題3
問題文
次の中から 2 つ選んで説明してください． 3a. データ構造としての Hash table と Tree の違いについて．
3b. pthread_mutex_lock() と CAS 命令等を使って作る spinlock の違いについて．
3c. Write-ahead Logging (WAL) について．
3d. Strict Two-Phase Locking (S2PL) について．
3e. Deadlock と Starvation について．
解答
3aと3cを選びました．
3a
Hash tableとは，キーを持つデータ集合に対して，動的な挿入，検索，削除を効率的に行うことができるデータ構造の一つである．ハッシュテーブルはm個の要素を格納できる配列Tと，データのキーから配列の添字を決定する関数(ハッシュ関数)から構成されている．以下のように実装できる． def insert(data): T[h(data.key)] = data def search(data): return T[h(data.key)] ハッシュ関数はハッシュ値が0..m-1(mは配列Tのサイズ)をとるように実装する．この条件を満たすためには，剰余算を使い出力値が必ず0..m-1の整数になるようにする．例えば， h(k) = k % m を使うことができるが，このままだと異なるkeyが同じハッシュ値になる衝突が起きる可能性があるので，回避するためにダブルハッシュを用いたオープンアドレス法がある．次のようにハッシュ関数を定義する． H(k) = h(k, I) = (h_1(k) + i * h_2(k)) % m このハッシュ関数h(k, i)はキーkに加えて，整数iを引数としている．このiは衝突が発生して次のハッシュ値を計算した回数を表している．つまり，ハッシュ関数H(k)は，衝突が起きる限りh(k, 0), h(k, 1), h(k, 2), …を計算し，衝突が起こらなかった最初のh(k, i)をハッシュ値として返す．計算量は衝突しない限りO(1)となっている．また配列を大きくとるため，空間計算量は大きくなる．しかし，要素の挿入・削除にはO(n)の計算量がかかる．
Treeとは，節点(node)と節点同士を結ぶ辺(edge)で表されるデータ構造である．Treeの一種であるBinary Treeは1つの根を持ち全ての節点についてその子の数が2つ以下の木である．計算量がO(log n)で行え，メモリを多めにとっておく必要がない．実装としては，各節点が親と子に対するポインタを持った構造体であることが多い．他にもヒープと呼ばれる配列を使った木構造で実装されることもある． まとめると，Hash tableは剰余算を使ってO(1)でアクセスできるような配列で，TreeはO(log n)でアクセスできる構造体あるいは配列である．参照するだけならHash tableが効率がよく，挿入，削除をする場合はTreeの方が効率がいい．
[プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 渡部 有隆 著，Ozy，秋葉 拓哉 協力(マイナビ出版) p.127~130, 186~187] http://d.hatena.ne.jp/yohei-a/20120130/1327887478
3c
Write-ahead Logging (WAL)とは，ログ先行書き込みと呼ばれるもので，トランザクションをコミットする前にその全てのデータ更新を逐一ログに書き出し，データベースの更新はそれをまずログに書き出してから行うというものである．これは，トランザクションを障害から守るためにログを記録するが，先にデータベースを更新してその後ログを記録する前に障害が起きてしまったら，ログに書き込もうとしていた情報が消えてしまい，再起動時にデータベースに対してその更新をREDO, UNDOする手掛かりがなくなってしまう．そのため，コミットする前にログに書き込むことが必要となる．
[リレーショナルデータベース入門 第3版 増永 良文 著(サイエンス社) p.276~277]
補足
とりあえずググってみて，すぐに説明ができそうなものと，競プロでよくあるデータ構造について解答しました．自分にとってわかりにくいものやあまり興味がわかないものは極力避けました． Treeの説明雑いなぁとか思いながら解答していましたが，提出期限ギリギリだったので許してくださいって感じです．
WALは言われてみればそうだなぁという感じです．gitのようなバージョン管理ソフトと本質は同じだと思います．ただ任意でrebaseできない(できないですよね？)などの違いはあると思います． リレーショナルデータベース入門 第3版は大学の図書館にありました．これから頑張って読んで勉強します...(追記: 結局そこまで読まなかった気がします...)
問題4
問題文
あなたの興味,経験,能力について自由に書いてください．
解答
弱くて恥ずかしいので割愛．
補足
とりあえず，DBについて興味があり，その中でも「たまたま」講師の方と同じトランザクションについて興味があったのでそれについて述べたり，競プロが好きなので(レート800程度の雑魚)そのことを述べたり，最近Web系を勉強している(PHPでインターンに参加している)ので，それ関連について述べたりしました．
一応自分が触れるのは(=ある程度コードが読めて，ググりながらなら書ける)C，C++，C#，PHPとかです．DBはMySQLぐらいです．この程度の技術力です．
今回応募することで得た知見
とりあえずでも，自信がなくてもチャレンジすることは大事，別に何かが減るわけではないので．
応募用紙を書くだけでも知識は身につく．
期限があるので，タスク管理には気をつけよう．
結論
本当どうして通った？！？！！
