DEIM 2015 にて講演，第77会情報処理学会全国大会にて座長をします

2015年3月2日 - 3月4日，福島県で開催される，DEIM 2015 の特別セッション「ライジングスター2015」という企画にて招待講演をさせて頂くことになりました．タイトルは「Inside Apache Hadoop: オープンソース開発の様子と研究者としての関わり方」で，Apache Hadoop のコミュニティがどうなっているのか？オープンソース開発と研究開発の関わりはどのようにあるべきか？という話をしようかなと思っています．なお，同じセッションでご講演される方々が強すぎて恐縮ですが，がんばります．

また，2015年3月17日 - 3月19日，京都大学で開催される第77回情報処理学会のクラウドコンピューティングセッションで座長を務めさせて頂くことになりました．学生の皆様と議論させて頂ければ幸いです．宜しくお願いします．

2014年のまとめ

2014年のまとめ．

• CROSS 2014 に個人で分散処理セッションでパネルディスカッション参加．@draftcode さんに会えた(CROSS のとき質問してもらったのだが，後日なべ会で再会した)．
• 筑波大学にて特別講義．
• 日本OSS奨励賞受賞．
• DEIM に初参加(DB 学会自体が初参加)．
• Hadoop 2 について日経SYSTEMS に寄稿(現在 ITPro から閲覧可能)．
• 情報処理学会 OS研究会の運営委員に就任．
• SWOPP 2014 に座長として参加．
• Hadoop Summit 2014，Hadoop World・Strata Conference 2014 に参加．ほとんどの Hadoop 開発者には覚えられてて良かった．オフラインであーだこーだ話すのは楽しい．
• ビッグデータ処理基盤勉強会に参加．
• Apache Hadoop の Committer 就任．

来年も宜しくお願いします．

Coordination Service(ZooKeeper，etcd ，consul) の比較

概要

最近，consul，etcd，ZooKeeper といった，いわゆる Coordination Service(この名前は ZooKeeper の論文から拝借した)の実装が頻繁に行われている．本記事では，開発が盛んな背景を踏まえた上で，オープンソース実装の Coordination Service の比較を行う．

Chubby から現在まで

Paxos が Google の手によって Chubby という形で実用化された後，故障検出+分散合意アルゴリズムを用いた高可用KVSという組み合わせによる Coordination Service のオープンソース実装がいくつが出てきた．そのはしりが ZooKeeper である．ZooKeeper は Hadoop ファミリではデファクトスタンダードの Coordination Service であり，Hadoop を初めとして HBase，Mesos，Flume などのプロジェクトや，多くの企業で実際に使われている．その後，しばらく新しい Coordination Service のオープンソース実装はでてきていなかった．それが，2013年に Raft という分散合意アルゴリズムが公開されて以降，一気に情勢が変わった．consul や etcd などが公開されたのである．Raft は，ざっくばらんに言うと実装が簡単な Paxos である．実装がどれくらい容易であるかは，実装数を見れば明らかであろう．

ZooKeeper と etcd と consul

複数の実装が出てくることで競争が発生しソフトウェアが成熟してくれるのは喜ばしいことである．しかしながら，利用する側から見ると，どういった観点で何を利用したら良いのかが自明ではない．そこで本節では，分散処理基盤の開発者という視点で比較を行う．

ZooKeeper は，以下の特徴を持つ Coordination Service である．まず，Paxos ベースの分散合意アルゴリズムである Zab  を利用しており，サーバ側の台数の増加に対し，読み込みがスケールする形で設計されている．また，Chubby の持っているファイルシステムのような API を拡張し，その API の上で様々な分散コンポーネントが構成可能である．特に，ephemeral node(クライアントが故障した際に消滅するznode) や sequential node(連番生成機能を行うためのznode)，watcher(特定のznodeおよびその子のznodeに対する変更を通知する仕組み)，multi(複数のznodeをアトミックに操作する仕組み) を用いることで幅広いアプリケーションを構築可能となっている．サーバ側で起きた全てのイベント(ephemeral node の消滅，増加およびその他 znode への書き込み)はどのクライアントから見て同じ順番で通知されることが保証されているため，妙なコーナーケースについて考える必要がない．
Server-Client は jute というシリアライゼーション形式と TCP コネクションに基づいた RPC で行われているため，実装コストが他の実装に比べて高いという欠点がある(この問題を解消するため，4.0.0 リリースに向けて protobuf などで置き換えようというチケットがある)．

etcd， consul は，Paxos ベースの分散合意アルゴリズムである Raft を利用しており，台数を増やしても書き込みも読み込みもスケールしない．また，ZooKeeper の API を踏襲しつつも，クライアントの実装コストを減らすために RESTful API が提供されている．これにより，クライアントの実装コストを大幅に削減できている．etcd， consul は両方とも，ephemeral node がないので，定期的にポーリングしてメンバシップの変更があったかどうかを自分で検出する必要がある(etcd も consul も，ephemeral node は fat client の原因になるので入れたくないと述べている．etcd のgithub issue とconsul のHP参照．)．このため，分散ロックなどの複雑な機能をバグなく作成する用途では，ZooKeeper の方が優れているように思う．もしくは，etcd，consul 版の Curator (ZooKeeper で使いたくなるような機能をまとめたライブラリ．当初は Netflix が作成し現在は Apache プロジェクト化) が出てきて，利用されるようになる可能性はある．

これに加え，consul にはいくつか大きな特徴がある．死活監視機能と DNS インタフェースである．まず死活監視機能だが，gossip protocol によるクライアントの死活監視機能とRaftベースの高可用KVSにregistrationすることによる死活監視機能の2つがあるという点である．gossip protocol によるクライアントの死活監視は一貫性が弱く，クライアント数の増加に対してスケーラブルである．この情報にアクセスするには， agent endpoint と利用する．一方で，高可用KVSによる死活監視機能は一貫性が強く，クライアントの増加に対しては gossip protocol による死活監視と比較してスケーラブルではない．この情報にアクセスするには catalog endpoint にアクセスをする．consul では，この2つを使い分けることで，強い一貫性を必要とする分散システムの構築(分散ロックなど)と，スケーラビリティを必要とする分散システムの構築(Web サービスのデプロイなど)の両方に対応しようとしているようにみえる．DNS インタフェースについては，register したノードに対して dig や nslookup でアクセスできるというものである．Chubby の論文の中でも，DNSライクに利用することについて触れられているので，この使い方は Coordination Service としては王道なように思える．

まとめ

本記事では，Chubby から ZooKeeper，そして Raft ベースの Coordination Service の流れをまとめて説明した上で，機能の比較を行った．ZooKeeper，etcd/consul の大きな違いは API(RESTful API が提供されているか否か)と ephemeral node の有無である．さらに，consul には，従来の Coordination Service の機能に加え，gossip protocol を用いた弱い一貫性のクライアント死活監視と，DNS インタフェースが用意されている．これらの特性の違いから， Coordination Service はAPIやスケーラビリティによって使い分けることが必要であるため，用途をよく理解した上でどれか1つを選択する必要がある．

知っている情報を，ソースを明らかにした上で述べたつもりですが，もし誤っている箇所などありましたら，ご指摘お願いします．

日経 SYSTEMS 4月号のテクノロジー最前線と技術評論社改訂版Linux エンジニア養成読本に寄稿しました

2014年3月26日発売の日経 SYSTEMS 4月号と，2014年3月18日技術評論社 改訂新版 Linux エンジニア養成読本に寄稿をしました．以下，それぞれの寄稿の概要について述べます．

日経 SYSTEM 2014年4月号に寄稿した Hadoop の記事について

テクノロジー最前線 分散処理フレームワーク "Hadoop 2" では，MapReduce の経緯と技術範囲を振り返った後で，Hadoop 1系と Hadoop 2系の違いについて述べています．共著のNTT DATA の皆様方と，Hadoop・MapReduce をご存知ない方でも読めるように推敲を重ねたつもりですので，Hadoop を知らない方はチェックして頂ければと思います．表紙に本寄稿の内容が掲載されれているのを見て，うれしくなったのは秘密です(笑)

技術評論社 改訂新版 Linux エンジニア養成読本 について

この本は，3年前に技術評論社から出版された Linux エンジニア養成読本の改訂版で 2014年3月18日に出版されました．過去に掲載された Software Design のLinux関連の記事を集めた総集編です．2009年12月号のSoftware Designの特集 に寄稿したLinux カーネルのメモリ管理の記事が再掲載されました．Linux に関する基本的な事項が網羅的に掲載されている本だと思いますので，春だし Linux を学ぼう！って方には丁度良いのではないかなと思います．

【改訂新版】Linuxエンジニア養成読本 [クラウド時代も、システムの基礎と基盤はLinux! ] (Software Design plus)

posted with amazlet at 14.03.24

技術評論社
売り上げランキング: 7,754

Amazon.co.jpで詳細を見る

まとめ

日経SYSTEMS4月号のテクノロジー最前線と改訂版Linuxエンジニア養成読本のLinuxカーネルの特集に寄稿をしました．いずれも2014年3月に発売されたもので，書店で見かける機会もあると思いますので，是非手に取ってみてください．ちょっとでも，みなさまの技術に関する疑問が解消できたら幸いです．宜しくお願い致します．

日本 OSS 奨励賞を受賞しました

日本OSS推進フォーラムより，第9回日本 OSS 奨励賞を頂きました．ありがとうございます．受賞理由は以下の通りです:

Hadoop開発コミュニティにおいて、リソース制御機構YARNの高信頼性を実現する新機能の開発等に貢献するとともに、品質強化に向けた取り組みにも貢献している。若手研究者として論文をまとめる一方で、その知見をもとに、積極的にOSS開発に参画・継続している。

受賞者の中には見慣れた名前の方もおり，大変恐縮です．特に @tagomoris 先生，おめでとうございます！同時受賞できるとはびっくりしました．

ここ1年の活動内容

良い機会なので，ここ1年の活動内容について振り返っておきたいと思います．

• Apache Hadoop プロジェクトに合計で100件以上のパッチを投稿．
• マージ件数は14件．
• 恐らく日本人としての投稿・マージ LOC 数はトップ．
• 筑波大学川島先生のお誘いで "情報システム特別講義" の非常勤講師を担当．
• 資料まとめはこちら．
• MapReduce 最適化技術の実装方法に関する論文で，情報処理学会より2013年度コンピュータサイエンス領域賞を受賞．
• CROSS 2014 にて 分散システムCROSS に登壇．
• Hadoop 徹底入門第二版 YARN の章を執筆．

Hadoop徹底入門 第2版 オープンソース分散処理環境の構築

posted with amazlet at 14.02.20

太田 一樹 岩崎 正剛 猿田 浩輔 下垣 徹 藤井 達朗 山下 真一
翔泳社
売り上げランキング: 13,773

Amazon.co.jpで詳細を見る

まだコミッタとして活動できている訳では無く，一貢献者として今回賞を頂けたのは，タイミング・運・環境が大きいかなと思っています．それでも，OSS 開発者と研究者という2つの側面で評価して頂いたのは，私が目指すところと合致しているので，大変うれしく思っております．

今後

奨励賞とのことで，つまるところ周りから "早くコミッタになるんだ！"というメッセージを頂いたのだと受け取りました．それを実現出来るよう．今年は最短距離を走り抜けたいと考えています．目下は Hadoop コミッタを目指します．実現のため，今年中に累積マージ件数を50件(あと35件！)を目指します．

コミッタになれた際には，魅力的な新機能はもちろん，ドキュメント・ログ・メトリックスといった運用上で必要な機能の開発速度を上げていきたいです．また，技術的に色々と挑戦しやすい分野ではあるので，オープンソース活動だけでなく，研究の方もがんばっていきたいです．

活動を通じて得た知識は，雑誌の記事や勉強会で共有し，Hadoop というプロダクトに還元して行けたらなと考えています．

謝辞

受賞に当たりましては，普段から議論頂いている方，職場の方，ご推薦頂いた方，友人に大変感謝しております．

特に，@shiumachi さんはコミュニティ活動をはじめた初期の段階で，Hadoop Hakathon を開催し，Hadoop コミュニティに疎い私に様々な情報を共有してくださいました．あの会がなかったらこのような賞を受賞できなかったでしょう．@tamtam180 さん，@tagomoris さん，@repeatedly は Hive T シャツを開発し，私のコミュニティ活動のモチベーションを大きく上げてくれました．

英語の文章ではないので詳細は省きますが，Hadoop コミュニティの皆様には，いつも容赦ないレビュー・コメントして頂いており，大変勉強になっています．

@tagomoris さん， @frsyuki さん，@repeatedly，@choplin さん，@nobu_k さん@okachimachiorz さん，@monizuka さん，@muga_nishizawa さん，@taroleo さん，@maropu さん，@kuenishi さん，@komamitsu_tw さん，@nobu_k さん，@hayamiz さん，@Guutara さん，@myui さん， @h_kaw さんにはいつも勉強会，議論におつきあい頂いており，大変感謝しております．今後とも宜しくお願い致します．改めて思いましたが，議論にお付き合い頂いている面子が豪華で恐縮です．

あと，色々迷ったりしたときに，"がんばれー" と，応援してくれた友人には大変感謝しています．ありがとうございます．

ここに書けなかった人，特に職場の方にはものすごく多種多様な迷惑をお掛けしていますが，嫌な顔せずサポートして頂いてものすごく助かっております．ありがとうございます．あと，いつもりんごありがとうございます，美味しいです．

最後に，私の生活力が低いことに起因し，今後も周りの方々には色々とご迷惑をおかけすることも多数あるかと思いますが，これからも宜しくお願い致します．

RCFile，Parquet，ORCFile

この2ヶ月で，Cloudera/Twitter，Hortonworks からそれぞれ別の列指向ファイルフォーマットが公開されました．Parquet と ORCFile です．

この記事では，まず RCFile の復習をして，その後 Parquet と ORCFile それぞれの共通点と違いをおおまかに見ていこうと思います．コードレベルの詳細な違いについては，次回以降で見ていきます．

RCFile の復習

RCFile は　Record Columnar File の略で，Hive から利用できるストレージフォーマットです．特に，HDFS や S3 といった分散ストレージ上でパフォーマンスがでるように設計されています．

HDFS/S3 といったストレージでは，基本的にデータを計算機間で同じ負荷になるようにデータを分散配置します．このため，従来の列指向ストレージフォーマットのように適当に列毎にデータを分割してしまうと，1レコードにアクセスする度に，異なる計算機にアクセスしてデータを読み込む必要があります．これは，Hadoop が Vertica などの分散DB異なり，スキーマを持っているデータを処理するとは限らないために発生する問題です(スキーマがある場合は，ロード時にデータ配置の初期化ができる)．

RCFile では，複数の Record をまとめて固定長の row group として扱い，かつそれを列毎に並び替えます．row group の HDFS/S3のブロックサイズは，HDFSやS3のブロックサイズより小さいです．このように設定することで，ブロックが複数計算機に分割配置されることを抑えつつ，

1. オブジェクトのデシリアライズ・解凍を lazy に行うことができる．

2. 圧縮を効きやすくする．

という利点を得ることができます．RCFile の論文を見ると，この辺りの詳細を知ることができます．

ORCFile -The successor of RCFile-

次に，ORCFile の特徴について述べます．ORCFile は，RCFile の苦手な操作を克服するためにメタデータを追加したファイルフォーマットです．

ORCFile の提案がされた JIRA 上の資料によると，以下の違いがあるようです:

* RCFile では列の中で blob として保存されていたため，型ごとに圧縮をしたり，列の読み飛ばし(SQL 内で where を使ったりした場合)ができなかった．ORCFile ではメタ情報に 型と index を追加することにより，列ごとの圧縮や読み飛ばしができるようになった．

* RCFile では row group の先頭を見つけ出すためにフルスキャンが必要であったが，ORCFile ではメタデータの追加によりスキャンしなくても分割ができる．

RCFile は，row groups という単位で row を分割していたのに対して，ORCFile では row を stripes という単位で分割します．stripes ごとに index と footer がついており，そこにメタデータが入っています．また，1つの ORFile ごとに 1つの Postscript  というメタデータが保持されています．

index には各列のMin/Maxの値が入っており，Min/Max といった集計処理を効率的に処理するためのメタデータと，データの読み飛ばしを効率的に行うための10000レコードごとのポインタが入っています．

footer には stripes の一覧と，型と行番号，Count， min， max， sum といった集計処理用を効率的に処理するための一時結果が入っています(index と footer に同じデータが入っているのは，CPU 効率を上げるため?)．2014/4/23 追記: @maropu さんのご指摘で，index には stripe ごとの， footer はファイル全体の Min，Max etc. の情報が入っているとのことでした．これにより，特定の列の数値の合計を footer 全体の scan を避けて取得することができたりします．

postscript には，圧縮パラメータと footer の圧縮サイズが含まれています．

ORCFile は，2013/3/18 時点で，既に Hive にマージされています．また，ORCFile を Hive から便利に，効率良く使えるようにするための開発が Hive コミュニティ内で行われている最中です．

Parquet -Dremel's nested columnar storage -

次に，Parquet の特徴について述べます．

Parquet は，Dremel の Columnar Storage clone の列指向フォーマットです．Dremel の論文の中で述べられているネスト構造の列指向ストレージが実装されているのが特徴です．

Parquet を利用することにより，以下の利点が発生します:

1. JSON/XMLと比較して，ネスト構造のデータを非常に効率良く保存できる．これは，Dremel の論文の中で述べられている definition/repetition levels を用いたストレージフォーマットの効果による．

2. Null を多く含むような粗なデータについて，高い圧縮率を達成できる．これは Dremel の論文の中で述べられている Null を skip する最適化による．

encoding/decoding の仕方については，Dremel の論文と Parquet のドキュメント  が参考になります．

Parquet では，シリアライゼーションフォーマットとして Thrift を採用しています．なので，

https://github.com/Parquet/parquet-format/blob/master/src/thrift/parquet.thrift

を読むことで内容を理解できます．また，ドキュメント内にストレージフォーマットのイメージ画像があるので，これを見ると理解しやすいです．

RCFile は，row groups という単位でファイル内の row を分割していたのに対して，Parquet では row group という分け方を明示的にはしません．その代わりに列を Column Chunk という単位で分割して，保存します．

なので，厳密には列をまたがった read は計算機をまたぐ可能性がありますが，Column Chunk の大きさを HDFS/S3 のサイズより十分に小さな値に設定することで，ある程度通信は抑えられます(ファイル内で列同士はすべてとなりあっているため，Column chunk のサイズを調整することで間接的に row group を指定できる)．

Column Chunk は Page という単位で構成されています．デフォルトでは，1 Page は 8KB のようです．

parquet-format 自体は単なるファイル形式の定義なので，それを読み込み，encoding/decoding する部分が必要となります．

この部分は， parquet-mr として公開されています．parquet-mr のドキュメントを見ると，主要な処理系(Pig/hadoop MR)のサポートが既に公開されているようです，

また，シリアライズする際の型ですが，公式ドキュメントによると以下の型がサポートされているようです(なぜ INT96という型があるんだろう…?)．

BOOLEAN: 1 bit boolean

INT32: 32 bit signed ints

INT64: 64 bit signed ints

INT96: 96 bit signed ints

FLOAT: IEEE 32-bit floating point values

DOUBLE: IEEE 64-bit floating point values

BYTE_ARRAY: arbitrarily long byte arrays.

Impala と同時に公開された Apache Trevni との差分が気になる人が居ると思います(自分が気になった)．Cloudera の記事 によると，Apache Trevni との差分はAvro への依存を取り除き，Thrift を用いているという点です．

つまり，定義さえすれば，protobuf/avro/msgpack でも実装可能です．ただし，msgpack に関していえば， int 96 がネイティブの型として存在しないので，raw type を拡張するなどする必要がありそうです．

Parquet，ORCFile 間の共通点

Parquet と ORCFile は共に列指向のファイルフォーマットであり，読み込み時に不必要な列(カラム)のオブジェクト生成コストを飛ばすことで，raw file と比較してCPU コストを削減することができます．また，似たデータ・同じ型のデータが連続するため，圧縮が効きやすくなり，IO コストの削減が見込めます．

両者は，ともに HDFS や S3 といった分散ストレージ上のファイルとして利用可能です．これらのストレージの上で，従来の列指向DBのように列ごとにファイルをわけて実装を行うと，計算機をまたがって通信してしまう可能性がありますが，Parquet・ORCFile 共に通信コストをなるべく抑えるように1つのファイル内で row groups のように行ごとにデータを分割しています．

まとめ

RCFile の復習と，Parquet・ORCFileの概要について触れました．両フォーマットとも，分散ストレージ上でのアクセスを意識した効率の高い列指向のストレージフォーマットです．

次回はコードを読んでいきたいと思います．この文章は，WIP の文章などを基に構成しました．なるべく情報ソースを明らかにして構成したつもりですが，誤っている箇所などありましたら，是非ご指摘ください．

Node-level aggregation の概要

本投稿は Hadoop Advent Calendar 25日目(#hadoopAC12jp)です．現在投稿中のパッチである MAPREDUCE-4502 の内容の日本語資料がないのに気づいたので，その説明をします．

現在取り組み中のパッチの内容

Node-level aggregation は，MapTask 毎に部分集約(Combine処理)を行うための機能です．従来の Combine 処理よりも広い範囲で適用できるため，より高速な処理が可能となります．

設計

MRAppMaster が各ノードを調停して，MapTask にNode-level aggregation を開始するように指示します．Combine 処理は重いので，処理によっては Combine 処理によるデータの圧縮効果よりもオーバヘッドの方が大きくなってしまう場合があります．そこで，現在の設計では，しきい値を超えたら Node-level aggregation を開始するようにしています．また，耐故障性も担保できるように設計しています．

改造箇所

1. Mapper
2. Reducer
2. MRAppMaster(JobTracker)
3. Mapper-MRAppMaster間の Umbilical Protocol

だいたい全部ですね^^;

ユーザからどう見えるか

設計上はフラグで本機能をON/OFF切り替えできるようになっています．最終的には，

conf.enableLocalAggregation();

としたら本機能が有効になるようにする予定です．

ベンチマーク

現在とっている最中なので，乞うご期待^^;

終わりに

現在 Hadoop の標準機能に入れようと取り組んでいる最中の Node-level Aggregation について書きました．

本機能を実装する上で，Hadooper の皆様の声をぜひ聞いておきたいというところが本音です．もし何か要望がありましたら，気軽に @oza_x86 までお気軽にご連絡ください．よろしくお願いします．