angle-left

Исследование параметров дедупликации

Данная статья является продолжением моей предудущей статьи,где была представлена и разьяснена технология дедупликации. В отличии от предыдущей статья, задачей данной работы является экспериментальное исследование зависимости параметров процесса дедупликации (от используемых хэш-функций и размера блока данных) . 

Основными целями работы являются:

  1. исследование зависимости коэффициента дедупликации от размера блока дедуплицируемых данных;
  2. исследование зависимости времени процесса дедупликации от используемых хеш-функций и размера блока данных;
  3. обнаружение коллизий в процессе дудупликации и способы уменьшения вероятности их возникновения.

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

Средства исследования :

Для экспериментального исследования было написано приложение для анализа эффективности использования дедупликации.

Принцип работы приложения:

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

Для процесса хеширования мною были использованны хэш-функции использующие алгоритмы MD5, SHA-256, SHA-512, SHA-1
Для уменьшения вероятности возникновения коллизии были использованы помимо одиночных алгоритмов, комбинации алгоритмов хеширования.
При использовании комбинаций алгоритмов, мы можем отловить коллизию в случае если результаты на запрос о наличие\отсутствии хеша в базе будут отличаться у двух функций используемых в данной комбинации хэш-функций. Полностью мы не избавляемся от возникновения коллизий, но таким образом мы снижаем вероятность возникновения коллизии.

В рамках исследования отлавливать ошибки хеширования можно по окончательным результатам, смотря на объем выходных данных в зависимости от использования хэш-функций: при совпадении коэффициентов дедупликации и, соответственно, объема выходных данных, мы предполагаем, что коллизий не было, в противном случае (несовпадении коэффициента дедупликации и выходных данных) говорит о том, что коллизии имели место в процессе работы приложения.

В качестве хранилища хешей используется хранение в памяти посредством структуры данных Java - ConcurrentHashMap

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

В качестве минимального размера блока был выбран размер сектора (512 байт), ввиду того, что операции чтения\записи происходят именно секторами. В качестве верхней границы был выбран 1 мегабайт, из предположения о достаточно низком коэффициенте дедупликации на таких, относительно больших, размерах блока.

Исходные данные :

Так как дедупликация является технологией находящее все более и более широкое и повседневное применение, в качестве набора исходных данных был взят набор образов трех виртуальных машин с развернутыми на них службами и данными ( в частности на одном из них живет drupal ).
 


Совокупный объем данных представляемый 3 образами ~ 17.2Gb (точный размер 17631364 байт)

Нужно выявить информацию, которая будет являться важной в рамках данного исследования:

  • объем входных данных
  • объем выходных данных
  • Размер блока данных
  • Наличие ошибок при хешировании
  • Время выполнения

Ниже приведена таблица результатов полученная на данном наборе данных
 

Условные обозначения
BS - BlockSize - размер блока данных
HA - HashAlgoritm - алгоритм( алгоритмы) хеширования
BR - BlocksRead - количество считанных блоков
BD - BlocksDedupl - количество уникальных блоков
TR - TimeRead - время чтения данных
TD - TimeDedup - время дедупликации
TA - TimeAll - общее время выполнени
SO - SizeOutput - количество дедуплицированных данных
K - Коэффицент дедупликации

BS HA BR BD TR TD TA SO K
кб       мс мс мс кб  
0,5 MD5 35262728 19454436 260108 82704 276222 7904146 1,81
  SHA-1 35262728 19454436 329639 101459 303935 7904146 1,81
  SHA-256 35262728 19454436 289300 165725 321189 7904146 1,81
  SHA-512 35262728 19454436 265209 150612 319567 7904146 1,81
  MD5 SHA-1 35262728 19454436 300940 168052 351500 7904146 1,81
  MD5 SHA-256 35262728 19454436 262224 253288 355135 7904146 1,81
  MD5 SHA-512 35262728 19454436 318362 187799 352672 7904146 1,81
  SHA-1 SHA-512 35262728 19454436 294886 237894 374526 7904146 1,81
  MD5 SHA-1 SHA-512 35262728 19454436 295782 263433 383262 7904146 1,81
1 MD5 17631364 11125573 478147 65627 533876 6505791 1,58
  SHA-1 17631364 11125573 403131 107286 473913 6505791 1,58
  SHA-256 17631364 11125573 232286 182778 338911 6505791 1,58
  SHA-512 17631364 11125573 382467 94365 439812 6505791 1,58
  MD5 SHA-1 17631364 11125573 233797 171011 332905 6505791 1,58
  MD5 SHA-256 17631364 11125573 193933 209590 297243 6505791 1,58
  MD5 SHA-512 17631364 11125573 275115 178408 380025 6505791 1,58
  SHA-1 SHA-512 17631364 11125573 215721 206724 293967 6505791 1,58
  MD5 SHA-1 SHA-512 17631364 11125573 250954 175735 298445 6505791 1,58
2 MD5 8815682 6047659 516625 43382 558559 5536046 1,46
  SHA-1 8815682 6047659 436059 121775 547420 5536046 1,46
  SHA-256 8815682 6047659 422604 127069 534863 5536046 1,46
  SHA-512 8815682 6047659 422009 120170 536094 5536046 1,46
  MD5 SHA-1 8815682 6047659 380303 154675 519450 5536046 1,46
  MD5 SHA-256 8815682 6047659 333133 176285 479810 5536046 1,46
  MD5 SHA-512 8815682 6047659 393703 139147 513992 5536046 1,46
  SHA-1 SHA-512 8815682 6047659 312747 174535 449811 5536046 1,46
  MD5 SHA-1 SHA-512 8815682 6047659 197262 239403 375259 5536046 1,46
4 MD5 4407841 3238922 473058 57484 530214 4675676 1,36
  SHA-1 4407841 3238922 493767 87433 576187 4675676 1,36
  SHA-256 4407841 3238922 380538 167992 542647 4675676 1,36
  SHA-512 4407841 3238922 447205 105566 550042 4675676 1,36
  MD5 SHA-1 4407841 3238922 374422 177318 545362 4675676 1,36
  MD5 SHA-256 4407841 3238922 334749 211298 535908 4675676 1,36
  MD5 SHA-512 4407841 3238922 378868 174867 547529 4675676 1,36
  SHA-1 SHA-512 4407841 3238922 317040 218977 525035 4675676 1,36
  MD5 SHA-1 SHA-512 4407841 3238922 258665 249268 487376 4675676 1,36
8 MD5 2203922 1728235 489233 44220 533006 3805488 1,28
  SHA-1 2203922 1728235 441905 112811 552007 3805488 1,28
  SHA-256 2203922 1728235 393392 154627 545127 3805488 1,28
  SHA-512 2203922 1728235 432876 110328 541555 3805488 1,28
  MD5 SHA-1 2203922 1728235 395499 154672 547342 3805488 1,28
  MD5 SHA-256 2203922 1728235 350791 198689 544660 3805488 1,28
  MD5 SHA-512 2203922 1728235 386206 159623 542725 3805488 1,28
  SHA-1 SHA-512 2203922 1728235 334705 211066 540665 3805488 1,28
  MD5 SHA-1 SHA-512 2203922 1728235 287632 246014 523194 3805488 1,28
16 MD5 1101963 882727 480980 53586 534426 3507752 1,25
  SHA-1 1101963 882727 448981 105784 552553 3507752 1,25
  SHA-256 1101963 882727 402071 153213 553208 3507752 1,25
  SHA-512 1101963 882727 434873 107238 541305 3507752 1,25
  MD5 SHA-1 1101963 882727 404958 152775 555720 3507752 1,25
  MD5 SHA-256 1101963 882727 347734 201271 545345 3507752 1,25
  MD5 SHA-512 1101963 882727 398452 154518 550866 3507752 1,25
  SHA-1 SHA-512 1101963 882727 345981 208492 550276 3507752 1,25
  MD5 SHA-1 SHA-512 1101963 882727 298733 248569 541414 3507752 1,25
32 MD5 550983 448885 491622 47141 538357 3267108 1,23
  SHA-1 550983 448885 467005 104319 569199 3267108 1,23
  SHA-256 550983 448885 397869 155779 550369 3267108 1,23
  SHA-512 550983 448885 439929 107897 546438 3267108 1,23
  MD5 SHA-1 550983 448885 392946 152850 542506 3267108 1,23
  MD5 SHA-256 550983 448885 357180 196940 548950 3267108 1,23
  MD5 SHA-512 550983 448885 398657 153645 550042 3267108 1,23
  SHA-1 SHA-512 550983 448885 357532 204913 555174 3267108 1,23
  MD5 SHA-1 SHA-512 550983 448885 310740 236376 537327 3267108 1,23
64 MD5 275492 228598 454490 46716 499372 3001188 1,21
  SHA-1 275492 228598 456413 104269 557903 3001188 1,21
  SHA-256 275492 228598 406350 148422 550369 3001188 1,21
  SHA-512 275492 228598 436965 106047 540650 3001188 1,21
  MD5 SHA-1 275492 228598 393965 151593 541524 3001188 1,21
  MD5 SHA-256 275492 228598 361369 196610 549932 3001188 1,21
  MD5 SHA-512 275492 228598 400109 150636 546437 3001188 1,21
  SHA-1 SHA-512 275492 228598 355471 203955 552116 3001188 1,21
  MD5 SHA-1 SHA-512 275492 228598 304482 244670 537265 3001188 1,21
128 MD5 137748 115952 404806 46820 450154 2789796 1,19
  SHA-1 137748 115952 384635 104283 485177 2789796 1,19
  SHA-256 137748 115952 354907 153518 503304 2789796 1,19
  SHA-512 137748 115952 397442 102798 496533 2789796 1,19
  MD5 SHA-1 137748 115952 362198 152918 510527 2789796 1,19
  MD5 SHA-256 137748 115952 313177 197008 501884 2789796 1,19
  MD5 SHA-512 137748 115952 348322 150890 495005 2789796 1,19
  SHA-1 SHA-512 137748 115952 316930 207674 514442 2789796 1,19
  MD5 SHA-1 SHA-512 137748 115952 268153 244016 495005 2789796 1,19
256 MD5 68876 59042 413452 47170 458095 2517284 1,17
  SHA-1 68876 59042 348106 106705 450560 2517284 1,17
  SHA-256 68876 59042 304536 148981 445318 2517284 1,17
  SHA-512 68876 59042 346736 105945 446738 2517284 1,17
  MD5 SHA-1 68876 59042 313820 153104 459842 2517284 1,17
  MD5 SHA-256 68876 59042 272617 198413 453898 2517284 1,17
  MD5 SHA-512 68876 59042 301490 152383 442892 2517284 1,17
  SHA-1 SHA-512 68876 59042 278589 208620 470809 2517284 1,17
  MD5 SHA-1 SHA-512 68876 59042 239228 241793 454600 2517284 1,17
512 MD5 34440 30308 396536 46107 437783 2115108 1,14
  SHA-1 34440 30308 341110 105937 436941 2115108 1,14
  SHA-256 34440 30308 317880 151842 443462 2115108 1,14
  SHA-512 34440 30308 342533 106774 437019 2115108 1,14
  MD5 SHA-1 34440 30308 316138 151811 443789 2115108 1,14
  MD5 SHA-256 34440 30308 278167 195980 430686 2115108 1,14
  MD5 SHA-512 34440 30308 318362 187799 352672 2115108 1,14
  SHA-1 SHA-512 34440 30308 271175 201109 427737 2115108 1,14
  MD5 SHA-1 SHA-512 34440 30308 256666 230340 425117 2115108 1,14
1024 MD5 17222 15876 349563 46545 390511 1377316 1,08
  SHA-1 17222 15877 332112 105328 407207 1377316 1,08
  SHA-256 17222 15877 310524 142464 142464 1377316 1,08
  SHA-512 17222 15877 343804 104690 413978 1377316 1,08
  MD5 SHA-1 17222 15877 343873 141015 414524 1377316 1,08
  MD5 SHA-256 17222 15877 303678 179529 389196 1377316 1,08
  MD5 SHA-512 17222 15877 330175 144149 406771 1377316 1,08
  SHA-1 SHA-512 17222 15877 321123 186738 406989 1377316 1,08
  MD5 SHA-1 SHA-512 17222 15877 294870 214378 388534 1377316 1,08

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

Сводная таблица полученных данных :

 

BS BR BD TR TD TA SO K
кб     c c c мб  
0,5 35262728 19454436 291 179 338 7719 1,81
1 17631364 11125573 296 155 377 6353 1,58
2 8815682 6047659 379 144 502 5406 1,46
4 4407841 3238922 384 161 538 4566 1,36
8 2203922 1728235 390 155 541 3716 1,28
16 1101963 882727 396 154 547 3426 1,25
32 550983 448885 401 151 549 3191 1,23
64 275492 228598 397 150 542 2931 1,21
128 137748 115952 350 151 495 2724 1,19
256 68876 59042 313 151 454 2458 1,17
512 34440 30308 315 153 426 2066 1,14
1024 17222 15877 326 141 373 1345 1,08

 

   

По данному графику можно увидеть две важные зависимости : зависимость коэффицента дедупликации от размера блока и время выполнения дедупликации от размера блока.

Мы можем наблюдать уменьшение коэффицента дедупликации с увеличением размера блока. Данная зависимость достаточно очевидна.
По графику времени выполнения от размера блока видно, что в момент скачка ( размер блока 8 кб) настает момент когда время вычисления хеш-функции  увеличивается быстрее, чем уменьшается количество блоков. 


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

Причина проседания графика времени выполнения обьяснена выше.
 

Выводы :

Наиболее благоприятный интервал выбора блока : 512 байт — 2 килобайта . Данный интервал выбран ввиду наиболее благоприятного отношения коэффицента дедупликации и времени выполнения процесса, обеспечивающего эффективную экономию свободного пространства за приемлемое время.