O^3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading

O artigo apresenta o O³-LSM, uma nova arquitetura de armazenamento de chaves-valor baseada em LSM que maximiza o desempenho de escrita em ambientes de armazenamento desagregado ao implementar um offloading de três camadas (memtable, flush e compactação) utilizando memória desagregada compartilhada, resultando em ganhos significativos de throughput e redução de latência em comparação com soluções existentes.

O essencial

Imagine que você tem uma biblioteca gigante (o seu banco de dados) que precisa ser acessada por milhares de pessoas ao mesmo tempo. No mundo da computação moderna, essa biblioteca está separada em duas partes: os escritórios (onde as pessoas trabalham e processam informações) e o armazém (onde os livros são guardados permanentemente).

O problema é que os escritórios têm pouco espaço para guardar os livros que estão sendo usados agora (a memória), e o armazém é muito longe e lento para buscar coisas. Quando o escritório enche, ele precisa parar tudo para enviar os livros para o armazém, o que causa gargalos e lentidão.

O artigo O3-LSM propõe uma solução inteligente para esse problema, criando um "sistema de três camadas" para tornar essa biblioteca super rápida. Vamos entender como funciona usando analogias do dia a dia:

1. O Problema: O Escritório Está Estourado

Nas bibliotecas atuais (chamadas de LSM-KVS), quando os funcionários (computadores) recebem muitos pedidos novos, eles anotam tudo em um bloco de notas rápido (memória). Quando o bloco enche, eles têm que parar de escrever, organizar os papéis e correr até o armazém distante para guardar.

• O gargalo: O bloco de notas é pequeno. Se encher, o trabalho para. Além disso, a corrida até o armazém é lenta e cansativa.

2. A Solução: O "Armário Intermediário" Inteligente

O O3-LSM descobre que existe um armário intermediário (Memória Desagregada) que fica entre o escritório e o armazém. Ele é rápido, mas não é o escritório. O desafio é que, se você apenas jogar os papéis lá, eles ficam bagunçados e difíceis de achar depois.

O O3-LSM resolve isso com 3 truques principais:

Truque 1: O Bloco de Notas "Pronto para Uso" (Memtable Otimizada)

• O problema antigo: Se você pegar um bloco de notas cheio de anotações com "setas" (ponteiros) que apontam para lugares específicos na mesa do escritório e jogar no armário intermediário, as setas quebram. Para usar lá, você teria que reescrever todo o bloco do zero, o que demora muito.
• A solução O3-LSM: Eles redesenham o bloco de notas. Em vez de usar setas complexas, eles organizam as anotações em uma lista contínua e organizada (como uma fila de pessoas em pé, uma atrás da outra).
• A analogia: É como se, em vez de passar um mapa cheio de setas para o armário, você apenas empilhasse os papéis em uma caixa organizada. Quando chega no armário, eles já estão prontos para serem lidos, sem precisar de reorganização. Isso torna o transporte super rápido.

Truque 2: A Equipe de Entrega Colaborativa (Flush Offloading)

• O problema antigo: Quando o bloco de notas enche, o funcionário original tem que parar seu trabalho, pegar o bloco, correr até o armazém, organizar, empacotar e guardar. Isso deixa o funcionário parado e sobrecarrega a porta do escritório.
• A solução O3-LSM: Eles criam um gerente de entregas (um agendador). Quando um bloco de notas está pronto para ir ao armazém, o gerente olha ao redor: "Quem está livre? Quem tem mais energia?". Ele pode enviar o bloco para qualquer outro funcionário ou até para o próprio armário intermediário para ser organizado e enviado.
• A analogia: Imagine que, em vez de você ter que parar e ir ao correio, um motoboy passa, pega seu pacote, e um funcionário da loja de conveniência (que está livre) já organiza o pacote e manda para o correio. Você continua trabalhando, e o pacote sai mais rápido porque foi distribuído entre várias pessoas.

Truque 3: Dividir para Conquistar (Shard-Level Optimization)

• O problema antigo: Enviar um bloco de notas gigante de uma vez só causa um "engarrafamento" na estrada (rede). Além disso, quando chegam no armazém, muitos blocos se misturam e ficam confusos.
• A solução O3-LSM: Eles cortam o bloco de notas em pedaços menores baseados no assunto (ex: tudo sobre "Animais" vai para um pacote, "Veículos" para outro).
• A analogia: Em vez de tentar carregar um caminhão inteiro de uma vez e causar um engarrafamento, você usa 10 motos pequenas que vão por caminhos diferentes ao mesmo tempo. No armazém, como os pacotes já estão separados por assunto, é muito mais fácil organizá-los sem bagunça.

3. O Toque Final: O "Guia Rápido" (Cache de Leitura)

Às vezes, você precisa ler um livro que está no armário intermediário. Procurar em uma lista gigante é lento.

• A solução: O O3-LSM cria um pequeno caderno de endereços no escritório. Se você já pediu um livro antes, o caderno diz exatamente onde ele está no armário. Se não estiver no caderno, o sistema manda um "mensageiro" (um funcionário do armário) procurar por você, em vez de você ter que correr até lá e procurar página por página.

O Resultado?

Com essas melhorias, o sistema O3-LSM consegue:

• Escrever 4,5 vezes mais rápido do que os sistemas atuais.
• Fazer buscas 5 vezes mais rápidas em intervalos de dados.
• Reduzir o tempo de espera (latência) em até 76%.

Resumo da Ópera:
O O3-LSM transforma o processo de guardar e buscar dados em uma operação de "logística inteligente". Em vez de um funcionário sobrecarregado correndo sozinho, eles usam um armário intermediário organizado, uma equipe de motoboys colaborativa e caminhos separados para garantir que a biblioteca nunca pare, não importa o quanto de gente tente acessar ao mesmo tempo.

Resumo técnico

Resumo Técnico: O3-LSM

1. O Problema

Os sistemas de armazenamento de chave-valor baseados em árvores Log-Structured Merge (LSM-KVS), como o RocksDB, são otimizados para escritas de alta velocidade. No entanto, em Data Centers Desagregados (DDCs), onde computação, memória e armazenamento são separados em pools de recursos independentes, surgem gargalos críticos:

• Memória Limitada nos Nós de Computação (CN): Os nós de computação frequentemente hospedam múltiplas instâncias de LSM-KVS, limitando a memória disponível para buffers de escrita (memtables). Quando o buffer local enche, as escritas são bloqueadas (stalls) até que os dados sejam despejados (flushed).
• Desempenho de Flush Lento: O processo de despejar dados da memória local para o Armazenamento Desagregado (DS) é lento devido à latência de rede e à contenção de I/O.
• Limitações das Soluções Atuais: Soluções existentes que apenas descarregam a compaction (consolidação de arquivos) para o DS não resolvem o problema do buffer de escrita limitado.
• Desafios ao Usar Memória Desagregada (DM): Embora a Memória Desagregada (DM) ofereça uma extensão de memória de baixa latência, uma abordagem ingênua de mover memtables inteiras para a DM falha devido a:
  1. Custo de Transferência e Reconstrução: Estruturas de dados baseadas em ponteiros (como skip-lists) tornam-se inválidas ao serem copiadas para a DM, exigindo reconstrução cara.
  2. Ineficiência no Flush: A DM não possui a lógica para criar arquivos SST (Sorted String Tables) diretamente; os dados precisariam ser trazidos de volta ao CN para flush, adicionando um salto de rede desnecessário.
  3. Busca Lenta: Procurar chaves em memtables remotas via RDMA é significativamente mais lento do que localmente devido às múltiplas idas e vindas de rede (round-trips).

2. Metodologia: Arquitetura O3-LSM

O O3-LSM propõe uma nova arquitetura de três camadas de descarregamento (offloading) para maximizar o desempenho de escrita, utilizando a Memória Desagregada (DM) como um buffer intermediário inteligente. As inovações principais são:

A. Memtable Otimizada para DM (DM-Optimized Memtable)

• Separação de Dados e Índices: Em vez de transferir uma estrutura de ponteiros complexa, o O3-LSM separa a memtable em dois blocos contíguos:
  • Index-Block: Contém apenas os ponteiros (que são recalculados na DM) e metadados.
  • KV-Block: Contém os pares Chave-Valor em um formato contíguo e serializado, sem ponteiros.
• Transferência Barata: O KV-Block pode ser transferido diretamente para a DM via RDMA sem necessidade de reconstrução de ponteiros. Apenas o Index-Block precisa de um ajuste simples de endereçamento na DM.

B. Flush Colaborativo (Collaborative Flush Offloading)

• Desacoplamento do Controle: O processo de flush é separado da instância LSM-KVS original.
• Agendamento Inteligente: Um scheduler centralizado monitora a carga de CPU e I/O de todos os nós (CNs e nós de DM).
• Execução Remota: Quando uma memtable na DM precisa ser despejada, o scheduler atribui a tarefa a qualquer nó disponível (um CN ocioso ou o próprio nó de DM) para executar a criação do arquivo SST e a escrita no DS. Isso evita trazer os dados de volta ao CN original, eliminando o custo de leitura de volta e permitindo paralelismo massivo.

C. Otimização por Nível de Shard (Shard-Level Optimization)

• Particionamento: Cada memtable é dividida em vários shards (fragmentos) baseados em intervalos de chaves disjuntos.
• Transferência Assíncrona: Os shards podem ser transferidos para a DM de forma assíncrona e paralela, sem esperar que a memtable inteira seja preenchida.
• Compaction Integrada ao Flush: Ao invés de despejar memtables inteiras, o sistema agrupa shards do mesmo intervalo de chave de várias memtables diferentes e os despeja juntos. Isso gera arquivos SST na camada L0 com menos sobreposição de chaves, reduzindo drasticamente a necessidade de compaction serializada e lenta na camada L0.

D. Delegação de Leitura Aprimorada por Cache (Cache-Enhanced Read Delegation)

• Cache Local de Offset: Mantém um pequeno cache no CN mapeando chaves "quentes" para seus offsets na DM. Se houver um hit, a leitura é feita diretamente via RDMA de um lado (one-sided).
• Delegação de Leitura: Se houver um miss, o sistema delega a busca para um nó de DM, que executa a busca localmente e retorna o resultado. Isso reduz o número de viagens de rede (round-trips) necessárias para percorrer a estrutura de índice remota.

3. Principais Contribuições

1. Arquitetura de Três Camadas: É a primeira solução a integrar offloading de memtable, flush e compaction em um sistema LSM-KVS desagregado.
2. Projeto de Estrutura de Dados para DM: A separação entre bloco de dados e bloco de índice permite transferência eficiente sem reconstrução de ponteiros.
3. Protocolo de Flush Colaborativo: Permite que qualquer nó na rede execute o flush, transformando a DM em um recurso de computação ativo, não apenas de armazenamento.
4. Paralelismo Fino: A abordagem baseada em shards quebra o gargalo serial da compaction L0, permitindo operações massivamente paralelas.

4. Resultados Experimentais

O O3-LSM foi implementado sobre o RocksDB v8.2.0 e avaliado no CloudLab contra estados da arte (Disaggregated-RocksDB, CaaS-LSM, Nova-LSM).

• Desempenho de Escrita: Melhoria de até 4.5x na taxa de transferência (throughput) de escritas aleatórias em comparação com as soluções existentes.
• Latência: Redução de até 76% na latência P99 em cargas de trabalho mistas.
• Leitura e Consulta de Intervalo:
  • Aumento de 1.8x no throughput de leitura pontual.
  • Aumento de 5.2x no throughput de consultas de intervalo (range queries), devido à redução de arquivos L0 sobrepostos.
• Aplicação Real: Em testes com o Kvrocks (um sistema compatível com Redis), o O3-LSM mostrou ganhos de até 3.4x em throughput e redução de 54% na latência P99.
• Estabilidade: O sistema demonstrou maior estabilidade e menos stalls de escrita, especialmente sob picos de carga, graças ao uso de um pool de memória compartilhado dinâmico.

5. Significado e Impacto

O O3-LSM representa um avanço fundamental na otimização de bancos de dados para a arquitetura de Data Centers Desagregados. Ao tratar a Memória Desagregada não apenas como um armazenamento passivo, mas como uma extensão ativa e gerenciável do buffer de escrita, o sistema resolve o dilema clássico de "memória limitada vs. desempenho de escrita".

A solução demonstra que é possível escalar o desempenho de sistemas LSM-KVS em ambientes de nuvem moderna, onde a elasticidade de recursos é priorizada, sem sacrificar a durabilidade ou a consistência. As técnicas propostas, especialmente o flush colaborativo e a otimização por shards, oferecem um roteiro para futuros sistemas de armazenamento que precisam lidar com volumes massivos de dados e alta concorrência em infraestruturas desacopladas.