Řekněme, že máme soubor velký 2 GB a chceme někde uprostřed smazat pár bajtů. Co s tím? Ačkoli se zadání zdá jako triviální záležitost, ve skutečnosti tato akce vůbec jednoduchá není, protože žádný filesystém nenabízí pro tento úkol vhodnou operaci. Mazání dat ze souboru je a vždy bylo problematickou záležitostí.
Funkce podporované filesystémem zahrnují„otevření“ souboru (inicializace práce se souborem)skákání kurzorem v souboru (seek)čtení či zapisování dat na aktuální pozici ukazatelevynucení zapsání změn z paměti na disk (flush)řízení přístupu (lock)označení konce souboru (truncate)
Jak patrno, programátor má možnost v souboru skákat, zapisovat nová data přes stará, zapisovat nová data na konec (a tím soubor zvětšovat), dokonce může označit určité místo jako konec souboru (a tím efektivně zahodit data uložená v souboru za pozicí ukazatele a soubor zmenšit). Ovšem operace pro odstranění dat z prostředka souboru chybí. Už desítky let. Co s tím?
Pokud jsou v souboru uloženy záznamy nějakého libovolného typu, je situace částečně řešitelná. Stačí když každý záznam obsahuje informaci o tom, zda je platný či smazaný. Odstranění záznamu se pak provede jednoduchým přepsáním příznaku (delete flag). Data fyzicky zůstanou na disku, jen aplikace která soubor čte je bude ignorovat. Při přidávání dalších dat do souboru se nejprve zjistí, zda se data vejdou do některého bloku označeného ke smazání, a pokud ano, dojde k jeho přepsání novými daty, a tím k recyklaci místa na disku.
Dobře řešitelná je i situace, kdy jsou záznamy konstantní délky. Pak je možné na místo „mazaných“ dat přepsat poslední záznam ze souboru, a soubor zkrátit o délku posledního bloku (truncate).
Ovšem situace, kdy soubor obsahuje stream dat, u kterého záleží na jejich pořadí (například video), není řešitelná vůbec. Představme si například úkol z videa vystříhnout nějakou sekvenci. V současné době nezbývá nic jiného, než data od místa odstraněného bloku bajtů přepsat (posunout, překopírovat). Taková operace je dost nebezpečná, protože při výpadku proudu bude soubor v nekonzistentním stavu, proto se většinou volí varianta jiná, kdy je původní soubor zachován, všechna data (bez smazaných bloků) jsou duplikována do souboru druhého, a až je vše hotovo tak se druhý soubor přejmenuje na první (a tím ho efektivně nahradí). Přejmenování je atomická operace, takže nekonzistence dat v tomto případě nehrozí.
Proč ale neexistuje operace pro smazání dat ze souboru? Tomu dost nerozumím. Přijde mi to jako velice užitečné, a navíc samotná implementace na úrovni filesystému musí být triviální. Všechny filesystémy totiž musí z principu počítat se situací, kdy je nutné interně soubor rozdělit (fragmentovat) na několik částí (fragmentů). Naše operace mazání dat uprostřed souboru by pak udělala to stejné – soubor by fyzicky na disku zůstal jak je, jen místo kde začíná mazání dat by se označilo příznakem konce fragmentu, a místo kde mají data zase pokračovat by se označilo začátkem dalšího fragmentu. Vše by se samozřejmě muselo nějak zaokrouhlit na interní velikost bloku filesystému, eventuelně někde na disku překopírovat pár základních bloků, pořád ale kopírujeme maximálně kilobajty.
Chápu, že pokud by programátor (či jeho aplikace) tohoto postupu zneužíval, docházelo by k obrovské fragmentaci dat na disku. Ovšem to už je otázka zodpovědnosti programátora, nikoli problém filesystémové operace.
Rád se nechám vyvést z omylu či poučit. Existuje filesystém který takovou operaci podporuje? Pokud ne, proč to ještě nikdo v Linuxu neimplementoval? Jsme sto let za opicemi? :)
Protože diskový soubor je sekvence bloků pevné délky. Potřeba smazat soubor by jen zřídkakdy vycházela tak, aby to padlo na hranici bloků. Tudíž by to nebyla efektivnější operace, než to udělat z user programu pomocí zkopírování soubory za mazaným oknem.
Pokud je třeba častěji mazat uprostřed souboru, dělá se to tak, že soubor se myšlení rozdělí do sekvence kratších binárních kousků, tzv. chunků. Ty se uloží do jednoho souboru, nebo každý zvlášť do zvláštního souboru. A na začátku, nebo uvnitř chunku je mapa, jak za sebou pokračují. Smazání chunku uprostřed souboru je pak triviální operace, jednouše změna jednoho pointeru (32, nebo 64 offsetu) v mapě jako ukazatele na další chunk v pořadí.
Operační systém obvykle neimplementuje věci, které se stejně efektivně dají udělat z user space. Stejně jako linux kernel neimplementuje třeba Newton-Rapsonovu metodu pro hledání kořenů rovnic.
Operační systémy zkrátka implementují takovou množinu operací se soubory, které dovolí efektivní práci z programu.
Funkci nazvanou třeba:
int ferase(int handle, off_t start, off_t size)
si můžete velmi snadno naprogramovat sám a používat.
Kromě toho operace smazání části souboru uprostřed se používá minimálně. Při návrhu struktur a algoritmů programu se lidé snaží takové operaci maximálně vyhnout, protože je velmi neefektivní a nedá se udělat rozumně zaručeně atomicky.
Miloslav Ponkrác
Mozna tohle:
fcntl(2):
F_FREESP
Free storage space associated with a section of the
ordinary file fildes. The section is specified by a
variable of data type struct flock pointed to by arg.
The data type struct flock is defined in the
header (see fcntl.h(3HEAD)) and is described below. Note
that all file systems might not support all possible
variations of F_FREESP arguments. In particular, many
file systems allow space to be freed only at the end of
a file.
Konkretne treba ZFS tohle plne podporuje.
Tahle funkce by byla VELMI uzitecna pro editaci videi nebo muziky. Ve videu se ti stane velmi casto, ze potrebujes vystrihnout kus (treba reklamu). Ovsem v aktualnim stavu veci se vystrizeni jedne sekundy z prostredka rovna zkopirovani nekolika giga z jednoho mista disku na druhe.
Fragmentace neni problem, protoze mpeg podporuje vyplnovani mezer, takze kdyby bylo potreba vystrihnout napriklad 66000 bytes, tak 64kilo (65536) se vystrihne fyzicky a zbytek (464) se vyplni podle standardu mpegu.
Samozrejme zustava problem s atomicnosti teto operace, ale to by se dalo resit prehazovani bloku v souboru a hardlinkama = ve smyslu sdileni inodu mezi vice soubory.
Nejak takhle:
Mam file tvoreny inodama 10 11 12 13 14 15 16. Chci vystrihnout kus kolem bloku 13. Vyrobim novy file s inodama 10 11 20 15 16 - v inode 20 je zkopirovany zacatek inode 12 a konec inode 14 a vypln toho co zbylo do velikosti bloku. Az je to hotovo, prejmenuju puvodni file na ten novy. Tim se zrusi puvodni file a bloky 12 13 14 se uvolni, protoze je uz zadny dalsi file nepouziva. ostatni bloky zustanou alokovane.
Netusim, jestli tyhle operace nektery filesystem podporuje, ale predpokladam, ze jo. Vicemene staci, abych mel moznost zjistit ktere inody tvori muj puvodni file a abych mohl vyrobit novy file, kteremu ja reknu ze kterych inodu ma byt slozeny.
Ostatni operace ktere potrebuju jsou jenom seek, read a write, abych mohl vyrobit obsah toho meho inode 20 z minuleho prikladu.
[2]: programatori se tomu vyhibaji prave proto, ze optimalne mazat data uprostred souboru nejde. Teda neslo, ted vidim ze uz to jde pres fallocate, jak nekteri poznamenali v komentarich, coz dany problem kompletne resi.
Napise nekdo jednoduchy tool, kraticky C zdrojak, ktery vezme jako parametr jmeno souboru, offset a length, a jen zavola ten fallocate() s parametrem pro collapse? To by bylo bomba :)
[8] ... http://man7.org/linux/man-pages/man1/fallocate.1.html
Ale to pridavani by me taky zajimalo.
Randolf
Tak to je důvod proč byly vymyšleny (relační) databáze. Reprezentace je ve formě stromu, ten ma koncove nody stejne velikosti jako je block na disku. A pak se to řeší stejně jako operace nad stromem.
I střihání videa, co si tak pamatuji, se řeší v databázi a to i dokonce i relační s extensema (frame je řádek, ten pak má další informace jako histogram).
[12] Existuji patche (http://linux-kernel.2935.n7.nabble.com/template/NamlServlet.jtp?macro=user_nodes&user=1498), ale v hlavnim stromu to asi zatim neni.
Randolf
[3][8] Já bych na vašem místě počkal s nadšením pro fallocate, protože řeší kulové. Jen se potvrzuje to, co si myslím dávno, internet je plný „odborníků“, kteří „rozumnější“ všemu. V linuxové komunitě je takových „odborníků“ desetinásobek.
fallocate dokáže smáznout oblast, ale jen, pokud mu to dovolí jeho interní struktura. Tedy třeba jen pokud je offset a délka odstraňované oblasti zarovnaná na násobek diskového bloku (512 bajtů) nebo clusteru.
Funkce fallocate nijak nezaručuje, že je schopna odstranit libovolný rozsah souboru na libovolném offsetu. A pokud vámi zvolený rozsah nedokáže, tak hezky vrátí -1 a v errno najdete EINVAL.
Na to všechno byste přišli, kdybyste alespoň elementárně prošli manuálovou stránku k fallocate.
[13][15]
Přesně tak, jak už jsem psal výš, pokud potřebujete významněji editovat a odstraňovat a přidávat bloky dovnitř souboru, pak se to rozhodně nedělá na souborové úrovni, ale pomocí stromů a stránek. Tak, jak to dělá databáze.
Fragmentace je jiná věc, a ta v tomto případě vadí méně. Protože primárně nejde o fragmentaci, ale o rychlost souborových operací.
A jak je ze sw inženýrství známo, výběr vhodné datové struktury přináší raketové urychlení, než bezhlavé a fanatické trvání na jednom způsobu, například mít video či data v jednom souboru a dělat úpravy délky vprostřed.
[17] Mirku, nevim, proc se do nas hned navazis. Samozrejme, ze jsem si to prosel, a je mi jasne, ze to neni vsemocne, ale je to krok spravnym smerem. Pro konkretni ucely je to uzitecne. Samozrejme, ze je treba splnit mnoho podminek (pouziti spravneho souboroveho systemu, pohlidat si spravne zarovnani na bloky, atd.) Taky je treba posoudit, zda je pro danou aplikaci akceptovatelna velka fragmentace, ktera castym pouzitim vznika.
Nechapu, proc mas pocit, ze jsme si to neprecetli a ze jsme neschopni. To je jako bychom nasli nove implementovany malloc a Ty bys nam rekl: "no jo, ale vy jste neschopni, protoze jste si neprecetli, ze nefunugje, pokud Vam dosla alokovatelna pamet, a co teprve kdyz je fragmentovana, to se pak chova uplne nepredvidatene." To si pak od Tebe horoskopy delat nenechame :)
Randolf
[20] Já se do nikoho nenavážím. Řešení s fallocate není jenom všemocné, ale ve valné většině případů dokonce zcela nefunkční a fallocate jen ohlásí chybu. Zkuste si to, volejte fallocate, dejte mu různé meze a zjistíte, že v 99,9 % případů fallocate zahlásí, že to neumí. A to ani s tím správným souborvým systémem.
Pomíjím to, že použítím fallocate tímto způsobem vytváříte program, který bude fungovat jen na určitém souborovém systému, jen někdy, a taky musí duben a zároveň středa a ještě dojít ke trigonu Jupitera s Proximou Centauri. Pokud nebudou všechny tyto podmínky splněny, bude mít program problém.
Ne, není to řešení, a je to krok špatným směrem. Ba tím nejhorším. Namísto volby správných datových struktur a správného způsobu uložení dat, což je jediný správný krok, se snažíte používat to, co byste neměli dělat jinak, než v naproté nouzi.
Diskové soubory mají svůj způsob uložení, a ten má svá omezení. Správným směrem je neznásilňovat, ale navrhnout způsob uložení dat programu tak, aby neměly problémy s věcmi, které drhnou.
Namísto správného řešení problému si tu všichni myslí, že všechno se řeší rambovským způsobem najít větší kladivo, a pokud to nejde, najít ještě větší kladivo. S tímto přístupem je dobré kopat kanály, ale proboha neprogramujte. Dělejte ochranku, nebo někd,e kde je důležité jít proti zdi, ale nedělejte duševní práci.
Základem správného programování je správný návrh datových struktur a to včetně způsobu uložení na disku. Takový, který je pro daný problém nejefektivnější. Namísto potřeby častého mazání okna uprostřed souboru je třeba řešit: „Proč mám tak blbě navržené struktury, že takovou neefektivní operaci často potřebuji. Jak bych to měl udělat jinak, abych nepotřeboval mazat uprostřed souboru, a nebo jenom velmi výjimečně.“
A pokud už se maže uprostřed souboru okno, tak použít poněkud stabilnější způsob, který funguje i jindy, než v dubnu, a udělat to trochu robustněji, tedy nepoužít fallocate.
Víc k tomu nemám co říci. Styl: „Nejde-li to silou, půjdu to ještě větší silou“ vám zaručí, že velmi rychle skpončíte jako neschopní programátoři.
[19] Ne, fallocate není řešení ani pro vystřihnutí souboru.
fallocate je funkce pro ty, kteří vědí, co dělají. Na pro ty, kteří hledají kladivo, protože programovat neumí.
fallocate je funkce pro ty, kteří vhodně navrhnou datové struktury. Zjistí si informace o velikosti clusteru na disku, granularitě ukládání dat na disk a další a přizpůsobí tomu strukturu. Tedy ideálně pro databázové výojáře, nebo pro ty, kteří přizpůsobí diskové soubory granularitě přirozených diskových bloků. Neznalec by měl zapomenout, že nějaká fallocate existuje, nepomůže mu – nepatří do jeho rukou.
Neznalec by si měl imnplementovat vlastní funkci, které smaže okno uprostřed souboru pěkně po staru. Tedy překopíruje data v souboru od (start_block + erase_size) na pozici (start_block) a na konci pekně nastaví souborové ukazovátko handle na (old_size - erase_size) a hezky na tomto místě ukončí soubor.
Funkce fallocate je pro ty, co se přizpůsobí, tedy polopaticky řečeno, navrhnou struktury na disku správně. V jiných rukách nadělá fallocate pouze škodu. Nepoužívejte ji pro běžné souborové operace, ani tehdy, pokud nic neznáte a jste začátečníci. Není to funkce pro vás.
Nejsem nějaký expert na fs, ale neměl by tohle teoreticky fs umět?
Přece by stačilo nalézt bloky, který obsahuje to co chceme smazat. Vytvořit si nový blok, ve kterým bude to, co z těch bloků nechceme odstraňovat. A pak stačí změnit ukazatele bloků tak, aby se ty staré zahodili a nahradil je ten nový.
Akorát na tyhle akce budou potřeba použít funkce na defragmentaci, nebo přímý přístup na disk.
No já tedy nevím, ale i smazání bloku uprostřed souboru bych řešil jeho kompletním překopírováním bez odstraněných bloků. Pokud toho mám smazat víc, tak si jen sestavím soupis odstraňovaných míst a nakonec to uložím do nového souboru.
Proč?
1. Co když operace uprostřed selže? (elektřina, HW chyba, pád OS, whatever)
2. Co když uživatel smazal něco, co nechtěl?
3. Dneska pořád někdo zápasí s místem na disku?
4. Nehledě na to, že přepisování souboru posouváním bloků rozhodně není atomická záležitost
Jinak pro vážnější operace se opravdu dělá to, že se soubor rozdělí na spoustu menších souborů a s těma se pak pracuje. Tam ani nemusí být ten předmětný chunk pevné velikosti. Další možností je "interní FS" (prostě FS realizovaný uvnitř pracovního souboru na míru potřebě i třeba s možností mazat uprostřed)
[25] Samozřejmě se najdou případy, kdy to má smysl dělat složitě. A také případy, kdy ne. Číst a zapisovat gigabajty dat, když by stačily jen kilobajty. Nebo vymýšlet důmyslné datové struktury pro provedení operací, které umí zhruba udělat i filesystém.
4) To snad hrozí jen u FAT, ostatní fs mají aspoň nějaké žurnálování, a i když se nežurnáluje všechno, tak zrovna metadata ano.
Tomáš je autorem několika více či méně známých projektů jak z oblasti operačních systémů, tak internetu. V současnosti samozvaný expert na Linux, Bash, PHP a MySQL.
Přečteno 25 303×
Přečteno 23 659×
Přečteno 19 216×
Přečteno 17 987×
Přečteno 12 787×