Google has provided cloud app storage for quite some time now and I believe with M they even said that they are doing full restores including the APK. The real issue as I understand it is that developers haven't taken advantage of all the services available to them.