LSM Tree

Question 1

Z jakich komponentów składa się LSM-Tree?

Answer 1

• 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

Question 2

W jaki sposób przebiega zapis w LSM Tree?

Answer 2

1. Save in WAL
2. Save in Memtable
3. Update Bloom Filter

Question 3

W jaki sposób przebiega odczyt w LSM Tree?

Answer 3

1. Check for existence in Bloom Filter.
2. Search in Memtable
3. Search in SSTable starting from the newest segment.

Question 4

Dla jakich zastosowań sprawdzi się LSM Tree?

Answer 4

Write-intensive workloads (when we want to optimize for fast and massive writes).

Question 5

Objaśnij różnice między leveled i size-tiered compaction w LSM Tree

Answer 5

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). 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 space and write amplification przy kompakcji.

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 read and 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).

Question 6

Dla jakich workloadów leveled-compaction będzie lepszy niż size-tiered compaction?

Answer 6

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.

Question 7

Jakie bazy danych używają pod spodem LSM Tree do przechowywania danych?

Answer 7

LevelDB, RocksDB, Cassandra, HBase (LSM Tree comes from BigTable papers) i pewnie wiele innych.