Android incremental update scheme research

The original address: xuzx. Making. IO / 2020/05/23 /…

What is incremental update

As APP continues to be updated iteratively with business requirements, with more and more functions (complex), the volume of APK package will become larger and larger, resulting in more bandwidth and download waiting time for each client upgrade and update operation. Therefore, it is necessary to seek some better update schemes.

Generally speaking, incremental update refers to the binary differential comparison between a new VERSION OF APK package and an old version of APK package to generate a smaller incremental package and then send it to the client for download and update. Incremental update is relative to full update. The process is shown in Figure 1.

Incremental updates can reduce traffic costs and reduce client upgrade time.

Figure 1 Incremental update process

Comparison of incremental update schemes

There are many incremental update solutions on the web, such as BSDiff, Xdelta, Courgette, etc. Since Courgette does not work with Android APK updates, it will not be compared here. Table 1 below is a comparison of the former two schemes.

Table 1 Framework comparison (Note: [-] : unknown; [√] : indicates support. [×] : not supported)

Contrast test

Environment configuration

• Differential generation environment: Windows 10(64-bit), CPU I5-6500 (3.2ghz), RAM 16GB
• Differential synthesis environment: SamSung SM-P583, Android 7.0, RAM 3GB
• Differential tools: BSDiff(4.3) and Xdelta(3.1.0) generated by the MinGW 32-bit compiler

Note: The differential generation phase is usually operated on the server side, while the differential synthesis phase is usually operated on the mobile side.

Test Group 1 (APK around 15M)

The Flipboard redboard is selected as the test object, and the versions are 4.3.12 (14.5MB) and 4.3.13 (14.6MB) respectively. The test comparison data is shown as follows.

FIG. 2 Comparison of APK time around 15M

Table 2 EXPERIMENTAL results of APK at around 15M

Test Group 2 (around 100M APK)

Wechat is selected as the test object, with versions 6.7.3 (75.5MB) and 7.0.3 (104MB) respectively. The test comparison data is shown below.

FIG. 3 Comparison of APK time around 100M

Table 3 Results of APK experimental data at around 100M

Test Group 3 (500M APK or so)

Here, the king of Chaos is selected as the test object, with versions 1.6.8.25 (532MB) and 1.6.12.26 (560MB) respectively. The test comparison data is shown below.

Figure 4 comparison of APK time around 500M

Table 4 Experimental results of APK around 500M

Test Group 4 (around 1.8GB APK)

Here, the game package PubG is selected as the test object, versions of which are 0.13.5(1.79GB) and 0.14.5 (1.86GB) respectively. The test comparison data is shown below.

FIG. 5 APK time comparison around 1.8g

Table 5 Experimental results of APK around 1.8G

Note: The data are from the average of 5 experiments

conclusion

From the previous several groups of test experiments combined with relevant source code, we can draw the following conclusions:

1) In terms of difference time, Xdelta3 is better than BSDiff in difference generation and difference synthesis, and the difference between the two is about 10 times. The difference synthesis is better than the difference generation.

2) From the aspect of memory consumption, with the increase of APK package size, BSDiff memory will double, but Xdelta3 is stable within a certain range;

3) When the APK package reaches a certain size, BSDiff(32-bit compiler) will have differential failure. It can be analyzed from the source code of C that a large number of dynamic memory space application is caused by the difference, which is also the main reason for the large memory occupied, but Xdelta can still difference;

4) In addition, BSDiff needs to read the old and new files into memory to form a string dictionary, sort (qsufsort), search (search) and so on, and generate the diffString and extra String blocks. Finally, the incremental package (patch) was generated by bzip2 compression. Meanwhile, it was found that the difference comparison operations such as sorting and searching took half of the time with the bzip2 compression generation operations. Xdelta3 uses the correlation window algorithm to block old and new files into memory, and generates incremental packages by comparing the differences.

5) It should be noted that the incremental packets generated by the two reinforcement packets cannot be combined with the unreinforcement packets;

6) Xdelta 3.1.1 is slightly optimized in terms of time consumption and memory compared with 3.1.0;

7) In addition, it is found that the Xdelta executable generated by different compilers has a related influence on the differential generation time. For example, the mingW-W64 compiler and CL compiler generate the execution file, and the time of the differential generation operation is about half different (the former is better).

Tips: This article is the blogger’s original article, if found in the article, welcome criticism and correction, thank you for your support!