IDFS je distribuovany filesystem s prvkami p2p ktory by mal byt schopny zdielat data medzi nodami uplne
transparentne,redundante a bezpecne. Cielom clanku je predstavit ciastocny navrh resp
myslienky ku ktorym som dospel zhruba pol rocnom uvazovani,nejakymi predstavami a tym
ze sem videl ako sa zdielaju data v Ynete :).
Ako z nazvu vypliva, mal by byt implementovany ako aplikacia nad Infernom a uz existujucou
melua grid sietou. Je to vlastne aplikacia Melua grid projektu. Vdaka Infernu mame zabezpecene
ze to bude fungovat na roznych pocitacoch.
Ked som pracoval na Melua grid projekte vedel som ze bude potrebny nejaky filesystem ktory
umozni vyuzit nevyuzite miesto na diskoch. V sieti Ynet na intrakoch FEI/FIIT ktora
ma pripojenych cez 1400 userov v ramci LAN je ten problem ze data su casto krat zdielane
na roznych pocitacoch, tj ze tie iste data su na roznych pocitacoch. Vacsinou sa jedna
o multimedialny obsah ktory len zabera zbytocne miesto. Taktiez bol casto problem ze
v momente ak bol dany pocitac vypnuty alebo sa vypol pocas kopirovania tak sa k datam
uz nedalo dostat.
Napadlo ma ze by bolo skvele mat nejaky sietovy distribuovany filesystem ktory by vedel toto:
- umoznit dostat sa k datam ktore su ulozene na nedostupnych pocitacoch
- decentralizacia, nesmie mat ziadny centralny bod (takze vlastne policia nema co vziat :)
- transparentne sifrovanie a kompresia
- pristupny z roznych OS (vdaka Infernu)
- klasicke unixove prava
- ma sa tvarit ako dalsi sietovy disk (bud Z: alebo napr. /mnt/remote)
- neobmedzenu velkost suborov, adresarov a podobne
- snapshoty
- linky
- neukladal viac krat ten isty obsah
- - ACL *
- - quota *
* - su veci v ktorych este nemam jasno
a to vsetko by mal stihat tak aby si clovek co najmenej tieto veci vsimol, teda rychlo :)
V praxi by to malo vyzerat takto:
Pripojite sa so svojim pocitacom do siete s tym ze idete robit s datami na idfs. Zacnete
tam kopirovat svoj novy film ale kedze uz to spravil vas kamarat skor tak sa len vytvori
odkaz na tie iste data (rozlisuju sa podla SHA-1 hashu) cize sa usetri par stovak MB. V
tom si spomeniete ze vo vasom domovskom adresari sa nachadza projekt ktory treba dokoncit.
Vojdete do svojho domovskeho adresara ktory ma nastaveny bit na sifrovanie takze cokolvek v
nom zapisane alebo citane sa sifruje. V nom sa nachadza adresar s vasou pracou. Lenze
potrebujete projekt skompilovat so suborom ktory bol pred tyzdnom zmazany. Ziaden problem
kedze adresar projektu ma nastaveny aj snapshot bit. Specialnym prikazom poprosite aby
vam filesystem vybavil stav suboru v case pred tyzdnom no a skompilujete... :). Ze medzi tym
vypadla tretina pocitacov na ktorych mate poukladane data ani nespominam :).
Realizacia
1.Fungovanie na roznych operacnych systemoch
Kedze Inferno OS funguje ako aplikacia nad roznymi OS nie je problem ho rozbehat nad akymkolvek
Unixom, Windowsom alebo Plan9. Inferno komunikuje protokolom Styx ktory uz vie citat linux a
nie je problem si jeho namespace primountovat pod linuxom. Pod windows este take nieco nie
je ale urcite by sa to dalo spravit kedze existuje Styx kniznica. Vdaka tomu by mal byt
pristupny uplne transparentne roznym aplikaciam.
2. Ako chces zabezpecit dostupnost dat na nedostupnych pocitacoch ?
Hadam toto je najlepsia featura celeho systemu. Ako sa dostat k tym datam ?Jedna moznost je takzvana replikacna moznost tj ze ten isty subor sa nakopiruje na co najviac pocitacov a budete dufat ze bude aspon jeden dostupny. Preco je tato metoda nevhodna ukazem dalej. Je tu lepsi sposob a ten je
Information dispersal algorithm (IDA: http://www.blackhole.sk/~v92/dfs/p335-rabin.pdf).
IDA dokaze subor rozdelit na n casti a to tak ze povodny subor sa da zrekonstruovat len pomocou m
casti a to tak ze
m < n
pricom celkova velkost mnozstva ulozenych dat je rovna
n/m * |F|, kde |F| je velkost suboru
Vyhoda a zaroven aj nevyhoda je ze ak mate m - 1 casti tak nemate ziadnu predstavu ako vyzeral
povodny subor ani ze polovicnu :).Neda sa to.
dajme si priklad:
Mame subor velky 10 000B a siet ktora pozostava zo 14 pocitacov. Subor rozdelime cez IDA na 14 casti a to tak ze nam staci 10 roznych z nich aby sme povodny subor zrekonstruovali.Skutocne mnozstvo dat ktore musime ulozit do idfs je:
(n/m) * |F| = (14/10) * 10 000B = 14 000B
a velkost jednej casti bude
|F|/m = 10 000B / 10 = 1000
Mnozstvo dat ktore musime ulozit navyse je 40% z povodneho suboru. Staci nam vsak len 10 dostupnych lokacii teda pocitacov (ak berieme ze jedna cast je ulozena na jeden pocitac) a subor sme schopny zrekonstruovat.
Pri replikacnej metode je mnozstvo dat ktore musime ulozit 14 * 10 000 teda o 1400% viac ako pri IDA. Avsak nam staci jeden pocitac dostupny. Ale to je to prave comu sa snazime vyhnut pretoze ak by pri kopirovani nastalo prerusenie spojenia alebo pad pocitaca, data by boli znova nedostupne.
IDA v tomto jednoznacne vyhrava, nielenze jej staci 40% redundancie navyse oproti 1400% ale ak padne pocitac z ktoreho tahame aktualnu cast tak nam staci najst iny pocitac ktory obsahuje cast ktoru este nemame a stiahneme. Navyse je velka vyhoda v tom ze parametre n a m sa daju nastavit takze je mozne dynamicky upravovat redundanciu podla potrieb.
3. Ako chces zriesit decentralizaciu ? Budes mat problem s konzistenciou dat.
Ak nemate centralny bod tak cely system sa stava automaticky robustnejsim avsak je nachylny
na nekonzistenciu. V nasom pripade to znamena ze by sa mohlo stat ze nebudeme mat konzistentne data
a informacie na nodach. Koli korektnej adresarovej strukture je nutne aby vsetky nody mali rovnake
informacie o tom ktory subor je otvoreny kym, na ktore data sa odkazuje subor ci na stare alebo nove
a pod. V prvom rade ide o to ze ak si chceme otvorit nejaky subor mozme sa pozriet do svojej tabulky
otvorenych suborov (slovo mozme je namieste, vysvetlim neskor).Ak sa da otvorit tak mozme tym
oboznamit dalsie stroje. Na to su dva sposoby:
A) notifikacia linearne - prechadzat zoznam vsetkych strojov a hovorit im ze ste si otvorili subor. To je
celkom fajn ale predstavme si ze mame 1400 strojov a kazdy chceme informovat. Nielenze zbytocne
prenasame tie iste data (v tomto pripade 1400x) ale trvalo by to aj dost dlho. Proste blud.
Preto musime pouzit fintu :).
B) notifikacia cez binarny strom - nam umozni zrychlit notifikaciu vsetkych strojov o niekolko radov a zabezpeci ze sa nemusia posielat vzdy tie iste data. Riesi sa to cez taky kvaaazi centralny bod. Totizto cely Melua grid projekt vyuziva takzvany registry server ktory zbiera informacie o tom ze ktora noda cim disponuje a hlavne kde. Treba si uvedomit ze idfs je jedna z aplikacii ktora vyuziva prostredie Melua grid projektu a ze podobnych aplikacii moze byt viac resp. staviat jednu nad druhou. Ale to je uz buducnost a odbehol som, takze ten registry server nam poskytne zoznam nod ktore su v gride. Mozme si to predstavit ako pole nod ktore si mozme zoradit najlepsie podla dlzky uptimu nod. Tj prva bude ta co je v systeme najdlhsie a posledne tie co sa prihlasili len teraz. Kto pozna binarne stromy vie ze sa daju pekne reprezentovat aj cez pole, takze priamy dosledok je ten ze sa nam automaticky s pribudanim a ubudanim nod rekonstruuje binarny strom prakticky zadarmo. Ale to este vzdy nie je toto co je na tom najlepsie. Najlepsie je ze ak prvej node v zozname oznamime ze otvarame subor ta to posle dalsim dvom strojom podla tohto pravidla:
Hn -> H2n & H2n+1
H1 -> H2 & H3
H2 -> H4 & H5
H3 -> H6 & H7
Dosledkom je ze cely strom prejdeme za cas log n (so zakladom 2) cize pre nas pripad (1400 pocitacov)
to bude log2 1400 = 10.39. Je to preto lebo notifikacia prebieha paralelne a preto je pre nas dolezita len vyska stromu. Cize ak by notifikacia jedneho stroja trvala jednu sekundu tak tymto sposobom
notifikujeme 1400 pocitacov za cca 11 s a cas nam rastie logaritmicky a tym prvym za 1400 s nam cas rastie linearne :).
Co vsak v pripade ze niekto nabehne a vezme prve tri nody z tabulky? Nuz nastane pripad ze korenom stromu sa stane stvrta noda ktora ma najaktualnejsie data pretoze su nody zoradene podla _uptime-u_. Takze navzdory tomu ze mame centralny bod tak ho aj zaroven nemame pretoze v pripade jeho vypadku sa automaticky cely system bude odkazovat na dalsi za nim u ktoreho je predpoklad ze bude mat najkonzistentnejsie data kedze je tu najdlhsie. Ono mali by mat vsetky nody v systeme ale v pripade pochybnosti je mozne sa pozriet ako to vyzera v korenovej node a upravit sa. Tento fakt aj suvisi s tym ze informacie o adresarovej strukture sa nikam neukladaju.Je to preto aby nevznikal bordel a nove nody, resp nody ktore sa hlasia do systemu si stiahli najaktualnejsi stav fs od korenovej nody (pretoze ta je
tu najdlhsie). Informacie o adresarovej strukture su ukladane do ramdisku.
4. Ako sa ukladaju data ? ...alebo ked adresar je suborom a subor adresarom
Ukladat data na disk treba tiez nejakym systemom pretoze ukladat ich hocjako tak to by bola riadna habadura ze. Najlepsie je aby sme co najmenej museli kodit takze sa pozrieme co nam ponuka operacny system Inferno. Po blizsom nahliadnuti zistime ze kniznicu na vytvorenie a manazment databazy. To je ono. Databaza je dedikovana na vyhladavanie,ukladanie a vyberanie dat a vobec na pracu s nimi. Konkretne tato
db funguje na principe hashovacej tabulky. Kazdopadne je dolezite ze nam ponuka jednoduchy interface na pracu s datami.
Ale akymi datami ?
Co su tie data ? Data su vlastne bloky velkosti 8kB ktore sa ukladaju do databazy. Tieto bloky mozu byt rydzo datove alebo adresarove, tj ze definuju adresarovu strukturu. Datove bloky sa ukladaju na disk kde sa nimi aj pracuje, kdezto adresarove sa ukladaju len do ramdisku koli tomu
aby v pripade vypadku sa nacitala vzdy ich najaktualnejsia verzia. Aku maju strukturu tieto bloky si ukazeme na tejto scheme:
Blok:
0....................191................................8191B
________________________________________________________
| hash | attr | hash1 | hash2 | hash3 | ... | hash400 |
--------------------------------------------------------
hash - 20B dlha sekvencia bajtov vygenerovana SHA-1
attr
- size - 64b cislo udavajuce velkost suboru
- mode - pristupove prava, typ bloku:dir,file...
- atime - cas pristupu
- mtime - cas modifikacie
- name - meno suboru alebo adresara ale ako string
- uid - meno uzivatela
- gid - meno skupiny
- mid - meno uzivatela ktory naposledy zmenil subor
Atributy este nemam celkom premyslene a je velmi pravdepodobne ze sa este vela veci zmeni. Spomedzi vsetkych moznych blokov v celom idfs ma len jeden jeden jediny jedno vysadne postavenie a to je ROOTBLOCK. Tento rootblock je strukturov uplne taky isty ako ine bloky len s tym rozdielom ze sa pevne vola / resp. na jeho identifikaciu sa pouziva hash pismena /. Najlepsie ako to cele funguje si ukazeme na priklade ked sa nova noda pripoji do systemu.
V tomto momente sa stane toto:
1. noda vysle spravu STAT / korenovej node binarneho stromu ktora mu posle rootblok a ak nie tak potom ine (spominate na notifikaciu otvorenych suborov?)
2. prebehne nejaka zakladna kontrola integrity a pravosti
3. od 192. B zacinaju v bloku hashe, kedze hash ma 20 B a mame este 8000B mame celkovo 400 hashov
4. noda si zacne od systemu pytat bloky s tymito hashmi. tieto hashe sa mozu odkazovat na dalsie adresare a subory
5. hash400 moze byt odkaz na blok v ktorom su dalsie hashe takze mame neobmedzene mnozstvo poloziek v korenovom adresari (aj vsade inde)
Predstavme si ze hash1 je odkaz na subor. Noda si vypyta blok s hashom hash1 a ide rozparsovat ale tu nastupuju iste pravidla ktore urcuje atribut size.
0 < size < 8 KB (to je 8000B a nie 8192 B teda 8 KiB!!!)
0.............191................................8191B
___________________________________________________
| hash | attr | data |
---------------------------------------------------
to znamena ze ak je subor dost maly tak nebude prechadzat ani IDA ale data sa ulozia priamo do bloku co sposobi ich okamzitu dostupnost.
8 KB < size < 32 MB
0............191.............................................................8191B
_______________________________________________________________________________
| hash | attr | hash1_block | hash2_block | hash3_block | ... | hash400_block |
-------------------------------------------------------------------------------
jednotlive hashe sa odkazuju na bloky ktore su uz datove, tj priame adresovanie
a prechadzaju IDA transformaciou.
32MB < size < 12800 MB
0............191.....................................8191B
_______________________________________________________
| hash | attr | idab1 | idab2 | idab3 | ... | idab400 |
-------------------------------------------------------
jednotlive hashe sa odkazuju na takzvane IDA bloky ktore su velke 32 MB kazdy.
A zase, ak subor bude vacsi ako 12800MB potom hash400 nebude odkazovat na IDA blok ale na dalsi blok kde budu odkazy na dalsie IDA bloky. A tak do nekonecna :).
A preco prave 32 MB ?
Problem je v tom ze ak by sme si chceli pozriet subor ktory ma 12800MB ktory by bol pretransformovany cez IDA museli by sme ho jednak cely stiahnut k sebe a po druhe potrebovali by sme cez 13 GB RAMky na transformaciu. Dalo by sa to cez disk ale je to hodne neprakticke. Tento sposob vlastne rozdeli vstupny subor alebo stream (je to jedno) na casti velke 32MB ktore su z pohladu IDA nezavysle preto IDA bloky. Mozu byt transformovane nezavisle na sebe. Cize ak by sme si pustili z idfs film staci nam stiahnut prvych 32MB a mozme pozerat zatial co na pozadi by sa uz stahovali dalsie bloky.A v momente keby sme chceli skocit na polovicu tak by sa na zaklade offsetu vypocitala poloha hashu v bloku, ten by sa stiahol, transformoval a slo by sa dalej. Idealne by bolo aby kazdy pocitac v sieti obsahoval aspon jednu cast z kazdeho IDA bloku.
Snapshoty
V pripade ze by bol bit snapshot aktivny tak nezavysle na tom ci je to blok na subor alebo adresar dialo by sa toto:
0....................191............................8191B
_______________________________________________________
| hash | attr | snap1 | snap2 | snap3 | ... | snap400 |
-------------------------------------------------------
kde snap* su hashe na prvy blok adresara alebo suboru v nejakom case podla mtime.
snap1:
0....................191.....................................8191B
_______________________________________________________________
| hash | attr | hash1 | hash2 | hash3 | hash4 | ... | hash400 |
---------------------------------------------------------------
snap2:
0....................191..........................................8191B
____________________________________________________________________
| hash | attr | hash1 | hash423 | hash1234 | hash4 | ... | hash400 |
--------------------------------------------------------------------
Takze akakolvek zmena by sa prejavila len tym ze by sa do bloku len pridavali odkazy ktore by zachytavali
inkrementalne zmeny. Defaultny by bol samozrejme ten posledny.
Ale je velmi pravdepodobne ze cela sekcia sa bude musiet upravit.
5. A co bezpecnost ?
Pri navrhu som vychadzal z toho ze svet neni len ruzova zahrada a cajove party. Uvedomil som si ze zriesit bezpecnost pri takomto systeme je pomerne narocne zvlast koli tomu ze si ukladate svoje data na stroje inych ludi co moze byt pre niekoho problem.V prvom rade tu mame sifrovanie ktore si musi kazdy user nastavit sam tam kde potrebuje, druha vec je ze ako som uz vyssie spominal IDA ma tu vlastnost ze ak mate m - 1 blokov tak nemate ziadnu informaciu o tom ako vyzeral povodny subor, suvisi to totizto z maticami a pravidlami s nasobenim medzi nimi. Samozrejme je sifrovanie sifrou IDEA medzi nodami ktore zabezpecuje uz samotne Inferno/Melua grid projekt.
Taktiez je dolezite aby neprebehlo neautorizovane citanie zo systemu. Totizto ide o to ze ak chcete
z nejakeho suboru citat musite o tom upovedomit vsetky ostatne nody takze si ho vlastne zamknete pre seba (za predpokladu ze mate na to pravo). Kazda noda si o tom vedie zaznam ze kto ma co otvorene, takze ak pride nejaky dotaz ze chcem takyto a takyto hash a dotycny nie je evidovany ze ma
otvoreny subor tak ma smolu lebo ziadne data nedostane a jedine co dostane je maximalne -EPERM. Na to aby ste si mohli otvorit nejaky subor potrebujete samozrejme prava, a zase...ak tie prava nemate tak si nody nezaznamenaju ze ste otvorili subor a mate smolu. Takze s kludom moze nabehnut nejaky
haxor do systemu s tym ze si dumpne cely idfs na svoje diskove polia (hi wire ! :) a s upravenym idfs klientom ktory neriesi svoju tabulku otvorenych suborov.Dostane nic.Nody mu nedaju ani bajt. A podobne to bude asi aj s quotami. Totizto kazda kontrola otvorenia a prav a podobne prebehne hlavne s lokalnymi tabulkami ktore sluzia len na urychlenie procesu, ale program ich nemusi vobec pocuvat.
6. Problemy
Najvacsou prekazkou ale zase aj plusom zaroven ze sa to cele kodi v programovacom jazyku Limbo ktory je urceny na concurrent programming takze ako stvoreny na pracu na multithreadovane aplikacie. idfs ak bude tak bude silno multithreadovy takze vytazi tie dual cory a quadcory a mozno aj gpucka na maximum :).
Problemom je zaroven aj algoritmus IDA ktoreho implementacia pod Infernom je pomerne pomala resp cely algoritmus je dost pomaly takze kodovanie 32 MB suboru trva skoro 48 sekund (ale ja mam 1 GHz cpu :). Ale je tu mnozstvo ciest na optimalizaciu takze casom by sa to mohlo o hodne zlepsit. Dalej je celkom
nedobre ze nemam este v mnohych veciach celkom predstavu resp. sa veci menia a casto je zdrojom problemov IDA :).
6.1 Ked kapacita idfs = f(uptime_nod)
IDFS ma jednu zvlastnu vlastnost...jeho kapacita nerastie ani tak s mnozstvom nod ale skor s mnozstvom pocitacov ktore su online dlhsie podla isteho kriteria u ktoreho este nemam celkom predstavu ako vyzera (bude to mat nieco s uptimemom za rok v hodinach :). Pretoze mozme rozsievat
bloky kade tade po nodach ale co ak prave ta mnozina pocitacov na ktoru sme to rozsiali tu nebude ? Cyklycky prechadzat 1400 pocitacov a davat im vzdy nejaky blok ? Asi nie... . Ukazeme si na
tomto obrazku.
ako vidite z tejto statistiky ktoru som spravil za vikend v ynete (kedy je na sieti najmenej ludi) vypliva ze bolo za kazdych okolnosti a v kazdu hodinu online minimalne 100 pocitacov. To znamena ze ak chceme garantovat 100% dostupnost dat je najlepsie ak budeme data v idfs ukladat hlavne na tychto 100.
Ak je ich viac tak sa nic nedeje lebo ostatne pocitace mozu mat len take bloky ktore su na tych hlavnych 100. Za tychto okolnosti budeme mat vzdy dostupnych m ida blokov (teda ak by sa nestala nejaka katastrofa, ale to je uz potom userom asi nejaky idfs ukradnuty ze :) lebo budu len na tych 100 strojoch co su vacsinou online. ked si predstavime ze kazdy stroj da idfs povedzme 100 GB priestoru, tak mame 10 TB uloziste dat ktore vysi nad celou sietou ako oblacik na cisco
obrazkoch :).
7. Zaver
Tento text berte len informacne. Napisal som to preto aby som oboznamil inych ludi so svojimi myslienkami a aby to co mam po roznych potrhanych papieroch a zositoch popisane dal na jedno miesto. Je toho este viac ale myslim si ze toto pre zaciatok staci. Feel free to comment.
len chcem este upozornit ze to je len proof-of-concept nic vytesane do kamena. hej ? :)
cita sa to pekne, ale ma to niekolko dost podstatnych bodov inkonzistencie, ktore su u distribuovanych systemov vcelku bezne a stretne sa s nimi skoro kazdy system:
- system neriesi subehy (co ak dvaja ludia simultanne kopiruju rovnake data do systemu? ak zmeny nebudu commitovane, tak sa tam proste nakopiruju 2x, riesi sa tato situacia?)
- system znizuje redundanciu dat tym, ze robi symlinky na existujuce data, ak sa zisti, ze kopirovane data su identickou kopiou inych uz existujucich dat. Dovolim si tvrdit, ze toto sa da s rozumnym mnozstvom overheadu a bez silenych bitmap redundancie riesit jedine na WORM systemoch (Write Once Read Many). Predstav si, ze vytvoris subor, napriklad image bootovacieho disku. Niekto iny potom zacne do IDFS kopirovat ten isty subor, IDFS zisti, ze ten subor uz existuje, tak ten novy len nalinkuje na ten prvy. Potom majitel povodneho suboru ten image zamontuje na remotnej masine s write pravami cez loopback a image zmeni? Bude system o tom notifikovany a vykona nejaku obdobu copy-on-write a tie zmenene bloky oddeli?
- ukladat adresarovu strukturu do ramky je volovina, kym jej zmeny v binarnom strome okamzite nedistribuujes dalej. ak takyto stroj zostrelis, informacie sa stratia a system sa rozhasi.
- priame adresovanie blokov nad hash cislo 400 je koncepcna vada.
- ten system snapshotov mi nejako celkom nie je jasny. Podla coho sa da do kopy jeden commit do filesystemu tak, aby ta revizia suboru bola konzistentna nie len voci filesystemu, ale aj voci aplikacii?
Registry server by mozno ani nemusel existovat, ak by sa vsetky stroje zorganizovali do binarneho stromu a pamatali by si cestu od seba k najvyssiemu stroju a identifikaciu svojho surodenca. Nasledne by sa dal strom nejakym algoritmom automaticky balancovat a pomocou HA-podobnych algoritmov zabezpecit, ze ak lubovolna noda vypadne, tak sa strom automaticky zrekonstruuje (najneskor v case prvej poziadavky, ktora by sa len trocha opozdila). Zanikla by tak zavislost na registry serveri.
Co sa tyka toho, ze IDA je v Inferne naprogramovana v jazyku Limbo. Dost ludi vie, aky mam nazor na programovanie algoritmov, kde sa pozaduje vysoky vykon v jazyku, ktory nema ponatie o tom, ako vyzera HW, na ktorom bezi. Jednoducho povedane: napisat v Ccku, alebo rovno v assembleri pre kazdu platformu, kde to ma bezat, defakto ak ma Limbo nejaky solidny pamatovy model, by mala stacit jedna implementacia IDA pre kazdy typ HW, na ktorom to ma bezat (co sa v sucasnej dobe aj tak obmedzuje len na x86 a x86_64, co ma v C (skoro) rovnaky kod).
Je zarucene, ze dostupnost celeho suboru po rozdeleni do 32MB blokov bude po rozdistribuovani IDA framgnetov rovnaka, ako keby sa subod nerozdelil? Narazam na to, ci si skumal, zda-li distribucia n blokov vzniknutych po IDA transformacii nebude rozdelenim suboru na 32MB bloky ovplyvnena natolko, ze by sa mohlo stat, ze budu bloky do siete rozhodene tak, ze pri vypadku niektorych strojov bude system nachylnejsi k fatalnemu vypadku, nez u inych strojov.
A posledna vec: Zaznamy v DB ukazuju na 32 MB bloky. Kde je tabulka transformacie 32MB blokov na n IDA blokov?
---
Cuchat s nadchou, to je ako sniffovat bez promiscu.
takze zacnem
> - priame adresovanie blokov nad hash cislo 400 je koncepcna vada.
a ani sa to tam nerobi, ak treba ulozit viac dat ako dokaze adresovat 400 blokov musi sa vytvorit novy
IDA blok a potom sa uz zmeni ten prvy blok na
0............191.....................................8191B
_______________________________________________________
| hash | attr | idab1 | idab2 | idab3 | ... | idab400 |
-------------------------------------------------------
kde idab1 su hashe ktore sa odkazuju na jednotlive ida bloky a kazdy ida blok obsahuje vlastne toto:
0............191.............................................................8191B
_______________________________________________________________________________
| hash | attr | hash1_block | hash2_block | hash3_block | ... | hash400_block |
-------------------------------------------------------------------------------
a to uz umoznuje adresovat 12800MB pri dvoj urovnovom adresovani. to by malo na vacsinu suborov
stacit :).
> - system neriesi subehy
dobry postreh, pri tomto navrhu to vyzera na race condition. keby kopirovali naraz tie iste data tak potom sa to jednak ulozilo 2x a druha vec je ze system by si vsimol jedine toho kto by s kopirovanim skoncil posledny. je to preto lebo sa data najprv nakopiruju a az potom sa posle do siete vyhlasenie ze ako sa k tym datam dostat
> - system znizuje redundanciu dat tym, ze robi symlinky na existujuce data,
v tom nevidim problem, skratka spravis SHA-1 hash suboru ktory ides skopirovat a porovnas ho ci uz sa taky hash v adresarovej strukture nenachadza (to bude znamenat ze tam neni identicky subor).kazda noda si robi kopiu adresarovej struktury k sebe a sleduje zmeny a spravanie na sieti tj ze kto otvoril subor,zatvoril a pod a podla toho si upravuje tabulku tak aby bola vzdy aktualna. ak by bol tak sa spravi to ze sa budu odkazovat na tie iste bloky len hlavy budu mat ine. take siamske dvojcata. s tou neskorsou zmenou je pravda ze nieco ako copy-on-write je nutnost, mozno sa to bude dat zriesit nejako so snapshotmi elegantne.
ad adresarova struktura) preto je dolezite aby bola na ramdisku aby tie data boli najaktualnejsie, aby sa neplietli uz stare data. napriklad ked je noda vypnuta tak za ten cas sa moze stat x operacii ktore nezastihne. ramdisk nam jednak umozni rychly pristup ale zaroven aj sa vymaze sam ked sa vypne. ked sa noda prihlasi tak si od korenovej nody v binarnom strome stiahne najaktualnejsii stav fs, tj kto ma kde otvorene subory a aj adresarovu strukturu.
> - ten system snapshotov mi nejako celkom nie je jasny. Podla coho sa da do kopy jeden commit do
> filesystemu tak, aby ta revizia suboru bola konzistentna nie len voci filesystemu, ale aj voci aplikacii?
zatial som nad tym neuvazoval. podla tohto navrhu by sa tie zmeny prejavili az po zapise a close() pretoze
po nom by zase sa do siete vyhlasilo ze ktore bloky patria suboru. takze az po close().
> Je zarucene, ze dostupnost celeho suboru po rozdeleni do 32MB blokov bude po rozdistribuovani IDA
> framgnetov rovnaka, ako keby sa subod nerozdelil?
dobry postreh, je to celkom problem ale ktory by sa dal zriesit tak ze na vsetky nody co sa kopiruje by sa skopirovali casti z kazdeho IDA bloku. napriklad vsetky prve casti n ida blokov by sli na pocitac A, vsetky druhe casti na pocitac B a tak dalej. to by mohlo fungovat.
>A posledna vec: Zaznamy v DB ukazuju na 32 MB bloky. Kde je tabulka transformacie 32MB blokov na n
> IDA blokov?
zaznany v DB ukazuju na 8kB bloky, lebo to je zase tak :) 32MB blok prejde IDA, dostanem n casti, kazda ta casti ma velkost |F|/m ako pisem hore problem je ze to neni 8kB :). a kazda ta cast sa musi este rozbit do 8 KB velkosti aby sa napchali vsetky do jednej DB. v tomto este tiez nemam celkom jasno ako to spravit. najjednoduchsie by bolo aby |F|/m bolo 8KB ale to by potom tych casti muselo byt 4096 a ty by sme stravili dni kym by sa nieco na idfs skopirovalo cez IDA :)
> Co sa tyka toho, ze IDA je v Inferne naprogramovana v jazyku Limbo. Dost ludi vie, aky mam nazor na
> programovanie algoritmov, kde sa pozaduje vysoky vykon v jazyku, ktory nema ponatie o tom, ako
> vyzera HW, na ktorom bez
tu si skratka nevyberies, danou za vykon je to ze ti to bez uprav bezi vsade a zase nemusi to byt az take pomale. co som cital nejake testy tak sa uvadzalo ze limbo programy su o 50%-30% pomalsie ako tie napisane v C. nezatracoval by som zvlast tento jazyk prave koli jeho concurrent vlastnostiam ktore ho robia prave takym silnym do podobnych prostredi. je tu vsak moznost este implementovat IDA ako kniznicu a spravit do Inferna len rozhranie. tymto sposobom su dokonca implementovane veci ako pristup ku koprocesoru a podobne. co sa tyka rychlosti IDA ja osobne vidim este velky priestor na zrychlovanie, takze to by som ako tragediu az tak nebral
no ok, takze adresovanie blokov nie je priame, ale nepriame... to je uz ako - tak OK. Adresovanie rozsahov tuna asi neprichadza v uvahu...
riesenie subehov je podstatna vec, hlavne ak chces znizovanie redundancie zarucit, alebo ak bude na fakt, ze subor nie je vo filesysteme redundantny zalozene napriklad vyhladavanie, alebo alokacia blokov. (ak by sa napriklad neratalo s tym, ze jeden blok mozu mat 2 rozne stroje, tak by mohlo dojst k tomu, ze pri nespravne ohlavickovanych requestoch by sa uplne malformovalo telo suboru).
kym tam bude nieco ako copy-on-write, tak je to OK a da sa to pouzit aj mimo WORM systemu.
to akoze adresarova struktura celeho filesystemu bude ulozena LEN v ramdiskoch? takze ked prijdem, vyjebem poistku v hlavnom rozvadzaci pre cely Ynet, tak sa system rozhasi? Dost blby napad.
nuz, majme hypoteticky subor o piatich IDA blokoch velkosti 32 MB.
1. krok: subor vytvorim, cize mam 0. reviziu suboru, schematicky zaznacene:
[ 0 | 0 | 0 | 0 | 0 ]
2. krok: subor otvorim na prepis a urobim zmeny, ktore zasiahnu 2. a 3. IDA blok: vzninke mi teda 1. revizia bloku 2 a 3, schematicky zaznacene:
[ 0 | 1 | 1 | 0 | 0 ]
3. krok: otvorim subor znova a urobim take zmeny, ktore zasiahnu 4. a 5. blok, vznikne teda 2. revizia suboru so zmenenymi blokmi 4 a 5:
[ 0 | 1 | 1 | 2 | 2 ]
4. krok: otvorim ho znova na prepis a zmenim 3. a 4. blok, vznikne mi 3. revizia so zmenenymi blokmi 3 a 4:
[ 0 | 1 | 3 | 3 | 2 ]
ako to ale vidi filesystem? kedze on nejako nespaja dohromady jednotlive revizie, vidi to ako:
[ 0 | 1 | 2 | 2 | 1 ]
teraz ked odroluje druhu zmenu, dostane:
[ 0 | 1 | 1 | 1 | 1 ]
co sa mu ale javi ako jedna zmena, aj ked v skutocnosti prebehli zmeny 2 a teda sa k skutocnej revizii 1 suboru neda dostat.
V tomto bode je irelevantne, ze bloky skutocnej revizie 2 nemenili tie iste bloky, ako skutocna revizia 1, pretoze to, co vyzera (a dokonca aj je) konzistentne z pohladu filesystemu uz nemusi byt konzistentne z pohladu aplikacie. Tu povodnu reviziu 1 uz jednoznacne z tohto vyrobit nedokazes. Samozrejme sa daju vymysliet ovela masochistickejsie postupy zmien, ktore by ani pri vyluceni poziadavku na moznost kompletneho vykonania vsetkych urobenych zmien neboli voci aplikacii konzistentne.
Vytvarat pri revizii kopiu celeho suboru je zasa postavene na hlavu a v rozpore so setrenim miestom pomocou IDA.
"dobry postreh, je to celkom problem ale ktory by sa dal zriesit tak ze na vsetky nody co sa kopiruje by sa skopirovali casti z kazdeho IDA bloku. napriklad vsetky prve casti n ida blokov by sli na pocitac A, vsetky druhe casti na pocitac B a tak dalej. to by mohlo fungovat."
to zaklada predpoklad, ze vsetky cielove masiny maju volne miesto minimalne pre tolko dat, ktore sa na nich chystas ulozit, co je ale velmi krehky predpoklad.
Ono je to s tou absenciou alokacnej tabulky blokov tak, ze ti mozu v zasade nastat 2 moznosti:
a) pri neosetrenom subehu sa ti vo filesysteme moze najst napriklad jeden blok 2x, potom si ho cez broadcast vyziadas, oba sa zamknu, ale informacia o tom, ze ho ma od prveho stroja, bude prepisana informaciou o tom, ze ho ma, od druheho stroja, ty potom ten blok od druheho stroja releasnes a na tom prvom zostane zamknuty az do resetu stroja, popripade sa lockne cely filesystem, alebo ako to bude riesene. alebo ti 2 stroje vratia informaciu o tom, ze ten blok daju, ale cielova masina to pochopi ako notifikaciu o dvoch blokoch po sebe, takze sa obsah suboru posunie a uplne sa rozbije.
b) pri cakani na to, aby sa ti ozval ten, kto dany blok drzi, existuje nejaky timeout? je treba si uvedomit, ze pre jeden 32 MB blok budes potrebovat vyvolavat z filesystemu obrovske kvantum 8000B blokov. Tebe ich sice vsetky fyzicky netreba, ale aj tak musis pocitat jednak s latenciou, kym tych ( pre jednoduchost pocitajme s 10 KB blokmi) 32000/10 = 3200 requestov na vydanie bloku preleti celym systemom ( je sice pekne, ze requesty v strome pojdu paralelne, ale ty ich predsalen nemozes chrlit paralelne, ale musis seriovo ), co pri latencii povedzme 300 ms (ktoru sme realne namerali) v *krajnom pripade* znamena 3200 * 300 ms a to sa dostavas uz k extremnym hodnotam latencii. A ne ze ne. Plus este musi existovat nejaky timeout, ze co robit, ked sa ten blok naozaj nikde nenajde (dany stroj je off). Alebo ak sa blok nikde nenajde, bude sa cely system znova testovat dalsou vlnou broadcastov a potom ti rootnoda odpovie, ze go fuck yourself? Ak ten timeout nebude, tak da cely system deadlockne (skor ci neskor).
No... vyberies. Riesit klucovy algoritmus celeho systemu v interpretovanom jazyku je postavene na hlavu (podobne ako programovanie operacnych systemov vo vnutri webovych prehliadacov a podobne pakaze). Ten algoritmus je predpokladam len nejaka slusna matematika nad pamatovymi blokmi. To sa da krasne prenositelne napisat v Ccku za pomoci elementarnych a velmi rychlych rutin (ak sa to samozrejme napise dobre). To sa potom moze skompilovat ako externa kniznica a s vnutornym prostredim sa spoji pomocou API. Prekladat 32 MB 40 sekund je tak trochu volovina ;) aj keby si mal 10x rychlejsi stroj (co uz od 1GB masiny asi sotva najdes), robit preklad 32 MB 4 sekundy, aj 2 sekundy pri 100% vyhulenom procaku je nonsens. Na vedecke ucely, pokusiky, skumanie a tak je to pekne, lebo sa v tom programuje lahko, rychlo a relativne bez chyb, ale vysledny software moc rychlostou neovplyva. Ako by to vyzeralo, keby bol Linuxovy kernel napisany v Pythone?!
To, na co sa snazim poukazat miestami az za vlasy pritiahnutymi ukazkami, je to, ze v tom navrhu su zasadne nedostatky voci robustnosti. Ten system pobezi, mozno v istych podmienkach pobezi aj dobre, ale jeho skalovatelnost bude limitovana, pretoze jeho uspesnu prevadzkyschopnost bude ovplyvnovat vela vonkajsich okolnosti, pricom kombinacie niektorych z nich budu prenho fatalne. Ked sa system navrhuje, tak sa obvykle navrhuje tak, aby stacil na situacie, ktore su mierne za poziadavkami, ktore kedy nanho budu realne kladene.
---
Cuchat s nadchou, to je ako sniffovat bez promiscu.
> to akoze adresarova struktura celeho filesystemu bude ulozena LEN v ramdiskoch? takze ked prijdem,
> vyjebem poistku v hlavnom rozvadzaci pre cely Ynet, tak sa system rozhasi? Dost blby napad.
jedna noda moze byt dedikovana na robenie zaloh v tom nevidim problem. ukladat to na disk nema zmysel preto lebo tie data sa casto menia a v pripade ulozenia a znovupripojenia nody je velka pravdepodobnost ze uz budu neaktualne
k tym snapshotom
0....................191............................8191B
_______________________________________________________
| hash | attr | snap1 | snap2 | snap3 | ... | snap400 |
-------------------------------------------------------
|0| |0| |0|
|0| |1| |1|
|0| |1| |1|
|0| |0| |2|
|0| |0| |2|
takze kazdy snapshot sa odkazuje na subor v roznych casovych usekoch. v momente ak sa zmeni mtime suboru, vytvori sa nova polozka snap v bloku (to je len SHA-1 hash ktory sa odkazuje na subor) skopiruje si staru hlavicku suboru a hashe ktore boli zmenene nahradi odkazom na aktualne data. cize ziadne kopirovanie suboru tam neprebieha, len sa upravi hlavicka s novymi hashmi.
> to zaklada predpoklad, ze vsetky cielove masiny maju volne miesto minimalne pre tolko dat, ktore sa na > nich chystas ulozit, co je ale velmi krehky predpoklad.
mozem si nejake miesto prealokovat povedzme vytvorim prazdnu db datovych blokov ktora ma 10 GB takze tymto sposobom budem presne vediet kolko miesta mi tam este ostava
> b) pri cakani na to, aby sa ti ozval ten, kto dany blok drzi, existuje nejaky timeout? je treba si uvedomit,
> ze pre jeden 32 MB blok budes potrebovat vyvolavat z filesystemu obrovske kvantum 8000B blokov.
na kazdy stroj sa ulozi jedna cast IDA bloku, ale tato cast urcite nema 8kb. na priklade ze n = 14 a m = 10 pri |F| = 32 MB nam vychadza ze jeden takyto blok bude mat velkost:
|F| / m = 32 MB / 10 = 3.2 MB
ci uz si to dany stroj rozbije lokalne na 8kB alebo ulozi inak nam moze byt jedno. takze nie obrovske kvantum ale len 10 requestov.
> No... vyberies. Riesit klucovy algoritmus celeho systemu v interpretovanom jazyku je postavene na hlavu > (podobne ako programovanie operacnych systemov vo vnutri webovych prehliadacov a podobne pakaze).
> Ten algoritmus je predpokladam len nejaka slusna matematika nad pamatovymi blokmi.
Na zrychlenie kodovania dat cez IDA je podla mna este velky priestor na zlepsovanie, to ze to je napisane v interpretovanom jazyku (aj ked sa to kompiluje do byte codu, just-in-time compilation a pod) nemusi byt na skodu pretoze to napises raz a ide ti to vsade.
> Ako by to vyzeralo, keby bol Linuxovy kernel napisany v Pythone?!
zle, ale toto neni linuxovy kernel. toto je Inferno aplikacia na ktoru sa vztahuju iste pravidla prostredia.
ako to ze ma byt napisana v Limbe.
(co sa v sucasnej dobe aj tak obmedzuje len na x86 a x86_64, co ma v C (skoro) rovnaky kod) : suhlasim, abstrakcia tu zdrzuje a zbytocne zerie vykon cpu. Nieje ale potrebne mat "modul" pre kazdu platformu, staci to dorabat postupne, ak bude napr. x86 a si na x86 pojde to rychlejsie, ak nie, nic vazne sa nedeje akurat stracas cpu time ale system bezi.
Security: co v pripade ak pripojim do systemu x (x>m) masin s upravenym klientom a necham ich tam bezat dlhsie (mesiace?) ty si ulozis subor, nevyberas kam. Ja ziskam kompletny obsah (alebo vsetky potrebne bloky na jeho rekonstrukciu). Samozrejme este sifrovany ale ziskam bez ohladu na prava.
to hej ale pri vacsich sietach kde su radovo stovky pocitacov je to celkom problem ziskat vacsinu svojich klientov takze to nevnimam az ako taku hrozbu
no, nepotrebujes vela masin, staci ti upravit klienta aby sa tvaril ako "viac strojov", pripadne zopar VM na jednom stroji.
Asi by som na ziadnom distribuovanom systeme neriesil security priamo ale viac by som sa zameral na sifrovanie a ochranu. Akonahle data tecu von, skor ci neskor sa najde sposob ako ich ziskat (napr. fizly zhabu 50% masin).