JavaでCSVファイルを高速に読む方法

最近、とある任務があって「数百万レコード」のCSVファイルを読み、
統計解析を実施するAPを自作したいと考えています。

しかし、ファイルのレコード数が膨大なため、解析する前にファイル読み込みに
大きな時間がかかってしまい困っています。

読み込みを高速化するために、複数のスレッドを用意し、スレッド毎に読みこむ
レコードの行を決めて、並列処理を行いたいと考えたのですが・・・

・任意の行をランダムに読むためRandomAccessFileクラスの利用を
　考えたがレコードが固定長でないと利用できない。

という点があり断念しています。私も詳しくはわかっていないのですがHadoopという
技術を使ってファイルを分割して並列処理するといった方法が取られているようですが
ファイルを高速に読み込む方法について、この質問を見ていただけた方の中で
こうすれば高速化できるというノウハウがもしあればご教授いただけるとありがたいです。

またできれば、複数の筐体にファイルを分割して分散処理するという大掛かりの手法ではなく、
一つの筐体で並列処理して高速化したいと考えています。

Javaは、あまり詳しくなくとんちんかんな質問かもしれませんがどうぞよろしくお願いします。

No.1 ベストアンサー 回答者： wormhole 回答日時： 2012/08/14 03:00

Hadoopは大規模分散ファイルシステムであって、ファイルを分割して並列処理するというのとは違うみたいですが・・・

とりあえず私の思いついたのは読み込み専用スレッドを1つ用意しておいて順次解析用のスレッドを起動する方法かなぁ

この回答へのお礼

回答いただき有難うございます。

Hadoopについて勉強不足ですいません。もう少し勉強が必要ですが
知人に教わった内容では、１つのファイルを64MB単位（これをチャンクというそうですが）毎に分割し、分割したデータをそれぞれ複数のサーバにコピーして、各サーバで分散処理すると聞きました。

おしゃられる通り、並列処理するというのは違うものかと思います。（すいません。）書籍で勉強します。

また、下記の件、参考にさせていただきます。

＞とりあえず私の思いついたのは読み込み専用スレッドを1つ用意しておいて順次解析用のスレッドを起動する方法かなぁ

ファイルは先頭から1行ずつ順に読むしかないのでまず、

(1)行単位でファイルを読み込むスレッドを用意し、
　 メモリ上に確保（配列上の格納）

(2)区切り文字の解析・フィールドの値を取得する処理を行う
　スレッドを複数用意し、非同期処理。データの競合が起きないように
　配列上にアクセスするアクセスする要素をスレッド毎に決めておく。

という処理を実装してみたいと思います。（勘違いしてたらご指摘お願いします。）

い

お礼日時：2012/08/14 22:38

No.2 回答者： kmee 回答日時： 2012/08/14 08:16

ファイルアクセスで、時間のネックになるのは、記憶装置とCPUとのデータのやりとりです。

一つのHDD上のファイルを別スレッドで同時に読みにいっても、HDDは順番にデータを返すだけで、同時に返したりはできません。むしろ、シーク時間(ヘッドを目的のデータの場所まで移動させる時間)が増える可能性があります。

SSDなどの高速な記憶装置を使う、複数のHDDの分割して同時に読み出す/RAIDでスライピングにする、といった方法はあります。
が「複数の筐体にファイルを分割して分散処理する」よりはましですが、装置の追加変更が必要です。


あとは、本当に「ファイルの読み込み」がネックなのでしょうか?

統計処理の時間が長いようなら、並列処理によって高速化できるかもしれません。
Javaではなく、統計処理に特化したもの(R言語等)を使うとか。

この回答へのお礼

ご回答いただきありがとうございます。

下記の件、理解不足ですいませんが、例えば仮に読み込むファイルが１レコードが固定長・ファイルの全体総レコードが既知済みと仮定した場合、ランムアクセスでファイルを読みにいっても結局、HDDは順番にデータを返すので
性能は向上しないということでよろしいでしょうか？

＞一つのHDD上のファイルを別スレッドで同時に読みにいっても、HDDは順番＞にデータを返すだけで、同時に返したりはできません。むしろ、シーク時間＞(ヘッドを目的のデータの場所まで移動させる時間)が増える可能性があり＞ます。

私の考えたのは、下記はそのとおりなのですが、


＞時間のネックになるのは、記憶装置とCPUとのデータのやりとり

そのためにJavaではバッファリング（記憶装置とCPUとの処理性能の差
を埋める）というもの
があり、一旦、メモリ上にデータを展開してからマルチスレッドで読み込
めば性能向上するのかなと考えていました。
（勘違いしてたらすいません。）


また、統計処理自体は予定どおりの処理性能が出ています。
（おしゃられる通り、並列処理するともっと早くなると思いますが）

個人的には、JavaはRより性能は早いと考えています。
Rは、インタプリタ言語ですので遅い（※）かなと思っています。
（Rの関数をCやJava作って・呼べばRからも高速に読めると思います。
　ベンダーさんによっては早いRを利用できる製品（高い！）もあるそう）

しかしながら、Rは色々な統計関数が用意されているようなので
時間の許す限り、少し組み込みを検討したいと考えています。

ご意見いただきありがとうございます。

お礼日時：2012/08/14 23:09

No.3 回答者： Tacosan 回答日時： 2012/08/14 23:56

ランダムアクセスできるならその方が速いです. 例えば, ふつうの本を読むときに「100ページ目を読もう」と思ったら, 1ページ目から順に読んでいきますか? それとも, いきなり 100ページ目を開きますか?

あと, 「記憶装置とCPUとのデータのやりとり」については「ディスクから読み込んで電線にのせる」までを考えるのが (ここがボトルネックになるので) ふつう. これもふつうの本でたとえるなら, 「1ページ目から順に読んでいく」のと「てきと～な順でてきと～なページをばらばら見ていく」のと, どっちがいいかってレベル.

この回答へのお礼

回答ありがとうございます。

知り合いにも聞いたところ、ランダムアクセスできるならかなりファイルを
早く読めるということも確認できました。

ただ、今回はファイルが単純な固定長ではなく可変長なので
少しよく考えたいと思います。

お礼日時：2012/08/16 08:16

No.4 回答者： kmee 回答日時： 2012/08/15 01:52

念の為に確認ですが、CSVの全部のデータを読んで、全データで使って統計処理をする、ということですよね?

#3さんの例を拝借して。

・現状
一冊の本を先頭から読んでいる。
本がぶ厚くて、読むのに時間がかかっている

・やろうとしたこと
何人か使って、同時に読めば早く読めるのではないか(マルチスレッド)

・実際
本が1冊しかないので、結局は1ページずつ読むしかない。合計の読む時間は同じ。
※ バッファは、1ページコピーを写しを取るようなもの。写しを取るためには本を読む必要がある。取れてしまえば、それを読み書きするのは速い。

途中から読もうとしても、文章の長さがばらばらで、どこから読んでいいかわからない
→ 固定長なら、X番目のデータはYページ目、と簡単にわかる。
ランダムアクセスが速いのはこの「Yページ目」がすぐわかることで、そのページを読む時間は変わらない。

・対策
早く読める本にする(SSD等)
本を分ける(RAID,別HDD等)

・本当に読む時間が問題?計算時間は?
一人が本を読んで、計算を他の人にやらせれば、同時進行できる。

という感じになると思います。


○R等の速度
ベンチマークをしたわけではないですが。

言語自体はインタプリタかもしれませんが、演算や関数の実装までインタプリタということはまずありません。
配列の統計処理、と言ったものは、並列処理や高速アルゴリズムを採用する等の最適化を行なっているのが普通です。特に、R等は統計処理が売りなのですから。
下手にJavaで作るより速い、ということも十分に考えられます。

No.5 回答者： hanabutako 回答日時： 2012/08/16 01:22

CSVファイルの数や構成、更新の仕方、形式の変換の可否、解析内容、解析が単発か繰り返しがあるかなどで随分解き方が変わると思います。

追記による更新しかなされないなど、更新箇所が明確にわかり、形式を変換していいなら、RDBMSにデータを入れて、適切なインデックスをつけるのもひとつの方法です。データの解析が繰り返し行われ、一度データを入れたあとの差分データのアップロードがそんなに負担にならないなら、その変形として、クラウドデータストアサービスを利用する方法もあるでしょう。クラウドデータストアサービスで適切なクエリを走らせれば裏ではHadoopと同じように分散並列にデータ処理が行われて高速に解析結果が得られます。

CSVファイルが複数あり、それぞれに対して同じような数値解析を行わないといけないし、それぞれ1回限りしか解析をしないという場合が一番最悪で、読み込みについては高速化する方法はないですね。コンパイラなど、複数プロセス動くと高速化できるというのはディスクI/Oをした時にデータが来ずに止まっている (ブロックしている) 時間にその他の処理を行えるから高速になるわけなので、各スレッドが読みながら解析するような処理をしない限りは複数スレッド動いても高速にならないですね。単一ファイルについてそれをちゃんと作るのは面倒なので、それこそ#1さんの仰るように、読み込み専用スレッドと処理スレッドを分けたほうが良いでしょう。

しかしながら、Javaにかぎらず色々と頓珍漢な感じがします。
「○○をやると速い、○○をやると遅い」というようなお題目ではなく、なぜそうなのかを考えられたほうが良いと思います。

> そのためにJavaではバッファリング（記憶装置とCPUとの処理性能の差
> を埋める）というものがあり、一旦、メモリ上にデータを展開してからマルチスレッドで読み込
> めば性能向上するのかなと考えていました。

その「一旦、メモリ上にデータを展開」というのが、解析を除いて一番重い処理だと思います。

ちなみに、こんな話をどこかで見たことありますか？
https://gist.github.com/2841832

Javaにかぎらず、一度ディスクからファイルを読むとメモリーが不足しない限り、OSが管理しているバッファキャッシュにデータが保存されます。そして、その状態でデータを読むとカーネル領域からユーザー領域への単純なメモリーコピーなので、1MBやっても0.25 msです。一方、ディスクからの読み込みはシーケンシャルリードでも1MBにつき、20 msです。ランダムにデータを読むとなると、ディスクから読み込む場合はシークが一度発生するごとに 10msのペナルティがあり、キャッシュミスごとに 100 nsのペナルティが課せられます。よって、アルゴリズムか並列処理で挽回できない限り、ランダムリードはあまり良くありません。

> 個人的には、JavaはRより性能は早いと考えています。
> Rは、インタプリタ言語ですので遅い（※）かなと思っています。

ことディスクI/OについてはJavaもRも大した差はないと思います。
JavaもJITが行われるとはいえ、Java Bytecodeを実行するインタプリタです。
I/Oなどシステムコールを使うところにJITは行えないと思いますので、おっしゃるようなI/Oヘビーなタスクにはあまり向いていないのではないでしょうか？
むしろ、I/Oヘビーな場合は、Javaの利便性を犠牲にしてシステムコールを直に叩けるCやC++を使ったほうがいいですね。ちなみに、自分だったら単に読み込むのがボトルネックだったらCSVファイルをmmapして、無駄なカーネルからのコピーをなくします。お金の余裕があるなら、これに加えて#4さんのおっしゃるとおりSSDなどを使いますが。

また、インタプリタ言語が遅いというのもものによりけりです。#4さんのおっしゃるとおり、インタプリタ言語でも組み込み関数を読んだ先はネイティブなコードで処理を行い、それもカリカリにチューニングされたコードになっているのが普通です。だから、組み込み関数を使った場合、下手くそがいい加減なアルゴリズムで書いたJavaやCのプログラムよりもはるかに速いのが普通です。
(極論を言うと、pythonのsortとCで書いたバブルソートではどちらが速いでしょう？)


というわけで、どういう解き方をするかはCSVファイルの更新方法などの背景を知らないと決まらないですね。自分だったら、ビッグデータを処理するためのクラウドサービスなんかも検討の視野に入れますし、RDBMSも検討します。そして、実際のデータに似せたデータを使ったごく簡単なプログラムをそれぞれに向けて書いて、ベンチマークをとります。 データサイズを変えて計測してプロットするとだいたい傾向がわかりますしね。

この回答への補足

すいません。

少し補足させていただくと、おしゃられるとおりだとは思います。

＞むしろ、I/Oヘビーな場合は、Javaの利便性を犠牲にしてシステムコールを＞直に叩けるCやC++を使ったほうがいいですね。ちなみに、自分だったら単＞に読み込むのがボトルネックだったらCSVファイルをmmapして、無駄なカー＞ネルからのコピーをなくします。

ただ、全体的にアプリをJavaで統一したいという意向もありJavaでファイル
読み込み高速化するという話に焦点をあてさせてください。

＞SSDなどを使いますが

また、ハードウェアなどを追加・強化すれば性能が向上することもわかりますが、前述したとおり、与えられた資源の中でJavaでどう性能向上するかという
点を検討したいと考えています。（お金を使うのは最終手段なのかなと）

補足日時：2012/08/16 08:10

この回答へのお礼

連絡ありがとうございます。

要件を明確化（といってもすべてお伝えするわけにはいきませんが）
しておらずすいませんが定期的に生成されるCSVファイルを
逐次読み込み解析し、データをリアルに活用して、
なんらかのアプリケーションを仲間内で作ろうとしています。

結論から言うと状況としては

-------------------------------------------------------
・データサイズが大きすぎて入力ファイルを読み込みに時間がかかり、
　分析する側に必要なデータを投入できない。

・統計処理の部分のスピードは十分
　（なお、Rにも同様なアルゴリズムがあるが遅く（※）てダメとのこと。
　 明らかにJavaやCで作りこんだ方が早い。）

　※どういうアルゴリズムを実施するかまでは、お伝えできませんが、
　結論から言うと仲間が統計に詳しく、Rを動かして評価していますが、
　Java、Cで動かした場合と比較して遅いというのが結論です。
　（Cが一番早いですがJavaで十分性能が出ていますので）
　
　また、Rに詳しい方から聞いても、関数にもよるでしょうが
　自作した方が明らかに早いと意見いただいております。
　更に、Rは遅いということを書いてあるブログなんかも結構見かけます。
　（ソートとか行列の操作とかは差はほとんどないかもしれませんが
　 差分を意識して書くアルゴリズムは特に顕著な気がします。）
-------------------------------------------------------

ということで、ファイルの読み込みを性能向上する必要があるという
話になっています。(ちなみに、ファイルを読み込む作業と統計処理
を行う作業はスレッドは分けています。)

読み込むファイルですが、レコード毎に可変長のため、ランダムアクセス
自体がそもそもできないのかなと思っていますのでシーケンシャルに読む
しかないと考えています。

下記は、そのとおりかもしれませんが、JavaVM上にデータを展開するよりも
レコード毎のフィールドを解析する時間がかかっていると考えています。

＞「一旦、メモリ上にデータを展開」というのが、解析を除いて一番重い処理だ＞と思います。

よって、解析のコストを下げるために、一旦配列に格納して、フィールドの
解析を並行処理すれば性能向上するかもしれないと思っています。

いろいろと試行錯誤していきたいと思いますが、#1さんからいただいた
ご意見をもとにまず検討していく方針で進めたいと思います。

色々と貴重なご意見をいただきありがとうございます。

お礼日時：2012/08/16 03:09