Efficient Delta Updates
Most modern OTA update solutions for embedded Linux support a form of delta updates. Delta updates can reduce the amount of data transferred and the time required to install a new version by reusing locally available parts of the old version of a system. This is especially useful for devices on metered or bandwidth-constrained connections. In this article, we will survey the different delta update techniques implemented within popular OTA update tools, examine their tradeoffs, and present benchmarks that compare their efficiency on the basis of real-world update scenarios.
This article aims to serve as a guide for engineers looking to implement delta updates in their embedded Linux projects. Together with this article, we release Rugix version 0.8.12 which introduces support for static delta updates and functionality for benchmarking delta update techniques. With the benchmarking functionality included in Rugix Bundler, we enable engineers to evaluate the efficiency of different delta update techniques and make informed decisions about which approach to use based on their specific update scenarios. While we aim to present general benchmarks in this article, we would like to encourage you to run your own benchmarks and share your own findings with us.
For reproducibility we provide the benchmarking code on GitHub.
Outline and Overview. We will first have a look at the existing tools and techniques for OTA updates in the embedded Linux ecosystem. We will then present and discuss our benchmarking methodology, tooling, and results. Finally, we will conclude with a summary of our findings. If you do not care about the technical details, feel free to skip directly to the benchmark results.
TL;DR
There are two approaches for delta updates: static and dynamic. Static delta updates require the pre-computation of deltas whereas dynamic delta updates do not require pre-computation of deltas. Due to the pre-computation of deltas, static delta updates are more efficient than dynamic delta updates, however, they are also more complex to implement and manage. Rugix is implements best-in-class support for both static and dynamic delta updates, allowing you to choose the approach that best fits your specific requirements and update scenarios.
Use our savings calculator to estimate the cost you may save by implementing delta updates.
Tools and Techniques
Let's first have a look at the existing tools for OTA updates in the embedded Linux ecosystem and the techniques they implement for delta updates. In addition to Rugix, we will consider the following popular tools: RAUC, SWUpdate, Mender, and OSTree. While there are other tools, these are the major players in the OTA update space and are the ones we will focus on in this article.
Before diving in, it's helpful to clearly introduce the terms “tool” and “technique” and distinguish between them. The term “tool” refers to a complete OTA update solution—like RAUC, Mender, or Rugix Ctrl—while the term “technique” refers to an underlying abstract method for delta updates, such as block-based diffing or delta compression. Note that a tool may implement multiple techniques, and a given technique may be implemented by multiple tools.
Dynamic vs. Static Delta Updates. All delta update techniques have in common that they are based on the computation of some sort of delta between the old and the new version. This delta describes the difference between both versions. We generally distinguish between dynamic delta updates and static delta updates. With dynamic delta updates, the update tool running on a device dynamically computes the delta based on what is currently available on the device. Hence, dynamic delta updates do not require the pre-computation of the delta between versions and can thus typically tolerate on-device modifications. Furthermore, they can often be implemented without much additional effort.1 In contrast, with static delta updates, the delta is pre-computed and stored in a separate patch file which then allows to update from one specific version to another specific version. As our benchmarks will show, static delta updates are generally more efficient than dynamic delta updates, however, they are more complex to implement, both because they require the pre-computation of deltas between all relevant versions and because they require a read-only root filesystem to ensure that the base version is unmodified.
We will now look at the three delta update techniques which are widely used by OTA update tools in the embedded Linux ecosystem: block-based diffing, delta compression, and file-based diffing.
Block-Based Diffing
The core idea of block-based diffing is to split a binary file, e.g., a filesystem image, into individual blocks, compute a hash for each block, and then use a list of block hashes (called a block index) of the new version to reconstruct the new version from locally available blocks of the old version and remotely fetched blocks. Block-based diffing can operate on arbitrary files. While block-based diffing can be used to implement static delta updates, it is typically used for dynamic delta updates.
Block-based diffing is implemented by RAUC as the block-hash-index adaptive update method.2 It is also the fundamental principle behind the standalone tools Casync and Zchunk, which can both be used as part of an update workflow. Casync can be used with RAUC3 and SWUpdate supports an integration with Casync as well as Zchunk.4 Neither Mender nor OSTree support block-based diffing. Rugix has its own implementation of block-based diffing which is comparable to Casync.
Block-based diffing has the advantage that it is relatively simple to implement and can use any block device (e.g., a partition) or other file as the source of blocks. Of course, it is also possible to use multiple sources for an update and Rugix supports that. Depending on the implementation, block-based diffing can also tolerate mutable block sources, such as mounted filesystems. Changes to blocks can be detected based on their hash and, if a block changed, it can simply be fetched from the network.
Different block-based diffing variants vary in the way they split binary files (e.g., filesystem images) into blocks. While RAUC's block-hash-index adaptive update method uses a fixed block size of 4 KiB, Casync and Zchunk implement content-defined chunking, i.e., they determine block boundaries based on a file's content, which leads to variable-sized blocks. Content-defined chunking has the advantage that it can tolerate insertions into blocks. If you insert a single byte into a file, everything afterwards will be shifted by one byte likely leading to entirely different blocks when using fixed-size blocks. In contrast, with content-defined chunking, the block boundaries are determined by the actual content around the boundary, likely shifting the boundary when insertions occur. Technically, content-defined chunking is typically implemented by moving a rolling hash over the file.
All tools implementing block-based diffing also implement some sort of compression to reduce the download size while being able to decompress blocks individually or in groups. Both Casync and Zchunk directly compress the blocks they identified. In contrast, RAUC's block-hash-index adaptive update method does not compress blocks individually but implicitly compresses groups of blocks by compressing the entire update bundle using SquashFS.5 While larger blocks or group-wise compression generally lead to better compression ratios, they also lead to coarser delta updates, i.e., due to the grouping or larger blocks, adjacent data may need to be fetched although this data did not change.
Rugix implements both fixed-size blocks as well as content-defined chunking using the same algorithm as Casync. It also supports block-wise compression. Note that Rugix is the only OTA update solution that natively implements content-defined chunking. Both, RAUC and SWUpdate support content-defined chunking through an integration with Casync or Zchunk only.
Delta Compression
Delta compression re-uses concepts and ideas from compression algorithms to compute a delta between two binary files. This delta takes the form of an explicit patch to go from one file to the other. As such, delta compression can only be used for static delta updates.
Explaining the underlying algorithms of delta compression is beyond the scope of this article. If you like a broad overview, check out the explanation in the source code of Xdelta. While being relatively old, Xdelta is still the de-facto standard for delta compression (at least as far as open-source tools go).
Mender uses Xdelta for their delta update mechanism which is, however, only available commercially as part of Mender's Professional and Enterprise plans, i.e., if you are using Mender's open-source standalone version, you do not get delta updates. SWUpdate can integrate with Xdelta, however, you need to build this integration yourself. Rugix provides a ready-made integration with Xdelta for free.
File-Based Diffing
While the aforementioned techniques work on opaque binary files, it is also possible to implement delta updates directly on a file and directory level. This approach is pursued by OSTree. While the other tools rely on filesystem images, OSTrees implements a form of object store for directories and files, allowing to synchronize individual files and directories while reusing what is already locally available.6 File-based diffing has the advantage that it can avoid any noise that is introduced when treating the filesystem as a binary blob. Like block-based diffing, file-based diffing can be used for dynamic delta updates as well as static delta updates, and OSTree supports both.
None of the other update tools besides OSTree supports file-based diffing, although, we did implement an experimental file-based method within Rugix for benchmarking purposes. We may later integrate this implementation into Rugix Ctrl itself to also support file-based diffing.
Note that updates via a package manager are, in essence, also file-based updates. If you install updates via a package manager, like APT, the package manager will always download entire packages, containing all the files to install. Notably, this may also include files that have not actually changed. In contrast, with file-based diffing, updates are typically more efficient than package-based updates, as the file-based delta update mechanism only needs to download the files that have actually changed.
All tools and update techniques we look at here target full system updates, where the entire system is updated as a whole (at least conceptually) instead of individual packages. Full system updates have the advantage that updates are atomic and all software can be properly tested together. It is therefore the gold standard and we strongly recommend against using package-based incremental updates. For the reasons given above, with proper delta updates, package-based updates may also be less efficient in terms of download size than full system updates.
Summary
To summarize, Rugix and the other popular OTA update tools are build around three core techniques for delta updates: block-based diffing, delta compression, and file-based diffing. Block-based diffing is most widely used and supported by RAUC, SWUpdate, and Rugix. For delta compression, SWUpdate, Mender, and Rugix rely on Xdelta, while RAUC and OSTree do not support delta compression. OSTree is the only popular tool that supports file-based diffing. By looking at file-based diffing, we can also compare the efficiency of delta updates against package-based incremental updates.
Having a high-level understanding of the techniques, we will now turn to concrete benchmarks to compare the efficiency of the different techniques on realistic update scenarios.
Empirical Evaluation
As we have seen, there are many different tools and techniques available for OTA updates, however, it is not immediately clear how effective they are on realistic update scenarios. While the general wisdom is that delta updates are effective, implementing delta updates, in particular static delta updates, can also consume a lot of engineering resources. So, the question is:
How effective are delta updates in practice and are they worth the effort?
To answer that question, we consider two update scenarios: minor updates and major upgrades. Minor updates represent frequent but smaller changes, e.g., security updates, bug fixes, and occasional new features in business applications. In contrast, major upgrades represent significant system changes, like moving from Debian Bullseye to Bookworm or from Yocto Kirkstone to Scarthgap.
We also look at different update cadences: monthly, quarterly, biannual, and annual. The update cadence is the frequency with which updates are applied to the system. For example, a monthly update cadence means that updates are applied every month, while a biannual update cadence means that updates are applied every six months. More frequent updates mean less changes per update, however, more updates overall. We will benchmark how effective delta updates are for each cadence, respectively.
Prior Work. The efficiency of delta updates implemented by popular tools has already been investigated by Drew Moseley who shared his findings in a talk at EOSS 2024 and a blog post on the Torizon blog. Our findings are generally in-line with his findings, however, we (a) pursue a different approach, focusing on the fundamental techniques instead of tools, (b) we use a more comprehensive data set based on two years of real-world updates according to different cadences, and (c) we also show where delta updates become harmful. We view our findings as complementary to Moseley's work.
System Images
To benchmark anything, we first need a realistic dataset. For our benchmarks, we used Rugix Bakery to build bit-by-bit reproducible root filesystems and filesystem images based on Debian snapshots. By using Debian snapshots, we ensure that the scenarios are reproducible and based on realistic systems that we would have built when we could go back in time.
Concretely, we start with the snapshot 20230611T103552Z and build a system for each month up to the snapshot 20250611T033537Z for both, Debian Bookworm and Bullseye. As a result, we obtain 50 system images. The images are minimal Debian images with Rugix and A/B update support. To add some additional applications, we installed the packages python3 and build-essential.
While Yocto images can generally be much smaller than Debian images, we still believe that the Debian images we built are representative for typical update scenarios even when using Yocto. Different Linux distributions vary in their update policies and Debian is particularly known for its stability and only shipping updates when necessary. You should take all benchmarks with a grain of salt and benchmark your own update scenarios to base your decisions on. With the benchmarking functionality integrated into Rugix Bundler, we make this particularly easy.
With those images, we can now go through different update cadences for minor updates and also study major upgrades, going from Debian Bullseye to Debian Bookworm.
Methodology
Given the size of our dataset, carrying out all the updates and measuring the download sizes manually is not feasible. Thus, instead of conducting the benchmarks manually, we decided to develop a dedicated benchmarking tool that would allow us to simulate updates and compute the download sizes for different techniques under different assumptions, e.g., for block-fetching overhead. By using a simulation, we can quickly conduct benchmarks for different parameters, eliminate noise, experiment with assumptions, and better understand the inherent limits of the fundamental techniques.
Of course, when relying on simulation there always is a chance for a simulation-reality gap, i.e, the simulation may not reflect reality. We will discuss various aspects in which our simulation may not be faithful to reality in the next section when presenting our results. Although, we will not claim that our simulation is perfect, we believe that it provides a realistic picture of the effectiveness of delta update techniques. This claim is corroborated by the fact that our findings are in-line with Moseley's, who did not use simulation but benchmarked the actual tools, although on a much smaller dataset.
The benchmarking tool implements block-based and file-based diffing. For delta compression, we simply used Xdelta as is. The implementation of block-based diffing reuses the core functionality provided by Rugix and used for actual updates with Rugix. It supports fixed-size blocks and content-defined chunking implementing the same algorithm as Casync, i.e., it will produce exactly the same blocks as Casync would. The simulation allows accounting for the overhead of fetching individual blocks and can use block-wise compression as well as compress blocks in groups (as RAUC does it). Using different parameters for the simulation, this allows us to obtain results indicative for the block-based diffing implemented in RAUC, Casync, and Rugix. The file-based diffing implementation uses a novel approach we call Deltar. The idea is to construct a tar-like archive where the file contents is not inlined into the file but stored separately and potentially split into blocks for deduplication using content-defined chunking. So, a Deltar update essentially consists of a file index, listing the files and directories, followed by a list of file blocks that can be fetched individually. The benchmarking tool allows separately computing the size of the file index and the size of the actual file data that needed to be fetched. Again, by using different parameters, we can use that to obtain results indicative for OSTree and package-based updates.
The benchmarking tool is available as part of Rugix Bundler. You can use it to quickly conduct benchmarks of the different techniques for your own update scenarios.
With all that out of the way, let's now turn to the benchmark results.
Minor Updates
We first look at minor updates. The metric we are considering is the ratio between the size of a simple compression of the entire update (we use LZMA for the benchmarks) and the download size of delta updates. This ratio tells us how effective delta updates are in terms of bandwidth saved compared to a non-delta update using compression of the entire filesystem image.
Here are the results for different techniques for minor updates with different cadences:
These values are obtained by taking the average over all minor updates for Debian Bookworm and Debian Bullseye, e.g., in case of monthly updates, they represent an average over 48 updates and in case of annual updates they represent an average over 4 updates. The red bar is always at 1.0, indicating the base line of a simple compression of the entire filesystem image. Compared to this baseline, delta updates can reduce the size by between 30% and 90%, depending on the cadence and technique.
Before we look at the different techniques in detail, we observe that the higher the update cadence, the more effective delta updates become. This makes sense as each update contains less changes over the previous version, allowing for a larger portion of the update to be reused from the previous version. At the same time, however, updates are more frequent leading to a higher cost overall. This is evident from the next plot that shows the absolute accumulated download size per year:
These results show that the most effective way to minimize the overall cost is to lower the update cadence. Of course, if you need to ship new features or bug fixes frequently, you may not be able to get away with fewer updates. In that case, delta updates are especially effective.
Let's now have a look at the different techniques in more detail.
Block-Based Diffing. For our benchmarks, we assumed an overhead of 768 bytes to fetch a block or a block group. The purple bars (Block-Based, Fixed 4KiB/32KiB and Block-Based, Fixed 4KiB/64KiB) represent a typical RAUC update using a fixed block size of 4 KiB and combining blocks to 32 KiB and 64 KiB groups for compression, respectively (RAUC's documentation recommends 64KiB2). The blue bars (Block-Based, Casync 64KiB and Block-Based, Casync 16KiB) represent typical Casync updates using an average block size of 64 KiB and 16 KiB, respectively. Those bars also represent a typical Rugix update, as Rugix implements the exact same algorithms as Casync under the hood. While Rugix and Casync use the same block hashes for delta updates and integrity checks, RAUC uses dm-verity over the update bundle, which does add a small overhead not accounted for in the simulation. Generally smaller block sizes, as in the case of RAUC, also increase the size of the block indices. Overall, Casync and Rugix are slightly more efficient than the fixed-size block-based diffing approach implemented by RAUC. Furthermore, it is noteworthy that 4 KiB fixed-size blocks only work well for filesystem images, where these blocks align with the blocks of the filesystem. In contrast, Rugix's and Casync's content-defined chunking approach also works well for other file types. So, we conclude that for minor updates, among the block-based diffing techniques, Rugix and Casync are slightly more efficient than RAUC while also being more versatile. SWUpdate should be able to achieve results comparable to the other block-based diffing techniques by using Zchunk under the hood. Although, Moseley's work shows that SWUpdate with Zchunk is less efficient than RAUC and Casync (and thus Rugix).
File-Based Diffing. As discussed earlier, file-based diffing techniques can avoid noise introduced by treating the filesystem as a binary blob. The green bar (File-Based, Deltar 16KiB) represents a file-based update based on our prototypical Deltar approach. The plot shows the index and data portion separately. As one can see, the index portion only makes up a small part of the update. Here, we assume that we are downloading the entire file index. In contrast, OSTree can avoid downloading the entire file index by just syncing in the new files and directories on a file and directory level, respectively. While this may avoid downloading some data, it also introduces overhead. This overhead is likely not worthwhile, as the file index only makes up a negligible small part of the entire update. The much larger part is the actual data that changed. Note that the values shown here assume that the data is split into 16 KiB blocks (on average) using content-defined chunking and downloading these blocks individually (with an overhead of again 768 bytes). By default, OSTree does not do such splitting. Instead, it will download entire files which might again introduce a bit more overhead. Hence, with regards to OSTree our simulation is probably a bit optimistic, nevertheless our findings are in-line with Moseley's.7 We did not implement a static variant of file-based diffing. A static variant, e.g., as implemented by OSTree static deltas, could compress all new file blocks together, likely leading to a higher compression ratio of the data and thereby improving the efficiency ratio further. In general, we conclude that file-based diffing is typically more efficient than block-based diffing. However, it is not as versatile as block-based diffing, as block-based diffing does work for arbitrary binary files, not just filesystems (files and directories).
Delta Compression. The difference between block-based and file-based diffing is not particularly large. However, if we look at delta compression (Xdelta) in comparison, we find that delta compression can be more than twice as efficient as block-based and file-based diffing. It is by far the most efficient method for minor updates in our benchmarks. This can be attributed, in part, to the fact that delta compression is a static delta update technique while all other techniques in our benchmarks are dynamic. Being static, Xdelta has perfect information about the old and new version to optimize the download size. However, it is not just the fact that delta compression is a static technique. As Moseley's results show, Xdelta can also be significantly more efficient than OSTree's static delta updates (which are based on file-based diffing).7 Another reason is that delta compression does use very sophisticated techniques to identify reusable parts and patterns on a byte-level, making it very effective. The results presented here are typical for Rugix's and Mender's static delta updates, as they both use Xdelta internally. While delta compression is the most efficient approach in our benchmarks, it requires pre-computing deltas and is therefore the most complex to implement and operate. If you need to reduce the size of updates to an absolute minimum, delta compression is probably the right choice for minor updates.
Package-Based Updates. An often brought-forward argument against full systems is their suspected size compared to package-based incremental updates. As discussed earlier, package-based updates are essentially file-based updates, where always all files of a new package are downloaded, even if they did not change. Our results show that delta updates of the entire system can be more efficient than updating individual packages, in particular, when using delta compression. In general, a proper static variant of file-based diffing is guaranteed to be at least as efficient as package-based updates, as it can identify the files and only the files that did change and compress them together.8
Limits of Dynamic Techniques. Given the ratio between the file index size and the data size in case of updates with our prototypical Deltar approach, we believe that our Deltar approach is close to optimal for dynamic delta updates. If you cannot assume anything about the currently installed version, e.g., due to on-device modifications, you need to somehow prepare individually addressable and retrievable chunks of the changed file data and this is exactly what Deltar is doing.
Major Upgrades
Let's now turn to major upgrades. Major upgrades are not as frequent and typically contain a lot of significant changes. As for minor updates, we also conducted benchmarks for the different update cadences, but instead of updating within a Debian version in each step, we update from Debian Bullseye to Bookworm in each step and then average the results. This represents a major update being done with the specific cadence but at different points in time. Here are the results:
First of all, we observe that there is not much difference between the different cadences. This is because there are significant changes between both versions in any case.
In fact, the changes are so significant that the benchmarked delta update techniques stop being effective and become actually harmful compared to a compression of the entire filesystem image as a whole. This shows up as ratios that are above 1 across the board. If you think about it, it also makes sense. Delta updates come with a certain overhead such as indices or less-effective compression due to splitting data into blocks. In contrast, a simple compression of the entire filesystem image does not suffer from such overhead. This overhead only pays off when there are not too many changes, which is not the case for major upgrades. Moseley's findings show that static OSTree-based updates are most efficient when doing a major upgrade (of Torizon OS).7 We suspect that this may be the case as those updates come down to a simple compression of exactly and only the data that has changed, and, while not much of the old version is reused, compression of all new data as a whole is very effective without any of the overhead that comes with dynamic delta update techniques. Unfortunately, Moseley's analysis lacks a comparison to a simple compression of the entire filesystem.
So, using delta updates can actually be harmful for infrequent major updates with significant changes. As such updates are, however, very infrequent, delta updates are still generally a good idea and likely lead to significant efficiency gains for most updates.
Savings Calculator
Based on the results of our benchmarks, we developed a calculator that allows you to estimate the cost savings (over your entire fleet per year) that you may achieve by using different delta update techniques for minor updates compared to not using delta updates.
| Method | Cost (USD/year) | Savings (USD/year) | Tools |
|---|---|---|---|
| No Delta Updates | 303 | 0 | |
| Block-Based, Fixed 4KiB/32KiB | 77 | 226 | ≈RAUC |
| Block-Based, Casync 16KiB | 68 | 234 | Rugix, Casync |
| File-Based, Deltar 16KiB | 60 | 242 | (≈OSTree, ≈APT) |
| Delta Compression (Xdelta) | 36 | 267 | Rugix, Mender, Xdelta |
We use 0.09 USD as a default cost per GiB as this is the standard egress fee for AWS S3. The calculations are based on averages over all update scenarios for a each schedule, respectively. The baseline against which savings are calculated assumes that the entire image is LZMA compressed. Note that these are estimates only and the actual savings may vary depending on your specific scenario.
Conclusion
There are different ways to approach OTA updates and delta updates in particular. While we have shown that delta updates can significantly reduce the size of updates, in particular, if updates are frequent and changes are small, our results also show that delta updates can be harmful in certain scenarios. The ideal approach depends on the specific update scenario and the tradeoffs that you want to make.
Fortunately, with Rugix you can chose different delta update strategies based on your specific update scenarios. Rugix is the only open-source OTA solution that implements best-in-class block-based diffing and delta compression in a ready to use package, supporting both static and dynamic delta updates. With the new simulation functionality build directly into Rugix Bundler, you can also conduct benchmarks quickly to determine the optimal strategy for your specific update scenarios.
We will use the insights gained from our benchmarks to improve Rugix and make it even more efficient. In particular, we will look into static variants of block-based and file-based diffing.
We would love to hear your feedback and for you to share your own findings and experiences with us. Feel free to use the GitHub discussion for this article or start a new one.
At Silitics, we help companies develop robust and secure embedded products faster. If you need help implementing OTA updates, delta updates, or with any other embedded Linux related topic, we'd love to hear from you. Let's solve your challenges together!
Footnotes
-
In particular, Rugix and RAUC support them without any additional effort. The only prerequisite is that the update is served by an HTTP server supporting range queries. ↩
-
Torizon Blog: Over-The-Air Updates | Choose the best Linux OS Image Update Model ↩ ↩2 ↩3
-
As compression techniques typically rely on heuristics, there may be extremely rare cases where compressing packages individually is more efficient than compressing everything together. ↩