51GB・8.9億行を開いて、理論上どこまで開けるのか計算してみた — 実データと「約920京行」の話

技術解説

大容量テキストビューア「UwView」をGitHubで公開した記事では「最大2億行クラスを高速に閲覧できる」とうたっていました。ただ、それまでの実測は行番号を振っただけの合成データでのもの。「実際の、しかも桁違いに大きい実データではどうなのか」——まずはそれを確かめ、そのうえで理論上どこまで開けるのかを、自分のコードの型と構造から計算してみます。

題材は OpenStreetMap(OSM)日本全体をXML化したファイル。結果は 51GB・約8.9億行 という、うたい文句の「2億行」を4倍以上も上回る規模になりました。

リポジトリ: amru195704/UwView(PolyForm Internal Use License 1.0.0)


テストデータの作り方 — OSM日本を51GBのXMLに

OSMの日本データは Geofabrik から配布されています。配布形式はバイナリの .osm.pbf(約2.3GB)なので、これを osmium-tool でXMLテキスト(.osm)に展開します。

# pbf(2.3GB・バイナリ)を取得
curl -L -o japan-latest.osm.pbf \
  https://download.geofabrik.de/asia/japan-latest.osm.pbf

# osmium で XML(テキスト)に変換 → 51GB・8.9億行
osmium cat japan-latest.osm.pbf -o japan-latest.osm

できあがったファイルはこんな中身のUTF-8テキストです。緯度経度を持つ <node> 要素が延々と並びます。

<?xml version='1.0' encoding='UTF-8'?>
<osm version="0.6" generator="osmium/1.19.1">
  <bounds minlat="20.08228" minlon="122.5607" maxlat="45.815403" maxlon="154.4709"/>
  <node id="31236558" version="5" timestamp="2020-06-27T07:40:04Z" lat="35.635073" lon="139.768101"/>
  ...

wc -l で数えると 892,239,125行。まさに「エディタでは絶対に開けない」領域のファイルです。


実測結果(51GB・892,239,125行・Apple Silicon Mac・外付けSSD)

UwViewに同梱のベンチハーネス(UwView.Bench)で計測しました。

項目 実測値
ファイルサイズ 51,254,526,392 バイト(約48 GiB)
open+文字コード判定 12 ms
ページモード表示(先頭50行+50%位置50行) 3 ms
索引構築(1回の順次読み) 172.8秒(283 MB/s)
総行数 892,239,125wc -l と完全一致)
チェックポイント数(索引) 3,485,310件 ≒ 26.6 MB
マネージヒープ増加 33.3 MB
GetLineランダム1000回 平均 1.28 ms/p99 3.0 ms/最大 5.7 ms
先頭行取得 <?xml version='1.0' encoding='UTF-8'?>(2.9 ms)
末尾(8.9億行目)ジャンプ </osm>0.006 ms
文字コード切替 3.4 ms(索引再構築なし)
WorkingSet 12,083 MB(mmapページ含む・OSが回収可能)

「2億行の壁」は問題なく越えた

いちばん確かめたかったのは、うたい文句の2億行を超えても破綻しないかでした。結論から言うと、問題ありませんでした。

  • 総行数が正確:UwViewが数えた 892,239,125 は、wc -l の結果と1行の狂いもなく一致しました。
  • 末尾ジャンプが即時:8.9億行目(最終行 </osm>)へのジャンプは 0.006 ms。索引さえできていれば、ファイルのどこへ飛んでも一瞬です。
  • メモリは据え置き:51GBのファイルに対して、常駐するのは索引26.6MB+マネージヒープ33MB程度。ファイル本体はメモリに載せません。

UwViewは行番号を long(64bit整数)で通していますが、そもそも8.9億は int の上限(約21.4億)にも収まる範囲です。設計上、行数がここでボトルネックになることはありません。

なお表の「WorkingSet 12GB」は大きく見えますが、これはmmapで触れたファイルページのキャッシュで、OSがメモリ圧に応じて随時回収する非常駐領域です。アプリが確保しているメモリではありません。


合成データとの差 — 正直なところ

以前の合成2億行データと、今回の実データ8.9億行を並べてみます。

項目 合成2億行(5.1GB) 実データ8.9億行(51GB)
索引構築速度 538 MB/s 283 MB/s
GetLineランダム(平均) 0.005 ms 1.28 ms
末尾ジャンプ 0.003 ms 0.006 ms
索引サイズ 6.0 MB 26.6 MB

GetLineが合成データより遅い(0.005ms → 1.28ms)のは正直に触れておきます。理由は3つあります。

  1. 外付けSSDのランダム読みが律速(内蔵SSDならもっと速い)。
  2. 実XMLは行長がまちまちで、キャッシュ効率が合成データより悪い。
  3. 51GBはメモリに載りきらず(WorkingSet 12GB)、多くの読みが実ディスクI/Oになる。

とはいえ「ミリ秒級」であることに変わりはなく、スクロールや行ジャンプの体感は十分実用的です。索引構築の283MB/sも、51GBを1回だけ順次に読む処理で、こちらは完全にストレージの速度で決まります。


開いた瞬間から見える — ページモードの強み

もうひとつ強調したいのは、索引構築(約3分)を待たずに閲覧を始められる点です。今回も、開いてから文字コード判定まで12ms、最初の1画面の表示は3msでした。51GBのファイルであっても、less で巨大ファイルを開いた瞬間のように、まず「バイト位置ベースのページモード」で即座に中身が見え、裏で索引ができあがったら「行番号ベースの行モード」へ静かに昇格します。

「巨大ファイルを開く」と身構える必要がなく、ダブルクリックした瞬間から中身が見える——これがUwViewのいちばん伝えたい体験です。


では、理論上どこまで開けるのか?

8.9億行が問題なく開けたところで、ふと思いました。理論上は何行まで開けるのか? 気になったので、型と構造から上限を順に計算してみます。

まず結論:型の上限は約920京行

UwViewは行番号もバイトオフセットも符号付き64bit整数(.NETのlongで通しています。したがって型としての天井は次の値です。

long.MaxValue = 9,223,372,036,854,775,807 (≈ 9.2×10^18 行 = 約920京行)

すでに現実味がない桁ですが、話はここで終わりません。実際にはこの手前に壁が順番に現れます。

壁① ファイルサイズ

バイトオフセットもlongなので、扱えるファイルは最大約8 EiB(エクスビバイト)です。しかも1行の最小は改行1バイト(\n)だけなので、「行数の上限」と「ファイルサイズの上限」はどちらも8 EiB級でほぼ一致します。もちろん現実には、その手前でファイルシステム側の最大ファイルサイズ(ext4は16TB/ファイル、APFSやNTFSは数EBなど)が先に効きます。

壁② 索引の構造

UwViewは省メモリのために「N行ごとに1個だけバイト位置を記録する」スパース索引を使っています(既定値 N=256)。このチェックポイントはList<long>——内部的には配列——で保持していますが、.NETの配列要素数の上限は約21.4億(Int32.MaxValueです。

つまり既定設定では、次の行数で索引配列が頭打ちになります。

21.4億 × 256 ≒ 5.5×10^11 行(約5,500億行)

これはblockLines(N)を大きくすれば緩和できる設計ですが、そもそも索引のメモリが先に効いてきます。索引サイズは「行数 ÷ 256 × 8バイト」で概算でき、今回の実測では8.9億行で26.6MBでした。この比率で5,500億行まで伸ばすと、索引だけで約17GBのRAMが必要になり、実効的にはこの辺りが現実の上限になります。

壁③ 本当の壁は「容量」

整理すると、次の3段構えになります。

段階 上限 実際に効くか
型としての上限 約9.2×10^18行(約920京行) 事実上到達不能
構造上の実効上限 既定で約5,500億行(設定変更で拡張可) 索引RAMが先に律速
実務上の本当の壁 ストレージ容量 ここが現実的な上限

8.9億行のテストで一番効いたのも、まさに「行数よりファイル容量が先に効く」という点でした。51GBがキャッシュに載りきらず、ランダム読みはミリ秒級に落ちる——でも破綻はしません。ファイル本体を常駐させず(mmap)、可視行だけ描画し、行位置は小さなスパース索引で引く、という設計の素直な帰結です。


で、実用上の限界は?

型上限の9.2×10^18行に触れるには8 EiB級のファイルが必要になるので、人類が普通に用意できるストレージでは到達できません。現実的には「用意できる一番大きいファイル=ビューアの限界」ということになります。

とはいえ実用の話をすると、8.9億行ともなると索引作成に約3分かかり、検索してもなかなか結果が出ません。快適に使えるのは2億行ぐらいまで、というのが正直な体感です。「最大2億行」はあくまで目安で、実際には行数よりストレージ容量が先に効く——それが実データでも理論計算でも同じ結論になりました。

もし手元に極端に大きいテキスト(数百GB〜TB級)をお持ちの方がいたら、ぜひUwViewで開いて限界を調べて教えていただけると嬉しいです。


まとめ

  • OSM日本全体をXML化した 51GB・8.9億行 の実データを、UwViewで開いて検証した。うたい文句の「2億行」を4倍以上超えても破綻せず、総行数は wc -l と完全一致、末尾(8.9億行目)ジャンプも 0.006 ms。
  • 常駐メモリは索引26.6MB+ヒープ33MB程度で、ファイル本体は非常駐。開いた瞬間(12ms/3ms)からページモードで閲覧でき、索引は裏で構築(約3分・283MB/s=ストレージ律速)。
  • 理論上の上限は、型としては約920京行(long)だが事実上到達不能。その手前で、スパース索引の配列要素数上限(既定で約5,500億行)や索引メモリ(約17GB)が先に効く。
  • 索引の壁を越えても、最終的に効くのはストレージ容量というシンプルな現実。実用の体感は2億行ぐらいまで。
  • 「行数よりファイル容量が先に効く」という実測の結論が、理論計算でもそのまま裏付けられた。

関連記事

出典

  • amru195704/UwView(GitHub) https://github.com/amru195704/UwView
  • OpenStreetMap Japan extract(Geofabrik) https://download.geofabrik.de/asia/japan.html
  • osmium-tool https://osmcode.org/osmium-tool/
  • Int64.MaxValue プロパティ(.NET) https://learn.microsoft.com/dotnet/api/system.int64.maxvalue
  • Array クラスの上限(.NET) https://learn.microsoft.com/dotnet/api/system.array

上位版:UwView Pro(発売中・全OS対応:Windows/macOS/Linux)

「巨大ファイルをいつでも瞬時に表示・検索、索引を保存して2回目以降は行番号付きで瞬時に開く・検索が最大約9倍・ログを約1/9で保管してそのまま開ける」商用版です。買い切り $129 / 月額 $9。
→ https://uvp.y42u.net/pro/
(UwView / UwView Pro は、初回でも開いた瞬間からファイル全体を閲覧・検索できます。索引はバックグラウンドで作成し、完成後に行番号を表示。UwView Pro は索引と圧縮を保存するので、2回目以降は行番号付きで瞬時に開けます。他ツールは索引が終わるまで先頭しか見えませんが、UwView は1回目から全体を瞬時に閲覧・検索できます)


開発者より: アプリ・Kindle本・オープンソースの一覧は GitHub: amru195704 にまとめています。


お願い
本記事の情報は参考目的で掲載しており、正確性・完全性を保証するものではありません。誤記・不正確な情報がございましたら、コメント欄よりご指摘いただければ、確認のうえ修正いたします。

コメント

タイトルとURLをコピーしました