日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

メニーコアマシン環境における並列 B 木マージを利用したビッグデータ処理方式の検討
天沼 駿亮

鷹野 俊介

加藤 和彦

阿部 洋丈

CPU 単体のクロック周波数の増加が限界になりつつある現状から、一筐体で数十個の CPU コアと数 TB 規模の主記憶を搭載するメニーコアマシンがこれから普及していくことが予想される。メニーコアマシンは 1 台のマシンで多数の CPU を持つため、処理をする上でクラスタ環境が必要だった処理をメニーコアマシンで行うことが出来る。
そのため、ビッグデータの並列分散処理に代表されるような、現在はクラスタ環境を利用して実現されている処理をメニーコアマシンで実現することができれば、計算機の運用コストが下がると期待できる。しかし、メニーコアマシンの持つ性能を活かすためには従来のロック手法では並列度の低下を招いてしまう。そこで、本研究では複数の B+-tree を用いてデータにロックを掛けずに並列分散処理を行う処理手法を提案する。この手法では各処理ノー
ドに B+-tree を割当て、各々のノードで処理を行いその結果を B+-tree に格納する。その後、全ての B+-tree を一つの B+-tree にマージすることによって結果を得る。その際、各ノードが限られた範囲にのみ操作を行うことでロックフリーな並列分散処理を実現している。この手法を用いたワードカウントのアプリケーションを作成し、単語データを用いて検証を行った
We forecast that much attention will be paid on many-core machine because manufacturing technology isapproaching to technical limit of performance. Many-core machine processes in parallel without connecting a number of cluster computers because the machine equipped with many CPUs and tremendous main
memory. We consider that managing cost of machines could be cut by constructing parallel distributed
processing on a single many-core machine. In general, a process is independent from other process in parallel processing because confliction of threads tend to cause performance degradation. We propose a highly
parallel processing scheme with merging multiple B+-trees on many-core machine without locking data.
We prepare large amount data divided into the number of threads and assign data to each threads andprocessing each data. Each thread makes a B+-tree based on each data after processing, and they merge
each B+-tree into one. We had conducted an experiment using the program of word count with this method
to verify the eﬃciency of the proposed scheme.

る。そのため、プロセッサの数を活かした並列分散処

1 はじめに理手法が関心を集めている [3]。現在、大規模なデー私たちを取り巻くデータ量は爆発的な増加を見せてタ処理を行うシステムとして、Google 社が開発した

おり [1]、これらのデータを可能な限り分析、活用しMapReduce [4] や、そのオープンソース実装であるて価値を見出す試みに注目が集まっている [2]。CPU

Hadoop[5] をはじめとするクラスタ計算機を用いたのクロック周波数の向上が頭打ちとなっている現状か分散処理形態が広く用いられている。また、Hadoop

ら、プロセッサ数を増やして性能向上を図る傾向にあ上で動作し、中間データの保存用に活用することでより高速な処理を可能にした Spark[6] も登場していBigData Processing on Many-core Machine with B+tree.
Amanuma Shunsuke, Takano Shunsuke, Kato Kazuhiko,Abe Hirotake, 筑波大学大学院 システム情報工学研
究科 コンピューターサイエンス専攻, Department ofComputer Science, Graduate School of Systems andInformation Engineering, University of Tsukuba.

る。クラスタ計算機を用いた分散処理基盤はスケーラブルな処理基盤を比較的容易に構築することが出来るという利点を持つ。しかし、その反面、高速な処理を期待する上で複数台のクラスタマシンを用いることを前提としているため、システム管理に多大なコストを要するという問題点がある。
一方で、一筐体で数十規模の CPU コアと 1 から数 TB 以上の大容量主記憶を持つメニーコアマシン

ログラムの処理手法について説明する。第 4 章では、比較実験について説明する。第 5 章では本論文の結論と今後の課題について述べる。

が入手可能となってきている。クラスタマシンは台数を増やしていくことで数千から数万ものコアを用い2 基本概念て並列処理を行う基盤を作成することが出来る。そ2. 1 B+-treeの反面、クラスタマシンほどのスケーラビリティを期

B+-tree は木構造の一種である B-tree から派生した待するのは難しい。しかし、メニーコアマシンは 単構造である。B-tree は木の全てのノードに key-value一のマシン内で動作することから CPU 同士の通信やペアの並びを所持し、その中でも最下層のノードをCPU とメモリとの通信をクラスタ環境よりも高速に葉ノードと呼ぶ。葉ノード以外のノードを内部ノー行うことが出来る。よって、メニーコアマシンで処理ドと呼び、そこには key-value ペアだけでなく他の内が可能な規模であれば、クラスタ環境よりも効率的部ノード、もしくは葉ノードへのポインタを格納してに処理を行うことができる可能性がある。さらに、メいる。このデータ構造はオーダーが最悪でも O(logn)

ニーコアマシンはクラスタ環境に比べて、マシン台数であると言う特徴を持つため、オーダーが O(n) であを減らすことが出来るため、管理コストの大幅な削るブロック構造に比べて少ない計算回数で処理を行う減が期待出来るという利点がある。また、サーバ運用ことが出来るという利点を持つ。B+-tree は B-treeの視点から見たとき、クラスタ環境で運用する場合の派生系であり、葉ノードには key-value ペアの並びに比べてメニーコア環境で運用する方が、消費電力を持ち、内部ノードにはキーと内部ノード、もしくはやサーバー管理コスト、パフォーマンスの点で優れて葉ノードへのポインタが格納されている構造となっていると考えられる [9]。また, 処理を行った中間データいる。

を保持する上で十分な大きさの主記憶を保持していれば、HDD 等の記憶媒体からデータを読み取る場合

2. 2 一貫制御に比べてアクセスコストを削減できる。よって、機械本研究では B+-tree を用いて並列処理を行う。並学習のような何回も同じ実行を繰り返すアルゴリズ

列処理を行う上でスレッド間のデータ競合を防ぎ、ムはクラスタ環境に比べて、メニーコアマシン環境データ更新競合を制御する必要がある。破損からデーでより効率的なデータ処理を実現することが出来る。

タを守る手段としてはロックをかけるのが一般的であしかし、クラスタ環境と同じ方法では、メニーコアマり、データをロックするための手法として楽観的ロッシンの性能を活かしきることは困難であると思われクと悲観的ロックが存在する。

る。そのため、メニーコアマシンの性能を引き出すた楽観的ロックは処理を行うレコードに対して更新タめのソフトウェア技術を新たに開発する必要がある。

イムスタンプを保持し、レコードの更新の直前に更新

本研究ではメニーコアマシン上でほぼロックフリー

タイムスタンプが最初の状態と変わっていないかどうに並列分散処理を行う処理手法の提案を行う。

かで排他処理を行うというロック方法である。この方

ビッグデータ処理の多くが並列性を引き出しやすい

法はスレッドの競合がないため、デッドロックを気に構造とみなせるということを利用し、複数に分割されしないでいい反面、一つのデータに対して更新処理がたビッグデータそれぞれに対して対応するノードで個複数ノードから行われる並列処理には向いていない。

別に処理を行い、最後にロックフリーにノードの結果

悲観的ロックは処理を行うレコードに対し、他のスの集計を行う。

レッドからの更新を受けていないかどうかを最初に確

本論文は以下の章によって構成される。第 2 章で認し、抑止されている場合は待機し、そうでない場合は、本研究に関連する技術と研究における基本的な概は他からの更新を抑止したうえで処理の終了時に抑止念について説明する。第 3 章では本研究で用いるプを解除する。この方法は複数のスレッドから更新を受けてもデータの破棄が行われないため並列処理向きに Insert, Merge, Reorganize の 3 つのフェーズからではあるが、複数スレッドから同時にアクセスがあっ成り立っている。まず Insert で各々のスレッドでファた場合にデッドロックが生じる可能性が存在する。

イルを読み込み、B+-tree を作成する。次に各スレッ

この悲観的ロックを用いた古典的な B-tree の並列ドで作成された B+-tree を一つの B+-tree に Merge

化方法 [7] が存在する。B-tree の持つノードが保持でする。最後に Merge された B+-tree を Reorganize

きるデータ量の最大数を N とし、データの挿入の際、して、バランスすることで、全ての単語を内包したデータ数が N 以下であるならば safe であると判別

B+-tree が完成し、ワードカウントが終了する。この

し、データを削除する際、データ数が N/2 以上であ全てのフェーズにおいて出来るだけロックを行わずにれば safe であると判別する。ノードの探索を行う時、処理を行う。

対象が safe であるノードであれば葉に処理を行っても再帰的な変更を必要としないため、ロックをかける必要がないことから並列度を高めることが出来るという考えである。メニーコアマシンに対してこの手法を適用する場合、スレッドの数がとても多くなるため、更新待ちのスレッドが多くなることが予想され、処理速度の低下につながると考えられる。そのため、本研究で用いるプログラムは B+-tree の特性を利用したロック不要な並列処理を行うことでこの問題を解決する。

3 B+-tree を用いた並列分散処理手法

図1

各ノードの処理の流れ

3. 1 基本方式
あらかじめ対象データを各スレッドのメモリに乗3. 2. 1 Insert

る大きさになるよう分割して、メモリに配置する。必まず、ファイルから単語を切り出し、B+-tree に登要であるならば HashMap などのデータ構造に一旦録していく作業を行う。しかし、いきなり単語一つデータを格納するなどの処理を行う。次に、データに一つに対して B+-tree insert を行っていくとすると、対して各ノード毎に計算処理を行い、ノードの数だ単語を B+-tree に挿入するオペレーションの数が単

け B+-tree を作成する。その後、各 B+-tree の要素語の個数と同数となってし まうため、データの規模を一つの B+-tree にマージし、結果を集計する。こが大きくなればなるほど処理速度に遅延が生じるとの手法の利点は中間データをメモリに保持すること考えられる。

を前提としているため、MapReduce 等のクラスタ処

そこで、最初にハッシュテーブルに単語を追加し理における shuﬄe フェーズの部分で中間ファイルをていくことで、B+-tree への挿入回数をへらす。ハッHDD に書き込む処理を行わずに集計処理を行うこと

シュテーブルはデータの入力、取得をО (1) で行うこが出来る点と、ロックフリーにマージを行うことが出とが出来る。一方木構造ではО (log(n)) でデータの来るため、デッドロックの心配をせずに並列処理を行取得を行うため、データ数が 100 倍になれば約 2 倍、うことが出来る点にある。

データ数が 1000 倍になれば約 3 倍程度の時間がハッシュテーブルに比べて必要となってくる。そのため、

3. 2 実装

単語をあらかじめハッシュテーブルに挿入し、単語の以下にワードカウントプログラムの実装を例とし重複をなくした状態で B+-tree に挿入していくことて説明を行う。プログラムは図 2 のように、おおまかで処理速度の向上が期待できると考えられる。

ハッシュテーブルに代入することによってキーと値のペアを作成する。ワードカウントでは単語をキー,単語の数を値として格納する。この処理を分割されたビッグデータに対して並列に行うことによって、各スレッドがスレッド内では重複を持たない単語のキーと値という中間結果を保持している状態になる。この状
態から ハッシュを B+-tree に変換する作業を行い、次のフェーズに移行する。
ワードカウントのプログラムでは単語を抜出、格納するという簡潔な処理のみを行うことや、単語が重複することを考慮した結果から ハッシュテーブルを用いてキーと値の格納を行っているが、それ以外の複雑な処理を要するプログラムでは赤黒木や B+tree など

図2

B+-tree によるキー空間の分割の他のデータ構造に直接中間結果の格納を行うことも考えられる。また、この手法は主記憶に中間結果を保選ぶ。次に分割されたキー空間にそれぞれ独立した持できることを仮定として考えている。これは、ビッスレッドを割当て、各スレッドがマージしたい全てのグデータ本体が主記憶に収まりきらないデータ量でB+-tree から、割り当てられたキー空間の中にあるあっても、演算や関数の計算によってカウントに必要キーのみに対してマージ処理を行う。これによって、なデータのみを抜き出すことによって主記憶に格納す各々のスレッドがあらかじめ決められたキー範囲にのることが可能であるという仮定に基づくものであり、みしか処理を行わないため、全ての B+-tree にロッ序論で述べた Spark システムにもこの仮定が使われクをかけずにマージ処理を行うことが出来る。ていることからも合理的な考えであると思われる。

3. 2. 2 Merge

3. 3 Reorganize

このフェーズでは前のフェーズでキーと値に分けら

このフェーズではマージ処理を行った後の B+-tree

れ、B+-tree に格納された中間データに対して B+-をバランスする処理を行う。先ほどのマージ処理を終tree の特性を用いたマージ処理を行うことで最終結えた後、B+-tree には全ての単語が内包されている状果を得る。B+-tree はその性質から全てのキーを葉に態になる。しかし、キーの範囲によって単語の数はバ保有している。そして、その葉へのポインタを各内部ラバラであり、マージを終えた段階ではあるキーの範ノードが所持しており、各葉ノードは内部ノードの持囲のみとても単語数が多くなっていると言う状態も考つポインタによって排他的に分割された構造を取る。

えられる。その状態だと葉ノードがオーバーフローしつまり、キー空間 key0 から key10 を各葉ノードのている状態となり、B+-tree としての形ではなくなっkey を境に分割しているということになる。その様子てしまう。そのため、オーバーフローしているノードを図 3 に示す。 例えば葉の一段上のノードを参照す

に対してバランス処理を行い B+-tree の形にする必るとそのノードにあるキー (key2,key4,key7,key9) は要があるのである。

この木に格納される可能性のあるキーを排他的に分割

このアンバランスな状態は B+-tree を下のレベルしていることになる。つまり、この B+-tree はキーから順々にスプリット処理をしていくことで解決す空間を 5 つの区間に分割していることになる。

る。まず一番下の葉ノードに対してオーバーフロー

このようにキー空間全体が内部ノードのキーによっしているかどうかの判断を行う。その中でオーバーフて分けられることを利用してマージ処理を行う。まローしているノードがあった場合、そのノードに対しず、マージ先となる B+-tree を全スレッドから一つてスプリット処理を行う。葉ノードが全てオーバーフローしていない状態になったことを確認したら次はそる。また、各々のファイルの処理に対してフェーズごの一つ上の中間ノードに対して再度オーバーフローとに時間を計測し、各々のフェーズでどれだけの処理しているかどうかの判断を行う。この操作を繰り返し時間がかかっているかを確認する。

行い、親ノードに達するまで処理を終えた時点でこのフェーズを終了するというのが一連の流れである。

4. 3 ワードカウントプログラムの処理の流れ

このフェーズにおいて、各ノードに対して各スレッ

本実験で用いるプログラムの処理の流れの説明をドを割り振り、オーバーフローしているかどうかの判行う。まず巨大なファイルを各スレッドの保持するメ断をさせ、レベルごとに処理ノード全てで同期を取るモリに乗るサイズまで分割する。それぞれのスレッドことによってノードのレベルの中で並列化することがはそのファイルから単語をキー、個数をバリューとし出来る。

た組み合わせを抜き出し、ハッシュに保存していく。
ファイル内全ての単語をハッシュに格納し終えた後、

4 実験

B+-tree へと格納する。入力の処理が全て終わった後

実際にこの処理手法で実装したワードカウントプ

全ての B+-tree に対して merge,reorganize の処理をログラムを用いて実験を行い、マルチコアを有効活用行い、集計することで処理を終了する。

できているかを明らかにする。この処理手法はメニーコア環境で動作することを目的に作成した手法であ4. 4 実験結果

るが、NUMA アーキテクチャを考慮した方式の検討

図 3, 4 に Linux ソースコードに対しての実験結果、がまだ不十分であるため、今回は UMA アーキテク

図 5, 6 に Wikipedia 単語データに対しての実験結果

チャに絞ったマルチコア環境下で実験を行い、提案手を示す。図 3, 5 からどちらのデータに対しても割り法の可能性を検討する。

当てるスレッドの数が増加するに連れて、処理時間が減少していることが分かり、単一ノード内に於いてス

4. 1 実験環境ケーラブルな処理が出来ていることが確認できた。ま実験環境として, CPU が Intel Xeon CPU E7-

た、図 4, 6 から、どちらの場合もほとんどの処理時

4870 2.40GHz 80cores (10cores × 8nodes), メモリ間を insert と merge が占めていることが分かる。そが 1TB, OS が, Linux 3.2.0-4 の環境を用いた。 この中で、スレッド数によって処理時間が短くなっていのマシンは NUMA アーキテクチャであり、メモリ 1るのは insert の部分であり、merge と reorganize につに対して CPU コアが 10 個繋がった構造を一つのかかる時間は 1 スレッド時の実験結果の約 7 分の 1ノードとし、それを 8 ノード分持つ。本実験ではこ程度の処理時間から変化が無いことが分かる。また、の内 1 ノードのみに限定して、10 コアの環境下で実reorganize に関しては図 6 の実験ではほとんど処理験を行う。

時間がかかっていないことから、ファイルが大きくなると、小さいファイルに比べて reorgznize にかかる4. 2 実験内容時間はとても短くなっていくということが分かった。

入力データとして、Wikipedia の英語版のページかこれらの結果から、まず merge 処理の時間が変わっら単語を抜出し、タブで区切りを行ったデータ 10GBていないことについて考察する。merge 処理を並列分と、Linux のソースコード [8] を全て txt ファイルに行っているため、merge の部分がスレッド数の増加に起こしたデータ 180MB 分用いる。Wikipedia のに応じて速度が上がっていなければならないのだが変データは 1GB を 10 ファイル、Linux のデータは小化が無い。原因として考えられるのが、データに偏りさいファイルが 28267 ファイル集まったデータセットがあるというケースである。マージ処理をするにあである。そのデータに対して使用スレッド数を変化さたって、一部のスレッドにのみデータが集中してしませ、ワードカウントを行い、処理速度の変化を観測す

い、並列な動作が実質的に行えていない状態になっている。もしくは、並列マージは正常に動いているが、同期のオーバーヘッドに時間がかかってしまっているケース等も考えられる。次に、図 4, 6 を比べて各々のデータの処理時間についてフェーズごとに比較し考察を行う。insert 部分にかかる時間は対象となるデータの大きさによって変化するため、180MB と 10GBのデータとではデータの大きさでは 50 倍程度の処理時間の差が生じると考えられる。実験結果からは約40 倍の差が出ていると読み取れるが、ファイルの個数が Linux 側の方がとても多く、少ないとはいえ読み取りに時間がかかっていることを考慮に入れると、

図3

スレッド数の変化による処理速度の推移 (Linux)

図4

スレッド数の変化による各処理時間の内訳 (Linux)

速度としては想定通りであると言える。次に merge
部分に関してだが、こちらはデータ全体の要素数に応じて処理時間が変わると考える。merge 処理では全ての B+-tree の該当する範囲に対して各々のスレッドがアクセスし、要素の集計を行う。つまり、アクセスする要素の数が多ければ多いほど処理の時間が長引くと考えられる。今回実験で用いたデータの要素数の差は約 30 倍程度の差があったため、これだけの時間の差が生まれたと考えられる。最後に reorganize 部分に関してだが、reorganize にかかる時間は作成される木の構造や葉の数、データ全体の要素数等、複数の要素によって変化すると考えられる。今回の実験ではどちらも 3 段の木が作成されていたものの、葉の数と内部ノード、データの要素数の全てが異なっていたた
め、処理時間に差が出ている。仮に葉の数以外の要素が全て同じで、葉の数が 2 倍異なる木に reorganizeを行った場合、処理時間は 2 倍異なると考えられる。
また、木の高さが増えればその段数分 reorganize の回数は増え、逆に内部ノードの数が増えればその分並列に処理できる葉の数が増えるため処理は高速化すると考えられる。

図5

スレッド数の変化による処理速度の推移 (Wiki)

図6

スレッド数の変化による各処理時間の内訳 (Wiki)5 結論と今後の課題
本研究ではメニーコア環境に於けるロックフリーな並列分散処理方式の提案を行った。B+-tree を使った処理方式によってデータにほぼロックをかけずに並列分散処理を実現した。また、実験によってスレッド数の増加に応じてスケーラブルであることが確認できた。今後の課題としては、まず、メニーコア環境で実際に使用するための実装を行って行きたいと考えている。また、ワードカウント以外のアプリケーションの実装や、機械学習等の繰り返し処理に対する処理の最適化等を行っていきたいと考えている。
謝辞 本研究は JSPS 科研費 15K12006 の助成を受けたものです。

参 考 文 献[ 1 ] John Gantz and David Reinsel: THE DIGITAL UNIVERSE IN 2020: Big Data, Bigger Digi-tal Shadows, and Biggest Growth in the Far East United States,2013[ 2 ] Chen, Hsinchun, Roger HL Chiang, and Veda C.
Storey: Business Intelligence and Analytics: FromBig Data to Big Impact. MIS quarterly 36.5:1165-88
2012[ 3 ] Akhter, Shameen, and Jason Roberts: Multicore programming. Vol. 33. Hillsboro Intel press,
2006[ 4 ] Jeﬀrey Dean and Sanjey Ghamawat: MapReduce:Simplified Data Processing on Large Clusters.
Communication of ACM 51.1, 2008: 107-113[ 5 ] Jeﬀrey Shafer: A storage Architecture for DataIntensive Computing. Diss. Rice University, 2010
[ 6 ] Matei Zaharia, Mosharaf CHowdhury et al:
Resilient Distributed Datasets: A Fault-Tolerant
Abstruction for In-Memory Cluster Computing.
USENIX Association, 2012
[ 7 ] R. Bayer and M Schkolnick: Concurrency of Operations on B-Trees. Acta Infomatica 9:1-21,1977[ 8 ] http://www.kernel.org/pub/linux/kernel/v3.0/linux3.7.1.tar.bz2[ 9 ] Raja Appuswamy,Christos Gkantsidis et al:Scaleup vs scale-out for Hadoop: time to rethink?, SOCC
’13 Proceedings of the 4th annual Symposium on
Cloud Computing Article No. 20, 2013