実行ファイルはSQLiteデータベースである

TL;DR: Farid Zakariаは ELF 形式の実行ファイルを SQLite データベースで置き換えるプロトタイプ「SELF」(Structured Executable & Linkable Format) を開発し、723 個の実行ファイルと 400 個の共有ライブラリを 1 つの SQLite ファイルに統合することで、644.4 MiB の ELF ファイルより小さい 611.9 MiB のデータベースを実現した。

Farid Zakaria は、従来の ELF 実行ファイル形式を SQLite データベース形式で置き換えるプロトタイプ「SELF」(Structured Executable & Linkable Format) を開発した。この革新的なアプローチは、ELF が本質的にはデータベースであるという認識から生まれており、SQLite の構造化されたクエリ機能を活用して実行ファイルの管理と実行を実現する。

実装の詳細

SELF ファイル形式は SQLite の application_id フィールド(バイトオフセット 68)に「SELF」を刻印することで、通常の SQLite データベースと区別される。実行に必要な 2 つのコア テーブルは self_meta(ELF ヘッダのキーバリューペア)と segments(ロードイメージ)である。シンボルテーブルは複数の ELF セクションと .gnu.hash インデックスに代わる単一テーブルとインデックスで保存される。

elf2self ツールは ELF ファイルを SELF ファイルに変換し、NixOS の postFixup フック上で動作する。self-exec はインタープリタであり、libsqlite3 にリンクされた小規模な C プログラムで、データベースからプログラムヘッダとシンボルテーブルを取得する。self-ld は概念実証として SQL のみで動的リンクを実装し、glibc rtld-audit インターフェースを使用して共有オブジェクトのルックアップをインターセプトし、SQL クエリで ライブラリ解決質問に応答する。

パフォーマンスとサイズの比較

ストリップされた coreutils の SELF は 1,794,048 バイトで、ELF の 1,768,632 バイトとの差は 1% である。SQLite を開いてインタープリタを開始するまでの固定オーバーヘッドは約 5 ミリ秒である。ベンチマークでは 15 KiB の hello バイナリと 47 個のライブラリをリンクする 42 MiB の gdb、27 個のライブラリを持つ 274 KiB の curl、5 個のライブラリをリンクする 4.6 MiB の git が使用された。

SELF バイナリは mmap された ELF ファイルのようにプロセス間でテキストページを共有しない。これは b-tree からバイトがコピーされてマッピングされないためである。一方、self closure はバイナリとその推移的依存関係を 1 つのデータベースに詰め込み、依存関係の辺を解決する。ls 実行ファイル closure は 5 個のライブラリと計 6 個のオブジェクトを含む 4.8 MiB ファイルに収まる。

ユーザーランド全体への適用

システム PATH から 723 個の実行ファイルと 400 個の異なる共有ライブラリが 1 つの SQLite ファイルに統合され、1,123 個のオブジェクトと 346,386 個のシンボルが含まれた。ユーザーランド データベースは 611.9 MiB で、等価の ELF ファイル 644.4 MiB より小さく、1,123 個のオブジェクト全体で b-tree オーバーヘッドはおよそ 6% である。同じ 723 個のプログラムを AppImage モデルを使用してプライベート closure で配布する場合、合計 5.53 GiB となる。

399 個の sonames を持つオブジェクトのうち、345 個の異なる sonames が存在し、実行ファイル間での重複排除が実現されている。libsystemd.so.0、libpthread.so.0、libgcc_s.so.1、libc.so.6 はそれぞれ 3 回オブジェクト内に出現する。ユーザーランド データベース内の依存関係の辺は 3,808 個で、ld-* ライブラリを除く未解決の依存関係の辺は 4 個である。

利点と新しい可能性

Zakaria は 「ELF はデータベースを認めようとしないデータベース」と論じ、ELF は文字列インターニング、インデックス作成、スキーマテーブル、外部キーなどのデータベース プリミティブを手作業で再実装していると指摘した。形式が SQL ベースであることで、従来のコマンドは新しく理解される。「strip は DELETE と VACUUM、patchelf は UPDATE、ldd は JOIN」となるのである。

また、LD_PRELOAD は環境変数ではなくテーブルの行として実装でき、トランザクションを通じた原子的な変更が可能になる。「interpose a tracing malloc everywhere, then ROLLBACK is a single transaction」というアプローチにより、デバッグやプロファイリングが簡潔になる。

形式は ELF との間でロスレスのラウンドトリップが可能であり、コードは GitHub の fzakaria/selfdb で公開されている。nix run .#self-vm では、hello が SQLite データベースであるような NixOS VM をブートできる。

Zakaria は arXiv:2405.03883 として当概念に関するペーパーを執筆した。

この記事は元記事の事実のみに基づいて自動生成されました。

筆者の見立て

• ELF を SQLite で置き換えることが可能であると論じている
• 必要な情報すべてが SQLite データベースで表現できると予想している
• オーバーヘッドをさらに償却する興味深い方法が存在すると予想している
• データベースアプローチにより、多くのオブジェクト全体で b-tree コストがほぼ無視できるようになると解釈している
• LD_PRELOAD をトランザクションとして切り替えることが有意な改善であると論じている
• Nix は Linux カーネルに至るまで世界を再構築できるような急進的なアイデア探索を可能にすると解釈している
• このアイデアが読者にとって筆者と同じくらい興味深いことを望んでいると述べている

出典

Farid Zakaria's Blog「Your executable is a SQLite database」https://fzakaria.com/2026/08/23/your-executable-is-a-sqlite-database (arXiv:2405.03883 の報道による)