データベースやSQLの学習のため、データが欲しかった。Pwned Passwords listという5億件を超えるデータがある。よし、データベースに突っ込もう、と思い立った。因みに検索した範囲で扱っている最も大きなデータは8000万件で、それ以上となると殆ど見当たらない。このことを知るのは作業を開始した後である。
よくよく考えれば当たり前の酷く間抜けなミスをしたが、調べた範囲内にその間抜けなミスを指摘していたものが無かったので他の人のためになればと記録に残しておく。**予め書いておくが本当に間抜けなミスである。**気付かない方がどうかしてる。
「データベース初心者に対して教える人」向けにどのような経緯でこのミスをしたのか、気付かなかったのか分かりやすくするため、時系列順に記述します。結論は最後に書くので、結論だけ知りたい方はすっ飛ばして結論だけご覧ください。
前提
- データベースに関する知識
- り、りろんはしってる
- C#に関する知識
- 最近Streamクラスと言うのを覚えた。
- 英語に関する知識
- グーグル翻訳様万歳
応用情報を持ってるが実践はしたことがない奴と言えば大体合ってる。
そもそもPwned Passwords listとは
555,278,657件の漏洩したパスワードのハッシュと各パスワードの漏洩件数のリストである。Have I Been Pwned: Pwned Passwordsで公開されている。
作業開始
正直、時間が掛かりすぎて検索履歴から作業時間を割り出してるので誤差は大きい。あまり関係ないところは飛ばしている。
0分～
Pwned Passwords listのダウンロード
一番上のをダウンロード。.7zなので7-Zipで解凍する。ダウンロード自体に数時間かかる。
SQLiteのダウンロード
SQLiteからPrecompiled Binaries for Windowsをダウンロード。PATHは通しておく。
テーブルの作成
DB Browser for SQLiteを使用してテーブルを作成。
CREATE TABLE "passwordhashs" (
"hash" TEXT NOT NULL,
"prevalence" INTEGER NOT NULL,
PRIMARY KEY("hash")
);
CSVファイルのインポート
Windows PowerShellを使用してPwned Passwords listをインポートする。区切り記号が:であることに注意。デフォのファイルネームが長いので雑にリネームした。
>sqlite3 password-hashs.db
>.separator :
>.import password-hashs.csv passwordhashs
30分～
全然終わらない。タスクマネージャーでCSVのファイルサイズ24GBとディスクの書き込み速度6MB/sを見比べる。何年かかるんだ？
実のところ理由はもう出ているのだが全く気付かず模索。SQLite 高速化、書き込み速度、巨大、なんて単語で検索。
PRAGMAを変更すると早くなるらしい。
×ボタンで雑に終了。当然データベースは破損。復旧方法を探す。破損したSQLiteのファイルを修復するを発見。
>sqlite3 password-hashs.db .dump | sqlite3 new.db
C#でPRAGMAとやらを設定してデータベースに書き込む。
C#でSQLite3を使ってみるを参考にした。SQL文を直接書いて実行したほうが早いようだ。
public class CsvToDatabaseConvert {
const int MAX_READ_LINE_LENGTH = 100000;
const string DATABASE_NAME = @"./password-hashs.db";
const string CSV_NAME = @"./password-hashs.csv";
static void Main(string[] args) {
try {
var prg = new CsvToDatabaseConvert();
Console.WriteLine("Start");
prg.Go(DATABASE_NAME, CSV_NAME);
} catch(Exception e) {
Console.WriteLine(e.ToString());
Console.ReadKey();
}
Console.WriteLine("Press any key to exit...");
Console.ReadKey();
}
private void Go(string dbName, string csvName) {
//SQLite設定
var builder = new SQLiteConnectionStringBuilder() {
DataSource = dbName,
Version = 3,
LegacyFormat = false,
SyncMode = SynchronizationModes.Off,
JournalMode = SQLiteJournalModeEnum.Memory
};
//Database,CSVFileオープン
using(var db = new SQLiteConnection(builder.ToString()))
using(var file = new FileStream(csvName, FileMode.Open, FileAccess.Read, FileShare.Read, 65536))
using(var csv = new StreamReader(file)) {
db.Open();
SkipCSV(db, csv);
WriteDatabase(db, csv);
db.Close();
}
}
//DBから入力済みの行数を取得し、読み飛ばす。
private void SkipCSV(SQLiteConnection db, StreamReader csv) {
long len = context.GetTable<PwnedPasswordsRow>().Count();
for(long i = 0; i < len; i++) {
csv.ReadLine();
}
}
private void WriteDatabase(SQLiteConnection db, StreamReader csv) {
//CSVFile終端まで繰り返し
while(!csv.EndOfStream) {
InsertRowsMultiple(db, csv);
Task.Run(() => Console.Write('.'));
}
}
private void InsertRowsMultiple(SQLiteConnection db, StreamReader csv) {
using(var command = new SQLiteCommand(db)) {
command.Transaction = db.BeginTransaction();
var sb = new StringBuilder();
sb.Append("insert into passwordhashs values");
long i = 0;
while(i < MAX_READ_LINE_LENGTH && !csv.EndOfStream) {
var row = new PwnedPasswordsRow(csv.ReadLine().Split(':'));
if(row.hash == null)
continue;
sb.Append("(" + $"'{row.hash}', {row.prevalence}),");
i++;
}
sb.Remove(sb.Length-1,1);
sb.Append(";");
command.CommandText = sb.ToString();
command.ExecuteNonQuery();
command.Transaction.Commit();
}
return;
}
}
[Table(Name = "passwordhashs")]
public class PwnedPasswordsRow {
public PwnedPasswordsRow(string[] v) {
hash = v[0];
prevalence = int.Parse(v[1]);
}
public PwnedPasswordsRow() {}
[Column(Name = "hash", CanBeNull = false, DbType = "TEXT", IsPrimaryKey = true)]
public string hash { get; set; }
[Column(Name = "prevalence", CanBeNull = false, DbType = "INT")]
public int prevalence { get; set; }
}
8時間後～21時間後
適当に放置。思い立ったタイミングで、中断処理だったり経過時間を表示したりを追加。全然終わらない。ディスクの書き込み速度は0.3MB/sまで低下。なぜだ。
CSVファイルを読み飛ばすためにCountで行数を調べているので更新のため中断する度一々O(n)時間掛かる1テキストファイルに読み込んだ行を書き込んでおくことを思いつく。
1日後
ようやくどこの処理に時間が掛かってるのか調べる。
command.ExecuteNonQuery();
command.Transaction.Commit();
コミットの辺りですごい時間が掛かってることが判明。CSVの読み込みに時間が掛かってるんじゃないかと調べてたのは無駄でした。
11日後
経過がわかりやすいようにといろいろ改造しつつ、このあたりで8000万件ぐらい。なんだか自分の寿命のほうが先に来そうなことからは必死に目を背ける。この間ずっとHDDがカリカリ言ってる。
10万件入れるのに30分ほど掛かる。
14日後
ふとPRIMARY KEYはInsertの度に格納されているデータを全て調べているのではと思い立つ。400万件のテストデータで試してみる。
| PK有り | PK無し |
|---|---|
| 144806166 | 114177699 |
ちょっと早い。PRIMARY KEYを外して試してみる。めっちゃ早い。10万件ごとに打たれるドットがズラーと並ぶ。
結論
CREATE TABLE "passwordhashs" (
"hash" TEXT NOT NULL,
"prevalence" INTEGER NOT NULL,
PRIMARY KEY("hash")
);
PRIMARY KEY("hash")が全ての原因でした。2週間以上掛かったのは何気なくチェックボックスをクリックしたせいです。**PRIMARY KEYはInsertするたびに同じフィールドがないか調べます。**つまりO($n^2$)時間かかるのです。
PKのチェックボックスを外して試してみると、30分程で終わりました。
因みに
PRIMARY KEYの設定をInsert終了後にやったらヒープソートのO($nlogn$)位に下がるのでは？ と夢見て思って試したところ普通に固まりました。
-
ここで気付くべきだった。 ↩