Atingindo latência de cauda em escala de microssegundos com eficiência por meio de escalonamento ótimo aproximado

Serviços de datacenter respondem a requisições em microssegundos, mas enfrentam metas rígidas de latência de cauda, porque uma requisição de usuário se espalha por muitos servidores e o mais lento define o tempo de resposta. Em um único servidor, a latência de cauda é dominada pelo atraso de enfileiramento. A teoria de filas diz que o First Come, First Served (FCFS) é ótimo para cargas de cauda leve, que o Processor Sharing (PS) é ótimo para cargas de cauda pesada, e que uma fila única supera várias. Os runtimes do estado da arte, por isso, combinam uma fila com preempção, mas os autores argumentam que isso custa throughput. Eles citam uma penalidade de 20% de throughput na preempção do Shinjuku com quantum de 5 µs e de 50% com 2 µs. O Shinjuku também depende de um uso não padrão do hardware de virtualização, o que o exclui de VMs em nuvem pública, e o Persephone precisa conhecer a distribuição de tempos de serviço de antemão.

Este artigo do SOSP 2023 (Koblenz), da EPFL e do Imperial College London, apresenta o Concord. Ele não cria uma política nova. Cria mecanismos que aproximam os ótimos a baixo custo, aceitando um escalonamento um pouco impreciso em troca de throughput.

Termos que convém manter distintos. O dispatcher é a thread dona da fila, que entrega requisições às threads de trabalho fixadas em cores. O quantum é quanto tempo uma requisição pode rodar antes de ser preemptada. O JBSQ(k), Join-Bounded Shortest Queue, adiciona uma fila limitada de profundidade k por worker. Uma política blind não usa conhecimento da aplicação. O slowdown é o tempo que uma requisição passa no servidor dividido pelo seu tempo de serviço sem instrumentação.

Vale conhecer antes: o trade-off entre FCFS e PS, o custo de uma troca de contexto e de uma interrupção entre processadores (IPI), e os cache-coherence misses entre cores. O artigo cita o ghOSt como um escalonador de produção com outras prioridades (multi-tenancy, isolamento de falhas), e cita o Snap e o Demikernel entre os sistemas com metas na escala de microssegundos. Dois pareamentos meus, não do artigo: o Skyloft, posterior, cita o Concord entre os sistemas que fazem preempção mas dedicam cores a uma só aplicação, e o PeeR também faz preempção em pontos conhecidos (chamadas de helper do eBPF) em vez de usar interrupções.

• Um modelo de overhead. Com um dispatcher e n workers fixados em cores, os autores dividem os ciclos perdidos em três fontes: a preempção (custo de notificação mais instrumentação), a entrega síncrona entre dispatcher e worker, e um dispatcher que não executa código da aplicação. O Concord responde a cada uma com um mecanismo.
• Cooperação imposta pelo compilador. O dispatcher cronometra cada requisição e, quando o quantum acaba, escreve em uma cache line dedicada de cada worker. A instrumentação do compilador faz o código da aplicação consultar essa linha. Ao ver o sinal, o worker confirma, salva o contexto da requisição, troca para o contexto padrão e cede a CPU, e o dispatcher recoloca a requisição na fila. Os probes ficam na entrada das funções, em torno de chamadas a código não instrumentado e nos back-edges de loops, e os loops são desenrolados até ter ao menos 200 instruções de LLVM IR. A maioria das verificações é um acerto no L1 mais uma comparação (cerca de 2 ciclos), e a verificação final é um coherence miss de cerca de 150 ciclos, contra cerca de 1.200 ciclos de uma IPI do Shinjuku e cerca de 30 do rdtsc(). O yield é impreciso, já que o worker só para no próximo probe.
• Preempção com segurança em primeiro lugar. Os workers nunca são preemptados dentro de chamadas externas, como chamadas de sistema, nem enquanto seguram um lock da aplicação. O compilador controla o que instrumenta, então a libc não precisa de mudanças. Para os locks, os desenvolvedores incrementam e decrementam um contador em torno de lock e unlock, e os autores precisaram de 4 linhas no LevelDB.
• JBSQ(k) para workers sem paradas. O dispatcher empurra cada requisição para a fila de worker mais curta que tenha vaga, de modo que o worker que termina uma requisição já encontra a próxima local. Os autores acharam k = 2 suficiente para tempos de serviço acima de 1 µs e sugerem k em torno do custo da entrega dividido pelo tempo de serviço, mais um. Eles dizem ser os primeiros a notar que o JBSQ(k) é necessário para mascarar a latência de coerência de cache nesse cenário.
• Um dispatcher que conserva trabalho. Quando todas as filas dos workers estão cheias, o dispatcher executa uma requisição por um quantum, fazendo auto-preempção por probes de rdtsc(). Por isso ele usa uma segunda versão compilada do código da aplicação, e só pega requisições que ainda não começaram e termina as que começa, guardando o contexto em um buffer privado.
• API e tamanho. As aplicações fornecem três callbacks (setup, setup_worker, handle_request). Dois passes de LLVM 9 de cerca de 350 linhas cada fazem a instrumentação. O Concord foi integrado ao Shinjuku com 847 linhas adicionadas e ao Persephone com 2.358, o que exigiu também portar do Shinjuku as threads em nível de usuário.

Duas máquinas CloudLab c6420 ligadas diretamente, cada uma com um Xeon Gold 6142 de 32 cores a 2,60 GHz, 376 GB de RAM e uma NIC Intel X710 de 10 Gbps, com round trip de 10 µs. O servidor roda Ubuntu 18.04 no Linux 4.4.185, a versão que o módulo de kernel do Shinjuku exige, com 14 workers em cores físicos dedicados. As chegadas seguem um processo de Poisson, cada execução dura 60 segundos com os primeiros 10% das amostras descartados, e a latência é medida no cliente.

As bases de comparação são o Shinjuku e o Persephone, restritas a políticas blind. O Persephone é configurado como C-FCFS ("Persephone-FCFS") para cargas de baixa dispersão, e todas as execuções no cluster dos autores usam o Concord construído sobre o Shinjuku. A métrica é o throughput sustentado com slowdown de 50× no percentil 99,9. As cargas sintéticas ficam em spin pelo tempo pedido: Bimodal(50:1, 50:100), Bimodal(99.5:0.5, 0.5:500), Fixed(1) e uma mistura TPCC. As cargas reais usam o LevelDB com 15.000 chaves mantidas em memória (GET cerca de 600 ns, PUT e DELETE cerca de 2,3 µs, SCAN cerca de 500 µs), uma vez com 50% de GET e 50% de SCAN e outra com uma mistura baseada no ZippyDB de 78% de GET, 13% de PUT, 6% de DELETE e 3% de SCAN. Os quanta são 5 µs e 2 µs, e 10 µs no TPCC. Outros experimentos cobrem uma ablação, 24 benchmarks do Phoenix, Parsec e Splash-2, uma configuração de 4 cores, uma simulação de filas e um servidor Sapphire Rapids de 192 cores.

Estes são os resultados relatados pelos autores.

• Para onde vai o overhead. As IPIs do Shinjuku custam cerca de 1.200 ciclos para receber, o que o modelo converte em cerca de 12% de overhead com 5 µs e 30% com 2 µs, e o overhead medido é de 33% com 2 µs e 6% com 10 µs. A instrumentação com rdtsc() custa cerca de 21% em qualquer quantum. O overhead do Concord fica em torno de 1% a 1,5%, e ele empata com as IPIs perto de 25 µs.
• Cargas sintéticas de alta dispersão. Em comparação com o Shinjuku, o Concord sustenta 18% e 20% mais throughput com quantum de 5 µs nas duas cargas bimodais, e 45% e 52% mais com 2 µs. O Persephone-FCFS cruza a meta de slowdown bem antes.
• Cargas de baixa dispersão. No Fixed(1), o Concord obtém 2% menos que o Shinjuku e o Persephone, porque o dispatcher é o gargalo e calcula a fila mais curta. No TPCC, o Persephone-FCFS supera os dois sistemas com preempção, e o Concord ainda supera o Shinjuku.
• LevelDB. Com 50% de GET e 50% de SCAN (dispersão de 1000×), o Concord sustenta 52% mais com 5 µs e 83% mais com 2 µs. Na mistura do ZippyDB, sustenta 19% mais com 5 µs.
• Ablação. Na carga de LevelDB 50/50, o Shinjuku sustenta cerca de 19 kRps na meta. Somar a cooperação dá cerca de 22,5, depois o JBSQ(2) cerca de 32, depois o dispatcher cerca de 35.
• Verificações dos mecanismos. Com toda requisição preemptada, o Concord reduz o overhead de preempção em 4× contra o Shinjuku, e a cooperação contribui mais. O JBSQ(2) reduz de 9× a 13× o overhead de ociosidade dos workers. Um dispatcher que conserva trabalho soma 33% de throughput em uma configuração de 4 cores (1 dispatcher, 1 networker, 2 workers).
• Instrumentação. Em 24 benchmarks o overhead médio é de 1,04% (máximo de 6,7%), contra 13,7% (máximo de 37%) nos números publicados do Compiler Interrupts, ou seja, 13,1× menor na média e 5,5× no máximo. Com quantum de 5 µs, o desvio padrão do quantum obtido fica abaixo de 2 µs (média de 0,29 µs, máximo de 1,8 µs).
• Locks e hardware. Em um microbenchmark montado pelos autores, o Shinjuku não conseguia preemptar por 100 µs dentro de um GET longo do LevelDB, e o Concord deu 4× o throughput. Contra as IPIs em espaço de usuário da Intel em um servidor Sapphire Rapids, o overhead do Concord é cerca de 2× menor.

O artigo declara seus custos abertamente. Ele admite o seguinte.

• Slowdown maior com carga baixa. O dispatcher às vezes pega uma requisição durante uma rajada e não pode migrá-la depois, o que eleva o slowdown do percentil 99,9 em cerca de 3 acima do Shinjuku com carga baixa. Os autores aceitam isso e dizem que o roubo de trabalho pode ser desligado.
• Código-fonte e um único dispatcher. O protótipo exige código-fonte em uma linguagem compilada com LLVM, então não serve como runtime oferecido por um provedor de nuvem, e a instrumentação de binários está planejada. Um único dispatcher pode virar gargalo conforme os cores crescem e os tempos de serviço encolhem, e os autores sugerem replicação ou batching.
• Segurança por convenção. Não preemptar em chamadas de sistema ou seções críticas pode, em teoria, causar picos, o que os autores chamam de raro na prática. Multi-tenancy e isolamento de falhas, que o ghOSt oferece, ficam para trabalho futuro.

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

• O texto discorda de si mesmo em alguns pontos. A introdução diz até 18% com quantum de 5 µs nas cargas sintéticas, enquanto a avaliação traz 18% e 20%. A Seção 3.1 diz 25 benchmarks, enquanto a Tabela 1 e a Seção 5.4 têm 24. A Seção 5.1 diz que a Seção 4 detalha a diferença entre Concord-Shinjuku e Concord-Persephone, mas a Seção 4 só traz contagens de linhas, então a afirmação de que as diferenças são minúsculas não é demonstrada. Com 2 µs o texto dá ao Shinjuku 33% de overhead e ao Concord 12× menos, cerca de 2,8%, mas também descreve o Concord como quase constante entre 1% e 1,5%. Esta análise usa os números do corpo do texto.
• A pontualidade é validada em outra escala que os maiores ganhos. A simulação usa média de 5 µs e o desvio padrão foi medido só com quantum de 5 µs, em benchmarks de computação, enquanto os maiores ganhos (45% a 83%) são com 2 µs, onde um desvio como o máximo de 1,8 µs visto com 5 µs seria quase o quantum inteiro.
• A comparação de instrumentação é indireta. Os números do Compiler Interrupts são os publicados, já que os autores não conseguiram replicá-los, e o overhead do Concord é muitas vezes negativo por causa do desenrolamento de loops, o que puxa a média de 1,04% para baixo.
• Uma bancada, duas bases de comparação. Tudo roda em duas máquinas bare-metal com 14 workers. A facilidade de implantação em nuvem pública é argumentada pelo mecanismo, e a única evidência de VM pequena é uma emulação de 4 cores. Shenango, Caladan, ZygOS e ghOSt são discutidos mas não executados, então a extensão a sistemas de fila lógica única é um plano.
• Sem dispersão reportada. Cada execução dura 60 segundos, e o texto não informa repetições nem barras de erro. Os ganhos são lidos onde as curvas cruzam a meta, trecho íngreme perto da saturação, então uma diferença como 18% contra 20% poderia ser ruído. A afirmação de que o slowdown com carga baixa sobe "em todas as cargas" é mostrada para uma.
• Evidência estreita para a segurança. O "esforço desprezível" se apoia em 4 linhas em uma aplicação, e o LevelDB rodou totalmente em memória, onde não há chamadas de sistema nem I/O bloqueante, que é onde nunca preemptar em chamadas externas mais importaria. O motivo de usar só quantum de 5 µs no ZippyDB (todas as requisições maiores que 2 µs) também combina mal com os GETs de 600 ns informados na mesma seção.
• O ganho do dispatcher depende da carga. Ele exige um dispatcher ocioso, e os 33% vêm de uma carga com volume absoluto baixo.

• Instrumentação em nível de binário, para que os tenants não precisem compartilhar o código-fonte, o que os autores planejam.
• Vários dispatchers, ou a cooperação e o roubo de trabalho do Concord sobre sistemas de fila lógica única como Shenango e Caladan, além de políticas multi-tenant e isolamento de falhas no estilo do ghOSt, tudo citado pelos autores.
• A cooperação imposta pelo compilador além do escalonamento, para garbage collection, gerenciamento de timers, membarrier() e VMs confidenciais, onde interrupções injetadas pelo hypervisor não são confiáveis, como os autores sugerem.
• Medir a pontualidade com quanta de 2 µs, em serviços que fazem chamadas de sistema, bloqueiam em I/O ou seguram seções críticas longas, dentro de uma VM real de nuvem pública e com execuções repetidas.