Predictive B+ tree

Il predictive B+ tree (abbreviato BP tree o $B^{P}$ tree) è una variante del B+tree studiata appositamente per operare con memorie a cambiamento di fase (o PCM, Phase Change Memory).

Il BP tree è stato presentato nel IEEE transaction on knowledge and data engineering, vol.26, N°10 di Ottobre 2014 ed ancora in fase di sperimentazione. Gli autori principali di questo albero binario sono Weiwei Hu, Dalie Sun, Guoliang Li, Kian-Lee Tan e Jiacai Ni. La prima presentazione del progetto è stata fatta presso l'Università di Tsinghua come tesi di laurea di Weiwei Hu dal titolo Redesign of database algorithms for next generation non-volatile memory technology..

Posizione delle PCM nella gerarchia della memoria

In fase di progettazione del BP tree si è presentato il dilemma di come posizionare le PCM nella gerarchia della memoria. Le possibilità sono due.

• Rimpiazzare direttamente la DRAM con una PCM in modo da avere una maggiore capacità di memoria principale
• Utilizzare una grande PCM insieme ad una piccola DRAM (quest'ultima con capacità pari al 3%/8% della prima) come sistema di memoria principale.

Il modello utilizzato nel BP tree è il secondo. In tal modo è possibile utilizzare la piccola DRAM come buffer per la PCM al fine di mantenere quei dati che devono essere spesso acceduti o modificati.

Vantaggi e problematiche per sistemi operanti con PCM

Le memorie a cambiamento di fase promettono feature interessanti. Innanzitutto offrono uno storage non volatile ad accesso casuale con indirizzamento a byte e velocità di lettura e scrittura molto elevate. Hanno inoltre una densità molto superiore alle attuali DRAM ed un consumo energetico decisamente inferiore alle memorie NAND FLASH. In seguito è possibile vedere una semplice tabella prestazionale che confronta le performance degli attuali tipi di memorie analizzando principalmente la densità, la velocità, il consumo energetico e l'endurance (ossia quante scritture è possibile eseguire su ogni blocco prima di un deterioramento).

	DRAM	PCM	NAND	HDD
Densità	1X	2-4X	4X	N/D
Latenza in lettura Latenza in scrittura	20-50 ns 20-50 ns	50 ns 1 µs	25 µs 500 µs	5 ms 5 ms
Energia in lettura Energia in scrittura	0.8 J/GB 1.2 J/GB	1 J/GB 6 J/GB	1.5 J/GB 17.5 J/GB	65 J/GB 65 J/GB
Endurance	$\infty$	$10^{6}-10^{8}$	$10^{5}-10^{6}$	$\infty$

Come si evince dalla tabella, le PCM sono più lente delle attuali DRAM, soprattutto nelle operazioni di scrittura; inoltre tali operazioni hanno un consumo energetico nettamente superiore. Infine è importante evidenziare che il numero di scritture su singolo blocco non ha importanza per le DRAM, ma è un elemento critico sul lungo periodo per le PCM.

Obiettivo del BP tree

Date le prestazioni della tabella precedente, l'obiettivo principale del BP tree è dunque quello di ridurre il più possibile le operazioni di scrittura sulla PCM. A tal scopo sono state adottate diverse tecniche.

Modello predittivo

Per ridurre le scritture è stato adottato un modello predittivo per calcolare il valore futuro (o la distribuzione futura) di un valore casuale. Questo modello combina l'andamento precedente e l'andamento attuale della distribuzione dei valori dei dati al fine di predirne la futura distribuzione.

Strategia a foglie non ordinate

All'inserimento di una nuova chiave nel BP tree non viene effettuato l'ordinamento. Ciò riduce il numero di scritture aumentando però il costo di ricerca.

Minimizzazione delle operazioni di split e merge

Soverchiando alcune delle regole principali del B+ tree (su cui il BP tree si basa), accettiamo nel BP tree un bilanciamento non canonico al fine di diminuire le operazioni di Split e Merge che rappresentano la fonte maggiore di scritture nei B+ tree.

Architettura del BP tree

DRAM Buffer

Al suo interno viene memorizzato un piccolo B+ tree (altezza h e branching factor 2m) e l'istogramma delle distribuzioni delle chiavi precedentemente inserite. Il B+ tree viene utilizzato per gli inserimenti correnti delle chiavi; l'istogramma per poter attuare il modello predittivo. Quando il buffer è pieno, il B+ tree verrà unito al BP tree presente sulla PCM.

PCM

Come anticipato, sulla PCM viene memorizzato il vero e proprio BP tree (altezza h e branching factor 2M), ossia un albero binario del tutto uguale al B+ tree ad eccezione di alcune caratteristiche:

• La struttura ed i nodi possono essere pre-allocati.
• Dato il branching factor 2M del BP tree, il numero di nodi figlio di un nodo interno può essere minore di M (comunque compreso tra 0 e 2M).
• Differente gestione degli inserimenti e delle cancellazione rispetto ai B+ tree.

Fasi

Fase di warm-up

Esempio di fase di warm-up. Il B+ tree è pieno e viene trasferito nella PCM. Nell’istogramma la parte blu rappresenta l’effettiva distribuzione delle chiavi, la parte rossa la predizione ottenuta con il modello matematico. Il nodo C del B+ tree viene scisso nel BP tree nei nodi C e C’ a causa della predizione futura.

Con questo termine si identifica la prima fase di creazione di un BP tree. Inizialmente il BP tree è vuoto e utilizziamo il B+ tree presente nella DRAM per la creazione del primo albero binario. Ad ogni nodo inserito aggiorniamo l'istogramma delle distribuzioni. Quando il buffer sarà pieno lo svuoteremo sulla PCM, creando così lo scheletro del BP tree. Durante la fase di trascrittura del B+ tree nella PCM sarà utilizzato il modello predittivo in funzione dei dati presenti nell'istogramma per scindere o concatenare i nodi che saranno parte del BP tree.

Fase di update

In seguito alla fase di warm-up nella PCM è presente la struttura del BP tree. La fase successiva, detta di update, comprende tutte le operazioni future:

Inserimento

Le nuove chavi vengono inserite nel B+ tree con aggiornamento del relativo istogramma. Se il buffer DRAM è pieno, il B+ tree viene fuso con il BP tree nella PCM.

Ricerca

La chiave viene ricercata sia nel B+ tree che nel BP tree.

Rimozione

La chiave viene ricercata e rimossa sia nel B+ tree che nel BP tree, con conseguente aggiornamento dell'istogramma. In caso di underflow dei nodi del BP tree, questi non vengono concatenati (riservando spazio per inserimenti futuri).

Aggiornamento

Viene trattato come una rimozione seguita da un inserimento.

Prestazioni

Il BP tree è stato testato su un DBMS PostgreSQL. I dati raccolti hanno evidenziato che nelle architetture a memoria principale ibrida DRAM + PCM il BP tree è più performante del B+ tree.

Voci correlate

• B-albero
• Memoria a cambiamento di fase
• DRAM

Collegamenti esterni

• IEEE transaction on knowledge and data engineering, vol.26, N°10, OCT 2014, su ieeexplore.ieee.org.
• Redesign of database algorithms for next generation non-volatile memory technology (PDF) , su scholarbank.nus.edu.sg.