notizia ufficiale di Daniel Phillips creatore del nuovo progetto Tux3 un nuovo file system.

Dal momento che tutti sembra divertirsi costruzione di nuovi filesystem questi giorni, pensavo dovrebbe aderire al partito. Tux3 è spirituale e morale successore di Tux2, il più famoso filesystem che non è mai stato liberati. [1] Nei dieci anni da quando è stato Tux2 prototipato su Linux 2.2.13 noi tutti abbiamo imparato una cosa o due su filesystem di progettazione. Tux3 è un scrivere ovunque, impegnarsi atomica, basata BTree versioni filesystem. Come parte di questo lavoro, il venerato HTree utilizzati nella progettazione e Ext3 Lucentezza è ottenere un giro a sostenere meglio NFS e, eventualmente, diventare più efficiente.

Lo scopo principale è di Tux3 di incarnare le mie nuove idee su di archiviazione dati versioni. Obiettivo secondario è quello di fornire una più efficiente snapshotting e metodo di replica per il Zumastor NAS progetto, e un terziario obiettivo è quello di essere meglio di ZFS.

Tux3 è big endian come il Grande Penguin destinati.

Descrizione generale

A grandi linee, Tux3 convenzionale è un nodo / file / directory di progettazione con rughe. Un inode Tux3 tabella è un BTree con attributi di versione a foglie. Un file è un inode attributo che è un BTree con
le versioni di estensioni a foglie. Directory indici vengono mappati in directory di file di blocchi con HTree. Spazio libero è mappata da un BTree con estensioni a foglie.

La parte interessante è il modo inode attributi e sono estensioni di file di versione. A differenza della moda attualmente copia ricorsiva a scrivere disegni e modelli con un albero radice per versione [2], Tux3 negozi di tutti i suoi versioni informazioni nelle foglie di btrees utilizzando la versione puntatore algoritmi descritti in dettaglio qui:

    http://lwn.net/Articles/288896/

Questo metodo promette una significativa contrazione di metadati per pesantemente filesystem di versione rispetto a ZFS e Btrfs. La distinzione Tux3 tra stile e versioni WAFL stile delle versioni utilizzate e di ZFS
Btrfs è analoga alla distinzione tra delta e tessitura di codifica per la versione sistemi di controllo. In realtà il puntatore Tux3 versioni algoritmi sono stati ottenuti da un binario tecnica di tessitura ho lavorato a
prima per il controllo di versione nel giorni in cui noi tutti siamo stati da corsa per la gloria di sostituire il sistema di proprietà Bitkeeper per il kernel il controllo della versione. [3]

Filesystem caratteristiche e limiti

  * Versioning dei singoli file, directory o interi filesystem
  * La replica remota dei singoli file, directory o interi filesystem
  * Tutte le versioni (alias istantanee) scrivibile
  * 2 ^ 60 dimensione massima del file
  * 2 ^ 60 volume massimo dimensioni
  * 2 ^ 48 massimo versioni
  * 2 ^ 48 massimo inode
  * Di dimensioni variabili, assegnati dinamicamente inode
  * Nuovo metodo versioni (versione puntatori)
      -- Versione di estensioni per il file / directory dati
      -- Attributi di versione standard (ad esempio modalità di attesa, uid, mtime, dimensione)
      -- Versione attributi estesi (compresi immediata dei dati di file)
  * Nuovo metodo di aggiornamento atomica (AVANTI registrazione)
  * Nuovo fisicamente stabile directory indice (PHTree)
  * BTree backpointers per robusta fsck

Registrazione avanti

Atomica aggiornamento in Tux3 è un nuovo metodo di accesso chiamato in avanti che evita la doppia scrive convenzionali di journalling e la ricorsive copia comportamento di copia a scrivere.

Ogni operazione di aggiornamento è una serie di blocchi di dati seguito da un impegno blocco. Ogni blocco di commettere negozi o la posizione in cui il prossimo impegnarsi blocco sarà se noto, altrimenti è la fine di una catena di impegna. L'inizio di ogni catena di riferimento si impegna dal superblock.

Impegnarsi dati possono essere logico o fisico. Logico aggiornamenti sono per la prima volta applicato al bersaglio struttura in memoria (di solito un blocco di tabella di inode o il file Indice blocco), poi il cambiamento di blocchi sono fisicamente connesso prima di essere applicata sia verso la destinazione finale o implicitamente fusa con la destinazione tramite logica di registrazione. Questo multi livello la registrazione dei suoni come un sacco di extra iscritto, ma non è perché il logico aggiornamenti sono più compatta di quella fisica e bloccare gli aggiornamenti di molti essi possono essere registrate con un periodico cumulativo di passare ad eseguire il fisico o superiore livello logico aggiornamenti.

Una tipica operazione di scrittura, pertanto, si presenta come una singola misura dei dati seguito da uno impegnarsi blocco, che può essere scritto in qualsiasi punto del disco. Questo è di circa efficiente come sia possibile per un aggiornamento atomica di essere.

Fragmention di controllo

Versioning filesystem a rotazione media tendono a frammentazione. Con una scrittura in qualsiasi strategia, abbiamo una grande quantità di latitudine in scegliere dove scrivere, ma la traduzione di quella capacità in minimzing cerca di leggere è ben lungi dall'essere facile. Per i metadati, si può ripiegare per aggiornare
in luogo utilizzando il metodo di trasmettere la registrazione che agiscono come "due volte di scrivere"
ufficiale. Perché i metadati è piccola (almeno quando il filesystem è non pesantemente le versioni) di spazio sufficiente di impegnare il singolo blocco richiesta per accedere logicamente un "metadata aggiornamento, di norma, essere disponibili vicino alla posizione originale e l'aggiornamento in luogo di ripiego non spesso necessari.

Quando non vi è alcuna scelta, ma per scrivere nuovi dati lontani da originale location, un metodo chiamato "scrivere in sospeso" deve essere utilizzato, dove il assegnazione obiettivo è reindirizzato secondo una funzione generatrice di un nuovo obiettivo zona lontano da quella originale. Se nella zona è troppo affollato, quindi il prossimo candidato zona più lontano sarà controllati e così via, fino a quando l'intero volume è stato controllato per spazio disponibile. (Analogo ad un hash quadratica.) Ciò significa, anche se è cambiato volto a blocchi di un file di grandi dimensioni non è del tutto evitato, almeno può essere conservato fino a pochi cerca nella maggior parte dei casi. File ReadAhead aiuterà molto qui, perché un certo numero di periferiche in grado di misura essere recuperata in una pass. Fisico ReadAhead contribuirebbe anche di più, a affrontare con cross-frammentazione di file in una directory.
Con il flash di stoccaggio, cercano il tempo è essenzialmente zero e larghezza di banda di trasferimento
è il tema dominante, al quale dovrebbe Tux3 eccellere.

Inode attributi

Un inode è un elemento di dimensioni variabili indicizzati dal suo numero di inode nel Inode BTree. È costituita da un elenco di blocchi con attributi standard attributi sono raggruppati secondo la loro frequenza di aggiornamento, e attributi estesi. Ciascun attributo standard comporta un blocco versione etichetta in cui l'attributo è stato cambiato per l'ultima volta. Esteso attributi hanno la stessa struttura di file, e in effetti i dati dei file è solo un attributo esteso. Attributi estesi non sono in versione l'inode, ma l'indice a blocchi di foglia. La atime attributo viene gestita separatamente dal inode tabella per evitare di inquinare il tavolo con inode Versioni generati da solo filesystem di legge.

Unversioned attributi:

    Blocco count
      -- Blocco di condivisione rende difficile calcolare in modo giusto dare la
        count blocco totale per i dati attributo BTree

Attributo blocco standard:
    modalità
    UID
    GID

Scrivere attributo di blocco:

    dimensioni - Aggiornamento a scrivere ogni proroga o troncare
    mtime - aggiornare con ogni cambiamento

Dati attributo:

    Né immediata dei dati di file o principale di un BTree indice con le versioni
    estensioni a foglie

Immediata dei dati attributi:

    immediata dei dati di file
    link simbolico
    Versione link (vedi sotto)

Unversioned riferimento alla versione attributi:

    xattrs - versione: Atom: datalen: i dati
    File / Directory dati

Versione collegamenti:

    Il inode può essere liberato quando conta collegamento di tutte le versioni sono pari a zero

Nessuno dei precedenti:

    atime - Aggiornamento con ogni lettura - separare le versioni BTree

Nota: un inode non è mai riutilizzati a meno che non sia libera in tutte le versioni.

Atomo tabella

Attributi estesi sono codificati con l'attributo "atomi" che si svolge in un contesto globale,
unversioned atomo tabella, per tradurre nomi degli attributi in compatto
numeri.

Indice directory

La directory Indice regime di Tux3 è PHTree, che è una (P) fisicamente stabile variante di HTree, ottenute mediante l'inserimento di un nuovo livello di indice blocchi tra l'indice e il nodi dirent blocchi, il "terminale"
Indice blocchi. Ogni terminale Indice blocco è popolato con [hash, blocco] coppie, ognuna delle quali indica che vi è una dirent in <block> con <hash> hash.

Quindi ci sono due "foglia" strati in una PHTree: 1) il terminale di nodi l'indice BTree e 2) la directory contenente i blocchi di dati dirents. Ciò richiede uno extra per ogni operazione di ricerca contro HTree, che è regretable, ma non risolve il problema di stabilità fisica che ha causato così tanto dolore in passato con il supporto di NFS. Con PHTree, dirent blocchi non sono mai scomposto e dirents non sono mai spostato, permettendo la logica di file offset per servire come telldir / seekdir posizione così come avviene per
primitivo come filesystem Ext2 e UFS, su cui la semantica di Posix directory trasversale purtroppo sono basate.

Ci sono altri vantaggi di stabilità fisica di oltre dirents sostenere cervello danneggiato NFS directory trasversale semantica: perché dirents e inode sono inizialmente assegnati nello stesso ordine, una
trasversale della foglia blocchi fisici in modo da eseguire elimina etc, tenderanno ad accedere al inode in ordine crescente, che riduce cache thrashing del inode tabella, un problema che è stato osservato in
pratica, con programmi come HTree che attraversare le directory in hash ordine.

Perché foglia di blocchi in PHTree sono tipicamente pieno invece del 75% come piena in HTree, lo spazio di utilizzo finisce per circa lo stesso. PHTree non BTree nodo a eliminare la fusione (che non HTree) così la frammentazione del tasto cancelletto di spazio non è un problema e un po 'meno uniforme, ma molto di più hash efficiente funzione può essere utilizzata, che dovrebbe fornire notevolmente prestazioni migliori.

HTree assegna sempre nuove directory voci in BTree nodi foglia, scissione, se necessario, in modo che non ha bisogno di preoccuparsi di libero gestione dello spazio a tutti. PHTree tuttavia, poiché le lacune nella
dirent blocchi di sinistra di entrata cancellazioni devono essere riciclati. Un lineare per la scansione di spazio libero sarebbe troppo inefficiente, per cui, invece, PHTree si avvale di un pigro metodo di registrazione delle dimensioni, il massimo disponibile in dirent ogni directory blocco. L'effettiva libera dirent più grande può essere inferiore, e questo verrà rilevato una ricerca quando non riesce, causa il pigro max di essere aggiornato. Possiamo tranquillamente saltare alla ricerca di spazio libero in qualsiasi blocco per il quale il pigro massimo è inferiore a quello necessario dimensioni. Un byte è sufficiente per i pigri max, per cui si 4K blocco è sufficiente a mantenere traccia di 2 ^ 12 * 2 ^ 12 bytes vale la pena di directory blocchi, a 16 meg
directory con circa mezzo milione di voci. Per i grandi directory questa struttura diventa una radice di albero, con pigro max registrate anche a ogni indice puntatore per una rapida ricerca di spazio libero senza dover
esaminare ogni pigro mappa.

Come HTree, un PHTree è un BTree incorporato in blocchi la logica di un file. Proprio come un file, una directory viene letta in una pagina cache di mappatura come blocchi sono accessibili. Fatta eccezione per la cache manca, altamente efficiente pagina cache di radice di albero meccanismo è utilizzato per risolvere i BTree puntatori, evitando molti file di metadati accessi. Una seconda conseguenza di immagazzinare directory indici nei file è che il meccanismo stesso delle versioni che le versioni di un file anche versioni una directory, quindi nulla esigenze particolari da fare a sostegno dei nomi delle versioni in Tux3.

Scaling a un vasto numero di versioni

Che cosa succede come numero di versioni diventa molto grande è qualcosa di un preoccupare. Allora un sacco di metadati per le versioni non possono essere caricato, ricerche e cura. Un relativamente equilibrato versione simmetrica albero può essere suddiviso in una serie di sottostrutture. Fratello sottostrutture
non sono in grado di incidere a vicenda. O (log (sottostrutture)) sottostrutture devono essere caricati e gestiti per qualunque versione.

Per quanto riguarda la scalatura di versione completamente catena lineare? Quindi i dati fortemente ereditato e quindi compressi. Che cosa succede se i dati sono fortemente di versione e quindi non molto ereditato? Quindi dobbiamo memorizzare elementi in ordine stabile e binsearch, che funziona bene in questo caso perché molti genitori non devono essere cercati.

Sono convinto che io stesso a scalare arbitrario numero di versioni provocherà rallentamento peggiore dei casi di non più di O (log (versioni)) utilizzando il metodo descritto sopra. Quando dico "gran numero di versioni" significa "più di qualche centinaio di", quindi non è un problema urgente per oggi versioni filesystem di applicazioni, che usano principalmente versioning loro capacità di attuare il backup e la replica.

Filesystem di espansione e contrazione

(Che cosa potrebbe andare male?)

Più file system che condividono lo stesso volume

Questa è solo una questione di fornire più inode btrees la condivisione libero stesso albero. Non tanto di una sfida, e qualcuno potrebbe avere un bisogno per questo. C'è davvero alcun vantaggio se il volume manager e filesystem già supporto on-demand di espansione e contrazione? Contingenti

(Non hai ancora pensato ancora. Contingenti devono essere globale, multa
grana e libero di stallo.)

Nuove interfacce utente per il Controllo versione

Il metodo standard per accedere a una particolare versione di un volume è tramite una versione opzione il comando mount. Ma è anche possibile accesso versioni dei file attraverso una serie di altri metodi, tra cui una nuova variante di syscall aperto con una versione etichetta parametro.

"La versione di trasporto" permette la versione attualmente montato ad essere cambiato ad alcuni altri. Tutti i file aperti continuerà ad accedere alla versione in che essi sono stati aperti, ma di recente apertura file dovranno avere il nuovo versione. Questa è la "Git Cache".

Tux3 introduce l'idea di una versione link, simile a quello di un link simbolico, ma esecuzione una versione etichetta per consentire il nome di file che devono essere aperti per alcuni altra versione rispetto alla versione attualmente montato. Come collegamenti simbolici, non è necessario che l'oggetto di riferimento è valida. Versione link non introdurre alcuna nuova versione inter-requisito di coerenza, e sono quindi robusto. A differenza di collegamenti simbolici, versione link non sono seguite da predefinito. Questo rende facile attuare una NetApp-come caratteristica di di nascosto. istantanea sottodirectory in ciascuna directory attraverso la quale periodiche istantanee può essere letta da un utente.

Sintesi delle strutture dei dati

Superblock
    Solo fisso fs attributi e puntatori a metablocks

Metablocks
    Come tradizionali superblocchi, ma contenente solo i dati variabili,
    Distribuite in volume, tutti i iniziare a leggere
    Contengono variabili campi, e.g., trasmettere i log

Inode tabella
    Versione standard di attributi
    Versione attributi estesi
    Attributo di versione dati
    Nonversioned BTree file di root

Atime tabella
    BTree albero di versione presso il terminale Indice nodi foglia blocchi sono
    array di 32 bit atimes

Libero albero
    BTree con estensioni a foglie
    sottostruttura accenni di spazio libero su nodi

Atomo tabella
    BTree Un po 'come una directory di mappatura nomi degli attributi per interno
    attributo codici (atomi). Forse dovrebbe essere solo una directory come
    tutte le altre?

Avanti log commettere blocco
    Hash dei dati di transazione
    Magic
    Ss
    Cumulativo - che precedenti voci di registro di ignorare
    I blocchi di dati

Indice directory
    Embedded a rigor di logica, blocchi di directory di file, quindi
    automaticamente le versioni

Attuazione

Attuazione di lavoro è iniziato. Gran parte del lavoro è costituito da taglio e incollato di bit di codice ho sviluppato nel corso degli anni, ad esempio, i bit di HTree e ddsnap. La obiettivo immediato è quello di produrre un gruppo di lavoro prototipo che taglia un sacco di angoli, ad esempio, anziché bloccare i puntatori di misura, di assegnazione bitmap invece di libero misura albero, lineare di ricerca invece di indicizzati, e non atomica impegno a tutti i. Appena sufficiente a dimostrare le versioni algoritmi e sviluppare nuove interfacce utente per il controllo della versione.

Il più grande singolo pezzo di prototipo di lavoro restante per andare da un semplificata prototipo per il filesystem descritto qui è di estendere il versione puntatore algoritmi per gestire le versioni misura, di una sfida po 'di hacking anzi. Gestione delle transazioni a livello di metodo VFS dovrebbe essere anche in una delle principali cause del mal di testa così come lo è stato per ext3. BTree metodi sono più o meno sotto controllo.

Il progetto Tux3 casa è qui:

    http://tux3.org/

Una mailing list è qui:

    http://tux3.org/cgi-bin/mailman/listinfo/tux3

Tutte le parti interessate del benvenuto. Hacker soprattutto benvenuto.

Prototipo comprovanti il codice delle versioni algoritmi è qui:

    http://tux3.org/source/version.c

Mercurial Un albero è in arrivo.

Saluti,

Daniel

[1] Per l'intera storia: google "male + + brevetti vedenti"

[2] Copia a scrivere delle versioni, che ho avuto una mano in inventare.

[3] Linus vinto. Un importante elemento di progettazione Git (la directory manifesto)
è stato dovuto a me e, naturalmente, Graydon Hoare (Google quicksort) merita
più credito di chiunque.