Google Chromeのソフトアップデート用圧縮技術Courgetteが面白そうなのでちょっと考えてみた (blog@browncat.org)

Googleがソフトウェアのアップデートのためのバイナリ差分配布の新しい圧縮方法を実装したようなのでメモ。

Google Chromeの190.1から190.4へのアップデートで従来方法ではフルアップデートに比べ6.7%の転送量の所、0.75%と9倍近く圧縮率が高いとのこと。

従来方法でもバイナリ差分を使っているし、圧縮アルゴリズム自体はそれなりに進んでいるのに、今更なんでこんなマジックみたいな高圧縮率が実現出来るかというのが３つ目のエントリの内容。

技術的に非常に面白い内容なのですが、簡単に書くと、従来方法ではバイナリで差分を生成し、これを配布して、受け取った側でパッチを当てています。

ところがCourgetteでは新旧バイナリをdisassembleして調整した後でそのバイナリ差分とり、これを逆のプロセスでパッチ当てを行うという方法をとるとのこと。

この方法でなんでそんなに小さくなるの？というのが面白いところで、いわゆる実行ファイルを作成する際、ソースコードを修正しコンパイルを行うわけですが、このとき修正した以外の箇所にも実際には手を加えていないにも関わらず多数の変更点が発生することがあります。

これはプログラムが変更されることで内部のアドレス(関数やループのジャンプ先、データのアドレス)などが変化します。これを参照するジャンプやメモリ参照命令のアドレス情報やオフセット、場合によっては参照命令が変化してしまうためです。もちろんバイナリコード自体の配置も変化します。

しかしこの方法のようなアセンブリレベルで考えると、各アドレスは後で決定されるため、変更点は実際に変更された箇所だけになります。従って変更がないにも関わらずバイナリに変更が発生した箇所が含まれない非常に小さい差分が得られることになります。

これは実行ファイルというデータの特性を生かした圧縮方法と言えるでしょうね。ただしこの方法をバイナリ配布に採用するということはパッチに相当に複雑なプログラムと時間がかかることが想像されますが、このへんはどうなのかわかりません。(objdumpとか使えば比較的簡単に作れそうな気もする..)

また、実行ファイル以外のファイルについては、ヒント情報を作成して送ることでデータを圧縮するとのこと。これについては、いまいちわかってません。

で、この実行ファイルの差分をとる手法にちょっと触発されてもう一歩考えてみると、

リンク前のいわゆるオブジェクトファイルのレベルでは修正していないソースコードに関係するオブジェクトファイルは変化なしです。また変更されたファイルでも、ほとんど変更箇所のみの差分しかないわけです。単純にこれのバイナリ差分を配布して、クライアント側でリンクし直すようにすれば結構いい線いけるような気がします。が、このオブジェクトファイルは商用ソフトの場合などは配布出来ない場合も多いでしょうし、不要な情報も含まれるので実用的ではないでしょう。

で、実行ファイルレベルの中身で考えると、無駄な変化点を抑えるために内部の参照先と参照元、それに関連するタイプ(相対、絶対、セクション情報、命令の置き換えに関する情報)などのリロケート情報というかリンク情報のようなものを初回に配布しておけば、バイナリパッチ時にはデータの挿入・置き換えなどとアドレスのリロケートのみで逆アセンブルのような過程を経ずにクライアントの負荷が比較的低い高効率なバイナリパッチができるのではないでしょうかね。

しかもエンディアンさえ考慮すればあまりCPUの種類にもOSにも依存しませんし、意外に作りも簡素(といってもそこそこでしょうが)に出来るかも知れません。