Subversion и хранение ревизий
Суббота, 19 января 2013

Многие знают, что Subversion хранит историю в виде списка разниц-дельт между различными версиями файла. Это и понятно: обычно изменения в файлах происходят не глобальные и небольшое описание разницы будет занимать значительно меньше места. Но тут возникает вопрос, как сервер извлекает информацию из истории. Можно предположить, что самая свежая версия файла хранится целиком, а предыдущую можно получить, применив изменения (reverse-patch) к самой свежей версии. Но что делать, когда нужно посмотреть вариант, который был 100500 ревизий назад? Не зависнет ли сервер на этом действии? Кроме того, при таком подходе во время сохранения нужно изменять 2 файла: записать новый целиком и заменить старый на дельту.

Или еще вариант: делать всё в обратную сторону. Т.е. хранить не последнюю ревизию, а просто разницу. Тогда запись значительно упрощается, но вместе с тем чтение файлов с длинной историей превращается в ад. Я бы навскидку предложил добавить какие-нибудь контрольные точки, например, каждые 128 ревизий держать целую версию файла. Это не должно сильно увеличить время записи, но вместе с тем время поиска возрастет в разы. Кстати, примерно так поступают кодировщики видео, что обеспечивает возможность перемотки.

В любом случае, вариант, воплощенный на самом деле, во много раз лучше. Он называется skip-deltas. Приведу картину из документации.

0 <- 1    2 <- 3    4 <- 5    6 <- 7
0 <------ 2         4 <------ 6
0 <---------------- 4
0 <------------------------------------ 8 <- 9

Например, нам нужно записать ревизию 60. 6010 = 1111002. Правую 1 заменяем на 0 и получаем ревизию, относительно которой нужно построить разницу, т.е. 1110002 = 5610. Ревизия 0 для всех файлов одинаковая и соответствует пустому файлу. Вот и получаем быстрый доступ к любой ревизии на репозитории практически любого размера.

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

← Google Closure JSDoc cheat sheetБудущее →