時計屋

このTweetが発端

めんどいので、　AHundredGigaSort といってみる。

CSVファイルの仕様

とのことだったので、以下のように仕様を決めた

UTF-8でEncodingされる
ヘッダは含めない
最終行も改行する
IDは0>=ID>99999999 の値域を取る
重複は存在しない。
ValueはDoubleQuoteやCommaが存在しないランダムな文字列を生成
その際、UTF-8の表現で3byteのみ
改行は\n

早い話が、レコードサイズが3,010バイト固定かつ決め打ちで何処に何があるかすぐ分かるファイル形式とした。

時計屋

ダミーデータ作ってみた

以上の仕様ので36,000,000レコードほどこさえてみたらちょうど100Gbiになったのでこいつを使うことにした。
100Gbiのデータぶん投げるとかどう考えても狂気の沙汰なので、後日Generatorを公開する予定

時計屋

検証してみたいこと

上記データ柄って検証してみたいことをいくつか

最初に僕が考えた方法

KeyとRecordのOffsetをインメモリで管理してSortして書き出す方法

Pros

Write I/Oが一発で済む
固定長にしてるので読み取りも決め打ちでかけることが可能

Cons

Read I/Oがランダムアクセスになる

Yohhoyセンセの方法

インメモリで読めるブロックに区切ってその後マージソートしていく形になると思う。

Pros

Write/Read　I/O共にシーケンシャルアクセスになる。

Cons

複数回のDiskI/Oが発生する

DBMSにぶん投げる

割と優勢だった意見。僕個人的にはワーストケースだと思ってる。（特にSQLite使ったら）
RaspPi4 8GBモデルに128GBiのSSDを2枚指してそいつをRaid0にした上でPostgreSQL使って試してみることにする。
併せて、ローカルでSQLite使った場合も同様に検証する

時計屋

実行環境

Source/Soted共々HDDにおいておく
どっちも同じ物理ストレージ
環境の詳細は追々

検証前（2022/09/01）の予想

実はソートアルゴリズムとかどうでも良くて、ひたすらI/OのThroughputを稼げるかがキモになると思う

時計屋

予備調査

360RecordsほどPostgreSQLにぶち込んでみた。

PrimaryKeyは指定しない。
Indexも張らない
COPYでBulkInsertする
Insert終了後にIndexを張る

Insertだけで約13分かかっている

時計屋

詳細

Writeback after In memory key sort

Logging

キー読み出し
- Period:32,768
Sort
書き戻し
- Period:32,768

Merge sorting after the initial block sort

ブロックソートは16分割
- 2.25MRecord/Block
Ping-Pongで書き出す
- ReadとWriteを物理的に別のStorageで行う

Logging

Block sort
- Per block
MergeSort
- Per sort

RDBMS

Logging

BulkInsert
- Period:32768
Indexing
Writeback.

時計屋

Memo

Key/Valueで構築するのではなくてI/O稼ぐためにKey/BinaryDatumのほうが良いかもしれない（2022/09/03対応済み）
FileStreamのBufferSizeをOptimizeすべき（RecordSizeと一致させるのが良いと思う）（2022/09/03対応済み）
I/OでStorageが物理的に分かれているので、Channel使って非同期化した方が稼げる気がする

時計屋

で、試してみた結果

UASPがRaspberry Pi4というかUbuntuというかLinuxでまともに動かなかった(後述

時計屋

実行環境

共通事項

ReadとWriterでStorageを分けた
ソート結果の書き戻しは並行的に行った

Raspberry Pi4

前述の通りなのでUSB Mass storageモードで走らせる

PC(Windows

元々やるつもりはなかったけど、UASPで走らせたときの結果を見てみたかったので試した。

時計屋

	multi_uasp	multi_usb	single_usb
insert	436	581	632
sort	11	13	13
write	14314	18043	21177

以上のことから、圧倒的にソート済みデータを書き戻す作業二時間がかかっている。
SingleとMultiの差は、Singleがある程度バッファリングしてから同期的に書き戻す手法をとった場合になっている。
この場合でもさほど効率が悪化しないのは書き戻す作業(Write)はシーケンシャルに行われるのでディスクキャッシュが相応に効いている物と考えられる。

時計屋