世界を動かす技術を、日本語で。

Show HN: Zeekstd – ZSTDシーク可能フォーマットのRust実装

概要

  • Zeekstd はRust製のZstandard Seekable Format実装ライブラリ
  • 圧縮データを 独立したフレーム 単位で管理し、部分展開が容易
  • CLIツール も同梱し、通常のzstdツールと類似の使用感
  • C実装の制約を解消し、 高度なAPI を活用
  • BSD 2-Clauseライセンスで オープンソース公開

Zeekstd: RustによるZstandard Seekable Format実装

  • Zeekstd は、Rustで書かれた Zstandard Seekable Format の実装ライブラリ
  • Seekable Formatは、圧縮データを 独立した複数フレーム に分割管理
    • アーカイブ中間部の展開時、 必要最小限のフレームのみ展開 可能
    • 通常のzstd圧縮ファイルは 単一フレーム、全体展開が必要
  • 初期仕様との互換性 を維持しつつ、アップデートされた仕様を実装
  • 圧縮時、デフォルトで 2MiBごとに新フレーム自動生成
    • オプションで フレームサイズ等の調整 が可能

圧縮処理例(Rustコード)

  • ファイルを seekable.zst として圧縮保存
  • 圧縮終了時に シークテーブル を末尾へ書き込み
use std::{fs::File, io};
use zeekstd::Encoder;

fn main() -> zeekstd::Result<()> {
    let mut input = File::open("data")?;
    let output = File::create("seekable.zst")?;
    let mut encoder = Encoder::new(output)?;
    io::copy(&mut input, &mut encoder)?;
    encoder.finish()?; // 圧縮終了とシークテーブル書き込み
    Ok(())
}

展開処理例(Rustコード)

  • デフォルトで 全フレーム展開
  • 特定フレームのみ展開 する設定も可能
use std::{fs::File, io};
use zeekstd::Decoder;

fn main() -> zeekstd::Result<()> {
    let input = File::open("seekable.zst")?;
    let mut output = File::create("decompressed")?;
    let mut decoder = Decoder::new(input)?;
    io::copy(&mut decoder, &mut output)?; // 全体展開

    let mut partial = File::create("partial")?;
    decoder.set_lower_frame(2);
    decoder.set_upper_frame(5);
    io::copy(&mut decoder, &mut partial)?; // フレーム2〜5のみ展開
    Ok(())
}

CLIツール

  • コマンドラインツール を同梱
  • ライブラリ同様の seekable圧縮・展開 処理が可能

ライセンス

  • zstd Cライブラリ はBSD/GPLv2のデュアルライセンス
  • Zeekstd はBSD 2-Clauseライセンス

開発背景と経緯

  • 通常のzstd圧縮ファイルは 単一フレーム構造
    • 途中から展開できず、 先頭から全体展開が必須
  • 大容量ファイルのダウンロード再開や部分展開 要件から、seekable formatに着目
  • C実装(upstream/contrib/seekable_format)を バインディング利用 も、機能制限・API非推奨・メンテナンス性に課題
  • Rustによる完全な再実装 を決意
    • zstd 1.4.0以降 の高度な圧縮APIを活用
  • 単一依存のライブラリクレート と、 CLIクレート を公開
    • CLIは 通常のzstdツールと同等の使用感

参考リンク


フィードバックのお願い

  • 利用者からのフィードバック を歓迎
  • 不具合報告や要望 の受付

主な特徴まとめ

  • 部分展開に最適なZstandard圧縮 のRust実装
  • 高い互換性柔軟なフレーム制御
  • CLIツール同梱 で即利用可能
  • BSD 2-Clauseライセンス によるオープンソース提供

Hackerたちの意見

https://www.htslib.org/doc/bgzip.html

ありがとう!シーク可能なフォーマットを扱うツールがほとんどないのには驚いたよ。少なくとも何人かは使い道があると思うんだけど。そうそう、名前はzstdとseekの組み合わせなんだ。面白いことに、最初は「zeek」って名前にしたかったんだけど、すでに存在することを知らなくて、zeekstdに変更したんだ。zeekとの関係を聞いてくる人は君が初めてじゃないし、それが誤解を招くのは理解できるよ。振り返ると、名前はちょっと残念だね。

これいいね!この分野で一番よく使われてるツールはbgzipだと思うよ。各ファイルの最初の数チャンクで辞書をトレーニングして、スキップ可能なフレームにその辞書を埋め込むことを考えたことある?チャンクサイズが2MBならあまり影響ないかもしれないけど、小さいサイズだとかなり効果があるかも。

スペックを見たけど(https://github.com/facebook/zstd/blob/dev/contrib/seekable_f...)、君が言ってるようなカスタム辞書については言及されてないね。スペックにはこう書いてある:> 現在存在するのはChecksum_Flagだけだけど、このフィールドには将来のフォーマット変更に使える7つのビットがある。例えば、インライン辞書の追加とか。だから、シーク可能なzstdはまだこれらの辞書をサポートしてないと思う。複数のインライン辞書があれば、新しいチャンクが前の辞書でうまく圧縮できないときに検出して、リアルタイムで新しい辞書をトレーニングできるかも。ヘッダーや混合データを持つフォーマット(ゲームファイルとか、テキスト+音声+動画の混合、あるいは普通の.tarファイルとか)を圧縮するのに役立つかもしれないね。

シーク可能なフォーマットはランダムリードも可能だから、リモートホストの圧縮ファイルからqemu VMを起動するみたいなトリックができるんだよね(HTTPS経由で)。俺たちはもうxzでこれをやってるよ: https://libguestfs.org/nbdkit-xz-filter.1.html https://rwmj.wordpress.com/2018/11/23/nbdkit-xz-curl/ zstdは実際にシーク可能なバージョンを標準化したの?最後にチェックしたとき(かなり前だけど)、まだ標準とはされてなかったから、nbdkit用のフィルターを書くのに躊躇してたんだ。リクエストは結構ある機能なのにね。

私の知る限りでは、標準化されてないね。

俺はすでにプロジェクトでzstd_seekable(https://docs.rs/zstd-seekable/)を使ってるよ。このクレートと君のやつのAPIを比較してくれない?

もし間違ってたら教えてほしいんだけど、zstd_seekableには特定のオフセットでデコンプレッションするSeekable::decompressに相当するものがないみたいだね。これがあれば、どのフレームをデコンプレッションするか計算しなくて済むから、俺はこれをzstd_seekableから使ってるんだ。だから、zeekstdにもそれがあったら嬉しいな。

最近、シーク可能なzstdでファイルを圧縮するためのツールサポートはどうなってるの?既存のライブラリを考えると、圧縮データベースを透過的に読み取るSQLite VFSをGoドライバー用に作るのはすごく簡単なはずなんだけど、ツールサポートがちょっと不足してるんだ。zstd CLIはいつかそれをサポートするのかな? https://github.com/facebook/zstd/issues/2121

参考までに、zeekstdにはCLIツールが付いてるみたいだよ: https://github.com/rorosen/zeekstd/tree/main/cli

フレームにはコストがかかると仮定した場合、シーク可能なzstdファイルはどれくらい大きくなるんだろう?フレームサイズやデータの種類(テキストやバイナリなど)に基づいたグラフがあればいいな。

それはコンテンツや圧縮オプションによるよ。ZSTDには4つの異なる圧縮方法があって、Raw literals、RLE literals、Compressed literals、Treeless literalsがあるんだ。最後の2つは、コンテンツが分割されると特に影響を受けると思う。

選ぶフレームサイズによるね。フレームごとに追加のメタデータが数バイト必要なんだけど、正確にどれくらいかは他の圧縮設定による(例えば、フレームのチェックサムは4バイトで、これが有効になってる場合だけ存在する)。1Gのファイルで圧縮レベル3でテストしたら、zstdは559Mに圧縮したけど、zeekstdは2Mのフレームで565Mになった。フレームサイズを4Mに増やすと、zeekstdは562Mになるよ。READMEにセクションを追加するつもり。これは他の人も気になるいい質問だね!

シーク可能なzstdフォーマットについてもっと学ぼうとしてるんだけど、zstdについては数週間前に仕様書を読んだくらいしか知らないんだ。でも、これって仕様書の一部じゃなかったっけ?確か、zstdファイルは1つのフレームだけでなくてもいいんだよね。ファイルに対して1つの大きなフレームが標準なのかな?それとも複数フレームのバージョンはあまり一般的じゃないの?gzipも複数の「フレーム」を連結できて、シームレスに復号できるよね。これって基本的に同じ概念なのかな?他の人も言ってたけど、bgzipはgzipのこの機能をうまく使っていて、バイオインフォマティクスでは標準的な圧縮方式になってる(残念ながら他の有用なgzip拡張を制限するようにハードコーディングされてるけど)。zstdをgzipの代わりにフォーマットの基盤として使うことが有益かどうかに興味があるんだ。圧縮率が良くなることは期待してるけど、それが本当に価値があるほどのものになるかは疑問だな。

Zstdの仕様ではストリームが複数のフレームで構成されることを許可しているけど、それだけでは効率的なシークには不十分なんだ。特定のバイトオフセットに対応する圧縮フレームを特定するためには、すべてのフレームヘッダーを読み取る必要があるよ。「シーク可能なZstd」は基本的にマルチフレームのZstdストリームで、ファイルの最後に「シークテーブル」が追加されていて、各フレームの圧縮サイズと非圧縮サイズが含まれているんだ。シークテーブル自体はスキップ可能なフレームとしてマークされているから、シーク可能なZstdは通常のZstdデコーダーと後方互換性がある(シークテーブルはメタデータとして扱われて無視されるだけ)。

ちょっとバカな質問かもしれないけど、どれくらいのフレームをスキップするかどうやって知るの?例えば、圧縮されていないファイルの10MBのところにシークしたいとするじゃん。そのためには、スキップするフレームの数を知るためにメタデータを別に保存する必要があるの?

シーク可能なZstdファイルにはシークテーブルが含まれていて、すべてのフレームの圧縮サイズと非圧縮サイズが記載されているんだ。それだけの情報があれば、目的のオフセットがどのフレームに含まれているか、そしてそのフレームの非圧縮データのどの位置にあるかを特定できるよ。

zstdについてはよくわからないけど、xzではブロック(zstdのフレーム)はファイル全体に分散して保存されていて、オフセットでリンクされた連結リストになってるから、圧縮ファイルの最初をサッとスキャンして、メモリ内に非圧縮の仮想オフセットと圧縮ファイルの位置のマップを作ることができるよ。nbdkit-xz-filterのコードはこちらだよ:

これめっちゃクールだね!ゲノムデータに役立ちそうだな。ゲノムデータはいつも圧縮されたチャンクで保存されるからね。シーク時間と圧縮の間の厳しいトレードオフを本当に理解したのはこれが初めてだったよ。

CHD(圧縮データの塊)は、シークをサポートする別のフォーマットで、LZMA圧縮もできるんだ。CDシステムのディスクイメージ用に作られてるけど、他のケースでも使えるよ。