Alocador de blocos Orlov

O alocador de blocos Orlov é um algoritmo para definir onde um arquivo irá residir em um dado sistema de arquivos (com relação aos blocos), de modo a acelerar as operações de disco.

Etimologia

O esquema é nomeado ao seu criador Grigory Orlov, que primeiro postou uma breve descrição e implementação para o OpenBSD da técnica que mais tarde foi utilizada nas variantes de núcleo do sistema de arquivos rápido do BSD.

Conhecimento

O desempenho de um sistema de arquivos depende de muitas coisas, um dos fatores cruciais é somente como sistema de arquivos grava arquivos no disco. Em geral, é melhor manter os itens relacionados em conjunto. Nos sistemas de arquivo ext2 e ext3 do Linux, por exemplo, os diretórios são espalhados nos cilindros do disco. Imagine a criação de um sistema com os diretórios dos usuários no /home: se todos os diretórios de primeiro nível dentro da /home (ou seja, os diretórios home para inúmeros usuários) são colocadas lado a lado, pode não haver espaço deixado para o conteúdo esses diretórios. Arquivos de arquivos, assim, acabam sendo colocados longe dos diretórios que os contêm, e o desempenho é prejudicado.

Espalhando diretórios no disco permite que os arquivos no mesmo diretório permaneçam mais ou menos contíguos conforme seu número e/ou tamanho cresce, mas existem algumas situações em que isto provoca o espalhamento excessivo dos dados sobre a superfície do disco.

Como funciona

Essencialmente, o algoritmo Orlov tenta espalhar os diretórios de "alto nível", no pressuposto de que eles são independentes uns dos outros. Diretórios criados no diretório raiz do sistema de arquivos são considerados diretórios de alto nível; Ted adicionou uma marcação inode especial que permite que o administrador do sistema tambémpossa marcar outros diretórios como diretórios de alto nível. Se /home está no sistema de arquivos raiz (e as pessoas realmente criam sistemas desta maneira), um comando chattr simples fará com que o sistema trate-o como um diretório de alto nível.

Ao criar um diretório que não está em um diretório de alto nível, o algoritmo Orlov tenta colocá-lo no mesmo grupo de cilindros de seu diretório pai. Um pouco mais de cuidado é tomado, no entanto, para garantir que o conteúdo do diretório também seja capaz de se encaixar nesse grupo de cilindros, se não há muitos inodes ou blocos disponíveis no grupo, o diretório será colocado em um grupo de cilindros diferente, que tem mais recursos disponíveis. O resultado de tudo isso, felizmente, é muito uma localização melhor para os arquivos que são verdadeiramente relacionados uns aos outros e que podem ser acessados em conjunto.

Performance

Desde outubro de 2007, apenas uma marca de referência com o novo alocador parece ter sido postada. Os resultados parecem animadores: o tempo requerido para atravessar transversalmente através da árvore do Linux foi reduzido em bruscos 30%.

Evolução

O esquema Orlov precisa de marcas mais rigorosas; ele também precisa de testes de estresse sérios para demonstrar como o sistema de arquivos se degrada ao longo do tempo.

Ligações externas

• The Orlov block allocator
• Orlov block allocator for ext3 e-mail from Theodore Ts'o to Linus Torvalds and Alexander Viro