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

Трябва ми програма която да не позволява на харда да има 2 файла с 1 и също име .Има ли такава ?
Става въпрос за ФТП искам да го огранича потребителите да немогат да качват 1 файл 5-10 пъти
Благодаря предварително

Я пак?

В мрежата всеки потребител си има папка в ftp
и може да качва квото си иска само в неговата папка
Та въпроса е как да се направи така че 1 файл като го има на харда на ftp да неможе да се качи пак и демек повече от 1 копие на файла да няма така ще се спести доста пространство ама номера е как да се направи Ако някой има отговор на загадката ще съм благодарен ако го сподели

Е, ами ако го качи с различно име просто?

Щом имат право да качват, сигурно имат право да разглеждат съдържанието на папката и да свалят. Ако някой качи файл, който съществува в друга папка, какво ще направим? ln -s към файла в чуждата директория? Ами правата ? Или за двамата ще направим група?    Ще се получи интересна база данни с потребители, файлове и права. Може и да има такова нещо ...

С hash суми на файловете се прави обикновено това. Но програма не знам ...

А може ли някой след като е качил някакъв файл в даден момент да реши да го редактира или да го качи отново, но с редактирано съдържание?

Представи си, ако двама са качили един и същ файл, а ние сме премахнали едното копие. Единият от тях решава и го редактира. Другият си мисли, че го има във варианта, в който го е качил, но не би... Значи при редактиране трябва да се пази и предната версия. Хм, май ще измислим файловия сървър Novell Netware  

Може да се вадят MD5 хешове и да се сравняват, това не е проблем, естествено не в рамките на ftp сесията, но да речем в рамките на някакъв cronjob.

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

П.П. и скриптът също ще е забавен, ако не се оптимизира поне малко да не смята суми на качени вече файлове, на 4 ТБ файлове как ще им смяташ сумите, ще е грозно изпълнение с много iowait и много деградиране на  производителността. От друга страна, ако потребител презапише качен отпреди файл, трябва да се сметне сумата наново. Май най-добре е един скрипт дето гледа наскоро модифицираните файлове и им смята сумите, да речем нещо от сорта на:

find /dir -mtime -1 |xargs myscript.sh

И myscript.sh да хваща това от $1, да си смята сумата (с md5sum да речем) и да си прави сравненията и да трие ако се наложи.

Забавна задачка е иначе

За MD5 не знам, но със SHA1 вероятността е толкова малка, че има много програми, които го използват като адрес към файл/блок (git anyone?). А пък ако има колизия, винаги може да се провери дали двата файла са различни.

Прекрасно, опресних си знанията за hash алгоритмите.

SHA1 генерира 180-битов хеш. MD5 генерира 128-битов, в този ред на мисли, при SHA1 вероятността от колизии наистина е по-малка.

Интересен е въпросът, какво се влага в понятието "колизия", защото има огромно значение големината на съобщението, от което се вади хеша. Ако става въпрос за пароли дето са рядко над 16 символа, въпросът с колизиите сигурно е важен, а вероятността за наличието на такива е...много малка. Ако става въпрос за 700-мегабайтови файлове обаче нещата стоят малко по-различно. Съвсем се абстрахирам от хеш-алгоритмите, защото при това положение те нямат толкова значение. Представи си че имаш 700 милиона позиции да наредиш както си искаш 256 стойности, това ти е множеството възможни 700-мегабайтови файлове. Съответно множеството възможни изходни MD5 хешове представлява броят възможности да наредиш на 16 позиции 256 различни стойности. Чисто теоретично, възможните колизии при това положение са 700.000.000 / 16. Не са малко все пак, как мислите? При това положение SHA1 би променило нещата с порядък 180/128 пъти по-малко възможни колизии. Надали има особена разлика

Поправете ме ако греша, но ... на файл 4.5GB (DVD филм например) колко време се изчислява MD5 или SHA1 ключа? Незнам дали има такава възможност, но за файловете в една и съща папка дали може да разрешиш имена само с главни или малки букви? Защото тогава нещата май са по-лесни. Или аз се заблуждавам.

Ми като гледам около минута отнема за 2ГБ файл тука на щайгата ми вкъщи. Нямам раид0 масив, процесорът е athlon64 3000,  и дискът ми не е кой знае какво. Не знам доколко това може да се дължи на някакво кеширане, но все пак това е огромен файл. Не е малко де, представям си ако става въпрос за 4ТБ файлове какво ще е  

Такова нещо съществува и го има на ftp-то на ISP-то ми. Как е направено, чия собственост е и дали ще ти го дадат не мога да ти кажа, но може да влезеш тука, да преровиш из "контакт"-тите за Цецо (демек шефа) и да го питаш. Успех!

gateway,

Големината на "съобщението" няма никакво значение. Помисли! Иначе подобни системи се използват от много хора и никой досега не се е оплакал от колизии. Аз например вкъщи използвам подобна система, съдържаща около 20 милиона хеша (200GB данни на по 8КБ блокове), засега нямам колизии. Ако имаш 1 ексабайт данни (10^18) и правиш SHA1 хеш на блокове по 8К, вероятността два блока да имат един и същ хеш е 10^-20. Ако такава вероятност те притеснява, използвай друга хеш функция

luda_glawa,

А за колко време се download-ва 4.5GB файл? :Р

В този случай големината на съобщението ти не се ли води 8кб?

А дали не може да се напише един скрипт, викан периодично, който да проверява дали в резултата от

Примерен код

ls -lR

няма два еднакви(или относително еднакви, зависи какви критерии определят дубликациите) реда?

gateway,

Големината на съобщенията няма _нищо_ общо с вероятността от колизия.

Добре де, нека няма, признавам се за победен

Вземаме случаят с MD5.

Сметките обаче пак не излизат правилни, 2^64 е вероятността за колизия на хешовете при две произволни съобщения. В случая обаче не смятаме директно възможността при два файла да се получат еднакви хешове, а възможността това да се случи по принцип с която и да е двойка файлове.

Една предварителна сметка: 2^64 е приблизително равно на 2*10^19.

Значи ако например има 10000 файла, то има C= 10000! / 2*(10000-2)! = (10000*9999)/2 = 5000*9999 - приблизително 50 милиона комбинации от два файла от тези 10000, върху които да смятаме възможността за колизия. Следователно, общата вероятност да се случи колизия на хешовете измежду някоя двойка файлове от тази файлова система става приблизително:

5*10^7 / 10^19 = 5 / 10^12 = 1/2*10^11

или едно на 200.000.000.000, уаааа, наистина е много малко вероятно да стане, не съм го очаквал.

Ще сметна само какво ще стане със 100.000 файла, просто за справка:

C=100000!/2!*(100000-2)! = 100000*99999/2=50000*99999
= 4.999.950.000 = (appr.) 5.000.000.000= 5*10^9

P(колизия)=5*10^9/10^19=5/10^10=1/2^9 = 1 на 2.000.000.000.

Съответно при един милиона файла, вероятноста става едно на (хм) 20 милиона.

Всъщност SHA1 в този случай трябва да излезе сериозно по-добър вариант, не е далече от ума, ще добави няколко нули към вероятността...

Сметките ти са грешни. Ако имаме 10000 файла, значи имаме 10000 хеш стойности. Ако предположим, че вероятността за получаване на всяка възможна хеш стойност за еднаква (2^-128, прибл. 10^-28), тогава вероятността хеш стойностите на два файла да са еднакви е 10^-24.

Комбинаториката в случая не ти дава нищо повече. Припомни си теория на вероятностите.

Но пък всъщност може двамата да имаме предвид две различни неща. Аз имам предвид възможността да има колизия на хешове между кои и да са два файла в някаква файлова система. Ти вероятно имаш предвид вероятността за всеки нов качен файл да се случи колизия. В този случай и двамата сме прави

Мисля, че си позабравил теория на вероятностите. Припомни си я и ще разбереш защо няма нужда от сметки с комбинации.

Това не е аргумент. Замисли се малко:

Задачата не е каква е вероятността от 10 хиляди тегления да извадиш червена топка, при положение че в кутията червените топки са 1 на 2^x. Задачата е каква е вероятността ако изтеглиш 10.000 топки, да изтеглиш 2 с един и същ цвят. При положение че в кутията имаш неограничен брой топки от 2^64 различни разцветки. Как според теб се решава задачата?

Апропо, нека променим леко задачата и искаме да намерим вероятността да имаме не 2, а 3 файла с еднаква MD5 стойност. Това по какъв начин ще промени твоята сметка?

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

gateway,

Днес нещо не мога да смятам, но мисля, че и двамата грешим. Ще помисля по въпроса утре

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

Примерен код

#!/bin/sh # Pyt do osnovnata papka, v koqto 6te se tyrsqt ednakvi failove # Skriptyt tyrsi i v podpapkite failove=/pyt/do/papkata # Pyt do faila, v koito 6te se izpisvat syvpadeniqta syvpadeniq=/pyt/do/faila/fail ### Ne e nujno redaktirane na komandite po-dolu ### osnova=`echo $failove | cut -d/ -f2` /usr/bin/fdupes -q -f -r $failove > $syvpadeniq cat $syvpadeniq | grep / | sed 's/ /\\ /' | sed 's/\/'$osnova'/rm \/'$osnova'/' > $syvpadeniq chmod +x $syvpadeniq $syvpadeniq chmod -x $syvpadeniq

За използването на скрипта, предварително трябва да се създаде един празен неизпълним файл някъде. В него ще се впишат всички съвпадения, като в списъка няма да влиза по едно съвпадение от всяка група съвпадения. Това невписано съвпадение ще е файла, който няма да се премахва. Скриптът трябва да се сложи в един изпълним файл и да се сложи в crontab-а да се изпълнява в определени моменти. Трябва да се има предвид, че процеса е натоварващ. Изпробвах скрипта на машина със Celeron 2,7MHz, 1GB RAM, ATA HD с 16MB cache за търсене на съвпадения в папка с 40 386 файла (какви ли не файлове от текстови бележки до филми; оказа се, че няма съвпадения) и процеса отне 20 минути. Като цяло, бих препоръчал скрипта да се изпълнява в интервал минимум 2 часа при такава бройка и вид на файловете (препоръчително - 12 часа). Това, което се опитвам да изчистя като недостатък в скрипта, е контрол на автоматичния избор на файла, който няма да се премахне. В момента скрипта си избира един от файловете по логика, която все още не мога да хвана, но в симулациите, в които го пробвах, винаги избираше един и същи файл от групата със съвпадения.

edit: Всъщност не е задължително файла, в който ще се записват съвпаденията, да се създава предварително. Ако файлът го няма, скриптът ще си го създаде, според зададената стойност на променливата $syvpadeniq.

Хрумна ми още по-интересна идея, за съжаление, не мога да предложа реализацията и. Идеята е следната:
През определено време се стартира Програмката;
Програмката изпълнява

Примерен код

ls -laR /home/

и пъха някъде изхода. После търси редове със еднакви файлови имена. При съвпадение, проверява размера и при съвпадение проверява md5 или sha1 сумите им и чак тогава при равенство трие по-новия. Иначе нищо.
Така ми се струва, че ще става по-бързо, отколкото ако се смята сумата на всеки файл и ще може да се изпълнява по честичко. Освен това не ми изглежда точно добра идея да се пренебрегва разликата на файловото име при съвпадение на md5 сумата. Колкото и малка да е вероятността от колизия, все пак е по-голяма от нула. Никой не може да гарантира, че колизия няма да настъпи на втората проверка(да речем. Не съм достатъчно запознат, да го твърдя съвсем убедително, но знам, че ако гръм удря човек веднъж на 100 години, това не означава, че през следващите 99 години няма да се случи.).
Принципно бих написал Програмата на Java, понеже не съм запознат достатъчно от близо със bash-а, но принципно нямам време в момента. Иначе май със bash(или некоя друга люспа) ще стане най-бръзо(с по-малко писане).

tarator, май си прав.

Реших да сметна нещо подобно, само че за думи от 10 букви, при азбука от 30 такива, каква ще е вероятността да излезе да има 2 повтарящи се букви вътре. По моята логика излезе по-голяма от 1. Или примерът не е удачен, или и моите сметки не са много наред

Според мен е хубаво да се прави проверката за дублиращи файлове още в момента когато рече да се качва някакъв файл, защото с тези скриптове които искате да се пускат периодично ще се товари доста фтп-сървърът, особено при голямо ftp.
Например правите си една база да речем в mysql в която съхранявате MD5 сумите на файловете и при upload се извиква външен скрипт, който проверява дали сумата е вече в базата и според зависимостта или reject-ва даденият upload или вкарва сумата на новият файл в базата.
Понеже не спомена какъв фтп сървър използваш само ще спомена че при pure-ftpd е има реализирана горната схема с PurePostPro.
За подробности:
http://www.pureftpd.org/project/pure-ftpd

има много хора които биха дали лявата си ръка за да могат да правят файлове на които размера да е един и същ и два хеш алгоритъма да дават еднакви резултати ...

sdr,

Това е много лесно -- трябва файловете да имат идентично съдържание :Р