In questo paragrafo presentiamo vari studi inerenti la compressione dei dati, il trasferimento efficiente di informazioni in rete, la ricerca di porzioni simili di file e una parte di sincronizzazione remota di file. Tali documenti raccolti, insieme a quelli di Peer to Peer, sono stati tutti analizzati nella fase preliminare della progettazione del nostro lavoro al fine di conoscere lo stato dell’arte sulle metodologie di trasferimento di dati in rete.
Una delle prime ipotesi prese in considerazione per il nostro progetto è stata quella di effettuare la distribuzione dei file effettuando prima una verifica dei dati già presenti sugli host (resemblance detection) per poi effettuare l’invio dei soli dati necessari a ricostruire i file a partire da quelli già presenti (delta compression).
Infatti, una delle ottimizzazioni che possono essere effettuate dalla libreria, è quella di minimizzare la quantità di dati trasmessi dal Committente (nodo che invoca il deployment) ai nodi destinatari (Rappresentanti) della Grid; tali comunicazioni si riferiscono al dispatching del codice, dei dati e dei metadati che il committente deve effettuare verso i nodi destinatari.
L’importanza di questa ottimizzazione è amplificata dalla necessità di distribuire file di grandi dimensioni su una rete geografica oltre che dalla possibilità di diminuire il tempo di invio.
Considerando che potrebbero esserci file o porzioni di file comuni tra successive sessioni di deployment, abbiamo cercato di sviluppare un meccanismo che sfrutti i dati già presenti sugli host di destinazione per minimizzare la quantità dei nuovi dati da trasmettere.
Situazioni frequenti in cui tale meccanismo può risultare molto vantaggioso sono quelle che prevedono successive esecuzioni dello stesso codice utilizzando diversi file di dati, oppure test consecutivi di
più file eseguibili sugli stessi insiemi di dati oppure ancora la compilazione di programmi a partire da librerie standard comuni. Per evitare di inviare delle informazioni che sono già state inoltrate nella griglia si potrebbero usare delle tecniche di individuazione di somiglianze tra file e l'uso di algoritmi di compressione (come il delta encoding) per inviare solo le differenze tra file simili tra loro senza ritrasmettere interamente il file.
Questa problematica è approfondita nell’articolo “Application-specific Delta-encoding via Resemblance Detection” [25]. Il delta encoding è la tecnica che consente di ricostruire un file a partire da un file di base e quindi da una serie di delta (differenze) da applicare allo stesso per ricostruire il file finale. Questo è esattamente quello che accade con le patch che consentono, con piccoli frammenti di dati, di ricostruire una versione più recente di un programma a partire da una release più vecchia senza inviare interamente il nuovo software in rete.
La prima parte dell’articolo precedentemente menzionato tratta il funzionamento della Resemblance Detection, ovvero la tecnica che consente di effettuare il delta encoding non solo tra due differenti versioni dello stesso file, ma tra due file diversi. Con tale tecnica si estraggono e si contano le parti dei file in comune (sequenza di byte che si sovrappongono) chiamate “shingles”. Se il numero di shingles è superiore ad una certa soglia allora è molto probabile che ci sia una parte significativa di dati in comune e quindi il delta encoding è vantaggiosamente applicabile su questa particolare coppia di file. Questa tecnica dà spesso buoni risultati su una piccola parte di file di un dataset e su questi ha degli enormi benefici; nella media però su dati molto eterogenei (file dati e file di testo) i benefici sono molto ridotti se non nulli e spesso la sola applicazione di un semplice algoritmo di compressione come gzip fornisce risultati analoghi o migliori ad un costo computazionale inferiore.
Per capire se fosse possibile applicare questa tecnica di ottimizzazione al nostro caso abbiamo anche analizzato l’articolo "Cluster-Based Delta Compression of a Collection of Files" [26] di Zan Ouyang. In questo studio si valutano i benefici che si hanno, in termini di dimensioni di messaggi da inviare su una rete, utilizzando il delta encoding su un numero elevato di file (in questo caso si tratta di pagine web) rispetto all'utilizzo di tar+gzip.
Abbiamo evinto che questa tecnica non può essere applicata al nostro particolare caso di studio in quanto ci sono delle condizioni da rispettare che non la rendono applicabile.
Innanzitutto il delta encoding deve essere applicato su coppie di file di cui si calcolano le differenze (i delta appunto) e questi file devono essere quindi entrambi "visibili" a chi calcola i delta; inoltre la versione base del file, a cui poi applicare i delta calcolati, deve essere presente sul nodo destinatario.
Nel nostro caso specifico si dovrebbe assumere che il committente abbia una copia di ogni file inviato in precedenza agli altri nodi. Solo in questo modo infatti sarebbe in grado di calcolare le differenze con i file da inviare e di cui trasmettere solo i delta ai nodi destinatari. Nel nostro caso non è possibile però fare assunzioni sul contenuto delle cache del generico nodo destinatario R: in pratica il committente non può calcolare i delta ed essere sicuro che R sia in grado di applicarli ai file di base in quanto potrebbe non averli disponibili.
Inoltre valutando i risultati presentati nell'articolo menzionato, anche se questa tecnica fosse applicabile, si dovrebbe comunque mettere in conto il costo computazionale per il calcolo delle somiglianze tra i vari file considerati. L’applicazione della tecnica nel caso di studio dell’articolo ha portato ad un guadagno in termini di spazio di circa il 25% rispetto alla compressione globale di tutto il set dei file utilizzando tar+gzip (che computazionalmente costa circa un decimo). Altro punto a sfavore per il nostro sistema di deployment su Grid, oltre alla non possibilità di prevedere il contenuto delle cache, è
che il miglioramento di circa il 25% sopra indicato, è riferito all’applicazione dell’algoritmo a grandi quantità di pagine HTML. Come noto queste hanno una gran quantità di elementi ripetuti (tag) e si prestano ottimamente ad un delta encoding. Nel caso del nostro sistema è poco probabile riuscire ad ottenere gli stessi benefici visto che i file sono costituiti da codice e dati eterogenei. Infatti da esempi visti nei documenti studiati i miglioramenti dell’applicazione del delta compression su file di dati (eseguibili, attachment, file di archivio compressi…) sono generalmente inferiori al 2%, anzi spesso vi sono dei peggioramenti dovuti allo spazio occupato dal framework per l’applicazione della tecnica.
Considerata la scarsa efficacia del delta compression nel nostro progetto, si è approfondita la tecnica del resemblance detection per valutare eventuali ottimizzazioni da applicare al nostro sistema di distribuzione di file eterogenei (con cui il delta encoding funziona peggio). Si è pertanto studiato l’articolo “Signature extraction for overlap detection in documents” [27] dove gli autori trattano il problema di identificare i plagi, ovvero documenti che hanno una certa parte di testo in comune con altri documenti (utile per verificare copie di compiti in classe, di tesine e/o di altri testi). Nel documento si discute prevalentemente dell’estrazione delle firme, ovvero un’approssimazione degli “shingles” [25] e quindi della loro comparazione. Un tema simile è trattato in “Finding Similar Files in a Large File System” [28] dove l’autore Udi Manber studia la ricerca di file simili all’interno di un filesystem. Da questi abbiamo evinto che la resemblance detection è un processo computazionalmente molto costoso e che su file di dati produce risultati poco apprezzabili.
Per tale motivo nel nostro progetto abbiamo deciso di implementare un meccanismo di resemblance detection basato su blocchi di dimensione fissa che, anziché trovare le somiglianze tra coppie di file, si basa sulla ricerca di blocchi di dati in comune (par. 3.1.3).
Una tecnica analoga è utilizzata anche in “Redundancy Elimination Within Large Collections of Files” [29] dove vengono analizzate e commentate anche altre combinazioni di tecniche già viste atte a raggiungere lo stesso obiettivo, ma basate in particolare su grandi dataset dove molte tecniche di compressione non sono molto efficaci a causa di una finestra di compressione troppo piccola. Molto interessanti in questo documento sono le prove fatte e l’implementazione della tecnica studiata dagli autori che si chiama REBL (acronimo di Redundancy Elimination at the Block Level).
REBL è una combinazione di varie tecniche: eliminazione dei blocchi duplicati, delta-encoding e l’uso di super-fingerprints che trasforma un costo di confronto di fingerprint da O(n2) ad un costo costante di
un accesso ad una tabella hash. L’intero documento verte sulla spiegazione dell’implementazione di queste tecniche e degli effetti del tuning dei parametri base, che influenzano molto il risultato finale. Tra i risultati del lavoro si mette in evidenza come l’efficacia in termini di spazio di REBL rispetto al TGZ vari da 0.59 a 2.46 (dipende dal tipo di dataset) con un impatto sulle performance non altissimo.
A rendere ulteriormente inefficiente l’applicazione di tecniche di delta encoding su reti geografiche ad alta latenza, è il fatto che per la determinazione dei delta tra due host sono necessari molti scambi di messaggi. Come si evince ad esempio anche in “Improved File Synchronization Techniques for Maintaining Large Replicated Collections over Slow Networks” [30] il framework per la sincronizzazione di due file è composto da due fasi: 1) la costruzione di una mappa per identificare le porzioni in comune ed evitare di rimandarle in rete e 2) la vera e propria fase di delta compression. Sebbene quindi i risultati possano essere interessanti per la sincronizzazione di particolari tipi di file in rete locale, non lo sono nella fattispecie del nostro progetto.
Riteniamo pertanto che la soluzione adottata della sincronizzazione a blocchi possa essere un buon compromesso tra costi e benefici.