Back in July, Google introduced a new algorithm to reduce the download size of app updates by up to 50%. Dubbed as "Bsdiff", the delta algorithm analyzes the difference between the installed components and the updated components available in the new APK, eventually delivering only this differential to the user.
Now, Google is rolling out another approach, dubbed "File-by-File patching", which further reduces the size of app updates. Using this technique, app update sizes can be reduced by 65% on average, and has also been cut to 90% in some cases.
Google describes File-by-File patching as follows:
File-by-File therefore is based on detecting changes in the uncompressed data. To generate a patch, we first decompress both old and new files before computing the delta (we still use bsdiff here). Then to apply the patch, we decompress the old file, apply the delta to the uncompressed content and then recompress the new file. In doing so, we need to make sure that the APK on your device is a perfect match, byte for byte, to the one on the Play Store (see APK Signature Schema v2 for why).
While this process is very efficient in compressing the size of app updates, the company has warned that it requires a lot more processing power. Google indicates that on modern devices released after 2015, recompression can take a little over one second per megabyte, however, it can take much longer on older devices.
Keeping this in view, the company is restricting File-by-File patching to auto-updates so that users don't have to wait for an update to finish when manually updating another app. To demonstrate the improvements in this patching technique, Google has posted the table shown below:
If you're interested in knowing more about the compression technique, you can view the source code on GitHub.
Source and image: Google