|
LOBOTOMY PROJECT
|
|
HYPPOCAMPUS PROJECT
|
Modello di Disposizione dei
Metadati: Array Linkato
(v0.4, 04.02.2006)
Abstract
Questo documento presenta una struttura dati, attualmente ancora in
fase di perfezionamento, studiata per poter conservare nel filesystem
di Hyppocampus tutti i dati (e, soprattutto, i metadati) dei files
presenti nel sistema e per agevolarne la ricerca.
Sommario:
Introduzione
Sulla mailing list del progetto Hyppocampus si e' piu' volte dibattuto
sul modo migliore di disporre i metadati all'interno del filesystem
fisico, in modo da poter effettuare velocemente ricerche, anche
incrociate, su una quantita' di dati potenzialmente immensa e poter
operare poi sui risultati di tali ricerche delle operazioni di tipo
relazionale, tipiche dei database cui Hyppocampus si ispira.
Allo stato attuale esistono due proposte per soddisfare questa
necessita': qui ne viene presentata una, al momento quella maggiormente
dettagliata, che contempla l'uso di una struttura dati molto
particolare, studiata ad hoc per l'esigenza, chiamata informalmente
"array linkato". Essa permette di effettuare ricerche sia per metadato
che per file, ovvero di reperire sia l'insieme di files cui e'
associato un tal metadato con un tal valore sia l'insieme dei metadati
associati ad un dato file, in tempi non esageratamente lunghi ma
comunque migliorabili.
Si prevede di sperimentare al piu' presto la seguente struttura "sul
campo", realizzando cioe' un piccolo programma che agisca secondo le
specifiche sotto riportate su un insieme ristretto di informazioni,
onde poterne meglio valutare le effettive potenzialita'.
Precondizioni
Prima di iniziare la descrizione della struttura in se', e' bene
fornire qualche informazione sui dati che essa dovra' contenere: i
files saranno identificati univocamente da un numero, un ID, unsigned a
32 bit: il che vuol dire che potranno esistere fino a 4.294.967.296
diversi files. I metadati saranno raccolti entro un insieme predefinito
di tipi, ed ogni tipo sara' identificato a sua volta da 32 bit unsigned
(dunque: 4.294.967.296 possibili tipi di metadati) e sara' descritto da
un nome utente ("nome file", "larghezza immagine", "album del brano
musicale"... Si prevede che tali nomi saranno gestiti con un meccanismo
di internazionalizzazione, onde poter associare ad ogni tipo di
metadato il suo nome utente nella lingua preferita) e da un tipo di
valore (int, char, wchar_t... Indica il modo in cui interpretare i bit
che si troveranno nel nodo di definizione di un metadato).
Come forse intuibile, buona parte degli algoritmi di ricerca si
fonderanno sulle proprieta' matematiche degli unsigned long long che
rappresentano tanto i files quanto i metadati.
Panoramica
iniziale
La struttura si compone di un numero prefissato di array (attualmente
se ne sono ipotizzati 65536, ovvero 2^16) numerati che contengono
ognuno, in modo ordinato, tutti i metadati (di tutti i files) il cui
tipo e'
tipo_metadato % numero_totale_array == numero_array
Tali metadati saranno ordinati in modo crescente per tipo, e al loro
interno i sottoarray di metadati saranno ordinati in ordine crescente
per valore. Da considerare sin da ora che ogni sottoarray di metadati
viene preceduto da un "header", ovvero un elemento dell'array
facilmente identificabile in quanto header e che contiene utili
informazioni sul sottoarray che lo segue.
Ogni array conterra' strutture cosi' definite:
typedef struct NodoArray {
unsigned long next;
unsigned long file;
char flags;
char value [ 64 ];
};
"next" indica il prossimo metadato specificato per il file cui il
metadato si riferisce; "file" l'ID del suddetto file; "flags" e' un
array di bits che fornisce maggiori informazioni sul valore del
metadato contenuti nel nodo (secondo lo schema di seguito presentato);
"value" un insieme di bit che rappresenta il valore del metadato per
quel file, oppure, se sfora la dimensione fissata, un indirizzo per
un'area del disco appositamente preposta a contenere informazioni che
non stanno fisicamente all'interno della struttura dati. Suddetta area
speciale deve ancora essere studiata nel dettaglio, e per ora non se ne
forniscono ulteriori informazioni.
I flags definiti per il nodo sono: {
00000001 nel nodo / puntatore
00000010 un elemento / piu' di un
elemento nel valore
00000100 unused
00001000 unused
00010000 unused
00100000 unused
01000000 unused
10000000 unused
}
A questo punto pare evidente che non solo si puo' facilmente (e
velocemente) reperire l'insieme di files cui e' associato un certo
metadato, ma, ricostruendo la "lista" di metadati che si collegano
logicamente tra loro mediante il parametro "next", anche l'insieme di
metadati associati ad un certo file.
Ricerca
per metadato
La ricerca per metadato avviene in realta' per "tipo" di metadato:
conoscendo quale numero identifica univocamente quel tipo di metadato,
lo si puo' cercare nell'array numero tipo_metadato %
numero_totale_array. Sapendo che i metadati in tale array sono ordinati
innanzitutto per tipo, e' sufficiente proseguire all'interno dell'array
sinche' non si incontra il primo elemento che ha appunto tipo ==
tipo_metadato; ma ricordiamo che ogni sottoarray di metadati e'
preceduto da un descrittore, ovvero un elemento speciale all'interno
dell'array, che riporta nella struttura, anziche' le informazioni
canoniche, i seguenti dati:
next = 4294967296; // questo permette di identificare subito l'elemento
in
quanto header di sottoarray
file = tipo_metadato; // l'unsigned long long che rappresenta il tipo
di metadato
flags = 00000000; // array di bit che descrivono il tipo di dato
permesso per il metadato, descritto sotto
value = numero_di_elementi|numero_blocchi_liberi; // in formato long
long, il numero di
elementi contenuti nel sottoarray
e il numero di blocchi liberi presenti nel sottoarray, prima del
prossimo header
flags per l'header {
00000000 void
00000001 char
00000010 short
00000011 int
00000100 double
00000101 float
00000110 struct
00000111 enum
00001000 unsigned
00010000 long
00100000 array
01000000 permessi piu' valori nello stesso nodo
10000000 ordinati per file (anziche' per valore)
}
In questo modo, e' palese che per avanzare nell'array e' sufficiente saltare da un header all'altro procedendo di
sizeof(NodoArray) * ( *(array_numero_N[posizione_header].value) + (array_numero_N[posizione_header].value[32] )
bytes alla volta, fino a giungere a quello che interessa.
A questo punto, una volta identificato l'inizio del sottoarray, si puo'
procedere con una classica ricerca all'interno di dati ordinati per
valore.
Ricerca per file
Il parametro distintivo di ogni file e' il suo ID, il quale viene
trattato come qualunque altro tipo di metadato: tutti gli ID si
troveranno in uno degli array di metadati (possibilmente in testa ad
uno di questi, per facilitare l'accesso immediato), ordinati secondo
gli stessi criteri. Come accennato, date le proprieta' degli elementi
all'interno degli array l'assembramento dei metadati associati ad un
file consistera' nella ricerca di ogni singolo metadato, dal quale si
passera' al successivo verificando il campo "next" dell'elemento e
cercando nel sottoarray previsto il nodo che ha settato nel campo
"file" l'ID del file che si sta cercando.
E' evidente che questo tipo di ricerca e' assai sfavorito rispetto alla
ricerca per metadato, in quanto consiste a sua volta nella ricerca di
piu' metadati, ma, essendo l'obiettivo primario del progetto la
manipolazione dei metadati e delle relazioni che intercorrono tra loro,
si preferisce sacrificare un poco questo aspetto per garantire veloci
tempi di accesso ai singoli metadati.
Accesso ai dati
In Hyppocampus, anche gli indirizzi dei blocchi che compongono i dati
contenuti nei files veri e propri sono espressi come metadati, che dunque
vanno trattati nello stesso modo di tutti gli altri.
Al contrario di quanto accade con la maggior parte degli attuali filesystem,
i blocchi non hanno un dimensionamento fisso, ma la loro dimensione cambia
a seconda dello spazio libero che si trova tra un blocco e l'altro, e si
tiene traccia della dimensione di ognuno. In questo modo e' molto facile
sia allocare contiguamente buona parte dei files che rintracciare in un
colpo solo tutti i blocchi che compongono l'elemento desiderato. Cio' pero'
implica alcune problematiche nell'indirizzamento dei blocchi, che possono
essere (almeno parzialmente) mitigate con l'introduzione dei "gruppi": dividendo
l'area del filesystem in parti uguali (suddivisione gia' implicita a causa
della molteplicita' degli array dei metadati) e' possibile indicare solo il
gruppo in cui e' stato allocato il file, e l'indirizzo dei singoli blocchi
puo' essere un offset tra l'inizio del gruppo e il blocco stesso.
Da notare che l'array segnato come "dimensione dei blocchi" e' ordinato non per
valore ma per file di appartenenza: in questo modo e' garantito il veloce calcolo
della dimensione reale del file.
E' facile desumere che questi due array (per le dimensioni e per gli indirizzi dei
blocchi) debbano essere gestiti con regole diverse rispetto a tutti gli altri.
Inserzione / rimozione di elementi
E' palese che il maggiore problema con questo tipo di struttura e'
l'inserimento di nuovi elementi negli array: essendo tali elementi
disposti in modo ordinato, sembra d'obbligo dover traslare una parte
dell'array per far posto ad un nuovo elemento che viene prima,
compromettendo, e non di poco, i tempi dell'intero sistema.
Per ovviare, almeno parzialmente, a tali inconvenienti, si pensa di
generare volontariamente dei "buchi" all'interno degli array, in modo
che questi possano ammortizzare gli spostamenti di dati e limitarli a
piccole zone della struttura.
Quando verra' aggiunto un metadato si fara' spazio non ad uno ma a piu'
elementi (il numero e' ancora da definire, ma probabilmente 5 e' un
compromesso, ancora da valutare in via sperimentale), e quando verra'
eliminato lo spazio lasciato libero rimarra a disposizione; i nodi non
occupati potrebbero essere riconosciuti dal fatto che riportano il
valore 0 nel campo "file".
Lasciando delle aree libere all'interno degli array, nel momento in cui
ci sia da inserire un nuovo elemento non si dovra' spostare tutto il
blocco di array che segue ma il blocco che va dalla posizione assunta
dall'elemento al primo nodo disponibile.
Disposizione fisica della struttura
Essendo la struttura disposta in realta' su piu' elementi (gli array)
e' facile ipotizzare che questi possano essere disposti fisicamente sul
disco rigido in modo da allinearsi tra di loro e ai cilindri del disco
stesso, guadagnando sul tempo di latenza fisico richiesto per la
lettura dei dati.
Questo aspetto deve ancora essere approfondito, e non se ne forniscono
qui ulteriori dettagli.
Links
