ダメ人間オンライン

あまり信用しないほうがいい技術メモとか備忘録とかその他雑記

ISUCON2014予選に参加してきた

念願のISUCONに初参加してきた。
チームメンバーは同僚のaskaさんshiya氏で、「西日本世界チャンピオン*1」というチーム名で参加した。

予選までの準備

まずチーム名を考えるのに一ヶ月近く時間をかけた。最終的に満足のいくチーム名になって100万とった気になってた。

他には事前に準備しておいたほうがいいものや、どういう方針でやっていくかなどをチートシートとしてまとめて(githubのprivate repositoryで管理)メンバー内で共有した。これは当日も役に立ったので良かった。

特にshiya氏は普段objective-cを書いててサーバーまわりのことはわからないことだらけとのことだったので(しかも我々が選択する言語はPerlだ!)、事前に準備しておけばできるような作業(アクセスログ解析とかhttpdからnginxへの入れ替えとか)についてもチートシートにまとめておいて確認してもらった。

予選当日

まず心の拠り所として
f:id:dameninngenn_owata:20141003032100p:plain
を共有してた。これも共有しておいて良かった。

開始直後は予め決めていた進め方通りに進めた。

  • 俺がAMIを起動して一旦みんなでそこへログインする
  • 他の皆が環境やapplicationを確認してる間、俺が必要なもの(webapp, my.cnf, nginx.conf, etc...)をgitで管理できるようにしてprivate repositoryへpush
  • デフォルトで動いてるrubyのアプリケーションを止めてperlで起動するよう変更
  • 各種再起動スクリプト等を準備
  • 環境が整ったらその状態からAMIを作成してチームメンバーに共有して、各メンバーはそのAMIを元にインスタンスを立ち上げて自分の環境で作業する

ここまでは割りとスムーズに進んだ。もちろんインスタンス起動直後にベンチマークを走らせてお約束の

をやってゲラゲラ笑ってた。

ちなみにベンチマークは比較がしやすいよう17時ぐらいまでは--workload 1しばりで行こうという方針にしてた。

各自確認した情報を口頭やIRCで共有しつつどこから取り掛かるか目星をつけていった。

  • proxyからstaticファイル配信したい
  • appへの接続をTCPからUNIX domain socketへ変更したい
  • session storeをファイルからメモリへ
  • memcachedいれとくかー
  • 気まずいSQLたくさんあるのでなんとかする
  • まず明らかindex貼ったほうがいいとこは貼る
  • mypageでアクセスするたびusersからSELECTしてるけどどうかなー

最初挙げたのはこれぐらいだったと思う。

そこから各自これやるわーって言ってやり始めた。
俺とaskaさんはアプリケーションまわりとか気になったとこからやり始めて、shiya氏にはまずnginxの設定変更してstaticファイルをnginxから配信してもらうようお願いした。

リポジトリの運用ルールとしては、

  • まずブランチを切って作業してそのブランチでベンチマークを走らせる
  • masterにマージした時もベンチを走らせてスコアをタグとして記録

という風にした。途中から案の定ぐだったけど、ぐだった場合はこのルール気にせず本質的な対応に注力しようというのも共有してたので「おい!このマージスコアいくつやねん!!タグついてへんぞオラァ!!!!」みたいなケンカには発展しなかった。

で、ここまではわりかし順調やったけどここから雲行きが怪しくなってきた。
なんかしらんけど(←)ベンチマークのfailカウントが0じゃなくなった。
特に大した対応してないはずやのに突然。なんか変更加えるたびにベンチ走らせて確認してたはずやのに突然。
なんか記録してない意図せずやったことがあるんやろうけどhistory遡ったりcommitログ遡ったりしてみたけど全く改善しない。
masterとして扱っていたインスタンスでは同じgitのリビジョンでも再現しなくてほんとにわけわからん状態になった。

結論から言うともちろんなんかしてたわけで原因はあったわけやねんけど、それが判明した頃には既に2時間ぐらい経過してた。
askaさんがこれが原因じゃね?って言ってくれて「いやいやまさか、、、うわぁああああああああ」みたいに判明した。askaさんの時間も奪ってしまったしほんと死ぬしかない感じだった。

いやいや違うんですよ。だって(言い訳は削除されました)

で、ここで完全に壊されて次の対応も何かハマって死にそうになって気がついたらえらい時間経っててご飯も食べてないから頭回ってなくて昼飯買いに行ったのが3時か4時ぐらいだったと思う。

そこから慌ててindex貼ったり、ログインに失敗したカウントはip基準とuser_id基準で別テーブルにしてそっちでカウントとってったほうが楽そうってことでそうした。
ここらへんでスコア13000(--workload 1)ぐらいだった。そういえばスコアの送信最初と最後のほうしかしてなかった。

ここで気づいたのが別テーブルにしたらinit時にダミーでinsertしてるデータ分も同様に最初に対応しとかないとダメってことでその対応もした。この初期データ対応は結構難航した。

failure_countを上のように別テーブルで管理するんじゃなくmemcachedとかでincrしてけばいいかなって話も出たけど、一度ログインに成功したらそこからのカウントを元々とるようになってたしmemcachedでincrした場合に途中でサーバー再起動かかってデータ吹っ飛んだら正しくカウントができないってことでその案は没になった。
一度BANされれば状態は変わらないけど失敗カウントが増えてる段階ではそのカウントも保持しておかなければいけない。

それ以降もなんかやろうとしてたけどベンチマークのfailが増えたりして中々うまくいかんくて気づいたら17時とかになってたのでそれなりのスコアで送信しとかないともうまずいってことに気づいた。

その時点でのmasterブランチは安定してなかったので過去のスコアがよさそうなブランチでworkloadの値変えながらベンチとった。
それでスコア30000ぐらいとかだったしまだやれることもあったけどどんどん時間がなくなっていった。

結局nginx.confとmy.cnfをいじってる時間もなくてほぼデフォルトの状態のままだった。my.cnfは予め準備してたサンプルのmy.cnfからコピペしつつちょっと設定いじったりもしたけど特にスコアに反映されるようなことはできなかった。

最後masterも安定した状態になったよってことだったのでそれに変更してベンチマークとった。
最終的に送信したスコアは33000ぐらいだった。

あの無駄にした2時間あればもうちょいなんとかなったかもっていう悔しさばかりが残ってるけどこればかりは仕方がない。
我々西日本世界チャンピオンはチャンピオンになれなかった。

最後スコア33000↑で時間内に送信したはずやのにグラフには30000のが残ったままやなーそういうもんかなーって思ってたら、どうやら最後のベンチはreportのcheckのとこでfailしてたようでそれに気づいてなくてそのまま提出してしまってた。後日提出したAMIからインスタンスもっかい立ち上げてベンチマークとってみてその時気づいた。もう死ぬしかない。


今回の失敗によってISUCONを戦ううえで大事なことがわかった。
ご飯は食べよう。


本選に出場できないのはほんと悔しいけど初めてのISUCON予選すごく楽しかったので運営の皆様には感謝するばかりです。
本当にありがとうございました。

The scrypt algorithm

scrypt(scriptではない)について調べた。何か間違ってたらご指摘下さい。

ググらビリティが最悪すぎて情報を探すのにすごく苦労した。。

Proof-of-work

BitcoinのProof-of-workではSHA-256が使われてるけど、LitecoinやMonacoinの場合はscryptっていうのが使われてるらしいってのを知って興味持ったので調べてみた。

scryptとは

Tarsnap - The scrypt key derivation function and encryption utility

  • ハッシュ方式の1つで、計算時に大量のmemoryを必要とするよう設計されている。
  • memoryを大量に必要とすることでブルートフォースアタックへの耐性を高めていると主張。
  • 一度の演算でmemoryリソースが大量に必要となればハードウェアにそれなりのスペックを要求することになる。
  • 昨今SHA-256の演算とかだと専用のチップとかですげー速さで演算できたりするらしいけどそういったことを困難にしている。

アルゴリズム

本家資料
http://www.tarsnap.com/scrypt/scrypt.pdf

簡易的な説明(図がわかりやすい)
http://alpha-t.net/wp-content/uploads/2013/11/Alpha-Technology-Scrypt-Analysis-on-FPGA-proof-of-concept.pdf

日本語での詳細な説明!!!(日本語での解説はこの方のblogしか見つけられなかった)
scryptを実装してみた 前編 | プログラマのつれづれなるままに

正味本家の資料見ただけじゃちんぷんかんぷんすぎて頭が痛くなった。。
頭の悪い俺にもわかりやすい資料を~~って探して図がわかりやすいのを見つけた。 なんとなく全体像がわかったけど詳細部分がいまいちまだ理解できなくて探してたら日本語で詳しく解説してるエントリ(最高!)を見つけて大体大雑把な感じで理解した。

細かい部分を理解するにはやっぱりコード見るのが早いなってことでscrypt実装のコード探してみた。

scrypt - Wikipedia, the free encyclopedia
ここに色んな言語での実装一覧があって、あっPerlもある~~~って思って見てみたけどXSで書かれてて全然読めなかった。つらい。
RubyとかPHPとかのコードもなんか .c ってファイルが見えたりしてアッアッてなって自分の無能さがただただつらかった。

で、ひと通り見て自分にとってはJavaの実装が一番わかりやすかった。
https://github.com/kocakosm/pitaya/blob/master/src/org/pitaya/security/SCrypt.java

ここまでの資料とか図とかコードとかを全部見てようやくなるほどーって感じになった。

キーとなっているのは BlockMix って書かれてるとこの処理で、ROMix の中で2回 BlockMix のフェーズがある。
どちらのフェーズでも1024回ループぶん回して(CPU/memoryのコストパラメータが 1024の場合) Salsa20(Rounds => 8) でハッシュ値をこねくりまわしてる。

最初のフェーズでは演算毎に得られたハッシュ値を全て保持するようにしている。ここがmemoryを一番使うところで、例えばブロックサイズのパラメータが 1 でCPU/memoryのコストパラメータが 1024 とかだと 128 * 1 * 1024 = 128kB のmemoryサイズを必要とする。
ブロックサイズのパラメータやCPU/memoryのコストパラメータを変更すると必要なmemory量も変化する。

2度目の BlockMix のフェーズでは上記で演算した結果を用いて1024回ループぶん回している。

memoryを必要としている仕組みがこれでわかったのでスッキリした。

スッキリしたついでに理解できてるかの確認も含めてXSじゃないPerl実装書いてみようかなと思ったけど、技術力もなけりゃ元気もないのでやめた。(`ェ´)ピャー

まとめ

たぶん2ヶ月もすれば全て忘れそう。

いまさらBitcoinの仕組みについて調べてみた

Bitcoinって聞いたことあるけど「アーハン、ネット上の仮想通貨みたいなやつなんでしょ。あとなんかハッシュめっちゃ計算する必要があるとかなんとか」ぐらいの理解で 、「儲かる!」「いや、今はもう儲からない!」とかは耳に入ってたけどあまり興味もてなかった。

けど先週末あたりに Monacoin をきっかけに急に興味持ち始めて色々調べてみた。

Bitcoinとは

ざっくり言うと P2P型の決済網及び暗号通貨 とのこと。

俺の下手くそな説明見るよりこれ見たほうが早い
Bitcoin-ビットコイン-とは何か?
ビットコインの採掘とは実際には何をしているのか?

元となった論文(pdf)
http://www.bitcoin.co.jp/docs/SatoshiWhitepaper.pdf

公式FAQ
Bitcoin P2Pベースの仮想通貨 - ビットコイン

氏名とか口座番号とかなくても気軽に送金・受取ができるようになるのは良い。

よくわからなかったとこ

上記の資料読んだり他にもwebでもろもろ調べたり、実際にpool(採掘場)に登録してcoin採掘してみたりしたけど仕組み的によくわかんないとこがでてきた。

ハッシュ値計算中に貨幣取引トランザクションを追加する必要が出た場合

ある時点での取引トランザクションを含めたブロックでハッシュ値計算をしてる最中に新たなトランザクションが追加された場合、次の計算はそれを加えるべきか無視して次のブロック計算にまわしていいのか、加えてしまった場合また1から計算しないといけないので無駄になるのではないか、とか明記されていないことについて疑問に思った。

結論から言うとこの疑問自体が間違ってて、新たなトランザクションが追加された場合は普通にそれを加えて計算すればよい。
というのもハッシュ値の計算には複数パラメータが必要で、そのパラメータの中にブロック生成の時間(unixtime)が含まれているので1秒毎にハッシュ計算元の値は変化する。
これは全マイナー同様なので採掘の性能として重要なのは単純に1秒間の演算処理能力だけである。なのでどっちみち変化するのでトランザクション追加したところで何も変わらない。すごく乱暴に言うと1秒毎にヨーイドンを繰り返してるようなもの。
重要なのは1秒間にどれだけの数のNonceを試行できるかということ。

Block hashing algorithm - Bitcoin

pool(採掘場)利用時、支払先アドレスがpoolのものになるのでnonceを除いた計算元のハッシュがユニークにならずnonceがかぶったりするのでは?

ソロマイニングだと支払先アドレスが自分のものになるので生成するハッシュは(ほぼ)必ずユニークになるが、poolだとその部分が固定になっちゃうのでnonceがかぶったりするのどうしてるんだろうと思った。

poolが各nodeに「あなたはnonce何番から~」とか指示したりしてるのかなとか、nonceはインクリメンタルじゃなくランダムな数値を使って試行してるのかなとか考えて MPOS とか cpu-miner とかのソースコードを適当に読んでみたけどそうではなさそうだった。

pool利用時はstratumっていうプロトコル使っててそこのドキュメントにそれっぽいことが書いてあった。
Stratum mining protocol - mining.bitcoin.cz

Extranonceという値を用いてcoinbaseのトランザクション(のserialization)をユニークにしてるらしい。
この例で言うとScryptSigかScriptPubKeyのことなんかな?トランザクションの生成のとこはちゃんと読んでないから間違ってるかもやけど。
http://blockexplorer.com/tx/51d37bdd871c9e1f4d5541be67a6ab625e32028744d7d4609d0c37747b40cd2d

へーなるほどーって思ったけど英語誤読してる可能性もワンチャンある。

ブロックに含めるトランザクションがMerkle TreeのRoot Hashだけで良い理由

基本的にnode間ではブロックチェーンだけやりとりしてるから Root Hash だけあったところで詳細なトランザクションの検証をあとからするには情報が足りないのではと思った。

どっかに明記されてたわけじゃないけど、マイナー(採掘)ノードじゃなく財布ノードのほうで分割してデータ持ったりしてんじゃないかな。以上。

おわりに

だいたい理解できたつもりでいる。

あとはBitcoinはいいけど、Litecoin とか Monacoin は SHA-256 じゃなく scrypt って方式でやってるらしい。よく知らないからこれもちゃんと調べときたい。ググってもちゃんとした情報見つけられなくてよくわかんなかった。

採掘は今Monacoinだけでやってて、だいたい 300kh/s ぐらい。
Monacoin はまだできたばっかで利用用途とか考えたりするのがおもしろそう。投げ銭推奨派なのでこの先楽しみ。Monacoinについてはまた別途書く。たぶん。

気軽に投げ銭してくれてもいいんですよ?

進捗どうですか?

進捗ダメです

大体インターネッツのせいでダメなこと多いので、人間から怒り口調で聞かれるより前に優しく聞いてくれるChrome拡張書いた。
dameninngenn/chrome-ext-shinchoku-san · GitHub

f:id:dameninngenn_owata:20131001025607g:plain

ウェッッッブページ開いた回数をカウントして指定した回数に達したら通知が出る。回数は自分で設定できる。

YAPC::Asia Tokyo 2013に行ってきた&LT-THONで話してきた

今年もYAPC::Asia Tokyoに行ってきました。

前夜祭

LT-THONで話しました。
前半は前夜祭であるということをお伝えし、後半はここ一年ぐらいで書いたコードのことをいくつか話しました。

誕生日ですっつってあんなに拍手もらったの人生で初めてで、社交辞令的拍手だとわかってはいても嬉しいものでした。

あ、そういえば今日は25日ですね。多くの方は今日給料日ではないでしょうか?有益なURL置いておきますね^^

https://www.amazon.co.jp/registry/wishlist/2NFCUB363SFD8

https://www.amazon.co.jp/registry/wishlist/2NFCUB363SFD8

https://www.amazon.co.jp/registry/wishlist/2NFCUB363SFD8

https://www.amazon.co.jp/registry/wishlist/2NFCUB363SFD8

https://www.amazon.co.jp/registry/wishlist/2NFCUB363SFD8

まだ間に合いますし遠慮しなくていいんですよ^^^

あと質疑応答で「コメントは差し控えさせていただきます」みたいなこと言ったのは、名前挙がった方とは面識ないので(もちろん一方的に知ってはいる)何も言えなかっただけです。。


前夜祭の会場は結構広かったんですが、後ろのほうまで机が並んでいてみんなちゃんと座る感じだったのでみんなLTを聞き入ってた感じでした。後ろ1/3ぐらいは机とっぱらってLT聞きたい人は前のほう座って後ろのほうは人と話して交流できるような感じにしとくのもアリだったのかなとも思いました。

LT-THONは気楽に参加できるので、今年も開催されて嬉しかったし楽しかったです。ありがとうございました。

1日目

急行乗ってると思ったら特急乗ってて日吉余裕で通りすぎて遅刻した。

1日目で一番印象に残ったのはおまけの話だったけど Regexp::Debugger で、なんかワクワク感がすごかった。ワクワク人間。

某非公式イベントもすげーおもしろくて良かった。特にyusukebeさんが親指を立てながら溶鉱炉に沈んでいくシーンは涙無しには見られなかった。

2日目

座談会のセッションおもしろかった。今回のYAPCで一番楽しみにしてた。

懇親会ではビールこぼしておもらししたみたいになってしまった。実際におもらししたとしてもみんな酔っ払ってたのできっと気づかれないし何も問題はなかった。

まとめ

今年も3日間とても楽しかった。スタッフの方々や皆様に感謝です。

ちらっと話が出てたYAPC::Tohokuも楽しみですね。

さて来年は・・・