Пару дней назад, задумчиво оглядев свои файлы на домашнем хранилище, <strike> и разобрав папки sort, _sort, _sort2, _sort3</strike>, стёр всё пересекающееся и половину ненужного, а вторую половину заархивировал. Места стало хватать, но запаса всё равно мало. На этом месте можно было бы сорваться и <strike>стереть 6 сезонов Хауса</strike> купить ещё один терабайтный винт, но мне эта экстенсивная альтернатива не показалась слишком заманчивой, пока не выработаны все интенсивные варианты.
Оглядевшись вокруг, понял несколько вещей: <ol> <li>По существу, вся возня с поиском дубликатов и сжатием на лету должна делаться файловой системой. ФС для того ведь и нужны, чтобы мне не заниматься грамотным размещением информации на устройстве.</li> <li>Хорошие файловые системы поддерживают компрессию на лету.</li> <li>Очень хорошие файловые системы поддерживают блочную дедупликацию на лету.</li> <li>Отличные файловые системы поддерживают и компрессию, и блочную дедупликацию.</li> <li>Степень сжатия сильно зависит от присутствующих на диске данных.</li> </ol><habracut /><h4>Определения</h4> <a href="http://en.wikipedia.org/wiki/Data_deduplication">Дедупликация</a> — это способ убрать избыточность поиском повторяющихся (дубликатных) данных. Различают три вида дедупликации: <ul> <li><b>байтовая</b>, характерный элемент — последовательность байтов в файле. Байтовой дедупликацией занимаются компрессоры, типа DEFLATE, Lempel-Ziv и прочих. Не будем отклоняться от общепринятой терминологии, будем называть байтовую дедупликацию <i>"компрессией"</i>.</li> <li><b>блочная</b>, элемент — блок файловой системы.</li> <li><b>файловая</b>, элемент — отдельный файл. </li> </ul>Под определение отличной файловой системы попадает ZFS: поддерживает и компрессию, и блочную дедупликацию. Конечно, тут можно было бы сорваться и просто поставить себе OpenSolaris/FreeBSD с последним ZFS и попробовать скопировать данные туда, но лучше бы каким-нибудь иструментом наперёд оценить, стоит это делать или нет. Могущественный Гугл <a href="http://www.google.co.uk/search?q=estimate+data+deduplication">нашёл</a> только проприетарную NetApp’овскую программку, которая выдаётся через их premium support. Я уже было расстроился, но тут же понял, что написать её самому не очень трудозатратно.
<h4>Подготовка</h4> Давайте разберёмся, что написанный тул делает. Технические детали по запуску — в последнем разделе. Тул пытается поиграть в крутую ФС и реально перемолоть показанные ему файлы в поисках избыточности, на которой можно было бы сэкономить. Делает он это при помощи двух базовых операций: <ul> <li><b>COMPRESS</b>: Сжатие при помощи GZIP с уровнем 1 (best speed). В ZFS используется куда более шустрый алгоритм <a href="http://en.wikipedia.org/wiki/LZJB">LZJB</a>, но за неимением под рукой его Java-овской реализации, остановился на самом быстром доступном компрессоре. Я, кстати, понимаю, зачем ZFS’овцы изобрели LZJB: мой тул тормозит по большей части из-за компрессора.</li> <li><b>DEDUP</b>: Дедупликация а ля ZFS. Входной поток разбивается на блоки в 4 Кб (размер блока вообще-то настраивается), на каждом блоке считается хеш, затем хеш сверяется с внутренним хранилищем, и если такой хеш уже встречался, блок считается дубликатным и "отбрасывается". Тут важны две детали: <li><ol><li>дедупликация действует в рамках всего хранилища целиком, т.е. получает возможность устранять избыточность <i>между</i> файлами, </li> <li>мы предполагаем, что <a href="http://en.wikipedia.org/wiki/Collision_(computer_science)">коллизий</a> на хешах будет исчезающе мало. Утверждается, что на SHA256 вероятность коллизии равна примерно 2^(-256), но всё равно хочется это проверить. Перечитывать файлы каждый раз на обнаружении подозрительного хеша весьма дорого, поэтому я считаю <i>две</i> хешсуммы, более слабую MD5, и более сильную SHA256. Таким образом, можно будет поймать редкую коллизию на какой-нибудь хешсумме, а уж вероятность коллизии на обеих хешсуммах одновременно уже точно на порядки меньше этой измеренной величины. </li></ol></ul>Операции COMPRESS и DEDUP можно комбинировать четырьмя разными способами: <ol> <li><b>COMPRESS</b>. Сжать каждый файл без дедупликации.</li> <li><b>COMPRESS+DEDUP</b>. Сжать каждый файл, затем дедуплицировать сжатый файл.</li> <li><b>DEDUP</b>. Дедуплицировать каждый файл без сжатия</li> <li><b>DEDUP+COMPRESS</b>. Дедуплицировать каждый файл без сжатия, затем сжать полученные <i>блоки</i>.</li></ol></li></ul> На этом месте читателю можно предложить выбрать, какой из способов потенциально лучше. Я бы сказал, что COMPRESS и DEDUP по отдельности не выиграют, поскольку они покрывают только часть избыточности. А вот в каком порядке их применять? Кажется, что эффективность COMPRESS+DEDUP будет сильно ограничена тем, что словарные компрессоры будут ломать потенциально дедуплицируемые блоки из-за того, что основываются на частотном словаре, полученном на предыдущих блоках. С другой стороны, эффективность DEDUP+COMPRESS ограничена тем, что разбиение на мелкие блоки лишает этой же возможности: строить частотные словари на основании предыдущих блоков.
Ответ, понятно, зависит от данных. Вот, например, что получилось у меня на нескольких характерных наборах.
<h4>Эксперименты</h4> <h6>Тест 1. Эталон</h6> Для начала эталонный пуск. В папке лежат 10 симлинков на ISO-образ Ubuntu 10.04. С точки зрения тула — это 10 файлов по 700 Мб каждый, после запуска показывает:
<pre>COMPRESS: 1.01x increase. 7162300 Kb --(compress)-→ 7068243 Kb COMPRESS+DEDUP: 10.13x increase. 7162300 Kb --(compress)-→ 7068243 Kb --(dedup)-→ 706820 Kb DEDUP: 10.02x increase, 7162300 Kb ----(dedup)--→ 714486 Kb DEDUP+COMPRESS: 10.05x increase. 7162300 Kb ----(dedup)--→ 714486 Kb --(block-compress)-→ 712649 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> …что и ожидалось. Любой вариант, включающий дедупликацию, сжал папку в 10 раз. Простая компрессия дала только +1% — избыточности в самом iso-файле мало.
<h6>Тест 2. Смешанные данные</h6> Давайте ближе к реальным данным. Вот папка ~/Downloads, в которой лежит куча бинарных и небинарных файлов:
<pre>COMPRESS: 1.19x increase. 5080699 Kb --(compress)-→ 4275194 Kb COMPRESS+DEDUP: 1.19x increase. 5080699 Kb --(compress)-→ 4275194 Kb --(dedup)-→ 4261479 Kb DEDUP: 1.16x increase, 5080699 Kb ----(dedup)--→ 4371377 Kb DEDUP+COMPRESS: 1.18x increase. 5080699 Kb ----(dedup)--→ 4371377 Kb --(block-compress)-→ 4289665 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> Даже обычное сжатие помогло сэкономить по максимуму. Дедупликация сверху смогла снять лишних 1.5 мегабайта. Видимо, файлы достаточно разношёрстные.
<h6>Тест 3. Mercurial-пространство</h6> Рабочее пространство одного из проектов, в нём же Mercurial’овская папка .hg/, в которой хранится метаинформация, включая предыдущие ревизии:
<pre>COMPRESS: 1.29x increase. 598627 Kb --(compress)-→ 464654 Kb COMPRESS+DEDUP: 2.72x increase. 598627 Kb --(compress)-→ 464654 Kb --(dedup)-→ 220418 Kb DEDUP: 2.14x increase, 598627 Kb ----(dedup)--→ 280043 Kb DEDUP+COMPRESS: 2.61x increase. 598627 Kb ----(dedup)--→ 280043 Kb --(block-compress)-→ 229649 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> Немудрено, что дедупликация обнаружила .hg и понаходила в нём кучу дубликатов. Интересно другое: дедупликация на сжатых файлах дала больший прирост, чем сжатие конкретных блоков!
<h6>Тест 4. Пачка пространств</h6> Окей, ещё у меня есть папочка ~/trunks, в которой лежат рабочие пространства open-source проектов, в код которых я лазил.
<pre>COMPRESS: 1.79x increase. 7074165 Kb --(compress)-→ 3959337 Kb COMPRESS+DEDUP: 3.22x increase. 7074165 Kb --(compress)-→ 3959337 Kb --(dedup)-→ 2194769 Kb DEDUP: 1.88x increase, 7074165 Kb ----(dedup)--→ 3770317 Kb DEDUP+COMPRESS: 2.94x increase. 7074165 Kb ----(dedup)--→ 3770317 Kb --(block-compress)-→ 2406935 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> Там намешано и Mercurial, и SVN, и даже (эх) CVS, поэтому следовало ожидать минимум двухкратного прироста. Оказалось, что дедупликация нашла 1.8х, и дожало почти до 3х. Но дедупликация уже сжатого впечатляет ещё больше.
<h6>Тест 5. Squid’овский кеш</h6> Вот пример поближе к админской действительности, сжатие кеша локального squid’а: <pre>COMPRESS: 1.07x increase. 437135 Kb --(compress)-→ 410237 Kb COMPRESS+DEDUP: 1.07x increase. 437135 Kb --(compress)-→ 410237 Kb --(dedup)-→ 409091 Kb DEDUP: 1.17x increase, 437135 Kb ----(dedup)--→ 374082 Kb DEDUP+COMPRESS: 1.19x increase. 437135 Kb ----(dedup)--→ 374082 Kb --(block-compress)-→ 366212 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> +20% места к кешу.
<h6>Тест 6. Много пересекающихся данных</h6> Понятно, что дедупликация сильно рулит, когда есть много пересекающихся файлов. Классический пример — бекапы. У меня, однако, бекапы делаются rsnapshot’ом, который делает всё на хардлинках, так что файловая дедупликация у меня получается автоматически. А вот если не пользоваться rsnapshot’ными трюками, тогда сжимается на ура. Для симуляции такого характерного случая я выбрал рабочую папку с результатами тестирования одного очень популярного продукта:
<pre>COMPRESS: 7.52x increase. 23711826 Kb --(compress)-→ 3154215 Kb COMPRESS+DEDUP: 25.54x increase. 23711826 Kb --(compress)-→ 3154215 Kb --(dedup)-→ 928274 Kb DEDUP: 4.77x increase, 23711826 Kb ----(dedup)--→ 4974532 Kb DEDUP+COMPRESS: 20.43x increase. 23711826 Kb ----(dedup)--→ 4974532 Kb --(block-compress)-→ 1160892 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> В 25 раз меньше места надо!
<h6>Тест 7. Видеоархив</h6> А теперь ложка дёгтя. Аудио-видео-архивы и прочие уже выдавили из себя большую часть избыточности, поэтому на них не выиграешь. Вот, например, мой местный видеоархив:
<pre>COMPRESS: 1.12x increase. 5910125 Kb --(compress)-→ 5291057 Kb COMPRESS+DEDUP: 1.12x increase. 5910125 Kb --(compress)-→ 5291057 Kb --(dedup)-→ 5289737 Kb DEDUP: 1.11x increase, 5910125 Kb ----(dedup)--→ 5323949 Kb DEDUP+COMPRESS: 1.11x increase. 5910125 Kb ----(dedup)--→ 5323949 Kb --(block-compress)-→ 5331559 Kb detected collisions: 0 on MD5, 0 on SHA256</pre> <h5>О чём помнить</h5><ul> <li>В этом эксперименте не учитываются накладные расходы на поддержание таблицы хешей. Я считаю это верной оценкой, так как накладные расходы будут сильно зависеть от реализации дедупликации. Один из вариантов оффлайновой дедупликации вообще не требует поддержания огромной таблицы, например, если попарно дедуплицировать все файлы в хранилище. За это, понятно, заплатится процессорным временем.</li> <li>Этот эксперимент ни под каким соусом нельзя считать тестом производительности дедупликации, Java’ы, BerkeleyDB и прочих компонент. Единственное надёжное знание, получаемое из этого эксперимента — это оценка сжимаемомости самих данных</li> </ul> <h5>Как запустить</h5> Собственно, вот он (<a href="http://people.apache.org/~shade/articles/dedup-habr/dedup.tar.gz">архив с исходниками</a> [~15Kb], <a href="http://people.apache.org/~shade/articles/dedup-habr/dedup.jar">скомпиленный jar</a> [~1Mb]). Технические данные: Java SE, Apache License v2. Хотите что-то менять — меняйте. Хотите экспериментировать на своих данных — экспериментируйте.<img src="http://shipilev.net/marker.png" width=1 height=1>
Запуск производится следующей командой: <pre> $ java -jar dedup.jar <path> [storage-engine] [block-size]</pre><ul> <li><b>path</b> — путь к папке/файлу, над которым мы работаем. Нам достаточно только привилегий на чтение, в сами целевые файлы ничего не пишется.</li> <li><b>storage-engine</b> определяет способ хранения списка хешей. В моей версии есть несколько storage’ей: <ul> <li><b>inmemory</b>. Хранить в памяти. Работает быстро<strike>, но недолго</strike>, пока не кончится память. Памяти ей нужно примерно 15:1, т.е. на 15 Гб пережёванных данных требуется порядка 1 Гб памяти.</li> <li><b>berkeley</b>. Включена по умолчанию. Хранит хеши в BerkeleyDB, файлы для БД создаёт прямо в рабочем каталоге, поэтому не забудьте перед очередным запуском их снести (hashes-*). Работает приемлемо быстро, но на больших объёмах я её ещё не проверял. Свободного места на диске ей нужно примерно в том же соотношении 15:1.</li> <li><b>derby/h2</b>. Хранить в Derby/H2. У меня возникли проблемы с их масштабируемостью (ну, реляционные они, не для того они сделаны), поэтому оставил их just for fun. Для того, чтобы их использовать, нужно в pom.xml поменять provided→runtime в депендах.</li> </ul></li> <li><b>block-size</b> выбирается в байтах, по умолчанию 4096</li> </ul>