GitLab

In mid-2012, beginning with Jelly Bean (4.1), Google Play began using Smart App Updates [0]

Smart App Updates

Smart app updates is a new feature of Google Play that introduces a better way
of delivering app updates to devices. When developers publish an update, Google
Play now delivers only the bits that have changed to devices, rather than the
entire APK. This makes the updates much lighter-weight in most cases, so they
are faster to download, save the device’s battery, and conserve bandwidth usage
on users’ mobile data plan. On average, a smart app update is about 1/3 the
size of a full APK update.

Considering Orfox is now ~30MB, and this may increase with additional locales, we should track the current diff patch size Google Play distributes for incremental updates, and we should investigate if we can tweak our APK so it provides minimal diffs.

Can we (nearly) reproduce their results?

StackOverflow suggests they are using GDIFF [1].

Google was nice enough to publish some more details (4 years later) about how they're now using a newer diff method in some situations [2]:

For approximately 98% of app updates from the Play Store, only changes (deltas)
to APK files are downloaded and merged with the existing files, reducing the
size of updates. Google Play has used delta algorithms since 2012, and we
recently rolled out an additional delta algorithm, bsdiff (created by Colin
Percival1), that our experimentation shows can reduce delta size by up to 50%
or more compared to the previous algorithm for some APKs. Bsdiff is
specifically targeted to produce more efficient deltas of native libraries by
taking advantage of the specific ways in which compiled native code changes
between versions. To be most effective, native libraries should be stored
uncompressed (compression interferes with delta algorithms). 

Unfortunately, we are restricted by our user base and by which platforms Mozilla is targeting. At this point, Mozilla are still targeting SDK 16, which is good for us, but we don't get new optimizations:

However, please note, native libraries should only be uncompressed when the
minimum SDK version for an APK is 23 (Marshmallow) or later

So we should keep bsdiff optimizations in mind for when Mozilla eventually move to min-sdk 23+.

[0] https://developer.android.com/about/versions/jelly-bean.html [1] https://stackoverflow.com/questions/12860938/smart-app-updates-on-google-play-store-how-does-it-work/12877791#12877791 [2] https://android-developers.googleblog.com/2016/07/improvements-for-smaller-app-downloads.html