Designing a Reliable Delta-Based Game Update System with xdelta3

1. Problem Statement

Game updates are critical for delivering new features and bug fixes, but most current systems still require users to download full builds every time a new version is released. This leads to:

• Heavy bandwidth usage for both users and infrastructure.
• Long update times that frustrate players.
• Large CDN costs, especially for games with frequent releases or large data sizes.
• Redundant downloads - most files haven’t changed between versions.
  

Below is the size of the game Naraka, which is 80GB. If the game only updates 1MB in a single file but still requires downloading the full 80GB again, it will take a lot of time and make users unhappy.

2. Existing Approaches & Why xdelta3

When implementing delta (diff-based) update systems for game builds, there are several ways to generate and apply differences between versions. Each approach has different trade-offs in terms of patch size, memory and compute cost, and suitability for large binary files. Below is a structured explanation and comparison:
This approach only detects which files have changed between versions and sends entire changed files to the client. It does not generate internal differences within a file.
Strengths:

• Very simple to implement.
• Reads only file metadata (exists/changed) to decide what to send.
  

Weaknesses:

• No byte-level diff inside large binaries - e.g., if a 5 GB file changes only slightly, it still must be sent whole.
• Limited bandwidth savings when most files are large binaries.

rsync / rdiff-Based Deltas:

The rsync algorithm uses rolling checksums to find matching blocks between source and target and only transfers blocks that differ. This is often used in remote sync (networked file replication). It is also the basis for tools like librsync.
Strengths:

• Efficient for network synchronization where one end does not have both versions.
• Low memory usage compared to some binary diff tools.
  

Weaknesses:

• Produces larger delta files compared with specialized binary diff tools when both source and target are known locally.
• Not optimized for offline patch generation where full information is available locally.

bsdiff / bspatch:

bsdiff is a binary diff algorithm that constructs patch files optimized for minimal size. It focuses on achieving very small patch files using suffix sorting and additional compression.
Strengths:

• Often produces the smallest patch size among common tools because it aggressively compresses differences.
• Works well when changes are structural and recurring.
  

Weaknesses:

• Requires large amounts of memory and is slow on multi-GB files in many cases.
• May be impractical in real-world game update pipelines due to heavy resource usage.

xdelta3 (VCDIFF Standard)

xdelta3 is a binary differencing tool that generates patch files based on the VCDIFF (RFC 3284) standardized format. It was originally derived from rsync principles and enhanced with a sliding window and block matching to balance performance and patch size.
Strengths:

• Designed for binary diffs and supports very large files (up to 2⁶⁴ bytes).
• Produces reasonably compact patches with good performance.
• Compatible with the VCDIFF standard, allowing integration with other tools and formats.
  

Weaknesses:

• Patch sizes are typically larger than optimized bsdiff in some benchmarks.
• Creation time and memory usage are moderate (higher than rsync but lower than bsdiff).

Feature / Approach	Directory diff only	rsync / rdiff	bsdiff / bspatch	xdelta3 (VCDIFF)
Typical Use	Simple file-level change detection	Network sync & incremental remote synchronization	Binary diff with minimal patch size	Binary diff with balanced size & performance
Patch Size	❌ Sends full file when changed	⚠️ Moderate (larger than advanced binary diff)	✔️ Often smallest patches	✔️ Small patches
Memory Usage	🟢 Very low	🟢 Low	🔴 High (especially for large files)	🟡 Moderate
Compute Complexity	🟢 Simple	🟡 Moderate	🔴 High	🟡 Moderate
Supports Large Files	✔️ Yes	✔️ Yes	⚠️ Limited by memory	✔️ Yes (VCDIFF designed for large files) [turn0search26]
Standard Format	❌ N/A	❌ N/A	❌ Custom	✔️ VCDIFF standard
Best For	Simple update cases	Sync across network without full source	Very small binary patches	Balanced game patch updates
Typical Users	Small apps or simple assets	Backup tools, delta replication	Executable patching (research & niche)	Large builds, game update pipelines
Real-world Efficiency	❌ Inefficient for large binaries	⚠️ Suboptimal compared to xdelta3/bsdiff	✔️ Excellent if memory allows	✔️ Practical & widely used

3. Algorithm Overview

What xdelta3 Is

xdelta3 is a binary differencing tool that implements the VCDIFF (RFC 3284) delta encoding format - a standard way to represent the difference between two data streams so that the target file can be reconstructed from the source and the delta patch. VCDIFF defines a small set of instructions that encode differences compactly. xdelta3 handles very large binary files (up to 2⁶⁴ bytes) and produces patches based on those instructions.

How It Works (Step-by-Step, Illustrative)

At a high level, xdelta3 compares two versions of a file (source and target) and encodes only the information needed to reconstruct the target from the source. The output is a sequence of simple instructions.
Here’s a step-by-step conceptual walkthrough of how it works:

1. Index Source File - Build Lookup Table The old version (source) is read and divided into fixed-size windows (blocks). For each window, xdelta3 computes hashes and stores them in an efficient lookup structure. This allows the algorithm to quickly find matching sequences when scanning the new file. This step makes searching fast while keeping memory usage moderate.
2. Scan Target File - Rolling Cursor xdelta3 moves a cursor from left to right across the new version (target). At each position, it computes a rolling hash over a small sliding window of bytes. This sliding hash helps the algorithm detect whether the current segment matches something previously seen in the source.
3. Match Discovery - Search for Copy Candidates For each cursor position, the algorithm tries two kinds of matches:
   • Copy from source file: if a segment of the target exists in the source.
   • Copy from already processed target segments: when data repeats inside the target itself. If a match is found, it is verified and then extended both forward and backward to maximize match length.
4. Instruction Selection - ADD vs COPY Based on matches found:
   • If a sufficiently long match exists: emit a COPY(offset, length) instruction, pointing to a segment in the source or previously decoded target.
   • If no match is found: emit an ADD(data) instruction, carrying the raw bytes that differ. The algorithm then advances the cursor by the length of the instruction and repeats.
5. Output Patch: The result is a compact patch containing only the instructions needed to reconstruct the target from the source file.

Instruction Types in VCDIFF

VCDIFF defines three fundamental instruction types that xdelta3 uses:

Instruction	Meaning
COPY	Copy a sequence of bytes from source or prior output (no new data sent)
ADD	Insert new data directly into the output
RUN	Repeat a single byte value multiple times (useful for runs of identical bytes)

These simple instructions can describe even complex changes between versions.

Detailed Example (With Step-by-Step Expansion)

Let’s walk through a concrete example that shows how a patch is built. Source file (old):

ABCDEFGH-1234-IJKLMN

Target file (new):

ABCDEFGH-5678-IJKLMN

We want a patch that transforms the source into the target.

Step 1 - First match at start: The first 8 bytes (ABCDEFGH) are identical in both files.

→ Emit:

COPY(0, 8)   // copy 8 bytes from offset 0 of source

Step 2 - Next segment differs (-1234- vs -5678-): At this point, there’s no match of -5678- in the source.

→ So we emit:

ADD("-5678-")

Step 3 - The remaining characters (IJKLMN) match again: The last 6 bytes already exist in the source.

→ Emit:

COPY(12, 6)

(The offset 12 points to the start of IJKLMN in the source.)

Final Patch Instructions:

COPY(0, 8)
ADD("-5678-")
COPY(12, 6)

Reconstruction (Applying Patch): Applying each instruction to the source file yields:

ABCDEFGH         // from COPY(0,8)
-5678-           // from ADD
IJKLMN           // from COPY(12,6)

The result is byte-identical to the target. This example mirrors the general logic of VCDIFF encoding.

4. Proposed Solution Overview

Delta updating with tools like xdelta3 can offer major bandwidth and time savings compared with full downloads, but it also introduces practical challenges that must be addressed in a real-world game update pipeline.

Real-World Challenges with xdelta3

While xdelta3 is widely used for binary differencing and patching, it has several characteristics that affect how it should be used in production:

1. Patch Output Can Be Large for Some Files Even when only a small portion of a file changes, binary differencing sometimes produces large patches - especially for files that are already compressed or reorganized internally. This is a known behavior observed in real use cases where delta output grows unexpectedly large due to the nature of the data.
2. Exact Source Required for Successful Apply xdelta3 expects the exact original source file used to generate the patch. If the client’s old file differs even slightly (for example, due to corruption or local modification), patch application will fail with checksum mismatch errors.
3. Resource Consumption During Patch Application Generating and applying patches incurs memory and compute cost. While xdelta3 can handle large files, it still uses more memory than simpler rsync-style diffs and can consume noticeable CPU on patch apply.
4. No Built-In Multi-File or Directory Delta Support xdelta3 focuses on single file differencing. It does not natively handle directory-level or multi-file diff generation, requiring wrapper logic to generate sets of patches. Because of these practical constraints, a real update system must do more than just run xdelta3 on every file pair. It must decide when it’s worth using a patch, and when fallbacks should be triggered to ensure correct and efficient updates.

Delta Update Strategy

Our proposed solution uses xdelta3 as the core differencing engine, but surrounds it with a robust set of rules to handle real-world conditions:

1. Patch Generation with Threshold Rule

Instead of blindly using delta patches for every file, the system evaluates patch usefulness:

• For each file, generate a delta patch between the old and new versions.
• Compare the patch size to the original file size.
• If the patch is larger than a defined percentage (e.g., 70%) of the original file, skip the patch and use the full file instead. This threshold rule ensures that delta applies only when it yields meaningful savings. Serving a patch that is nearly as large as the full file defeats the purpose of delta updates. This approach avoids very large patches on files that are hard to diff efficiently (such as compressed assets), and prevents wasted download effort on the client.

2. Version and Hash Verification

To ensure patching is safe and correct:

• After downloading patches or full files, the launcher verifies each local file against a stored manifest of SHA-256 hashes.
• If any file’s hash diverges from expected, the system treats the file as invalid.
• In that case, patching is skipped for that file, and it is replaced by a clean, verified full download. This prevents checksum mismatches and corrupted file scenarios from silently breaking the update - a failure mode inherent in xdelta3 patch application when the source file differs slightly. ([GitHub][2])

3. Atomic Replacement and Safe Writes

Because updates touch critical game files, we enforce atomic operations:

• Patches are applied to temporary files.
• Only after full patch application and verification do temporary files replace existing ones.
• If anything fails mid-update, the launcher preserves the last known good state and avoids leaving the installation in a corrupted state. This prevents half-applied updates or partially overwritten files.

4. Fallback to Full Download When Needed

There are cases where delta is inefficient or unsafe:

• When a client is on a very old version outside the available patch range.
• When patch chain sizes across multiple versions grow too large.
• When patch generation or application fails. In these cases, the launcher falls back to downloading the full build for the latest version. Fallback is not considered a failure - it is a predictable, deterministic outcome of the update strategy.

Why These Choices Matter

Strategy	Why It’s Needed	Problem Addressed
Patch Threshold Rule	Prevents excessive patch sizes	Large patch output for certain data types
Hash Verification	Ensures file integrity before/after patch	xdelta3 fails if source differs
Atomic Apply	Guarantees safe file replacement	Prevents corrupted or partial updates
Full Download Fallback	Keeps updates predictable	Handles old clients and patch failures

Together, these strategies form an update system that:

• Reduces bandwidth and CDN usage through effective delta application.
• Maintains high reliability and consistency across real client environments.
• Handles edge cases where pure delta logic (xdelta3 alone) would fail. This balanced approach acknowledges the strengths of xdelta3 while mitigating its limitations with robust logic surrounding patch generation, verification, and fallback.

End-to-End Update Flow

Server / Operator Side

1. Upload Build: Operator uploads the new build version.
2. Patch Generation: For each changed file, generate an xdelta3 patch; if the patch exceeds a configured threshold (e.g., >70% of original file size), skip patching and serve the full file instead.
3. Delete List: Generate a list of files removed in the new version.
4. Manifest Update: Update file metadata (paths, hashes, sizes).
5. Publish Metadata: Patch URLs, version information, and delete lists are published so clients can retrieve them.

Client (Launcher) Side

1. Read Local Version: Read existing local version manifest and hashes.
2. Check Update Strategy: Ask server what patches are applicable to the local version and whether delta update is efficient.
3. Download: Retrieve patch folders or full files.
4. Pre-Verify: Verify local file hashes before applying patches.
5. Patch Application: Apply delta patches in version order.
6. Post-Verify & Replace: After patching and verifying, atomically replace old files with updated ones.
7. Metadata Update: Update local version metadata and clean up temporary files.

5. Proof of Concept

Real build tests Naraka game using xdelta3 show:

• Source: 77.4 GB
• Target: 78.3 GB
• Window size: 32 MB

Total patch: Apply process’s performance: When download and apply are executed in parallel: Total time ≈ max(download time, apply time)

Network Speed	Download Time	Total Time (Download + Apply)
1 Gbps	~2 min	~23 min
300 Mbps	~5 min	~23 min
100 Mbps	~14 min	~23 min
50 Mbps	~27 min	~27 min
30 Mbps	~45 min	~45 min
20 Mbps	~65 min	~65 min

The Naraka proof of concept shows that delta patch downloads using xdelta3 cut download size dramatically, but on high-speed networks the update is ultimately limited by the patch application time, while on slower networks it’s limited by download speed. In all cases, the total update time tends to be roughly the maximum of download and apply time, which matches expectations for delta-based updates where only changed data is sent.

Limitations

1. Dependent on Similarity:
   Patches work best when files don’t change drastically. Large rewrites limit delta efficiency.
2. Disk Space During Update:
   Patching requires temporary storage (old file + patched file). Clients with limited space may fail.
3. Algorithm Trade-offs:
   Alternative diff tools like bsdiff can produce smaller patches but at the cost of memory and speed - xdelta3 provides a practical balance.