Proposal: Version Checkpointing

[majin1102]

Motivation

• Timeline queries require O(N) manifest reads (dataset.versions()), where N = number of versions, which would significantly impact memory and response time if the manifests are big enough.
• After cleanup, older version metadata is lost. Sometimes we want to save history commit changes even we don't need to check the data.

Goal:

• Stable versions() performance: Make dataset.versions() highly performant with consistent latency
• Support time travel: Query any historical version metadata within a version/time window by O(1) lookup
• Transaction and version history: View the full/nearly full transaction history of changes even after cleanup

There's also a related API proposal #5885 and the motivation has been raised in that thread.

Overall design

Layout

dataset/
├── _checkpoints/
│   ├── 00000000000000000020.lance  # checkpoint at version 20
│   └── 00000000000000000030.lance  # checkpoint at version 30 (latest)
├── _versions/
│   └── ...
└── ...

• Checkpoint files use version-based naming: {version:020}.lance
• Each checkpoint file contains metadata for all preserved versions in Lance format (Arrow RecordBatch)

Spec

The checkpoint is stored as a Lance file containing an Arrow RecordBatch with the following schema:

Field	Type	Description
version	UInt64	The manifest version number
timestamp_millis	Int64	Manifest creation timestamp in milliseconds
total_fragments	UInt64	Total number of fragments
total_data_files	UInt64	Total number of data files
total_files_size	UInt64	Total size of all files
total_deletion_files	UInt64	Total number of deletion files
total_data_file_rows	UInt64	Total rows in data files
total_deletion_file_rows	UInt64	Total rows in deletion files
total_rows	UInt64	Total rows (data - deletions)
is_tagged	Boolean	Whether this version is pinned by a tag
is_cleaned_up	Boolean	Whether the data files have been cleaned up
transaction_uuid	String (nullable)	Transaction UUID for external transaction files
read_version	UInt64 (nullable)	The base version read by the transaction
operation_type	String (nullable)	Operation type string (e.g., "Append", "Delete")
transaction_properties	String (JSON)	Transaction properties as JSON string

Metadata (stored in Lance file metadata):

• lance:checkpoint:dataset_created: Dataset creation timestamp (inherited, never changes)
• lance:checkpoint:created_at: Checkpoint creation timestamp

Key Design Decisions

1. Append-only Checkpoint: Each cleanup operation writes a new checkpoint file containing all preserved versions
2. Version-based Filename: Simple {version:020}.lance naming for easy lookup
3. Graceful Degradation: If latest checkpoint is corrupted, fall back to previous checkpoints
4. Idempotent & Conflict-free: Same version range always produces identical file content, so concurrent writes never conflict
5. Lance Format: Uses native Lance format for efficient columnar storage and compression

Configuration

Parameter	Default	Description
enabled	true	Enable/disable checkpointing
max_entries	10000	Max versions per checkpoint file
max_checkpoint_files	2	Max checkpoint files to retain

Trigger Flow

cleanup.run()
      │
      ▼
process_manifests()          ──►  Scan all manifests, identify old vs retained
      │
      ▼
delete_unreferenced_files()  ──►  Delete data files not referenced by retained manifests
      │
      ▼
archive_versions()           ──►  Archive version metadata (checkpoint)
      │
      ▼
cleanup_old_checkpoints()    ──►  Delete old checkpoint files beyond max_checkpoint_files
      │
      ▼
Done

archive_versions() detailed flow:

1. Load latest checkpoint file (or create new if none exists)
      │
      ▼
2. Identify existing checkpointed versions from loaded checkpoint
      │
      ▼
3. Scan current manifest files from _versions/ directory
      │
      ▼
4. For each manifest version NOT in checkpoint:
      - Read manifest file
      - Extract version metadata
      - Add to checkpoint
      │
      ▼
5. Mark versions that were cleaned up with is_cleaned_up = true
      │
      ▼
6. Apply max_entries limit (remove oldest if exceeded)
      │
      ▼
7. Write new checkpoint file

Key Points:

1. Checkpoint happens AFTER cleanup: This ensures we capture the final state of all versions after cleanup decisions are made
2. Incremental update: Only new versions since last checkpoint are added; existing entries are updated (is_cleaned_up flag)
3. is_cleaned_up flag: Marks versions whose data files have been removed (cannot checkout, but can query metadata)
4. Single write per cleanup: One new checkpoint file written, old ones pruned by count
5. No version increment: Checkpoint updates do NOT create new dataset versions - they are metadata-only operations
6. Existing datasets: On first checkpoint, only currently existing versions are checkpointed. No migration or schema changes required - datasets without checkpoint files simply have no checkpoint history yet

Why Not a System Index?

We chose NOT to implement this as a system index for these core reasons:

1. Avoid polluting dataset version lineage: A system index would require creating a new manifest version each time checkpoint is updated. Since checkpoint happens during cleanup (not during normal writes), this would create unnecessary versions in the dataset's version history, polluting the timeline.

2. Self-contained files: Checkpoint files are standalone Lance files stored in _checkpoint/ directory. They don't need to be tied to any specific manifest version and can be managed independently.

3. No index infrastructure dependencies: System indices require complex infrastructure (index metadata, cleanup, migration, etc.). Checkpoint files are simple, self-describing files that can be inspected/debugged without any special tools.

The key insight is: VersionCheckpoint is metadata about versions, not data to be indexed for queries. It doesn't need to be versioned alongside the data - it provides a historical view that transcends individual dataset versions.

Graceful Degradation

If the latest checkpoint file fails to load (corruption, partial write, etc.):

1. List all checkpoint files in the directory
2. Sort by version (descending, newest first)
3. Try each file until one loads successfully
4. If all fail, return empty (timeline falls back to manifest-only reads)

This ensures partial writes or corruption don't break the system - users simply get slightly older checkpoint data.

Storage Overhead

Component	Size
Per-version metadata	~200 bytes
10K versions	~2 MB
2 checkpoint files (default)	~4 MB total

This is negligible compared to typical dataset sizes and provides significant query performance benefits.

Performance Overhead

Checkpoint runs as part of cleanup, which already scans all manifests. Since checkpoint can reuse that scan, the additional cost is minimal:

• Read: One additional read of the previous checkpoint file (typically ~KB), potentially several transaction file reads.
• Write: One write of the new checkpoint file (~2MB for 10K versions)

Implementation Details

Transaction Properties Size Limit

Transaction properties are stored as JSON strings. To prevent performance issues:

• Limit: 10KB per transaction properties
• Overflow handling: If exceeded, the JSON is truncated to 10KB and wrapped as:

  {"_truncated":true,"_size":<original_size>,"_data":<truncated_json>}

• Parsing fallback: If the wrapped JSON fails to parse, the raw string is preserved in the transaction_properties key for debugging

Code Structure

pub struct VersionCheckpoint {
    versions: Vec<VersionSummary>,
    latest_version_number: u64,
    dataset_created_millis: i64,
    created_at_millis: i64,
    config: CheckpointConfig,
    base: Path,
    object_store: Arc<ObjectStore>,
}

Key methods:

• load_or_new(): Load latest checkpoint or create empty one
• add_summaries(): Add new version summaries
• flush(): Write checkpoint to storage
• cleanup_old_checkpoints(): Prune old checkpoint files

[westonpace]

In general I like the idea. You list one of the goals as "support time travel". However, if a manifest has been archived, we can't check it out right? How do archive files support time travel?

I do like the idea of keeping the archive around for auditing and debugging a dataset.

I think you are missing a message for ManifestSummary? Should we include the entire transaction instead of just the uuid?

[majin1102]

In general I like the idea. You list one of the goals as "support time travel". However, if a manifest has been archived, we can't check it out right? How do archive files support time travel?

The phrase support time travel might be a bit misleading. By "support," I specifically mean the ability to resolve a target version directly through archived files—without requiring a full scan of manifests.

A couple of clarifications on how this works:

1. Archiving is greedy: Each cleanup operation archives the most recent complete versions. So, a manifest being archived does not imply it has already been cleaned up.
2. Cleanup status tracking: If a manifest has been cleaned up, there's an is_cleaned_up field to indicate whether that version is still eligible for time travel.

Even with these mechanisms in place, there's still a small chance of encountering a file not found error if cleanup is happening concurrently with a time-travel query. This is an inherent edge case in any eventually-consistent cleanup workflow.

I think you are missing a message for ManifestSummary? Should we include the entire transaction instead of just the uuid?

1. Yeah, I missed ManifestSummary initially. However, I think a flatter structure might work better for the spec overall. The transformed structure will include ManifestSummary accordingly—I've already updated it.

2. Actually, I do include read_version, uuid, operation_type, and transaction_properties; I just excluded the operation details. I'm not sure whether operation details will be useful in the future (we don't include manifest details either), and I'm concerned that their potential size could be unpredictable.

[jackye1995]

Overall I like the idea, I think we all want something like this, and I agree that doing it separately is better than making it a system index that could produce new versions. For existing system indexes, we want the related operation to check conflict with existing operations, so doing them as a part of table manifest makes sense. Here the case is the reverse, we don't want to interfere with table manifest versioning further.

But just for the purpose of time travel, I didn't fully get the perf benefit. The archived file would be larger, and we will have to read those files, so the performance is not necessarily better than doing a binary search (or multiway search if we want to be even faster and fully leverage object store bandwidth)

Just to brainstorm here, 2 approaches I could think of to accelerate the time travel:

alternative 1: oldest_version_hint.json

When cleanup, write a oldest_version_hint.json that simply records the oldest version available. Combined with latest version, we then we do binary ssearch between the version range.

The problem of this approach is that if we keep may tags and branches, the range has holes, and could be unevenly distributed, causing search to be inefficient.

alternative 2: checkpoint.binpb

When cleanup, directly write a map of version number -> creation time in protobuf for all retained manifests, name it checkpoint.binpb. This is basically a lite version of the version archive, but it is much smaller, you can store 20k entries in 200KB, so basically 1 file is sufficient. We can also consider storing it as a lance file, if that is more performant and compact

Then for any version higher than the checkpoint file's latest tracked version, we can do binary search if time travel falls out of the range.

I feel we probably need this to be truly performant?

[majin1102]

The archived file would be larger, and we will have to read those files, so the performance is not necessarily better than doing a binary search

There's an issue in binary search approach: binary search requires ordering by manifest timestamp. However, unless we fully read the manifest, we cannot guarantee a strict timestamp ordering (ltimestamp_nanos may not be monotonically increasing with version in distributed deployments—particularly when writers have unsynchronized clocks or when commits occur concurrently). This creates a paradox. Please let me know if I've missed anything。

As I understand, the archive file only contains the metadata of manifest files and transaction files(exclude fragments and operation details). It shouldn't be that large. I give a evaluation in this proposal:

Component	Size
Per-version metadata	~200 bytes
10K versions	~2 MB
3 archive files (default)	~6 MB total

I think a typical archive file should be around 6 MB. For time-travel queries—whether for a single point or a range—we can load the latest archive file (~6 MB) into memory, where versions are strictly sorted by timestamp, and perform an in-memory binary search.

However, the archive file might not include the most recent versions. In that case, we would need to fall back to an incremental scan of the manifest files that are not yet covered by the archive. I think we could define some heuristic conditions to determine whether it's necessary to scan recent manifest files—for example, if the latest timestamp in the archive file is more than 1 hour ahead of the target time-travel timestamp, we could skip the incremental scan.

Here's a little example:

Let's say we have a dataset with 1-10 versions initially.

• t1: 1-10, never cleanup, no archive
• t2: 1-12, prepare to cleanup

Now we could time travel by scanning all manifest files at t1 and t2. After a cleanup:

• t3: 3-12, archive: 1-12, now we could time travel by archive file
• t4: 3-15, archive: 1-12, travel by archive by archive file and scanning 13-15 manifest files

Then for any version higher than the checkpoint file's latest tracked version, we can do binary search if time travel falls out of the range.

IMO, the archive file is similar to the checkpoint you mentioned, except it might be 10-50 times larger(Performance impact is likely negligible in this case). The key difference lies in whether we can perform a binary search when the target version falls out of the archived range.

What do you think about the binary search?

[majin1102]

I think we can use _checkpoint/xxxxxxx.binpb as the layout. What do you think? @jackye1995 If you agree I will follow up in the PR

[jackye1995]

However, unless we fully read the manifest, we cannot guarantee a strict timestamp ordering (ltimestamp_nanos may not be monotonically increasing with version in distributed deployments—particularly when writers have unsynchronized clocks or when commits occur concurrently)

Actually, I had a PR for that, just don't get time to push it through... #5899

[majin1102]

Actually, I had a PR for that, just don't get time to push it through... #5899

Then for any version higher than the checkpoint file's latest tracked version, we can do binary search if time travel falls out of the range.

Great, than we can make incremental version query more performant

[majin1102]

I've modified dataset.versions() to support reading from archived files(and incremental read by manifest files). Code review is in #6049. Detailed benchmarks are provided below.

TL,DR

The Version Archive feature improves dataset.versions() performance by 1.5x to 899.8x on S3 and 5.0x to 12,200x on local storage , with improvements scaling dramatically as version count and manifest size increase—making version listing operations near-instantaneous regardless of dataset history size.

However, the current block only handles the case where dataset.versions() relies solely on the archive file. The following block introduces an incremental versioning scenario to simulate a production environment more accurately

Test Methodology

Test Scenario

We measure the time to list all versions of a dataset under two conditions:

• Without Archive: Don't cleanup and generate archive files, dataset.versions() requires individual manifest file reads
• With Archive: Trigger cleanup to generate archive file without cleaning any versions, dataset.versions() will go reading archive file.

For each test we use 3 seconds to warnup and run 10 samples and take the average value.

Test Variables

1. Number of Versions: 2, 4, 8, 16, 32, 64, 128, 256, 512
2. Manifest Size (Fragments):

• 1k fragments, manifest size 60k
• 10k fragments, manifest size 600k
• 100k fragments, manifset size 6m

3. Storage Backend: Local filesystem and S3-compatible object storage

Test Environment

Component	Specification
CPU	Apple M3 Pro
Memory	36 GB
OS	macOS 14.8
Rust	Stable channel
Object Storage	Volcengine TOS (S3-compatible)

Results

Detailed Results

S3 Benchmark Results

Versions	Fragments	No Archive (ms)	Archived (ms)	Speedup
2	1K	174.19	116.08	1.5x
2	10K	230.03	99.35	2.3x
2	100K	626.06	123.65	5.1x
4	1K	205.49	122.07	1.7x
4	10K	508.77	115.74	4.4x
4	100K	1517.31	93.17	16.3x
8	1K	348.36	103.65	3.4x
8	10K	870.18	108.13	8.0x
8	100K	2038.88	112.76	18.1x
16	1K	789.76	119.01	6.6x
16	10K	1896.61	126.96	14.9x
16	100K	4261.41	103.28	41.3x
32	1K	1226.74	117.14	10.5x
32	10K	3162.72	97.76	32.4x
32	100K	8238.26	149.18	55.2x
64	1K	3012.69	128.60	23.4x
64	10K	5885.27	110.79	53.1x
64	100K	16257.41	132.38	122.8x
128	1K	6355.74	130.86	48.6x
128	10K	13003.76	127.73	101.8x
128	100K	33185.29	130.78	253.8x
256	1K	11958.24	127.51	93.8x
256	10K	26130.58	154.40	169.2x
256	100K	68365.02	127.16	537.6x
512	1K	21349.12	166.34	128.3x
512	10K	54600.08	170.19	320.8x
512	100K	136130.28	151.29	899.8x

Local Benchmark Results

Versions	Fragments	No Archive (ms)	Archived (ms)	Speedup
2	1K	0.86	0.17	5.0x
2	10K	10.02	0.17	58.7x
2	100K	134.77	0.17	799.0x
4	1K	1.66	0.18	9.3x
4	10K	19.57	0.18	109.0x
4	100K	266.67	0.18	1477.7x
8	1K	3.13	0.20	15.9x
8	10K	39.84	0.20	203.7x
8	100K	525.18	0.20	2639.6x
16	1K	6.20	0.24	26.3x
16	10K	83.56	0.25	338.5x
16	100K	1113.98	0.24	4606.4x
32	1K	12.31	0.41	30.4x
32	10K	160.00	0.44	367.4x
32	100K	2136.33	0.44	4826.0x
64	1K	24.39	0.70	35.0x
64	10K	339.11	0.65	517.8x
64	100K	4302.01	0.71	6079.0x
128	1K	48.04	1.01	47.6x
128	10K	639.96	0.99	645.2x
128	100K	8463.67	0.98	8599.8x
256	1K	104.20	1.75	59.7x
256	10K	1335.48	1.76	758.0x
256	100K	17316.94	1.69	10264.8x
512	1K	1042.96	3.16	330.0x
512	10K	3444.43	3.16	1088.3x
512	100K	36322.76	2.98	12200.3x

Performance Speedup Summary

The following charts show the performance improvement (speedup) when using Version Archive:

S3 Storage

Local Storage

Response Time Comparison

S3 Storage

Local Storage

Analysis

Key Findings

1. Significant Performance Improvement: The Version Archive feature provides substantial performance improvements across all test scenarios, ranging from 1.5x to 899.8x speedup on S3 and 5.0x to 12,200x speedup on local storage.

2. Scales with Version Count: The performance improvement increases dramatically with the number of versions:

   • At 2 versions: 1.5x - 5.1x (S3), 5.0x - 799x (Local)
   • At 512 versions: 128x - 900x (S3), 330x - 12,200x (Local)

3. Scales with Manifest Size: Larger manifests (more fragments) show greater improvements:

   • 1K fragments: 1.5x - 128x (S3), 5x - 330x (Local)
   • 100K fragments: 5.1x - 900x (S3), 799x - 12,200x (Local)

4. Local vs S3: Local storage shows more dramatic improvements due to lower baseline I/O latency. However, S3 still benefits significantly, which is important for cloud deployments.

5. Consistent Archived Performance: With archive, the response time remains relatively constant (~100-170ms for S3, ~0.2-3ms for Local) regardless of version count or manifest size, demonstrating O(1) complexity for version loading.

Why It Works

Without Version Archive:

• Each version requires a separate file read for its manifest
• O(n) I/O operations where n = number of versions
• Network latency compounds for S3 storage

With Version Archive:

• All version metadata is consolidated into a single archive file
• O(1) I/O operations regardless of version count
• Single file read loads all version information

[majin1102]

Incremental Version Analysis (S3)

Scenario

This analysis simulates a scenario where a dataset has an existing archive for base versions, with additional unarchived versions added incrementally.

Columns:

• Archive (ms): Response time with archive for base versions only, speedup vs No Archive in parentheses
• Arch Inc 8 (ms): Archive(base) + NoArchive(8 incremental), speedup vs NoArchive(base+8) in parentheses
• Arch Inc 16 (ms): Archive(base) + NoArchive(16 incremental), speedup vs NoArchive(base+16) in parentheses
• No Archive (ms): Response time without archive for base versions only

Formula:

• Archive + Inc = Archive(base) + NoArchive(incremental)
• Speedup = NoArchive(base + incremental) / (Archive + Inc)

Results

Base	Frag	Archive (ms)	Arch Inc 8 (ms)	Arch Inc 16 (ms)	No Archive (ms)
64	1K	128.60 (23.4x)	476.96 (7.0x)	918.37 (4.1x)	3012.69
64	10K	110.79 (53.1x)	980.97 (6.9x)	2007.40 (3.9x)	5885.27
64	100K	132.38 (122.8x)	2171.26 (8.4x)	4393.79 (4.7x)	16257.41
128	1K	130.86 (48.6x)	479.22 (14.0x)	920.62 (7.8x)	6355.74
128	10K	127.73 (101.8x)	997.91 (13.9x)	2024.34 (7.4x)	13003.76
128	100K	130.78 (253.8x)	2169.66 (16.2x)	4392.19 (8.5x)	33185.29
256	1K	127.51 (93.8x)	475.87 (25.9x)	917.28 (13.9x)	11958.24
256	10K	154.40 (169.2x)	1024.58 (26.4x)	2051.01 (13.7x)	26130.58
256	100K	127.16 (537.6x)	2166.04 (32.5x)	4388.57 (16.5x)	68365.02
512	1K	166.34 (128.3x)	514.71 (42.2x)	956.11 (23.2x)	21349.12
512	10K	170.19 (320.8x)	1040.37 (53.3x)	2066.80 (27.3x)	54600.08
512	100K	151.29 (899.8x)	2190.17 (63.1x)	4412.70 (31.8x)	136130.28

Charts

Speedup Comparison

Response Time

Conclusion

1. Even with 8-16 unarchived incremental versions added to an archived base, performance remains 4x-63x faster than no archive. The speedup increases with base version count (64→512 versions: 7x→63x for 8 incremental), demonstrating that partial archiving still delivers substantial benefits for datasets with frequent version additions.

2. In the incremental version scenario, since archive read time is negligible, dataset.versions() response time remains stable as version count increases.

[Xuanwo]

I recall that delta-rs has a similar feature, where evolutions go from JSON to PB to Parquet. I suggest we write a Lance file as our checkpoint instead of using a custom file format or PB. This way, we can even query the Lance file directly, which unlocks more possibilities.

[majin1102]

Thanks for the advice. This is a good idea. Jack also mentioned this:

We can also consider storing it as a lance file

I'm using PB for now for convenience and consistency. I can switch to lance file after we align on the layout and schema specs.

[majin1102]

@wjones127 curious what you think about this proposal. We've discussed this topic in other threads.

[Xuanwo]

Hi, @majin1102, could you please update the proposal once more to reflect the latest status? I think we have agreed to name this feature "version checkpoint" instead of "archive"?

[majin1102]

Thanks for reviewing. I've updated the design and PR:

• Unified checkpointing logic across the project.
• Switched to Lance files for checkpoint storage.