Indagini empiriche e teoriche sulle prestazioni di reti peer-to-peer basate su grid-file distribuito

Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Introduzione                                                                                                                          3  
L’altra parte importante è  lo studio teorico dei grafi, un argomento della branca 
combinatoria che rappresenta da tempo un valido metodo per la modellazione 
del nostro sistema. Questo studio ha, in particolare, l’obiettivo di definire altri 
aspetti teorici del sistema tra cui la definizione della distanza media, 
corrispondente alla lunghezza media del percorso attraversato in ogni 
interscambio di dati tra peer. 
Le indagini di cui sopra sono state integrate da analisi empiriche circa 
l’evoluzione della struttura. Abbiamo infatti effettuato simulazioni, in base ai 
parametri del nostro modello, che ci hanno permesso di valutare la bont à  delle 
misure teoriche, oltre che fornirci importanti visuali sui vari aspetti delle 
prestazioni del sistema.   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        4  
Capitolo 1 
STRUTTURE DATI E GRID-FILE 
 
L’innovazione insita nel fenomeno dei sistemi peer-to-peer, ha suscitato 
l’entusiasmo degli ambienti di ricerca e ha spinto verso la creazione di decine e 
decine di architetture ed ambienti a suo supporto. 
Diverse famiglie di sistemi fanno capo a questo nuovo paradigma, tra cui: 
l’instant messaging (considerato precursore del P2P), il file sharing (divenuto 
famoso con Napster),  il distributed computing ed il cooperative computing. Le 
strutture tecnologiche ideate nel corso del tempo sono numerose ed è fuori 
luogo eleggere il sistema “migliore”, in quanto ognuno ha punti di forza e 
criticità . I lavori forse più significativi corrispondono però  a quattro 
denominazioni principali: CAN, CHORD, P-GRID e Litwin LH. 
Ciascuno ha particolari tecniche di gestione a fronte di: 
� inserimenti e cancellazioni di risorse  
� ingressi e abbandoni di peer 
� esecuzione di query di ricerca 
Il lavoro di L. Morosato (2002) raccoglie una definizione degli aspetti 
fondamentali di queste strutture. 
 
I “ dati spaziali” 
Possiamo definire gli “spatial data” come uno speciale tipo di dati che possiede 
particolari caratteristiche tali da richiedere metodi “ non standard”  per la loro 
gestione e manipolazione, relativamente agli ambienti tradizionali 
implementati: ad esempio all’interno dei moderni RDBMS - Relational 
DataBase Management System.  
Si tratta di dati che possiedono caratteristiche uniche. Essi hanno infatti una 
struttura complessa (non sono le classiche tuple a dimensione fissa dei database 
relazionali), sono soggetti a frequenti manipolazioni, sono ospitati in sistemi 
dalle dimensioni elevate, non hanno un set specifico di operatori e, soprattutto, 
sono multidimensionali. 
Secondo quest’ultima caratteristica non esiste un ordinamento globale fra gli 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        5  
oggetti che preservi la “spatial proximity” [Gaed97]. In altre parole, non è  
possibile ordinare gli oggetti in modo tale quelli vicini nello spazio 
(bidimensionale o multidimensionale) lo siano anche nella rappresentazione 
lineare. Ciò  rende assai difficile l’applicazione dei tradizionali metodi di 
indicizzazione (come ad esempio B-trees) utilizzati dai moderni databases. 
 
Questi aspetti particolari rendono lo sviluppo dei metodi di accesso a tali dati 
un compito particolarmente gravoso che deve rispondere ad una molteplicità  di 
requisiti, fra cui: 
• Gestione dello storage: molto spesso risulta impossibile mantenere l’intera 
base dati in memoria principale, per questo il metodo dovrà  consentire 
l’integrazione con altri dispositivi di memorizzazione (ad esempio dischi 
rigidi). 
• Ampia gamma di operazioni supportate: il metodo non dovrà  limitarsi al 
supporto di una sola operazione (ad esempio il recupero delle informazioni) a 
discapito degli altri compiti, come l’aggiornamento o la cancellazione. 
• Indipendenza dei dati inseriti: il metodo dove mantenere la propria efficienza 
anche quando i dati inseriti sono distribuiti in modo particolare e non uniforme 
(anche perché  in realtà  raramente i dati sono distribuiti in modo uniforme). 
• Scalabilità : ovvero capacità  di adattarsi e adeguarsi alla crescita della base 
dati sottostante. 
• Efficienza: il recupero delle informazioni deve essere veloce, magari 
paragonabile alto prestazioni fornite da un B-tree unidimensionale. 
• Concorrenza e recovery: data la molteplicità  degli utenti, il metodo dove 
prevedere efficaci tecniche per gestire le transazioni senza penalizzare le 
prestazioni. 
 
Point Access Methods (PAM) 
Si tratta di metodi di accesso multidimensionale ai dati. Furono inizialmente 
definiti per supportare ricerche di tipo spaziale su basi di dati puntuali (ovvero 
databases con elementi mutidimensionali ma senza estensione spaziale). 
Tipicamente essi organizzano i punti (ossia i dati, o files) in buckets 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        6  
(letteralmente “secchi”) ognuno dei quali corrisponde ad uno spazio di storage 
(tipicamente una pagina di disco) e ad alcuni sottospazi dell’universo 
multidimensionale in cui i punti sono distribuiti.  
Fra i Point Access Methods, molto importanti per il nostro lavoro sono i 
cosiddetti “Multidimensional hashing access methods”. Questi metodi usano 
un hashing uni-dimensionale per indicizzare punti d-dimensionali. Sebbene 
non esista un ordinamento degli oggetti d-dimensionali su di una dimensione, 
questi metodi utilizzano tecniche euristiche per garantire che due oggetti vicini 
fra loro nello spazio multidimensionale siano indicizzati nel medesimo bucket 
o in buckets adiacenti. Alcuni esempi di questa metodologia sono il “Grid File” 
[Niev8l], e “EXCELL” [Tamm82]. 
 
Il grid-file 
Il grid-file fu introdotto nel 1981 da Nievergelt, Hinterberger e Sevcik e 
costituisce un tipico esempio di PAM basato su tecniche di hashing. Essa 
scompone lo spazio-universo utilizzando una griglia ortogonale 
d-dimensionale. 
 
 
 
 
Poiché  la griglia non è  necessariamente regolare le celle risultanti dal processo 
di decomposizione possono essere di differente forma e dimensione. Esiste poi 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        7  
una directory che serve per associare le celle ai buckets (i contenitori di dati) 
che a loro volta sono contenuti in distinte pagine su disco. Ne deriva quindi che 
un bucket può  contenere una o più celle adiacenti. Poiché  con il crescere della 
struttura le dimensioni della directory tendono anch’esse ad aumentare di solito 
la directory non può  essere mantenuta in memoria centrale e pertanto essa 
viene gestita su disco. 
In memoria principale invece mantenuta la struttura del grid-file attraverso un 
array d-dimensionali chiamati scales. Ciò  consente risolvere sempre e 
comunque un operazione di ricerca puntuale con al massimo due accessi al 
disco (uno per accedere alla directory e uno per accedere ai dati). 
Il grid-file, se utilizzato per gestire dati uniformemente distribuiti, garantisce 
un’occupazione media dello spazio (da intendersi come capacità  massima dei 
buckets) pari al 69% (ln 2). 
Una tecnica rilevante per poter ottenere elevate prestazione in fase di 
elaborazione delle interrogazione è  il clustering. Tale tecnica implica che tuple 
aventi i medesimi valori su tutti gli attributi o valori uguali su almeno un 
numero minimo di prefissati attributi, vengano fisicamente archiviate vicine fra 
loro. Ciò  significa che una struttura di clustering può  essere implementata 
attraverso processo di ordering definito attraverso una relazione definita su di 
un predeterminato attributo. Non tutte le strutture di accesso ai dati permettono 
l’adozione di tecniche di clustering, ma il grid file lo supporta appieno il 
clustering. 
  
Particolarità del Grid-File 
La caratteristica fondante del grid-file è  l’offrire metodologie d’accesso ai dati 
simmetriche e multi-attributo, qualità  particolarmente importanti visto che 
molte soluzioni concorrenti non supportano tale features. L’utilizzo di strutture 
derivate dai B-tree non consente di raggiungere l’obiettivo definito. 
Il Grid-File (GF) è uno dei più  interessanti metodi in letteratura in grado 
di supportare, anche su file di elevate dimensioni un accesso ai dati 
simmetrico e multi-attributo. 
 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        8  
 
 
Esistono due motivi per cui un “tuple space”, da intendersi come spazio fisico 
(pagina) su memoria principale o secondaria, non può  essere direttamente 
utilizzato per memorizzare le tuple: 
• Le tuple hanno quantomeno due dimensioni mentre l’indirizzamento fisico 
alla pagina è  forzatamente unidimensionale; 
• Le tuple n-dimensionali sono tipicamente caratterizzate da clusters (ovvero 
grappoli di punti concentrati in una determinata area del piano) cosi come da 
regioni vuote o con scarso addensamento, 
Le celle possono essere fra loro differenti in termini di dimensione degli 
attributi (detta anche grandezza o copertura), ma, nonostante ciò , ognuna di 
esse contiene sempre e comunque uno ed un solo puntatore alla pagina di 
archiviazione. 
Il criterio per stabilire le dimensioni di una cella è  il numero di punti presenti 
nella cella stessa, mentre i limiti fra celle vicine/confinanti vengono definiti in 
base alla distribuzione dei valori: in range di valori con un’alta frequenza di 
tuple le celle sono di dimensioni più piccole, e viceversa. 
Quando lo spazio viene suddiviso da piani paralleli agli assi i punti di divisione 
per ogni dimensione vengono memorizzati separatamente in un array detto 
scale. Ogni scale corrisponde ad una dimensione e contiene i valori di quella 
dimensione in cui un “piano divisore” taglia lo spazio n-dimensionale, 
generando cosi nuove celle. In ogni scale i valori dei “punti di taglio” vengono 
memorizzati secondo un ordine ascendente. 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        9  
 
Il GF è dinamico, nel senso che le pagine vengono allocate e rilasciate a 
seconda delle necessità , ecco perché  la suddivisione degli scales in range (per 
ottenere i confini delle celle) deve essere dinamica. Ciò  significa che non 
esistono strutture di celle prestabilite (anche se ciò  renderebbe le cose più 
semplici), ma i confini delle celle vengono definiti dinamicamente in base alla 
distribuzione delle tuple all’interno del grid file. 
Il processo di inserimento di un nuovo elemento inizia con un’operazione di 
recupero, più precisamente una ricerca puntuale, avente lo scopo di individuare 
la pagina in cui la tupla andrà  inserita.  
Se la pagina può  contenere la nuova tupla, ovvero il numero di punti già  
contenuti è  inferiore al prefissato limite massimo di punti archiviabili in ogni 
pagina (detto “ bucket size”), il processo di inserimento termina qui, con 
l’archiviazione della tupla nella pagina individuata. 
Se invece la pagina è già  piena, ovvero il numero di punti già  contenuti 
corrisponde al ‘bucket size” prefissato, essa dovrà  essere suddivisa (splittata) 
in 2 pagine, e di conseguenza anche lo schema di indirizzamento dovrà  essere 
rivisto e adeguato; inoltre visto che la directory del GF ha un page pointer per 
ogni sottospazio e poiché  i limiti di tali sottospazi sono contenuti all’interno 
degli scales, sarà  indispensabile riorganizzare anche gli elementi di tali vettori. 
Il grid-file è in grado di supportare processi di ricerca garantendo elevate 
performance. Ad esempio le interrogazioni di tipo puntuale vengono effettuate 
con un costo costante di 2 accessi al disco. 
 
IBGF: Interpolation Based Grid File 
IBGF è una variante, un’evoluzione del concetto base di grid-file. Questa 
struttura, proposta in letteratura da M. Aris Ouksel [Ouks85], combina le 
proprietà  geometriche del grid-file con quelle tipiche delle strutture di 
manutenzione degli indici basate su algoritmi di interpolazione. 
IBGF opera un partizionamento dinamico dello spazio dati in regioni 
identificabili univocamente e fra loro anche innestate (nested). Ogni regione è  
localizzabile tramite un identificatore univoco, ricavato con un particolare 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        10  
algoritmo di codifica. 
IBGF garantisce, nel peggiore dei casi, prestazioni analoghe ad una struttura 
B-tree in quanto a recupero dei dati  e utilizzo dello storage. Ogni pagina 
utilizza almeno il 33% dello spazio di storage disponibile, ovvero contiene 
sempre e comunque un numero di punti (dati/tuple) non inferiore ad 1/3 del 
bucket size. Misurazioni di tipo probabilistico hanno mostrato che lo storage 
utilization resta quasi sicuramente sopra il 63%. Inoltre, IBGF garantisce 
elevate performance ed un comportamento tendenzialmente omogeneo, 
qualunque sia il tipo di dati trattati. 
 
NIBGF: Nested Interpolation Based Grid File 
NIBGF, proposto in letteratura da M. Aris Ouksel e 0. Mayer, si presenta come 
una nuova struttura che integra ed estende le proprietà  e le performance di due 
strutture precedentemente definite in letteratura: IBGF e BANG file [Free87]. 
Il BANG file mostrò , infatti , limiti di performance in fase di recupero dei dati. 
Tali limiti derivavano principalmente dalla tecnica di nesting adottata, che per 
garantire migliore prestazioni in fase di storage penalizzava i costi di ricerca e 
recupero dei dati.  
NIBGF invece è in grado di garantire costi di ricerca di tipo logaritmico, 
indipendentemente dalla distribuzione dei dati, mantenendo allo stesso tempo 
uno storage utilization elevato tanto quanto nell’originaria versione di BANG 
file. 
L’idea base di NIBGF è  quella di decomporre lo spazio d-dimensionale dei dati 
in un numero finito di sottospazi rettangolari (regioni), univocamente 
identificabili, che possono risultare fra loro disgiunte oppure racchiuse una 
nell’altra, e che possono formare delle directory  (organizzate come un B-tree 
bidimensionale), al fine di garantire migliori performance in fase di recupero 
dei dati. 
Tale implementazione di NIBGF permette di soddisfare tutte le principali 
caratteristiche strutturali riconducibili al grid-file, indipendentemente dalle 
caratteristiche dei dati trattati e dalla loro distribuzione. 
Le caratteristiche del grid-file sono certamente degne di nota come le sue 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        11  
qualità  indiscutibili. Uno dei limiti più evidenti è  però  l’ambiente di lavoro: la 
logica del grid-file non si spinge al di là degli ambienti centralizzati dove 
invece esso svolge egregiamente il suo lavoro come gestore di basi di dati in 
genere. Sarebbe quindi interessante poter migrare questa eccellente 
infrastruttura gestionale anche ad ambienti che centralizzati non sono, come 
appunto le reti fra calcolatori.  
 
GGF: Generalized Grid File 
Il problema dell’espansione all’ambiente distribuito di strutture centralizzate 
come quelle del precedente capitolo trova la sua più attuale soluzione in un 
modello: il Generalized Grid File (GGF). Si tratta di un ampliamento di una 
struttura dati già  esistente, NIBGF (Nested Interpolation Based Grid File): 
mentre però  NIBGF crea e gestisce l’archivio dati su di un’unica macchina, 
GGF compie proprio l’espansione d’orizzonte più volte enunciata, riuscendo a 
lavorare su un cluster di computer, ovvero un insieme di calcolatori fra loro 
connessi e comunicanti, ognuno dei quali gestisce una o più pagine della 
struttura dati. 
Si lavora su di uno spazio a d-dimensioni, d sono gli attributi (detti anche campi 
o dimensioni) dei record appartenenti all’archivio. Si considera che il dominio 
di ogni attributo sia ordinato linearmente e limitato da un range definito di 
valori, ogni valore di un attributo possa essere rappresentato da un numero 
razionate net suo intervallo di dominio specifico. Per comodità , si può  
rappresentare ogni dominio con l’intervallo semi-aperto [0,1): si ha quindi che 
ogni record rappresentato nel file di dati può  essere visto come un punto 
dell’ipercubo d-dimensionale Ud= [0,1)d, formante lo spazio con dati 
normalizzati a tale intervallo. Lo spazio dati Ud può  essere diviso in sottospazi 
chiamati regioni. Una regione R è a tutti gli effetti quindi un sottospazio 
iper-rettangolare di Ud. 
Ovviamente in partenza esisterà  solo una regione occupante tutto lo spazio 
dell’ipercubo a d-dimensioni di partenza. La struttura dimensionale può  essere 
soggetta a divisioni con creazione di nuove regioni. Per capire quando ciò  
avviene, definiamo bucket b un numero caratteristico indicante la quantità  
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        12  
massima di record che una regione può  contenere. Quando, a fronte di un 
aumento del numero dei record, causa inserimenti, tale numero viene 
raggiunto, la regione si porta in uno stato, detto di overflow. A questo punto per 
ripristinare una situazione stabile si ricorre ad uno split della regione interessata 
(e solo di essa), ovvero una suddivisione lungo uno degli assi del sistema, 
partendo dall’asse 0 e procedendo ricorsivamente nel caso in cui la situazione 
non migliori immediatamente. 
 
Le regioni 
Ogni regione può  essere identificata con una coppia di numeri, R(pi,l). II 
numero intero 1 indica quante volte è stata suddivisa la regione iniziale per 
arrivare a quella interessata. Il termine pi invece è  ottenuto convertendo in 
decimale il termine bin1(pi), stringa binaria risultante dalla manipolazione delle 
coordinate dello spigolo inferiore sinistro della regione. La metodologia per 
ottenere tale pi è una procedura matematica precisa, che si concretizza nel 
calcolo di un indicatore chiamato TS. 
 
 
I peer 
Con tale sostantivo, nelle reti P2P si indica il mattone fondamentale di queste. 
Si tratta di calcolatori, anche comuni PC, che vengono organizzati per formare 
la struttura distribuita. 
Nelle comuni reti di sharing esistono molto spesso dei ruoli, anche indiretti che 
Indagini empiriche e teoriche  sulle prestazioni  
 di reti peer-to-peer basate su grid file distribuito 
    
Cap. 1 ~  Strutture dati e grid file                                                                                        13  
ogni macchina svolge, o è  portata a svolgere. Ad esempio ci saranno alcuni 
peer che tengono fisicamente in gestione i dati in share; essi quindi sono punti 
di storage per regioni ma anche punti da cui possono partire richieste di ricerca 
di tipo puntuale (dette query exact match) o per intervallo (le range query). 
Inoltre possono per svariati motivi essere presenti attori esterni, nel senso che 
fanno parte della struttura in quanto hanno effettuato join alla rete, inseriscono 
nuove risorse in essa ma non ne prendono gestione. Quest’ultima viene affidata 
ai peer precedenti, mentre essi si adoperano solamente per l’inserimento e la 
ricerca nelle sue forme. 
Va fatta una categorizzazione dei peer proprio a tale scopo, non per questo 
intaccando le fondamenta della filosofia peer-to-peer, in quanto ogni macchina 
può  cambiare in ogni momento il suo ruolo divenendo dell’altra specie. 
Sono detti S-peer (o server) coloro che contribuiscono a porre il loro hardware 
per immagazzinare la struttura dati vera e propria del GGF, a mantenere quindi 
copia fisica dei contenuti della rete. Essi prendono in gestione un certo numero 
di regioni. Tale numero non deve superare una certa soglia detta 
“ Regions-per-server”  avente lo stesso ruolo del bucket-size per le regioni. 
Durante la creazione delle regioni, alla necessità  di uno split, si creerà  una ed 
una sola regione in più rispetto alla configurazione stabile precedente. In 
questo caso bisognerà  controllare se il server ospitante la regione oggetto di 
split sia in grado di prendere in gestione altre regioni. Se il controllo è  
affermativo la nuova regione creata la si affiderà  a lui, se negativa si dovrà  
cercare nel modo migliore un altro S-peer per farlo. 
Sono C-peer coloro che invece sono uniti alla rete ma non prendono parte a 
compiti di storage. Possono in ogni modo effettuare inserimenti di risorse nella 
community, risorse che poi verranno prese in gestione dagli S-Peers e possono 
altresì lanciare query di ricerca per trovare e servirsi dei dati immagazzinati 
 
Inserimento, splitting, bilanciamento e ottimizzazione della struttura 
Le funzioni supportate da GGF non ancora descritte comprendono funzioni 
d’aggiunta d’informazioni e casi in cui tali aggiunte mandano in overflow 
regioni e server rispetto ai parametri di sistema, funzioni di manutenzione della