Analiza uticaja dvoslojnog keširanja i proređenih indeksa na latenciju čitanja u LSM skladištima podataka

Autori

  • Aleksa Dejanović Fakultet tehničkih nauka Univerziteta u Novom Sadu Autor
  • Petar Popović Fakultet tehničkih nauka Univerziteta u Novom Sadu Autor
  • Boško Vasilić Fakultet tehničkih nauka Univerziteta u Novom Sadu Autor
  • Sara Stojkov Fakultet tehničkih nauka Univerziteta u Novom Sadu Autor

DOI:

https://doi.org/10.63356/stes.ing.2026.003

Ključne reči:

LSM stablo, Key-Value skladište, Block Cache, LRU Cache, latencija čitanja

Apstrakt

Uvod: Skladišta podataka zasnovana na LSM stablu (Log-Structured Merge-Tree) omogućavaju visoku propusnost upisa, ali pretraga više nivoa i pojačano čitanje sa diska mogu povećati latenciju čitanja.

Cilj: Eksperimentalno ispitati uticaj dvoslojnog keširanja (aplikativni LRU Cache i diskovni Block Cache), te različitih nivoa proređenosti Summary/Index struktura na performanse tačkastih GET upita u prilagođenom LSM Key-Value sistemu.

Materijal i metode: Implementiran je Key-Value sistem sa dvoslojnim keširanjem i podesivim Summary/Index strukturama. Evaluacija je obuhvatila 10⁶ operacija čitanja sa Zipfovom i uniformnom distribucijom, nad postojećim i nepostojećim ključevima. Varirane su veličine blokova od 4, 8 i 16 KB i odnosi uzorkovanja Summary/Index struktura od 1 : 4 do 1 : 64.

Rezultati: Najbolje ukupne performanse postignute su blokovima od 4 KB, odnosom uzorkovanja Summary strukture 1 : 16 i aktivnim L1 i L2 kešom. L2 keš je, u odnosu na konfiguraciju bez keširanja, smanjio prosečnu latenciju sa 1.048,2 na 214,7 µs (79,5%), a kombinacija L1 i L2 keša na 178,4 µs (83,0%). U mešovitom opterećenju od 10⁶ zahteva dvoslojno keširanje je, u odnosu na samo L2 keš, smanjilo prosečnu GET latenciju sa 220,30 na 182,36 µs (17,2%) i povećalo propusnost sa 4.539 na 5.484 GET/s (20,8%). L1 keš ostvario je stopu pogodaka od 37,5%, uz 16,5% manje pristupa L2 kešu.

Zaključak: Dvoslojno keširanje značajno unapređuje performanse čitanja, a veličina blokova i proređenost indeksa omogućavaju balansiranje latencije, propusnosti i memorijskih zahteva. U evaluiranom sistemu najpovoljnija je kombinacija blokova od 4 KB, odnosa uzorkovanja 1 : 16 i aktivnih L1 i L2 keševa.

##submission.downloads##

Objavljeno

2026-11-18

Broj časopisa

Rubrika

Članci