Linux за българи: Форуми

Първо, такъв домейн и такава услуга не същестуват, името е избрано съвсем произволно.

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

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

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 - доста добър калкулатор е и го има в хранилищата на по-разпространените дистрибуции (поне със сигурност го има в тези на дебиан и в тези на федора.

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

Първо при такива обеми традиционното резервно копиране, което се стартира през нощта е невъзможно и това ще ти го каже всеки, който се е занимавал с това....

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

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

Това как се прави бекъпа има малко отношение, идеята е да се създаде някаква по-увлекална предистория на задачата, защото иначе нещо от сорта на "за множеството 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)

//off
Тук за дата.бг ли става въпрос, щото след последния ъпгрейт техният портал и нещо такова :)

А, не знам, никога не съм им бил потребител, само разбрах че направили тегленето платено или нещо такова.

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

И такива работи.

@gat3way интересен аватар ;)

Аватарът е да плаши тези дето развиват конспирационни теории :)

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

Лято е. Време за  [_]3, жени и море.  ;)

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

Това е базата на архилошите.

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

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

Старо като света, всеки знае отговора, макар поне аз да не мога да го сметна, а го има и в страницата на едно хакерче Мильо, дет все дири бъгове на Дебилиан  [_]3

Шът сега за това :) Сериозно искам да разбера наистина хората дали в повечето случаи мислят да го смятат като 22 пъти вероятността два рождени дни да се засекат, щото са го кръстили "парадокс", трябва да има защо . Не мога да разбера по каква логика става това. Питах няколко човека, наистина имаше такива дето тръгнаха да го смятат така, ама бяха малко.

Ха gat3way  яка  задчка ще ми е интересно да разбера имали  решение задачката. :)

Намирате се в една стая с още 22 човека. Каква е вероятността двама души в стаята да имат рожден ден на една и съща дата?

0.003467818=(22*21)/(365*365)
това е без отчитане на високосни години  >:D
също така трябва да се уточни какво се разбира под "една и съща дата" - ако е ден.месец.година ............ няма да стане :)

Това е базата на архилошите.

Добре де, по-проста задача. Намирате се в една стая с още 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 ($2)

Аз си мисля за аватара. Това не беше ли някаква ядрена електроцентрала след земетресение.

Така е, 50% (ако игнорираме високосните години).

За колизиите обаче сметките не са правилни. 2^24 е около 16 милиона, но и да беше 100, пак не е правилно - така се смята каква е вероятността за един файл, някой от останалите 99,999,999 да извади същата хеш сума. Обаче това не включва вероятността измежду останалите 99.999.999 да има друга двойка файлове с еднакъв хеш. В смисъл, твоят отговор е валиден, ако задачата е зададена така: "имаме 99.999.999 файла и записваме нов. Каква е вероятността хешът на новия файл да съвпадне с хеша на някой от останалите".

Разбира се, както казваш, трябва да приемем че MD5 алгоритъма генерира стойности, които имат равномерно разпределение в интервала 0..2^128 - което надали е точно така.

Така е, 50% (ако игнорираме високосните години).

За колизиите обаче сметките не са правилни. 2^24 е около 16 милиона, но и да беше 100, пак не е правилно - така се смята каква е вероятността за един файл, някой от останалите 99,999,999 да извади същата хеш сума. Обаче това не включва вероятността измежду останалите 99.999.999 да има друга двойка файлове с еднакъв хеш. В смисъл, твоят отговор е валиден, ако задачата е зададена така: "имаме 99.999.999 файла и записваме нов. Каква е вероятността хешът на новия файл да съвпадне с хеша на някой от останалите".

Разбира се, както казваш, трябва да приемем че MD5 алгоритъма генерира стойности, които имат равномерно разпределение в интервала 0..2^128 - което надали е точно така.

Хм, мисля си че това, което дадох е по-скоро вероятността (наистина при разномерно разпределение на хеша) два файла от N  да са с еднакъв хеш
П.П. А ми излезе 2^24 защото го смятах по малко обратния начин и съм сметнал lg2, a трябва да е 1/lg2 t.e. 2^26.4, но според мен разликата е несъшествена за мащаба
П.П.П. Да си срещал някъде  вероятностното разпределението на хеш, все някой го е извел (надявам се)

Мне, ако сведем задачата с хешовете до някой по-прост проблем, например този с рождените дни, тогава по същата логика ще имаш 1/(365/23) = 23/365 = 0.06 = 6% (а не 50% какъвто е отговора).

Иначе за разпределението на хеш стойностите нямам идея, не съм виждал. Според мен ще е ужасно сложно да се сметне нещо такова, ама знам ли...

Освен хеша добави и размера на файла. Така получаваш 100% съвпадение.

Колизия при еднакъв хеш, но различен размер ще е доста трудна за осъществяване.

Математически погледнато, размера на файла няма значение. Преди известно време, даже ако не се лъжа точно в този форум, спорех с някого, че големината на файла има отношение към вероятността за колизия. Няма никакво отношение. Стига да са достатъчно големи файловете, за да може да има 100 милиона уникални такива, вероятността два файла да направят колизия на хеш сумите им е една и съща: 1^128. Ако от друга страна направим ограничение: два файла да дават еднакъв хеш и да имат еднаква големина, това е друго нещо. Тогава обаче трябва да имаме максимална големина на файла, иначе задачата няма да има решение.

Математически погледнато, размера на файла няма значение. Преди известно време, даже ако не се лъжа точно в този форум, спорех с някого, че големината на файла има отношение към вероятността за колизия. Няма никакво отношение. Стига да са достатъчно големи файловете, за да може да има 100 милиона уникални такива, вероятността два файла да направят колизия на хеш сумите им е една и съща: 1^128. Ако от друга страна направим ограничение: два файла да дават еднакъв хеш и да имат еднаква големина, това е друго нещо. Тогава обаче трябва да имаме максимална големина на файла, иначе задачата няма да има решение.

Така като си правя сметки наум размера на файловете (ако са двоични) е 4 байта, тогава уникалните биха били 4 милиарда. Друг е въпроса с именуването, но тогава даже и имената им да са само цифри и букви (малки) 7 символа биха били достатъчни
П.П. мисля че имаш предвид 2^128 Ако някой има интерес ще спретна md5 сумите на първите 4 милиарда файла

Ох, да, 1/2^128 имах предвид.

Обаче това с първите 4 милиарда файла ще се окаже доста интересна задача. Значи аз мога да сметна каква е вероятността за колизии (имайки предвид birthday paradox-a):

p=1-exp(-1*(4*10^9)^2/2^128*2) = 0.0000000000000000094%

Това е при положение че хешовете наистина са разпределени равномерно и MD5 е идеална хеш функция, излиза че шансът да се получи колизия е доста нисък. Обаче в действителност е възможно шансът да е по-висок. Да оставим това на страна.

Изпълнението е по-интересно. Генерирането на "първите" 4 милиарда файла не е такъв проблем, както и хешването им - резултатът ще е един файл с хешове с големина 4*16 = близо 64 гигабайта. Дотук няма проблеми - днешните харддискове са големи.

Обаче за да тръгнеш да търсиш колизия в тази база става малко сложно. Единият вариант е да имаш машина с над 64 гигабайта РАМ, за да качиш всичкото в паметта и да го обхождаш бързо. Това е идеален вариант, обаче такива системи с 64 гигабайта рам са скъпички и не всеки има под ръка такава.

Другият вариант е да тъпчеш в паметта някаква част от тях, да изчиташ от файла хеш по хеш и да сравняваш, после да тъпчеш в паметта следващата част и да изчиташ до края и такам...това обаче ще е ужасно бавно. Отделно, с 32-битова машина имаш ограничение откъм адресно пространство - повече от 3 гигабайта не можеш да вдигнеш в рамта по този начин (останалия 1 гигабайт се ползва от ядрото и се мапва на 0xC0000000 до 0xFFFFFFFF) - има друг вариант да се форкнат няколко процеса и да си правят IPC някакво, ама е сложно и пак не е много бързо.

Има и трети вариант - всичко да се натъпче в SQL база и да се напише някакво къдраво query по въпроса. Този вариант поне за мен е най странния (щото не разбирам много) - чудно ми е какво ли ще се получи? Обаче интуицията ми казва, че mysql таблица с 4 милиарда реда и един забавен SELECT отгоре ще отнеме доста време...чудно някой по-опитен с разните бази какво ли би казал по въпроса?

...
Има и трети вариант - всичко да се натъпче в SQL база и да се напише някакво къдраво query по въпроса. Този вариант поне за мен е най странния (щото не разбирам много) - чудно ми е какво ли ще се получи? Обаче интуицията ми казва, че mysql таблица с 4 милиарда реда и един забавен SELECT отгоре ще отнеме доста време...чудно някой по-опитен с разните бази какво ли би казал по въпроса?

Ще си спретна един Оракъл и ще го пробвам как ще се държи с такава "табличка" :)
Проблема е че партиционирането няма да е от полза, защото трябва да се пусне едно картезианско търсене и......

Ще е забавно колко време ще отнеме...

Ще е забавно колко време ще отнеме...

Ха, очаквам да е от порядък на десетки часове и даже денонощия. Но сега съм в отпуска и не ми се мисли за такива неща :)

Няма да отнеме чак толкова време статистиката след това ..и с БД и без (т.е. някакаъв скрипт) защото има едно нещо т.нар. сорт+двоично търсене но в сл. даже няма нужда да се стига дотам - още при въвеждане на хеш гледаш дали вече го има и ако е така само му увеличава брояча т.е. втората(3тата) колона - нали табл. няма да е само с 1 колона?!
т.е. думарното време ми се чини че ще е само колкото да се генерират хешовете - вкарването в БД е пренебрежимо бързо :-) а и после заявката е доволно проста - Да вади само тези с бр. > 1

Това ще работи добре до момента в който не генерираш прекалено много хешове (все пак старите трябва да ги пазиш някъде, за да можеш да сравняваш). Под прекалено много хешове имам предвид повече от количеството, което можеш да натъпчеш в RAM-та. От този момент нататък ще трябва да пазиш нарастваща бройка от тях върху диска и при генериране на следващият хеш, освен че ще претърсваш това в РАМ-та, ще трябва да изчиташ записаното на диска. Първоначално, това няма да отнема много време, но в последствие ще стане доста бавно (за всеки новогенериран хеш примерно да трябва да изчиташ няколко гигабайта от диска).

Обаче ако имаш достатъчно много РАМ, тогава няма да се стигне дотам. Просто зависи колко хеша искаш да сметнеш.

като се замислих всичко може да се реши само с един ред без експлицитно да трябва да се указва сравнение на хешовете (то ще се прави вътрешно). И няма да има нужда от трета колона. Нещо от рода:

Това ще работи добре до момента в който не генерираш прекалено много хешове ....Първоначално, това няма да отнема много време, но в последствие ще стане доста бавно (за всеки новогенериран хеш примерно да трябва да изчиташ няколко гигабайта от диска).

gat3way има едни неща наричат се индекси  и НЕ трябва цялото нещо да се пази в паметта - по индекса с двоично търсене (т.е. зареждат се само тези части които му трябват) става доста бързо а и ако избереш правилната БД освен индекса може и да не ти трябва още едно изчитане за реалните данни (т.е. при някой БД само индекса е достатъчен ако е по цялото поле напр. InnoDB но пък при MyISAM не е така)
П.П. За по-простичко обяснение (cpp код) може да погледнеш kbgoffice assistant-а как го прави  ;)

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

Честно казано не съм сигурен кое би било по-бързо: генериране в движение и вмъкване в базата или генерирне и вмъкване на целия файл. Мисля си че във втория случай ако сме дефинирали стойността (0 до 2^32-1) като индекс процеса на създаване на индекса няма да е за всяка стойност а на по-крупни парчета

Честно казано не съм сигурен кое би било по-бързо: генериране в движение и вмъкване в базата или генерирне и вмъкване на целия файл.

Естествено Ромео е прав - повече БД правят точно така при вкарване на много голям обем данни наведнъж - явно или неявно забраняват индексите => импортират данните и ре-генерират индекса наново за по-бързо... само че така остава гадната бавна заявка после а аз имах предвид по-скоро че докато се изпълнява смятането на мд5 на следващ файл т.е. процесороемка процедура едновременно ще се за генерира и записва и индекса в/у диска и ще се броят еднаквите. 4 Гб днес нищо не са - ако искаш може и програмка да си напишеш (не за ВМ освен ако нямаш излишна такава с 4 Гб ОП) но ..като се замисля и тя може да се окаже излишна - записваш ги във файл по 1 на ред после sort ; sort -u и накрая с diff сравняваш 2та и броиш различните редове ;-)

П.П. Извинявам се предварително - в момента не се сещам за по-елегантно решение с една команда което от вече сортиран файл да брои само повтарящите се редове (освен със собственоръчно написана програмка)

Само да вметна, че не става въпрос за 4 гигабайта, а за 64 гигабайта - хеш сумите са 16-байтови.

Цитат на: romeo_ninov в Aug 12, 2009, 19:51

Честно казано не съм сигурен кое би било по-бързо: генериране в движение и вмъкване в базата или генерирне и вмъкване на целия файл.

Естествено Ромео е прав - повече БД правят точно така при вкарване на много голям обем данни наведнъж - явно или неявно забраняват индексите => импортират данните и ре-генерират индекса наново за по-бързо... само че така остава гадната бавна заявка после а аз имах предвид по-скоро че докато се изпълнява смятането на мд5 на следващ файл т.е. процесороемка процедура едновременно ще се за генерира и записва и индекса в/у диска и ще се броят еднаквите. 4 Гб днес нищо не са - ако искаш може и програмка да си напишеш (не за ВМ освен ако нямаш излишна такава с 4 Гб ОП) но ..като се замисля и тя може да се окаже излишна - записваш ги във файл по 1 на ред после sort ; sort -u и накрая с diff сравняваш 2та и броиш различните редове ;-)

П.П. Извинявам се предварително - в момента не се сещам за по-елегантно решение с една команда което от вече сортиран файл да брои само повтарящите се редове (освен със собственоръчно написана програмка)

няколко бързи вметвания:
1. не мисля че операцията по смятането на хеша ще е много трудоемка, защото дължината на текста е 4 байта
2. за да е налична пълната картина и за да може да се сметне разпределението е нужно да има информация за всички хешове: този се среща веднъж, този този два пъти, този три
3. мисля си че diff, sort няма да са много по-бързи от база данни (ако са по-бързи)
4. файла за зареждане ще е 84 гигабайта: 4 байта стойност (от 0 до (2^32)-1), разделител, 16 байта (за md5, които стават 20 за sha1)

Мисля, че разделителя може да се спести - все пак всяка входна стойност е с фиксирана дължина (32 бита) и всеки хеш тоже. Не че ще спестим кой знае колко - 4 гигабайта не са кой знае колко на фона на останалото.

В крайна сметка обаче мисля, че експериментът ще е неуспешен, защото 4 милиарда хеша са прекалено малко, за да си изградим някаква представа (на фона на множеството от 2^128 възможни стойности).  Чисто статистически, вероятността да се получи колизия е 0.0000000000000000094%, това ако стойностите са разпределени равномерно разбира се. Трябва да са ужасно неравномерно разпределени, за да имаме вероятност примерно от 1% да имаме  една колизия (един процент е 106 квадратилиона пъти по-висока вероятност). Това не означава, че ще ни трябват 106 квадратилиона пъти повече хешове, за да достигнем 1% вероятност, разбира се, защото според birthday paradox-a, зависимостта между броя хешове и вероятността за колизия не е линейна.

Имам ужасно силно усещане, че няма да открием нито една колизия за 4-те милиарда входни стойности. Ако открием, това ще бъде или невероятен късмет, или просто MD5 алгоритъмът ще излезе невероятно криво направен. Но за да се разбере кое от двете е, трябва да повторим същата операция за много по-голяма извадка от входни стойности и техните хешове.

Поне така си мисля де.

...
Имам ужасно силно усещане, че няма да открием нито една колизия за 4-те милиарда входни стойности. Ако открием, това ще бъде или невероятен късмет, или просто MD5 алгоритъмът ще излезе невероятно криво направен. Но за да се разбере кое от двете е, трябва да повторим същата операция за много по-голяма извадка от входни стойности и техните хешове.

Поне така си мисля де.

Не знам дали ще открием дублираща се стойност, но и на мен ми се струва че ще трябва да заложим поне на десетина порядъка повече данни примерно 2^64, но нещо не ми се мисли за пълно търсене там :D

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

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