Indeed のようなデータドリブンなアプローチをとる組織には、優れたツールが必要だ。

クエリーの並列実行を管理するために、私たちは Imhotep を開発した。これは、インタラクティブなデータ分析のプラットフォームで、昨年リリースされたものである。

Imhotep におけるメモリ効率とパフォーマンスのバランスを取るために、私たちはベクトル化された可変バイト ( variable-byte を指す。 以下、VByte とする。) を復号化するテクニックを開発した。

差分符号化を使用した VByte

ソートされた整数のシークエンスを圧縮するのに、多くのアプリケーションが VByte や差分符号化を使用する。逆索引で最も一般的な圧縮方法は、この種類の符号化を使用している。このアプローチでは、整数自体の代わりに整数間の逐次差分を符号化してくれる。これは、小さな整数には少ないバイトで済むかわりに、大きい整数ではより多くのバイトを食ってしまう。

従来の VByte のデコーダは一度に１バイトだけを検証するので、スループットは制約される。また、各 input byte は１つのブランチを必要とするので、誤って予測されたブランチへ移動してしまう。

ベクトル化したVByteの復号化

自社開発したマスク済みの VByte のデコーダはもっと大きい塊の 12 バイトのインプットデータを一度に処理する。これは一度に1バイトを復号化するよりもずっと速い。 Indeed にとってこれは重要である。なぜなら Imhotep は CPU 時間の 40％ を VByte の整数のデコードに費やしているからだ。このアプローチについては、昨年行ったテックトーク Large Scale Analytics and Machine Learning at Indeed でも話している。

Jeff Plaisance ジェフ・プレザンス ( Indeed ) 、 Nathan Kurz ネイサン・カーツ ( Verse Communications ) 、 Daniel Lemire ダニエル・レミア ( LICEF  ケベック大学 ) が、 Vectorized VByte Decoding （ベクトル化された VByte の復号化）という論文でマスク済み VByte のデコーダについて詳細に述べている。論文の概要を以下に引用する。

VByte 圧縮の遍在するテクニックについて考察する。これは、各整数を可変長のバイトのシークエンスとして、表すものとする。各バイトの下位７ビットは整数の部分を符号化し、各バイトの上位ビットは、継続フラグとして、保持される。
このフラグは、最後部分を除き全てのバイトに対し、１と設定される。そして各整数の復号は、上位ビット ０ を持つバイトが出てきたら完了する。
VByte の復号は、パフォーマンスのボトルネックになり得る。特に符号化された整数の予期せぬ長さが、しばしブランチの誤った予測を引き起こす。SIMD のベクトル命令を使用して VByte を加速させようとした先の試みは、失望する結果となった。パフォーマンスを重視するコードについて、Google などの検索エンジンを、より複雑だが高速にデコードする形式を使用するように促しただけだったからだ。
我々のデコーダ (MASKED VBYTE) は、通常のスカラーの VByte デコーダよりも、 2 倍から ４ 倍速く、速さの面でも再び競合できるものにしている。

Vectorized VByte Decoding は 2015 年の 6 月 2 日から 3 日に行われるウェブアルゴリズムの国際シンポジウム International Symposium on Web Algorithms  (iSWAG) に受理された。 iSWAG は、ウェブアルゴリズムに関連するあらゆるトピックについて、学術分野および業界の研究を推進している。

大規模なインタラクティブツール

Imhotep についての詳細は、以下のテックトークやスライドからも調べることができる。

Scaling Decision Trees

Large-Scale Analytics with Imhotep

Github でも Imhotep のソースやドキュメンテーションが閲覧可能である。

今回の記事では、オープンソースで利用可能な util-mmapを取り上げていく。 util-mmap は Java のメモリマッピング・ライブラリで、大きなファイルにアクセスするのに有効なメカニズムを提供する。 Indeed の分析用プラットフォーム Imhotep ( 2014年にリリース ) は、 これをデータアクセスの管理に使用している。

メモリマッピングを使用する理由

Indeed のバックエンドサービスはLSM trees や Lucene のインデックスのような大きなデータセットを扱っている。util-mmap のライブラリは、そういった大きなファイルへの安全なメモリマッピングを提供している。 また、これは JDK 内の MappedByteBuffer の既知の制約を克服している。メモリマッピングとは、ファイルの一部を、仮想メモリのセグメントに移すプロセスを指す。 メモリマッピングをすることで、アプリケーションはマップされた部分をメインメモリのように処理できるのだ。 Indeed では、大きなファイルを持つ、レイテンシに影響されやすい本番のアプリケーションでメモリマッピングを使用している。そうすることで、 I/O 操作にかかるコストをおさえられるからだ。

MappedByteBuffer の制約

JDK は、メモリマッピングをするために java.nio パッケージ内にある MappedByteBuffer を提供している。 このライブラリには三つ、主要な問題がある。

安全にアンマップできない MappedByteBuffer を使用したアンマッピングをリクエストする唯一の方法は、System.gc()を呼び出すことだ。 このアプローチはアンマッピングを保証するものではなく、 既知のバグである。 メモリにマップされたファイルは、削除する前にまずアンマップする必要がある。
このバグは、サイズが大きく、頻繁に更新されるファイルをマップすると、ディスクの容量に問題を発生させてしまう。

サイズが 2GB を超えるファイルをマップできない MappedByteBufferは全インデックスにint を使用している。つまり 2GB を超えるファイルを管理するには複数のバッファを使用する必要があるのだ。 複数のバッファを管理するのは煩雑で、エラーが発生しやすいコードにつながる。

スレッドセーフではない ByteBuffer は内部ステータスを保持して、位置をトラッキングおよび制限している。 get() などの関連したメソッド使用を読み込むのには、 duplicate() 経由でスレッドにつきユニークバッファを一つ必要とする。

例:

public class ByteBufferThreadLocal extends ThreadLocal<ByteBuffer>
{
    private ByteBuffer src;
    public ByteBufferThreadLocal(ByteBuffer src)
    {
        src = src;
    }

    @Override
    protected synchronized ByteBuffer initialValue()
    {
        return src.duplicate();
    }
}

util-mmapを使用したメモリマッピング

util-mmap はこれらの課題すべてに対応している。

• アンマッピングを実装することで、使用していないファイルをすぐに削除可能。
• long ポインタを使用するので 2GB より大きなファイルもメモリマッピングが可能。
• AtomicSharedReference を使用して、複数のスレッドから安全でシンプルなアクセスが可能。

例: 大きなlong[] 配列のメモリマッピング

バイナリファイルの作成に Guava のリトルエンディアン・データ出力ストリーム を使用:

try (LittleEndianDataOutputStream out =
        new LittleEndianDataOutputStream(new FileOutputStream(filePath))) {
    for (long value : contents) {
        out.writeLong(value);
    }
}

このファイルをメモリマッピングするために  MMapBuffer を使用:

final MMapBuffer buffer = new MMapBuffer(
       filePath,
       FileChannel.MapMode.READ_ONLY,
       ByteOrder.LITTLE_ENDIAN);
final LongArray longArray =
    buffer.memory().longArray(0, buffer.memory().length() / 8);

Java のシリアライゼーションを使用しない理由とは? Java は、 ビッグエンディアン方式でデータを管理している。 Indeed の本番システムは、リトルエンディアンの Intel プロセッサで実行されている。 また、長い配列の実際のデータは、ファイル内でオブジェクットヘッダの後の 17 バイトから開始する。 ネイティブ Java のシリアライズされた配列をきちんとメモリマッピングするためには、上記に述べたオフセットを正しく管理するためのコードを書く必要が出てくる。 バイトをひっくり返さなくてはならなくなるし、その作業はコストがかかる。 リトルエンディアンでデータを書き込むと、よりシンプルなメモリマッピングのコードがもたらされる。

スレッドセーフ

複数のスレッドから安全なアクセスをするためには、 AtomicSharedReference を使用する。このクラスはメモリにマップされたファイルを使用する Java オブジェクトをラップしている。
例:

final AtomicSharedReference<LongArray> objRef =
    AtomicSharedReference.create(longArray);

変数 objRef は、内部にある SharedReference、つまり 参照カウントをもつオブジェクトに対する可変の参照である。
配列を使用する際には getCopy() を呼び出し、参照を閉じる必要がある。

try(final SharedReference<LongArray> myData = objRef.getCopy())  {
    LongArray obj = myData.get();
    // … do something …
}

SharedReference は参照のトラッキングをし、どのファイルも使用されていない時に、アンマップを行う。

リロード

setQuietly のメソッドを使用し、より新しいファイルのコピーと置換する。

final MyObject newMyObj = reloadMyObjectFromDisk();
objRef.setQuietly(newMyObj);

終了

アプリケーションのシャットダウンの際には closeQuietly を使用し、ファイルをアンマップする。

objRef.closeQuietly();

util-mmapを使ってみよう

Indeed では、複数のプロダクションサービスで util-mmap を使用している。
数分ごとに更新される最大 15GB のファイルにアクセスするためである。
読者の皆さんの中で、大きなファイルをメモリマッピングする必要がある方は、 GitHub のサイトから、util-mmap を是非試してみて欲しい。

プロコンと、音楽とアートのフェスとゲームを足したら？

そもそも一緒になんてできるの？

2014年11月にリクルートとIndeed　東京オフィス共催のCODE FESTIVAL2014が開催。2日間に渡り200名の学生プログラマーが東京に集結した。

フェス中は5種類のプロコン問題の他、プロコン以外の楽しいコンテンツなども用意された。また、最初のプロコン問題の後、参加者はその問題へ個人指導なども受けられるなど、普通のプロコンとは一線を画したものとなった。

200名のプログラマーが一堂に会した様子は…?

プロコン史上初めての試み

才能あるプログラマーたちが、自身のプログラミングとプロコンへの愛を通じて、集い、切磋琢磨し、楽しみ、仲間を作り、そして新しい事を学ぶことができる―主催者たちは、彼らにそんな環境を与えたのだ。

通常、プロコンに出場できるのは少数の上位選手に限られる。基準に満たない選手のモチベーションがあがらない事もあるだろう。

イベントのプロジェクトリーダーである松尾彩佳は、この伝統から自由になることを決めた。

フェスの形を取ることで、より多くの参加者がコンテンツを楽しめるようになったのだ。

もう一つ、このフェスの新しい試みは、松尾のチームメンバー。 Indeed 東京オフィスに2015年4月に新卒入社予定の16名だ。　彼らは問題のアイデアを出し、イベント運営を手伝い、盛り上げ役を務めた。
Indeed 東京オフィスに2015年4月に新卒入社予定の16名だ。　彼らは問題のアイデアを出し、イベント運営を手伝い、盛り上げ役を務めた。

経験を活かす

Indeedとリクルートは2013年秋、12月、そして2014年2月にもプロコンを開催している（詳細はこちら）。これらイベントは、どういう種類の問題を今後どう展開するか等の有意義な課題を残し、2014年11月のフェスのベースとなっている。CODE FESTIVAL2014も大成功を収めたので、既に次のイベントの計画も練られているとか。さらに多くの選手参加に繋がるか？

コーディング・チャレンジ

フェス中は、全部で5種類のプロコンが開催。問題のうちの2問である本選と2日目の朝に行われたあさプロ（朝からプロコン）が、一般的なプロコンとも言えたが、後の3問は一風変わったものとなった。

本選

200名の全参加者は、3時間以内に10問（デバッグを含む）解答に挑戦。

本選の競技中の参加者

最短時間で一番多くの問題を解いた参加者が優勝。本選トップ5はこの後、エキシビションに進むことに。

トップ5の入賞者と、Indeedのエンジニアリング部門上級副社長（SVP）　ダグ・グレイ

優勝者は294,409円の賞金を獲得。素数みたいな額である。

去年のコーディング・デュエル東京大会の賞金は、確かに素数だった。今年は皆を悩ませるため、主催者たちは強擬素数を賞金額に選んだ。

競技と強擬がかかっている。　実に賢い。

上位20位までの賞金額はこちらから。

エキシビションマッチ

Day 1の夕方、本選トップ5の決勝戦進出者はエキシビションマッチのために用意された別室に移動した。

エキシビション戦最中に参加者を撮影

プライバシーがあるとは言い難い部屋だが、5名の各PCのライブ動画は、本会場にストリーミングされた。これにより、問題を取り組む参加者の状況を、全員が見守ることとなった。音声解説も、さらにこれを盛り上げた。

エキシビションの観戦者

挑戦者は、別室で一挙一動を見られていることに気づいてたかって？

もちろん！観客がいることで、とにかく競技は活気に満ちたものとなった。

あさプロ（朝からプロコン）

Day 2の朝にも、全参加者200名はプロコンに参加。変化を出すため、参加者はスキルとレベルに応じて3グループに分けられ、各グループの中での個人戦を行った。

A.I. Challenge

AI （人工知能）プロコンでは、参加者はコンピューターゲーム上のプレイヤーを操作するコードを書いた。フェス開催前に事前エントリーのあった50名が予選に参加し、うち16名が決勝進出。上位16名は、4グループに分けられ、トーナメント方式で競った。

また、高橋直大氏( AtCoder の代表取締役 であり競技プログラマー) と Colun 氏 (競技プログラマー)　と A.I. Challenge 上位2名によるエキシビションが行われた。

チーム対抗早解きリレー

Day 2の最終問題では、200名の全参加者を各10名いる20チームに分けた。これは、各チームが1時間半以内に10問を1人1問ずつ解く、というもの。ライブ動画と実況中継が流された。

参加者が問題を解く間、残りのチームメンバーは、解答エリアから離れた場所に集まった。「バトン」を持っているチームメイトは、疑問があれば、PCのある解答エリアを離れて、他のチームメンバーに協力を仰ぐことが可能。

リレー中に作戦会議をするチーム

プロコン以外のコンテンツ

全参加者が、学び、遊び、そして仲間と繋がれる機会を持つ―　これが実現できるよう今回イベント主催者は心を砕いた。プログラミング以外のコンテンツは、コードっぽいコンテンツを書く書道コーティングや、ボードゲーム、太鼓の達人、そしてDDR(Dance Dance Revolution)など様々。

書道コーディング

参加者はまた、プロコンのエキスパートから個人指導を受けられた。さらには、業界のプロたちのパネルディスカッションも開催。パネルディスカッションのトピックは以下の通り。

• 競技プログラミングの未来
• 競技プログラミングはプログラミング学習目的に有効か？
• レッドコーダーの作り方
• プロコン高速化対策

さらに詳しく知りたい方は…

ギズモード・ジャパン による特集記事はこちらとこちらから。

各参加者の解答は、AtCoderの順位表ページに掲載中。

同ページで、各ユーザー名の横の拡大鏡マークをクリックして見ることができる。

腕をあげたい皆さん、Top Coder 参加や、ACM-ICPC 世界大会決勝戦の過去問に挑戦してみよう。