・0 pv・5 min read
相互依存関係を一元的に管理するための中心的なデータ構造の仕組み①
相互依存関係を一元的に管理するための中心的なデータ構造の仕組み①
インクリメントな変更を効率的に更新する手法(増分ビルドとか)についてのメモ
語句
- ノード: バージョン
- エッジ: バージョン間の依存関係
- delta: 差分
操作順序と差分管理
ドキュメント全体の状態（＝バージョン）をノードとして表現し、それらの間の更新履歴や依存関係をツリー構造として管理する
version_id to GVT node map
左図
- A → B バージョンAから派生してバージョンBが作られた。
- A → C バージョンAから派生してバージョンCが作られた。
- C → E バージョンCからさらにEが作られた。 …といった具合に、バージョン生成の親子関係を表す矢印が引く。
右図
- Pre-order sort (例: A, B, D, C, E) ツリーを先行順（深さ優先で「自分 → 子供」）に走査した際の順序。
- Post-order sort (例: D, B, E, C, A) ツリーを後行順（深さ優先で「子供 → 自分」）に走査した際の順序。
- Creation-order sort (例: 0, 1, 2, 3, 4, 5) バージョンが生成された（作られた）順序。いわゆる「作成時系列」の並び。
並び情報は、バージョンが他のバージョンの祖先かどうかを判定するのに使用。典型的には、あるノード と の前行番号・後行番号を比較することで、「 が の祖先である」かどうかを定数時間で判定できる。
右下図
「各バージョンID」→「GVTノード」への対応表（マップ）
バージョン管理を追加
Versioned Object
- Log: どの時点でどのバージョンが生まれたかを記録しているログ。差分情報やメタデータも入る。
- current global version #: 現在アクティブなバージョン、または最新のグローバルバージョン番号。
Pre-orderとPost-orderの組み合わせによる祖先判定において、ノード がノード の祖先であるための必要十分条件は、以下になる。
つまり、 が に完全に含まれている形になるので、ふたつの数値比較だけで先祖関係がわかる。
Creation-order（作成順）では、最新バージョンの生成時に連番を通知することに使う。タイムスタンプとしての機能も担う。
式1のサンプル
A
/ \
B C
DFSをA,B,Cの順で訪れる
-
Aに到達:
- pre(A) = 1
-
Bに移動して到達:
- pre(B) = 2
- Bには子がないので、Bの探索終了
- post(B) = 3
-
Aに戻り、Cに移動して到達:
- pre(C) = 4
- Cにも子がないので、Cの探索終了
- post(C) = 5
-
Aのすべての子が探索されたので、Aの探索終了:
- post(A) = 6
結果として、各ノードは以下の時刻を持つ:
- A: pre = 1, post = 6
- B: pre = 2, post = 3
- C: pre = 4, post = 5
差分管理について
Differential Versioned Object
差分バージョン管理されたオブジェクトの表現。
Versioned Objectの図で示したようにノードの関係性をたどったメタ情報のみをcached value(s)に格納するlogオブジェクトのコードイメージとしては以下のようになる。const std = @import("std");
/// 差分情報（delta）の構造体
const Delta = struct {
version: u32, // delta が適用されるバージョン番号
diff: []const u8, // 差分情報
};
/// 差分情報を管理するバージョン管理オブジェクト
/// 現在の完全な状態（currentValue）と、過去の変更履歴（deltas のリスト）を保持。
pub const VersionedObject = struct {
allocator: *std.mem.Allocator,
currentValue: []const u8, // 最新の完全な状態（キャッシュ）
deltas: std.ArrayList(Delta), // 差分情報のログ（各エントリが delta を表す）
pub fn init(allocator: *std.mem.Allocator, initialValue: []const u8) !VersionedObject {
var obj = VersionedObject{
.allocator = allocator,
.currentValue = initialValue,
.deltas = std.ArrayList(Delta).init(allocator),
};
return obj;
}
/// 新たな delta を追加して新バージョンを記録する関数(好きなロジックを入れる)
pub fn addDelta(self: *VersionedObject, newDelta: Delta) !void {
try self.deltas.append(newDelta);
}
/// 指定したバージョンの状態を再構築する（好きなロジックを入れる）
pub fn reconstructVersion(self: *VersionedObject, targetVersion: u32) []u8 {
return self.currentValue;
}
};
pub fn main() !void {
var allocator = std.heap.page_allocator;
var obj = try VersionedObject.init(allocator, "Initial value");
var delta = Delta{
.version = 1,
.diff = " updated",
};
try obj.addDelta(delta);
const version1 = obj.reconstructVersion(1);
std.debug.print("Version 1: {s}\n", .{version1});
}次回へ続く