Google: прорыв в минимизации патчей

Новый алгоритм, получивший название Courgette ("Кабачок"), обеспечивает вычисление разницы между двумя бинарными файлами с недоступной ранее эффективностью.

Современное программное обеспечение нуждается в постоянных обновлениях. Если код программы имеет очень большой объем, то наиболее продуктивная форма обновлений - передача дельты (разницы между предыдущей и обновлённой версиями). Такой метод называется дельта-кодированием или дельта-компрессией, поскольку эффективная дельта между последовательными версиями меньше, чем обновлённая версия.

Малый объем дельты обеспечивает быстроту передачи обновлений и экономию дискового пространства при хранении версий файлов. Поэтому задача её минимизации является весьма актуальной.

Однако дельта-кодирование исполняемых бинарных файлов (файлов в двоичном формате) - непростая задача. Даже небольшое изменение исходного кода (имеющего высокий уровень абстракции) может вести к существенным изменениям в бинарном коде. В результате дельта становится близкой по размеру к обновлённой версии, что делает её использование бессмысленным.

В то же время передача обновлений в виде исходного кода затруднена из-за частого отсутствия на клиентской стороне полноценных средств трансляции в машинный код.

Инженеры компании Google решили задачу минимизации дельты, создав технологию Courgette, позволяющую пересылать обновления в виде псевдо-ассемблерного кода. Последовательные версии дизассемблируются, их дельта высылается клиентскому компьютеру и применяется к дизассемблированной старой версии программы. Затем полученная изменённая версия опять переводится в машинный код.

Основное преимущество Courgette - возможность обратимого преобразования бинарного кода в псевдо-ассемблерный код низкого уровня абстракции, пригодный для легкого и быстрого вычисления дельты.

"Изобретение Google очень интересное и перспективное. Минимизация размеров обновлений важна для антивирусной индустрии, поэтому мы всегда внимательно следим за подобными разработками, - комментирует Никита Швецов, руководитель лаборатории антивирусных исследований "Лаборатории Касперского". - Разработчики нашей компании уже реализовали аналогичное улучшение технологии дельта-кодирования, но с учетом специфики антивирусных баз".

По данным Google, Courgette показал 9-кратное снижение объема обновлений для браузера Google Chrome по сравнению с использовавшимся ранее инструментом дельта-кодирования bsdiff.