LSM Tree Flashcards
(10 cards)
Z jakich komponentów składa się LSM-Tree?
- Memtable (generally sorted tree, e.g. Red-Black Tree)
- SSTable (String Sorted Table)
- WAL (Write Ahead Log)
- Bloom Filters (probabilistic data structure with O(1) complexity - can have false positive but no false negative for existence)
- Sparse Index for each segment (both in-memory and in disk)
- Compactor
W jaki sposób przebiega zapis w LSM Tree?
- Save in WAL
- Save in Memtable
- Update Bloom Filter
W jaki sposób przebiega odczyt w LSM Tree?
- Check for existence in Memtable.
- Search in SSTables starting from the newest one. Before actually searching SSTable check Bloom Filter.
Dla jakich zastosowań sprawdzi się LSM Tree?
Write-intensive workloads (when we want to optimize for fast and massive writes).
Objaśnij różnice między leveled i size-tiered compaction w LSM Tree
Leveled compaction - SSTables podzielone na różne levele, każdy kolejny level posiada większy zbiór danych. Klucze w SSTables na danym poziomie się nie przeplatają (cały level jest posortowany, wyjątkiem level 0). Compaction jest triggerowane przez przekroczenie zadanej maksymalnej pojemności danego levelu. Mergowanie następuje z wybranej tabeli w niższym poziomie do kilku tabeli na wyższym poziomie (takich, które rozpościerająsię na ten sam podzbiór kluczy). Taki sposób zapisu minimalizuje space amplification i read amplification przy lookupie kosztem zwiększenie write amplification przy kompakcji (częściej się dzieje).
Size-tiered compaction - SSTables podzielone na poziomy, ale tym razem compaction następuje, kiedy dwie SSTable z danego poziomu przekroczą threshold. Są one wtedy mergowane i przeniesione do kolejnego poziomu. Taki sposób zapisu minimalizuje write amplification kosztem space amplification (ciężko o zmergowanie dwóch wielkich SSTable na wysokim levelu) i kosztem read amplification przy lookupie (więcej tabel do przeszukania, bo na danym levelu nie są posortowane).
Dla jakich workloadów leveled-compaction będzie lepszy niż size-tiered compaction?
Leveled compaction sprawdzi się, gdy chcemy optymalizować pod lookup, zwłaszcza taki, który równomiernie rozprzestrzenia się na cały zbiór kluczy. Będzie też dobry gdy często nadpisujemy wartość danego klucza, bo ogranicza space amplification w takim przypadku. Prawdopodobnie da się też przy takim zapisie w miarę sensownie zrobić range query.
Size tiered compaction sprawdzi się, jeśli dużo zapisujemy, ale rzadziej czytamy. Albo gdy rzadko nadpisujemy wartość danego klucza i nie boli nas przez to space amplification (ale dalej lookup może być kosztowny). Ewentualnie, jeśli najczęściej czytamy świeżo zapisane dane, wtedy lookup rzadko musi wchodzić w wyższe i tym samym większe levele SSTable. Raczej nie da się odpalić przy takim zapisie range query, bo dany klucz może wystąpićwe wszystkich SSTables.
Jakie bazy danych używają pod spodem LSM Tree do przechowywania danych?
LevelDB, RocksDB, Cassandra, HBase (LSM Tree comes from BigTable papers) i pewnie wiele innych.
Wyjaśnij różnicę między covering, clustered i non-clustered index.
Clustered - wartość to faktyczny rekord który chcemy wyciągnąć
Covering - wartość to część rekordu plus referencja do heap file
Non-clustered index - tylko referencja do heap file’a (albo primary indeksu)
Wady LSM Tree
-compaction może wpływać na bieżące operacje
-przy wysokim write throughput compaction ogranicza ograniczony write bandwidth, im większa baza tym większy wpływ compaction
-przy dużym write throughput źle skonfigurowane compaction może nie nadążać i doprowadzić do wyczerpania miejsca na dysku
-duże write amplification związane z compaction
-potencjalnie dłuższy czas odczytu niż tradycyjny b-tree index bo trzeba przeszukać kilka miejsc
Zalety LSM Tree względem b-tree
-mniej miejsca jeśli compaction dobrze skonfigurowane (nie ma pustych page’y)
-zwykle jest w stanie wytrzymać większy write throuput, ograniczony głównie Disk bandwidth, a zapisuje sekwencyjnie co też dobre dla magnetycznych dysków
