Prolly: prollyツリー上に構築されたコンテンツアドレス指定された順序付きマップ
Prolly: A content-addressed ordered map built on prolly trees (github.com)
要約
Prollyは、Rustで書かれたコンテンツアドレス指定された順序付きマップライブラリです。不変で、キーと値のペアをバイト列で管理し、構造的な共有、差分、マージ、バルクロードを効率的に行えます。各ノードは内容に基づいて一意のアドレス(CID)を持ち、変更は影響を受けたパスのみを更新するため、効率的なバージョン管理とデータ共有が可能です。ストレージはプラグイン可能で、メモリ、SQLite、RocksDBなどがサポートされています。
全文翻訳
Prolly: prollyツリー上に構築されたコンテンツアドレス指定の順序付きマップ
Prolly は prolly Rustライブラリクレートを公開します。ユーザーは prolly-map としてパッケージに依存し、コードのインポートは use prolly::{Config, Prolly}; のように簡潔に保たれます。
このクレートは、コンテンツアドレス指定された prolly ツリーのストレージプリミティブを提供します。これは、バイトキーとバイト値に対する不変の順序付きキー/値インデックスであり、効率的な構造共有、差分、マージ、バルクロードのための安定したコンテンツ由来の構造を持ちます。
API境界では、Tree は小さな永続的なハンドルです。
root: Option<Cid>はコンテンツアドレス指定されたルートノードを指します。config: Configはツリーで使用されるチャンキングとエンコーディングパラメータを記録します。
実際のノードは、プラグ可能な Store に存在します。操作は、影響を受けるパスまたはサブツリーのみをクローンおよび書き換え、新しいコンテンツアドレス指定ノードを書き込み、新しい Tree ハンドルを返します。
ストレージバックエンドを持つツリーのすべての作業は、ランタイムに依存しない非同期ファーストエンジンによって一度実装されます。AsyncProlly<S: AsyncStore> はこれを直接使用します。Prolly<S: Store> は、インラインの読み取り専用アダプターを介して同じ完全な操作を駆動します。同期パスはランタイムを作成せず、スレッドをパーキングせず、Tokioにストアコールをディスパッチしません。
アーキテクチャ
[画像: Prolly tree architecture]
同じ図は、ラスター画像を好むコンテキストのために diagram/prolly-tree-architecture@2x.png としてもレンダリングされます。
完全なエンドユーザー向けドキュメントセットは docs/ にあり、開始ガイド、チュートリアル、クックブックのレシピ、アーキテクチャ、設計仕様、実装ノート、ロードマップ、言語ポートガイドが含まれています。正規のクックブックは docs/cookbook.md です。ネイティブの近似最近傍検索インデックスは docs/proximity-map.md に文書化されています。破壊的な変更とリリース資格は CHANGELOG.md に記録されています。
インタラクティブビジュアライザー
3rd/prolly-tree-visualizer のブラウザアプリは、このリポジトリの実際の prollydb-wasm バインディングに対してミューテーションを実行し、結果のコンテンツアドレス指定ツリー、ルックアップパス、構造差分、およびストレージ履歴をレンダリングします。
prollyツリーの上にGitのようなリポジトリレイヤーを構築したいアプリケーションビルダーについては、提案されている prolly-vcs 設計 を参照してください。これは prolly-map を不変順序付きマップに集中させながら、コミット、参照、リファログ、パッチ、マージオーケストレーション、同期計画、およびリポジトリレベルのGCのための汎用バックエンドニュートラルな KvStore 基盤を持つ別のクレートを概説しています。
このクレートが提供するもの
- 文字コード順のバイトキー検索。
- 不変更新:
put、delete、batchは新しいTreeを返します。 - コンテンツアドレス指定ノード: 各ノードCIDは、決定論的なノードバイトのSHA-256ハッシュです。
- xxHash64境界チェックを使用した決定論的なコンテンツ定義チャンキング。
- 変更されていないノードが同じCIDを保持するため、バージョン間の構造共有。
- CIDと無関係な子スパンを削除することによる効率的な差分と範囲差分。
- 競合リゾルバーをサポートする3者マージ。
- CRDTスタイルの競合フリーマージ戦略。
- 遅延範囲イテレーションとカーソルベースのトラバーサル。
- ソート済み、グループ化済み、追加負荷の高い、マルチリーフ書き込みのためのバッチミューテーションパス。
- 大規模な初期ツリーのための並列バルクビルダー。
Storeトレイトを介したプラグ可能なストレージ。メモリ、SQLite、およびオプションのRocksDB実装が含まれます。- Merkleスタイルの欠落ノード計画とストア同期のためのコピーヘルパー。
- ブランチ、タグ、チェックポイント、カスタムルートのスナップショット名前空間ヘルパー。
- 自動ヘッド、不変コンテンツ由来バージョン、ピン留めされた読み取り、証明、比較とマージ、バックアップ/同期、型付きコーデック、サブスクリプション、マルチマップトランザクション、バウンド履歴、スコープ付きGCを備えたトランザクションセーフな
VersionedMapファサード。 - ランタイム定義の非ユニークなセカンダリインデックスのための厳密な
IndexedMapコーディネーター。単一ルートアトミック公開、有限操作予算、スパースおよびマルチバリュー項、KeysOnly/Include/Allプロジェクション、正確な履歴スナップショット、永続ピン、安全なGC、構造化診断、検証済みバウンド転送。アプリケーションは、ProllyまたはAsyncProllyの同じengine.indexed_map(...)シェイプを介してこれを開きます。両方のパスは同じ正規状態フォーマットと厳密なトランザクションルート公開を使用します。ネイティブ非同期サポートは、PostgreSQL、MySQL、Redis、Turso、DynamoDB、Cosmos DB、Spannerでファーストクラスであり、ブロッキングアプリケーションが必要な場合は同期ファサードが利用可能です。 - ツリールートのストア独立単一キー、共有マルチキー、完全範囲、カーソルページ、および差分ページ証明。
- ツリーの形状、充填率、ファンアウト、およびシリアライズサイズを検査するためのツリー統計。
- 正確なルックアップ、フィルタリングされたベストファースト検索、ローカライズされた正規COW、オーバーフロー/外部ベクトル、SQ8/PQ/HNSWアクセラレーション、非同期/SIMD実行、型付きレプリケーション/GC、およびディスクリプタバウンド証明を備えたハードカット決定論的近傍マップ。
クイックスタート
use prolly::{Config, MemStore, Prolly};
let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let tree = prolly.create();
let tree = prolly
.put(&tree, b"name".to_vec(), b"Alice".to_vec())
.unwrap();
let value = prolly.get(&tree, b"name").unwrap();
assert_eq!(value, Some(b"Alice".to_vec()));
let tree = prolly.delete(&tree, b"name").unwrap();
assert!(prolly.get(&tree, b"name").unwrap().is_none());
すべての更新APIは永続的です。ストアが参照されているノードをまだ保持している限り、古い Tree ハンドルは有効なままです。
スタンドアロンチェックアウト
このディレクトリは独自のレポジトリとして開くことができます。このツリーの下にあるRustマニフェストは、独自のパッケージメタデータ、依存関係バージョン、およびリンティング設定を宣言します。
リポジトリのルートからコアクレートを実行します。
cargo check --all-targets
cargo test
cargo run --example basic_map
プロバイダーストアとRustバインディングはネストされたパッケージにあります。--manifest-path でチェックします。
cargo check --manifest-path stores/prolly-store-redis/Cargo.toml --all-targets
cargo check --manifest-path bindings/uniffi/Cargo.toml --all-targets
cargo check --manifest-path bindings/wasm/Cargo.toml --target wasm32-unknown-unknown
コピー可能な例は examples/ にあります。
agent_event_log.rs: メッセージ、ツール、メモリ書き込み、チェックポイント、およびサマリーのための追加負荷の高いエージェントイベントログ。background_compaction.rs: リテンションを考慮したイベントログのコンパクション、サマリーインデックスの再構築、およびGC。basic_map.rs: put、get、delete、および範囲スキャン。batch_build.rs: バルクビルドとツリー統計。diff_merge.rs: 差分と競合フリーの3者マージ。resolver.rs: 削除を考慮したマージリゾルバー。secondary_index.rs: 厳密なIndexedMapインデックスの宣言、構築、クエリ、検証、置換、保持、エクスポート、およびインポート。indexed_map_real_world.rs: ステータス、顧客、テナント、時間、スパース、マルチバリュー、カバリング、パス、ジオスペース、テキスト、および履歴インデックスの14のプロダクション形状パターンを実行します。materialized_view.rs: ソース差分からマテリアライズドビューを派生および更新します。ソース/ビューのルートはマニフェストにあります。crdt_merge.rs: LWW、マルチバリュー、削除/更新、診断、およびベースを考慮したカスタムマージの例。conversation_memory.rs: 正規のメモリルート、エージェント試行ブランチ、マージ、およびCAS公開。deterministic_rag_snapshot.rs: 再現可能なRAG回答とロールバックのために正確なインデックスルートを記録します。document_chunk_index.rs: ドキュメント/チャンクキーの規約、ブロブバックドテキスト、およびベクトルサイドカーID。vector_sidecar.rs: prollyルートが検索メタデータを保持している間に、埋め込みをサイドカーベクトルエンジンに保持します。versioned_map.rs: アトミック編集、履歴、差分、ロールバック、およびリテンションのための組み込み管理マップファサードを使用します。provenance_values.rs: ソース、パーサー、埋め込み、モデル、親チャンク、およびCIDの来歴を運ぶ値。file_blob_store.rs: 永続的なブロブオフロードとブロブGC。filesystem_snapshot.rs: ファイルブロブと名前付きルートを持つGitのようなファイルシステムスナップショット。
アダプター固有の例には semantic_rag.rs があります。これは、完全にオフラインの1,536次元 ProximityMap で、コーパスと名前付きディスクリプタをSQLiteに永続化し、プロセス実行をまたいで再オープンし、ランク付けされたRAG引用とLLM対応コンテキストブロックを発行します。
スタンドアロンの prolly-gluesql 統合は、完全なGlueSQLデータベースを単一のトランザクションProllyツリーに変換します。永続的なブランチ、不変バージョン、セカンダリインデックス、論理差分、履歴読み取り、およびオプションのSQLiteバックエンドCLIが含まれます。
ネイティブRustストアアダプターは stores/ の下にあります。prolly-store-turso アダプターは、ローカルストレージのためにネイティブ非同期Tursoデータベースエンジンを埋め込み、オプションで sync Cargo機能の背後にある明示的なTurso Cloudプッシュ/プルを公開します。
主要ヘルパー
キーは生のバイトであり、文字コード順にソートされます。アプリケーションレベルのスキーマには、KeyBuilder を使用してセグメントセーフな複合キーを構築し、prefix_range を使用して論理名前空間をスキャンします。
use prolly::{prefix_range, Config, KeyBuilder, MemStore, Prolly};
let prolly = Prolly::new(MemStore::new(), Config::default());
let mut tree = prolly.create();
let conversation = KeyBuilder::new()
.push_str("tenant")
.push_str("t1")
.push_str("conversation")
.push_str("c42")
.finish();
let message_key = KeyBuilder::from_prefix(conversation.clone())
.push_u64(7)
.finish();
tree = prolly.put(&tree, message_key, b"hello".to_vec()).unwrap();
let (start, end) = prefix_range(&conversation);
let messages = prolly
.range(&tree, &start, end.as_deref())
.unwrap()
.collect::<Result<Vec<_>, _>>()
.unwrap();
assert_eq!(messages.len(), 1);
数値順序がバイト順序と一致する必要がある場合は、push_u64、push_u128、push_i64、push_i128、および push_timestamp_millis を使用します。テストと診断では decode_segments を、読みやすいログでは debug_key を使用します。
キーと範囲の証明
証明APIにより、リーダーはバックエンドストアを開かずにルートCIDに対してマップの内容を検証できます。検証は、ノードCIDを再計算し、子リンクをチェックしてから、検証済みデータを返します。
交換に一致する最小の証明形状を使用します。
prove_key: 1つの値または1つの不在を証明します。prove_keys: 証明ノードを共有しながら、複数のキーを証明します。prove_range:[start, end)のすべてのエントリを証明します。prove_prefix: 1つの論理キープレフィックスの下にあるすべてのエントリを証明します。prove_range_page: 1つのカーソルページを証明します。prove_diff_page: ベースとターゲットのルートに対して、1つのバウンドされた差分ページを証明します。inspect_proof_bundle: バンドルの種類、境界、ルート、およびカウントを読み取ります。verify_proof_bundle: 不明瞭な正規バンドルバイトを検証します。
ピアが改ざん検出、アプリケーションコンテキスト、キーID、ノンス、または発行/有効期限を必要とする場合は、正規バンドルバイトをHMAC-SHA256エンベロープでラップします。verify_authenticated_proof_bundle を使用して、エンベロープを認証し、含まれる証明バンドルを一度に検証します。
小さなツリーから始めます。
use prolly::{
inspect_proof_bundle,
sign_proof_bundle_hmac_sha256,
verify_authenticated_proof_bundle,
verify_authenticated_proof_envelope,
verify_proof_bundle,
Config,
Diff,
DiffPageProof,
KeyProof,
MemStore,
Prolly,
RangeCursor,
RangePageProof,
RangeProof,
};
let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly
.put(&prolly.create(), b"name".to_vec(), b"Alice".to_vec())
.unwrap();
1つのキーを証明し、ストアから読み取ることなく結果を検証します。
let proof = prolly.prove_key(&tree, b"name").unwrap();
let verified = proof.verify();
assert!(verified.exists());
assert_eq!(verified.value, Some(b"Alice".to_vec()));
ピアが同じ証明形状を再構築したい場合は、コンパクトな証明ノードをエクスポートします。
let portable_path = proof.path_node_bytes();
let rebuilt = KeyProof::from_node_bytes(proof.root.clone(), proof.key.clone(), portable_path)
.unwrap();
assert!(rebuilt.verify().valid);
受信者が不明瞭な証明ペイロードのみを必要とする場合は、正規バンドルバイトを使用します。
let proof_bundle = proof.to_bundle_bytes().unwrap();
let bundle_summary = inspect_proof_bundle(&proof_bundle).unwrap();
assert_eq!(bundle_summary.kind_name(), "key");
assert_eq!(bundle_summary.key_count, 1);
let bundle_verified = verify_proof_bundle(&proof_bundle).unwrap();
assert!(bundle_verified.valid);
assert_eq!(bundle_verified.exists_count, 1);
let bundled = KeyProof::from_bundle_bytes(&proof_bundle).unwrap();
assert!(bundled.verify().exists());
1つのリクエストが複数のエントリをカバーする場合は、マルチキー、範囲、およびプレフィックス証明を使用します。
let batch_proof = prolly
.prove_keys(&tree, &[b"name".as_slice(), b"missing".as_slice()])
.unwrap();
let batch_verified = batch_proof.verify();
assert!(batch_verified.valid);
assert!(batch_verified.results[0].exists());
assert!(batch_verified.results[1].is_absence());
let range_proof = prolly.prove_range(&tree, b"name", None).unwrap();
let range_verified = range_proof.verify();
assert!(range_verified.valid);
assert_eq!(
range_verified.entries,
vec![(b"name".to_vec(), b"Alice".to_vec())]
);
let range_bundle = range_proof.to_bundle_bytes().unwrap();
let range_bundled = RangeProof::from_bundle_bytes(&range_bundle).unwrap();
assert_eq!(range_bundled.verify().entries.len(), 1);
let prefix_proof = prolly.prove_prefix(&tree, b"na").unwrap();
assert_eq!(prefix_proof.verify().entries.len(), 1);
カーソルベースの範囲スキャンの場合はページ証明を使用します。
let page_tree = prolly
.build_from_sorted_entries(vec![
(b"a".to_vec(), b"A".to_vec()),
(b"b".to_vec(), b"B".to_vec()),
])
.unwrap();
let proved_page = prolly
.prove_range_page(&page_tree, &RangeCursor::start(), None, 1)
.unwrap();
assert_eq!(proved_page.page.entries, vec![(b"a".to_vec(), b"A".to_vec())]);
assert_eq!(proved_page.proof.verify().entries, proved_page.page.entries);
let page_bundle = proved_page.proof.to_bundle_bytes().unwrap();
let page_bundled = RangePageProof::from_bundle_bytes(&page_bundle).unwrap();
assert_eq!(page_bundled.verify().entries.len(), 1);
ピアが変更の1ページを検証する必要がある場合は、差分ページ証明を使用します。
let diff_tree = prolly.delete(&page_tree, b"a").unwrap();
let diff_tree = prolly
.put(&diff_tree, b"b".to_vec(), b"B2".to_vec())
.unwrap();
let proved_diff = prolly
.prove_diff_page(&page_tree, &diff_tree, &RangeCursor::start(), None, 1)
.unwrap();
assert_eq!(
proved_diff.page.diffs,
vec![Diff::Removed {
key: b"a".to_vec(),
val: b"A".to_vec()
}]
);
assert_eq!(proved_diff.proof.verify().diffs, proved_diff.page.diffs);
let diff_bundle = proved_diff.proof.to_bundle_bytes().unwrap();
let diff_summary = inspect_proof_bundle(&diff_bundle).unwrap();
assert_eq!(diff_summary.kind_name(), "diff_page");
assert_eq!(diff_summary.limit, Some(1));
assert!(diff_summary.has_lookahead);
let diff_bundle_verified = verify_proof_bundle(&diff_bundle).unwrap();
assert!(diff_bundle_verified.valid);
assert_eq!(diff_bundle_verified.diff_count, 1);
let diff_bundled = DiffPageProof::from_bundle_bytes(&diff_bundle).unwrap();
assert!(diff_bundled.verify().lookahead_valid);
受信者がエンベロープ認証も必要とする場合は、バンドルバイトに署名します。
let signed = sign_proof_bundle_hmac_sha256(
proof_bundle.clone(),
b"proof-key-v1".to_vec(),
b"shared secret",
b"tenant=t1".to_vec(),
Some(1_700_000_000_000),
Some(1_700_000_100_000),
b"nonce-1".to_vec(),
)
.unwrap();
let envelope = signed.to_bytes().unwrap();
let decoded = prolly::AuthenticatedProofEnvelope::from_bytes(&envelope).unwrap();
let authenticated =
verify_authenticated_proof_envelope(&decoded, b"shared secret", Some(1_700_000_050_000));
assert!(authenticated.valid);
assert!(KeyProof::from_bundle_bytes(&authenticated.proof_bundle)
.unwrap()
.verify()
.exists());
または、エンベロープを認証し、含まれる証明バンドルを一度に検証します。
let authenticated_bundle =
verify_authenticated_proof_bundle(&envelope, b"shared secret", Some(1_700_000_050_000))
.unwrap();
assert!(authenticated_bundle.valid);
assert_eq!(
authenticated_bundle.proof.as_ref().unwrap().exists_count,
1
);
値コーデック
コアマップは値をバイトとして保存します。アプリケーション値が型付き構造体の場合、encode_json / decode_json または encode_cbor / decode_cbor を使用します。
use prolly::{decode_json, encode_json};
use serde::{Deserialize, Serialize};
#[derive(Debug, PartialEq, Serialize, Deserialize)]
struct MemoryRecord {
source: String,
content: String,
}
let record = MemoryRecord {
source: "conversation/c42".to_string(),
content: "User likes durable local-first state.".to_string(),
};
let bytes = encode_json(&record).unwrap();
let decoded: MemoryRecord = decode_json(&bytes).unwrap();
assert_eq!(decoded, record);
モジュールがアプリケーションスキーマを所有し、エンコード/デコードポリシーを渡したい場合は、再利用可能なコーデックオブジェクトを使用します。
use prolly::{JsonCodec, ValueCodec, VersionedJsonCodec};
#[derive(Debug, PartialEq, serde::Serialize, serde::Deserialize)]
struct MemoryRecord {
source: String,
content: String,
}
let record = MemoryRecord {
source: "conversation/c42".to_string(),
content: "User likes durable local-first state.".to_string(),
};
let json = JsonCodec;
let bytes = json.encode(&record).unwrap();
let decoded = json.decode::<MemoryRecord>(&bytes).unwrap();
assert_eq!(decoded, record);
let versioned = VersionedJsonCodec::new("ai.memory.record", 1);
let stored = versioned.encode(&record).unwrap();
let decoded = versioned.decode::<MemoryRecord>(&stored).unwrap();
assert_eq!(decoded, record);
保存されたバイトにスキーマと移行メタデータが必要な場合は、VersionedValue を使用します。
use prolly::{Config, MemStore, Prolly, VersionedValue};
#[derive(Debug, PartialEq, serde::Serialize, serde::Deserialize)]
struct MemoryRecord {
source: String,
content: String,
}
let record = MemoryRecord {
source: "conversation/c42".to_string(),
content: "User likes durable local-first state.".to_string(),
};
let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly.create();
let value = VersionedValue::json("ai.memory.record", 1, &record)
.unwrap()
.to_bytes()
.unwrap();
let tree = prolly
.put(&tree, b"memory/record/1".to_vec(), value)
.unwrap();
let stored = prolly.get(&tree, b"memory/record/1").unwrap().unwrap();
let envelope = VersionedValue::from_bytes(&stored).unwrap();
envelope.require_schema("ai.memory.record", 1).unwrap();
let decoded: MemoryRecord = envelope.decode_json().unwrap();
assert_eq!(decoded, record);
トゥームストーン
同期負荷の高いアプリケーションが、ピアが物理的に削除される前に観測できる論理削除を必要とする場合は、Tombstone を使用します。トゥームストーンは、アクター、タイムスタンプ、および因果メタデータを通常の値として格納します。
use prolly::{tombstone_compaction, Config, MemStore, Prolly, Tombstone};
let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly.create();
let tree = prolly
.put(&tree, b"doc/1".to_vec(), b"live".to_vec())
.unwrap();
let tombstone = Tombstone::new(b"agent-a".to_vec(), 1_700_000_000_000)
.with_causal_metadata("base-root", b"cid-before-delete".to_vec());
let tree = prolly
.batch(&tree, vec![tombstone.to_upsert_mutation(b"doc/1").unwrap()])
.unwrap();
let stored = prolly.get(&tree, b"doc/1").unwrap().unwrap();
let decoded = Tombstone::from_stored_bytes(&stored).unwrap().unwrap();
assert_eq!(decoded.actor, b"agent-a".to_vec());
let delete = tombstone_compaction(b"doc/1".to_vec(), &stored)
.unwrap()
.unwrap();
let compacted = prolly.batch(&tree, vec![delete]).unwrap();
assert!(prolly.get(&compacted, b"doc/1").unwrap().is_none());
コアデータモデル
Tree
Tree は呼び出し元に返される永続的なハンドルです。ノードデータを所有しません。ルートCIDとツリーの構築に使用された Config のみを記録します。
空のツリーは root == None を持ちます。空でないツリーは root == Some(Cid) を持ちます。
Cid
Cid は、シリアライズされたノードバイトの32バイトSHA-256ダイジェストです。等しいノードコンテンツは同じCIDを生成し、これによりツリーはMerkleスタイルのIDを持ちます。
- 等しいルートは等しいツリーを意味します。
- 等しい子CIDは、差分全体サブツリーをスキップできます。
- 書き換えられたパスは、変更されていないすべての兄弟サブツリーを共有できます。
Node
Node はソートされた keys と並列の vals を格納します。
リーフノードの場合:
keys = [k1, k2, k3]
vals = [v1, v2, v3] // raw user value bytes
内部ノードの場合:
keys = [first_key_child_1, first_key_child_2, ...]
vals = [child_cid_1, child_cid_2, ...] // 32-byte CID bytes
重要なノードフィールド:
leaf: 値が生のデータか子CIDか。level: リーフの場合は0、ルートに向かって増加します。child_counts: 各内部子の下の論理レコード数。format: パーシステッドチャンキング、ノードレイアウト、および値エンコーディングのID。
ノードは、現在の自己記述的な決定論的フォーマットで CRAB マジックヘッダーでシリアライズされます。以前の実験的なノードフォーマットは意図的にデコードされません。このクレートは現在、ハードカットオーバーフォーマットポリシーを使用しています。
コンテンツ定義チャンキング
Prollyツリーは、固定Bツリー分割ポイントではなく、コンテンツ定義チャンク境界を使用します。TreeFormat は、呼び出し元がエントリ数、論理バイト、またはエンコードバイト測定、キーのみまたはキー/値入力、およびしきい値、ワイブル、またはローリングハッシュ境界を選択できるようにします。すべてのポリシーは、最小、ターゲット、最大、およびハードエンコードバイト境界を適用します。組み込みプリセットには、エントリ数/キー値、エントリ数/キーのみ、論理バイト/キーのみワイブル、および論理バイトローリングハッシュポリシーが含まれます。
キーのみのポリシーは、値が変更されてもチャンク境界を安定させます。正規ライターは、影響を受ける最初のチャンクからストリームし、コンテンツ定義境界が再び整列するとすぐに古いサフィックスを再利用するため、同等の論理コンテンツは編集履歴に関係なく同じルートに収束します。
これは、prollyツリーがローカルファーストストレージとバージョン付きマップまたはデータベースインデックスに適している主なプロパティです。小さな編集は通常、ローカルリーフと祖先パスを書き換えますが、変更されていないコンテンツは同じCIDを保持します。
読み取りパス
get(&tree, key) は、ルートからリーフへの検索を実行します。
Storeからtree.rootをロードします。- 現在のノードのソート済み
keysをバイナリ検索します。 - 内部ノードでは、キーを含むことができる子のスパンに降下します。
- リーフでは、正確なキーの値または
Noneを返します。
期待される複雑さは O(log n) ノード訪問です。
範囲APIは同様のポジショニングを使用します。
range(&tree, start, end)は遅延RangeIterを返します。range_after(&tree, after_key, end)は、処理されたキーの直後に再開します。range_from_cursor(&tree, cursor, end)は、安定したRangeCursorから再開します。range_page(&tree, cursor, end, limit)は、チェックポイントのためにバウンドされたページを読み取ります。reverse_page(&tree, cursor, start, limit)およびprefix_reverse_page(&tree, prefix, cursor, limit)は、安定したReverseCursorで降順ページを読み取ります。prove_range_page(&tree, cursor, end, limit)は、同じページに加えて、排他的カーソルウィンドウのストア独立証明を返します。cursor(&tree, key)は、キーの近くにカーソルを配置します。range_cursor(&tree, start, end)は、カーソル走査を使用してバウンドされたスキャンを実行します。
範囲イテレーションは、最初のシークを実行し、次にソートされたキー順でリーフを前進させます。
use prolly::{Config, MemStore, Prolly, RangeCursor};
let prolly = Prolly::new(MemStore::new(), Config::default());
let mut tree = prolly.create();
for i in 0..5 {
tree = prolly
.put(
&tree,
format!("k{i:03}").into_bytes(),
format!("v{i:03}").into_bytes(),
)
.unwrap();
}
let mut cursor = RangeCursor::start();
let mut rows = Vec::new();
loop {
let page = prolly.range_page(&tree, &cursor, Some(b"k004"), 2).unwrap();
rows.extend(page.entries);
match page.next_cursor {
Some(next) => cursor = next,
None => break,
}
}
assert_eq!(rows.len(), 4);
書き込みパス
put および delete は不変操作です。
単一キー書き込み:
find_pathはルートからターゲットリーフまでをウォークします。- 正規のストリーミングエミッターは、ツリーのパーシステッドチャンキングポリシーと正確なバイトキャップを使用して、影響を受ける順序付きスパンを再生します。
- エミットされた子サマリーは、影響を受ける親レベルをストリームします。
- 新しいまたは変更されたノードは収集され、ストアを介してフラッシュされます。
- メソッドは新しいルートCIDで新しい
Treeを返します。
元のツリーは有効なままで、変更されていないサブツリーを共有します。
追加負荷の高い単一キー書き込みは、キーが現在の右端エッジの後ろに属する場合、右端パスの高速パスを使用できます。
バッチミューテーションパス
batch(&tree, mutations) は、複数の更新のためのデフォルトAPIです。
use prolly::{Config, MemStore, Mutation, Prolly};
let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let tree = prolly.create();
let mutations = vec![
Mutation::Upsert {
key: b"a".to_vec(),
val: b"1".to_vec(),
},
Mutation::Upsert {
key: b"b".to_vec(),
val: b"2".to_vec(),
},
Mutation::Delete {
key: b"old".to_vec(),
},
];
let tree = prolly.batch(&tree, mutations).unwrap();
オペレーションのテレメトリが必要な場合は、batch_with_stats または append_batch_with_stats を使用します。統計情報を持つエントリポイントと並列エントリポイントは、同じ正規ライターのアダプターです。これらは異なる境界またはツリーアルゴリズムを選択できません。
バッチ処理:
- ミューテーションをキーでソートします。
- 最後の書き込みが優先されるセマンティクスで重複キーを重複排除します。
- 追加専用バッチを検出し、可能な場合は右端パスを直接更新します。
- ミューテーションをターゲットリーフごとにグループ化します。
Store::batch_get_orderedを介してリーフを事前フェッチできます。- 2ポインタマージまたはバイナリ検索のいずれかでグループ化されたミューテーションを適用します。
- サポートされている場合は、影響を受ける親を再構築し、ストアバッチ書き込みを介してノードをアトミックにフラッシュします。
ライターオブジェクトが便利な場合は、BatchWriter を使用します。その ParallelConfig はスケジューリング幅としきい値のみを制御します。永続化されたポリシーと正規出力は不変です。
報告された実効幅は、多くの大きなライターが同時に実行される場合、要求された幅よりも低くなる可能性があります。呼び出し元スレッドが共有Rayonプールを飽和させると、過剰サブスクリプションとテールレイテンシの低下を回避するために、内部並列処理が無効になります。選択されたポリシーが証明された独立した作業を見つけられない場合も1つになる可能性があります。テレメトリは、要求された、または最初に許可された幅ではなく、実際に使用された幅を報告します。
直接並列リーフ置換は、キーのみのエントリ数ハッシュの下での非成長値更新に限定されます。値に敏感なポリシーとバイト測定ポリシーは、右端リーフでも正規ストリーミングライターを使用します。
バルクビルド
多くのソートされていないエントリがあり、新しいツリーを構築したい場合は、BatchBuilder を使用します。
use prolly::{BatchBuilder, Config, MemStore};
use std::sync::Arc;
let store = Arc::new(MemStore::new());
let mut builder = BatchBuilder::new(store, Config::default());
for i in 0..1000 {
builder.add(
format!("key-{i:04}").into_bytes(),
format!("value-{i}").into_bytes(),
);
}
let tree = builder.build().unwrap();
BatchBuilder はエントリをソートし、Rayonでハッシュ境界述語を並列に計算し、リーフノードをバッチで書き込み、次に内部レベルをボトムアップで構築します。
入力が既にキーでソートされている場合は、SortedBatchBuilder を使用します。これは、すべてのキー/値ペアをメモリに保持せずにリーフ構築をストリームできます。
差分、範囲差分、およびマージ
差分APIは、リーフレベルの比較にフォールバックする前にツリー構造を比較します。
diff(&base, &other)は収集されたDiffエントリを返します。range_diff(&base, &other, start, end)は、ハーフオープンキー範囲外のサブツリーを削除します。diff_from_cursor(&base, &other, cursor, end)は、カーソルキーの直後に再開します。diff_page(&base, &other, cursor, end, limit)は、チェックポイントされたインデックス作成と同期ジョブのためにバウンドされた差分ページを読み取ります。prove_diff_page(&base, &other, cursor, end, limit)は、同じ差分ページに加えて、ページネーションを検証するために必要な両方のルートと継続的なルックアップに対するストア独立証明を返します。structural_diff_page(&base, &other, cursor, limit)は、大きな差分ジョブがキーから再計算せずに再開できるように、実際のCIDフロンティアをチェックポイントします。diff_cursor(&base, &other)およびstream_diff(&base, &other)は変更をストリームします。stream_conflicts(&base, &left, &right)は、完全な右側差分をマテリアライズせずに、削除を考慮したConflictのみをストリームします。
高速パス:
- 同じルートCIDは
O(1)で変更を返しません。 - 等しい子CIDは、全体サブツリーをスキップします。
- 一致する子スパンは構造的に再帰します。
- 分岐した境界は、影響を受けるサブツリーの順序付きコレクションと比較にフォールバックします。
use prolly::{Config, MemStore, Prolly, RangeCursor};
let prolly = Prolly::new(MemStore::new(), Config::default());
let base = prolly.create();
let base = prolly.put(&base, b"a".to_vec(), b"1".to_vec()).unwrap();
let other = prolly.put(&base, b"b".to_vec(), b"2".to_vec()).unwrap();
let mut cursor = RangeCursor::start();
let mut diffs = Vec::new();
loop {
let page = prolly.diff_page(&base, &other, &cursor, None, 16).unwrap();
diffs.extend(page.diffs);
match page.next_cursor {
Some(next) => cursor = next,
None => break,
}
}
assert_eq!(diffs.len(), 1);
チェックポイント間のサブツリープルーニングを維持したいバックグラウンド同期またはインデックス作成ジョブの場合、構造走査を直接ページングします。
let mut cursor = None;
let mut diffs = Vec::new();
loop {
let page = prolly
.structural_diff_page(&base, &other, cursor.as_ref(), 16)
.unwrap();
diffs.extend(page.diffs);
match page.next_cursor {
Some(next) => cursor = Some(next),
None => break,
}
}
merge(&base, &left, &right, resolver) は3者マージを実行します。両側が同じキーを異なる方法で変更した場合、競合を検出します。リゾルバーは Resolution::Value、Resolution::Delete、または Resolution::Unresolved を返します。解決されない競合は Error::Conflict を返します。
use prolly::{resolver, Config, MemStore, Prolly};
let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let base = prolly.create();
let base = prolly.put(&base, b"mode".to_vec(), b"base".to_vec()).unwrap();
let left = prolly.delete(&base, b"mode").unwrap();
let right = prolly
.put(&base, b"mode".to_vec(), b"right".to_vec())
.unwrap();
let merged = prolly
.merge(&base, &left, &right, Some(Box::new(resolver::update_wins)))
.unwrap();
assert_eq!(prolly.get(&merged, b"mode").unwrap(), Some(b"right".to_vec()));
キー範囲の1つのみが右側変更を受け入れるようにしたい場合は、merge_range(&base, &left, &right, start, end, resolver) を使用します。merge_prefix は、1つのドキュメント、テナント、ワークスペース、またはセカンダリインデックスシャードなどのプレフィックスパーティション化されたデータ用の便利な形式です。
use prolly::{Config, MemStore, Prolly};
let prolly = Prolly::new(MemStore::new(), Config::default());
let base = prolly
.put(&prolly.create(), b"doc/1/title".to_vec(), b"old".to_vec())
.unwrap();
let left = prolly
.put(&base, b"doc/2/title".to_vec(), b"local".to_vec())
.unwrap();
let right = prolly
.put(&base, b"doc/1/title".to_vec(), b"remote".to_vec())
.unwrap();
let merged = prolly
.merge_prefix(&base, &left, &right, b"doc/1/", None)
.unwrap();
assert_eq!(
prolly.get(&merged, b"doc/1/title").unwrap(),
Some(b"remote".to_vec())
);
assert_eq!(
prolly.get(&merged, b"doc/2/title").unwrap(),
Some(b"local".to_vec())
);
マージ動作を観察可能にするには merge_explain を使用します。これは、マージ結果と型付きトレースの両方を含む MergeExplanation を返します。マージ結果が Error::Conflict の場合でもトレースは保持されるため、アプリケーションはカスタムリゾルバー呼び出し、フォールバック理由、再利用されたサブツリー、および書き換えられたノードスパンをデバッグUIまたは同期ログに表示できます。マージが差分/バッチパスにフォールバックする場合、トレースには比較されたノード、スキップされた等しいサブツリー、収集されたサブツリーフォールバック、およびエミットされた差分エントリなどの DiffTraversal カウンターが含まれます。
use prolly::{Config, MemStore, MergeTraceEvent, Prolly};
let prolly = Prolly::new(MemStore::new(), Config::default());
let base = prolly.create();
let base = prolly.put(&base, b"k".to_vec(), b"base".to_vec()).unwrap();
let left = prolly.put(&base, b"k".to_vec(), b"left".to_vec()).unwrap();
let right = prolly.put(&base, b"k".to_vec(), b"right".to_vec()).unwrap();
let explanation = prolly.merge_explain(&base, &left, &right, None);
assert!(explanation
.trace
.events
.iter()
.any(|event| matches!(event, MergeTraceEvent::StructuralMergeStarted)));
assert!(explanation.result.is_err());
async-store 機能の下で、リモート同期ジョブやオブジェクトストアバックエンドのアプリケーションが、同期ストレージAPIにブロックすることなくリゾルバー診断を保持できるように、AsyncProlly::merge_explain で同じ説明形状が利用可能です。これは、ストアバックエンドが非同期である場合に、型付きトレースを非同期で生成します。
アプリケーションがユーザー、エージェント、またはドメインポリシーに問い合わせる必要がある場合は、stream_conflicts を使用します。イテレーターは削除を考慮した Conflict 値を生成し、クリーンな右側変更をスキップします。
let conflicts = prolly
.stream_conflicts(&base, &left, &right)
.unwrap()
.collect::<Result<Vec<_>, _>>()
.unwrap();
AsyncProlly::stream_conflicts は、next().await、collect().await、および into_stream() アダプターを使用して、同じ削除を考慮した競合ストリームを非同期で公開します。
ドメイン固有のルールを持つアプリケーションの場合、MergePolicyRegistry を使用して、キープレフィックス、正確なキー、またはカスタムマッチャーによってリゾルバーを合成します。後続のマッチングルールは、先行するルールをオーバーライドします。
use prolly::{resolver, MergePolicyRegistry, Resolution};
let policies = MergePolicyRegistry::with_default(|_| Resolution::unresolved())
.add_prefix(b"settings/".to_vec(), resolver::update_wins)
.add_prefix(b"permissions/".to_vec(), resolver::delete_wins)
.add_prefix(b"documents/".to_vec(), resolver::prefer_left)
.add_pattern(
"summary merge",
|key| key.ends_with(b"/summary"),
|conflict| {
let mut value = conflict.left.clone().unwrap_or_default();
value.extend_from_slice(b"\n---\n");
value.extend(conflict.right.clone().unwrap_or_default());
Resolution::value(value)
},
);
let merged = prolly.merge(&base, &left, &right, Some(policies.as_resolver()));
crdt_merge は、最後の書き込みが優先される、マルチバリューの保持、またはカスタムマージ関数などの自動競合フリーマージ動作のために CrdtConfig を使用します。構造化されたイベント(サブツリーの再利用、フォールバックパス、および各自動競合解決)も必要な場合は、crdt_merge_explain を使用します。
公開APIサーフェス
クレートルートはサポートされているユーザー向けAPIです。実装モジュールはプライベートであるため、呼び出し元は prolly::Prolly、prolly::Store、prolly::BatchBuilder、および prolly::resolver のような安定したインポートを使用します。
低レベルのルート計画と再構築ヘルパーはクレート内部です。公開バッチスケジューリングは ParallelConfig を介して公開されます。BatchWriter と parallel_batch は両方とも同じ正規ライターに委任します。ワーカー幅はスケジューリングを変更できますが、チャンキングアルゴリズム、シリアライズされたノード、またはルートを変更することはありません。幅1のベースラインとして ParallelConfig::sequential() を使用します。
互換性ポリシー
prolly は、オープンソースの 0.1 リリースに向けて準備中です。1.0 まで、マイナーリリースは、長期的なマップ抽象化を単純化したり、偶発的な内部実装を削除したりする場合、APIの破壊的変更を行う可能性があります。意図された安定したサーフェスは、上記で文書化されたクレートルートAPIです。
現在のリリース前フォーマットポリシー:
- ツリーハンドルは不変です。バックエンドストアが参照されているすべてのノードCIDを保持している限り、既存の
Tree値は有効なままです。 - ストアキーはコンテンツIDであり、ストア値はシリアライズされたノードバイトです。ストアはバイトを正確に保持する必要があります。
- ノードバイトは永続化されたデータですが、リリース前のワイヤーフォーマットは明示的なハードカットオーバーに置き換えられる可能性があります。デコーダーは現在の
CRABフォーマットのみを受け入れます。 - ノードシリアライゼーションは、特定のノードペイロードとエンコーディングバージョンに対して決定論的です。シリアライゼーション、チャンキング設定、またはエンコーディング設定を変更すると、新しく生成されたCIDとルートが変更される可能性があります。
- ストレージアダプターは別々のクレートであるため、アプリケーションは選択したデータベースエンジンのみをコンパイルして出荷します。
async-storeはハードTokio依存関係を回避します。Tokio固有のアダプターはtokio機能の背後に残ります。- リゾルバーおよびCRDTカスタムマージコールバックは、決定論的で副作用のないものである必要があります。マージの高速パスは、異なる実行パスを介して同等の競合を評価する可能性があります。
ストレージバックエンド
Store トレイトは意図的に小さく、コンテンツアドレス指定されています。ストアキーはCIDバイトであり、値はシリアライズされたノードバイトです。
必須メソッド:
getputdeletebatch
オプションの最適化メソッド:
batch_getbatch_get_orderedbatch_get_ordered_uniquebatch_putsupports_hintsget_hintput_hintbatch_put_with_hint
組み込みストア:
MemStore: テストおよび軽量使用のためのインメモリストア。FileNodeStore: 永続的なコンテンツアドレス指定ファイル/オブジェクトレイアウトストア。不変ノードをCID名前空間の下に保持し、読み書き時にノードバイトを検証し、ヒントと名前付きルートを別々の名前空間に格納します。
オプションのアダプタークレート:
prolly-store-sqlite: 永続SQLiteバックエンド。これには永続的なセマンティックRAG例 が含まれます。prolly-store-turso: ネイティブローカル非同期Tursoデータベースバックエンド。オプションのturso-cloud-sync機能の背後にある明示的なクラウドプッシュ/プルを備えています。prolly-store-redb: 純粋なRust、単一ファイルredbバックエンド。アトミックトランザクションを備えています。prolly-store-rocksdb: 埋め込みRocksDBバックエンド。prolly-store-pglite: PGlite/Nodeサイドカーバックエンド。prolly-store-slatedb: オブジェクトストアバックエンドのSlateDBバックエンド。- 追加のサービスアダプターは
stores/の下にあります。
機能フラグ:
async-store: 空の互換性スペル。非同期トレイト、アダプター、およびAsyncProllyは常に利用可能です。tokio: Tokioブロッキングストア/ブロブアダプターを追加します。コアエンジンはランタイムニュートラルなままです。
cargo test
cargo test --features async-store
cargo test --features tokio
cargo test --manifest-path stores/prolly-store-sqlite/Cargo.toml
cargo test --manifest-path stores/prolly-store-turso/Cargo.toml
cargo test --manifest-path stores/prolly-store-redb/Cargo.toml
cargo test --manifest-path stores/prolly-store-rocksdb/Cargo.toml
cargo test --manifest-path stores/prolly-store-pglite/Cargo.toml
cargo test --manifest-path stores/prolly-store-slatedb/Cargo.toml
ルートマニフェスト
不変ツリーハンドルはメモリ内で便利ですが、アプリケーションはブランチ、チェックポイント、ワークスペース、および同期カーソルに永続的な名前を必要とします。ManifestStore は、コンテンツアドレス指定ノードの隣に名前付き RootManifest 値を格納します。
名前付きルートは不変のポインタです。put、delete、batch、または merge を呼び出しても、名前付きルートは自動的に進みません。これらの操作は新しい Tree を返します。アプリケーションは、publish_named_root または、同時ライターの場合は compare_and_swap_named_root を使用して、そのツリーを公開する必要があります。これは、新しいGitツリーオブジェクトを作成してから、それを指すように参照を更新するのと似ています。
use prolly::{Config, FileNodeStore, Prolly};
use std::sync::Arc;
let store = Arc::new(FileNodeStore::open("./target/prolly-prefix-hints").unwrap());
let prolly = Prolly::new(store.clone(), Config::default());
let tree = prolly.create();
let tree = prolly
.put(&tree, b"project/name".to_vec(), b"trail".to_vec())
.unwrap();
let update = prolly
.compare_and_swap_named_root(b"main", None, Some(&tree))
.unwrap();
assert!(update.is_applied());
let loaded = prolly.load_named_root(b"main").unwrap().unwrap();
assert_eq!(
prolly.get(&loaded, b"project/name").unwrap(),
Some(b"trail".to_vec())
);
名前が存在した後も同じルールが適用されます。
let current = prolly.load_named_root(b"main").unwrap().unwrap();
let next = prolly
.put(¤t, b"project/owner".to_vec(), b"team-a".to_vec())
.unwrap();
// ここでは `main` はまだ `current` を指しています。
let still_current = prolly.load_named_root(b"main").unwrap().unwrap();
assert_eq!(
prolly.get(&still_current, b"project/owner").unwrap(),
None
);
let update = prolly
.compare_and_swap_named_root(b"main", Some(¤t), Some(&next))
.unwrap();
assert!(update.is_applied());
compare_and_swap_named_root は、現在のツリーが期待されるツリーと一致する場合にのみ、同時ライターが名前付きルートを更新できるようにします。publish_named_root は名前を無条件に置き換え、delete_named_root はコンテンツアドレス指定ノードを削除せずに名前を削除します。MemStore はテストと軽量使用のためにこれをサポートします。SQLiteおよびPGliteアダプターは専用テーブルにルートを格納します。RocksDBStore は専用カラムファミリーにルートを格納します。SlateDbStore は専用キープレフィックスの下にルートを格納します。永続ストアは、名前付きルートデータをコンテンツアドレス指定ノードバイトから分離して保持します。
マニフェストを列挙できるストアは ManifestStoreScan を実装します。list_named_roots、load_named_roots、および load_retained_named_roots を使用して、バックグラウンドジョブおよびガベージコレクションのために明示的に保持されたルートセットを構築します。NamedRootRetention は、すべてのルート、正確なルート名、名前プレフィックス、プレフィックスの下の辞書順で最新のN個のルート、またはUnixミリ秒タイムスタンプ以降に更新されたルートを保持することをサポートします。マネージャーレベルの公開およびCASヘルパーは created_at_millis および updated_at_millis をスタンプします。*_at_millis バリアントは、決定論的なインポートとテストのために明示的なタイムスタンプを受け入れます。
トランザクションとMVCC
ツリーハンドルは不変のMVCCスナップショットです。古い Tree を保持しているリーダーは、ライターが新しいものを構築している間、そのバージョンを見続けます。厳密なトランザクションは、それらの不変書き込みの周りにステージングレイヤーを追加します。トランザクションは、新しいコンテンツアドレス指定ノードと名前付きルート書き込みをメモリにバッファリングし、読み取ったすべての名前付きルートを検証し、次にストアにステージングされたノードとルートをアトミックにコミットするようにストアに要求します。クロージャがエラーを返すか、検証が失敗するか、バックエンドコミットが失敗した場合、ステージングされたオーバーレイは破棄され、部分的なルート更新は表示されません。
SqliteStore は、単一のSQLトランザクションで厳密なトランザクションをサポートします。
use prolly::{Config, Prolly};
use prolly_store_sqlite::SqliteStore;
let store = SqliteStore::open_in_memory().unwrap();
let prolly = Prolly::new(store, Config::default());
let commit = prolly
.transaction(|tx| {
let source = tx.put(
&tx.create(),
b"ticket/123/status".to_vec(),
b"open".to_vec(),
)?;
let by_status = tx.put(
&tx.create(),
b"by_status/open/123".to_vec(),
b"ticket/123".to_vec(),
)?;
// 両方のスナップショットを指す小さなアプリケーションマニフェストを格納します。
let manifest = tx
.put(&tx.create(), b"source".to_vec(), serde_cbor::to_vec(&source).unwrap())?;
let manifest = tx.put(
&manifest,
b"by_status".to_vec(),
serde_cbor::to_vec(&by_status).unwrap(),
)?;
tx.publish_named_root(b"tickets/current", &manifest)?;
Ok(manifest)
})
.unwrap();
assert_eq!(prolly.load_named_root(b"tickets/current").unwrap(), Some(commit));
マテリアライズドビューやセカンダリインデックスの場合、ソースとインデックスのスナップショットを含む単一の権威あるコミットルート(例:tickets/current)を優先します。リーダーはその単一ルートをロードし、一貫したペアを取得します。ライターはトランザクション内で候補ソース/インデックスツリーを構築し、コミットルートのみを公開します。複数の名前付きルートを単一トランザクションで更新できますが、単一コミットルートはリーダーの調整を単純化します。
Gitライクなアプリケーションプリミティブ
名前付きルートは意図的に低レベルです。アプリケーションは、名前付きルート、不変ツリー、アプリ定義のコミットメタデータ、差分、マージ、およびGCリテンションを組み合わせて、Gitライクな操作をレイヤー化できます。
| 操作 | Prollyビルディングブロック | 注記 |
|---|---|---|
| ヘッドの解決 | load_named_root(name) | refs/heads/main、workspace/<id>/head、または他のアプリ名の現在のツリーをロードします。 |
| スナップショット / コミット | put/delete/batch -> 新しい Tree、次にヘッドのCAS | 親、作成者、メッセージ、またはタイムスタンプが必要な場合は、コミットライクなメタデータを別途格納します。 |
| ブランチ | ソースヘッドをロードし、新しい名前の下で公開 | 既存のブランチの上書きを避けるために、compare_and_swap_named_root(new, None, Some(tree)) を使用します。 |
| タグまたはチェックポイント | 既存のツリーに安定した名前を公開 | 不変のタグ/チェックポイントには、expected = None を持つCASを優先します。 |
| ステータス | 編集可能な候補ツリーを名前付きヘッドと比較 | ファイルシステムの場合、変更されたパスから候補パスマップを構築し、次にヘッドと比較します。 |
| 差分 | diff(left, right) | 名前付きルートは最初に解決されます。差分は不変の Tree ハンドルで機能します。 |
| ファストフォワード | 古いヘッドから新しいヘッドへのブランチCAS | アプリケーションレベルの祖先メタデータが必要です。生のツリールートは親を記録しません。 |
| マージ | ベース、ターゲット、ソースツリーをロードし、merge を呼び出し、ターゲットをCAS | 競合を再現できるように、選択したベースをアプリメタデータに格納します。 |
| リセット / 巻戻し | ヘッド名を以前のツリーに戻すCAS | ユーザーがリカバリを必要とする場合は、リファログ/チェックポイント名を保持します。 |
| チェックアウト / マテリアライズ | アプリ状態または作業ディレクトリにツリーを範囲読み取り | ファイルシステムターゲットの場合、パスを検証し、ステージングエリアに書き込みます。 |
| フェッチ / プッシュ | 不足しているノード/ブロブをコピーし、リモート追跡名をCAS | 参照されているクロージャが存在した後でのみ参照を公開します。 |
| GC | NamedRootRetention および plan_store_gc_for_retention | ブランチヘッド、タグ、チェックポイント、ワークツリーマニフェスト、およびアクティブな同期カーソルを保持します。 |
主な設計境界は、prollyツリーがコンテンツアドレス指定された順序付きスナップショットを提供することです。名前は移動可能なヘッドを提供します。コミットの祖先、リファログ、権限、およびユーザー向けのブランチセマンティクスは、アプリケーションレイヤーに属します。
大規模値オフロード
大きなペイロードは、大規模値ヘルパーレイヤーを使用してリーフノードから除外できます。小さな値は生のインラインリーフバイトのままです。構成されたしきい値より大きい値は、コンテンツアドレス指定された BlobStore に書き込まれ、ツリーはブロブCIDと長さを格納するコンパクトな ValueRef::Blob エンベロープを格納します。
use prolly::{Config, LargeValueConfig, MemBlobStore, MemStore, Prolly, ValueRef};
let prolly = Prolly::new(MemStore::new(), Config::default());
let blobs = MemBlobStore::new();
let policy = LargeValueConfig::new(1024);
let tree = prolly.create();
let payload = vec![42; 8 * 1024];
let tree = prolly
.put_large_value(&blobs, &tree, b"doc/body".to_vec(), payload.clone(), policy)
.unwrap();
assert_eq!(
prolly.get_large_value(&blobs, &tree, b"doc/body").unwrap(),
Some(payload)
);
let stored = prolly.get_value_ref(&tree, b"doc/body").unwrap().unwrap();
assert!(matches!(stored, ValueRef::Blob(_)));
put_large_value は、ツリー更新を公開する前にブロブバイトを書き込みます。繰り返しの大きな書き込みはコンテンツアドレス指定され、MemBlobStore で重複排除されます。get_large_value は通常の生の値を読み取るため、アプリケーションは徐々にオフロードに移行できます。オフロードされた値に対して通常の get を呼び出すと、解決されたブロブバイトではなく、格納されている参照エンベロープが返されます。
ローカル永続ブロブストレージで十分な場合は、FileBlobStore を使用します。これは、ブロブを blobs/sha256/aa/bb/<cid-hex> の下に格納し、読み取り時にブロブバイトを検証し、BlobStoreScan を実装してGCがバックエンドリストを候補セットとして使用できるようにします。
use prolly::{Config, FileBlobStore, LargeValueConfig, MemStore, Prolly};
let prolly = Prolly::new(MemStore::new(), Config::default());
let blobs = FileBlobStore::open("./target/prolly-blobs").unwrap();
let policy = LargeValueConfig::new(1024);
let tree = prolly.create();
let tree = prolly
.put_large_value(&blobs, &tree, b"doc/body".to_vec(), vec![9; 4096], policy)
.unwrap();
let plan = prolly.plan_blob_store_gc(&blobs, &[tree.clone()]).unwrap();
assert!(plan.is_empty());
オフロードされたブロブには、独自の候補駆動GCヘルパーがあります。これはノードGCを反映しています。保持されたツリーからの到達可能なブロブ参照をマークし、候補セットに対してドライランを実行し、次に到達不可能な候補のみをスイープします。既存の prolly、blobs、および policy を使用して続行します。
let old = prolly.create();
let old = prolly
.put_large_value(&blobs, &old, b"doc/body".to_vec(), vec![1; 4096], policy.clone())
.unwrap();
let old_ref = match prolly.get_value_ref(&old, b"doc/body").unwrap().unwrap() {
ValueRef::Blob(reference) => reference,
ValueRef::Inline(_) => unreachable!("payload is larger than the threshold"),
};
let current = prolly
.put_large_value(&blobs, &old, b"doc/body".to_vec(), vec![2; 4096], policy)
.unwrap();
let current_ref = match prolly.get_value_ref(¤t, b"doc/body").unwrap().unwrap() {
ValueRef::Blob(reference) => reference,
ValueRef::Inline(_) => unreachable!("payload is larger than the threshold"),
};
let candidates = vec![old_ref, current_ref];
let plan = prolly.plan_blob_gc(&blobs, &[current.clone()], &candidates).unwrap();
let sweep = prolly.sweep_blob_gc(&blobs, &[current], &candidates).unwrap();
assert_eq!(sweep.deleted_blobs, plan.reclaimable_blob_count);
ガベージコレクション
不変更新は古いツリーノードを保持するため、長期間実行されるアプリケーションは、保持されているルートから到達できなくなったノードを最終的に回収する必要があります。汎用GC APIは明示的な候補CIDを受け入れ、ノード名前空間をスキャンできる組み込みストアは、ストア全体の計画のために NodeStoreScan も実装します。
use prolly::{Config, FileNodeStore, Prolly};
use std::sync::Arc;
let store = Arc::new(FileNodeStore::open("./target/prolly-prefix-hints").unwrap());
let prolly = Prolly::new(store.clone(), Config::default());
let base = prolly.create();
let base = prolly.put(&base, b"k".to_vec(), b"old".to_vec()).unwrap();
let updated = prolly.put(&base, b"k".to_vec(), b"new".to_vec()).unwrap();
let candidates = prolly
.mark_reachable(&[base.clone(), updated.clone()])
.unwrap()
.into_cids();
let plan = prolly.plan_gc(&[updated.clone()], &candidates).unwrap();
println!(
"reclaimable nodes={}, bytes={}",
plan.reclaimable_nodes,
plan.reclaimable_bytes
);
let sweep = prolly.sweep_gc(&[updated], &candidates).unwrap();
assert_eq!(sweep.deleted_nodes, plan.reclaimable_nodes);
mark_reachable は、ルート間の共有サブツリーを重複排除します。plan_gc はドライランです。ストアに存在する到達不可能な候補CID、それらの回収可能なバイト数、および既に欠落していた候補CIDを報告します。sweep_gc は、計画の回収可能な候補を正確に削除し、その後マネージャーキャッシュをクリアして、スイープされたノードがメモリから提供されないようにします。
バックエンドストアが NodeStoreScan を実装している場合は、すべての格納ノードCIDを自動的にスキャンするために plan_store_gc および sweep_store_gc を使用します。
let plan = prolly.plan_store_gc(&[updated.clone()]).unwrap();
let sweep = prolly.sweep_store_gc(&[updated]).unwrap();
assert_eq!(sweep.deleted_nodes, plan.reclaimable_nodes);
名前付きルートアプリケーションの場合、GCがブランチ、チェックポイント、ワークスペース、および同期カーソルルートを保持するように、リテンションポリシーを使用します。
use prolly::NamedRootRetention;
prolly.publish_named_root(b"checkpoint/0001", &base).unwrap();
prolly
.publish_named_root(b"checkpoint/0002", &updated)
.unwrap();
let retention = NamedRootRetention::newest_by_name(b"checkpoint/", 1);
let selected = prolly.load_retained_named_roots(&retention).unwrap();
assert_eq!(selected.roots.len(), 1);
let plan = prolly.plan_store_gc_for_retention(&retention).unwrap();
let sweep = prolly.sweep_store_gc_for_retention(&retention).unwrap();
assert_eq!(sweep.deleted_nodes, plan.reclaimable_nodes);
正確な名前リテンションは欠落している名前を報告し、正確なルートが欠落している場合、GCの便利なヘルパーは Error::MissingNamedRoots で失敗します。プレフィックスおよび最新の名前ポリシーは、現在存在するルートから意図的に選択します。タイムウィンドウリテンションの場合は、マニフェストに updated_at_millis メタデータがある場合に NamedRootRetention::updated_since(prefix, cutoff_millis) または期間スタイルの updated_within* ヘルパーを使用します。
prolly
.publish_named_root_at_millis(b"checkpoint/0001", &base, 1_800_000)
.unwrap();
prolly
.publish_named_root_at_millis(b"checkpoint/0002", &updated, 3_600_000)
.unwrap();
let recent = NamedRootRetention::updated_since(b"checkpoint/", 3_000_000);
let selected = prolly.load_retained_named_roots(&recent).unwrap();
assert_eq!(selected.roots.len(), 1);
let now_millis = 3_600_000;
let last_hour = NamedRootRetention::updated_within_millis(
b"checkpoint/",
now_millis,
60 * 60 * 1000,
);
let selected = prolly.load_retained_named_roots(&last_hour).unwrap();
assert_eq!(selected.roots.len(), 2);
不完全な保持ルートセットを渡すと、他のブランチまたはチェックポイントがまだ必要としているノードが削除される可能性があります。
スナップショット名前空間
名前付きルートは意図的にバイトレベルであるため、アプリケーションは独自のルートスキームを選択できます。スナップショット名前空間は、同じマニフェストストレージ、CAS更新、リテンションポリシー、およびGC動作を再利用しながら、一般的なブランチ、タグ、チェックポイント、およびカスタムルート名のために小さな規約レイヤーを追加します。
use prolly::{Config, MemStore, Prolly, SnapshotNamespace};
let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly
.put(&prolly.create(), b"k".to_vec(), b"v".to_vec())
.unwrap();
let branches = prolly.branch_snapshots();
branches.publish_at_millis(b"main", &tree, 1_700_000).unwrap();
assert_eq!(branches.root_name(b"main"), b"refs/heads/main".to_vec());
assert_eq!(branches.load(b"main").unwrap(), Some(tree.clone()));
let listed = branches.list().unwrap();
assert_eq!(listed.snapshots.len(), 1);
let deleted = branches
.compare_and_swap(b"main", Some(&tree), None)
.unwrap();
assert!(deleted.is_applied());
let tags = prolly.snapshots(SnapshotNamespace::tag());
tags.publish(b"v1", &tree).unwrap();
組み込みバージョンマップ
アプリケーションが線形履歴を持つ永続マップを必要とするが、完全なGitライクなリポジトリモデルを必要としない場合は、VersionedMap を使用します。このファサードは、一般的なパスから手動のツリーと名前付きルートの調整を削除します。
use prolly::{Config, MemStore, Prolly};
let prolly = Prolly::new(MemStore::new(), Config::default());
let users = prolly.versioned_map(b"users");
let v1 = users.edit(|edit| {
edit.put(b"user/1", b"Ada");
edit.put(b"user/2", b"Grace");
}).unwrap();
let v_next = users.put(b"user/1", b"Ada Lovelace").unwrap();
assert_eq!(users.get(b"user/1").unwrap(), Some(b"Ada Lovelace".to_vec()));
assert_eq!(users.get_at(&v1.id, b"user/1").unwrap(), Some(b"Ada".to_vec()));
let changes = users.diff(&v1.id, &v_next.id).unwrap();
assert_eq!(changes.len(), 1);
users.rollback_to(&v1.id).unwrap();
assert_eq!(users.get(b"user/1").unwrap(), Some(b"Ada".to_vec()));
管理マップAPIは、スナップショット整合性のあるバルク読み取りとカーソルページも公開します。リクエストシーケンスがヘッドを移動しないようにページをバージョンにピン留めします。
use prolly::RangeCursor;
let values = users.get_many(&[b"user/1", b"user/2"]).unwrap();
assert_eq!(values.len(), 2);
let page = users
.prefix_page_at(&v1.id, b"user/", &RangeCursor::start(), 100)
.unwrap();
assert_eq!(page.entries.len(), 2);
リクエストレベルの楽観的同時実行性のために、条件付きヘルパーを使用します。
let expected = users.head_id().unwrap();
let update = users.edit_if(expected.as_ref(), |edit| {
edit.put(b"user/3", b"Margaret");
}).unwrap();
assert!(!update.is_conflict());
リクエストの開始時に MapSnapshot をピン留めして、他のライターがマップヘッドを進めても、すべての読み取りと証明が単一の不変ルートを使用するようにします。
let snapshot = users.snapshot().unwrap().unwrap();
let page = snapshot
.prefix_page(b"user/", &RangeCursor::start(), 100)
.unwrap();
let proof = snapshot.prove_prefix(b"user/").unwrap();
assert!(proof.verify().valid);
assert_eq!(page.entries.len(), 2);
同じピン留めモデルは、比較とコラボレーションをサポートします。compare は再現可能な差分ストリーム、カーソルページ、証明、統計、および変更されたスパンヒントを提供します。prepare_merge はベース、現在のヘッド、および候補をピン留めし、厳密な、ポリシーレジストリ、またはCRDT競合処理を使用してCASで公開します。
運用ワークフローは管理マップハンドル上に残ります。
backup/restore_backup、スナップショットエクスポート/インポート、不足ノードコピー、およびpush_toは、ポータブルな検証とストア間転送を提供します。put_large_valueおよびget_large_valueは構成されたブロブオフロードを使用します。plan_blob_gcおよびsweep_blob_gcは、保持されたマップバージョンにスコープされたままです。initialize_sorted、append、parallel_apply、およびrebuild_sorted_ifは、最初のロード、追加負荷の高い取り込み、並列ミューテーション、およびアトミック置換をカバーします。verify_catalog、keep_last、keep_for、およびkeep_versionsはカタログメンテナンスをマップスコープにします。plan_gc/sweep_gcは、コンテンツアドレス指定ノードとブロブストアが共有される可能性があるため、他のすべての名前付きルートを安全に保持します。versioned_maps_transactionは、権威あるマップ、派生データベースインデックス、およびマテリアライズドビューをアトミックに変更します。
アプリケーションは、typed::<K,V,KC,VC> を使用してほとんどのシリアライゼーションボイラープレートを削除できます。StringKeyCodec またはアプリケーション定義の順序保持 KeyCodec がキーエンコーディングを所有します。VersionedJsonCodec および VersionedCborCodec は値スキーマとバージョンを検証します。migrate_from は、ピン留めされた古いバージョンを1つデコードし、値を書き換え、それがまだヘッドである場合にのみCAS公開します。subscribe および subscribe_from は、論理差分を持つ再開可能なヘッド遷移を発行します。async-store 機能を使用すると、AsyncVersionedMap、ピン留めされた非同期スナップショット、および非同期サブスクリプションが、対応するリモート/ブラウザパスを提供します。
エンジンは、新しいノードをアトミックに書き込み、ヘッドを進め、TransactionalStore を介してバージョンをカタログ化します。便利な書き込みは楽観的な競合を再試行します。アプリケーションが古い呼び出し元を拒否する必要がある場合は、apply_if を使用します。マップバージョンIDは、更新イベントではなく、一意のツリー状態を識別します。作成者、メッセージ、親コミット、ブランチ、およびリファログは、提案されている prolly-vcs リポジトリレイヤーの懸念事項のままです。
リテンションポリシーは、カスタムストアレベルポリシーを構成する際に、このマップの完全なカタログを識別します。
let retention = users.retention_policy();
let retained = prolly.load_retained_named_roots(&retention).unwrap();
assert!(!retained.roots.is_empty());
カタログの成長は明示的です。prune_versions(n) は最新の n スナップショットを保持し、常に現在のヘッドを保持します(古いロールバックされたヘッドも含む)。トランザクションでバージョンルートを削除します。後でリテンションを考慮したGCを実行して、到達不可能なノードを回収します。
let pruned = users.prune_versions(10).unwrap();
println!("removed {} old versions", pruned.removed_count());
let sweep = users.sweep_gc().unwrap();
sweep_gc は、共有ストア内の残りのすべての名前付きルートを保持します。他のマップがそのストアを共有している場合、単一マップのプレフィックスをストア全体のスイープに渡さないでください。
ここで、「マップ」とは、権威ある順序付きキー/値コレクションを指します。データベーススタイルのインデックスは、個別の派生マップ(例:email -> user_id)であり、通常はソースマップの差分から、または同じ厳密なマルチマップトランザクションで維持されます。したがって、VersionedMap はprollyツリーのライフサイクルファサードであり、管理されるすべてのマップがデータベースインデックスであるという主張ではありません。この別のパターンについては、secondary_index.rs を参照してください。
ストア同期
宛先が既に持っているノードを書き換えることなく、ツリールートをストア間でコピーするには、不足ノード計画を使用します。これは、リモートピア、オブジェクトストアキャッシュ、ワークスペース同期、およびバックグラウンドエージェントのための低レベルのMerkle同期プリミティブです。
use prolly::{Config, MemStore, Prolly};
use std::sync::Arc;
let source_store = Arc::new(MemStore::new());
let destination_store = Arc::new(MemStore::new());
let source = Prolly::new(source_store, Config::default());
let tree = source.create();
let tree = source
.put(&tree, b"doc/title".to_vec(), b"Design notes".to_vec())
.unwrap();
let plan = source
.plan_missing_nodes(&tree, &destination_store)
.unwrap();
println!(
"send {} nodes / {} bytes",
plan.missing_nodes,
plan.missing_bytes
);
let copied = source
.copy_missing_nodes(&tree, &destination_store)
.unwrap();
assert_eq!(copied.copied_nodes, plan.missing_nodes);
let destination = Prolly::new(destination_store, tree.config.clone());
assert_eq!(
destination.get(&tree, b"doc/title").unwrap(),
Some(b"Design notes".to_vec())
);
plan_missing_nodes はソースツリーをウォークし、順序付きバッチ読み取りで宛先をチェックし、宛先バイトをCIDと比較して検証します。不足しているソースバイトも、カウントまたはコピーされる前に再ハッシュされます。ストアが要求されたCIDと一致しないバイトを返した場合、破損したコンテンツを信頼するのではなく、操作は Error::CidMismatch で失敗します。
ローカルオブジェクトレイアウトバックエンドの場合、FileNodeStore を使用します。これは、リモートオブジェクトストアアダプターが使用すべき名前空間分割をミラーリングします。不変ノードオブジェクトは nodes/sha256/... の下に、オプションのヒントは hints/... の下に、名前付きルートは roots/... の下に格納されます。
use prolly::{Config, FileNodeStore, Prolly};
use std::sync::Arc;
let store = Arc::new(FileNodeStore::open("./target/prolly-nodes").unwrap());
let prolly = Prolly::new(store.clone(), Config::default());
let tree = prolly.create();
let tree = prolly
.put(&tree, b"doc/title".to_vec(), b"Design notes".to_vec())
.unwrap();
prolly.publish_named_root(b"main", &tree).unwrap();
let reopened = Prolly::new(store, tree.config.clone());
assert_eq!(reopened.load_named_root(b"main").unwrap(), Some(tree));
非同期ストアサポート
非同期ストレージは基盤であり、Cargo機能は不要です。非同期APIは、リモート、ブラウザ、オブジェクトストア、およびバックグラウンドエージェントストレージのための正規のエンジン呼び出し規約です。埋め込み同期ユーザーは、同じエンジンを介してゼロランタイムパスを保持します。
use prolly::{AsyncProlly, AsyncStore, Config, MemStore, Prolly, SyncStoreAsAsync};
use std::sync::Arc;
let sync_store = Arc::new(MemStore::new());
let sync_prolly = Prolly::new(sync_store.clone(), Config::default());
let tree = sync_prolly.create();
let tree = sync_prolly
.put(&tree, b"cid-a".to_vec(), b"node bytes".to_vec())
.unwrap();
let async_store = SyncStoreAsAsync::new(sync_store);
let async_prolly = AsyncProlly::new(async_store, Config::default());
async fn read_nodes<S: AsyncStore>(store: &S) -> Result<(), S::Error> {
let keys: Vec<&[u8]> = vec![b"cid-a", b"cid-a", b"cid-b"];
let values = store.batch_get_ordered(&keys).await?;
assert_eq!(values.len(), 3);
Ok(())
}
async fn read_tree<S>(prolly: &AsyncProlly<S>, tree: &prolly::Tree) -> Result<(), prolly::Error>
where
S: AsyncStore,
S::Error: Send + Sync,
{
let value = prolly.get(tree, b"cid-a").await?;
assert_eq!(value, Some(b"node bytes".to_vec()));
Ok(())
}
async fn scan_tree<S>(prolly: &AsyncProlly<S>, tree: &prolly::Tree) -> Result<(), prolly::Error>
where
S: AsyncStore,
S::Error: Send + Sync,
{
let mut iter = prolly.range(tree, b"k", Some(b"l")).await?;
while let Some(entry) = iter.next().await {
let (_key, _value) = entry?;
}
Ok(())
}
async fn scan_page<S>(
prolly: &AsyncProlly<S>,
tree: &prolly::Tree,
cursor: &prolly::RangeCursor,
) -> Result<prolly::AsyncRangePage, prolly::Error>
where
S: AsyncStore,
S::Error: Send + Sync,
{
prolly.range_page(tree, cursor, Some(b"l"), 100).await
}
async fn write_tree<S>(prolly: &AsyncProlly<S>) -> Result<prolly::Tree, prolly::Error>
where
S: AsyncStore,
S::Error: Send + Sync,
{
let tree = prolly.create();
let tree = prolly
.put(&tree, b"k1".to_vec(), b"v1".to_vec())
.await?;
let tree = prolly.delete(&tree, b"k1").await?;
Ok(tree)
}
非同期ストアのデフォルトの順序付きバッチ読み取りは、繰り返しキーを重複排除し、結果スロットを保持し、ポイント読み取りを read_parallelism() までオーバーラップできます。ネイティブマルチゲットを持つストアは、batch_get_ordered を直接オーバーライドできます。広範な非同期ツリー走査は、統計、到達可能性、差分、範囲、バッチルーティング、および不足ノード同期がリモートまたはオブジェクトストアスタイルのバックエンドに無制限のマルチゲットを渡さないように、子フロンティアプリフェッチをチャンクします。
大規模値オフロードにも非同期ネイティブブロブサポートがあります。AsyncBlobStore は BlobStore をミラーリングし、SyncBlobStoreAsAsync はランタイム依存関係なしで埋め込みブロブストアをアダプトし、AsyncProlly は非同期ブロブバックエンドを介して put_large_value、get_large_value、mark_reachable_blobs、plan_blob_gc、および sweep_blob_gc を実行できます。
use prolly::{
AsyncProlly,
Config,
LargeValueConfig,
MemBlobStore,
MemStore,
SyncBlobStoreAsAsync,
SyncStoreAsAsync,
};
use std::sync::Arc;
let node_store = Arc::new(MemStore::new());
let prolly = AsyncProlly::new(SyncStoreAsAsync::new(node_store), Config::default());
let blobs = SyncBlobStoreAsAsync::new(MemBlobStore::new());
let policy = LargeValueConfig::new(1024);
async fn write_doc<B>(
prolly: &AsyncProlly<SyncStoreAsAsync<Arc<MemStore>>>,
blobs: &B,
policy: LargeValueConfig,
) -> Result<prolly::Tree, prolly::Error>
where
B: prolly::AsyncBlobStore,
B::Error: Send + Sync,
{
let tree = prolly.create();
let tree = prolly
.put_large_value(blobs, &tree, b"doc/body".to_vec(), vec![7; 4096], policy)
.await?;
assert!(prolly.get_large_value(blobs, &tree, b"doc/body").await?.is_some());
Ok(tree)
}
AsyncProlly は、一般的なツリー作業のために同期APIをミラーリングします。
- 読み取りと書き込み:
create、get、get_many、put、delete、およびbatch - スキャン: 範囲イテレーション、
range_after、range_from_cursor、range_page、およびreverse_page - 差分: イーガー
diff、range_diff、ストリーミング差分、および競合ストリーミング - マージ: 標準的な3者
merge、merge_explain、およびCRDTcrdt_merge - 操作: 統計、デバッグビュー、到達可能性、不足ノード同期、キャッシュ統計、キャッシュピン留め、およびキャッシュクリア
非同期バッチは、順序付き非同期ノードロードを介してソートされたミューテーション範囲をルーティングします。影響を受ける各リーフを1回適用し、影響を受ける祖先のみを再構築し、書き換えられたノードを1回フラッシュします。
非同期差分はCIDによって等しいサブツリーをスキップし、ストアがバッチ読み取りを優先する場合は順序付き非同期バッチ読み取りを介して変更されたフロンティアを水和します。ストリーミング差分は、AsyncDiffIter::next().await および into_stream() を介して同じプルーニングを公開します。
非同期マージは、同期マージと同じ削除を考慮したリゾルバーモデルを使用します。merge_explain は、成功したマージと Error::Conflict の両方で型付きトレースを保持し、非同期CRDTマージは同期CRDTマージと同じ競合フリー戦略を使用します。
追加負荷の高い非同期バッチは、同期追加バッチと同じ右端パスヒント名前空間を使用するため、新しい非同期マネージャーは追加アンカーを順序付き読み取りで水和できます。
本番アーキテクチャ、正しさ契約、可視性レベル、キャンセルセマンティクス、およびブラウザ/WASM制約については、docs/async-store.md を参照してください。
ブロッキングストアを使用する非同期アプリケーションの場合、tokio 機能を有効にし、ストアを TokioBlockingStore でラップします。これにより、同期ストアコールがTokioのブロッキングスレッドプールで実行され、ランタイムワーカーをブロックしません。
use prolly::{AsyncProlly, Config, MemStore, TokioBlockingStore};
use std::sync::Arc;
let store = Arc::new(MemStore::new());
let async_store = TokioBlockingStore::from_arc(store);
let prolly = AsyncProlly::new(async_store, Config::default());
キャッシュとヒント
各 Prolly<S> または AsyncProlly<S> マネージャーは、同じ2つのエンジンキャッシュを所有します。
node_cache: CIDでキー付けされた不変ノード。rightmost_path_cache: 追加負荷の高いワークロードで既知の右端。
デコードされたノードキャッシュは、履歴動作を維持するためにデフォルトで無制限です。保持されたノードを制限するには Config::builder().node_cache_max_nodes(n) を、保持されたシリアライズされたノードの重みを制限するには node_cache_max_bytes(bytes) を、または両方を組み合わせてハードメモリ予算を設定します。どちらの制限にも 0 を渡すと、ノードキャッシングが無効になります。キャッシュエビクションは安全です。キャッシュミスは常にバックエンドストアにフォールバックします。
ホットスナップショットは、パフォーマンスヒントとしてキャッシュエントリをピン留めできます。同じルートから多くの読み取りが開始される場合は pin_tree_root(&tree) を、ホットキー範囲のルートからリーフへのパスをメモリに保持するには pin_tree_path(&tree, key) を使用します。ピン留めされたエントリは、一時的に構成されたキャッシュ制限を超える可能性があります。ワークロードフェーズが終了したら unpin_all_cache_nodes() を呼び出して、通常の削除がキャッシュを再度トリミングできるようにします。AsyncProlly は、非同期メソッドとして同じピン留めAPIを公開します。
ストアはパフォーマンスヒントを永続化することもできます。ヒント対応ストアは、新しい同期または非同期マネージャーが追加アンカーを順序付きバッチ読み取りで水和できるように、ノード書き込みとともに右端パスヒントを格納できます。ヒントは決して正確さのために必要ではありません。呼び出し元は常に通常の走査フォールバックを持っています。
ホットプレフィックス範囲の場合、同期マネージャーは、バックグラウンドインデックス作成または同期ジョブのために、ルートからリーフへのパスヒントを明示的に永続化および水和できます。これは、サービスが新しいワーカーから同じテナント、ワークスペース、ドキュメント、またはインデックスシャードを繰り返しスキャンする場合に役立ちます。
use prolly::{Config, FileNodeStore, Prolly};
use std::sync::Arc;
let store = Arc::new(FileNodeStore::open("./target/prolly-prefix-hints").unwrap());
let prolly = Prolly::new(store.clone(), Config::default());
let tree = prolly.create();
let tree = prolly
.put(&tree, b"tenant/42/doc/1".to_vec(), b"body".to_vec())
.unwrap();
let prefix = b"tenant/42/";
let _published = prolly.publish_prefix_path_hint(&tree, prefix).unwrap();
let fresh_worker = Prolly::new(store, tree.config.clone());
let _hydrated = fresh_worker
.hydrate_prefix_path_hint(&tree, prefix)
.unwrap();
ヒントが存在しない、古い、破損している、または不足しているノードを指している場合、水和は false を返し、通常のツリー走査は正確なままです。
既に影響を受けるキー範囲を知っているライターは、バックグラウンドインデックス作成または同期ジョブのために、最近変更されたスパンヒントを永続化することもできます。
use prolly::ChangedSpan;
let old_root = tree.clone();
let tree = prolly
.put(&old_root, b"tenant/42/doc/2".to_vec(), b"new body".to_vec())
.unwrap();
spans = vec![ChangedSpan::for_prefix(b"tenant/42/".to_vec())];
let _published = prolly
.publish_changed_spans_hint(&old_root, &tree, spans)
.unwrap();
if let Some(hint) = prolly.load_changed_spans_hint(&old_root, &tree).unwrap() {
for span in hint.spans {
let _diffs = prolly
.range_diff(&old_root, &tree, &span.start, span.end.as_deref())
.unwrap();
}
}
変更スパンヒントは助言的なものです。これらは、プロデューサーが信頼できる場合、またはワーカーが最も可能性の高いホット範囲を優先したい場合に役立ちますが、呼び出し元は常に権威ある変更検出のために完全な diff、range_diff、または structural_diff_page にフォールバックできます。
テストまたは外部ストアメンテナンスの後、clear_cache() を使用します。これは、Prolly API外でバックエンドストアを意図的に変更します。cache_len() および cache_bytes_len() を使用して、現在のノードキャッシュサイズを検査します。cache_pinned_len() および cache_pinned_bytes_len() を使用して、ピン留めされたエントリを検査します。
マネージャーメトリクス
Prolly および AsyncProlly は、キャッシュとノードI/Oの観測可能性のための軽量累積メトリクスを公開します。
use prolly::{Config, MemStore, Prolly};
let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly.create();
let tree = prolly.put(&tree, b"k".to_vec(), b"v".to_vec()).unwrap();
let metrics = prolly.metrics();
assert!(metrics.nodes_written > 0);
prolly.reset_metrics();
prolly.clear_cache();
let _ = prolly.get(&tree, b"k").unwrap();
let metrics = prolly.metrics();
assert!(metrics.node_cache_misses > 0);
assert!(metrics.nodes_read > 0);
メトリクスは、バックエンド固有の圧縮またはレイアウトの前に、マネージャーが観測したシリアライズされたノードバイトをカウントします。キャッシュヒットは、インプロセスキャッシュから提供される要求されたノードスロットです。キャッシュミスは、バックエンドストアから取得された一意のノードCIDです。キャッシュエビクションは、マネージャーキャッシュから削除されたデコードされたノードをカウントします。メトリクスをリセットしてもキャッシュはクリアされません。
設定
use prolly::{chunking, Config, Encoding, NodeLayoutSpec};
let config = Config::builder()
.chunking(chunking::entry_count_key_hash())
.node_layout(NodeLayoutSpec::PrefixCompressed)
.encoding(Encoding::Raw)
.node_cache_max_nodes(50_000)
.node_cache_max_bytes(256 * 1024 * 1024)
.read_parallelism(8)
.build();
チューニングガイド:
| 設定 | 効果 |
|---|---|
chunking | パーシステッド測定、境界入力、ハッシュルール、境界、シード、およびレベルソルティングを選択します。 |
node_layout | プレフィックス圧縮、プレーン、またはオフセットテーブルノードバイトを選択します。 |
encoding | パーシステッド値エンコーディングメタデータを記録します。 |
node_cache_max_nodes | マネージャーごとに保持されるデコードノードを上限設定します。無制限の場合は省略し、無効にするには 0 を使用します。 |
node_cache_max_bytes | 保持されたシリアライズノードの重みを上限設定します。予測可能なメモリ予算のためにノード数と組み合わせてください。 |
read_parallelism | ランタイム専用の優先順位付き読み取り同時実行性。CIDには影響しません。 |
永続ストアの場合、チャンクが大きいほどノード数とI/Oが減少し、チャンクが小さいほど編集の局所性と差分粒度が向上する傾向があります。
組み込みチャンキングポリシーは明示的であり、ツリーフォーマットに永続化されます。
| ポリシー | それを選択する理由 |
|---|---|
entry_count_key_hash() | デフォルトを希望する場合:安定したキーのみの境界と予測可能なファンアウト。値のみの更新は境界を移動しません。 |
entry_count_key_value_hash() | 値のコンテンツは境界IDに参加する必要があり、値の更新は意図的に再チャンクする可能性があります。 |
logical_bytes_key_weibull() | レコードのサイズが大幅に異なり、バイトターゲットの周りにスムーズな確率的チャンクが必要な場合。 |
logical_bytes_rolling_hash() | ローリングウィンドウを備えたコンテンツ定義の論理バイトチャンクと、シフトされたコンテンツ後の強力な再同期が必要な場合。 |
すべてのポリシーは同じステートフルな BoundaryDetector と正規ノードエミッターを使用します。hard_max_node_bytes は、リリースビルドで正確なシリアライズノードに対してチェックされます。チャンキングポリシーまたはレイアウトの変更は、永続化されたツリーIDを変更します。これらはランタイムチューニングスイッチではありません。
このアルファ版のハードカットオーバーでは、ステートレス境界プローブと直接ノードリバランサーAPIが削除されました。どちらも永続化されたポリシーのストリーム状態を表すことができなかったためです。診断のために、順序付けられたエントリ全体で BoundaryDetector::observe を駆動し、書き込みには Prolly::batch、append_batch、またはそれらの統計バリアントを使用します。
統計
collect_stats(&tree) はツリーを走査し、TreeStats を返します。これには以下が含まれます。
- ノード、リーフ、内部ノードの数。
- ツリーの高さ。
- 合計キー/値ペア。
- シリアライズされたサイズメトリクス。
- レベルごとのエントリ。
- ファンアウトと充填率。
- キーと値のサイズ分布。
stats_diff(&before, &after) を使用して、両側を収集し、ベースライン統計、候補統計、絶対差分、およびパーセント差分を含む StatsComparison を返します。
let comparison = prolly.stats_diff(&before, &after).unwrap();
println!(
"entries: {:+}, bytes: {:+}",
comparison.absolute.total_key_value_pairs_diff,
comparison.absolute.total_tree_size_bytes_diff
);
これは、チャンキングパラメータのチューニング、ストレージバックエンドの比較、またはベンチマークでの書き込み増幅の追跡に役立ちます。
デバッグ可視化
debug_tree(&tree) は、ルートからリーフまでグループ化された TreeDebugView を返します。各ノードには、CID、レベル、リーフ/内部の種類、エントリ数、充填率、エンコードバイトサイズ、およびキー範囲が含まれます。
let view = prolly.debug_tree(&tree).unwrap();
println!("{}", view.to_text());
debug_compare_trees(&before, &after) は、共有、左のみ、右のみのCIDを報告するため、テスト、CLI、およびベンチマークレポートは、どのサブツリーが再利用または書き換えられたかを確認できます。
let comparison = prolly.debug_compare_trees(&before, &after).unwrap();
println!("{}", comparison.to_text());
assert!(comparison.shared_nodes > 0);
AsyncProlly は、順序付き非同期バッチ読み取りを介して子フロンティアをロードするのと同じメソッドを公開します。
CLI検査
prolly-inspect バイナリは、ファイルシステムバックエンドの FileNodeStore で名前付きルートを検査します。これは、ローカルデバッグ、CI成果物、およびGCまたは同期ジョブ前のオペレーターチェックを目的としています。
cargo run --bin prolly-inspect -- /path/to/store roots
cargo run --bin prolly-inspect -- /path/to/store stats main
cargo run --bin prolly-inspect -- /path/to/store walk main
cargo run --bin prolly-inspect -- /path/to/store compare main feature
cargo run --bin prolly-inspect -- /path/to/store changed main feature
cargo run --bin prolly-inspect -- /path/to/store verify --all
コマンドは、名前付きルートをリストし、ツリー統計を表示し、ノードレベルと充填率をレンダリングし、共有と書き換えられたサブツリーを比較し、変更されたキー範囲を要約し、1つのルートまたはすべての名前付きルートからの到達可能性をドライランします。
複雑さ
おおよそのコスト:
| 操作 | コスト |
|---|---|
get | O(log n) ノード訪問 |
put / delete | O(log n) パス書き換えと再調整 |
range | k 個のエントリの場合 O(log n + k) |
batch | ミューテーションをソートおよびグループ化し、影響を受けるリーフと祖先を書き換えます |
diff | 境界が整列する場合 O(変更されたサブツリー)。それ以外の場合はローカル順序付きフォールバック |
同じルートの diff | O(1) |
merge | 差分と、競合しない変更のバッチ適用 |
テストとベンチマーク
クレートテストを実行します。
cargo test
SQLiteアダプターテストを実行します。
cargo test --manifest-path stores/prolly-store-sqlite/Cargo.toml
リリース品質チェックを実行します(CIで使用)。
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --features tokio
cargo check --bin prolly-inspect
cargo check --examples
cargo check --benches --features tokio
共有ストア契約カバレッジを実行します。
cargo test --test store_conformance
cargo test --features async-store --test async_store
cargo test --manifest-path stores/prolly-store-sqlite/Cargo.toml
cargo test --manifest-path stores/prolly-store-redb/Cargo.toml
cargo test --manifest-path stores/prolly-store-rocksdb/Cargo.toml
cargo test --manifest-path stores/prolly-store-slatedb/Cargo.toml
cargo test --manifest-path stores/prolly-store-pglite/Cargo.toml
PGlite契約はデフォルトでコンパイルされ、PROLLY_PGLITE_TEST=1 が設定されている場合にのみNode.jsサイドカーを開きます。
mkdir -p /tmp/prolly-pglite-node
npm install --prefix /tmp/prolly-pglite-node @electric-sql/pglite@0.5.3
PROLLY_PGLITE_TEST=1 PROLLY_PGLITE_NODE_CWD=/tmp/prolly-pglite-node \
cargo test --manifest-path stores/prolly-store-pglite/Cargo.toml
メインベンチマークハーネスを実行します。
PROLLY_BENCH_SCALE=5000 cargo bench -p prolly-map --bench prolly_bench
AI/ローカルファーストワークロードハーネスを実行します。
PROLLY_AI_BENCH_SCALE=10000 cargo bench --bench ai_workloads_bench
厳密なセカンダリインデックス構築/更新/クエリ/転送ハーネスを実行します。
PROLLY_INDEX_BENCH_SCALE=1000 PROLLY_INDEX_BENCH_BATCH=64 \
cargo bench --bench secondary_index_bench
フォーカスされたSQLiteスケールハーネスを実行します。
PROLLY_SQLITE_SCALE_STAGES=1000000,10000000 \
PROLLY_SQLITE_SCALE_BATCH=100000 \
cargo bench --manifest-path stores/prolly-store-sqlite/Cargo.toml --bench sqlite_scale_bench
Dolt GoとRust prollyツリーをSQLiteバックエンドと比較します。
BENCH_PROFILE=smoke scripts/run_dolt_sqlite_comparison.sh
完全なマトリックス、タイミング境界、正しさゲート、および解釈制限については、docs/prolly-go-rust-sqlite-benchmark.md を参照してください。
パフォーマンスガイド、現在のベンチマークカバレッジ、および測定されたSQLiteスケール結果については、docs/performance.md を参照してください。
モジュールマップ
| モジュール | 責任 |
|---|---|
tree.rs | 永続的な Tree ハンドル。 |
node.rs | ノードレイアウト、コンパクトシリアライゼーション、ノードCID計算。 |
cid.rs | SHA-256コンテンツ識別子。 |
config.rs | チャンキングとエンコーディング設定。 |
boundary.rs | ステートフルでポリシーを意識したコンテンツ定義境界検出。 |
batch.rs | バッチルーティング、コレクター、および正規値更新ヘルパー。 |
builder.rs | 並列バルク構築と正規ストリーミングノードエミッター。 |
range.rs | 遅延範囲イテレーション。 |
cursor.rs | カーソル走査とストリーミング差分カーソル。 |
diff.rs | 構造差分、範囲差分、および3者マージ。 |
crdt.rs | 競合フリーマージ戦略。 |
parallel.rs | 正規書き込み上の並列バッチアダプター。 |
streaming.rs | ストリーミング差分トレイトとデフォルト実装。 |
stats.rs | ツリー形状とサイズメトリクス。 |
store/ | ストレージトレイトとバックエンド実装。 |
proximity/ | 正確なベクトルディレクトリ、決定論的ANN階層、検索、コーデック、検証、およびローカライズされたミューテーション。 |
使用時期
複数のバージョンを安価に保持し、それらを差分化、マージ、またはコンテンツアドレス指定ストアに永続化できる順序付きマップが必要な場合は、このクレートを使用してください。ローカルファーストデータベース、バージョン管理されたメタデータインデックス、レプリケーション/同期状態、およびTrailのようなスナップショット間で安定した構造的IDを必要とするシステムに適しています。