Android developers have reduced the size of updates by an average of 65%

Yesterday, an entry was posted on the Android blog in which developers talk about their work on reducing the size of updates. As noted in the text, every day millions of users update their system and applications, and many of them closely monitor how much mobile traffic it takes.

In order to reduce the size of updates, Android developers began to use the bsdiff algorithm written by Colin Percival in June 2016 to patch binary files. Then it helped to reduce the size of applications and updates to them, on average, by 47% relative to the full APK.

Now, the Android team wants to share a new solution that reduces the amount of updates by, on average, 65% of the original size. It's about file-by-file patching.

The approach is quite simple. Instead of downloading the full APK and reinstalling all the application files, the update system checks the user files and downloaded ones. This allows you to upload only those files that have undergone any changes during development.
')
According to Android developers, this simple but effective approach allows you to reduce update traffic by 6 petabytes daily.

But there are some pitfalls. Compressing APK files is almost the same as ZIP, using Deflate . This can significantly reduce the size, but at the same time makes it difficult to determine exactly which files were changed:


Demonstration of Deflate

As can be seen in the image above, the introduction of even one character completely changes the structure of the pinched file. Therefore, file-by-file patching is based on comparing uncompressed files with each other. In the process of updating, the unpacked files, both old and new, are reconciled. At this stage, bsdiff is still used. Then, when applying a patch, files that need to be replaced are detected and they are downloaded. After this, the APK is again rebuilt on the device side. As evidence, the developers cite a summary table for a number of the most popular Android applications:



These applications are already using the file-by-file update system.

This approach has several drawbacks. The first is that the final APK must completely coincide with the source, byte per byte. This parameter is affected by the Deflate assembly (most often used based on Zlib) and its settings.

As it turned out during the analysis, all developers use only two compression parameters using Deflate: either by default (6) or maximum (9). Android developers did not find any other parameters.

Another disadvantage of the approach is the computing power requirements on the end device, specifically, to the processor. The processes of unpacking, verification and reassembly in the APK require significant power from the user's device, and not all existing devices will be able to cope with this procedure equally well. This leads to a more prolonged use of the patch on old and low-power devices. In addition, the processing time increases proportionally based on the size of the update.