Dostoevsky beseitigt überflüssiges Merging in LSM-Trees
Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores [pdf]
Niv Dayan und Stratos Idreos zeigen, dass gängige LSM-Tree-basierte Key-Value-Stores Merge-Operationen auf allen Ebenen gleich teuer ausführen, obwohl Merges außer auf der größten Ebene kaum etwas zu Punkt-Lookups, Langbereichs-Lookups oder Speicherplatz beitragen. Mit Lazy Leveling entfernen sie überflüssige Merges, mit Fluid LSM-tree spannen sie den gesamten Designraum auf, und Dostoevsky wählt zur Laufzeit die beste Konfiguration für Workload und Hardware. Auf RocksDB implementiert, dominiert Dostoevsky bestehende Designs in Leistung und Speicherverbrauch.
Da der Worst-Case-Punkt-Lookup-Aufwand, der Langbereichs-Lookup-Aufwand und die Space-Amplification größtenteils von der größten Ebene herrühren, verbessern Merge-Operationen auf allen Ebenen des LSM-Tree außer der größten (d. h. die meisten Merge-Operationen) diese Metriken kaum, während sie die amortisierten Update-Kosten erheblich erhöhen.