Caladan: mitigando interferência em escalas de microssegundos
Título original: Caladan: Mitigating Interference at Microsecond Timescales
Publicado14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)
Saiu em uma revista, congresso ou livro, que normalmente avaliam o trabalho antes de aceitar. Mesmo assim, um único estudo nunca é a palavra final.
Resumo
A sabedoria convencional diz que recursos de CPU como núcleos, caches e largura de banda de memória precisam ser particionados para isolar o desempenho entre tarefas. A ampla disponibilidade de particionamento de cache nas CPUs modernas e a prática recomendada de fixar aplicações sensíveis à latência em núcleos dedicados confirmam essa crença. Neste artigo, mostramos que o particionamento de recursos não é nem necessário nem suficiente. Muitas aplicações têm padrões de requisição em rajadas ou comportamento em fases, mudando drasticamente a quantidade e o tipo de recursos de que precisam. Infelizmente, sistemas baseados em particionamento não reagem rápido o bastante a essas mudanças, o que resulta em picos extremos de latência e em oportunidades perdidas de aumentar a utilização da CPU. O Caladan é um novo escalonador de CPU que consegue qualidade de serviço (latência de cauda, vazão etc.) significativamente melhor por meio de um conjunto de sinais de controle e políticas que se apoiam em alocação rápida de núcleos em vez de particionamento de recursos. O Caladan consiste em um núcleo escalonador centralizado que gerencia ativamente a contenção na hierarquia de memória e entre hyperthreads, e em um módulo de kernel que contorna o escalonador padrão do Linux para permitir monitoramento e colocação de tarefas em escala de microssegundos. Ao colocar o memcached junto de uma carga de melhor esforço com coleta de lixo, o Caladan supera o Parties, um sistema de particionamento de recursos de ponta, em 11.000 vezes, reduzindo a latência de cauda de 580 ms para 52 µs durante mudanças no uso de recursos, mantendo alta utilização da CPU.
Tradução nossa do resumo original dos autores, em inglês.
Análise de pesquisa
Escrita pelo Kurz, não pelos autores do paper. O resumo acima é dos próprios autores.
- Última revisão
- Versão
- 1.0
Visão geral
Operadores empacotam tarefas sensíveis à latência (LC) e de melhor esforço (BE) na mesma máquina para elevar a utilização, e então as tarefas disputam núcleos, o cache de último nível (LLC), a largura de banda de memória e unidades de execução. A resposta usual é particionar: a Cache Allocation Technology (CAT) da Intel reserva vias do LLC, e sistemas como Heracles e Parties ajustam núcleos e vias passo a passo. Os autores medem a convergência desses sistemas em segundos (Tabela 1: o Heracles decide a cada 2 a 15 s, o Parties a cada 500 ms e converge em 10 a 20 s). A carga real muda mais rápido: um coletor de lixo numa tarefa BE satura a largura de banda de memória por 100 a 200 ms, reduz à metade a taxa de serviço do memcached e faz seu atraso de fila crescer 5 µs a cada 10 µs, chegando a uma cauda 1000 vezes maior que a normal (Figura 1). Dessa conta sai uma regra: para que a latência não cresça X depois que a taxa de serviço cai pela metade, o escalonador precisa reagir em até 2X.
Este artigo do OSDI 2020, do MIT CSAIL e da UC Berkeley, é o sucessor direto do Shenango e reaproveita seu runtime (threads verdes, roubo de trabalho, E/S com kernel bypass, núcleos garantidos e de rajada). O único sinal do Shenango é o atraso de fila, e ele só aloca núcleos em resposta à carga. O Caladan mantém a alocação de núcleos como única alavanca, mas acrescenta sinais que apontam a origem da interferência. O artigo também cita o IX e o Snap entre os sistemas que ajustam núcleos conforme a carga, e o Shinjuku pela preempção baseada em IPIs.
Vale conhecer antes: hyperthreads irmãos dividem um núcleo físico, então um irmão ocupado atrasa uma requisição; a latência de acesso à memória sobe devagar com a largura de banda e depois exponencialmente perto da saturação; e a diferença entre tempo de serviço (prejudicado pela interferência) e atraso de fila (prejudicado pela perda de capacidade de computação).
Contribuição
- Alocação de núcleos como única alavanca. Menos núcleos para uma tarefa significa menos largura de banda de memória, um irmão ocioso significa nenhuma contenção de hyperthread, e núcleos extras para a vítima recuperam a capacidade perdida. A Tabela 2 liga cada recurso disputado a uma ação. Para o LLC não há ação direta, então o Caladan apenas adiciona núcleos à vítima.
- Três controladores num núcleo escalonador dedicado, cada um rodando a cada 10 µs. O controlador de largura de banda lê o contador global da DRAM e, acima de THRESH_BW, amostra as faltas de LLC por núcleo pela PMU, acha a tarefa BE com mais faltas e revoga um núcleo por rodada. O controlador de hyperthreads bane o irmão de um núcleo cuja requisição LC passou de THRESH_HT. O alocador de topo concede um núcleo a qualquer tarefa cujo atraso de fila passe de THRESH_QD, pontuando núcleos por pares de irmãos ociosos, depois por pareamento entre tarefas diferentes, depois por localidade de cache.
- KSCHED, um módulo de kernel de 533 linhas. O escalonador escreve comandos em memória compartilhada por núcleo e acorda os núcleos-alvo com IPIs multicast, de modo que os próprios núcleos executam o trabalho de escalonamento, de forma assíncrona. Ele acorda ou preempta uma tarefa, deixa um núcleo ocioso com
mwaite lê contadores de desempenho remotos com carimbo de TSC. - Implementação. O escalonador tem 3.524 linhas e deriva do Shenango. O runtime liga libibverbs e SPDK diretamente, então o núcleo escalonador não encaminha mais pacotes (um gargalo do Shenango). O atraso de fila de pacotes é medido pelos carimbos de tempo dos descritores RX da placa.
- Sem hardware de particionamento. O Caladan não usa CAT nem Memory Bandwidth Allocation. Os autores argumentam que o MBA deixa núcleos limitados parados em stall, e que CMT e MBM levam milissegundos para estabilizar.
Metodologia
Um servidor com duas CPUs Xeon Broadwell de 12 núcleos (24 hyperthreads cada), placa ConnectX-5 de 40 Gb/s e um NVMe Optane, Linux 5.2.0 com caminho de IPI multicast modificado (5.4.0 para a linha de base Linux, com tarefas BE em SCHED_IDLE). Tudo fica confinado ao primeiro soquete, TurboBoost, estados C e escala de frequência estão desligados, e as mitigações de Meltdown e MDS estão desativadas. Os clientes são máquinas de quatro núcleos com gerador de carga de laço aberto e chegadas de Poisson. São 22 núcleos garantidos para LC, e um núcleo físico fica para o escalonador. Tarefas LC: memcached (mistura USR do Facebook, modificado para criar um thread por conexão), silo rodando TPC-C e um servidor novo de blocos NVMe com compressão e criptografia. Tarefas BE: x264, swaptions (e uma versão com coletor Boehm, swaptions-GC) e streamcluster do PARSEC, mais os antagonistas sintéticos stream-L2 e stream-DRAM. Como o Parties não estava disponível, os autores o reimplementaram no mesmo runtime ("Parties*"), com hyperthreads ligados. THRESH_QD é 10 µs, THRESH_BW 25 GB/s (70 a 80% da capacidade), THRESH_HT 25 µs para o silo, 40 µs para o storage e infinito para o memcached.
Resultados
- Interferência constante de largura de banda (stream-DRAM, Figura 4). Linux e Shenango chegam a latências de cauda até 235 e 6 vezes maiores que sem interferência, e o Shenango perde 75% da vazão porque seu núcleo escalonador, que também processa pacotes, fica sobrecarregado. Caladan e Parties* mantêm latência de cauda parecida com e sem interferência.
- Interferência em fases (memcached com swaptions-GC, 800.000 requisições/s, execução de 120 s, Figura 5). O Parties* tem latência no percentil 99,9 11.000 vezes maior que a do Caladan durante os ciclos de GC e 5% menos vazão BE. Os valores 580 ms contra 52 µs estão no resumo. A série temporal é um gráfico em escala log, então qualquer valor intermediário aqui seria leitura de gráfico.
- 15 pareamentos (Figura 6). Storage e memcached ficam perto da latência de cauda sem colocação. O silo mostra um pequeno aumento com carga baixa, atribuído à sensibilidade ao LLC. A vazão BE depende do par: x264, swaptions-GC e stream-L2 trocam tempo de CPU de forma linear, enquanto streamcluster e stream-DRAM são contidos pelo controlador de largura de banda. O texto não dá números para essa figura.
- Muitas tarefas (Figura 7). Três tarefas LC mais swaptions-GC e streamcluster, com até 230.000 realocações de núcleo por segundo e latência de cauda baixa mesmo com a carga e o GC mudando.
- KSCHED. Ao mover 22 tarefas, as chamadas de sistema do Linux custam 43 vezes mais trabalho de escalonamento e 5 vezes mais latência. Com 11 tarefas LC, o Caladan chega a 560.000 realocações/s no pico, enquanto a versão com mecanismos do Linux engarrafa perto de 285.000.
- Controladores (Figura 8c, Figura 9). Os dois são necessários com carga maior no storage. Contra as políticas do Elfen, o Caladan obtém 37% mais vazão LC por deixar a tarefa LC rodar junto de si mesma, e 5% mais vazão BE com carga baixa. Sem o controlador de hyperthreads, a latência de cauda chega a ser 117 µs maior.
- Parâmetros (Figura 10). Um THRESH_QD de 100 µs dá 7% mais vazão BE em troca de 54 µs a mais na latência de cauda LC.
Análise crítica
O que o artigo admite: o Caladan não gerencia interferência entre nós NUMA e não impede ataques de execução transitória entre hyperthreads irmãos. Exige que as aplicações usem seu runtime e que as tarefas LC exponham concorrência (o memcached foi modificado). Aplicações fora do runtime não podem ser contidas. Ele enxerga a interferência no LLC só pelo atraso de fila, e por isso compensa com núcleos extras; os autores sugerem trazer o particionamento em hardware de volta para esse caso. Gerenciamento de energia não é explorado.
O que segue é minha leitura, não afirmação do artigo.
- Especificidades da Intel. A avaliação usa Xeons Broadwell, e o desenho depende de um contador global de largura de banda da DRAM, de contadores de faltas de LLC da PMU, de
mwaite de IPIs multicast. O artigo não discute CPUs de outros fabricantes, então a portabilidade não foi testada. - Uma máquina. O escalonador é por host. Não há resultado em nível de cluster, e o artigo só diz que um escalonador de cluster poderia receber relatos quando o provisionamento impede a mitigação.
- A linha de base principal é uma reimplementação. Os 11.000x são contra o Parties*, feito pelos autores sem o código original e com E/S em kernel bypass e hyperthreads acrescentados, num único par de cargas, com uma única carga. Eles também não implementaram alguns componentes do Parties (escala de frequência, recursos fora de disputa). O Heracles não foi executado, e os números dele na Tabela 1 vêm do comportamento relatado.
- Não comparado. Nenhuma comparação direta com Shinjuku (só as velocidades de IPI relatadas), Arachne ou ZygOS, e nenhuma execução do próprio Caladan com cache particionado.
- A calibragem importa. Os autores ajustaram os três limiares para baixa latência, e as mitigações de Meltdown e MDS foram desativadas.
Literatura posterior, marcada como tal e conhecida aqui só pelas análises deste catálogo, não pelos artigos originais: a análise do Skyloft observa que o Caladan não aparece como linha de base ali, e a do Concord diz que o Caladan é discutido mas não executado. Não li outros trabalhos posteriores.
Pesquisas futuras
- Mitigação com consciência de NUMA (revogar núcleos ou migrar tarefas entre nós), que os autores planejam.
- Particionamento em hardware que tolere uso de LLC em rápida mudança, o que poderia reduzir os núcleos extras dados às vítimas.
- Rodar tarefas que não usam o runtime próprio, já que só núcleos gerenciados pelo Caladan podem ser contidos.
- Uma comparação com escalonadores no kernel e delegados (ghOSt, Rakaia): eles conseguem reagir à interferência em dezenas de microssegundos sem um núcleo escalonador em spin? Esta pergunta é minha, não do artigo.
Texto completo
Discussão · 0
Entre para participar da discussãoNenhum post ainda. Seja o primeiro a iniciar a discussão.