Implementing the xdelta algorithm in RDFM for more efficient delta updates generation

Antmicro’s Remote Device Fleet Manager (RDFM) is a flexible open source framework for deploying Over-The-Air updates to edge devices running Linux, Android or Zephyr. To make the update process as fast and efficient as possible, RDFM utilizes a delta package scheme, allowing you to download just the changes that occurred between software versions instead of the entire software image. A smaller delta size directly translates into reduced bandwidth usage, lower storage requirements, and faster update delivery, which is important especially in environments with limited network resources. On the other hand, algorithms that create smaller packages may require more resources (i.e. RAM, CPU, etc.) on the target device, which means choosing the optimal algorithm requires finding a balance between package size and resource usage.

So far, RDFM has been relying on the rsync algorithm for generating delta updates. While sufficient in most scenarios, in some corner cases it produces disproportionately large deltas for small changes. To mitigate that, based on the use cases we have been seeing in real world applications of RDFM in our customers’ products, we’ve decided to introduce choice in terms of the algorithm used for calculating delta updates. After evaluating and comparing several differential algorithms in terms of delta size, delta encoding time, delta decoding time and resource usage, we picked the xdelta algorithm as the most efficient other option.

In this article we describe the process of algorithm evaluation as well as the details of xdelta implementation in RDFM, including updates to the xdelta library, cgo integration with xdelta, and updates to RDFM itself.

The alternatives for delta generation

RDFM is a fully open source solution and Antmicro’s customers often use our services to customize it and/or deploy on-prem where needed. Scenarios can vary greatly, from massive fleets of smart city devices to deployments in space, and we try to make the framework flexible enough to allow different use cases to coexist, with enough configuration options to cater for various needs without compromising on important parameters.

Up until now, RDFM has been exclusively using librsync-go, a native Go implementation of the rsync algorithm, for delta package generation. In some cases occurring in internal and customer projects using RDFM, the delta update packages generated with librsync-go are larger than expected, especially when only minor changes have been introduced to the system images.

To find a suitable alternative to rsync, we evaluated several differential algorithms, focusing on the following key metrics: delta size, delta encoding time, delta decoding time, and resource usage.

Delta size is one of the most critical aspects, as it determines the final costs of deploying OTA updates. Delta encoding time represents the time required to generate a delta file from the source and target files, and describes the computational efficiency of the algorithm’s encoding process. Delta decoding time measures the computational cost incurred by the end device during the patching process and reflects the total CPU time consumed to reconstruct the target file from the source file and the delta file.

rdfm-artifact, a tool for generating delta updates in RDFM, is written in Go, therefore when choosing algorithms to evaluate we focused on those already implemented in native Go. Additionally, thanks to the cgo tool which allows linking Go code with C code, we also considered C-based libraries that implement delta algorithms. Ultimately, we analyzed four algorithms:

• xdelta3 - a native C implementation of the xdelta algorithm
• go-delta - a delta algorithm implemented in Go
• fdelta - a native Go implementation of the fossil algorithm
• librsync-go - a native Go implementation of the rsync algorithm, previously the only option in RDFM.

To provide some testing coverage of different situations, we prepared several testing scenarios:

• A: Adding 6 packages (openssl, iptables, gdb, strace, mosquitto, lsof) to a Linux image.
• B: Adding 28 packages (gcc, postgresql, redis, imagemagick, tar, gzip, xz, bzip2, iptables, strace, man-db, perl, ruby, gdb, lsof, mosquitto, make, bc, sqlite3, util-linux, openssh, curl, wget, rsync, vim, nano, htop, tmux) to a Linux image
• C: Linux kernel update from version 5.15.0 to 5.17.0.
• D: Removing six packages (openssl, iptables, gdb, strace, mosquitto, lsof) and downgrading the kernel from 5.17.0 to 5.15.0.
• E: Upgrading the kernel from 5.15.0 to 5.17.0, adding a mock driver and adding two packages: openssl and iptables.

Algorithm evaluation results

The results of the evaluation are shown below - in all three graphs, lower is better:

Based on these results, we established that rsync (librsync-go) is fast in encoding and the fastest in decoding, but produces large deltas. Fossil (fdelta) is a balanced option, with delta sizes smaller than rsync but longer computation times, positioning it as a middle-ground solution. Go-delta requires high memory usage, as well as long encoding and decoding times, making it the least optimal of the analyzed algorithms. Finally, xdelta achieved the smallest deltas while maintaining competitive encoding times, though its decoding times were quite high in some cases. However, this approach appears to be the most effective and balanced solution, providing much smaller packages without a significant increase in resource usage.

We also compared xdelta and rsync in terms of delta size in a few additional scenarios, which further proved that xdelta is a good alternative to rsync in situations that require the delta packages to be as small as possible.

Implementing xdelta in RDFM

With xdelta chosen as a suitable addition to RDFM, the next step was to introduce multi-algorithm support. First, we had to add support for xdelta in the RDFM Artifact utility and RDFM Linux Device Client. They are both implemented in Go, however the only available implementation of xdelta is written in the C language, so we had to update the xdelta library and integrate it with cgo before updating RDFM itself.

To update the xdelta library, we forked the Release_3_0_apl branch from xdelta GitHub and refined its API. The original offered a CLI or library with simple/advanced APIs, but the simple API was RAM-intensive, and the advanced API required manual configuration of the encoder settings driving the entire data-stream workflow (feeding input, handling source-block requests, flushing windows and cleanup). We added the xd3_encode and xd3_decode functions for CLI-like performance. Next, we had to integrate the xdelta C-library with the RDFM Go-code. To do so, we employed the cgo tool, which allows for linking C-code with Go-code. We developed an xdelta package, serving as the Go API for the library. It leverages helper functions for stream-based artifact reading/writing and wraps xdelta’s encoding and decoding C functions, enabling xdelta use in Go projects. Finally, we updated the RDFM Artifact utility and Linux Device Client to support this xdelta Go API.

In the rdfm-artifact tool there is a new CLI option, --delta-algorithm, which allows selecting the algorithm for artifact encoding (xdelta or rsync). The chosen algorithm is stored in the delta artifact’s .json metadata under Updates->Metadata->Files->Name. The file extension reflects the algorithm used, e.g. rootfs-image-delta-1701928641.4294967296.xdelta or rootfs-image-delta-1701928641.4294967296.rsync. The flag is optional, if it’s not used, rsync is still the default option. Additionally, the artifact’s metadata now includes a dependency flag under Depends (e.g., rdfm.software.supports_rsync: true) to enforce a client-side check that the target device supports the specified algorithm. In the latest version of the RDFM Linux Client, both algorithms are supported by default.

Based on this extension, the RDFM installer on the Linux device client decides whether to use the xdelta or rsync method for decoding. Rsync is recommended for large updates and scenarios where minimizing CPU load on end devices is critical, while xdelta is the most optimal choice when small delta size is a priority (e.g. devices deployed in areas with poor connectivity).

Configurable delta updates with RDFM

With both rsync and xdelta supported, the method of generating delta updates in RDFM can be now adjusted to your needs, allowing you to take full advantage of RDFM’s capabilities in a variety of scenarios.

If you’re interested in adopting RDFM or would like to learn more about other features RDFM offers for fleet management, including a Web GUI, single-file updates and cloud setups, don’t hesitate to contact us at contact@antmicro.com.