An efficient empirical method for file-level deduplication

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
1. Verfasser:	Pigovsky, Yu.R.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2019
Schlagworte:	UDC 004.023
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/680
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-680
record_format	ojs
resource_txt_mv	ppisoftskievua/67/b83532f6e7b7d879f059f9bc9a47d967.pdf
spelling	pp_isofts_kiev_ua-article-6802025-02-12T23:28:28Z An efficient empirical method for file-level deduplication Ефективний емпіричний метод дедублікації на файловому рівні Pigovsky, Yu.R. UDC 004.023 УДК 004.023 Вдосконалено метод пошуку дублікатів контенту у файловій системі на основі емпіричного правила доцільності хешування. Правило створено на основі побудови математичних сподівань тривалості процедур хешування і попарного порівняння файлів. Проведено експериментальні дослідження методу.Prombles in programming 2014; 4: 26-32 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2019-03-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/680 PROBLEMS IN PROGRAMMING; No 4 (2014); 26-32 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2014); 26-32 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2014); 26-32 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/680/732 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-02-12T23:28:28Z
collection	OJS
language	Ukrainian
topic	UDC 004.023
spellingShingle	UDC 004.023 Pigovsky, Yu.R. An efficient empirical method for file-level deduplication
topic_facet	UDC 004.023 УДК 004.023
format	Article
author	Pigovsky, Yu.R.
author_facet	Pigovsky, Yu.R.
author_sort	Pigovsky, Yu.R.
title	An efficient empirical method for file-level deduplication
title_short	An efficient empirical method for file-level deduplication
title_full	An efficient empirical method for file-level deduplication
title_fullStr	An efficient empirical method for file-level deduplication
title_full_unstemmed	An efficient empirical method for file-level deduplication
title_sort	efficient empirical method for file-level deduplication
title_alt	Ефективний емпіричний метод дедублікації на файловому рівні
description
publisher	PROBLEMS IN PROGRAMMING
publishDate	2019
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/680
work_keys_str_mv	AT pigovskyyur anefficientempiricalmethodforfileleveldeduplication AT pigovskyyur efektivnijempíričnijmetoddedublíkacíínafajlovomurívní AT pigovskyyur efficientempiricalmethodforfileleveldeduplication
first_indexed	2025-07-17T09:42:32Z
last_indexed	2025-07-17T09:42:32Z
_version_	1850413138716917760
fulltext	Інструментальні засоби та середовища програмування © Ю.Р. Піговський, 2014 26 ISSN 1727-4907. Проблеми програмування. 2014. № 4 УДК 004.023 Ю.Р. Піговський ЕФЕКТИВНИЙ ЕМПІРИЧНИЙ МЕТОД ДЕДУБЛІКАЦІЇ НА ФАЙЛОВОМУ РІВНІ Вдосконалено метод пошуку дублікатів контенту у файловій системі на основі емпіричного правила доцільності хешування. Правило створено на основі побудови математичних сподівань тривалості про- цедур хешування і попарного порівняння файлів. Проведено експериментальні дослідження методу. Вступ Дедублікація – це процес усунення дублікатних копій даних. Коли повторю- ваність (реплікованість) даних є доволі високою, що притаманне серверам резерв- ного копіювання, образам віртуальних машин і репозиторіям сирцевих (source) кодів, дедублікація може зменшити витра- ти простору і збільшити швидкість оброб- ки даних не те, що на проценти, а навіть на порядки [1]. Заощадження простору є очевид- ним наслідком дедублікації; підвищення ж швидкості відбувається внаслідок уник- нення операцій запису на диск при збере- женні дубльованих даних, а також змен- шеного обсягу задіяної віртуальної пам’яті за рахунок спільного використання її сто- рінок багатьма застосунками. В загальному випадку, дедубліка- ція може розглядатися на одному з трьох рівнів: файловому, блоковому або байто- вому. Дедублікація перших двох рівнів має практичний зміст, тоді як недоціль- ність дедублікації на байтовому рівні об- грунтовано в [1]. Відомим розв’язком задачі дедуб- лікації на файловому рівні є утиліта А. Лопеза fdupes [2], що входить до складу GNU Coreutils. Проте алгоритм її роботи недостатньо ефективний, бо обчилює MD5 хеш кожного файла безумовно, не врахо- вуючи доцільності такого обчислення для конкрентного співвідношення швидкості доступу до файлів та їхнього обcягу. На блоковому рівні задачу дедуб- лікації розв’язано Дж. Бонвіком [1] в мо- дулі файлової системи ZFS. Дедублікація в ZFS має велику кількість допустимих ком- бінацій параметрів, зокрема: хешування алгоритмом SHA256, проста побайтова верифікація або хешування алгоритмом Флетчера (fletcher4) з побайтовою верифі- кацією. При цьому існує проблема у ви- борі найефективніших налаштувань, ос- кільки на деяких даних хешування алго- ритмом SHA256 може відбуватися повіль- ніше ніж комбінований підхід хешування Флетчера (fletcher4) з побайтовою верифі- кацією і навпаки. Дану статтю присвячено підвищен- ню ефективності процедури дедублікації на файловому рівні шляхом побудови те- оретичного правила, що дозволило б ви- значити при яких співвідношеннях швид- кості доступу до файлів та їхнього обсягу доцільно проводити хешування, а при яких – ні. Ефективність теоретичного прави- ла буде перевірено експериментально. Правило доцільності хешування На сторінці вбудованої допомоги Linux (manpage) утиліту А. Лопеза описано так: “Searches the given path for duplicate files. Such files are found by comparing file sizes and MD5 signatures, followed by a byte-by-byte comparison” (“Шукає дубліка- ти файлів у вказаній папці. Такі файли знаходяться шляхом порівняння розміру файлів та їхніх MD5 дайджестів, після чо- го слідує їх побайтове порівняння” [2]. Недоліком такого алгоритму є те, що ціл- ком недоцільно обробляти незначну кіль- кість файлів великого розміру хеш- функцією MD5 [3] перед їх попарним по- рівнянням. Обгрунтуємо це твердження теоретично. Нехай LN – кількість файлів, кожен з яких має розмір L байт. Хеш-функція – Інструментальні засоби та середовища програмування 27 це функція, що приймає на вхід рядок змінної довжини, який називають вхідним образом (контентом), а повертає рядок фіксованої (звичайно меншої) довжини – хеш (дайджест). Тривалість роботи цієї функції лінійно залежить від кількості файлів та їхньої довжини, тому її склад- ність )( LNO L . Збіг значень дайджеста є необхідною, проте недостатньою умовою еквівалентності контенту [3]. Обчислення дайджестів дає можли- вість розбити множину з LN файлів на LK груп з однаковим дайджестом (далі – дайджест-групи), в кожній з яких буде kLn , файлів, kLKkL nN L ,1  . Розбиття на дайджест-групи дасть змогу зекономити час на пошук дублікатів, за рахунок того, що тривалість хешування файлів разом з тривалістю їх попарного порівняння в LK групах може бути мен- шою за тривалість попарного порівняння всіх LN файлів. Пояснимо це на екстремальному випадку, коли більшість файлів відрізня- ється вже першим блоком. Пошук дубліка- тів методом попарного порівняння в тако- му випадку буде особливо ефективний. Тривалість процедури попарного порів- няння в основному визначатиметься трива- лістю відкриття-закриття файлу prt , тобто підготовки внутрішніх структур даних яд- ра ОС при обслуговуванні файлової сис- теми. Процедура попарного порівняння являє собою два цикли, вкладені один в другий, а тому має квадратичну складність )( 2nO від кількості файлів n . Навіть у таких, найсприятливіших для попарного порівняння умовах, може виявитися, що складність попарного порі- вняння великої кількості файлів )( 2 LNO значно перевищить сумарну складність хешування )( LNO L і їхнього попарного порівняння у малих дайджест-групах  2 ,1 kLKk nO L . Крім того, попарне порі- вняння буде проводитися не у всіх групах, а лише в тих, до яких ввійшло два і більше файлів .= , 2 ,1 , LkL n LKk Nn kL     (1) Далі наведені оцінки складності ал- горитмів будуть уточнені. При 2=LN хешування, очевидно, марне, бо коли ці два файли матимуть різні дайджести, то їх хешування не відбудеться швидше ніж побайтове порівняння їхнього вмісту, навіть у найгіршому випадку, де вони відрізняються лише останнім байтом. Коли ж дайджести співпадуть, то до часу хешування додасться ще й час порівняння вмісту цієї пари файлів. При 3LN хешування, в деяких випадках, може бути і доцільним. Спро- буємо знайти правило, що дозволить ска- зати чи для заданої кількості файлів LN та довжини L доцільно проводити хешу- вання. Нехай ),( LnTC – тривалість попар- ного порівняння n файлів, кожен з яких має довжину L байтів. Для її оцінювання проаналізуємо алгоритм попарного порів- няння файлів. 1. 0i 2. Поки 1< ni робити 3. Якщо FILES[ i ] = , то крок 24 4. DUPLES  5. 1 ij 6. fd1  open(FILES[ i ]) 7. Поки nj < робити 8. Якщо FILES[ j ] = , то крок 18 9. fd2  open(FILES[ j ]) 10. Якщо cmpContent(fd1, fd2), то 11. Якщо DUPLES = , то 12. DUPLES  FILES[ i ] 13. Кінець якщо 14. DUPLES  FILES[ j ] 15. FILES[ j ]  16. Кінець якщо 17. close (fd2) 18. 1 jj 19. Кінець поки 20. close (fd1) 21. Якщо DUPLES  , то 22. ALLDUPLES  DUPLES Інструментальні засоби та середовища програмування 28 23. Кінець якщо 24. 1 ii 25. Кінець поки. При описі алгоритму використано нотацію Д. Кнута [4], де символ “Λ” озна- чає порожнє посилання (порожній список), символ “” означає занесення елемента, що знаходиться праворуч у список чи стек, що знаходиться ліворуч. Операції “open” та “close” призначе- ні для відкриття і закриття дескрипторів файлів (fd1, fd2), сума тривалостей їхнього виконання складає величину prt . Нехай FILES – лінійний список шляхів до n файлів однакового розміру L , ALLDUPLES – список стеків з шляхами до файлів-дублікатів. На початку роботи він порожній: ALLDUPLES=Λ. На кожній ітерації внутрішнього циклу (кроки 7–19) виконується наповнен- ня локального стеку DUPLES дублікатами і-го файла. Після завершення цього циклу, непорожній локальний стек DUPLES до- бавляється у результуючий список дублі- катів ALLDUPLES. Тривалість роботи ),( LnTC алгори- тму залежить від того, наскільки довго триватиме виконання кроку 10 на кожній ітерації попарного порівняння. На цьому кроці булева функція cmpContent(fd1, fd2), в найпростішому випадку, виконує ліній- ний пошук відмінності контенту відкри- тих файлів fd1 та fd2 і зупиняється при знаходженні відмінного байта, повертаю- чи false, або не знаходить відмінності і повертає true. Зупинка може відбутися на будь-якому від першого до останнього з L байтів. Припустимо, що номер першого байта, який відрізняє контенти файлів fd1 та fd2 є дискретною випадковою величи- ною m , що набуває значень у діапазоні Lm 1 , тоді ),( LnTC можна оцінити так: =),( LnTC )2()(1)(= rprpr tmtnMtn  , (2) де 1)( n – кількість разів, яку виконуєть- ся крок 6, prt – тривалість приготувань, тобто середній час, що потрібен на відк- риття і закриття одного файла, )(nM – кількість разів, яку виконується крок 10, m – випадковий номер першого байта, що відрізняє контенти файлів fd1 та fd2, rt – середня тривалість зчитування одного бай- та з жорсткого чи мережевого диска (тео- ретичний параметр, оскільки справжні ре- алізації алгоритму працюють з блоками). Слід зауважити, що у випадку еквівалент- ності контентів маємо Lm = . Кількість )(nM разів, яку вико- нується крок 10 можна оцінити як суму арифметичної прогресії  12)(1)(=)( nnnM .1)( 2 = n n (3) Припустимо, що номер першого байта m , що відрізняє контенти файлів fd1 та fd2 є рівномірно-розподіленою в діапа- зоні Lm 1 випадковою величиною з матсподіванням   2/1= Lm  . Підставив- ши цю величину та (3) в (2) отримаємо таку оцінку математичного сподівання тривалості ),( LnTC виконання алгоритму:  prC tnLnT 1)(=),(  .)(1 2 1)( rpr tLt nn    (4) З останнього співвідношення можна стверджувати, що алгоритм попарного порівняння n файлів має складність  ,)(2 rpr LttnO  де n – кількість файлів, L – їхній осяг. Беручи до уваги співвідношення (4) можна запропонувати наступне правило: хешування проводити доцільно, коли оці- нка його тривалості менша за математичне сподівання тривалості попарного порів- няння    ,інакше,ні );,(<),(так, =),( LnTLnT LnH CH (5) де ),( LnTH – тривалість обробки n файлів обсягом L байт деякою хеш-функцією (хешування). Інструментальні засоби та середовища програмування 29 Відомо велику кількість функцій хешування. З перспективи поставленої у статті задачі, їхніми найважливішими ха- рактеристиками є швидкість обчислення та імовірність колізій. Розглянемо кілька альтернативних функцій хешування на предмет того, котра з них краще підходить для розв’язання поставленої у статті задачі. Хеш-функція SHA-1 має широке прикладне застосування для задачі індек- сування версій файла в сучасних системах контролю версій, таких як Git, Mercurial та Monotone [5]. Вона відзначається надзви- чайно малою імовірністю колізії, завдяки досить великій довжині дайджеста (20 байт) і лавиноподібності його зміни при незначній зміні контенту. Проте має скла- дний алгоритм роботи. Іншим варіантом є функція хешу- вання на основі алгоритму обгляду нелі- нійної таблиці (NTL – Nonlinear Table Lookup). Вона відзначається високою швидкодією і простотою реалізації, проте, у порівнянні з SHA-1, вразливіша до імо- вірних колізій [3]. Хеш-функція MD5, використана А. Лопезом [2], посідає проміжне місце між NTL та SHA-1 за швидкодією та імо- вірністю колізії. Вона не настільки швид- кісна як NTL, але й стійкіша, у порівнянні з ним, до колізій, хоча й поступається на- дійністю алгоритму SHA. Усі ці алгоритми мають лінійну складність, тому тривалість їхньої роботи ),( LnTH лінійно залежить від обсягу об- роблюваних ними файлів chphH tnMtLtnLnT )()(=),(  , (6) де n – кількість файлів довжиною L бай- тів, pht – середній час, що витрачається на підготовку до хешування незалежно від об'єму оброблюваного файлу, ht – час, що в середньому припадає на хешування од- ного байту, ct – тривалість попарного по- рівняння дайджестів для визначення до якої дайджест-групи віднести щойно про- хешований файл. Оскільки операції попарного порів- няння дайджестів виконуються в операти- вній пам’яті комп’ютера, то час ct є насті- льки мізерним, що складність алгоритму хешування можна оцінити як )( hLtnO  . В наступному розділі буде проведе- но експериментальне дослідження побудо- ваного правила. Бенчмаркінг введення-виведення Чисельні експерименти проведено на жорсткому диску з файловою системою NTFS, корисний обсяг якого складає 465 Гб, 234 Гб з яких використовуються 634 589 файлами (загальним обсягом 226 Гб) в 95 189 папках. Пошук файлів на жорсткому диску виявив 46 150 груп файлів однакового ро- зміру. Загальна кількість файлів, що ство- рюють групи з двох і більше файлів, згідно з формулою (1), складає 368 599= , тобто 94% від загальної їх кількості. Найчисельнішою групою файлів однакового розміру виявилася група з 5110 файлів, що мають розмір 8 Кб (8192 байт). Потім виявлено 4 678 порожніх файлів. Присутність такої кількості порожніх фай- лів можна пояснити тим, що деяке програ- мне забезпечення використовує порожні файли, як прапорці, що керують включен- ням або виключенням тих чи інших функ- цій ПЗ (наприклад, це характерно для де- яких CMS), користувачі-розробники часто створюють порожні файли-стаби, які пла- нують наповнити вмістом згодом, а також тим, що антивірусні програми усувають код вірусів з виконуваних файлів, після чого вони перетворюються на порожні іменовані файли. Серед лідерів за чисельністю також можна назвати групи з 3 784 файлів дов- жиною 402 байти, 3 186 – довжиною 53 байти та 2 892 – довжиною 2 байти. На початку дослідження проана- лізуємо, яку кількість з виявлених 46 150 груп файлів однакового розміру слід обро- бити хеш-функцією. Для цього потрібно обчислити для кожної групи вираз (5) за допомогою формул (4) та (6). Таке обчис- лення можливе лише за умови відомості коефіцієнтів pht , prt , ht , rt та ct . Їх можна отримати за допомогою так зва- Інструментальні засоби та середовища програмування 30 ного бенчмаркінгу (Benchmarking) або на основі емпіричних міркувань. Процедури бенчмаркінгу були по- будовані таким чином, щоб можна було оцінити можливість наближення тривало- сті процедур зчитування інформації та хе- шування лінійними функціями. Тривалість хешування вимірюва- лася простим фіксуванням різниці часу між початком і завершенням процедури хешування. Як вже було сказано раніше, тривалість ct попарного порівняння дай- джестів для визначення до якої дайджест- групи віднести щойно прохешований файл – дуже незначна, оскільки таке порі- вняння не вимагає роботи із зовнішніми пристроями пам’яті, а всі порівняння про- водяться безпосередньо в оперативній пам’яті. Вимірювання такої незначної три- валості дуже утруднене і може містити значні метрологічні похибки, тому у фор- мулах покладемо 0=ct , але неявно вклю- чатимемо її при оцінці pht . Тривалість зчитування інформації вимірювалася при виконанні процедури попарного порівняння до появи першої відмінності між файлами. Таким чином нагромаджувалися дані про тривалість зчитування різної кількості інформації од- разу з двох файлів, що слід врахувати при аналізі результатів. Підсумкова тривалість при співпа- дінні обсягу прочитаної інформації усере- днювалася за формулою   2/= 1,,1,   kLkLkL ttt , де kLt , – поточна оцінка тривалості зчиту- вання L байт інформації, 1, kLt – попере- дня оцінка цієї тривалості. Результати бенчмаркінгу, на рис. 1, показують, що тривалість підготовки до роботи з файлами 210 prph tt мілісе- кунд на сім порядків перевищує тривалість обробки одного байта як у процедурі зчи- тування, так і в процедурі хешування 510 rh tt мс. Це пов'язано з тим, що при відкритті файла на жорсткому диску відбувається створення та ініціалізація внутрішніх структур даних ОС для де- скрипторів, створення і наповнення буфе- рів введення-виведення, а при відкритті файла з мережевого файлового сховища відбувається встановлення з’єднання, ви- конання так званого протоколу рукостис- кання, аутентифікації та авторизації. Вод- ночас rt включає лише послідовне прочи- тання даних з носія або мережевого ресур- су після виконання всіх підготовчих дій, що, зазвичай, оптимізується алгоритмами випереджуючого читання в контролерах сучасних жорстких дисків, кешування в ОС та протоколах мережевої взаємодії. a б Рис. 1. Спостереження тривалості зчиту- вання (а) та хешування (б) файлів різного обсягу При огляді графіків помітні такі два явища: середня тривалість хешування од- ного байта 5102.40= ht мс. виявилася, хоча і несуттєво, але меншою від тривало- сті простого зчитування 5102.79= rt мс., оскільки одночасне читання з двох різних Інструментальні засоби та середовища програмування 31 файлів утруднює роботу алгоритму випе- реджаючого читання, що працює безпере- шкодно при хешуванні одного файлу. Від- носна дисперсія спостережень тривалості зчитування файлів більша за відносну дис- персію тривалості хешування. Ці явища пояснюються тим, що у випадку з хешу- ванням програма обробляє на кожній іте- рації єдиний, причому, завжди інший файл, що не дозволяє ОС застосувати кеш, тоді як, у випадку з попарним порівнян- ням, дисперсія вниз від лінії тренду озна- чає зменшення тривалості зчитування за рахунок дії кешу ОС для файлів, що відк- риваються вже не вперше. Дисперсія вгору від лінії тренду пояснюється фрагментаці- єю файлової системи та затримками, що спричинені діями інших задач ОС. Отримані оцінки бенчмаркінгу уз- годжуються з даними, що наведені в літе- ратурі, зокрема, в [6], де розроблено та досліджено ПЗ Parabench оцінювання про- дуктивності зберігаючих пристроїв та ме- реж (Storage Area Network) шляхом імітації функціонування застосунків, що зчитують і зберігають великі обсяги даних. Експериментальні дослідження Експерименти показали, що пошук дублікатів серед 634 589 файлів алгорит- мом побайтового порівняння без хешу- вання на описаному в попередньому роз- ділі жорсткому диску триває 16 862.3 сек. (4 год. 41 хв.), тривалість роботи алгори- тму хешування-побайтового порівняння не надто відрізняється – 16 405 сек. (4 год. 33 хв.). Проте аналіз в розрізі груп файлів однакового розміру показав теоретичну можливість скоротити цей час до 14 816 сек., тобто на 12.12 % щодо алгори- тму без хешування чи 9.69 % щодо алгори- тму з хешуванням. Такий незначний, на перший пог- ляд, виграш часу, може обернутися суттє- вим виграшем при зростанні обсягу, кіль- кості файлів і зберігальних пристроїв у мережах Storage Area Networks. На графіку рис. 2 порівняно ефек- тивність роботи двох алгоритмів: без хе- шування (пунктирна крива) та з хешуван- ням (суцільна крива). Логарифмічна вісь ординат показує кількість сек., що знадо- билася на знаходження дублікатів серед тієї кількості файлів, що подана віссю абс- цис. Для групи восьмикілобайтових (8192 байт) файлів, що налічує максимальну кі- лькість з 5110 файлів (останні точки за віссю абсцис) помітно, що тривалість по- шуку з хешуванням-побайтовим порівнян- ням є на порядок меншою від тривалості пошуку простим побайтовим порівнянням (60.3 сек. проти 621.0 сек.). Така разюча відмінність тривалості свідчить про низьку частоту колізій у даній групі, а отже вели- ку ефективність алгоритму хешування в цьому випадку. Рис. 2. Порівняння ефективності роботи алгоритмів без хешування та з хешуванням Використовуючи отримані набли- ження коефіцієнтів, розрахунок виразу (5) за допомогою формул (4) та (6), показав, що хешування доцільно проводити лише для 5 373 груп файлів однакового розміру, тобто лише для 12 % від загальної кількос- ті з 46 150 груп. При цьому виявилося та- кож, що хешування доцільно проводити вже для груп, у яких кількість файлів пе- ревищує 20. Результати свідчать про те, що де- дублікація із застосуванням співвідношен- ня (5) триває 16 460 сек., що дає несуттє- вий виграш швидкодії у порівнянні з алго- ритмом без хешування і навіть дещо про- грає у швидкодії алгоритму з хешуванням. З метою покращення результатів було узагальнено співвідношення (5) шля- хом введення емпіричного коефіцієнту  : Інструментальні засоби та середовища програмування 32    .інакше,ні );,(<),(,так =),( LnTLnT LnH CH   (7) Роль коефіцієнту  можна поясни- ти як засіб урівноваження припущень що- до розподілу випадкової величини позиції відмінності при попарному порівнянні файлів. При 0.0= алгоритм зведеться до алгоритму без хешування, при 1.0= матимемо класичну версію (5), а для де- якого достатньо великого 1.0> алго- ритм зведеться до алгоритму із безумов- ним хешуванням. В ході експериментів виявилося, що останній випадок настає вже при 1.8> . На рис. 3 показано тривалість ро- боти узагальненого алгоритму з співвід- ношенням (7) для різних значень емпірич- ного коефіцієнту в діапазоні 2.00.0  . Рис. 3. Тривалість роботи узагальненого алгоритму для 2.00.0  З рисунку можна зробити висновок, що мінімальна тривалість дедублікації до- сягається при 0.1= і складає 15 950 сек., що на 3 % швидше від алгоритму із безу- мовним хешуванням і на 5 % швидше від алгоритму без хешування. Висновки Створено правило доцільності ви- конання процедури хешування в залежнос- ті від кількості, обсягу та швидкості дос- тупу до файлів у задачі пошуку дублікатів контенту. Правило створено на основі теоре- тичних досліджень математичного споді- вання тривалості процедур хешування та попарного порівняння. Розроблене правило дає змогу знайти ті групи файлів однакового розмі- ру, в котрих доцільно проводити хешуван- ня з метою підвищення ефективності по- шуку дублікатів на файловому рівні. Де- дублікація розробленим методом триває 15 950 сек., що на 3 % швидше від алгори- тму із безумовним хешуванням і на 5 % швидше від алгоритму без хешування. У наступних дослідженнях плану- ється покращити розроблений метод з ме- тою збільшення виграшу швидкодії і по- ширити область його застосування на за- дачу дедублікації на блоковому рівні. 1. Bonwick J. ZFS Deduplication. – 2009 [Еле- ктронний ресурс]. – Режим доступу: https://blogs.oracle.com/bonwick/entry/zfs_de dup 2. Lopez A. fdupes(1) – Linux man page [Елек- тронний ресурс]. – Режим доступу: http://linux.die.net/man/1/fdupes 3. Шеховцов В.А. Операційні системи // За- хист інформації в операційних системах. – К.: Видавнича група BHV, 2005. – Розд. 18. – С. 471–472. 4. Кнут Д.Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ.: Уч. пос. – М.: Издательский дом "Вильямс", 2000. – 720 с. 5. Chacon S. Pro Git. – Apress, 2009. 6. Mordvinova O. I/O Benchmarking of Data Intensive Applications / Olga Mordvinova, Thomas Ludwig, Christian Bartholomä // Проблеми програмування. – К.; 2010. – N 2–3. Спец. випуск. – С. 107–115. Одержано 16.05.2014 Про автора: Піговський Юрій Романович, доцент кафедри комп’ютерних наук, кандидат технічних наук, Місце роботи автора: Тернопільський національний економічний університет, 46001, Тернопіль, вул. Чехова, 8. Тел.: 55 0971. Е-mail: pigovsky@gmail.com mailto:rgrygoryan@gmail.com

An efficient empirical method for file-level deduplication

Institution

Ähnliche Einträge