Tesi di Laurea

(1)

Facoltà di Ingegneria

Corso di Laurea Magistrale in Ingegneria Informatica

Tesi di Laurea

Un Meccanismo efficiente per

l’implementazione del modello content-based

Publish-Subscribe su sistemi topic-based

Relatore: Laureando:

Prof. Roberto Baldoni Fabio Papale

Correlatore:

Dott. Leonardo Querzoni

Anno Accademico 2008/2009

(2)

Facoltà di Ingegneria

Corso di Laurea Magistrale in Ingegneria Informatica

Tesi di Laurea

Un Meccanismo efficiente per

l’implementazione del modello content-based

Publish-Subscribe su sistemi topic-based

Relatore: Laureando:

Prof. Roberto Baldoni Fabio Papale

Correlatore: matricola: 1197571

Dott. Leonardo Querzoni

Controrelatore:

Prof. Giuseppe Santucci

Anno Accademico 2008/2009

(3)

Ai miei genitori,

per esser stati un costante sostegno

durante questo lungo e difficile percorso.

Alla mia dolce metà,

per aver camminato al mio fianco

dall’inizio alla fine.

(4)

Ringraziamenti

Per la seconda volta sono arrivato a questo momento, scrivere i ringraziamenti per la mia tesi di Laurea. Finalmente, si spera, che questa sia l’ultima! 

Prima di tutto vorrei ringraziare il Professor Baldoni, per avermi ispirato con le sue parole, portandomi sulla “retta via” : giunto a Roma due anni fa, affascinato dall’Intelligenza Artificiale, è bastata una sola lezione del suo corso per farmi appassionare più che mai ai “Sistemi Distribuiti”, portandomi a rivedere il mio intero piano di studi magistrali. Lo ringrazio inoltre per avermi affidato a Leonardo, che con la sua passione e perspicacia, mi ha guidato ed aiutato durante questo duro lavoro di tesi. Grazie a entrambi per avermi permesso di lavorare ad un’idea così importante ed innovativa.

Inoltre un enorme Grazie ai miei genitori e alla mia famiglia, per avermi sostenuto in questa pazza idea di specializzarmi a Roma. Grazie mamma e papà per tutto quello che avete sempre fatto per me, e non vi preoccupate più:

finalmente è finita!!!

Infine, un ultimo ringraziamento lo voglio fare a quella pazzerella che è venuta a Roma con me: Floriana, grazie per avermi aiutato e sostenuto in questi due anni, e soprattutto per tutti quei momenti (e vi assicuro che sono stati tanti) in cui ti rompevo le scatole cercando di spiegarti tutte le contorsioni mentali dei Sistemi Distribuiti e di questa tesi! Grazie Amore.

Grazie a tutti.

Fabio

(5)

Un meccanismo efficiente per l’implementazione del modello content-based Publish-Subscribe su sistemi topic-based

Indice

Capitolo 1 - Introduzione ...3

1.1. Contributo della tesi...7

1.2. Organizzazione del testo...8

Capitolo 2 - I sistemi Publish-Subscribe ...9

2.1. Descrizione del sistema...9

2.2. Caratteristiche di disaccoppiamento...14

2.3. Altri paradigmi di comunicazione...15

2.4. Meccanismi di selezione delle notifiche...17

2.4.1. Channel-based selection...18

2.4.2. Topic-based selection...18

2.4.3. Content-based selection...19

2.4.4. Type-based selection...19

2.4.5. Schemi misti...19

2.5. Un approfondimento sui meccanismi topic-based e content-based...20

2.6. Implementazioni...21

2.6.1. CORBA Event Service...21

2.6.2. TIBCO Rendez-vous...23

2.6.3. SCRIBE...23

2.6.4. TERA...24

2.6.5. Elvin...25

2.6.6. Gryphon...25

2.6.7. SIENA...26

2.6.8. JEDI...26

2.6.9. Hermes...27

2.6.10. REBECA...27

(6)

Capitolo 3 - Trasformare un sistema topic-based in content-based...28

3.1. Introduzione al problema...28

3.2. Una corrispondenza dinamica tra spazi continui e insiemi discreti...31

3.2.1. Discretizzare lo spazio continuo multidimensionale...32

3.2.2. L’albero di sistema (ST)...35

3.2.3. Il problema dei falsi positivi...36

3.2.4. I protocolli di discretizzazione dinamica...38

3.2.5. Garantire la consistenza degli alberi nel sistema distribuito...45

3.3. L’interfaccia content-based...48

3.3.1. La pubblicazione di un evento...49

3.3.2. Sottoscrizioni ed advertisements...49

3.3.3. Annullamento di sottoscrizioni ed advertisements...52

Capitolo 4 - Test e risultati sperimentali...54

4.1. L’ambiente di simulazione...54

4.2. I test effettuati...56

4.2.1. Analisi dei tempi di risposta del sistema...56

4.2.2. Efficienza della discretizzazione dinamica...59

4.2.3. Costo della discretizzazione dinamica...63

Conclusioni...64

I risultati ottenuti...64

Sviluppi futuri...65

Appendice A - Implementazione del sistema...66

Bibliografia...75

(7)

Capitolo 1

Introduzione

Le architetture dei grandi sistemi informativi sono, ancora oggi, nella quasi totalità dei casi, costruite su piattaforme client/server. Nel paradigma client/server due host interagiscono tra loro: uno richiede dati o funzionalità (client), mentre il secondo (server) li fornisce. Il tipo di comunicazione è sincrono: il client invia una richiesta al server; questo la elabora, e quindi invia la risposta al client. Durante tutto il periodo di interazione, client e server risultano impegnati esclusivamente nella transazione e quindi impossibilitati ad eseguire altre operazioni.

Un esempio di architettura client/server ci è dato dal World Wide Web e nello specifico dal protocollo HTTP usato per richiedere pagine HTML ad un server web. In questo caso il client, impersonato da un browser, richiede al server una specifica pagina HTML; il server, ricevuta la richiesta, la elabora, ed invia il contenuto della pagina al client. In questo semplice esempio è possibile intravedere le caratteristiche del modello client/server che ne costituiscono la sua forza, ma anche la sua debolezza.

Innanzi tutto è bene notare che nei sistemi client/server le entità che possono interagire in un dato istante sono solo due (client e server): questo rende molto più difficoltosa la realizzazione di applicazioni che richiedono comunicazioni uno-a-molti o molti-a-molti, infatti il server deve essere strutturato in modo tale che sia possibile gestire parallelamente più canali di comunicazione indipendenti con altrettanti client distinti. Inoltre il client, cioè l’host che inizia la comunicazione, deve necessariamente conoscere l’indirizzo di rete del server a cui richiedere le informazioni di cui necessita, e non potrà quindi ottenere servizi se non dai server a lui noti; questa caratteristica è detta accoppiamento spaziale. Il paradigma richiede, affinché la comunicazione abbia luogo, che

(8)

Capitolo 1: Introduzione

entrambi gli host siano attivi al momento della comunicazione: se il client invia una richiesta, ma il server che deve riceverla non è in quel momento attivo, il client aspetterà inutilmente una risposta che non arriverà mai, fino allo scadere di un timeout; questa caratteristica prende il nome di accoppiamento temporale. Per concludere, come abbiamo già accennato, il paradigma prevede che i due host siano bloccati per tutto il periodo della comunicazione e non possano, durante questo periodo, compiere ulteriori operazioni: questa caratteristica è detta accoppiamento nel flusso delle operazioni.

Nonostante i limiti che abbiamo ora visto, il modello client/server ha riscosso, dalla nascita delle reti di elaboratori ad oggi, un incredibile successo. Ciò è da imputare sia alla semplicità del modello stesso (solo due entità interagiscono con un chiaro flusso temporale delle operazioni), sia alla sua adattabilità a moltissimi ambiti applicativi. Più in generale il paradigma client/server risulta adeguato per tutte quelle applicazioni in cui esiste un soggetto che necessita di un servizio o di un informazione solo in un certo istante nel tempo e sa già da chi ottenere questo servizio; il fatto che l’informazione venga prelevata dalla sorgente su richiesta ha portato a definire questo sistema anche come information pull.

Naturalmente non tutte le applicazioni ricadono in questa categoria. Esistono applicazioni in cui è l’informazione ad iniziare la comunicazione, e non la necessità di ottenere questa stessa informazione. In questo tipo di applicazioni l’informazione interessa solitamente più di un soggetto e può essere prodotta in un istante imprecisato nel tempo: per questo genere di applicazioni è più naturale pensare ad una forma di interazione in cui sia l’entità che produce l’informazione ad inviarla a chi ha espresso un interesse verso quell’informazione (information push).

Un tipico esempio di information push è offerto dai sistemi di monitoring delle quotazioni azionarie: ad ogni variazione nella quotazione di un singolo titolo, vengono avvertite (ma d’ora in poi diremo notificate) tutte le persone che hanno espresso il proprio interesse nei confronti di quel titolo. In questo ambito, gli

(9)

operatori di borsa possono trovarsi nelle condizioni di dover prendere molte decisioni con estrema rapidità a partire dal momento del cambio di valore di un titolo.

Un’applicazione di monitoring basata sul modello client/server interroga costantemente un server posto presso la borsa valori per aggiornare i valori dei titoli (polling). Perché un’applicazione del genere risulti utile deve effettuare interrogazioni con un’alta frequenza per garantire all’operatore un aggiornamento dei valori delle quotazioni con un ritardo massimo stabilito.

Minore è il ritardo massimo accettabile, maggiore è la frequenza delle interrogazioni al server e di conseguenza lo spreco di risorse: infatti ad un incremento della frequenza di aggiornamento corrisponde un incremento della probabilità che tra due interrogazioni successive il valore dei titoli a cui l’operatore è interessato non sia cambiato, rendendo quindi superflua l’interrogazione. Inoltre un’applicazione strutturata in questo modo difficilmente sarà scalabile verso un largo numero di client (ovvero in grado di richiedere una crescita di potenza elaborativa proporzionale alla crescita del numero di richieste da soddisfare): un singolo server dovrebbe elaborare costantemente, una ad una, tutte le richieste provenienti da tutti i client interessati ed inviare ogni volta lo stato aggiornato dei valori.

Appare quindi chiaro che la realizzazione di un applicazione come questa porterebbe ad una forzatura del paradigma client/server.

La ricerca improntata alla risoluzione di questi problemi ha portato all’ideazione di nuovi modelli di comunicazione. Tra questi molto credito è stato dato negli ultimi tempi al Publish-Subscribe.

Publish-Subscribe è un paradigma di comunicazione asincrono che garantisce un totale disaccoppiamento tra produttore e consumatori dell’informazione. I consumatori, chiamati in questo ambito subscriber, possono esprimere il loro interesse verso un sottoinsieme degli eventi, cioè delle informazioni prodotte, ed essere successivamente notificati di ogni evento generato da un publisher (cioè un produttore di informazioni) che appartiene al sottoinsieme a cui essi

(10)

sono interessati. Il punto di forza di questo modello risiede nel totale disaccoppiamento temporale, spaziale e del flusso delle operazioni tra il publisher ed i subscriber. L’introduzione di questo nuovo modello all’interno di applicazioni esistenti al posto di quello client/server ha permesso di migliorare l’uso delle risorse da parte delle applicazioni stesse, lasciando inalterato il modo di operare degli utenti.

Come si vedrà nel capitolo successivo (cfr. paragrafo 2.4), i sistemi Publish- Subscribe si differenziano principalmente in base al meccanismo di selezione delle notifiche. Nel corso degli anni, uno dei meccanismi che ha riscosso maggior successo è il topic-based, ed il motivo di tale successo è facilmente riconducibile alla sua estrema semplicità (per un approfondimento vedi anche paragrafo 2.5), la quale porta ad implementazioni molto efficienti. Il rovescio della medaglia di questo meccanismo è il problema dei falsi positivi, o più comunemente detti spam: siccome in un tale sistema gli utenti possono scegliere soltanto l’argomento, cioè il topic, degli eventi o delle sottoscrizioni da pubblicare, senza poter esprimere ulteriori vincoli, la probabilità di ricevere degli eventi che in realtà non sono di interesse è alta.

Per questo motivo, negli ultimi anni, la ricerca si è spinta verso altri meccanismi di selezione delle notifiche, individuando in quello content-based una valida alternativa al precedente.

Ad oggi molte sono le proposte di sistemi Publish-Subscribe basate su tale meccanismo (cfr. paragrafo 2.6), che quindi permettono una selezione molto più granulare dell’insieme di eventi di interesse, basata sui contenuti degli eventi pubblicati e non solo sull’argomento; di conseguenza, tali sistemi riescono ad abbattere la probabilità di ricezione dei falsi positivi.

Purtroppo, data la complessità di tali sistemi, che durante le pubblicazione devono essere in grado di realizzare un instradamento che sia funzione del contenuto degli eventi stessi, non si riesce ancora a raggiungere i livelli di efficienza dei sistemi Publish-Subscribe di prima generazione.

(11)

1.1 Contributo della tesi

In questo lavoro di tesi si è cercato di superare i limiti di efficienza che affliggono i sistemi Publish-Subscribe content-based appena evidenziati, sviluppando principalmente due idee innovative:

 Realizzare un sistema Publish-Subscribe content-based al di sopra di un generico sistema topic-based, sfruttando quindi l’efficienza di questi ultimi durante l’instradamento di eventi e sottoscrizioni, e contemporaneamente riuscendo a fornire agli utenti un’interfaccia altamente espressiva, tipica dei sistemi content- based.

 Realizzare un’associazione dinamica tra uno spazio continuo multidimensionale ed un insieme discreto di elementi, rappresentando questi i modelli dei dati su cui si basano rispettivamente i sistemi content-based e topic-based.

In particolare, lo sviluppo di queste due idee ha richiesto:

 La realizzazione di un meccanismo dinamico di mapping in grado di associare ad ogni evento definito dal modello content-based sovrastante, uno ed un solo topic del sistema topic-based sottostante.

 L’implementazione di un prototipo dotato di interfaccia content-based e del meccanismo di mapping dinamico del punto precedente.

 La scelta di un ambiente di simulazione topic-based in cui poter inserire il prototipo al fine di testare l’efficienza del meccanismo dinamico ideato.

 L’esecuzione di una serie di simulazioni e test sperimentali, e la relativa analisi dei risultati ottenuti.

(12)

1.2 Organizzazione del testo

Nel capitolo successivo analizzeremo le caratteristiche salienti del modello Publish-Subscribe ed i suoi punti di forza rispetto a quello client/server; faremo quindi un confronto con altri paradigmi nati come alternativa al client/server, analizzeremo le varie tipologie di sistemi Publish- Subscribe, approfondiremo le differenze fra due di queste tipologie (i topic- based ed i content-based), per concludere poi con un’analisi dei sistemi che rappresentano lo stato dell’arte per le architetture Publish-Subscribe.

Nel terzo capitolo entreremo nei dettagli di realizzazione delle idee alla base di questo lavoro di tesi; vedremo come sia possibile elevare un generico sistema topic-based in un più complesso sistema content-based, realizzando un meccanismo dinamico per il mapping tra i modelli dei dati dei due sistemi, senza modificare i meccanismi di instradamento degli eventi e delle sottoscrizioni propri del sistema topic-based.

Il quarto capitolo sarà quindi interamente dedicato ai risultati degli esperimenti che abbiamo svolto tramite un prototipo appositamente sviluppato, ed integrato in un simulatore di un particolare sistema topic-based: TERA. Tali esperimenti, ideati con lo scopo di confrontare il sistema sviluppato con soluzioni basate su mapping statici, mostreranno come il nostro sistema, dotato di un meccanismo di mapping dinamico, riesca ad essere, ad un costo relativamente basso, molto più efficiente di sistemi content-based basati su mapping statico dello spazio degli eventi.

(13)

Capitolo 2

I sistemi Publish-Subscribe

2.1 Descrizione del sistema

Un sistema Publish-Subscribe è essenzialmente costituito da un insieme di client che scambiano eventi tra di loro in modo asincrono comportandosi, secondo il caso, da produttori o consumatori di informazione [4, 5]. Un’entit{

logica, chiamata event notification service (d’ora in avanti ENS), agisce come mezzo di interconnessione, garantendo il disaccoppiamento tra i publisher ed i subscriber (Fig. 2.1). Possiamo immaginare l’ENS come un servizio raggiungibile da tutti gli host tramite il quale essi possono comunicare; il modello architetturale sarà a breve approfondito.

Figura 2.1: Architettura Publish-Subscribe

Un evento è costituito da dati strutturati solitamente secondo uno schema nome-valore. Per riprendere l’esempio precedentemente visto, un possibile evento nel sistema di monitoring delle quotazioni azionarie potrebbe essere [titolo “ACME INC”, valore=125.50].

Un evento può essere visto come un punto all’interno di uno spazio n- dimensionale: se infatti immaginiamo che ciascuno degli n attributi definiti negli eventi rappresenti una coordinata in uno spazio fittizio, un singolo evento

(14)

Capitolo2: I sistemi Publish-Subscribe

definisce un valore specifico per ogni coordinata, identificando quindi un punto nello spazio (Fig. 2.2). Questo spazio fittizio è chiamato event-space ed è una caratteristica di ogni applicazione basata sull’uso del paradigma Publish- Subscribe.

Figura 2.2: Esempio di spazio degli eventi bidimensionale

Ogni subscriber dichiara a quali eventi è interessato tramite l’invio all’ENS di sottoscrizioni. Ogni sottoscrizione contiene un insieme di regole che l’ENS userà per filtrare gli eventi pubblicati e notificare quindi al subscriber solo quelli di suo effettivo interesse.

All’interno dell’event-space una sottoscrizione è rappresentabile come un sottospazio definito dai singoli filtri che la compongono (Fig. 2.2). In questo modo l’interesse di una sottoscrizione verso un evento può essere facilmente verificato controllando l’intersezione nell’event-space tra la sottoscrizione e l’evento (questa operazione è detta matching dell’evento con la sottoscrizione).

L’inserimento di nuove sottoscrizioni o l’eliminazione di sottoscrizioni esistenti avviene tramite l’uso delle primitive subscribe() ed unsubscribe() sull’API (Application Programming Interface) esposta dell’ENS (Fig. 2.1).

I publisher inseriscono eventi nel sistema tramite la primitiva notify() sull’API dell’ENS; questi provvederà quindi a notificare l’evento ai subscriber interessati tramite l’uso della stessa primitiva sull’API di ogni singolo subscriber.

L’ENS `e un’entità che funge quindi da mediatore tra tutti i publisher e tutti i subscriber mascherando l’infrastruttura che permette la comunicazione tra essi.

(15)

Questa entità è un astrazione la cui implementazione varia in modo significativo da sistema a sistema. Nei primi esempi di sistemi Publish-Subscribe l’ENS era realizzato in modo centralizzato con un programma in funzione su un singolo server a cui facevano riferimento tutti i publisher e tutti i subscriber. In seguito ci si è resi conto che un’implementazione centralizzata non poteva in alcun modo porre rimedio ai problemi di scalabilità propri delle architetture client/server, e si è quindi passati ad implementazioni distribuite. In queste ultime l’ENS è composto da un insieme di processi indipendenti, chiamati broker, e posti su host distinti che interagiscono per portare a compimento tutte le operazioni richieste.

In ogni caso, il tipo di implementazione usato per l’ENS è un fattore che rimane completamente trasparente, sia ai publisher che ai subscriber, i quali interagiscono con esso esclusivamente tramite l’API che esso espone.

Nel seguito di questa tesi supporremo di avere a che fare sempre con implementazioni distribuite dell’ENS, il cui modello architetturale sar{ ora brevemente descritto.

Figura 2.3: ENS con un'infrastruttura distribuita

In un sistema Publish-Subscribe distribuito l’Event Notification Service è costituito da un insieme di N processi B1,....,BN, chiamati event brokers, i quali comunicano attraverso scambi di messaggi. Questi processi, ognuno in

(16)

esecuzione su differenti host (o nodi), cooperano in modo da realizzare le funzionalità di un sistema Publish-Subscribe. La figura 2.3 mostra un esempio della struttura interna di un ENS distribuito dove vari brokers (B) collaborano per servire le richieste provenienti dai publisher (P) e dai subscriber (S).

L’architettura generale di un sistema Publish-Subscribe distribuito è mostrata in figura 2.4, ed è principalmente costituita da cinque livelli: Network, Overlay, Routing, Matching e Interface.

Figura 2.4: Architettura generale di un ENS distribuito

Livello di rete. I protocolli di rete legano il sistema Publish-Subscribe alla rete sottostante permettendo la trasmissione dei dati tra i partecipanti. Dato che un sistema Publish-Subscribe può essere distribuito su un insieme eterogeneo di reti, esso potrebbe utilizzare più di un singolo protocollo di rete sia per coprire le possibili eterogeneità software/hardware, sia per massimizzare le performance.

Livello Overlay. Le primitive di comunicazione fornite dal livello di rete sono quindi usate dai broker per scambiare messaggi. Ogni messaggio è inviato da un broker Bi a un broker Bj attraverso un canale di livello applicativo, o link, li,j che li collega. Questi link sono delle pure astrazioni e non rappresentano delle connessioni durature o permanenti, quindi il vicinato di un broker nella rete

(17)

overlay è determinata solamente da una relazione di conoscenza. Tutti i broker e i loro link di collegamento, formano una rete di livello applicativo, la overlay appunto, che incarna il sistema distribuito di notifica di eventi. Questa overlay può essere gestita con una soluzione ad - hoc, specificamente progettata per il particolare sistema Publish-Subscribe in considerazione,oppure con un generico protocollo di gestione dell’overlay (Overlay Maintenance Protocol).

Livello di Routing. In un sistema Publish-Subscribe distribuito gli eventi e le sottoscrizioni possono essere emessi da uno qualunque dei broker che costituiscono il sistema. Quindi il sistema deve essere equipaggiato con un sistema di instradamento degli eventi che sia in grado di realizzare dei corretti flussi degli eventi all’interno dell’ ENS e raggiungere tutti i sottoscrittori interessati. Più formalmente: dato un evento e pubblicato su un broker Bi e una sottoscrizione s emessa su un broker Bj, se la sottoscrizione copre l’evento, il meccanismo di instradamento deve instradare sia e che s su uno stesso broker Bk, dove il matching sarà elaborato. Questo meccanismo di routing è spesso riferito, in letteratura, come event routing, anche se comprende anche le sottoscrizioni. Durante l’instradamento, un evento potrebbe essere ricevuto da qualche broker che non ospita nessuna sottoscrizione coprente; messaggi contenenti tali eventi sono chiamati messaggi di spam, perché il broker spreca risorse locali inutilmente. Tale problema verrà riaffrontato nel corso del terzo capitolo e, rinominato come Problema dei Falsi positivi, sarà studiato in modo approfondito per capire come può essere sfruttato per migliorare le prestazioni di un particolare tipo di sistema content-based, quello proposto in questo lavoro di tesi.

Livello di Matching. Il matching è il processo di controllo se un evento è coperto da una sottoscrizione, cioè se un evento soddisfa le condizioni espresse dalla sottoscrizione. Questa operazione di solito viene effettuata dal sistema Publish-Subscribe in modo da determinare se notificare un evento ad un sottoscrittore oppure no, ma, a seconda della particolare implementazione del

(18)

livello sottostante di instradamento, a volte esso può essere usato anche durante il processo di diffusione degli eventi.

Livello di interfacciamento. Questo livello rappresenta come i client, per esempio i publisher ed i subscriber, interagiscono con l’ENS. Due strategie opposte sono solitamente considerate. Con la prima strategia i broker che costituiscono l’ENS sono dei server specializzati distribuiti e mantenuti da una azienda; ogni broker funge da access point per un numero molto largo di clienti, memorizzando le loro sottoscrizioni e pubblicando i loro dati. Una seconda strategia richiede invece che ogni client partecipi attivamente all’interno del sistema anche come broker. Ogni broker, quindi, elabora solo le richieste provenienti dalle applicazioni locali che vogliono accedere al sistema. E’

comunque possibile un approccio misto, ma ad oggi, nessuna delle proposte esistenti lo adotta.

2.2 Caratteristiche di disaccoppiamento

L’intermediazione fornita dall’ENS ha lo scopo di isolare completamente ciascun client da tutti gli altri. Tale isolamento è in grado di garantire:

Disaccoppiamento spaziale: Gli elementi che interagiscono non devono necessariamente conoscersi dato che sia i publisher che i subscriber agiscono direttamente sull’ENS; quando un publisher inserisce nel sistema un evento non sa quanti e quali subscriber saranno notificati; allo stesso modo quando un evento viene notificato ad un subscriber questi non sa da quale publisher l’evento è stato inserito nella rete, ne quanti sono i publisher facenti parte del sistema. Questa caratteristica semplifica l’uso del sistema in quanto richiede che ogni entità interagente (publisher o subscriber che sia) conosca esclusivamente un punto di accesso all’ENS (solitamente l’indirizzo di rete di un broker).

Disaccoppiamento temporale: I subscriber interessati ad un dato evento non devono necessariamente essere collegati alla rete nell’istante di inserimento di

(19)

esso da parte di un publisher. Allo stesso modo all’istante in cui un subscriber riceve l’evento il publisher potrebbe essere già scollegato. Il disaccoppiamento temporale tra produzione e consumo dell’informazione è totale. Questo semplifica la realizzazione delle applicazioni in quanto lo sviluppatore non deve più preoccuparsi di gestire il sincronismo tra produzione e consumazione dell’informazione.

Disaccoppiamento nel flusso delle operazioni: Il normale svolgimento delle operazioni all’interno di un client non è in alcun modo interrotto dalla necessità di inviare o ricevere un messaggio dall’ENS. L’interazione con l’ENS avviene in modo asincrono all’interno dei client.

2.3 Altri paradigmi di comunicazione

Parallelamente allo sviluppo dei sistemi Publish-Subscribe si è assistito alla nascita di altri paradigmi tutti improntati a risolvere i problemi che affliggono le architetture client/server. Nessuna delle alternative che ora andremo brevemente ad analizzare riesce però a fornire lo stesso grado di disaccoppiamento che abbiamo riscontrato nei sistemi Publish-Subscribe.

Message passing: si tratta di un paradigma di comunicazione strettamente legato al concetto di socket, e come tale rappresenta una forma di comunicazione a basso livello. Con il message passing spesso vengono demandate all’applicazione molte funzioni basilari, come l’indirizzamento fisico o il data marshaling. La produzione dei messaggi è anche in questo caso asincrona, mentre rimane sincrono il consumo degli stessi. Produttore e consumatore sono accoppiati sia nel tempo, dato che entrambi devono essere contemporaneamente attivi al momento dello scambio dei messaggi, che nello spazio, dato che il produttore deve conoscere l’indirizzo fisico del consumatore.

(20)

RPC - invocazione remota: l’invocazione remota di eventi, nelle sue numerose forme, è ad oggi il metodo più diffuso per implementare il calcolo distribuito.

Con l’uso di questo paradigma lo sviluppatore può utilizzare nella propria applicazione metodi remoti come se questi fossero locali. La semplicità del paradigma, unita alla sua potenza, ha decretato il suo successo sin dalla prima apparizione sotto forma di RPC (remote procedure call), per continuare nelle successive incarnazioni object-oriented (Java RMI, CORBA, Microsoft DCOM).

D’altra parte la natura uno-ad-uno della comunicazione con RPC rende poco naturale il suo uso in applicazioni che richiedono comunicazioni del tipo uno-a- molti. Inoltre l’intrinseca sincronia di RPC introduce forte accoppiamento temporale, spaziale e nel flusso delle operazioni sugli host interagenti.

Notifications: si tratta di una forma primitiva di Publish-Subscribe. Con questa architettura i subscriber esprimono il loro interesse in un qualche tipo di informazione direttamente presso il publisher da cui quell’informazione sarà originata. In questo caso si ha un completo disaccoppiamento nel flusso delle operazioni dato che l’informazione verrà recapitata al subscriber solo nel momento in cui sarà disponibile, tramite l’uso di un callback precedentemente dichiarato. Permane invece un forte accoppiamento spaziale dato che ogni subscriber interessato ad un certo genere di informazione dovrà conoscere in anticipo quale publisher sarà fonte di quell’informazione.

Shared spaces: il paradigma distributed shared memory fornisce agli host partecipanti al sistema di calcolo distribuito, uno spazio di indirizzamento comune; la comunicazione tra gli host avviene scrivendo e leggendo dati in questo spazio comune. Il tipo di memoria condivisa pi`u semplice `e fornito dai cosiddetti tuple-spaces, spazi di memorizzazione condivisi in cui le informazioni assumono la forma di tuple ordinate accessibili da tutti gli host partecipanti. La comunicazione tra host avviene tramite una primitiva di scrittura delle tuple (out()), una di lettura e cancellazione (in()), ed una di sola lettura (read()). Gli shared spaces garantiscono un completo disaccoppiamento temporale e

(21)

spaziale tra i partecipanti, ma richiedono che il prelievo delle tuple dallo spazio condiviso sia sincrono.

Code di messaggi: le code di messaggi riprendono molti degli aspetti principali dei tuple spaces aggiungendo caratteristiche di ordinamento temporale dei messaggi, e proprietà transazionali alle operazioni. Le operazioni di prelievo di informazioni dalle code sono simili alla primitiva in() dei tuple spaces, ma in questo caso quale informazione viene prelevata dipende dall’istante di inserimento di questa nella coda e non dalla sua struttura. Come nel caso degli shared spaces le code di messaggi offrono disaccoppiamento nel tempo e nello spazio, ma non nel flusso delle operazioni.

2.4 Meccanismi di selezione delle notifiche

La scelta di un adeguato metodo di selezione degli eventi è un argomento di cruciale importanza nella progettazione di un sistema Publish-Subscribe, in quanto la scalabilità del sistema stesso dipenderà da esso. Un metodo di selezione che imponga scelte troppo generiche porterebbe alla diffusione di notifiche inutili e costringerebbe i subscriber ad effettuare ulteriori filtraggi all’arrivo delle notifiche stesse. D’altra parte un meccanismo in grado di offrire un’alta espressività, e quindi una maggiore specificità nella generazione dei filtri, renderebbe più complesso e computazionalmente impegnativo il meccanismo di routing delle notifiche, cioè quel meccanismo che, all’interno dell’ENS, porta le notifiche dal broker di ingresso a quelli su cui sono registrate le relative sottoscrizioni. Proprio il problema che si pone davanti a questa scelta ha ispirato questo lavoro di tesi, il cui contributo principale è la realizzazione di un sistema in grado di offrire un’alta espressivit{, pur mantenendo la complessità, in termini di routing degli eventi, dei sistemi che impongono scelte troppo generiche. Analizzeremo ora i cinque principali approcci adottati nelle implementazioni oggi esistenti, mettendo in luce il loro grado di espressività.

(22)

2.4.1 Channel-based selection.

I primi esempi di sistemi Publish-Subscribe hanno adottato uno spazio degli eventi suddiviso in canali. Quando un evento viene inserito nel sistema è necessario specificare il canale di appartenenza. Questo meccanismo risulta molto efficace dal punto di vista della consegna degli eventi in quanto la suddivisione in canali degli eventi e dei subscriber permette di adattare noti algoritmi di multicasting al sistema di consegna delle notifiche. D’altra parte sono evidenti i limiti di espressività: se un subscriber ha interesse per più canali simili dovrà inserire una sottoscrizione per ciascun canale; se un subscriber non è interessato a tutte le notizie pubblicate all’interno di un canale, dovrà adottare qualche strategia di filtraggio una volta ricevuta una notifica. E’ chiaro quindi che questo metodo non permette un’alta selettivi`a sulle notifiche se non moltiplicando il numero di canali. A questo si aggiunge l’accoppiamento tra i publisher ed i subscriber dato dal fatto che un publisher deve conoscere in anticipo i canali possibili per poi scegliere quello su cui inserire una notifica, ed i subscriber devono conoscere i canali dai quali potranno ricevere le notifiche a cui sono interessati.

2.4.2 Topic-based selection.

Il passo successivo nell’evoluzione dei sistemi Publish-Subscribe è stata l’introduzione di una gerarchia dei canali. In questi sistemi [6, 7, 8] è possibile creare canali (che in questo caso prendono il nome di topic) nidificati: quando un subscriber sottoscrive un canale riceve tutte le notifiche create in esso o in uno dei canali sottostanti nella gerarchia. Questa semplice modifica ha portato alla realizzazione di prodotti commerciali di successo tramite i quali è possibile implementare applicazioni anche molto complesse. Nonostante la maggiore flessibilità offerta dai sistemi topic-based, in essi possiamo riscontrare tutti i limiti propri dei sistemi channel-based.

(23)

2.4.3 Content-based selection.

Mentre con i due metodi precedentemente analizzati il contenuto di un evento rimaneva opaco all’event notification service, nel caso di content-based selection [9, 10, 11] la selezione delle notifiche da recapitare ai subscriber si basa sull’applicazione dei filtri, da cui le sottoscrizioni sono composte, al contenuto degli eventi. L’incremento di espressività ottenuto permette di ridurre, se non annullare completamente, il rischio di notificare ad un subscriber un evento a cui non è realmente interessato. Il rovescio della medaglia è dato dalla complessità nell’implementazione di efficaci algoritmi di routing delle notifiche e dalla minore scalabilità di sistemi basati su questo metodo. Il content-based routing garantisce un completo disaccoppiamento tra publisher e subscriber.

2.4.4 Type-based selection.

Molto spesso, in un sistema topic-based, le notifiche appartenenti ad un canale oltre a mostrare un affinità nel contenuto, mostrano una quasi totale identità nella struttura. Questa idea ha portato a sostituire il concetto di topic con quello di tipo. Grazie a questa scelta la gerarchia dei tipi non deve essere più esplicitamente dichiarata (come nel caso topic-based), ma viene indotta dalla struttura delle classi che realizzano i tipi.

2.4.5 Schemi misti.

Molte applicazioni richiedono la trasmissione di informazioni dalla struttura variegata che permette di attuare un approccio misto: un primo partizionamento con una metodologia topic-based, per poi affinare la selezione sugli attributi rimanenti per mezzo di tecniche di filtraggio tipiche dei sistemi content-based. Data la varietà delle applicazioni per cui è consigliabile l’uso del paradigma Publish-Subscribe, un approccio misto ha il grande vantaggio di risultare più facilmente adattabile ai vari possibili scenari.

(24)

2.5 Un approfondimento sui meccanismi topic-based e content-

based

Il paragrafo precedente ha fornito una visione generale di tutti i meccanismi di selezione degli eventi su cui si basano i sistemi Publish- Subscribe. In questo paragrafo si vuole dare un approfondimento su due dei meccanismi precedentemente introdotti, dato che sono gli elementi fondamentali di questo lavoro di tesi: i meccanismi topic-based e content-based.

Come si vedr{ nel terzo capitolo, l’obiettivo di questo lavoro di tesi è quello di trasformare un sistema Publish-Subscribe topic-based in un sistema content- based, con l’intento di superare i limiti imposti dal primo modello senza introdurre l’eccessiva complessit{ che caratterizza le implementazioni del secondo modello. Questo paragrafo, quindi, analizza in modo più approfondito i due modelli confrontandone vantaggi e svantaggi.

In un sistema topic-based il modello dei dati è estremamente semplice: esso è caratterizzato da un insieme discreto di argomenti, i topic, ai quali gli utenti

“devono” riferirsi per pubblicare eventi o per comunicare i loro interessi, cioè effettuare le sottoscrizioni (figura 2.5). Questa estrema semplicità porta a realizzare implementazioni molto efficienti, che riescono ad avere dei livelli di routing e di matching (vedi paragrafo 2.1) molto efficaci e veloci.

In un sistema content-based invece, il modello dei dati non è più un insieme discreto, bensì diventa uno spazio continuo multidimensionale definito da una serie di attributi (una dimensione per attributo), i quali a loro volta definiscono il “contenuto” degli eventi. Gli utenti di un sistema content-based, quindi, pubblicano eventi definiti all’interno di questo spazio (ogni evento è un punto dello spazio multidimensionale), e comunicano le loro sottoscrizioni, le quali rappresentano una particolare regione multidimensionale contenuta nello spazio del sistema. In questo modo, ad un sottoscrittore saranno notificati solo e soltanto quegli eventi che ricadono nelle regioni di interesse da lui definite.

(25)

Indubbi sono i vantaggi di una tale soluzione, ma come anticipato nel paragrafo precedente, essa comporta implementazioni dei livelli di routing e di matching abbastanza complesse.

Figura 1.5: Confronto tra i meccanismi topic-based e content-based

Questo lavoro di tesi, quindi, cerca di realizzare un’implementazione efficiente del meccanismo content-based, prendendo come punto di partenza il meccanismo topic-based, per cercare di sfruttare l’efficienza dei livelli di routing e di matching che si riesce ad ottenere con questo tipo di sistemi. Il terzo capitolo, quindi, affronta la problematica di come realizzare una tale implementazione.

2.6 Implementazioni

Analizzeremo ora le principali implementazioni esistenti del paradigma Publish-Subscribe.

2.6.1 CORBA Event Service.

Un richiesta CORBA standard genera un tipo di comunicazione sincrono. Per superare questa limitazione e permettere un maggiore disaccoppiamento nella comunicazione tra processi, l’OMG ha introdotto il concetto di Event Service.

L’Event Service [5] `e un servizio offerto da CORBA che permette di disaccoppiare la comunicazione tra oggetti. Esso definisce due ruoli per gli

(26)

oggetti: produttori e consumatori di informazione. L’informazione viene fatta transitare dai produttori ai consumatori attraverso richieste CORBA standard.

CORBA Event Service supporta due tipi di approccio per l’avvio di una comunicazione e due per forma che la comunicazione può assumere. I due approcci possibili per instaurare una comunicazione sono il modello push e quello pull. Il primo permette ad un produttore di informazioni di iniziare il trasferimento dei dati verso i consumatori; il secondo permette al consumatore di iniziare la comunicazione richiedendo i dati ad un produttore. Nel primo caso l’iniziativa è lasciata ai produttori, nel secondo ai consumatori. Il tipo di comunicazione può poi essere generico o tipizzato. Nel primo caso l’informazione, oggetto della comunicazione, è completamente nascosta al servizio: la comunicazione avviene quindi per mezzo di semplici operazioni di push/pull nelle quali l’unico parametro è il pacchetto contenente l’informazione da trasferire. Nel secondo caso l’informazioni è strutturata e può essere definita come lo sviluppatore preferisce.

L’Event channel permette a più produttori e più consumatori di comunicare in modo asincrono comportandosi esso stesso come produttore e consumatore.

CORBA Event Service si configura quindi come una classica implementazione di servizio Publish-Subscribe channel-based.

Successivamente l’OMG ha rilasciato la specifica relativa a CORBA Notification Service [12], un’evoluzione dell’Event Service. All’interno di CNS i messaggi possono essere di tre tipi: CORBA Any, un oggetto corba tipizzato in modo statico, o un Structured Event composto da un tipo, più campi filtrabili con una struttura nome-valore, ed un payload non filtrabile. Nel caso venga utilizzato quest’ultimo genere di messaggi, il canale permette ai consumatori che vogliono dichiarare il proprio interesse, di specificare un filtro da applicare ai messaggi in transito attraverso il canale. Oltre a questa caratteristica, che avvicina CNS ai sistemi Publish-Subscribe content-based, è anche possibile “federare” più canali indipendenti in modo da formare una semplice rete per la diffusione degli eventi.

(27)

2.6.2 TIBCO Rendez-Vous

TIBCO Rendezvous [13] è un’implementazione commerciale di grande successo del paradigma Publish-Subscribe. Si tratta di un sistema topic-based distribuito.

Il suo funzionamento è incentrato sulla definizione di una spazio di indirizzi comune tanto ai messaggi quanto ai subscriber. Ciascun subscriber si registra presso il servizio indicando gli indirizzi a cui è interessato (il linguaggio per la dichiarazione degli indirizzi è reso più espressivo dalla possibilità di usare wildcards). Allo stesso modo, all’atto della generazione di un messaggio da parte di un produttore, questo viene associato ad uno o più specifici indirizzi e recapitato quindi a tutti i relativi subscriber.

2.6.3 SCRIBE

SCRIBE [6] è un implementazione del modello Publish-Subscribe topic-based basato su una overlay network gestita da Pastry [14]. SCRIBE è in grado di gestire un alto numero di topic, ciascuno associato al proprio gruppo di publisher e subscriber. Ogni subscriber deve dichiarare il proprio interesse per un certo topic al sistema; questo mantiene, per ogni topic, un albero di multicast che ha la sua base in un nodo di rendez-vous, e che contiene tutti i nodi che hanno dichiarato il proprio interesse nei confronti del topic.

All’inserimento di un evento all’interno della rete, questo viene per prima cosa inviato al nodo di rendez-vous responsabile per il suo topic, e da questo inoltrato, tramite l’albero di multicast, a tutti i subscriber.

Questa particolare gestione dei topic basata sulla definizione di un nodo di rendezvous e sul mantenimento del relativo albero di multicast, deriva dall’infrastruttura peer-to-peer sottostante offerta da Pastry.

Il particolare metodo con cui, dato un topic, viene scelto il relativo nodo di rendezvous (basato sull’hashing del topic stesso), permette una buona distribuzione del carico tra tutti i nodi appartenenti alla rete.

(28)

2.6.4 TERA

TERA [24] è un’implementazione del modello Publish-Subscribe topic-based basato su overlay. La novità interessante che introduce questo lavoro è un meccanismo chiamato “Interest Clustering”, con il quale si cerca di ridurre il traffico inutile all’interno dell’ENS e soprattutto il numero di messaggi indesiderati, i cosiddetti spam, notificati agli utenti.

Dato che questo è il sistema topic-based utilizzato per simulare e testare il sistema sviluppato in questo lavoro di tesi, è doveroso trattarlo un po’ più approfonditamente.

Il meccanismo di interest clustering è basato sul concetto di similarità delle sottoscrizioni: quando le sottoscrizioni di un insieme di client sono sufficientemente simili, allora è possibile unire i client in un unico cluster. In questo modo il cluster riceverà principalmente traffico dati relativo alle sottoscrizioni che hanno dato vita al cluster stesso, diminuendo quindi la probabilità di ricevere spam. In un sistema Publish-Subscribe così fatto, la diffusione di un evento si divide in due fasi ben distinte: in una prima fase, chiamata Outer-Cluster Routing, l’evento deve essere instradato nel sistema fino a trovare il cluster associato alle sottoscrizioni che coprono l’evento; quindi, trovato il cluster, inizia la seconda fase, chiamata Inner-Cluster Diffusion, in cui l’evento viene inviato a tutti i client costituenti il cluster.

TERA, essendo topic-based, implementa un controllo della similarità delle sottoscrizioni molto semplice ed efficiente: due sottoscrizioni si dicono simili se esse si riferiscono allo stesso topic. In questo modo quindi, possiamo avere due casi: o le sottoscrizioni non sono simili perché si riferiscono a diversi topic, oppure sono perfettamente simili, in quanto si riferiscono allo stesso topic.

Come è mostrato in figura 2.6, TERA implementa una overlay a due livelli: il primo livello è costituito da una overlay generale a cui appartengono tutti i client del sistema Publish-Subscribe, ed è qui che viene effettuata la prima fase del processo di diffusione di un evento (in TERA anche le sottoscrizioni vengono diffuse in questa overlay), tramite un cammino random nel grafo costituito dai

(29)

nodi della overlay; il secondo livello è costituito invece da una serie di overlay, una per ogni cluster di similarità, ed è qui che avviene la seconda fase del processo di diffusione di un evento, diffondendo l’evento in tutti i client della cluster overlay che copre l’evento.

Figura 2.6: Architettura di TERA

2.6.5 Elvin

Elvin [15, 16] è un prototipo avanzato di sistema Publish-Subscribe content- based. La sua caratteristica principale è un meccanismo, chiamato di quenching, usato dai publisher per ridurre il numero di notifiche generato; in base a questo meccanismo ciascun publisher può interrogare il sistema per ottenere una rappresentazione degli interessi espressi dai subscriber; sulla base di questa rappresentazione il publisher può quindi stabilire quali eventi devono essere notificati e quali invece possono essere scartati, in quanto non sarebbero di interesse per nessun subscriber.

Il problema generato da questo metodo è dato dal fatto che, quando un publisher abilita il quenching su di un server, questi girerà su di lui l’intero database delle sottoscrizioni per ogni singolo cambio di sottoscrizione, generando una notevole quantità di traffico.

2.6.6 Gryphon

Gryphon [17] è un implementazione del modello Publish-Subscribe realizzata dalla IBM. Esso implementa sia un meccanismo di selezione delle notifiche basato su topic sia un più complesso content-based. Il sistema è composto da

(30)

una serie di broker (architettura multi broker) suddivisi in cluster detti “celle”;

ciascuna cella copre una limitata area geografica ed, all’interno di questa, offre un servizio scalabile e tollerante ai guasti; per ottenere una maggiore copertura geografica, più celle possono essere connesse tramite un numero arbitrario di link, in modo da garantire che la rete rimanga sempre connessa; eventuali cicli all’interno della rete vengono gestiti dai protocolli interni a Gryphon.

Oltre a queste caratteristiche Gryphon implementa anche diversi sistemi di sicurezza che ne permettono l’uso anche su reti pubbliche.

2.6.7 SIENA

Siena [10, 18] è un ENS distribuito con content-based routing.

La grande novità introdotta da Siena consiste in un meccanismo, chiamato di

“covering delle sottoscrizioni” che permette di ridurre la quantità di sottoscrizioni che il sistema deve inoltrare sulla rete per poi poter effettuare un corretto routing delle notifiche.

Oltre a questo Siena introduce anche il concetto di “Advertising delle pubblicazioni” tramite cui i publisher possono annunciare in anticipo il tipo di eventi che intendono pubblicare sulla rete.

Queste due caratteristiche permettono di “tagliare” parti della rete che costituisce l’ENS (che deve avere obbligatoriamente una topologia aciclica) dalla propagazione di certi eventi in quanto, le informazioni ottenute dalle sottoscrizioni e dagli advertisement delle pubblicazioni, garantiscono che tali rami non contengono subscriber interessati.

Il concetto di advertisement di una pubblicazione introdotto da questo sistema, sarà ripreso nel terzo capitolo, in quanto risulta un elemento fondamentale per il sistema sviluppato in questo lavoro di tesi.

2.6.8 JEDI

JEDI [19] è un’implementazione del modello Publish-Subscribe con content- based routing sviluppata presso il Politecnico di Milano.

(31)

L’ENS fornito da JEDI è distribuito: esso è composto da un numero variabile di nodi connessi in modo da formare una gerarchia alla cui sommità risiede un nodo radice.

Il funzionamento prevede una diffusione parziale delle sottoscrizioni dai nodi che le hanno ricevute fino alla radice. Queste informazioni vengono poi usate per evitare di dover distribuire le notifiche su tutta la rete.

2.6.9 Hermes

Hermes offre un’architettura molto simile a quella già vista con SCRIBE; si tratta quindi di un ENS distribuito sviluppato su un’infrastruttura offerta da una overlay network [20, 21, 22] sottostante.

Ciò che distingue Hermes da SCRIBE è l’implementazione di una tipologia di routing misto basata sia sull’utilizzo di un topic per gli eventi (chiamato in questo caso “tipo”), sia sul contenuto degli eventi stessi. La parte di filtering degli eventi basato sul loro contenuto, trae forte ispirazione dal lavoro svolto con Siena.

2.6.10 REBECA

REBECA [23] è un prototipo di sistema Publish-Subscribe realizzato nell’ambito di un lavoro per una tesi di dottorato. Anche in questo caso il routing degli eventi è basato sul loro contenuto.

La caratteristica più interessante di REBECA è quella di permettere l’uso di diversi tipi di routing delle sottoscrizioni per poter analizzare le loro prestazioni; a seconda dell’algoritmo scelto vengono sfruttati vari gradi di similarità tra le sottoscrizioni per ridurre il traffico dovuto alla loro diffusione all’interno dell’ENS.

(32)

Capitolo 3

Trasformare un sistema topic-based in content-based

3.1 Introduzione al problema

L’obiettivo di questo lavoro di tesi è realizzare, in modo efficiente, un sistema Publish-Subscribe basato su contenuti, che offra quindi la possibilità di esprimere, attraverso le sottoscrizioni, interessi verso particolari contenuti.

Diversamente da quanto accade nei sistemi basati su topic quindi, in cui si possono esprimere solo interessi verso interi argomenti, indipendentemente dai contenuti di un singolo evento, e dove il modello dei dati è rappresentato da un insieme discreto di argomenti, i topic, in un sistema basato su contenuti, possiamo immaginare l’insieme totale degli eventi come uno spazio continuo multidimensionale, in cui ogni dimensione rappresenta un attributo, mentre una sottoscrizione, definita attraverso un insieme di vincoli sui valori degli attributi, e cioè sui contenuti, individua un particolare sottospazio nel quale ricadono gli eventi di interesse. La figura 3.1 mostra la differenza tra i due

Figura 3.1: a sinistra il modello content-based; a destra il modello topic-based

(33)

Capitolo 3: Trasformare un sistema topic-based in content-based

modelli: un modello content-based tridimensionale di esempio con alcune sottoscrizioni, ed un insieme discreto di topic.

In letteratura troviamo molte implementazioni di sistemi Publish-Subscribe content-based: da sistemi basati su algoritmi e tabelle di instradamento degli eventi di livello applicativo, come SIENA [1], a sistemi basati su reti P2P strutturate, usate per ottimizzare l’instradamento degli eventi [2][3].

La soluzione innovativa che abbiamo deciso di sviluppare in questo lavoro di tesi, per l’implementazione di un sistema content-based scalabile ed efficiente, è basata sull’idea di non realizzare quest’ultimo da zero, bensì di cercare di sfruttare l’efficienza che riescono ad ottenere i sistemi topic-based nell’instradare gli eventi: data la semplicità del modello dei dati, in tali sistemi in pratica si instaura un semplice canale, il topic, tra i pubblicatori ed i sottoscrittori nel quale viaggiano gli eventi. L’idea, quindi, è quella di realizzare un sistema content-based costruito al di sopra di un generico sistema topic-based:

in altre parole, l’obiettivo è quello di realizzare un sistema content-based che utilizzi come livello di instradamento dei messaggi un sistema topic-based, in modo da sfruttare l’efficienza di quest’ultimo e, allo stesso tempo, fornire un’interfaccia utente caratterizzata da una elevata potenza espressiva per la definizione delle sottoscrizioni, tipica dei sistemi basati su contenuti. Tale concetto è schematizzato nella figura 3.2: il sistema offre un’interfaccia content- based e, attraverso il Mapping Layer, cuore del sistema, riesce a capire, per ogni evento appartenente allo spazio multidimensionale, su quale topic inoltrarlo;

dopodiché sarà compito del sistema topic-based sottostante inviare gli eventi. L’MPL, punto fondamentale di questa tesi, sarà presentato in ogni dettaglio nel paragrafo 3.2 .

(34)

Da quanto appena detto, risulta evidente che l’obiettivo principale di questa tesi è quello di sviluppare lo strato intermedio, l’MPL, il cui scopo è quello di realizzare un mapping tra lo spazio continuo multidimensionale che caratterizza i sistemi content-based, e il mondo discreto su cui si basano i sistemi topic-based. La figura seguente (3.3) illustra quanto detto: il Mapping Module, contenuto nel Mapping Layer, dovrà riuscire a determinare, per ogni evento, ovvero per ogni punto dello spazio multidimensionale, qual è il topic responsabile dell’instradamento del particolare evento, in modo da poter poi inoltrare il messaggio nel sistema topic-based sottostante.

Adottando tale modulo, essendo in grado di mappare un qualsiasi spazio continuo multidimensionale in un generico insieme discreto e finito di elementi, saremo in grado, nello specifico, di trasformare un qualsiasi sistema Publish- Subscribe basato su topic in un sistema content-based o, in altre parole, saremo in grado di costruire un sistema Publish-Subscribe content-based partendo da un qualsiasi sistema topic-based.

Concludendo, quindi, il sistema complessivo sarà caratterizzato, rispetto al sistema topic-based sottostante, da una maggiore potenza espressiva per la definizione delle sottoscrizioni, e dalla stessa efficienza per l’instradamento degli eventi.

Figura 3.3: Mapping tra uno spazio continuo ed un insieme discreto di topic

(35)

Nel paragrafo successivo sarà mostrato in dettaglio il livello di mapping, descrivendo come viene realizzata l’associazione biunivoca tra spazio continuo e topic e quali strutture ausiliare usa; viene inoltre introdotto il problema dei falsi positivi e come esso viene sfruttato nel modo migliore da un modulo di retroazione per migliorare le prestazioni.

3.2 Una corrispondenza dinamica tra spazi continui ed insiemi

discreti

Come abbiamo capito dal paragrafo precedente, per realizzare un sistema content-based che sfrutti come livello di instradamento dei messaggi un sistema topic-based è necessario realizzare una corrispondenza biunivoca tra i modelli dei dati dei due sistemi, e cioè tra uno spazio continuo multidimensionale ed un insieme discreto di topic. Tale corrispondenza, basata sulla discretizzazione dello spazio continuo, può essere principalmente di due tipi: statica o dinamica. Il primo tipo prevede una discretizzazione dell’intero spazio degli eventi fatta a priori, indipendentemente dalla distribuzione delle sottoscrizioni e degli eventi, come possiamo vedere in figura 3.4. Un esempio in cui è stata adottata tale soluzione è presentato in [2]: in tale articolo gli autori sfruttano una overlay strutturata per assegnare staticamente ad ogni nodo della overlay un particolare sottospazio.

(36)

Il secondo tipo, invece, prevede una discretizzazione che si adatta alla distribuzione delle sottoscrizioni e degli eventi, in modo da ridurre al minimo il problema dei falsi positivi (vedi paragrafo 3.2.3). Da questa prima e breve analisi possiamo intravedere vantaggi e svantaggi delle due soluzioni: con una discretizzazione statica, e quindi indipendente da una particolare distribuzione di eventi e sottoscrizioni, abbiamo che il numero di falsi positivi rimane costante; invece, nel caso di discretizzazione dinamica, abbiamo che il numero di falsi positivi diminuisce nel tempo, al costo però di introdurre overhead per la gestione della discretizzazione. Dato che un sistema a discretizzazione statica è già presente in letteratura e, volendo ridurre al minimo i falsi positivi che un utente riceve, in questo lavoro di tesi abbiamo scelto di realizzare un sistema a discretizzazione dinamica. Nel corso di questo paragrafo vedremo il Mapping Layer in tutti i suoi dettagli, responsabile della corrispondenza biunivoca dinamica tra lo spazio degli eventi del sistema content-based e l’insieme discreto di topic del sistema topic-based. Nel capitolo 4, invece, sarà approfondita l’analisi accennata precedentemente, e basandoci su risultati di simulazione, capiremo quando e quanto è conveniente utilizzare un sistema a discretizzazione dinamica piuttosto che un sistema a discretizzazione statica.

3.2.1 Discretizzare lo spazio continuo multidimensionale.

Dunque, la strada che abbiamo deciso di percorrere è quella di realizzare un sistema a discretizzazione dinamica, che crei quindi, quando necessario, le dovute associazioni tra sottospazi e topic. L’immagine precedente (figura 3.4) rimane valida in un sistema dinamico, solo che i vari sottospazi, e i relativi topic, anziché essere prestabiliti, vengono creati dinamicamentedal Mapping Layer, in base alle richieste dell’utente, e soprattutto in base alla distribuzione degli eventi. Vedremo a breve infatti, che in base alle frequenze di ricezione degli eventi, il sistema reagirà in modo opportuno cambiando lo stato della discretizzazione, sia introducendo nuovi sottospazi di minor dimensione, sia unendo più sottospazi in uno equivalente.

(37)

Nel nostro modello, la discretizzazione dello spazio degli eventi è rappresentata da un albero, il Discretization Tree (DT) in cui valgono le seguenti proprietà:

 Il nodo radice rappresenta l’intero spazio degli eventi.

 Ogni nodo dell’albero rappresenta un particolare sottospazio.

 I figli di un nodo p rappresentano un livello successivo di discretizzazione del sottospazio rappresentato da p.

 Gli unici sottospazi in cui si possono effettuare sottoscrizioni sono quelli rappresentati dai nodi foglia dell’albero (se fosse possibile sottoscriversi anche a nodi di livello superiore, una pubblicazione in un nodo foglia dovrebbe essere ripetuta per tutti i nodi sul percorso dal nodo foglia fino alla radice).

Per spiegare meglio il DT e la sua associazione allo spazio degli eventi, consideriamo un esempio in cui abbiamo uno spazio bidimensionale costituito dagli attributi x e y: in figura 3.5 possiamo vedere un esempio di discretizzazione effettuata sullo spazio S e il relativo Discretization Tree, dove, ad ogni discretizzazione, il sottospazio è diviso in due sottospazi utilizzando una dimensione come pivot della discretizzazione (quella indicata tra parentesi nei nodi del DT).

(38)

Come si può immaginare dalla figura precedente (3.5), ogni passo di discretizzazione avviene su una sola dimensione, scelta in modo da ridurre il più possibile il numero di falsi positivi che ricadono nel sottospazio che si sta discretizzando (vedi paragrafo 3.2.4 per ulteriori dettagli). Inoltre, un altro fattore importante che regola la discretizzazione di un sottospazio è la cardinalit{ di quest’ultima, ovvero il numero di sottospazi figli da generare: più è alto questo numero, più è alta la probabilità di eliminare i falsi positivi con un’unica discretizzazione, introducendo però maggiore complessit{ nel sistema.

Come possiamo immaginare, il DT avrà una struttura che cambia nel tempo, regolata dal Mapping Module: in base alla distribuzione degli eventi e delle sottoscrizioni, il modulo decide se discretizzare o meno un sottospazio, e se eliminare o meno una discretizzazione presente, cioè un sottoalbero di altezza unitaria, perché non più necessaria (anche in questo caso si rimanda al paragrafo 3.2.4 per ulteriori dettagli).

Infine, lo stato iniziale può cambiare da contesto a contesto: così come possiamo avere un semplice stato iniziale costituito solo dal nodo radice, il che significa non avere discretizzazione, potremmo avere uno stato iniziale costituito da più livelli di discretizzazione. Ad esempio, possiamo considerare come stato iniziale il nodo radice ed i suoi figli: ciò significa che, appena avviato, il sistema ha già un primo livello di discretizzazione. In base ai principi di funzionamento del MPL (vedi paragrafo 3.3 per approfondimenti), questa configurazione può portare, in alcuni scenari, a miglioramenti delle prestazioni.

A questo punto, per completare il mapping tra spazio continuo e topic, è sufficiente associare ad ogni nodo dell’albero un topic. Tuttavia, questo non significa che il Discretization Tree rappresenta l’insieme dei topic attualmente esistenti nel sistema, bensì esso rappresenta soltanto lo stato logico della discretizzazione dello spazio degli eventi. In altre parole, l’insieme dei nodi del DT rappresenta l’insieme dei possibili topic su cui è possibile effettuare operazioni di sottoscrizione, pubblicazione, ecc. Solo quando una sottoscrizione ad un topic viene richiesta per la prima volta, quest’ultimo viene effettivamente

(39)

creato ed associato ad un nodo dell’albero. Più formalmente possiamo affermare che il Mapping Layer realizza una prima corrispondenza biunivoca tra lo spazio degli eventi e l’insieme dei nodi dell’albero, ed una seconda corrispondenza biunivoca tra un sottoinsieme dei nodi dell’albero e l’insieme dei topic (figura 3): solo quando un sottospazio diventa di interesse per qualche sottoscrittore, allora il nodo associato entra a far parte del dominio della seconda corrispondenza, e quindi associato ad un topic.

3.2.2 L’albero di Sistema (ST)

Una volta definita la corrispondenza tra spazio degli eventi e topic, si rende necessaria la definizione di una serie di protocolli indispensabili per il corretto funzionamento del sistema, uno fra tutti il protocollo per la gestione della discretizzazione.

Essendo questo un sistema distribuito, tali protocolli si baseranno sullo scambio di messaggi e, volendo rimanere completamente disaccoppiati dal livello di rete sottostante, abbiamo deciso di utilizzare il sistema topic-based anche per le comunicazioni di sistema. Tuttavia, per non sovraccaricare i topic utente, e soprattutto, per rendere tali protocolli completamente trasparenti all’utente, abbiamo deciso di separare i canali applicativi, in cui viaggeranno gli eventi dei pubblicatori, dai canali di sistema, in cui viaggeranno i messaggi dei protocolli.

Per quanto riguarda i protocolli, oltre ad aver definito un protocollo di regolazione della discretizzazione, abbiamo definito una serie di protocolli che regolano il comportamento dell’interfaccia Content-based offerta all’utente per quanto riguarda l’interfacciamento con il Mapping Layer. Pertanto, mentre il primo è il cuore del modulo di mapping, e quindi sarà trattato in questo paragrafo (sezione 3.2.4), gli altri saranno approfonditi nel paragrafo seguente (3.3). Concentriamoci adesso sul definire un canale alternativo per le comunicazioni di sistema.

La soluzione adottata è quella di utilizzare un canale di sistema indipendente per ogni sottospazio: la scelta è giustificata dalla considerazione che ciò che riguarda un sottospazio è completamente indipendente da eventi esterni al