Saving Data: Reducing the Size of App Updates by 65%

Thanks, truly, for creating such a tremendously useful tool.

A quick estimate based on prices quoted by Google Cloud Engine for Egress transfers ($0.08/GB) gives $183 million in yearly savings.

Surely Google pays much less than that for their own transfers, but even if we assume they are paying 1% of that price it is still respectable. Pretty sure they are paying more than that though.

EDIT: Found better estimates - Amazon Cloudfront is charging as low as $0.02/GB (on demand pricing), which translates to $46 million. Given very good knowledge Google has about their users and their vast infrastructure I'm guessing their costs are fraction of this. Anyone with domain knowledge that can comment on this?

Edit: bsdiff is documented to use memory 17x the file size.

It's going to depend greatly on the type of packages, and the most problematic (bulky) ones are games, where the vast majority of the package is assets.

Note that Dalvik bytecode is very very different from the Java bytecode read by JVMs. For one, Dalvik is a register machine (like LuaJIT's internal bytecode) and the JVM is a stack machine (like Python bytecode).

My dream updater would just be a bunch of stream processors, so the downloading / decompression / disassembly (a la courgette), patching / recompression happens all at once, as the data packets come in (thus utilizing both CPU and IO). If done right an update shouldn't take much longer to complete than the download step, no?

I was thinking the exact same thing when I read that portion of the article. Trying to recreate the exact APK seems entirely irrelevant.

All the user (and developer) cares about is that the installed product is identical to the one the developer submitted via the Google Play developer console. This is much more easily achieved by generating a signature on the decompressed content. It also gives Google greater freedom to change compression algorithms etc.

No! That would create an additional security risk, in addition to potential performance issues.

Ideally, unchecked data should only ever hit the signature check and nothing else. Otherwise, it could also attack the decompression, not just through security holes, but also through denial of service (by injecting something that explodes in size on decompression).

This is a general principle! You should neither decompress, nor decrypt, nor unpack/untar, nor parse (XML/JSON/...), nor anything else before the signature check. See also:

"Preauthenticated decryption considered harmful"

http://www.tedunangst.com/flak/post/preauthenticated-decrypt...

However, I agree that it makes sense to have an additional check after decompression. However, that check usually happens in most decompression tools anyway, and usually through fast, lightweight checksums. Because, again, the point here is to detect bugs in the decompressor, not to protect from malicious tampering, which should always happen before complex stuff like decompression.

The zlib default is 6. The "maximum compression" is 9. Most people would either use the default, or request maximum compression.

> Why does almost nobody use zopfli which achieves 3–8% higher compression rates.

Most people are probably using Google's tools to create the APK, and these tools probably use zlib.

> Why aren't other compression formats supported like lzma, brotli, etc.?

Most compression formats with higher compression ratios (like lzma) need more power and memory to uncompress. As for brotli, not only IIRC it's newer than the APK format, but also most of its gains come from a predefined dictionary, which works only for text files.

Also, the APK format is AFAIK based on Java's JAR format, which uses Deflate exclusively. Many other recent formats also use a JAR-like container, like OpenDocument and EPUB.

I think there is also a certain amount of developer apathy towards application size.I was recently talking to a colleague who had worked on a new banking app and they saw no problem with developing, what was essentially a web front end, with the Unity game engine. When I asked if he was concerned the effect on the app size including a game engine would have he said it was what they where used to using and that was more important.

bsdiff predates the entire concept of Android by many years. To the extent that Google wasn't using it from day 1, it isn't because the solution didn't exist somewhere. (It sounds like it was due to problems that would have existed for any clever solution and they chose deliberately to ship down un-diffed-in-any-way updates.)

There's actually a profound lesson about how open source really works here. And I'm not really saying this as an open source evangelist... it's more an observation that our instinctive (and probably genetic) instinct in favor of centralization is not always an accurate model of how the world either does or should work. There's not much some sort of centralized contest could do in the present that wasn't already done in the real world over a decade ago without it.

I wonder if it's a sign of communication problems between the Android and Google Play teams? The Play team seems to have spent years bending over backwards to build this really awkward solution, which could have been done a lot better with some low-level Android changes (i.e. a new APK format).

They moved away from pure AOT compilation to JIT/AOT, because it was taking too much time and processing power.

So now they come up with unpacking and recompressing APKs on the device using CPU intensive algorithms.

Nope.

Hearthstone is a Unity game, and the issue (for mobile packaging at least) is Unity creates a giant bundle of all the assets, so it's a single binary file which tends to greatly change from one release to the next, even with per-file diffing you're not getting any improvement[0].

Other developers get around that by downloading assets separately from the main application bundle à la Supercell. I don't know that Supercell uses Unity, but they do follow that pattern, they have an application bundle of code & trivial assets, but most of the assets are downloaded at the loading screen.

Checking on my phone, Hearthstone is ~2GB with 10.5MB of "documents and data" (= a ~2GB base app bundle), clash royale is ~450MB with 336MB of data (= a ~100MB base app bundle), jetpack joyride is similar with ~330MB split between a ~90MB base bundle and ~250MB "documents and data".

The default unity approach makes sense for rarely updated applications (Monument Valley or République), it's an absolute bear for dynamic frequently updated on-line games like Hearthstone.

[0] IIRC per-file diffing is what apple does on the appstore, it does not work at all for HS

https://news.ycombinator.com/item?id=13121903