Skript pro paralelizovanou tvorbu md5 bloků disku

[Ħαℓ₸℮ℵ ␏⫢ ⦚]

Mám něco jako

Kód: [Vybrat]

ptr=0; while  [[  $ptr -lt 500000 ]] ; do dd if=/dev/sda bs=1M  count=10 skip=$ptr conv=fullblock  | md5sum  -b > blok$ptr.bin ; ptr=$((ptr+10));  done
Cílem je udělat (z 5TB)   jakýsi zhuštěný "hash".  Například každý 1MB dat do 2bajt bloku .
Abych poznal na první pohled, která pole jsou plná nul, která plná FF, a pak(volitelně) nevím něco mezi tím (něco jako entropie), ale aby to nebylo moc výpočetně náročné. Logicky aby stejný blok měl stejný výstup.

A taky tam jsou dvě vady:
Prostřední "výkonný" blok md5sum -b má  pevnou délku 160b, md5sum je pomalé,nechci md5sum, ale nějaké CRC, které mi třeba jen řekne počet nul a počet jedniček modulo 255.

Zadruhé je o procesor to v jednom sekvenčním zpracování brzdí. buď se čte a nebo vypočítává hash.

Zatřetí procesor by to ani nestíhal, kdyby jednovlákno neustále počítalo hash. Je třeba zaměstnat víc vláken

4. Opustit md5sum, sloužilo to jen jako příklad. Musí to být rychlé a zároveň nějak matematicky založené (že třeba první bajtu dává počet nul v bloku%1024) adruhý  počet nul v lichých bitech. A srozumitelné, když koukn že tam je 0x80CC, tak že tam je půl napůl nuly a CC nějaká hodnota entropie. Hodně zjednodušeně

Disk má 240 MB /s, ale zpracování md5 asi 50 MB/s. Potřeboval bych to paralalizovat (i kdyby tam md5 nezůstalo).

Jak tu paralalizaci řešit? Dá se to nějak v bashi elegantně řešit nebo na  to je lepší si napsat skript v rustu, perle, ruby, pythnu?

Aby disk jel maximum nonstop, nečekal na dkonočení výpočetní části, aby se nezastavoval ani neseekoval zběsile. a data předával nějakým threadům (4-8), která sama zpracují a zapíšou na příslušnou pozici.

Nechci zapisovat do 5000000 souborů *.bin, ale do jednoho 5MB/10MB souboru. Technicky i do nějaké paměťové struktury, které se občas syncne na disk.



Další nápad, vytvořím si soubor předvyplněný hodnotami třeba 0xEE.  A budu vědět v případě ukončení, kde se (kdzž to bude lineární) nebo které bloky jsou "neposkvrněné čtením"

Poradíte, nakopnete, jak začít, jaké klíčové konstrukce programátorské použít?

A hlavně , jaký algoritmu výpočtu otisku bloku zvolit, ideálně nějaké funkce z knihovny jazyka, ale nic jako CRC jsem v bashi nenašel. A zda zůstatu u bashe.

[Reklama]

[RDa]

1) co to mas za podivny hw? u me 5.773GB se zpracuje za 11.679s z disku, nebo 10.222s z pameti, cteni z disku (pole): 6.790s (Xeon E3-1220 v6 @ 3.00GHz):

Kód: [Vybrat]

disk cp do shm: 850 MB/s
md5sum z disku: 494 MB/s
md5sum z ramky: 564 MB/s
2) k cemu to ma slouzit? plna 00/FF jakozto identifikovat nealokovane misto.. bude lepsi pouzit nastroje typu dumpe2fs/dumpexfat, kde zjistis obsazene bloky primo

3A) poor man paralelizace v bashi - rozdel problem na cteni a zpracovani, cteci "vlakno" bude ladovat bloky linearne z disku do buffer poolu /dev/shm (pocka to pri urcitem naplneni) a vypocetni "vlakna" budou brat tyto bloky z poolu a delat nad nima operace. Podle toho jak chytre to napises, lze dostahnout 100% vytizeni cpu, jen si dej pozor na to, ze vysledky muzou padat out-of-order, takze je dobre drzet asociaci s indexem.

3B) Pokud netrvas na 100% dokonalosti, muzes to naskriptovat nevlaknove: nactes NCPU * BLOCK do devshm skrze DD, pak pustis paralelne NCPU instanci  echo $gid:$id:`dd skip=$id bs=BLOCK | md5sum`, pockas si s wait az vsechny dobehnou a jedes dalsi blok. V te paralelni skupine jiz muze byt prefetch na dalsi skupinu bloku, po wait to jenom prejmenujes a jede se cyklus dokola.

u 3A/3B bude propustnost systemu omezena tim, co je horsi (cpu nebo disk)

[NeroLama]

Kdysi dávno jsem o  něčem podobném přemýšlel v rámci forenzní analýzy obsahu disku. Nakonec to kvůli nutnosti analyzovat data na úrovni sektoru(512)  nebo fileclusteru nedávalo smysl. Takže se dělal a asi i stále děla hash přes celý disk, třeba md5tee. Ale třeba tvoje zadání je jiné. ? 

[_Jenda]

Potřebuješ jedno vlákno co bude číst sekvenčně a přečtená data rozhazovat dalším vláknům ke zpracování, zejména pokud je to rotační disk. Pokud je to SSD tak by 10MB bloky asi prošly, jenom to možná rozbije readahead, a možná je i 10MB dost na to abys mohl na každý blok forknout proces a otevřít soubor, ale bude to pořád trochu neoptimální.

Ale pokud ti jde jenom o kontrolu "jsou to nuly | jsou to jedničky | spočítat jednoduchý hash" tak by tohle vůbec nemělo být potřeba, protože alespoň trochu rozumná implementace poběží i v jednom vlákně tak rychle, že bottleneck bude ten disk.

Jak tu paralalizaci řešit? Dá se to nějak v bashi elegantně řešit nebo na  to je lepší si napsat skript v rustu, perle, ruby, pythnu?

Pokud budeš data zpracovávat ručně (custom funkce co vyhodnotí ty nuly | jedničky | hash) tak to určitě musí být v něčem rychlejším. Dá se dělat načítání v Pythonu a počítání v C (https://www.abclinuxu.cz/blog/jenda/2021/2/python-c-a-cffi) ale ta omáčka kolem výpočtu bude triviální read, takže bych to psal celé prostě v C (https://www.abclinuxu.cz/blog/jenda/2021/9/nacitani-dat-v-c-read-vs.-fread)

Myslím že by ti to mohl kompilátor dostatečně zoptimalizovat, každopádně na uvedené statistiky jsou intrinsics https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# - _mm_and_ps (jedničky), _mm_or_ps (nuly), popcount… A taky tam je CRC.

[Ħαℓ₸℮ℵ ␏⫢ ⦚]

2 ) Ano,  zjistit mapu obsazeného místa. Čili  0000 a FFFF by mohlo stačit. S nějakou rozumnou granularitou (celý disk 5TB je hrubé , 4096b by moslo stačit, ale i 1MB nebo 4MB by splnily účel, možná  1GB).

Abych viděl, kde je hluché místo a kde by mohlo být něco neprázdného. V podstatě taková forenzní před-analýza

Zkuste ale potvrdit mou domněnku, že (nevimjaké) filesystémy si nějak značkují disk, že  třeba při formátování (quick/pomalé?) třeba na každé 4GB zapíšou 1 cluster (16kB?) nějakého kontrolního bloku....

1) DISK:240 MB/s
 tak i7 by asi zvládla stovky MB/s, ale chtěl jsem to nechat běžet (kvůli komfortu, hluku, počtu adaptérů v zásuvce) na armovém 8jádru /bigg.little 4+4/ nebo ještě lépe na NASu (1.2GHz ARM 4jádro), kvůli tomu že NAS potřebuje 1 DC zdroj  a disk v něm je "zadarmo", ale tam je čtení asi omezené na 160 MB/s
Nemám totiž (ani jeden) normální počítač se SATA slotem 3.5", ale mám aspoň 3.5 USB 3.0 rámeček, přijaltených 220MB/s a možná i víc
Holt asi budu muse určit prioritu, nechci aby mi to hučelo, ale zase jestli to místo dne bude trvat tři dny by mi vadilo.

Filesystém na tom asi není žádný, resp NTFS (přeformátovaný, prázdný)
Vím, a dávám si máslo na hlavu, za ten měsíc jsem to mohl mít hotové i 20 MB/s...



Potřebuju to udělat jen jednou, nebudu to opakovat. Nemusí to ani být nějaký well-known známý algoritmus mapování  (pokud něco takového existuje)

[Reklama]

[kvr kvr]

shell je na paralelizaci peklo.

Buď Java nebo python (python je taky s otazníkem, ale pokud bude kód mimo GIL, tak asi půjde).  Řešení v Java:
1. Namapovat celý disk do paměti, případně po částech (celý v základní Java nepůjde - má limit 2GB).
2. Vytvořit Executor.
3. Tlačit do do Executor jednotlivé tasky (podle bloků) a omezit je počtem CPU, případně mírně vyšším v závislosti na zpoždění IO.  Tasky budou počítat MD5 nebo kontrolovat nuly apod.
4. Ve správném pořadí vyhodnocovat výsledky (zapsat je do výstupu nebo cokoliv) a cpát do Executor další bloky.  Kdysi jsem řešil podobný problém a publikoval: https://github.com/dryuf/dryuf-concurrent/blob/master/src/main/java/net/dryuf/concurrent/executor/CapacityResultSerializingExecutor.java
5. Čtení z disku můžou dělat přímo ty tasky a jít přímo po bytech, místo, aby četly bloky do další paměti.  Podle overhead může být kontraproduktivní, záleží na JVM, jak moc to zoptimalizuje.
6. Alternativně, pokud by IO bylo špatné v nesekvenčním přístupu (staré HDD), tak v takovém případě může být lepší načíst celý blok v hlavním vláknu.

Jestli dobře počítám, tak při 50 MB/s, 4 jádra a 5 TB disk, celá věc proběhne za 25000 s, tedy zhruba 7 hodin...?  I v jednom vlákně půjde "jen" o 1 den.

[Jan Fikar]

shell je na paralelizaci peklo.

Existuje taková pomůcka GNU Parallel, když to má být paralelní v shellu. S výhodou se dají použít třeba funkce v bashi.

https://www.gnu.org/software/parallel/

[RDa]

2 ) Ano,  zjistit mapu obsazeného místa. Čili  0000 a FFFF by mohlo stačit. S nějakou rozumnou granularitou (celý disk 5TB je hrubé , 4096b by moslo stačit, ale i 1MB nebo 4MB by splnily účel, možná  1GB).

Ja bych se drzel 4KiB granularity, protoze to je nejbeznejsi cluster size, ale taky zavisi na partition table - pokud neni 4K/1M aligned tak jakekoliv rozdelovani disku na bloky ztraci smysl, protoze vam to bude pretejkat o sektor.

5T/4Ki je  < 1.25G zaznamu * 16byte (md5) =  < 20 GB
5T/1Mi je  < 5M zaznamu * 16 byte =  < 40 MB
 
Pokud bych mel misto, tak bych resil oboji zaroven (na jedno cteni disku dva vypocty). Nic horsiho nez md5 (treba crc32) bych asi nepouzil, at to negeneruje false positives.

Prakticky ale je rozdil mezi "obsazenym mistem" a "mistem jednou pouzitym".

Tech 20GB pri 4KiB blocich se jeste pohodlne vejde do 32GiB ram pro nasledne bitmapovani - jen ten "obrazek" bude ponekud vetsi (cca 35355^2 px)

[RDa]

Abych viděl, kde je hluché místo a kde by mohlo být něco neprázdného. V podstatě taková forenzní před-analýza

:
:

Filesystém na tom asi není žádný, resp NTFS (přeformátovaný, prázdný)

Zde bych doporucoval namisto checksumu delat odhat typu clusteru - a pro prvni pass postaci identifikovat ty, co jsou adresare (obsahujici zaznamy o souborech).

Jako NTFS ctecku jsem si psal v PHP tak chapu ze nekdo potrebuje/chce samodomo udelany reseni...
... ale pro ostatni pripady staci udelat klon disku a pustit nejaky recovery soft a la testdisk :-)