o problema
A B-tree foi desenhada para uma máquina que não existe mais: um disco lento e um processador que ficava mais rápido sozinho a cada geração. Nessa máquina, o latch de página é barato — há poucas threads competindo — e atualizar a página no lugar é o óbvio, porque o gargalo está no I/O e não na memória. Os dois pressupostos caíram. Com muitos núcleos, o latch passa a bloquear, e bloquear é justamente o que limita a escalabilidade. Com caches grandes por núcleo, escrever no meio de uma página invalida linhas de cache em todos os outros núcleos que tinham aquela página: um insert numa página ordenada move, em média, metade dos elementos.
O segundo problema é o armazenamento. Flash resolve o número de operações de I/O por segundo que o disco não entrega, mas tem sua própria assimetria: leitura aleatória é rápida, escrita aleatória não, porque precisa de um ciclo de erase antes. O paper cita que em 2011 mesmo drives FusionIO topo de linha escreviam sequencialmente 3 vezes mais rápido que aleatoriamente. A FTL do SSD esconde parte disso, mas não toda.
a ideia
Entre a árvore e a memória entra uma tabela de mapeamento. Cada nó tem um PID, e todos os links da árvore — ponteiros de descida e side links — são PIDs, não endereços. A tabela traduz o PID para um ponteiro de memória ou para um offset no flash. O efeito é que a página perde tanto o endereço fixo quanto o tamanho fixo: ela pode mudar de lugar a cada atualização e a cada flush sem que ninguém acima precise saber.
Com isso, atualizar vira outra coisa. Em vez de mexer na página, cria-se um delta record descrevendo a mudança, aponta-se esse delta para o estado atual da página e faz-se um CAS no slot da tabela. Se o CAS passa, o delta é o novo estado. Um único CAS instala qualquer coisa: um insert, um split, um flush. E o estado anterior continua lá, byte por byte, válido para quem já estava lendo.
como funciona
Uma página é uma base page com uma cadeia de deltas na frente. No nível folha os deltas são insert, modify ou delete, cada um carregando o LSN fornecido pelo cliente. A busca percorre a cadeia e para na primeira ocorrência da chave; se não achar, faz busca binária na base page como qualquer B-tree. Quando a cadeia passa de um limiar, a própria thread que percebeu consolida: monta uma nova base page com o estado mais recente de cada registro, instala com CAS e manda o estado antigo para coleta. A recuperação de memória usa epochs — um objeto liberado na epoch E só é reciclado quando todas as threads inscritas em E saíram.
Split usa a estrutura B-link e acontece em duas metades atômicas. Primeiro aloca-se Q, monta-se sua base com os registros de P acima da chave separadora KP e prepende-se em P um split delta com KP e o side pointer para Q. Nesse ponto a árvore já está correta: buscas por chaves maiores que KP chegam em P, veem o split delta e atravessam o side link. A segunda metade prepende no pai um index entry delta com KP, o ponteiro para Q e KQ. Merge é pior: remove node delta em R, merge delta em L apontando fisicamente para o conteúdo de R (o que transforma a cadeia linear numa árvore) e index term delete delta no pai. O PID de R só volta ao pool depois que a epoch drena.
Como não há latch, uma thread pode encontrar uma SMO pela metade — o equivalente a ver estado não commitado. A regra é que ela termina a SMO alheia antes de fazer o que veio fazer. Ninguém espera; a SMO interrompida serializa antes da operação que a encontrou.
Na camada de cache, um flush delta registra o que já foi para o log estruturado. O flush seguinte marshalla só os deltas com LSN entre o último flushado e o ESL, o ponto até onde o log transacional está estável. Por isso o WAL nunca bloqueia um flush: dá para excluir as atualizações recentes porque elas estão separadas. O flush buffer agrega escritas até 1MB e alterna dois buffers com I/O assíncrono.
o que isso custou
A conta é paga na leitura. Uma página vive espalhada em pedaços descontínuos no flash, e trazê-la de volta exige ler todos eles — o desenho depende inteiramente da leitura aleatória rápida do flash. O limiar da cadeia de deltas é um parâmetro sensível ao tamanho do registro: com os registros grandes do Xbox a busca degrada acima de quatro deltas; com chaves de 8 bytes, oito deltas não doem.
Latch-free não elimina a disputa. As operações caras perdem para as baratas: no workload sintético, 8,88% dos splits e 7,35% das consolidações falharam o CAS, contra 0,0003% dos updates. O Bw-tree também não faz controle de concorrência — ele assume que alguém acima (um lock manager, um componente transacional) impede updates conflitantes.
E o paper mede menos do que descreve. A avaliação é toda em memória; o comportamento em armazenamento secundário fica para trabalho futuro, e o log estruturado é descrito em alto nível, com os detalhes prometidos para outro paper. Os autores admitem ainda que o Bw-tree explora a liberdade de reter atualizações até ser conveniente escrevê-las, o que exige cuidado ao comparar com stores que tornam cada update durável na hora. Não houve otimização de busca sensível a cache dentro da página, nem exploração do paralelismo interno do SSD.
onde isso aparece hoje
Os números que sustentam o argumento: 10,4M operações por segundo contra 555K do BerkeleyDB no workload do Xbox (18,7x), 8,6x na deduplicação, 5,8x no sintético, com 99% de utilização de processador contra 60%. Contra uma skip list latch-free, 3,7x no sintético e 4,4x num workload só de leitura — quase 90% dos acessos de memória do Bw-tree vindo de L1 ou L2, contra 75% da skip list, porque os nós internos são 1% da memória ocupada e os da skip list, metade.
A comparação com a skip list é a que envelheceu melhor como pergunta: ela era a estrutura ordenada latch-free padrão em bancos memory-optimized, e o Bw-tree mostrou que a vantagem dela era de implementação, não de princípio. O log estruturado com flush incremental está na mesma linhagem da LSM-tree: trocar escrita por leitura e pagar depois na compactação ou no cleaner. O trade-off que o desenho faz — mais memória e mais custo de leitura em troca de escrita e concorrência — é exatamente o triângulo que a conjectura RUM nomearia três anos depois. E o cuidado com ESL e LSN por delta é o protocolo WAL do ARIES sobrevivendo num mundo sem latch, com a diferença de que aqui o flush nunca precisa esperar.