Блог

Я ищу ограниченную форму контроля версий в базе данных здесь:

• Размер имеет наибольшее значение: множество ревизий одного и того же файла должно занимать как можно меньше места (я не ищу сжатия, поскольку данные уже сжаты)
• Вычислительные требования вторичны
• Я должен иметь возможность извлекать текущую ревизию документа как можно быстрее (извлечение более старых версий не критично по времени)

В основном ответы должны содержать как минимум две вещи:

• Какой алгоритм двоичного разделения вы бы использовали?
• Как бы вы структурировали эту систему специфичным для PostreSQL образом?

«Размер имеет наибольшее значение»: как насчет внешнего инструмента diff (например, bsdiff?), использующего, например, PL / sh.

«Я должен иметь возможность извлекать текущую ревизию документа как можно быстрее»: в этом случае вы захотите выполнить свой diff «неправильным» способом, поэтому каждая ревизия будет включать:

1. замените ‘предыдущую ревизию’ на разницу между ‘новой ревизией’ и ‘предыдущей ревизией’
2. добавить «новую ревизию»

Для возврата к старой ревизии потребуется итеративное применение предыдущих различий в виде исправлений, пока вы не доберетесь до нужной вам ревизии.

Что бы вы ни делали, я думаю, вам нужно будет сначала распаковать данные, прежде чем использовать инструмент diff. Вот почему:

 dd if=/dev/urandom of=myfile.1 bs=1024 count=10
cp myfile.1 tmp; cat tmp >> myfile.1
cp myfile.1 tmp; cat tmp >> myfile.1
cp myfile.1 tmp; cat tmp >> myfile.1
cp myfile.1 tmp; cat tmp >> myfile.1
dd if=/dev/urandom of=myfile.2 bs=1024 count=10
cp myfile.2 tmp; cat tmp >> myfile.2
cp myfile.2 tmp; cat tmp >> myfile.2
cp myfile.2 tmp; cat tmp >> myfile.2
cp myfile.2 tmp; cat tmp >> myfile.2
cat myfile.1 >> myfile.2
bsdiff myfile.1 myfile.2 diff
gzip -c myfile.1 > myfile.1.gz
gzip -c myfile.2 > myfile.2.gz
bsdiff myfile.1.gz myfile.2.gz gz.diff
rm tmp
ls -l

-rw-r--r-- 1 root root  17115 2011-04-05 10:54 diff
-rw-r--r-- 1 root root  21580 2011-04-05 10:54 gz.diff
-rw-r--r-- 1 root root 163840 2011-04-05 10:54 myfile.1
-rw-r--r-- 1 root root  11709 2011-04-05 10:54 myfile.1.gz
-rw-r--r-- 1 root root 327680 2011-04-05 10:54 myfile.2
-rw-r--r-- 1 root root  23399 2011-04-05 10:54 myfile.2.gz
  

Обратите внимание, что это gz.diff больше, чем diff — если вы попробуете это с реальными файлами, я ожидаю, что разница будет еще больше.

Мне, как правило, очень не нравится заново изобретать колесо. В случае оптимизации пространства хранения люди намного умнее меня уже нашли решения. Я бы предпочел, когда это возможно, использовать тяжелую работу этих действительно умных людей. С учетом сказанного я мог бы рассмотреть возможность хранения моих файлов в системе контроля версий, такой как Mercurial или Git, как только я пойму, как они хранят двоичные данные. Как только вы определите, какую из них вы хотите использовать, вы можете рассмотреть способы создания некоторых хранимых функций, скорее всего, на pl / perl или аналогичной, которая может взаимодействовать с системой контроля версий и преодолевать разрыв между вашими данными отношений в PostgreSQL и двоичными файлами.

Моя единственная проблема с этим подходом заключается в том, что мне не очень нравится, что я взял транзакционную систему и внедрил в нее внешнюю систему (Mercurial / Git). И вдобавок ко всему, резервная копия базы данных не будет создавать резервную копию моего репозитория Mercurial или Git. Но всегда найдется компромисс, поэтому просто определите, с какими из них вы можете смириться.