Storage

Implementace modulu storage, tzn. správy perzistentních dat, si kladla za cíl tři základní požadavky:

1.

Efektivní vyhledání resp. vytvoření prostoru na disku pro příslušný záznam

2.

Rovnoměrné rozložení zátěže mezi všechny vyhražené disky, určené pro trvalé uložení záznamů

3.

Rozumné pamětové nároky

Opěrným bodem pro dosažení všech tří cílů bylo využití hašovací funkce md5, která byla vyvinuta ke kryptografickým účelům a i přesto, že již existují funkce modernější a bezpečnější, stále je pro své dobré vlastnosti hojně rozšířena. Sledovanou vlastností této funkce byla její ``jednosměrnost'', čímž je myšleno, že ačkoli md5 lineárně spočte ze vstupu 128 bitový digest, je na druhou stranu velmi obtížné z výstupu funkce získat původní, či jakýkoli vstup, který by odpovídal získané hodnotě (v podmínkách běžných osobních počítačů a průměrné délky lidského života se dá říci, že je to až nemožné ;-). Z toho vyplývá, že se zkoumáním vlastností nějaké množiny vstupů prakticky nedá odhadnout interval oboru hodnot, do kterých md5 digesty vybraných vstupů padnou, tzn. nelze definovat třídy vstupů, pro které by md5 generovala v nějakém smyslu podobné hodnoty, čehož je využito v implementaci bodů 1, 2 a nepřímo i 3. Funkce MD5, její vlastnosti a referenční implementace jsou definovány v RFC1321.

Prvního bodu bylo dosaženo tím, že jméno souboru na disku, nesoucí příslušný záznam, tvoří přímo hodnota md5 digestu (v hexadecimální soustavě). Z této hodnoty je také v konstatním čase určeno přesné místo na FS, kam má být záznam uložen resp. kde již uložen je, což splňuje požadadvky dané prvním bodem.

Rovnoměrného rozložení zátěže mezi disky (ve skutečnosti buckety, ale jelikož nedává reálný smysl vytváření více bucketů na stejném fyzickém disku, pak se při předpokladu, že jeden disk odpovídá jednomu bucketu, zátěž rozkládá mezi fyzické disky) bylo dosaženo tím, že se z části md5 digestu za pomocí modulo operátoru určí bucket, do kterého záznam náleží, obdobným způsobem bylo dosaženo rovnoměrného rozložení záznamů v podadresářích jednotlivých bucketů (viz pododdíl Implementace v oddílu Storage). Nevýhodou této metody je, že rovnoměrnost rozkladu se projevuje až na početnějších a tím pádem i objemnějších vzorcích dat, počínaje stovkami kilobytů, megabajty a výše, což je ovšem kompenzováno současnou a s největší pravděpodobností i budoucí velkou dostupností vysokokapacitních pevných disků, takže vyhražení diskového prostoru o velikosti např. několika gigabytů by pro administrátora serveru, na kterém by měla být proxy cache provozována, neměl být problém, či spíše je podobná kapacita diskového prostoru pro perzistentní data očekávána.

Velikou výhodou současné implementace modulu storage jsou nízké paměťové nároky, protože není nutné uchovávat v operační paměti záznamy o všech uložených objektech, tak jak by tomu zřejmě muselo být, kdyby volba padla na algoritmus, který by přidělený diskový prostor zaplňoval precizněji. K tomuto řešení přispělo i cílení na OS Linux a vlastnosti jeho nativního FS ext2, jako je ukládání souborů a adresářových struktur do vyrovnávací paměti, což umožňuje ``přesunout zodpovědnost'' za efektivitu přístupu k jednotlivých souborům na disku plně na operační systém.

Zmíněné řešení bylo odzkoušeno na ext2, ale samozřejmě na něj není nijak pevně vázáno, je tudíž možné použít jakýkoli FS, který u souborů ukládá čas posledího přístupu a modifikace a umožňuje běžná systémová volání open, close, fstat apod., což kupodivu není zase taková samozřejmost! (viz NFS) Volba cílového FS může samozřejmě klíčově ovlivnit výkonnost a rychlost většiny funkcí modulu Storage.