Strutture dati

Le strutture dati utilizzate dagli store vengono decise dinamicamente sulla base dei consumatori e produttori presenti su quello store. Queste strutture puntano a velocizzare l’accesso ai dati da parte dei consumatori e minimizzare lo spreco di memoria.

Ci sono fondamentalmente 4 operazioni di scrittura in qualunque update pattern: Inserimento, Cancellazione, Aggiornamento di un valore e Garbage collection. Il garbage collection `e la procedura attraverso la quale si libera spazio dagli store in memoria eliminando/migrando i dati consumati od obsoleti su disco.

Di seguito analizziamo le strutture dati implementate dagli store sulla base dell’update pattern utilizzato (RANDOM, FIFO o IN-PLACE).

Implementazione di uno store RANDOM

La modalit`a RANDOM permette di cancellare qualsiasi elemento all’interno dello store in maniera non sequenziale.

La struttura dati pi`u adatta per implementare uno store RANDOM `e una lista concatenata in quanto risulta particolarmente flessibile e facilmente ma-nipolabile in caso di cancellazioni ed inserimenti molto frequenti. Una lista concatenata aumenta o diminuisce le sue dimensioni in maniera dinamica ed in tempo costante.

Inserire ciascuna tupla entrante in un nuovo elemento della lista risulta per`o svantaggioso nel caso che i tassi di arrivo sia molto elevato, pertanto la lista non contiene direttamente le tuple ma contiene dei puntatori (directors) a dei bloc-chi che contengono i dati. Questo migliora le prestazioni in caso di inserimenti molto frequenti. Un blocco `e implementato come un array di elementi con una particolare dimensione (fissa). Una nuova tupla entrante viene inserita nell’ul-tima posizione del blocco puntato dall’ultimo elemento della lista concatenata. Se tutti i blocchi sono pieni, viene creato un nuovo elemento in fondo alla lista e viene allocato un nuovo blocco di elementi in memoria.

Figura 3.7: Struttura dati che implementa uno store RANDOM.

Quando un elemento viene consumato, la lista viene scandita fino ad arrivare al blocco che contiene quella tupla che verr`a marcata come ’consumata’ e quindi eliminata/migrata da parte del garbage collector. Tutte le richieste successive relative ad un dato ’consumato’ falliranno. I dati scaduti (expired) perch`e troppo vecchi e quelli consumati vengono marcati nello stesso modo e verranno allo

stesso modo migrati/eliminati dal garbage collector. Ci sono due modi con cui il garbage collector pu`o cancellare i dati non pi`u utili:

• Si attende che un blocco sia completamente pieno di elementi consumati (o expired). In tal caso il garbage collector del sistema eliminer`a il punta-tore a tale blocco dalla lista concatenata e il garbage collector del sistema operativo si occuper`a di liberare la memoria.

• Gli elementi all’interno del blocco vengono eliminati non appena con-sumati. I blocchi decresceranno in dimensione fino a venire rimossi comple-tamente. Questo approccio richiede maggiore lavoro da parte del garbage collector ma libera pi`u velocemente la memoria.

Non `e possibile riutilizzare i blocchi cancellati inserendoci nuovi valori prove-nienti dallo stream in quanto, essendo gli aggiornamenti/cancellazioni di tipo casuale, una scansione lineare della lista concatenata restituirebbe elementi che non sono ordinati temporalmente tra di loro (e valutare operatori di finestra temporale su dati non ordinati temporalmente richiederebbe di visitare tutti i dati all’interno dello store), pertanto i blocchi una volta che vengono cancellati non possono pi`u essere riutilizzati e bisogner`a allocare un nuovo blocco che verr`a referenziato dall’ultimo elemento della lista concatenata. Nel caso di store con-diviso, una tupla viene marcata come consumata quando `e stata acceduta da tutti i consumatori. Comunque bisogna sempre garantire che un consumatore non possa accedere pi`u volte allo stesso dato (ad esempio mantenendo traccia del mapping tra i consumatori e le tuple a cui hanno acceduto).

Implementazione di uno store FIFO

Uno degli aspetti negativi dell’implementare uno store in modalit`a RANDOM riguarda la gestione della memoria poco efficiente. Questo si verifica in seguito al fatto che i blocchi vengono continuamenti creati e rimossi, ma mai riutiliz-zati, facendo calare le performance. La necessit`a di poter accedere e cancellare i dati in maniera casuale impedisce di poter riutilizzare i blocchi consumati, in quanto, come spiegato precedentemente, una scansione lineare dei dati nella lista concatenata restituirebbe tuple non ordinate temporalmente tra di loro. La modalit`a FIFO supera questo problema permettendo di riutilizzare i blocchi completamente consumati inserendo nuovi dati. Questa caratteristica pu`o essere

sfruttata grazie al fatto che la modalit`a FIFO `e implementata da una lista con-catenata circolare di puntatori a blocchi e che il produttore inserisce i dati in maniera sequenziale nella lista. Il risultato `e che, anche se i dati vengono con-sumati in maniera casuale, una scansione lineare della lista fornisce sempre dati ordinati temporalmente tra di loro e quindi gli operatori di finestra temporale possono essere applicati senza la necessit`a di dover scorrere tutta la lista (evi-tando quindi di valutare tutti i dati presenti nello store). Ad esempio, se nella lista ci sono 5 directors che puntano a blocchi di tuple relative a 30 secondi di osservazioni, e la query mi richiede una finestra temporale di 10 secondi, io posso procedere nella lista dal puntatore del director attuale (che contiene le tuple pi`u recenti) all’indietro fino a coprire una finestra di 10 secondi. Una volta coperta la finestra non ho piu necessit`a di guardare anche gli altri elementi perch`e saranno sicuramente pi`u vecchi di 10 secondi e quindi di nessuna utilit`a per quella query. Nel caso di store condiviso, si possono eliminare tutte le tuple che non rien-trano nella finestra temporale pi`u grande. Baster`a trovare il primo blocco che contiene delle tuple che non rientrano nella finestra temporale e cancellare tutti i blocchi ad esso precedenti nella lista.

Figura 3.8: Struttura dati che implementa uno store FIFO. Implementazione di uno store IN-PLACE

Nel caso di store IN-PLACE non ci sono mai cancellazioni, solo inserimenti o aggiornamenti di alcuni valori. Si pu`o utilizzare un unico grande blocco per mantenere tutte le tuple e in tal caso le letture saranno molto veloci ma ci sar`a la necessit`a di bloccare l’intero blocco ogni volta che bisogna eseguire un

aggiornamento. In un contesto dove il flusso di dati entranti `e molto elavato rischierebbe di tenere bloccato il blocco molto spesso e quindi le prestazioni degraderebbero. In alternativa, si possono utilizzare diversi blocchi in modo da ridurre la congestione (simile al partizionamento orizzontale dei database che divide una tabella in pi`u tabelle).

L’implementazione di uno store IN-PLACE prevede l’esistenza di un indice per recuperare rapidamente gli elementi che devono essere aggiornati.