Автор Тема: somepopularfilehostingservice.com  (Прочетена 3766 пъти)

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
somepopularfilehostingservice.com
« -: Aug 07, 2009, 14:00 »
Първо, такъв домейн и такава услуга не същестуват, името е избрано съвсем произволно.

Това е една задачка за губене на свободно време, дърлене, малко математика и такива разни работи.

Значи идеята е следната:

somepopularfilehostingservice.com е популярна услуга за качване на файлове, нещо като data.bg, само че платено, бързо и сигурно. Да речем че услугата има 1 милион потребителя като всеки потребител е качил средно по 100 файла, така общият брой на качените файлове е 100 милиона. Файловете са с различна големина и различно съдържание разбира се.

Всеки ден на тези 100 милиона файла се прави бекъп. Сега разбира се, копирането на 100 милиона файла е ужасно бавна и пипкава процедура, ужасно ресурсоемка (представете си как терабайти данни се компресират, пращат по мрежата и се записват на отдалечения storage). Това твърде вероятно ще отнеме повече от ден и съответно идеята с всекидневните бекъпи става невъзможна.

По този повод, софтуера за бекъпване е малко по-интелигентен - той си има една хубава база с MD5 суми на качените файлове - после просто проверява MD5 сумата на всеки файл и ако има разлика си ъпдейтва базата и праща по мрежата въпросния файл на отдалечената машина. Въпреки че md5sum на всичките 100 милиона файлове е бавна операция, то компресирането на всички файлове и копирането им по мрежата е доста по-бавна и затормозяваща, така че дневния бекъп евентуално по този начин става възможен. С цел базата да не става гигантска, в нея се пазят само хешове, без имена на файлове.  Тоза защото един MD5 хеш е 16 байта, следователно 100 милиона хеша са гигабайт и половина. Ако добавим към хеша и път и име на файла, базата ще стане в пъти по-голяма, ще стане проблем цялата да се зареди в паметта и да се обхожда, а постоянното й четене от диска е доста бавно, значи по-добре само хешове да се пазят. Възможното множество хешове е 2^128 - т.е 4 милиарда по 4 милиарда по 4 милиарда по 4 милиарда - безумно голяма стойност на фона на която 100-те милиона файла са супер малка бройка и дефакто се очаква колизии на практика да не се случват.

Ако все пак се случи колизия ще бъде леко гадно - реално погледнато ще се бекъпва само първият срещнат файл с такава хеш сума, вторият евентуално - не. Следвайки законите на Мърфи, това ще се окаже супер-хипер-мега важния файл на някой кисел костюмиран пърдялник.

Та задачата е следната - каква е вероятността при 100 милиона файла, да се намери каквато и да било двойка файлове с еднаква хеш сума?

П.П. нито гномския, нито на КДЕ калкулатора могат да смятат с нужната прецизност, за да ви изкарат правилния отговор. Ако наистина искате да ви бъде сметнато, препоръчвам SpeedCrunch - доста добър калкулатор е и го има в хранилищата на по-разпространените дистрибуции (поне със сигурност го има в тези на дебиан и в тези на федора.

Всъщност правилният отговор не е толкова важен, той и без това е едно дъъъълго число, по-интересна е самата сметка :)
Активен

"Knowledge is power" - France is Bacon

foxb

  • Напреднали
  • *****
  • Публикации: 175
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #1 -: Aug 07, 2009, 15:05 »
Първо при такива обеми традиционното резервно копиране, което се стартира през нощта е невъзможно и това ще ти го каже всеки, който се е занимавал с това....

Тук се използват съвсем други системи тип CDP а също и оборудване, което може да издържи такова натоварване - например EMC.

Колкото до колизиите те не само са възможни, но и реални не само при md5 но и дори при sha.

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #2 -: Aug 07, 2009, 15:32 »
Това как се прави бекъпа има малко отношение, идеята е да се създаде някаква по-увлекална предистория на задачата, защото иначе нещо от сорта на "за множеството H от 100 милиона стойности X намерете вероятността p(H) за която имаме f(Xi)=f(Xj) (1<=i<=100.000.000) (1<=j<=100.000.000) при положение че (0<=f(z)<=2^128)" звучи доста сухо.

Колизии има за всяка една хеш-функция и това е повече от нормално. Множеството от стойности е безкрайно, докато множеството от стойности на хеш функциите е ограничено, да речем 2^128 за MD5 или 2^160 за SHA, при това положение винаги ще има x1 и x2 за които f(x1) = f(x2)

« Последна редакция: Aug 07, 2009, 16:16 от gat3way »
Активен

"Knowledge is power" - France is Bacon

ANTIADMIN

  • Напреднали
  • *****
  • Публикации: 660
  • Distribution: Windows XP Pro latest updates
  • ANTIADMIN
    • Профил
Re: somepopularfilehostingservice.com
« Отговор #3 -: Aug 08, 2009, 11:30 »
//off
Тук за дата.бг ли става въпрос, щото след последния ъпгрейт техният портал и нещо такова :)
Активен

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #4 -: Aug 08, 2009, 14:47 »
А, не знам, никога не съм им бил потребител, само разбрах че направили тегленето платено или нещо такова.

А иначе, задачата си е математика, доукрасяването й с такива неща си е въпрос на интерпретация. Примерно друг вариант е "имаш една mysql таблица със 100 милиона реда и едно поле (не е UNIQUE) което пази хеш от някакъв уникален стринг. Каква е вероятността два реда в таблицата да имат полета с еднакъв хеш?"

И такива работи.
Активен

"Knowledge is power" - France is Bacon

arch

  • Напреднали
  • *****
  • Публикации: 78
    • Профил
Re: somepopularfilehostingservice.com
« Отговор #5 -: Aug 08, 2009, 19:27 »
@gat3way интересен аватар ;)
Активен

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #6 -: Aug 08, 2009, 20:28 »
Аватарът е да плаши тези дето развиват конспирационни теории :)

Пфу, всички ли ви мързи да смятате бе, не ви е срам :)
Активен

"Knowledge is power" - France is Bacon

m0rph

  • Напреднали
  • *****
  • Публикации: 271
    • Профил
Re: somepopularfilehostingservice.com
« Отговор #7 -: Aug 08, 2009, 20:45 »
Лято е. Време за  [_]3, жени и море.  ;)

go_fire

  • Global Moderator
  • Напреднали
  • *****
  • Публикации: 6997
  • Distribution: Дебиан Сид
  • Window Manager: ROX-Desktop / е17
  • кашик с гранатомет в танково поделение
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #8 -: Aug 08, 2009, 21:29 »
Аз съм пълен некъдърник- счетоводител и съм учил само две висши математики за това не мога да го сметна. Обаждам се, защото и аз се интересувам, какво аджеба има на въпросния аватар ??? Аз на абсолютно нищо не мога да го оприлича, а разряда му е толкова малък, че увеличено е още по-неразбираемо.
Активен

В $por4e2 e истината  ;)

***

Aко даваха стипендия за най-глупави, щях да съм човека с най-много Mини Kупъри

***

Reborn since 1998 || 15.09.2007 totally М$ free && conscience clear

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #9 -: Aug 08, 2009, 21:58 »
Това е базата на архилошите.

Добре де, по-проста задача. Намирате се в една стая с още 22 човека. Каква е вероятността двама души в стаята да имат рожден ден на една и съща дата? Ако не ви се правят сметки, дайте поне някакво предположение :)

После ще ви кажа защо точно питам, просто искам да проверя едно твърдение.

Активен

"Knowledge is power" - France is Bacon

go_fire

  • Global Moderator
  • Напреднали
  • *****
  • Публикации: 6997
  • Distribution: Дебиан Сид
  • Window Manager: ROX-Desktop / е17
  • кашик с гранатомет в танково поделение
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #10 -: Aug 08, 2009, 22:02 »
Старо като света, всеки знае отговора, макар поне аз да не мога да го сметна, а го има и в страницата на едно хакерче Мильо, дет все дири бъгове на Дебилиан  [_]3
Активен

В $por4e2 e истината  ;)

***

Aко даваха стипендия за най-глупави, щях да съм човека с най-много Mини Kупъри

***

Reborn since 1998 || 15.09.2007 totally М$ free && conscience clear

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: somepopularfilehostingservice.com
« Отговор #11 -: Aug 08, 2009, 22:11 »
Шът сега за това :) Сериозно искам да разбера наистина хората дали в повечето случаи мислят да го смятат като 22 пъти вероятността два рождени дни да се засекат, щото са го кръстили "парадокс", трябва да има защо . Не мога да разбера по каква логика става това. Питах няколко човека, наистина имаше такива дето тръгнаха да го смятат така, ама бяха малко.
Активен

"Knowledge is power" - France is Bacon

Djuroff

  • Напреднали
  • *****
  • Публикации: 80
  • Distribution: Fedora 11
  • Window Manager: Gnome,KDE
    • Профил
Re: somepopularfilehostingservice.com
« Отговор #12 -: Aug 09, 2009, 04:18 »
Ха gat3way  яка  задчка ще ми е интересно да разбера имали  решение задачката. :)
Активен

senser

  • Напреднали
  • *****
  • Публикации: 1328
    • Профил
Re: somepopularfilehostingservice.com
« Отговор #13 -: Aug 09, 2009, 07:00 »
Намирате се в една стая с още 22 човека. Каква е вероятността двама души в стаята да имат рожден ден на една и съща дата?
0.003467818=(22*21)/(365*365)
това е без отчитане на високосни години  >:D
също така трябва да се уточни какво се разбира под "една и съща дата" - ако е ден.месец.година ............ няма да стане :)
« Последна редакция: Aug 09, 2009, 08:57 от senser »
Активен

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: somepopularfilehostingservice.com
« Отговор #14 -: Aug 09, 2009, 09:51 »
Това е базата на архилошите.

Добре де, по-проста задача. Намирате се в една стая с още 22 човека. Каква е вероятността двама души в стаята да имат рожден ден на една и съща дата? Ако не ви се правят сметки, дайте поне някакво предположение :)

После ще ви кажа защо точно питам, просто искам да проверя едно твърдение.
50%, това е стара и известна задача, наричаше се парадокса на класа или нещо такова.
А за другия въпрос: от една страна имаме 2^128 от друга 10^8 (сто милиона), което е приблизително 2^24 т.е. вероятността е приблизително 1/(2^128/2^24)=1/(2^(128-24))=1/2^104
Това, разбира се е вярно в случай че самия метод на хеш няма слабости, които да увеличават вероятността за колизии. Например http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
Активен

0x2B|~0x2B