napisałem na usenecie, może tutaj jest lepsze miejsce:
Mamy bazę nie mieszczącą się w pamięci.
Jeśli cała baza mieści się w pamięci to przyjmujemy koszt=0, bo inne rzeczy poza przesyłaniami z dysku do pamięci pomijamy.
Nie musi cała dostępna pamięć być używana do bazy, miejmy dwa parametry: w pamięci 1 GB danych, baza ma 2GB (przykładowo, bo może tez liczyć terabajty). Rekord 100-160 bajtów.
Losowy dostęp do dysku 14 ms, prędkość przesyłu blokowego 120 MB/s.
Jak chcemy przeczytać rekord który nie jest w pamięci to musimy przeczytać blok, miejmy na to szeroki parametr: tylko 4 KB, czy 512 KB, albo nawet 128 MB.
Na szczęście mamy szeregowanie. Gdy zapytujemy kolejno , nie możemy szeregować, bo dostajemy odpowiedź synchronicznie.
Szeregowanie gdy wiele klientów, wiele wątków i najlepsza sytuacja - klient podaje całą listę 50 czy 1000 rekordów do znalezienia, możemy podzielić na bloki i czytać blok dyskowy dla wielu a nie jednego rekordu.
Mając te parametry jak wyliczyć ilość bajtów przesyłu, ilość odwołań do dysku, i z tych dwóch - czas.
Czasami preferuje się czas przesyłu z dysku zamiast losowego odwołania do dysku. W Hadoop przyjęto na przykład że czas odwołania to tylko 1% stąd tam są bloki 100 MB zamiast 1 MB.
------
M: wielkość pamięci
D: wielkość bazy
r: wielkość rekordu
B: wielkość bloku
n: ilość rekordów w jednym query
Zakładamy nietrywialny przypadek D>M
dostajemy jeden rekord. Prawdopodobieństwo że nie ma go w pamięci wynosi (D-M)/D
wtedy czytamy blok B bajtów. Wyrzucamy z pamięci B/r rekordów.
Choć mi coś się nie zgadza: jeśli cachowane będzie 10% bazy, to w 90% przypadków gdy zamierzany wczytać rekord, będziemy musieli wczytywać blok, który musi być jak najmniejszy. Cache zakłada że te wczytane mają większe prawdopodobieństwa, oraz że nie zawsze będzie losowy rekord ale kolejny. Gdyby tylko losowo dostawać się do rekordów, blok musiałby być dowolnie mały, ale jak jest większy to przewiduje że będą kolejne co często jest bo często kolejno idziemy po indeksie, a indeks bywa często tak duży jak tabela, indeksu sumarycznie przekraczają wielkość tabeli, więc się mogą nie mieścić w pamięci.