[devel] rpm: rsyncable deflate vs LZMA

[devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 3322 bytes --]

Я уже собирался включить LZMA сжатие для rpm payload (после некоторого
внутреннего тестирования), но Александр Боковой напомнил нам про
rsyncable патч для deflate сжатия (для gzip и zlib).

Поскольку deflate и LZMA алгоритмы по сути похожи (сжатие в два этапа --
замена подстрок по "словарю", точнее, поиск совпадающих подстрок в
пределах скользящего окна; и частотное кодирование "букв", когда
наиболее часто встречающиеся буквы кодируются ниболее короткими битовыми
последовательностями), то для LZMA в принципе возможен такой формат
"контейнера", в котором идут rsyncable сжатые блоки (как в zlib).

К сожалению, я убедился, что LZMA в текущем виде не может быть
использован (или ограниченно модифицирован) таким образом, чтобы
получить rsyncable сжатые данные.  "Старый" формат контейнера
LZMA_Alone вообще не предусматривание разбиение на блоки.  Спецификация
нового формата носит alpha status, разработчики пишут: "Do not trust
the files created by the alpha versions, unless you can uncompress
the files with the stable 4.32.x."  Кроме того, семантика "разбиения на
блоки" в новом LZMA формате отличается от семантики разбиения на блоки
в deflate.  В общем, если использовать новый формат LZMA контейнера
с целью добиться rsyncablity, то это плохо повлияет на сжатие.

Поэтому есть два варианта, как быть дальше.
1) Включить LZMA_Alone сжатие, забив на rsyncability.
2) Вернуться к идее rsyncable deflate.

Экономия на трафике будет и в том, и в другом случае, но она будет
проявляться по-разному.

Подробности про формат контейнера.  Чтобы эффективно реализовать
rsyncability для алгоритмов типа deflate/LZMA, должны быть выполнены
следующие условия: 1) небольшой размер окна; 2) продолжение/сохранение
прежнего словаря при записи сжатого блока (то есть "восстановление"
первого этапа кодирования при начале следующего сжатого блока);
3) повторная инициализация частотного кодирования "букв" (то есть
"ресет" второго этапа кодирования при начале следующего сжатого блока).

Семантика deflate блоков как раз состоит в том, что при переходе к
новому блоку словарь остаётся прежним (возможны backreferences в
предыдущие сжатые блоки в пределах окна), а частотное кодирование
инициализируется заново (в начале каждого сжатого блока идёт Huffman
tree).  Восстановление на первом этапе несколько ухудшает rsyncability,
то есть сжатые блоки могут различаться из-за несовпадающих backreferences;
но за счёт небольшого размера окна (см. требование №1) после
"провафленных" таким образом двух-трёх блоков backreferences будут
совпадать, и все последующие блоки будут rsyncable.  Зато восстановление
на первом этапе очень хорошо влияет на коэффициент сжатия.

А вот ресет частотного кодирования на втором этапе просто жизненно
неоходим для rsyncability, т.к. частотное кодирование определяет
бинарное представление сжатых данных (если частотная модель хоть
чуть-чуть отличается, то получается полностью несовпадающее побитовое
представление).

Более частый ресет частотного кодирования (из-за rsyncable patch)
отрицательно влияет на коэффициент сжатия, но это влияние огранчивается
где-то 1%.

В новом формате контейнера LZMA при начале нового блока ресетится
как словарь, так и частотное кодирование букв.  Из-за ресета словаря
коэффициент сжатия заметно падает.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexander Bokovoy]

29 мая 2008 г. 16:38 пользователь Alexey Tourbin <at@altlinux.ru> написал:
> А вот ресет частотного кодирования на втором этапе просто жизненно
> неоходим для rsyncability, т.к. частотное кодирование определяет
> бинарное представление сжатых данных (если частотная модель хоть
> чуть-чуть отличается, то получается полностью несовпадающее побитовое
> представление).
>
> Более частый ресет частотного кодирования (из-за rsyncable patch)
> отрицательно влияет на коэффициент сжатия, но это влияние огранчивается
> где-то 1%.
>
> В новом формате контейнера LZMA при начале нового блока ресетится
> как словарь, так и частотное кодирование букв.  Из-за ресета словаря
> коэффициент сжатия заметно падает.
Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
против lzma, потому что это дает следующие преимущества:
1. Позволяет более полно использовать состояние зеркала на стороне пользователя.
2. Повзоляет для популярного транспорта http включить механизм zsync,
что дополнительно дает возможность разгрузить сервера (основная работа
по вычислению разницы в блоках перекладывается на клиента, который и
так обычно недогружен)

То есть, с rsyncable мы выигрываем в долгосрочной перспективе, снижая
нагрузку на зеркала. Я бы для пущей эффективности закрыл бы
ftp-транспорт.

-- 
/ Alexander Bokovoy

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 965 bytes --]

On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
> Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
> против lzma, потому что это дает следующие преимущества:
> 1. Позволяет более полно использовать состояние зеркала на стороне пользователя.
> 2. Повзоляет для популярного транспорта http включить механизм zsync,
> что дополнительно дает возможность разгрузить сервера (основная работа
> по вычислению разницы в блоках перекладывается на клиента, который и
> так обычно недогружен)
> 
> То есть, с rsyncable мы выигрываем в долгосрочной перспективе, снижая
> нагрузку на зеркала. Я бы для пущей эффективности закрыл бы
> ftp-транспорт.

Okay, я сделал предварительную реализацию rsyncable gzdio (вопреки
тому, что думает джей-би-джей, для этого не требуется потрошить zlib;
достаточно в точках синхронизации вызывать gzflush).

Кто сможет проверить мой код?  Дело стрёмное, в этот раз на SuSE
надежды нету.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 416 bytes --]

On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
[...]
> Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
> против lzma, потому что это дает следующие преимущества:
> 1. Позволяет более полно использовать состояние зеркала на стороне пользователя.

Несмотря на неизменность большинства файлов, и постоянные переименования
большинства из оставшихся файлов?


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 849 bytes --]

On Thu, May 29, 2008 at 10:37:44PM +0400, Dmitry V. Levin wrote:
> On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
> [...]
> > Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
> > против lzma, потому что это дает следующие преимущества:
> > 1. Позволяет более полно использовать состояние зеркала на стороне пользователя.
> 
> Несмотря на неизменность большинства файлов, и постоянные переименования
> большинства из оставшихся файлов?

В следующих случаях:
rsync -y dir1/file dir2/
rsync -y dir1/ dir2/

при отсутствии dir2/file (destination file с таким же названием)
rsync будет искать dir2/other_file с названием, "наиболее похожим
на file".  То есть, с опцией -y, по идее, переименование rpm пакетов
вследствие увеличения релиза должно отслеживаться.  Правда, я не
смотрел в код rsync.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 1070 bytes --]

On Thu, May 29, 2008 at 11:50:00PM +0400, Alexey Tourbin wrote:
> On Thu, May 29, 2008 at 10:37:44PM +0400, Dmitry V. Levin wrote:
> > On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
> > [...]
> > > Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
> > > против lzma, потому что это дает следующие преимущества:
> > > 1. Позволяет более полно использовать состояние зеркала на стороне пользователя.
> > 
> > Несмотря на неизменность большинства файлов, и постоянные переименования
> > большинства из оставшихся файлов?
> 
> В следующих случаях:
> rsync -y dir1/file dir2/
> rsync -y dir1/ dir2/
> 
> при отсутствии dir2/file (destination file с таким же названием)
> rsync будет искать dir2/other_file с названием, "наиболее похожим
> на file".  То есть, с опцией -y, по идее, переименование rpm пакетов
> вследствие увеличения релиза должно отслеживаться.  Правда, я не
> смотрел в код rsync.

В мане также написано, что надо использовать опцию --delete-after (а
не --delete, которая равна --delete-before).

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexander Bokovoy]

29 мая 2008 г. 23:50 пользователь Alexey Tourbin <at@altlinux.ru> написал:
> On Thu, May 29, 2008 at 10:37:44PM +0400, Dmitry V. Levin wrote:
>> On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
>> [...]
>> > Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
>> > против lzma, потому что это дает следующие преимущества:
>> > 1. Позволяет более полно использовать состояние зеркала на стороне пользователя.
>>
>> Несмотря на неизменность большинства файлов, и постоянные переименования
>> большинства из оставшихся файлов?
>
> В следующих случаях:
> rsync -y dir1/file dir2/
> rsync -y dir1/ dir2/
>
> при отсутствии dir2/file (destination file с таким же названием)
> rsync будет искать dir2/other_file с названием, "наиболее похожим
> на file".  То есть, с опцией -y, по идее, переименование rpm пакетов
> вследствие увеличения релиза должно отслеживаться.  Правда, я не
> смотрел в код rsync.

/* This is an implementation of the Levenshtein distance algorithm.  It
 * was implemented to avoid needing a two-dimensional matrix (to save
 * memory).  It was also tweaked to try to factor in the ASCII distance
 * between changed characters as a minor distance quantity.  The normal
 * Levenshtein units of distance (each signifying a single change between
 * the two strings) are defined as a "UNIT". */

Так что это немного модифицированный алгоритм Левенштейна.
-- 
/ Alexander Bokovoy

Re: [devel] rpm: rsyncable deflate vs LZMA

[Led]

Thursday, 29 May 2008 23:13:44 Alexey Tourbin написав:
> On Thu, May 29, 2008 at 11:50:00PM +0400, Alexey Tourbin wrote:
> > On Thu, May 29, 2008 at 10:37:44PM +0400, Dmitry V. Levin wrote:
> > > On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
> > > [...]
> > >
> > > > Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
> > > > против lzma, потому что это дает следующие преимущества:
> > > > 1. Позволяет более полно использовать состояние зеркала на стороне
> > > > пользователя.
> > >
> > > Несмотря на неизменность большинства файлов, и постоянные
> > > переименования большинства из оставшихся файлов?
> >
> > В следующих случаях:
> > rsync -y dir1/file dir2/
> > rsync -y dir1/ dir2/
> >
> > при отсутствии dir2/file (destination file с таким же названием)
> > rsync будет искать dir2/other_file с названием, "наиболее похожим
> > на file".  То есть, с опцией -y, по идее, переименование rpm пакетов
> > вследствие увеличения релиза должно отслеживаться.  Правда, я не
> > смотрел в код rsync.
>
> В мане также написано, что надо использовать опцию --delete-after (а
> не --delete, которая равна --delete-before).

Может проще будет пропатчить rsync на предмет поддержки *.rpm (чтоб *.rpm 
файлы сравнивались  по названиям файлов за вычетом %version-%release.%arch)?

-- 
Led

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 822 bytes --]

On Thu, May 29, 2008 at 11:28:39PM +0300, Led wrote:
> > В мане также написано, что надо использовать опцию --delete-after (а
> > не --delete, которая равна --delete-before).
> 
> Может проще будет пропатчить rsync на предмет поддержки *.rpm (чтоб *.rpm 
> файлы сравнивались  по названиям файлов за вычетом %version-%release.%arch)?

Метрика Левенштейна не самая глупая вещь.  Она будет лажаться только
в специфических случаях, когда релиз меняется очень сильно.  Например,
имеем файлы:
libfoo1-alt1.rpm
libfoo2-alt0.cvs20080101.rpm

Надо просинхронизировать новый файл
libfoo2-alt1.rpm

Тогда алгоритм будет синхронизировать
libfoo1-alt1.rpm
libfoo2-alt1.rpm

тогда как по смыслу надо синхронизировать libfoo2-*.
Но это относительно редкие случаи.  А также не следует
вносить snapshot в релиз. :)

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 1610 bytes --]

On Thu, May 29, 2008 at 10:37:44PM +0400, Dmitry V. Levin wrote:
> On Thu, May 29, 2008 at 05:28:39PM +0400, Alexander Bokovoy wrote:
> [...]
> > Я в этом деле лицо скорее заинтересованное, но я бы выбрал rsyncable
> > против lzma, потому что это дает следующие преимущества:
> > 1. Позволяет более полно использовать состояние зеркала на стороне пользователя.
> 
> Несмотря на неизменность большинства файлов, и постоянные переименования
> большинства из оставшихся файлов?

Также следует понимать, что rsyncable deflate работает только для
достаточно больших (порядка 32K) полностью совпадающих кусков.
На практике это значит, что в *.rpm пакетах из синхронизации исключаются
маленькие файлы.  Например, для пакета man-pages rsyncable оптимизация
почти ничего не даёт (speedup 1.09 после _простой_ повторной
пересборки).  Это связано с тем, что в cpio хедере (перед содержимым
файла) есть mtime, и он получается всё время разный.  А различие в mtime
"надолго" сбивает синхронизацию (то есть весь "маленький" файл
выпадает).

У меня есть идея.  Для выбора точек синхронизации (gzflush) можно
использовать не только "слепой" rsync hint, но и cpio hint -- как
только мы видим cpio magic "070707", мы знаем, что через несколько
байтов будет mtime и потом пойдёт имя и содержимое файла.  То есть
sync можно делать в месте окончания очередного cpio header.

Правда, я не знаю, даст это что-нибудь в случае с маленькими файлами
или нет.  Это может ничего не дать из-за того, что первые совпавшие
блоки в сжатом виде всё равно могут отличаться (из-за backreferences
в предыдущий блок).

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 764 bytes --]

On Fri, May 30, 2008 at 01:31:14AM +0400, Alexey Tourbin wrote:
[...]
> У меня есть идея.  Для выбора точек синхронизации (gzflush) можно
> использовать не только "слепой" rsync hint, но и cpio hint -- как
> только мы видим cpio magic "070707", мы знаем, что через несколько
> байтов будет mtime и потом пойдёт имя и содержимое файла.  То есть
> sync можно делать в месте окончания очередного cpio header.

Это заметно снизит степень сжатия, когда в архиве много маленьких файлов?

> Правда, я не знаю, даст это что-нибудь в случае с маленькими файлами
> или нет.  Это может ничего не дать из-за того, что первые совпавшие
> блоки в сжатом виде всё равно могут отличаться (из-за backreferences
> в предыдущий блок).

Могут или будут?


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 3223 bytes --]

On Fri, May 30, 2008 at 01:56:10AM +0400, Dmitry V. Levin wrote:
> On Fri, May 30, 2008 at 01:31:14AM +0400, Alexey Tourbin wrote:
> [...]
> > У меня есть идея.  Для выбора точек синхронизации (gzflush) можно
> > использовать не только "слепой" rsync hint, но и cpio hint -- как
> > только мы видим cpio magic "070707", мы знаем, что через несколько
> > байтов будет mtime и потом пойдёт имя и содержимое файла.  То есть
> > sync можно делать в месте окончания очередного cpio header.
> 
> Это заметно снизит степень сжатия, когда в архиве много маленьких файлов?

Этим можно управлять, чтобы сознательно пропускать только "совсем
маленькие" файлы.

> > Правда, я не знаю, даст это что-нибудь в случае с маленькими файлами
> > или нет.  Это может ничего не дать из-за того, что первые совпавшие
> > блоки в сжатом виде всё равно могут отличаться (из-за backreferences
> > в предыдущий блок).
> 
> Могут или будут?

Если сделать как показано ниже, то для пакета man-pages (после повторной
пересборки) 'speedup 1.09' возрастает до 'speedup 1.19'.  То есть эффект
от синхронизации сразу после cpio хедера есть, он заметный, но не
настолько большой, чтобы всё искупать.

--- rpmio.c-	2008-05-29 22:27:55 +0400
+++ rpmio.c	2008-05-30 03:08:32 +0400
@@ -2148,6 +2148,9 @@ struct rsync_state {
 typedef struct rpmGZFILE_s {
 	gzFile *gz;
 	struct rsync_state rs;
+	uint32_t cs; /* cpio state */
+	uint32_t nb; /* bytes pending for sync */
+
 } rpmGZFILE;
 
 static /*@null@*/ FD_t gzdOpen(const char * path, const char * fmode)
@@ -2274,6 +2277,56 @@ bool rsync_next(struct rsync_state *s, u
 	return false;
 }
 
+/* from ../lib/cpio.h */
+#define CPIO_NEWC_MAGIC "070701"
+#define PHYS_HDR_SIZE 110
+
+static inline
+bool sync_hint(rpmGZFILE *rpmgz, unsigned char c)
+{
+    /* sync only if at least nb_min bytes pending */
+    static const uint32_t nb_min = PHYS_HDR_SIZE + 1024;
+    rpmgz->nb++;
+    if (rpmgz->cs >= sizeof(CPIO_NEWC_MAGIC) - 1) {
+	/* cpio major progress, reset rsync */
+	rpmgz->rs.n = rpmgz->rs.sum = 0;
+	rpmgz->cs++;
+	if (rpmgz->cs >= PHYS_HDR_SIZE) {
+	    /* sync after cpio header */
+	    rpmgz->cs = 0;
+	    if (rpmgz->nb >= nb_min) {
+		rpmgz->nb = 0;
+		fprintf(stderr, "SYNC cpio\n");
+		return true;
+	    }
+	    else {
+		fprintf(stderr, "SKIP cpio\n");
+		return false;
+	    }
+	}
+    }
+    else if (CPIO_NEWC_MAGIC[rpmgz->cs] == c) {
+	/* cpio minor progress */
+	rpmgz->cs++;
+    }
+    else {
+	rpmgz->cs = 0;
+    }
+    if (rsync_next(&rpmgz->rs, c)) {
+	if (rpmgz->nb >= nb_min) {
+	    rpmgz->nb = 0;
+	    rpmgz->cs = 0;
+	    fprintf(stderr, "SYNC rsync\n");
+	    return true;
+	}
+	else {
+	    fprintf(stderr, "SKIP rsync\n");
+	    return false;
+	}
+    }
+    return false;
+}
+
 static ssize_t
 rsyncable_gzwrite(rpmGZFILE *rpmgz, const unsigned char *const buf, size_t len)
 {
@@ -2283,7 +2336,7 @@ rsyncable_gzwrite(rpmGZFILE *rpmgz, cons
     size_t i;
 
     for (i = 0; i < len; i++) {
-	if (rsync_next(&rpmgz->rs, buf[i])) {
+	if (sync_hint(rpmgz, buf[i])) {
 	    size_t n = i + 1 - (begin - buf);
 	    rc = gzwrite(rpmgz->gz, begin, n);
 	    if (rc < 0)

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton V. Boyarshinov]

> 1) Включить LZMA_Alone сжатие, забив на rsyncability.
> 2) Вернуться к идее rsyncable deflate.
Мне, как человеку, собирающему болванки, на которые вечно ничего не помещается, кажется более привлекательным вариантом LZMA_Alone.

Антон

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1.1: Type: text/plain, Size: 1500 bytes --]

On Fri, May 30, 2008 at 01:56:10AM +0400, Dmitry V. Levin wrote:
> On Fri, May 30, 2008 at 01:31:14AM +0400, Alexey Tourbin wrote:
> [...]
> > У меня есть идея.  Для выбора точек синхронизации (gzflush) можно
> > использовать не только "слепой" rsync hint, но и cpio hint -- как
> > только мы видим cpio magic "070707", мы знаем, что через несколько
> > байтов будет mtime и потом пойдёт имя и содержимое файла.  То есть
> > sync можно делать в месте окончания очередного cpio header.
> 
> Это заметно снизит степень сжатия, когда в архиве много маленьких файлов?

Можно оценить деградацию сжатия от уменьшения deflate блока.

$ rpm2cpio /ALT/Sisyphus/files/x86_64/RPMS/glibc-core-2.5.1-alt5.x86_64.rpm |gzip -9 |wc -c
1488757
$ gcc -DBUFSIZE=$((8*1024)) gztest.c -lz
$ rpm2cpio /ALT/Sisyphus/files/x86_64/RPMS/glibc-core-2.5.1-alt5.x86_64.rpm |./a.out |wc -c 
1488040
$ gcc -DBUFSIZE=$((4*1024)) gztest.c -lz
$ rpm2cpio /ALT/Sisyphus/files/x86_64/RPMS/glibc-core-2.5.1-alt5.x86_64.rpm |./a.out |wc -c
1506758
$ gcc -DBUFSIZE=$((2*1024)) gztest.c -lz
$ rpm2cpio /ALT/Sisyphus/files/x86_64/RPMS/glibc-core-2.5.1-alt5.x86_64.rpm |./a.out |wc -c
1544170
$ gcc -DBUFSIZE=$((1*1024)) gztest.c -lz
$ rpm2cpio /ALT/Sisyphus/files/x86_64/RPMS/glibc-core-2.5.1-alt5.x86_64.rpm |./a.out |wc -c
1598928
$ 

Здесь deflate блок создаётся на каждые 8K, 4K, 2K, 1K входного потока.
Потери составляют 0%, 1.2%, 3.7%, 7.4%.  На данных, которые сжимаются
лучше, потери могут быть выше.

[-- Attachment #1.2: gztest.c --]
[-- Type: text/plain, Size: 362 bytes --]

#include <zlib.h>
#include <stdio.h>
#include <assert.h>

#ifndef BUFSIZE
#define BUFSIZE BUFSIZ
#endif

int main()
{
	char buf[BUFSIZE];
	gzFile gz = gzdopen(fileno(stdout), "w9");
	assert(gz);
	int n;
	while ((n = fread(buf, 1, sizeof(buf), stdin))) {
		int m = gzwrite(gz, buf, n);
		assert(n == m);
		gzflush(gz, Z_SYNC_FLUSH);
	}
	gzclose(gz);
	return 0;
}

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton Farygin]

Alexey Tourbin пишет:
> On Fri, May 30, 2008 at 12:21:00PM +0400, Anton V. Boyarshinov wrote:
>>> 1) Включить LZMA_Alone сжатие, забив на rsyncability.
>>> 2) Вернуться к идее rsyncable deflate.
>> Мне, как человеку, собирающему болванки, на которые вечно ничего не помещается, кажется более привлекательным вариантом LZMA_Alone.
> 
> Я помню, как собирали болванку Junior 2.2 (1 CD), и, значит,
> в последний день выясняли, войдёт туда WindowMaker или нет... :)
> http://lists.altlinux.org/pipermail/devel/2003-February/010742.html
> http://lists.altlinux.org/pipermail/devel/2003-February/010744.html
> 
> С появлением DVD как основного media-носителя дышать стало проще.  А
> ситуация с интернетом стала глобально выправляться только в последнее
> время; так что теперь экономия на трафике rpm пакетов это чаще вопрос
> комфорта, а не денег.  В общем, увы, общая актуальность вопроса сжатия
> несколько снизилась.
> 
> Возвращаясь к теме, дилемма как раз состоит в том, что для разовой
> передачи пакетов лучше подходит LZMA, а для последующей синхронизации
> пакетов, если в пакетах небольшие изменения, лучше подходит rsyncable
> deflate.  И если LZMA даёт эффект сразу, то от rsyncable deflate эффект
> появляется только со второго или третьего раза.
> 
> Но, в общем, хорошо иметь выбор, и этот выбор становится всё менее
> гипотетическим.  Можно будет сделать какую-нибудь статистику,
> перекрывает ли экономия от rsyncability экономию от LZMA или нет.
> Пока интрига сохраняется. :)

DVD конечно, ситуацию намного облегчило.. но, к сожалению, всё ещё 
востребованы дистрибутивы на CD.

Идеальный вариант - LZMA + rsync.

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 1449 bytes --]

On Fri, May 30, 2008 at 12:21:00PM +0400, Anton V. Boyarshinov wrote:
> > 1) Включить LZMA_Alone сжатие, забив на rsyncability.
> > 2) Вернуться к идее rsyncable deflate.
> Мне, как человеку, собирающему болванки, на которые вечно ничего не помещается, кажется более привлекательным вариантом LZMA_Alone.

Я помню, как собирали болванку Junior 2.2 (1 CD), и, значит,
в последний день выясняли, войдёт туда WindowMaker или нет... :)
http://lists.altlinux.org/pipermail/devel/2003-February/010742.html
http://lists.altlinux.org/pipermail/devel/2003-February/010744.html

С появлением DVD как основного media-носителя дышать стало проще.  А
ситуация с интернетом стала глобально выправляться только в последнее
время; так что теперь экономия на трафике rpm пакетов это чаще вопрос
комфорта, а не денег.  В общем, увы, общая актуальность вопроса сжатия
несколько снизилась.

Возвращаясь к теме, дилемма как раз состоит в том, что для разовой
передачи пакетов лучше подходит LZMA, а для последующей синхронизации
пакетов, если в пакетах небольшие изменения, лучше подходит rsyncable
deflate.  И если LZMA даёт эффект сразу, то от rsyncable deflate эффект
появляется только со второго или третьего раза.

Но, в общем, хорошо иметь выбор, и этот выбор становится всё менее
гипотетическим.  Можно будет сделать какую-нибудь статистику,
перекрывает ли экономия от rsyncability экономию от LZMA или нет.
Пока интрига сохраняется. :)

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton V. Boyarshinov]

On Fri, 30 May 2008 15:28:39 +0400 Alexey Tourbin
 wrote:

> Я помню, как собирали болванку Junior 2.2 (1 CD), и, значит,

> С появлением DVD как основного media-носителя дышать стало проще.
lite на 1 CD. Школьные Лёгкий и Юниор -- наборы из 2 CD.

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexander Bokovoy]

30 мая 2008 г. 14:44 пользователь Anton Farygin <rider@altlinux.com> написал:
>> Но, в общем, хорошо иметь выбор, и этот выбор становится всё менее
>> гипотетическим.  Можно будет сделать какую-нибудь статистику,
>> перекрывает ли экономия от rsyncability экономию от LZMA или нет.
>> Пока интрига сохраняется. :)
>
> DVD конечно, ситуацию намного облегчило.. но, к сожалению, всё ещё
> востребованы дистрибутивы на CD.
>
> Идеальный вариант - LZMA + rsync.
Пока по оценке Алексея в текущем контейнере LZMA это сделать не
получается. Все же, я бы предложил более внимательно смотреть на
формирование содержимого lite на пакетном уровне. Думаю, что там есть
еще резервы.


-- 
/ Alexander Bokovoy

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton V. Boyarshinov]

> Пока по оценке Алексея в текущем контейнере LZMA это сделать не
> получается. Все же, я бы предложил более внимательно смотреть на
> формирование содержимого lite на пакетном уровне. Думаю, что там есть
> еще резервы.
openoffice не выкинешь
и даже gcc :(

Re: [devel] rpm: rsyncable deflate vs LZMA

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 437 bytes --]

On Fri, May 30, 2008 at 07:03:38PM +0400, Anton V. Boyarshinov wrote:
> > Пока по оценке Алексея в текущем контейнере LZMA это сделать не
> > получается. Все же, я бы предложил более внимательно смотреть на
> > формирование содержимого lite на пакетном уровне. Думаю, что там есть
> > еще резервы.
> openoffice не выкинешь
> и даже gcc :(

Если для lite не нужен gcc, значит, существует способ от него избавиться.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton V. Boyarshinov]

> > и даже gcc :(
> Если для lite не нужен gcc, значит, существует способ от него избавиться.
пока только вместе с Xorg :(

Re: [devel] rpm: rsyncable deflate vs LZMA

[Mikhail Gusarov]

[-- Attachment #1: Type: text/plain, Size: 394 bytes --]

Twas brillig at 19:17:13 30.05.2008 UTC+04 when Anton V. Boyarshinov did gyre and gimble:

 >> Если для lite не нужен gcc, значит, существует способ от него избавиться.
 AVB> пока только вместе с Xorg :(

А какая там зависимость?

-- 
JID: dottedmag@altlinux.org / dottedmag@jabber.dottedmag.net

[-- Attachment #2: Type: application/pgp-signature, Size: 196 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton V. Boyarshinov]

>  >> Если для lite не нужен gcc, значит, существует способ от него избавиться.
>  AVB> пока только вместе с Xorg :(
> 
> А какая там зависимость?
http://lists.altlinux.org/pipermail/devel/2008-May/074683.html

Re: [devel] rpm: rsyncable deflate vs LZMA

[Mikhail Gusarov]

[-- Attachment #1: Type: text/plain, Size: 624 bytes --]

Twas brillig at 19:32:54 30.05.2008 UTC+04 when Anton V. Boyarshinov did gyre and gimble:

 >>  >> Если для lite не нужен gcc, значит, существует способ от него избавиться.
 >>  AVB> пока только вместе с Xorg :(
 >> А какая там зависимость?
 AVB> http://lists.altlinux.org/pipermail/devel/2008-May/074683.html

Ну, так я и думал. Значит, как Дима и писал, существует способ от него
избавиться.

-- 
JID: dottedmag@altlinux.org / dottedmag@jabber.dottedmag.net

[-- Attachment #2: Type: application/pgp-signature, Size: 196 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 3042 bytes --]

On Fri, May 30, 2008 at 03:23:31AM +0400, Alexey Tourbin wrote:
> On Fri, May 30, 2008 at 01:56:10AM +0400, Dmitry V. Levin wrote:
> > On Fri, May 30, 2008 at 01:31:14AM +0400, Alexey Tourbin wrote:
> > [...]
> > > У меня есть идея.  Для выбора точек синхронизации (gzflush) можно
> > > использовать не только "слепой" rsync hint, но и cpio hint -- как
> > > только мы видим cpio magic "070707", мы знаем, что через несколько
> > > байтов будет mtime и потом пойдёт имя и содержимое файла.  То есть
> > > sync можно делать в месте окончания очередного cpio header.
> > 
> > Это заметно снизит степень сжатия, когда в архиве много маленьких файлов?
> 
> Этим можно управлять, чтобы сознательно пропускать только "совсем
> маленькие" файлы.
> 
> > > Правда, я не знаю, даст это что-нибудь в случае с маленькими файлами
> > > или нет.  Это может ничего не дать из-за того, что первые совпавшие
> > > блоки в сжатом виде всё равно могут отличаться (из-за backreferences
> > > в предыдущий блок).
> > 
> > Могут или будут?
> 
> Если сделать как показано ниже, то для пакета man-pages (после повторной
> пересборки) 'speedup 1.09' возрастает до 'speedup 1.19'.  То есть эффект
> от синхронизации сразу после cpio хедера есть, он заметный, но не
> настолько большой, чтобы всё искупать.

Я реализовал более аккуратный cpio хинтинг для rsyncable_gzwrite().

Также появились первые результаты rsyncability тестирования.
А именно, мы тестируем rsyncability двух rpm пакетов, как если
бы они были собраны уже с помощью rsyncable_gzwrite().

test-rsynability glibc-core-2.5.1-alt4.x86_64.rpm glibc-core-2.5.1-alt5.x86_64.rpm => "speedup is 15.99"
test-rsynability glibc-core-2.3.5-alt7.x86_64.rpm glibc-core-2.5.1-alt5.x86_64.rpm => "speedup is 1.00"
test-rsynability glibc-2.3.5-alt7.x86_64.rpm glibc-2.5.1-alt5.x86_64.rpm => "speedup is 1.28"
test-rsynability firefox-2.0.0.13-alt1.x86_64.rpm firefox-2.0.0.14-alt1.x86_64.rpm => "speedup is 1.97"
test-rsynability xorg-x11-server-1.4.0.90-alt17.x86_64.rpm xorg-x11-server-1.4.0.90-alt19.x86_64.rpm => "speedup is 1.48"

Например, "speedup is 1.97" для пакета firefox означает, что примерно
половина кусков между этими двумя пакетами совпадают (если бы эти пакеты
были собраны с rsyncable_gzwrite), а другая половина кусков не совпадает;
так что по размеру придётся скачивать примерно половину фаерфокса.

Вот код для тестирования.

gzdio.c:
#include <stdio.h>
#include <assert.h>
#include <rpmio.h>
int main()
{
	FD_t Fd = Fdopen(fdDup(fileno(stdout)), "w9.gzdio");
	assert(Fd);
	char buf[BUFSIZ];
	size_t n, m;
	while ((n = fread(buf, 1, sizeof(buf), stdin))) {
		m = Fwrite(buf, 1, n, Fd);
		assert(m == n);
	}
	Fclose(Fd);
	return 0;
}

(gzdio.c надо линковать с новым librpmio, в котором сидит
rsyncable_gzwrite).

test-rsynability:
#!/bin/sh -efu
f1="$1" f2="$2"
shift 2
rpm2cpio "$f1" |./gzdio >cpio1.gz
rpm2cpio "$f2" |./gzdio >cpio2.gz
rsync -v -e ./rsync-shell foo:cpio1.gz cpio2.gz

rsync-shell:
shift && exec "$@"

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

[devel] rsyncability test: openoffice

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 2777 bytes --]

On Sat, May 31, 2008 at 01:31:09AM +0400, Alexey Tourbin wrote:
> Также появились первые результаты rsyncability тестирования.
> А именно, мы тестируем rsyncability двух rpm пакетов, как если
> бы они были собраны уже с помощью rsyncable_gzwrite().
> 
> test-rsynability glibc-core-2.5.1-alt4.x86_64.rpm glibc-core-2.5.1-alt5.x86_64.rpm => "speedup is 15.99"
> test-rsynability glibc-core-2.3.5-alt7.x86_64.rpm glibc-core-2.5.1-alt5.x86_64.rpm => "speedup is 1.00"
> test-rsynability glibc-2.3.5-alt7.x86_64.rpm glibc-2.5.1-alt5.x86_64.rpm => "speedup is 1.28"
> test-rsynability firefox-2.0.0.13-alt1.x86_64.rpm firefox-2.0.0.14-alt1.x86_64.rpm => "speedup is 1.97"
> test-rsynability xorg-x11-server-1.4.0.90-alt17.x86_64.rpm xorg-x11-server-1.4.0.90-alt19.x86_64.rpm => "speedup is 1.48"
> 
> Например, "speedup is 1.97" для пакета firefox означает, что примерно
> половина кусков между этими двумя пакетами совпадают (если бы эти пакеты
> были собраны с rsyncable_gzwrite), а другая половина кусков не совпадает;
> так что по размеру придётся скачивать примерно половину фаерфокса.

Вот пример с опенофисом.

$ ./test-rsyncability /ALT/archive/Sisyphus/2008/01/01/files/x86_64/RPMS/openoffice.org-2.3.1.1-alt2.x86_64.rpm /ALT/Sisyphus/files/x86_64/RPMS/openoffice.org-2.4.0.12-alt1.x86_64.rpm
sent 776603 bytes  received 88086117 bytes  6582423.70 bytes/sec
total size is 114643659  speedup is 1.29
$ 

Тут я взял старый опенофис (по состоянию на первое число сего года)
и новый опенофис.  Размер нового опенофиса составляет 114M (беру по
первым цифрам), но при синхронизации со старым опенофисом придётся
скачать всего 88M.

Теперь посмотрим, что будет, если сжать новый опенофис с помощью LZMA.

$ rpm2cpio /ALT/Sisyphus/files/x86_64/RPMS/openoffice.org-2.4.0.12-alt1.x86_64.rpm |./lzma -2 |wc -c
92916334
$ 

Значит, если сжать опенофис с помощью LZMA, то придётся заново качать
92M вместо 114M; при этом синхронизация с помощью rsync ничего не даст.

Таким образом, эффект rsyncability в данном случае перекрывает эффект
LZMA (заново надо качать 92M, а при синхронизации -- 88M).  Правда,
не знаю, имеет ли смысл сравнивать эти эффекты напрямую.  Всё же эффект
rsyncability получается не настолько большой, как того хотелось бы (с
другой стороны, я синхронизирую достаточно разные *версии* опенофиса
2.3.x -> 2.4.x).

> test-rsynability:
> #!/bin/sh -efu
> f1="$1" f2="$2"
> shift 2
> rpm2cpio "$f1" |./gzdio >cpio1.gz
> rpm2cpio "$f2" |./gzdio >cpio2.gz
> rsync -v -e ./rsync-shell foo:cpio1.gz cpio2.gz

Этот скрипт лучше немного поправить:

test-rsyncability:
#!/bin/sh -efu
rpm2cpio "$1" |./gzdio >cpio1.gz
rpm2cpio "$2" |./gzdio >cpio2.gz
rsync --block-size 1024 -v -e ./rsync-shell foo:cpio2.gz cpio1.gz

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 747 bytes --]

On Fri, May 30, 2008 at 02:44:39PM +0400, Anton Farygin wrote:
> Идеальный вариант - LZMA + rsync.

Для rsynability нужен маленьий размер словаря.  У deflate размер
словаря 32K, а у 'lzma -2' -- 1M.

Представь себе, что ты за раз съел десерт, первое блюдо и второе блюдо,
запив всё это компотом; в выходных данных всё премешается, и уже нельзя
определить, где что было.

А если заглатывать понемножку, долго переваривать и какать понемножку,
то можно установить связь между входными и выходными данными.  А это
и требуется для rsyncability.

Вот таблица для сравнения.

Алгоритм	Размер словаря		Сжатый размер опенофиса
--------	--------------		-----------------------
deflate		32K			114M
lzma -1		64K			100M
lzma -2		1M			92M

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Kirill A. Shutemov]

[-- Attachment #1: Type: text/plain, Size: 498 bytes --]

On Sat, May 31, 2008 at 02:25:23PM +0400, Alexey Tourbin wrote:
> А если заглатывать понемножку, долго переваривать и какать понемножку,
> то можно установить связь между входными и выходными данными.  А это
> и требуется для rsyncability.

В фортунки!

-- 
Regards,  Kirill A. Shutemov
 + Belarus, Minsk
 + ALT Linux Team, http://www.altlinux.com/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 567 bytes --]

On Sat, May 31, 2008 at 07:59:30PM +0300, Kirill A. Shutemov wrote:
> On Sat, May 31, 2008 at 02:25:23PM +0400, Alexey Tourbin wrote:
> > А если заглатывать понемножку, долго переваривать и какать понемножку,
> > то можно установить связь между входными и выходными данными.  А это
> > и требуется для rsyncability.
> 
> В фортунки!

$ fortune -a -m rabelaisian
fortune: /usr/share/games/fortune/off: No fortune files in directory.
fortune:/usr/share/games/fortune/off not a fortune file or directory
zsh: segmentation fault  fortune -a -m rabelaisian
$

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: [devel] rpm: rsyncable deflate vs LZMA

[Anton Farygin]

Alexander Bokovoy пишет:
> 30 мая 2008 г. 14:44 пользователь Anton Farygin <rider@altlinux.com> написал:
>>> Но, в общем, хорошо иметь выбор, и этот выбор становится всё менее
>>> гипотетическим.  Можно будет сделать какую-нибудь статистику,
>>> перекрывает ли экономия от rsyncability экономию от LZMA или нет

Re: [devel] rpm: rsyncable deflate vs LZMA

[Mikhail Gusarov]

[-- Attachment #1: Type: text/plain, Size: 458 bytes --]

Twas brillig at 04:33:31 01.06.2008 UTC+04 when Alexey Tourbin did gyre and gimble:

 >> В фортунки!

 AT> $ fortune -a -m rabelaisian
 AT> fortune: /usr/share/games/fortune/off: No fortune files in directory.
 AT> fortune:/usr/share/games/fortune/off not a fortune file or directory
 AT> zsh: segmentation fault  fortune -a -m rabelaisian
 AT> $

В багзиллу!

-- 
JID: dottedmag@altlinux.org / dottedmag@jabber.dottedmag.net

[-- Attachment #2: Type: application/pgp-signature, Size: 196 bytes --]

[devel] [JT] fortunezilla :)

[Michael Shigorin]

On Sun, Jun 01, 2008 at 08:07:43PM +0700, Mikhail Gusarov wrote:
>  >> В фортунки!
>  AT> $ fortune -a -m rabelaisian
>  AT> fortune: /usr/share/games/fortune/off: No fortune files in directory.
>  AT> fortune:/usr/share/games/fortune/off not a fortune file or directory
>  AT> zsh: segmentation fault  fortune -a -m rabelaisian
>  AT> $
> В багзиллу!

В фортунки всё вместе!

-- 
 ---- WBSegmentation fault (core dumped)

Re: [devel] rpm: rsyncable deflate vs LZMA

[Alexey I. Froloff]

[-- Attachment #1: Type: text/plain, Size: 372 bytes --]

* Mikhail Gusarov <dottedmag@> [080601 17:13]:
>  AT> $ fortune -a -m rabelaisian
>  AT> fortune: /usr/share/games/fortune/off: No fortune files in directory.
>  AT> fortune:/usr/share/games/fortune/off not a fortune file or directory
>  AT> zsh: segmentation fault  fortune -a -m rabelaisian
>  AT> $
> В багзиллу!
Типа уже пофиксил.

-- 
Regards,
Sir Raorn.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [devel] [JT] fortunezilla :)

[Sergey Balbeko]

А может нам действительно какой-то фортунозавр завести;) ? С
регулярным копи-пастом в него, постоянным голосованием и
чисткой-разбором раз в месяц;)

On 6/1/08, Michael Shigorin <mike@osdn.org.ua> wrote:
> On Sun, Jun 01, 2008 at 08:07:43PM +0700, Mikhail Gusarov wrote:
>>  >> В фортунки!
>>  AT> $ fortune -a -m rabelaisian
>>  AT> fortune: /usr/share/games/fortune/off: No fortune files in directory.
>>  AT> fortune:/usr/share/games/fortune/off not a fortune file or directory
>>  AT> zsh: segmentation fault  fortune -a -m rabelaisian
>>  AT> $
>> В багзиллу!
>
> В фортунки всё вместе!
>
> --
>  ---- WBSegmentation fault (core dumped)
> _______________________________________________
> Devel mailing list
> Devel@lists.altlinux.org
> https://lists.altlinux.org/mailman/listinfo/devel

-- 
Sent from Gmail for mobile | mobile.google.com

wbr, Sergey Balbeko <balbeko[at]altlinux.org>.
--
Ukraine, Lugansk region, Stakhanov.
Donbass State Technical University.
Institute of Automation and Electrotechnical Systems.
Computer Systems Department.

--
ICQ == "244-711"
JID == "m0s.bizzy[at]gmail.com"

Re: [devel] [JT] fortunezilla :)

[Mikhail Gusarov]

[-- Attachment #1: Type: text/plain, Size: 296 bytes --]

Twas brillig at 04:44:45 02.06.2008 UTC+03 when Sergey Balbeko did gyre and gimble:

 SB> А может нам действительно какой-то фортунозавр завести;)

Его wrar@ зовут :)

-- 
JID: dottedmag@altlinux.org / dottedmag@jabber.dottedmag.net

[-- Attachment #2: Type: application/pgp-signature, Size: 196 bytes --]

Re: [devel] [JT] fortunezilla :)

[Alexey I. Froloff]

[-- Attachment #1: Type: text/plain, Size: 190 bytes --]

* Mikhail Gusarov <dottedmag@> [080602 11:39]:
>  SB> А может нам действительно какой-то фортунозавр завести;)
> Его wrar@ зовут :)
Только не wrar@, а vvk@.

-- 
Regards,
Sir Raorn.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [devel] [JT] fortunezilla :)

[Michael Shigorin]

On Mon, Jun 02, 2008 at 04:44:45AM +0300, Sergey Balbeko wrote:
> А может нам действительно какой-то фортунозавр завести;) ?
> С регулярным копи-пастом в него, постоянным голосованием и
> чисткой-разбором раз в месяц;)

1) apt-cache search fortunes-ALT
2) можешь спросить у raorn@ его скрипты и помочь vvk@ ;)

> >>  >> В фортунки!
> >> В багзиллу!
> > В фортунки всё вместе!

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/