O projeto Baardskeerder, como explicado anteriormente, é uma implementação de uma estrutura de dados B-tree, usando um arquivo append-only para manter os dados para um dispositivo de armazenamento (por exemplo, um disco rígido ou dispositivo SSD). A não substituição de dados possui diversas vantagens (garantias de consistência, eficiência,…), ainda que também incorra em uma grande desvantagem: ao longo do tempo, uma quantidade crescente de dados é armazenada e nunca vai ser recuperada, mesmo que os dados em si não forem de uso qualquer por muito tempo (por exemplo, um node de valor não poderia ser mais referenciado porque a key correspondente foi excluída ou um novo valor foi armazenado, nodes internos descrevendo a tree em si se tornam inválidos, porque as mudanças na estrutura da tree mudam quando nos novos conjuntos de key/valor são adicionados,…).

Mesmo que a capacidade de armazenamento se torne menos onerosa, não existe algo como um disco infinito, e não liberar espaço em disco, mesmo que os dados nele contidos não tenham valor real por mais tempo, é inútil.

Uma maneira de reduzir a sobrecarga é reescrever o banco de dados, de modo que ele só tenha os dados contidos na tree no momento em que a ação é iniciada. Chamamos isso de uma “compactação completa”, reescrevendo o banco de dados para um segundo arquivo. Isso tem uma grande vantagem: após a compactação, o novo arquivo de banco de dados será o menor que você pode obter (ele não contém quaisquer dados gerais), e como, esses dados, é armazenado muito compactado.

Também há alguns inconvenientes: a operação não pode ser realizada online sem tomar medidas específicas, uma vez que o banco de dados resultante irá apenas representar um snapshot do original. Também pode haver um problema de capacidade de armazenamento: porque os dados são copiados para outro arquivo, precisamos de espaço disponível em disco poder executar essas cópias. No pior dos casos, se os dados não podem ser descartados, precisaremos de 100% do tamanho do banco de dados original disponível como espaço livre, isto é, quando compactar para o mesmo disco, o tamanho do banco de dados original deve ser inferior a 50% da capacidade total do disco. Note que isso realmente é uma situação de pior caso.

Depois disso, quando o banco de dados que resulta do processo de compactação deveria ser armazenado no disco rígido, que contém também o banco de dados original, o desempenho vai sofrer: uma grande quantidade de IO aleatória será necessária para ler o banco de dados original, e por isso as operações de IO para escrever o arquivo de saída, que devem ser sequenciais, de append-only durante a operação normal, vão se tornar aleatórias também (porque são intercaladas com leituras aleatórias).

No geral, mesmo que o mecanismo de compactação completa produza o melhor resultado no final, isso não é algo que você vai querer executar com muita frequência. Por outro lado, a gente quer retornar a sobrecarga de armazenamento para o sistema para que ele possa ser reutilizado para fins mais úteis. Esta operação não deveria ser onerosa, de modo que possa ser executada com mais frequência, e o número de operações de IO necessárias para realizar a operação deve ser tão baixo quanto for possível.

Primeiro, um pouco de intermezzo (você pode pular isso se souber o que é um arquivo ‘sparse’). A maioria dos sistemas de arquivos “modernos”, especialmente (mas não só) no mundo UNIX, possui suporte para arquivos ‘sparse’. Um arquivo sparse é aquele que contém regiões vazias, blocos que parecem ser preenchidos com zeros, mas não são realmente mapeados para os blocos no dispositivo de bloqueio para o sistema de arquivos que grava os dados. Essas regiões vazias podem ser adicionadas ao arquivo quando ele estiver sendo escrito (você pode estender um arquivo com tal espaço vazio), e os dados podem ser escritos para essas regiões vazias depois (nesse momento, os blocos são mapeados para blocos físicos, é claro).

Essas regiões “vazias” são levadas em consideração ao determinar o tamanho do arquivo, mas não ocupam nenhum espaço no dispositivo de disco. Ao ler a partir dessas regiões, tudo que você tem é “zero” byte.

Aqui vai uma demonstração simples, criando um arquivo (2GB) sparse grande que não contém nenhum dado, em seguida, exibindo seu tamanho aparente, bem como o tamanho real em disco:

[nicolas@tau ~]$ dd if=/dev/null of=demo.dat seek=$((2 * 1024 * 1024)) bs=1k
0+0 records in
0+0 records out
0 bytes (0 B) copied, 2.6617e-05 s, 0.0 kB/s
[nicolas@tau ~]$ ls -lh demo.dat
-rw-rw-r--. 1 nicolas nicolas 2.0G Dec 16 16:10 demo.dat
[nicolas@tau ~]$ du --block-size=1 demo.dat
0 demo.dat

Isso mostra que o tamanho do arquivo gerado aparenta ser de 2.0GB, mas ele está, na verdade, armazenado no disco utilizando exatamente 0 bytes (próximo do tamanho do inode/metadados, é claro).

Durante a operação normal, pode-se criar uma região sparse em um arquivo utilizando a chamada de sistema ftruncate(2). Isso só permite anexar uma região vazia para o final de um arquivo, não marcando uma região existente como sendo ‘vazia’.

Felizmente, versões (muito) recentes do kernel do Linux permitem isso em alguns sistemas de arquivos: suporte para a opção FALLOC_FL_PUNCH_HOLE para que a chamada fallocate(2) esteja disponível no ext4, XFS e OCFS2. Usando essa opção, uma região existente em um arquivo pode ser marcada como “vazia”, mesmo que ela contivesse dados antes. O sistema de arquivos irá mudar seus mapeamentos para que a região se torne escassa e zere quaisquer ‘overflow’ bytes no lado extremo esquerdo ou direito da região (uma vez que os blocos só podem ser desmapeados).

Graças a esse recurso, podemos implementar o barato recurso de desalocação por meio de punching holes em um arquivo de banco de dados para cada região que já não tem utilidade. Os blocos estarão disponíveis novamente, e o sistema de arquivos irá lidar com a desfragmentação (se necessário), enquanto todos os offsets codificados nos nodes internos permanecerão válidos.

Agora que conhecemos o mecanismo para liberar os recursos não utilizados, precisamos descobrir quais recursos podem ser liberados, ou seja, calcular onde podemos abrir buracos no arquivo do banco de dados. Inicialmente, pensamos em caminhar pela tree, mantendo o controle do deslocamento e o tamanho de todas as entradas referenciadas como uma lista de pares de números inteiros, então fazer um merge nos pares adjacentes e, finalmente, abrir buracos em todas as áreas do arquivo que não fazem parte desse último mapa.

Esta abordagem possui uma grande desvantagem: um monte de estado está sendo acumulado durante o percurso, o que resulta em uma quantidade alta de uso da memória: o número de entradas necessárias para representar um grande banco de dados pode ser enorme!

Graças a uma observação muito básica, um algoritmo mais simples, eficiente e elegante está disponível! É o seguinte: as entradas são adicionadas ao arquivo de banco de dados usando escritas append-only. Qualquer entrada pode conter ponteiros para outras, codificados como os deslocamentos dessas entradas no arquivo. Uma entrada pode, em todos os momentos, apenas apontar para outras que foram armazenadas antes dela. Como tal, uma entrada só pode apontar para outras na sua esquerda, em deslocamentos menores, uma entrada pode nunca fazer referência à outra na sua direita.

Isso simplifica muito as coisas, e nos permite implementar o seguinte algoritmo recursivo: o estado passado para cada chamada de função consiste em apenas dois valores: um conjunto de deslocamentos (inteiro) S, e um único offset (inteiros) O.

Em cada iteração, o maior inteiro no conjunto S é determinado, e removido do conjunto. Vamos chamar esse valor de C. Esse é o deslocamento da entrada com a qual iremos lidar durante essa iteração. Nós lemos e analisamos a entrada do disco. Se for uma entrada que faz referência a outras (ou seja, uma Leaf ou entrada de Índice), adicionamos os deslocamentos de cada entrada que faz referência ao conjunto S. Repare que esses deslocamentos sempre serão menores do que C (as entradas só podem se referir a outras encontradas anteriormente no arquivo!).

Em seguida, calculamos o tamanho L da entrada com que estamos lidando e o deslocamento do final da entrada no arquivo, E = C + L.

Neste ponto, podemos abrir tranquilamente um buraco de E para O (continue lendo para saber o que O representa).

Agora vamos verificar se S está vazio. Se estiver, não existem mais entradas referenciadas abaixo do offset C. Assim, pode-se abrir um buraco a partir do início do arquivo (ou, no Baardskeerder em formato de disco, após os blocos de metadados) até C.

Caso contrário, se S não estiver vazio, uma chamada recursiva será feita, passando o conjunto atualizado e usando C como um valor de O.

Finalmente, precisamos iniciar a operação. Veja como: em primeiro lugar, localize a entrada commit da versão mais antiga do banco de dados que você quer manter (lembre-se, Baardskeerder é uma estrutura de dados funcional/persistente!). Todas as versões mais antigas (com entradas de commit em deslocamentos inferiores) se tornarão inválidas por causa do processo de compactação. Agora, o processo recursivo pode ser iniciado utilizando o conjunto simples contendo o deslocamento da entrada raiz para o qual a entrada commit aponte como S e o deslocamento da entrada commit como valor de O.

Observe que definir S, ao contrário da lista na abordagem inicial, nunca será muito grande: vai, sempre, conter apenas o deslocamento de todas as entradas conhecidas à esquerda da qual estamos lidando, ela nunca vai conter os deslocamentos e todas as entradas do banco de dados.

Aqui está uma implementação Haskell do algoritmo. Acho que pode esclarecer algumas coisas:

import Prelude hiding (null)
import Data.ByteString (ByteString)
import Data.Int (Int32)
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS
import System.Posix (COff, Fd)

type Key = ByteString
type Value = ByteString

type Offset = COff
type Length = Int32

data Entry = Commit Offset Length Offset
           | Leaf Offset Length Value
           | Node Offset Length [(Key, Offset)]

getEntry :: Fd -> Offset -> IO Entry
getEntry f o = undefined

punch :: Fd -> Offset -> Length -> IO ()
punch f o l = undefined

data CompactState = CS Offset IntSet

fileStart :: Offset
fileStart = 4096

compact :: Fd -> Offset -> IO ()
compact f o = do
    c <- getEntry f o
    case c of
        Commit _ _ r -> compact' f $ CS o (IS.singleton $ fromIntegral r)
        otherwise -> error "compact: not a commit entry"

compact' :: Fd -> CompactState -> IO ()
compact' f (CS n os) = do
    -- At this stage, s should never be empty
    let (h, os') = IS.deleteFindMax os
        h' = fromIntegral h

    e <- getEntry f h'

    let (e', os'') = case e of
            Leaf o l _ -> (o + fromIntegral l, os')
            Node o l rs ->
                (o + fromIntegral l,
                    foldr (IS.insert . fromIntegral) os' $ map snd rs)
            otherwise -> error "compact': invalid entry type"

    punch f e' $ fromIntegral (n - e')

    if (IS.null os'')
    then punch f fileStart $ fromIntegral (h' - fileStart)
    else compact' f (CS h' os'')

Para concluir, farei algumas observações relacionadas ao “mundo real de engenharia de software”:

• Uma vez que apenas blocos só podem ser desmapeados, as chamadas para “punch” devem estar alinhadas em bloco, caso contrário, o overflow é preenchido com zeros, o que resulta em operações de escrita aleatórias completamente inúteis e desnecessárias.
• Alguém pode querer usar um limiar para perfurar somente se o buraco for grande o suficiente (por exemplo, pelo menos 10 blocos consecutivos): a criação de muitos buracos pequenos pode apresentar uma fragmentação indesejada (isso depende do padrão de uso do banco de dados).
• É possível ser “inteligente” e só abrir buracos em regiões que ainda estão apoiadas por blocos físicos (o algoritmo não leva, e não deve levar, todos os buracos existentes em conta!). Há duas maneiras de solicitar informações sobre os buracos existentes para o sistema de arquivos: usando ioctl(2) com a opção FS_IOC_FIEMAP, se o sistema de arquivo suporta isso, ou usando lseek(2) com SEEK_HOLE e SEEK_DATA (que também requer suporte do sistema de arquivos para trabalhar corretamente). Nenhum teste foi realizado para verificar se isso fornece quaisquer benefícios ainda.

***

Texto original disponível em http://blog.incubaid.com/2011/12/19/hole-punching-compaction-of-an-append-only-database/