HN 日本語サマリー

← 一覧へ戻る
プログラミング

F*ファイルシステム – OSカーネルをバイパスしてSSDを直接読み込むファイル検索

F* file system – file search that reads SSD directly bypassing OS kernel (github.com)

89 pointsby neogoose44 コメント

要約

FFSは、OSカーネルを介さずにディスクを直接読み込むことでファイルを検索するCLIツールです。これは実用性よりも面白さに重点を置いており、特に大規模なファイル検索において既存のツール(ripgrepなど)よりも高速になる可能性があります。macOSではSIPの無効化が必要な場合もありますが、非マウントボリュームの検索も可能です。

全文翻訳

FFS - F* File System

これは、ファイルを検索する(grepのような)CLIツールで、OSカーネルを使わずにファイルを読み取ります。実用的ではありませんが、非常にクールです。

これはわずか約1.5k行のCコードで、以下のことを行います。

  • 生のデバイスノード(例: /dev/rdisk*)を読み取る場合にのみsudoが必要(イメージファイルを検索する場合は、管理者権限は不要です)。
  • メインのmacOSディスクで実行するには、SIP保護を無効にする必要があります。
  • 一部の最近のファイル書き込みを見逃す可能性があります(手動での sync コールが必要になります)。
  • OSで他のシステムコンポーネントがファイルを書き込んでいる間に、非常に揮発性のファイルシステム上のツリーを検索できない可能性があります。
  • このプロジェクトで手動で実装されたファイルシステムでのみ動作します。

しかし、同時に

  • ディスクから直接ブロックを読み取ります。
  • VFS / バッファリングされた read() パスをバイパスし、代わりにブロックデバイスを直接 pread します。
  • ripgrepよりも段階的に高速になります(検索するファイルが多いほど、ripgrepよりも高速になります)。
  • マウントされていないボリュームを検索できます - バイナリブロブを解析するだけです。
  • バイナリファイルを検出し、スキップします。
  • openmpを介して、すべてのコアに負荷を分散します。

実際に動作する高速なファイル検索については、私のプロジェクト fff をチェックしてください - sudoを必要とせずに、ripgrepを大幅に上回ります。

サポートされているファイルシステム

Linuxでは、ほとんどのファイルシステムは実装が容易です。

Ext4

./fs/ext4.c

これは最もサポートしやすいファイルシステムです。ジャーナリングファイルシステムで、インプレース書き込み(コピーオンライトなし)を行うため、ほとんどの場合ffsにとって最良のファイルシステムです。時々、ffsがファイルの最近の更新の一部を見ることができない場合があります。これは、カーネルが最近の更新をキャッシュに保持し、ディスクへの書き込みを遅延させている場合に発生する可能性があります。同期を強制するには、以下を使用できます。

sync
Btrfs

./fs/btrfs.c

Bツリーファイルシステムは、はるかに複雑で、より効率的なファイルストレージであり、追加の制限があります。

ファイルシステム上のファイルが更新されると、スーパーブロック全体も更新が必要になります。これは、ffsがスーパーブロック(高レベルBツリー)を読み取った後、カーネルがツリーを更新した場合、読み取り全体が無効になることを意味します。

これは、fsfreeze を使用するか、別の分離されたボリュームを作成することで回避できます。

Apfs (MacOS)

./fs/apfs.c

APFSはAppleによって実装されたプロプライエタリなファイルシステムで、リバースエンジニアリングされており、ここでもサポートされていますが、Appleはセキュリティポリシーを大幅に強化しています。

SIPを無効にしない限り、メインディスクでffsを実行することはできません

SIP(System Integrity Protection)は、rootユーザーとしてもメインディスクのスーパーブロックへのいかなるアクセスも禁止する特別なセキュリティ機能です。sudoを使っても回避できません。この機能を無効にする必要があります(yabaiのようなプロジェクトを使用している場合は、すでに無効になっているかもしれません)。

メインディスクに触れることなく、Appleファイルシステムでffsをテストする方法があります。管理者権限なしで、生の .dmg ファイルを検索できます(はい、アプリインストーラーは単なる分離されたボリュームです)。ffsを使用すると、何もマウントする必要はありません。ボリュームの生のバイトへのパスとファイルシステムタイプを渡すだけです。

ffs "<QUERY>" /path/to/volume.dmg apfs

分離されたボリュームでの検索

ffsはバイトを直接読み取るため、マウントせずに任意の分離されたボリュームを検索するために使用できます。例: .iso または .dmg ファイルの読み取り。

スピード

これが最も面白い部分です - ffsはVFS / カーネルファイルシステムキャッシュにアクセスできません。そのため、小さな(またはすでにキャッシュされている)ディレクトリでは遅くなりますが、キャッシュが枯渇し、カーネルが実際のディスク状態を読み取る必要が出てくると、段階的に速くなります。

なぜか?カーネルVFSがオーバーヘッドになる時点を証明するためです。

これは、btrfsマウントされたドライブでffsとripgrepを比較した検索結果です。ripgrepははるかに高度なSIMDベースのマッチャーとファイルウォーカーを使用していますが、ffsは約1.8k行のCコードにすぎません。

[repos — 631k files]
  ffs |####                                              | 5.505s
  rg  |###                                               | 4.813s

[dev — 1.50M files]
  ffs |############                                      | 18.413s
  rg  |#################                                 | 25.673s

[home — 3.25M files]
  ffs |########################                          | 36.205s
  rg  |##################################################| 74.690s

ripgrepに使用されたフラグは -F --no-heading -H -n --no-ignore --hidden --one-file-system --no-messages で、ffsと同じ結果を出力させます。

プロジェクトのビルド

プロジェクトをコンパイルするために必要なのは、btrfs用のlibzstdと、pkg-configでのopenmpだけです。その後、単純に

make ffs
ffs --help