O^3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading

Il paper presenta O³-LSM, una nuova architettura per archivi chiave-valore basati su LSM che massimizza le prestazioni di scrittura in ambienti di storage disaggregato sfruttando la memoria disaggregata per un offloading a tre livelli (memtable, flush e compaction) e ottimizzazioni di lettura, ottenendo miglioramenti significativi nel throughput e nella latenza rispetto alle soluzioni esistenti.

L'essenziale

Immagina di avere un ristorante di lusso (il tuo sistema di database) che serve milioni di clienti ogni giorno. Il problema è che la cucina (il computer che elabora i dati) è piccola, ma il magazzino (lo storage) è enorme e si trova in un altro edificio collegato da un corridoio veloce (la rete).

Ecco come funziona il sistema attuale e qual è il problema, prima di arrivare alla soluzione geniale di O3-LSM.

Il Problema: La Cucina Che Si Blocca

Nel sistema attuale, quando arrivano gli ordini (i dati da scrivere):

1. Lo chef li scrive su un taccuino temporaneo (chiamato Memtable) sulla scrivania della cucina.
2. Quando il taccuino si riempie, lo chef deve fermarsi, ricopiare tutto su un foglio permanente (un file SST) e portarlo al magazzino.
3. Il collasso: Se la scrivania è piccola e il magazzino è lontano, lo chef si blocca. Deve aspettare che il taccuino si svuoti prima di prendere nuovi ordini. Se il magazzino è lento a ricevere i fogli, la cucina si intasa e i clienti devono aspettare.

I sistemi precedenti hanno provato a delegare solo la "pulizia" dei fogli vecchi (una cosa chiamata compaction), ma non hanno risolto il problema principale: la scrivania è troppo piccola e il trasferimento dei taccuini è lento.

---

La Soluzione: O3-LSM (Il Ristorante a Tre Livelli)

Gli autori di questo paper propongono O3-LSM, un nuovo modo di gestire il ristorante che sfrutta uno spazio di archiviazione intermedio chiamato Memoria Disaggregata (DM). Immagina la DM come un banco di appoggio extra situato esattamente a metà strada tra la cucina e il magazzino.

O3-LSM introduce tre innovazioni rivoluzionarie:

1. Il Taccuino "Intelligente" (Memtable Ottimizzata)

• Il vecchio modo: Quando sposti un taccuino dal banco della cucina al banco intermedio, devi rileggerlo, riscriverlo e cambiare tutti i riferimenti interni (come se dovessi riscrivere l'intero libro solo per cambiare la copertina). È lento e costoso.
• Il modo O3-LSM: Creano un taccuino speciale che è già pronto per essere spostato. È come se il taccuino fosse composto da due parti: un indice e i dati veri. Quando lo sposti al banco intermedio, sposti solo i dati (facile e veloce) e aggiorni solo l'indice con una semplice nota.
• Risultato: Spostare i dati diventa un'operazione istantanea, non più un collo di bottiglia.

2. Il Corriere Condiviso (Flush Collaborativo)

• Il vecchio modo: Se il tuo chef ha un taccuino da portare al magazzino, deve farlo lui stesso, anche se è stanco o se la sua strada è bloccata dal traffico.
• Il modo O3-LSM: C'è un capo corriere (uno schedulatore) che guarda tutti gli chef e tutti i corridoi. Se il tuo chef è occupato, ma il vicino ha la strada libera e un corriere in più, il capo assegna il compito al vicino.
• Risultato: Non importa quale chef ha scritto il dato; il sistema sceglie il percorso più veloce e meno affollato per portarlo al magazzino. Questo evita che un solo chef si blocchi per colpa del traffico.

3. I Pacchetti in Miniatura (Sharding)

• Il vecchio modo: Devi spostare un intero taccuino gigante (64 MB) tutto in una volta. Se il corridoio si intasa, tutto si blocca.
• Il modo O3-LSM: Tagliano il taccuino in tanti piccoli pezzi (shards) basati sugli argomenti (es. tutti gli ordini di "pasta" in un pacchetto, tutti quelli di "pizza" in un altro).
• Risultato: Invece di un unico camion enorme che blocca il traffico, hai decine di moto che viaggiano in parallelo. Inoltre, quando si portano i pezzi al magazzino, si possono unire subito quelli della stessa categoria, evitando di creare confusione e file duplicati.

Bonus: Il Menu Pre-ordinato (Lettura Intelligente)

Per leggere i dati, invece di correre a controllare ogni singolo taccuino nel banco intermedio (che è lento), O3-LSM tiene una piccola lista dei "piatti caldi" (cache) direttamente in cucina.

• Se il cliente chiede un piatto famoso, lo chef lo prende dalla lista veloce (istantaneo).
• Se è un piatto raro, invece di correre al banco intermedio da solo, chiama un assistente che va lì, cerca il piatto e lo porta indietro.
• Risultato: I clienti ricevono i piatti molto più velocemente.

---

I Risultati: Cosa Ottiene il Ristorante?

Grazie a queste tre strategie (Taccuino intelligente, Corrieri condivisi, Pacchetti piccoli), O3-LSM ha dimostrato risultati incredibili rispetto ai sistemi attuali:

• Scrittura: Fino a 4,5 volte più veloce. Il ristorante non si blocca più mai, anche con ordini esplosivi.
• Lettura: Fino a 1,8 volte più veloce. I piatti arrivano subito.
• Attesa: Il tempo massimo di attesa (P99 latency) si è ridotto fino al 76%. Significa che anche il cliente più sfortunato non aspetta quasi nulla.

In Sintesi

O3-LSM trasforma un sistema rigido e lento in un sistema flessibile, parallelo e intelligente. Invece di far lavorare un solo chef con una scrivania piccola, crea una catena di montaggio dove i dati viaggiano su corsie preferenziali, vengono divisi in piccoli pacchetti gestibili e vengono consegnati da chiunque abbia la strada libera. È come passare da un traffico cittadino bloccato a un'autostrada a più corsie con piloti autonomi che si scambiano i passeggeri in volo.

Sommario tecnico

Ecco un riepilogo tecnico dettagliato del paper "O3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading", presentato in italiano.

1. Il Problema

I sistemi di archiviazione chiave-valore basati su alberi LSM (Log-Structured Merge-tree), come RocksDB, sono stati ottimizzati per i Data Center Disaggregati (DDC) tramite il compaction offloading (spostamento del processo di compattazione sui nodi di storage). Tuttavia, le ottimizzazioni esistenti presentano limiti critici che degradano le prestazioni di scrittura:

• Memoria limitata sui nodi di calcolo (CN): I nodi di calcolo ospitano molte istanze di LSM-KVS, lasciando poco spazio per i buffer di scrittura (memtable). Quando la memoria locale è piena, le scritture vengono bloccate o rallentate.
• Operazioni di Flush lente: Il trasferimento delle memtable piene verso lo storage disaggregato (DS) genera un intenso traffico di I/O di rete, contendendo con altre operazioni e causando latenze elevate.
• Compattazione L0 inefficiente: L'accumulo di file SST (Sorted String Tables) nel livello L0, spesso sovrapposti, richiede compattazioni seriali e lente, creando colli di bottiglia.
• Limiti dell'approccio naive: Semplicemente spostare le memtable sulla Memoria Disaggregata (DM) tramite RDMA non è sufficiente. Le sfide includono:
  1. Costo di trasferimento e ricostruzione: Le strutture dati come gli skip-list contengono molti puntatori che diventano invalidi quando copiati su memoria remota, richiedendo una costosa ricostruzione.
  2. Flush inefficiente: La DM non ha la logica per creare file SST (ordinamento, compressione, ecc.). Le memtable devono essere riportate al CN per il flush, aggiungendo un hop di rete extra.
  3. Ricerca lenta: Cercare chiavi in memtable remote tramite RDMA richiede molteplici round-trip, degradando le prestazioni di lettura.

2. Metodologia: O3-LSM

O3-LSM propone una nuova architettura fondamentale che sfrutta la Memoria Disaggregata (DM) condivisa per implementare un Offloading a Tre Livelli: Memtable Offloading, Flush Offloading e Compaction Offloading.

Le innovazioni chiave sono:

A. Memtable Ottimizzata per DM (DM-Optimized Memtable)

Per risolvere il problema della ricostruzione dei puntatori:

• Separazione Indice-Dati: La memtable viene divisa in un blocco di indici (basato su puntatori) e un blocco KV continuo contenente i dati.
• Layout Contiguo: I dati KV sono memorizzati in modo contiguo e i puntatori nell'indice puntano agli offset all'interno di questo blocco, non agli indirizzi di memoria assoluti.
• Trasferimento Economico: Questo permette di trasferire il blocco dati alla DM come un semplice memcpy senza dover ricostruire la struttura ad albero/skip-list. Solo l'indice deve essere aggiornato localmente sulla DM per correggere gli offset di base, un'operazione O(1).

B. Flush Offloading Collaborativo (Collaborative Flush Offloading)

Per decouplare il controllo del flush dall'istanza LSM-KVS:

• Protocollo Multi-fase: Viene introdotto un protocollo leggero che separa il piano di controllo dal piano di esecuzione.
• Schedulatore Intelligente: Un Flush Scheduler centrale monitora le risorse (CPU, I/O) di tutti i nodi (CN e DM). Assegna il compito di flush a qualsiasi nodo disponibile (Locale, In-DM, o Remote-CN) che abbia risorse libere.
• Esecuzione Remota: Il nodo selezionato recupera i dati dalla DM, esegue l'ordinamento, la compressione e la scrittura su DS, eliminando la necessità di riportare i dati al CN proprietario.

C. Ottimizzazione a Livello di Shard (Shard-Level Optimization)

Per parallelizzare il trasferimento e mitigare la compattazione L0:

• Sharding delle Memtable: Ogni memtable è divisa in più "shard" (blocchi KV) basati su intervalli di chiavi disgiunti.
• Trasferimento Asincrono: Gli shard possono essere trasferiti alla DM in parallelo e in modo asincrono.
• Flush Aggregato: Invece di flushare memtable intere, il sistema aggrega shard con lo stesso intervallo di chiavi da diverse memtable. Questo crea file SST L0 più piccoli e con meno sovrapposizioni di chiavi, trasformando la compattazione L0 da un'operazione seriale a una parallela.

D. Delega di Lettura Potenziata dalla Cache (Cache-Enhanced Read Delegation)

Per mitigare la latenza di lettura sulle memtable remote:

• Cache Key-Offset Locale: Il CN mantiene una piccola cache locale che mappa le chiavi "hot" ai loro offset nella DM.
• RDMA One-Sided: Se la chiave è nella cache, il dato viene recuperato direttamente dalla DM con un singolo RDMA_READ.
• Delega di Lettura: In caso di miss, il CN invia una richiesta di delega (RDMA_SEND) a un thread sulla DM che esegue la ricerca localmente e restituisce il risultato, evitando molteplici round-trip di dereferenziazione.

3. Risultati Sperimentali

O3-LSM è stato implementato su RocksDB v8.2.0 e valutato su CloudLab confrontandolo con Disaggregated-RocksDB, CaaS-LSM e Nova-LSM.

• Prestazioni di Scrittura:
  • Miglioramento del throughput fino a 4.5x rispetto alle soluzioni esistenti.
  • Riduzione della latenza P99 fino al 60-76% (a seconda del carico di lavoro).
  • Riduzione significativa degli stalli di scrittura causati dalla memoria piena.
• Prestazioni di Lettura:
  • Miglioramento del throughput di ricerca puntuale (point lookup) fino a 1.8x.
  • Miglioramento del throughput delle query di intervallo (range query) fino a 5.2x, grazie alla riduzione dei file L0 sovrapposti.
  • Riduzione della latenza P99 di lettura fino al 69%.
• Workload Reali:
  • Su Kvrocks (un sistema Redis compatibile), O3-LSM ha mostrato miglioramenti fino a 3.4x nel throughput e riduzioni della latenza fino al 54%.
• Stabilità: O3-LSM dimostra una stabilità superiore nel tempo, evitando i picchi di latenza e i cali di throughput tipici delle architetture tradizionali.
• Scalabilità: Il sistema scala linearmente aggiungendo nodi di calcolo e nodi di memoria, gestendo efficacemente il traffico di rete attraverso lo sharding e lo scheduling collaborativo.

4. Significato e Impatto

O3-LSM rappresenta un passo avanti fondamentale nell'ottimizzazione dei database per architetture cloud disaggregati:

1. Superamento del collo di bottiglia della memoria: Trasforma la Memoria Disaggregata da un semplice storage passivo a un'estensione attiva e performante del buffer di scrittura, risolvendo il problema della scarsità di memoria sui nodi di calcolo.
2. Ridefinizione del ciclo di vita LSM: Introduce un approccio a tre livelli di offloading che non si limita alla compattazione, ma ottimizza l'intero flusso di scrittura e lettura.
3. Efficienza delle risorse: Sfrutta la potenza di calcolo distribuita del cluster per eseguire operazioni di flush e compattazione, bilanciando il carico e riducendo la contesa I/O sui singoli nodi.
4. Portabilità: Le tecniche proposte (memtable ottimizzata, flush collaborativo) sono state dimostrate portabili su altre architetture LSM esistenti (come CaaS-LSM), suggerendo che O3-LSM potrebbe diventare uno standard per i sistemi KVS disaggregati di prossima generazione.

In sintesi, O3-LSM risolve i problemi fondamentali di latenza e throughput nei sistemi LSM disaggregati, rendendo l'uso della memoria disaggregata non solo fattibile, ma altamente performante per carichi di lavoro intensivi in scrittura.