[devel] rsync_roll

[Alexey Tourbin <at@altlinux.ru>]

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

On Sun, May 25, 2008 at 12:31:24PM +0400, Alexander Bokovoy wrote:
> Патч, который брал ты, он отличается от рекомендуемого
> http://ozlabs.org/~rusty/gzip.rsync.patch2, на который ссылаются как
> Джефф, так и Эгмонт.

Что делает этот патч?  Почему "это работает"?
Прошу подсказать, правильно ли я понимаю это дело или нет.

Этот патч оперирует на входном (несжатом) потоке байтов
|--------------------------------------------------------->

Вычисляется "контрольная сумма" (с переполнением) "окна"
размером RSYNC_WIN байтов входного потока.

|--------------------------------------------------------->
   |___________|
     RSYNC_WIN

При добавлении каждого нового байта окно "сдвигается" и вычисляется
новая сумма.

|--------------------------------------------------------->
    -|__________+|
       RSYNC_WIN

Особенность вычисления этой суммы состоит в том, что достаточно
вычесть старый "выбывший" элемент (слева, отмечен знаком минус)
и добавить новый элемент (отмечен знаком плюс).

Когда сумма принимает определённое значение (а именно, когда
sum % RSYNC_WIN == 0) то в конце окна принимается решение
"сборосить блок" и заново инициализировать процедуру сжатия.

|--------------------------------------------------------->
     |_____0_____|
       RSYNC_WIN  \
       		   `reset compression here!
                
Это означает, что в этой точке как бы начинается "новый файл",
который gzip будет жать отдельно; если в двух разных входных
потоках в точке обнуления суммы несжатые данные идут одинаковые,
то и сжатые данные пойдут одинаковые.

Я всё равно плохо понимаю, почему "это работает", то есть как это
способствует повышению rsyncability.

Теперь дальше вопрос, что делает gzip при обнулении суммы?
Он полностью записывает блок?  Но ведь нормальный размер блока 32K,
а размер окна 4K.  Поскольку любое значение суммы по модулю 4096
можно считать равновероятным, то, выходит, что вместо блока 32K
gzip будет делать блоки в среднем по 4K.  Или нет?

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

$ ./rsyncable </etc/info-dir
sync at 4920
sync at 19949
sync at 24300
sync at 31782
sync at 44390
sync at 50260
sync at 68705
sync at 80677
sync at 85097
$ du -bk /etc/info-dir
84      /etc/info-dir
$ 

Из этого видно, что на самом деле размер блока в данном случае
получается примерно 8K (9 синков = 10 блоков на 84Кб), а не 4,
как я ожидал.  В чём тут дело?

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

#include <stdint.h>
#include <stdbool.h>

#define RSYNC_WIN 4096

struct rsync_state {
	uint64_t n;			/* number of elements in the window */
	uint64_t sum;			/* current sum */
	unsigned char win[RSYNC_WIN];	/* window elements */
};

static inline
bool rsync_next(struct rsync_state *s, unsigned char c)
{
	if (s->n < RSYNC_WIN) {		/* not enough elements */
		s->sum += c;		/* update the sum */
		s->win[s->n++] = c;	/* remember the element */
		return false;		/* no match */
	}
	int i = s->n++ % RSYNC_WIN;	/* wrap up */
	s->sum -= s->win[i];		/* move the window on */
	s->sum += c;
	s->win[i] = c;
	if (s->sum % RSYNC_WIN == 0) {	/* match */
		s->n = 0;		/* reset */
		s->sum = 0;
		return true;
	}
	return false;
}

#include <stdio.h>

int main()
{
	struct rsync_state rs = { 0, 0 };
	int c;
	while ((c = getc(stdin)) != EOF)
		if (rsync_next(&rs, c))
			printf("sync at %ld\n", ftell(stdin));
	return 0;
}

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