TreeSLS: um microkernel persistente de sistema inteiro com checkpoint de estado em árvore sobre NVM

Os sistemas operacionais convencionais rodam em DRAM volátil e persistem dados por meio de arquivos, então as aplicações ficam movendo dados entre uma camada de memória e uma camada de armazenamento. Os autores apontam bugs de consistência após falhas (crash consistency) em sistemas de arquivos e em aplicações construídas sobre eles, e o custo de trocar dados entre as camadas. Um single-level store (SLS) tira esse peso das aplicações: elas rodam em um único nível de memória enquanto o sistema tira checkpoints de tudo de forma transparente, o que também dá recuperação quase instantânea. SLSs anteriores, como o EROS e o Aurora, ainda ficam sobre DRAM mais disco, e os autores nomeiam dois problemas: o checkpointing é caro (write amplification, e uma frequência de checkpoint limitada por armazenamento lento), e a sincronia externa é difícil, isto é, um estado que já foi mostrado ao mundo exterior precisa estar persistente. Os SLSs existentes respondem ao segundo problema com APIs de journaling, o que devolve código de persistência às aplicações.

Este artigo do SOSP 2023 (Koblenz), do Institute of Parallel and Distributed Systems da Shanghai Jiao Tong University e do Engineering Research Center for Domain-specific Operating Systems do Ministério da Educação da China, propõe o TreeSLS. A observação é que um microkernel mantém seu estado em objetos do kernel referenciados por capabilities, então o estado do sistema inteiro forma uma única árvore, fácil de capturar em checkpoint, e que a NVM endereçável por byte permite que a mesma memória sirva de runtime e de armazenamento.

Cinco termos merecem atenção. A árvore de capabilities agrupa todos os objetos do kernel, e cada processo é uma subárvore. Um PMO (physical memory object) é um conjunto de páginas físicas. Uma pausa stop-the-world (STW) é o tempo em que todos os cores ficam parados para tirar um checkpoint. Sincronia externa (external synchrony) significa que uma resposta só é liberada depois que o estado por trás dela está persistente. O eADR é o recurso da Intel que descarrega os caches da CPU para a NVM em uma falha de energia, enquanto os registradores da CPU e dos dispositivos ainda se perdem.

Vale conhecer antes: memória virtual, page faults e copy-on-write, capabilities em microkernels e write-ahead logging, que a avaliação usa como base de comparação. O artigo cita o seL4 como microkernel de capabilities, e o Atmosphere é um microkernel posterior que também mantém drivers e pilhas de rede no userspace. Dois pareamentos meus, não do artigo: o Snap também tira o networking do kernel, e o μFork observa que os snapshots do Redis dependem do fork, enquanto o TreeSLS persiste o Redis sem nenhum código na aplicação.

• A árvore de capabilities é o estado inteiro. Os objetos do kernel são Cap Group, Thread, VM Space, PMO, conexão IPC, Notification e IRQ notification, todos alcançáveis a partir de um Cap Group raiz. Estado derivado, como as filas do scheduler, é reconstruído na recuperação, e as tabelas de páginas, que ficam na DRAM, são reconstruídas sob demanda por page faults. Cada objeto tem um registro ORoot que aponta para suas cópias de runtime e de backup, então um objeto compartilhado entra em checkpoint uma vez só e objetos intocados são pulados, o que torna os checkpoints incrementais.
• Um gerenciador de checkpoint resiliente a falhas. Um módulo dentro do kernel é dono do alocador de NVM (um buddy system mais slabs, com metadados na NVM). O estado do próprio módulo não entra em checkpoint, já que isso seria circular. Um journaling redo/undo o protege, e no reboot o journal é aplicado primeiro e o sistema é restaurado depois.
• O procedimento de checkpoint. Um core líder envia IPIs para quiescer os outros, copia a árvore de capabilities para uma árvore de backup sem copiar as páginas de usuário (elas são marcadas como somente leitura), enquanto os demais cores copiam páginas de forma especulativa. Um número de versão global é então incrementado atomicamente como ponto de commit, e os cores retomam. Uma escrita posterior gera um fault e copia a página para o backup.
• Versionamento que usa a página de runtime como backup. Como as páginas de runtime já estão na NVM, uma página de PMO precisa de no máximo uma página de backup extra, e os outros objetos mantêm dois backups ao lado da cópia de runtime. Na recuperação, usa-se o backup cuja versão é igual à versão global, e uma página com backup mais antigo ou sem backup é tomada da página de runtime.
• Hybrid copy. Os autores comparam stop-and-copy, stop-and-copy especulativo, copy-on-write e copy-on-write especulativo. O híbrido deles conta a hotness nos page faults, mantém as páginas quentes em uma dual-function active page list, migra essas páginas para a DRAM e as copia com stop-and-copy nos cores que de outro modo ficariam ociosos durante a pausa. As páginas frias ficam na NVM com copy-on-write. A migração exige um segundo backup por página, com regras de recuperação próprias.
• Visibilidade externa atrasada. Drivers em userspace registram um callback de checkpoint e um callback de restauração, e guardam seus ring buffers em um eternal PMO, que nunca sofre rollback. Uma mensagem adicionada à fila de envio só se torna visível ao dispositivo quando um checkpoint avança um ponteiro de escrita visível. As aplicações não mudam, os drivers sim.
• Tamanho. O TreeSLS é construído sobre o ChCore, um microkernel multicore educacional com suporte a POSIX via musl-libc e cerca de 21 mil linhas no kernel. Ele acrescenta cerca de 5 mil linhas ao kernel (cerca de 3,3 mil para checkpoint/restore, cerca de 1,2 mil no alocador) e cerca de 500 linhas ao servidor de rede em userspace.

Todos os experimentos rodam em uma máquina com duas CPUs Intel Xeon Gold 6330 com eADR, fixadas em 2,0 GHz, com hyperthreading ligado e turbo desligado. O TreeSLS usa um nó NUMA, com 256 GiB de DDR4 e 1 TiB de Intel Optane Persistent Memory. As cargas são a suíte Phoenix 2.0 (WordCount, KMeans, PCA), Redis 6.0.8, Memcached 1.6.21, LevelDB, RocksDB 6.6 e SQLite, comparadas com o Linux 5.4 e o Aurora. Os testes funcionais derrubam e reiniciam a máquina à mão enquanto rodam hello world, ping-pong, key-value stores simples e as aplicações reais.

O tempo de pausa é medido a 1000 Hz, com decomposições por carga e por tipo de objeto. O overhead em runtime é medido acrescentando um mecanismo de cada vez (checkpoint, page fault, cópia de página, hybrid copy), variando o intervalo de checkpoint no Memcached e com um teste de sincronia externa com 50 clientes do Redis. O Redis roda sob o YCSB contra o Linux com seu próprio log (Ext4-DAX no Optane, com o Redis compilado com musl-libc por justiça). O RocksDB roda a carga Prefix_dist do Facebook contra o Aurora, que os autores configuram com DRAM como armazenamento e intervalo de checkpoint de 5 ms. Os testes de aplicação rodam com a sincronia externa desligada.

Estes são os resultados relatados pelos autores.

• Tempo de pausa. Sem carga, o checkpoint STW leva cerca de 25 μs. SQLite e LevelDB são parecidos, e aplicações multi-threaded mais complexas terminam em torno de 100 μs. Fazer o checkpoint incremental de um único objeto leva no máximo 3,28 μs. As primeiras rodadas são checkpoints completos e custam mais, até cerca de 4 ms para os PMOs de um arquivo de dados de 100 MiB do Phoenix.
• Hybrid copy. A pausa em si soma um overhead marginal, e a maior parte vem dos page faults e da cópia de páginas. O hybrid copy remove até 49% do overhead. No Memcached, 395 páginas ficam em cache como quentes, 40% delas são modificadas entre checkpoints, e 46% das 338 páginas modificadas são copiadas de forma especulativa enquanto as outras 182 geram fault. A fatia de page faults eliminados é 89% no Redis, 95% no KMeans e 11% no PCA.
• Frequência de checkpoint. No Memcached com 10 milhões de chaves, a latência cresce conforme o intervalo diminui abaixo de 10 ms, e um intervalo de 1 ms soma de 11 a 160 μs.
• Sincronia externa. No teste de SET do Redis, atrasar as respostas aumenta a latência em cerca de um intervalo de checkpoint, e o throughput ainda sofre porque clientes bloqueados ficam no caminho crítico.
• Redis contra seu próprio log. Em cargas YCSB pesadas em escrita (100% update, 100% insert), o TreeSLS a 1 ms perde de 18% a 21% do throughput da sua própria base, o Linux com seu log perde de 64% a 78%, e o throughput absoluto do TreeSLS é de 1,9× a 2,2× o do Linux com seu log. Na carga A ele fica 28% à frente. Nas cargas pesadas em leitura B e C ele fica atrás do Linux com seu log, que não registra nada nas leituras. O texto informa degradação de 30% e 15% sem dizer qual é a referência.
• RocksDB. Contra a própria base, o TreeSLS a 1 ms perde 10% de throughput e soma 22% (P50) e 69% (P99) de latência de escrita, e a 5 ms os números são 2%, 6% e 32%. O Aurora a 5 ms perde 9% e soma 43% (P50) e 4,2× (P99). Os autores também relatam 2,4× e 2,5× o throughput da API de journaling do Aurora e do log do RocksDB. Eles dizem que o Aurora leva de 5 a 7 ms para persistir um checkpoint mesmo com DRAM como armazenamento, e cerca de 100 ms com um SSD.
• Testes funcionais. Todos os programas retomaram com o comportamento esperado depois de quedas manuais.

O artigo é aberto sobre vários limites. Ele admite o seguinte.

• Persistência uniforme. Aplicações e dados diferem no que precisam persistir, e persistir tudo pode guardar dados desnecessários.
• Confiabilidade e capacidade da NVM. Corrupção ou falha da NVM quebra o TreeSLS. Várias versões de checkpoint, replicação e erasure coding são propostos, não construídos. O over-commitment de memória não é tratado, e uma lista de páginas frias fica como esboço.
• A sincronia externa é parcial. Ela é implementada em um servidor de rede para a comunicação entre clientes e servidores na mesma máquina, com drivers de rede reais ainda em andamento. Os drivers precisam ser alterados para usar a API do TreeSLS, e atrasar a saída em até um intervalo de checkpoint só funciona se os checkpoints forem frequentes.

Os pontos a seguir são uma leitura das evidências, não afirmações do artigo.

• As comparações de destaque usam garantias diferentes. Os testes de aplicação rodam sem sincronia externa, então o 1 ms de latência adicional é declarado, não medido ali, e escritas confirmadas ainda podem se perder dentro do último intervalo. O log do outro lado registra cada escrita, e o texto não informa a política de sync do Redis. A razão de 1,9× a 2,2× compara, portanto, pontos de durabilidade diferentes.
• Razões entre sistemas misturam bases. Os autores dizem que a base do TreeSLS é mais lenta que o FreeBSD do Aurora por causa de outra libc, e que o TreeSLS a 1 ms tem desempenho absoluto menor que o Aurora a 5 ms. Os números de 2,4× e 2,5× não dizem qual configuração do TreeSLS foi usada, o Aurora usa DRAM como armazenamento, e o log do Aurora fica na DRAM, então não é durável.
• A evidência de corretude é leve para falhas de energia arbitrárias. O teste é queda e reboot manuais, e o argumento é um parágrafo informal e curto. Journaling, regras de versão e regras de migração interagem, mas não há injeção sistemática de falhas nem verificação. O Atmosphere mostra como é verificar invariantes de um kernel, embora prove outras propriedades e não persistência (pareamento meu).
• Escala e hardware são estreitos. A maior memória de aplicação da Tabela 2 é 1015 MiB em um dispositivo de 1 TiB, o Redis soma 262 PMOs a um padrão de 71, e o custo do checkpoint cresce com a quantidade e o tamanho dos objetos, segundo os autores. Casos com muitos processos, muitos cores e dezenas de GiB não são testados. Só se usa Optane com eADR em um nó NUMA.
• Duas inconsistências internas. O texto diz que o tamanho do checkpoint é muito menor que a memória de runtime, mas a Tabela 2 lista checkpoints maiores para o KMeans (134 contra 15 MiB) e o Redis (316 contra 129 MiB). Na Tabela 4, a linha de taxa de páginas sujas do Redis (33%) e do KMeans (37%) não decorre das contagens acima dela (89 de 241 é 37%, 197 de 431 é 46%). Além disso, "até 49%" é o melhor caso, já que o PCA elimina só 11% de seus faults.
• As entradas não são discutidas. Atrasar a saída cobre as respostas. O texto não diz o que acontece com requisições recebidas depois do último checkpoint, nem com estado de transporte como conexões TCP, depois de um rollback. A avaliação usa comunicação local à máquina, parecida com UDP.

• Sincronia externa em drivers reais de rede e de armazenamento, incluindo a restauração do estado dos dispositivos, o que os autores dizem estar fazendo.
• Proteger o estado na NVM com várias versões de checkpoint, replicação ou erasure coding, além da extensão de sistema eidético que permite ao usuário navegar por versões passadas, por exemplo para depuração.
• Persistência seletiva, para que aplicações ou regiões de memória possam ficar de fora do checkpointing, o que responderia ao limite da persistência uniforme (uma lacuna que vejo, não um plano do artigo).
• Injeção sistemática de falhas ou verificação formal do gerenciador de checkpoint e das regras de recuperação, e testes com muitos processos, muitos cores e mais memória (também uma lacuna minha).