X
  • ZFS
    May 28, 2008

Mapas de espaço

Guest Author


Todo sistema de arquivos precisa controlar dois itens básicos: onde há dados e onde há espaço livre.

Em princípio, controlar o espaço livre não é estritamente necessário: cada bloco está alocado ou livre, portanto, pode-se calcular o espaço livre pressupondo-se que tudo esteja livre e, depois, subtraindo-se tudo o que está alocado. Para saber o espaço alocado, percorra todo o sistema de arquivos desde a raiz. Qualquer bloco que não for encontrado nessa travessia desde a raiz estará, por definição, livre.

Na prática, localizar espaço livre dessa forma seria intolerável porque seria uma operação extremamente demorada em qualquer sistema de arquivos de um certo tamanho. Para agilizar a alocação e a liberação de blocos, o sistema de arquivos precisa de um método eficiente que permita controlar o espaço livre. Nesta postagem, examinaremos os métodos mais comuns, os fatores que dificultam sua escalabilidade e a nova abordagem que desenvolvemos para o ZFS.

Bitmaps

A maneira mais comum de representar o espaço livre é com um bitmap. Um bitmap é simplesmente uma matriz de bits, na qual o enésimo bit indica se o enésimo bloco está alocado ou livre. O overhead de um bitmap é bem baixo: 1 bit por bloco. Para um tamanho de bloco de 4K, isso significa 1/(4096\*8) = 0,003% (o 8 representa 8 bits por byte).

Para um sistema de arquivos de 1 GB, o bitmap tem 32 KB, algo que cabe facilmente na memória e pode ser examinado rapidamente para encontrar espaço livre. Para um sistema de arquivos de 1 TB, o bitmap tem 32 MB, ainda ajustável na memória, porém não mais trivial em termos de tamanho ou de tempo de exame. Para um sistema de arquivos de 1 PB, o bitmap tem 32 GB e simplesmente não cabe na memória da maioria das máquinas. Isso significa que o exame do bitmap requer a sua leitura do disco, que é um processo ainda mais lento.

Evidentemente, isso não é escalável.

Uma solução aparentemente óbvia é dividir o bitmap em pequenas partes e controlar o número de bits definidos em cada parte. Por exemplo, para um sistema de arquivos de 1 PB com blocos de 4K, o espaço livre pode ser dividido em um milhão de bitmaps de 32 KB cada um. O resumo informativo (o milhão de inteiros que indicam quanto espaço existe em cada bitmap) cabe na memória e isso faz com que seja fácil localizar um bitmap com espaço livre e que seja rápido examinar esse bitmap.

Mas ainda existe um problema fundamental: os bitmaps precisam ser atualizados não apenas quando um novo bloco for alocado, mas também quando um bloco antigo for liberado. O sistema de arquivos controla a localização das alocações (decide em quais blocos inserir novos dados), mas não tem controle sobre a localização das liberações. Algo tão simples como 'rm -rf' pode causar a liberação de blocos em todo o disco. Com nosso exemplo de sistema de arquivos de 1 PB, no pior caso, a remoção de 4 GB de dados (um milhão de blocos de 4K) poderia exigir a leitura, a modificação e a regravação de cada um dos um milhão de bitmaps. Isso representa dois milhões de entradas/saídas no disco para liberar míseros 4 GB, e isso simplesmente não é razoável, nem como comportamento de pior caso.

Mais do que qualquer outro fator individual, este é o motivo pelo qual bitmaps não são escaláveis: as liberações são normalmente aleatórias e os bitmaps que não cabem na memória apresentam um desempenho patológico quando são acessados aleatoriamente.

Árvores B

Uma outra maneira comum de representar o espaço livre é com uma árvore B de extensões. Uma extensão é uma região contígua de espaço livre descrita por dois inteiros: deslocamento e comprimento. A árvore B classifica as extensões por deslocamento, para obter uma alocação eficiente do espaço contíguo. Infelizmente, as árvores B de extensões sofrem da mesma patologia que os bitmaps quando confrontadas com liberações aleatórias.

O que fazer?

Liberações adiadas

Uma maneira de atenuar a patologia das liberações aleatórias consiste em adiar a atualização dos bitmaps ou das árvores B e, em vez disso, manter uma lista dos blocos liberados recentemente. Quando essa lista de liberações adiadas atingir um determinado tamanho, ela poderá ser classificada, na memória, e, depois, liberada para os bitmaps ou as árvores B subjacentes com uma localização um pouco melhor. Não é o ideal, mas ajuda.

Mas e se formos mais adiante?

Mapas de espaço: listas de liberações estruturadas em log

Lembre-se de que, há algum tempo, os sistemas de arquivos estruturados em log levantaram esta questão: e se, em vez de devolver um log de transações periodicamente ao sistema de arquivos, fizéssemos com que o log de transações fosse o sistema de arquivos?

Bem, a mesma pergunta poderia ser feita com relação à nossa lista de liberações adiadas: e se, em vez de devolvê-la a um bitmap ou uma árvore B, fizéssemos com que a lista de liberações adiadas fosse a representação do espaço livre?

Isso é precisamente o que o ZFS faz. Ele divide o espaço de cada dispositivo virtual em algumas centenas de regiões chamadas metaslabs. Cada metaslab tem um mapa de espaço associado, que descreve o espaço livre desse metaslab. O mapa de espaço é simplesmente um log de alocações e liberações, por ordem de tempo. Os mapas de espaço fazem liberações aleatórias e liberações seqüenciais com a mesma eficiência porque, independentemente da extensão que esteja sendo liberada, ela é representada no disco pela sua anexação (dois inteiros) ao objeto mapa de espaço, e as anexações têm uma localização perfeita. De maneira semelhante, as alocações são representadas no disco como extensões anexadas ao objeto mapa de espaço (com, obviamente, um conjunto de bits que as identifica como uma alocação, e não como espaço livre).

Quando o ZFS decide alocar blocos de um metaslab específico, primeiro ele lê o mapa de espaço do metaslab no disco e reproduz as alocações e as liberações em uma árvore AVL de memória com o espaço livre classificado por deslocamento. Isso gera uma representação compacta, na memória, do espaço livre que aceita a alocação eficiente de espaço contíguo. O ZFS também aproveita a oportunidade para condensar o mapa de espaço: se houver muitos pares alocação-liberação que se neutralizam mutuamente, o ZFS substituirá o mapa de espaço no disco pela versão menor na memória.

Os mapas de espaço apresentam várias propriedades interessantes:

  • Não exigem inicialização: um mapa de espaço sem entradas indica que não houve alocações nem liberações, logo, todo o espaço está livre.

  • São escaláveis: como os mapas de espaço são somente para anexação, apenas o último bloco do objeto mapa de espaço precisa estar na memória para assegurar um excelente desempenho, não importa quanto espaço seja gerenciado.

  • Não apresentam patologias: os mapas de espaço podem ser atualizados com eficiência, independentemente do padrão de alocações e liberações.

  • São igualmente eficientes para encontrar espaço livre quer o pool esteja vazio ou cheio (ao contrário dos bitmaps, que levam mais tempo para serem examinados à medida que ficam cheios).

Por fim, observe que quando um mapa de espaço está completamente cheio, ele é representado por uma única extensão. Portanto, os mapas de espaço têm a fascinante propriedade de que, à medida que o pool de armazenamento se aproxima de sua capacidade máxima, eles começam a evaporar, disponibilizando, assim, até a última gota do espaço em disco para informações úteis.

Be the first to comment

Comments ( 0 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.Captcha