o problema
Em 1995, uma aplicação TPC-A a 1.000 transações por segundo gravava uma linha de 50 bytes numa tabela History a cada transação. Para responder “o que aconteceu nesta conta depois de tal data” sem varrer a tabela inteira, era preciso um índice por Acct-ID||Timestamp. Vinte dias de acúmulo dão 576.000.000 entradas de 16 bytes: 9,2 GBytes, cerca de 2,3 milhões de páginas de 4 KBytes mesmo sem desperdício de espaço.
O Acct-ID de cada transação é sorteado entre 100.000.000 de valores, então cada insert cai numa página aleatória dessas 2,3 milhões. Pela regra dos cinco minutos, cada página volta a ser tocada só a cada 2.300 segundos — longe demais para justificar mantê-la em buffer. Sobra o pior caso: uma leitura e uma escrita por insert, 2.000 I/O aleatórios por segundo, mais 50 braços de disco. O índice dobrava o custo de disco da aplicação. E o problema não é da B-tree. Os autores definem Continuum Structure como qualquer método que coloca a entrada nova já na sua posição de colação final; hashing extensível, SB-tree e Bounded Disorder são todas Continuum Structures, e todas pagam os mesmos dois I/O.
a ideia
Parar de colocar a entrada onde ela pertence e deixar que ela chegue lá depois, junto com milhares de vizinhas. O LSM-tree tem um componente C0 pequeno em memória e um C1 grande em disco. O insert vai só para C0, sem I/O nenhum. Quando C0 encosta no seu limite de tamanho, um processo contínuo — o rolling merge — vai drenando faixas de C0 para dentro de C1, lendo e escrevendo C1 em blocos grandes e sequenciais. É merge sort transformado em regime permanente: nada é colocado, tudo é fundido. O nome vem do Log-Structured File System de Rosenblum e Ousterhout, que inspirou a escrita sempre em posição nova.
como funciona
C0 não precisa ter nós do tamanho de página, porque nunca vai para o disco: uma AVL ou uma (2-3) serve. C1 tem diretório parecido com B-tree, mas com nós 100% cheios e sequências de nós empacotadas em blocos multipágina de 256 KBytes. Find exato desce por nós de página única, para não puxar bloco inteiro; merge e range scan usam o bloco inteiro.
O rolling merge é um cursor que circula pelas faixas de chave. Em cada nível ele mantém dois blocos em buffer: o emptying block, com o que ainda não foi alcançado, e o filling block, com o resultado já fundido. Quando o filling block enche, ele é escrito numa área livre nova do disco — os nós antigos só são invalidados depois, o que é o que torna a recuperação possível. Chegando ao fim das chaves, o cursor recomeça do começo. Aqui há uma vantagem sobre o LFS: no LSM-tree os blocos velhos ficam totalmente livres na borda de trás do merge, então reaproveitá-los não custa I/O.
A conta que sustenta o resto do paper: o insert numa B-tree custa COSTP·(De+1); no LSM-tree custa 2·COSTπ/M, amortizado. A razão dá K1·(COSTπ/COSTP)·(1/M), com K1 ≈ 0,67. COSTπ/COSTP vale cerca de 1/10 nos discos medidos. M é quantas entradas de C0 entram em cada nó folha de C1 por viagem, e depende da razão de tamanho entre os componentes. Se C1 é grande demais em relação a C0, M cai abaixo de 1 e o esquema perde para uma B-tree comum. Manter M alto exigiria memória cara — e é daí que sai o componente intermediário. O Teorema 3.1 mostra que, com C0 e o maior componente fixos, o I/O total de merge é mínimo quando todas as razões entre componentes vizinhos são iguais.
Recuperação não precisa de log próprio: os logs transacionais de insert das linhas bastam para reconstruir as entradas de índice. O checkpoint grava C0, os nós sujos, o LSN da última linha indexada, os endereços das raízes, a posição de cada cursor de merge e o estado da alocação de blocos.
o que isso custou
Leitura. Um find imediato tem que consultar cada componente, e nos casos em que o valor está no maior deles isso é um I/O a mais por componente intermediário. Os autores são explícitos: o LSM-tree serve onde insert é bem mais frequente que find, como History e log. Nos exemplos, para igualar a velocidade de find de uma B-tree, é preciso comprar de volta parte da memória economizada.
A economia também tem piso: se o índice já cabia com folga na capacidade dos discos que ele exige, reduzir I/O não reduz mais nada. E o ganho depende de uma garantia dura — C0 tem que ser realmente residente em memória. Os autores atribuem a fraqueza da TSB-tree, da MD/OD R-tree e do Differential File exatamente a não terem essa garantia.
Sobrou trabalho declarado. A concorrência exige travar até quatro nós ao mesmo tempo e lidar com um cursor rápido ultrapassando um lento, o que invalida a posição do cursor ultrapassado; os autores deixam o algoritmo dos níveis altos de diretório e a prova de correção “para trabalho posterior, depois que uma implementação der mais experiência”. O paper é uma análise de custo, não um relato de sistema rodando. A análise de dimensionamento é só de insert; balancear find no modelo aparece na lista de pesquisa futura.
onde isso aparece hoje
A estrutura virou o padrão de fato dos key-value stores modernos: componente em memória, arquivos ordenados em disco, merge em background — memtable, SSTable e compaction são os nomes que o Bigtable e o Cassandra deram às mesmas peças. O RocksDB é um LSM-tree, e com ele o MyRocks e o relato de prioridades de desenvolvimento do time; o SILK ataca justamente o efeito colateral que este paper não mediu, o merge competindo com o tráfego de frente e produzindo picos de latência.
Duas ideias vizinhas ficaram permanentes. O filtro de Bloom, que aqui aparece só de passagem na discussão do Differential File, é hoje o jeito padrão de evitar consultar todos os componentes num find. E a troca central — pagar leitura para baratear escrita — é uma das arestas da conjectura RUM.