Hadoop MapReduce デザインパターン4章〜7章
Hadoop MapReduce デザインパターン ―MapReduceによる大規模テキストデータ処理
- 作者: Jimmy Lin,Chris Dyer,神林飛志,野村直之,玉川竜司
- 出版社/メーカー: オライリージャパン
- 発売日: 2011/10/01
- メディア: 大型本
- 購入: 4人 クリック: 254回
- この商品を含むブログ (16件) を見る
Hadoop MapReduce デザインパターン1章〜3章 - n-3104の日記の後編です。
4章 テキスト抽出のための転置インデックスの生成
- Web検索におけるコンテンツの収集(クローリング)、転置インデックスの構築、検索された際の検索結果の抽出(ランキング)の3つについて書かれています。といってもメインは転置インデックスの構築で、あとはおまけでちょっと書いてある感じです。
- Web検索の概要を知らない方はGoogleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)の第1章を読んでおくと読みやすいかもしれません。4-1に転置インデックスについても書かれています。
- 3章で紹介された以下のパターンの利用例が記述されています。
- 4.5 インデックスの圧縮 についてはよく分からなかったので読み飛ばしてしまいました(^_^;)
- Hadoop MapReduce デザインパターンの4章を読んでみた。 - watawata日記は読んだ方がよいと思います。
5章 グラフのアルゴリズム
- MapReduceによるグラフの並列幅優先探索とPageRankについて書かれています。
- グラフです。Hadoopやるならグラフは必須と聞いて、ちょっと前から少しずつ勉強してましたが、少しは理解できるようになった気がします。
- グラフの探索の基本的なところについてはAlgorithms with Python / 集合, グラフ, 経路の探索で私は勉強しました。ちなみに、このページで勉強する前に子象本を読み終えていたりするのですが、まぁ理解していなかったということですね(^_^;)
- まずは並列幅優先探索ですが、こちらについてはLarge-Scale Graph Processing〜Introduction〜(完全版)を見るといいと思います。実際にMapReduceによってどのようにデータが処理されているか図で説明されていてとても分かりやすいです。
- スライドの前半のSSSPの所です。ちなみに、子象本では距離1ですが、スライドでは距離nで書かれています。
- あと、子象本で指摘されている毎回グラフをReducerに転送する問題についての対処方法であるShimmy Trickについてもスライドには書いてあります!
- ちなみに、ダイクストラアルゴリズムについては文系 Hadooper でも分かる Dijkstra アルゴリズム - cocoatomo衝動日記を以前読んで理解しました。
- PageRankについてはもうちょっと数学力?がついてからリトライしようと思います。概要は理解できましたが、すっきりしない感じでした(^_^;)
6章 テキスト処理のためのEMアルゴリズム
- 期待値最大化法(EM)アルゴリズムとMapReduceへの適用について書かれています。
- 撃沈です\(^o^)/ 色々勉強してから出直します。
- とりあえず文字だけ追えば雰囲気はつかめました。
- WEB+DB PRESS Vol.64の特集3の「作って学ぶ日本語入力」も一緒に読むといいかもしれません。ビタビアルゴリズムも紹介されています。
後半まとめ
書いてよかったです。最初に読んだ時は5章はあまり理解できていなかったのですが、今回改めて読んだり調べたりしたお陰で並列幅優先探索について理解できました。
個人的にHadoopが好きなのは、ちゃんとアルゴリズムを扱っている感じがする所です(他にもトレードオフを常に意識させられる点とかミドルウェアっぽい所とか色々ありますけれど)。普段はif文と文字列操作が大半で、せいぜい再帰処理を書くぐらいなので(モデリングやら実装パターンやら色々ありますが)。もちろん、アルゴリズムを使う仕事もあると思うのですが、自分自身にそういう能力がないこともあり、縁遠いなーと思っていた所でHadoopに出会い、とても刺激的で楽しいです。
ちなみに、Hadoopそのものよりも大規模データ処理とか分散データ処理とかそっちに興味があって、その接点としてHadoopがあると言ったほうが適切だったりします。Hadoop自体も細かな部分は変わっていきますし、10年とかのスパンで見れば残っているか分かりませんし。
いずれにしても、こんなにわくわくしながら読んだ本は久しぶりでした。筆者および翻訳者に感謝です。ありがとうございました!
2011年7月-9月振り返り
8月頭、9月頭がちょうど忙しく、気がつけば前回の振り返りから3ヶ月経ってましたorz 特に8月後半から9月前半はプロジェクトの立ちあげ、DevQuiz、Hiveの勉強会の準備が重なり、マジで精神と時の部屋に入りたい気持ちになりました。
Keep
Problem
- 7月ぐらいの案件で、お客様の期待をコントロールするという考えなしに仕事をして、結果的に不要な残業をすることになった。
- お客様的には成果物が多くてよかったのだけれども、自社的にはコストオーバーになるし、自分自身も大変だった。
- お客様にとっても金額と成果物のバランスが合っていないのは、その瞬間はよくても、長期的には関係を維持できなくなるのでよくない事例だと思う。
- お客様的には成果物が多くてよかったのだけれども、自社的にはコストオーバーになるし、自分自身も大変だった。
- 技術メモをブログに書こうといって、ずっと書けていない。
Try
- A* アルゴリズムを理解する。
- GDDのスライドパズルはGDD 2011 DevQuizに参加しました #gdd11jp - nokunoの日記によるとA* アルゴリズムで解けるらしいので、理解する。
- Algorithms with Python / ヒューリスティック探索が分かりやすそうだったので、遡ってAlgorithms with Python / 集合, グラフ, 経路の探索まで終えた感じ。
- ちなみにスライドパズル自体は探索のやり方を知らなかったので、スライドパズルを解く手順を見つけてそれを実装した(1パネル解く毎に空白を真ん中に移動して次のパネルを解くみたいな感じ)。
近況報告
ここ1ヶ月半ほどは1週間単位のイテレーションでお客様のところにアプリケーションを持って行き、フィードバックをもらい、翌週機能追加するということを繰り返してました。たぶん、世に言うアジャイルっぽい開発をしていたのだと思います。
お客様と一緒に開発できるのはとても楽しいのですが、毎週機能追加をコミットしているのは精神的にかなりしんどかったですね。特に最初はプロジェクトの立ち上げからだったので。初めてのお客様だったので信頼関係を構築するところからでしたし。1人プロジェクトでフットワーク自体は軽かったですが、管理コストも丸かぶりなので、非常に大変でした。要件定義フェーズもなくてざっくりと見積もり時に要件が決まっていただけなので、要件をつめつつ、画面デザインをきめつつ、実際にものを作るという感じでした。画面自体は1画面しかありませんでしたが、要素技術がChromeExtension、GoogleDataAPI、JavaScript、ちょっとだけGoogleAppEngineという感じだったので、ほんと調査ばかりしていて、実現可能か不安になる時も多々ありました。
今回思ったのはJavaScriptだけで画面を作れるのだなーということですね。JQueryのプラグインが充実していることもあるのだとは思いますが、JavaScriptとGoogleDataAPI(WebAPI)を連携させることでサーバーなしでも画面が作れちゃう時代なのだと実感しました。あと、今回は shin1ogawa さんの勧めでJavaScriptをオブジェクト指向で書いてみたのですが、とても書きやすいし、可読性もよくなってびっくりしました。
色々調査メモもたまっているので、ブログで書ければなーと思ってます。
最後に、まだプロジェクトが終わったわけではないのですが、お客様には恵まれたのだろうなーと思います。最後までしっかりと進めたいと思います。
Hadoop MapReduce デザインパターン1章〜3章
Hadoop MapReduce デザインパターン ―MapReduceによる大規模テキストデータ処理
- 作者: Jimmy Lin,Chris Dyer,神林飛志,野村直之,玉川竜司
- 出版社/メーカー: オライリージャパン
- 発売日: 2011/10/01
- メディア: 大型本
- 購入: 4人 クリック: 254回
- この商品を含むブログ (16件) を見る
ずっと原書であるData-Intensive Text Processing With MapReduce (Synthesis Lectures on Human Language Technologies)を読もうとは思っていて、Pre-Production Manuscript(PDF)とかもチラ見していたのですが、Hadoop Conference Japan 2011 Fallで売っていたのでAmazonの予約をキャンセルしてその場で買いましたw
ちなみに、私のスペックを説明しておくとtry-hadoop-mapreduce-java - Hadoop MapReduceを気軽に試せるようにすることを目的としています - Google Project Hostingの作者なのでMapReduceの基本は理解しているつもりですが、仕事でMapReduceは書いたことが無いので経験値的には微妙です。あと、数学やら自然言語処理に関しては知識がないに等しいです。
1章 イントロダクション
2章 MapReduceの基礎
- 象本ことHadoop 第2版のMapReduce周りを要約したような内容です。ただ、こちらからいきなり読んでもよく分からないのではないかという気もしました。象本を読んでから再確認する感じで読んだほうがよいと思います。
3章 MapReduceアルゴリズムの設計
in-mapper combiningパターン
pairsとstripesパターン
- 複数のキーにまたがる演算を行う場合のデザインパターンという理解です。例えば、group byでsumを求めるとして、その集約キーが2つある場合の実装方法です。2つある場合にmapper側ではレコードの集約キーと値をそのままreducer側に送るのがpairsパターン。mapper側で予め第2集約キー単位に値を合計した上で、第1キーでまとめてreducerに送るのがstripesパターンになる、、、という理解です。
- ちなみに、pairsはキーと値のペアをそのままreducerに送るという意味で何となく分かるのですが、stripesはどのへんがstripesなのでしょうか。。。
- キーが単一の場合はmapperの出力のキー側にキーを入れるしか選択肢が無いわけですが、キーが2つあると第2キーをキーの側に入れるという選択肢と、値の側に入れるという選択肢が生まれるということだと思います。
- 書籍内では共起行列を例にして解説しています。詳細はHadoop MapReduce デザインパターンの3章まで読んでみた。 - watawata日記を読むのがよいと思います。共起行列の説明からサンプルコードまで載っていて素晴らしいです!
- 両者のパターンにおいて当たり前ですがトレードオフがあり、pairsとstripesの中間のsub-stripesについても紹介されています。
- ちなみに、sub-stripesのメモリの制約ってreducer側の話ですよね。本文では言及されていない気がしたので、誰か教えてくれると嬉しいです(^_^;)
order inversionパターン
- reducer側で受け取るキーを制御することで、例えば相対頻度の計算ができたりしますよという内容です。象本の結合を読んでいれば、あーそうねーみたいな内容だと思います。
セカンダリソートと結合
- 象本の結合を読んでいれば(ry
- ちなみに結合に関してはJoin Algorithms using Map/Reduce(PDF)もいいかと思います。
2-legged OAuthについて調べてみました
最近Google Apps ScriptでSitesにMLの一覧を表示するというのをやってまして、その中で2-legged OAuthが出てきたのでちゃんと調べようと思っていました。そして連休中にUsing 2-legged OAuth with the Google Tasks API for Google Apps domain administrators - Google Apps Developer Blogという記事に出会いまして、ちょっと調べてみました。
2-legged OAuth
OAuthについてはJavaでTwitterのOAuthを書いてみました - n-3104の日記で調べていたのですが、要はユーザーIDとパスワードではなくトークンを利用して認証を行う仕組みです。そのOAuthにも2-legged OAuth(以下2LO)と3-legged OAuth(以下3LO)の2種類あって、Twitterの場合は3LOでした。3LOの場合はProvider、Consumer、Userの3者が登場し、ConsumerがProviderにアクセスする際にUserに認可してもらいアクセストークンをもらいます。一方、2LOの場合はUserからの認可というフローが不要になりアクセストークンも利用しません。ProviderはConsumerから発行されるConsumerKeyとConsumerSecretのみでConsumerにアクセスします。
実際に2LOによる実装という意味では、まずHTTPリクエストの中身については2-legged OAuthによるAPIアクセス mixi Developer Center (ミクシィ デベロッパーセンター)が、ソースコードという意味ではpythonで署名付きリクエストを送る(2-legged OAuth) « taichino.comが参考になります。
署名アルゴリズム
2LOについて調べていたら、OAuthの仕様について 〜署名?それっておいしいの?〜 (Yahoo! JAPAN Tech Blog)というページを見つけました。あまり意識していなかったのですが、OAuthで利用する署名アルゴリズムは3種類あるそうで、HMAC-SHA1の場合はService Provider(以後SP)側でConsumerkeyとSecret(秘密鍵)のペアをConsumerし、RSA-SHA1の場合はConsumer側で公開鍵と秘密鍵を生成し、事前に公開鍵をSPに登録しておくらしいです。
Appsの管理者向けコントロールパネルには署名をアップロードするUIがあったのですが、RSA用だと分かって納得しました。実際、OAuth: Managing the OAuth key and secret - Google Apps HelpにもRSA用と書いてありました。
Appsにおける2LO
Google Appsで2LOを行う場合、ドメインに対する2LOという扱いになりますOAuth for Google Apps domains。ドメイン単位でOAuthを利用して認証するのは良いとして、実際にリクエストを送信したユーザーを特定する必要があります。例えばGoogle Documents List APIの認証にOAuthを利用してドキュメントを新規に作成しようとし場合、ドメイン単位の認証では誰のドキュメントと作成しようとしたのか分からなくなってしまいます。そのため、Appsではxoauth_requestor_idというパラメーターにメールアドレスをつけることで、どのユーザーとしてAPIをコールしたのか指定できるようにしているようです。詳細はExample: Accessing a Google Data API feedを参照してください。最初に出てきたUsing 2-legged OAuth with Google Tasks API for Google Apps domain administratorsはこのGoogle Tasks API版の記事で、サンプルソースにおいてxoauth_requestor_idを設定していることが分かります。
きんちゃん、ありがとう
主に家庭的な理由で、色々と疲れがたまっていたのですが、 @quindim の送別会に行くことで、とても元気をもらいました。特にLTを書いていて、かなり復活しました。ほんとありがとう、きんちゃん。
これまた家庭的な理由で、圧倒的に時間がなかったりするのですが、その中でもいろいろやっていきたいなーと思うようになりました。時間がない以上、取捨選択と単位時間あたりの生産性をどう向上するかがポイントになるのは明白なのですが、あんまりそういうことばっかり考えずに、やりたいことをやりたいときにやるのもありかと思いました。その時間がないという矛盾もあるのですが、矛盾とか気にせず、とにかく前に進めばいいかと思います。取捨選択と単位時間あたりの生産性向上という方向性でやった結果、疲れがたまるという結果になったので。
2011年7月振り返り
6月はいつもよりつぶやいていた気がします。2011-06のつぶやき - n-3104のつぶやき
Problem
- 休もうと意識していた割に休んでいない気がするし、家族にもエネルギーを割けていない気がする。
- とはいえ、5月よりは改善している気はする。
- 時間的な問題ではなく、意識的な部分で足りていない気がする。
- Asakusaの調査を出来ていない。
- ブログを書いていない。
- 英語の多読が止まっている。
Try
- 定期購読している雑誌にかける時間を減らす。
- もっとざっくり読む。丁寧に読み過ぎ。
- 多読は1日5分でいいから再開する。続ける。
- 数学の勉強