Saltar para o conteúdo
Ridgun
Português
EnglishEspañolPortuguêsSvenskaCatalàGalegoEuskaraItaliano

39 O Livro do Ridgun

A lib pool — Pool Limitado de Trabalhadores, Round-Robin e Work-Stealing

39.1. Por que existe a lib pool? (O problema real e a filosofia Ridgun)

«Por que preciso de uma lib pool escrita de raiz em Ridgun puro em vez de ligar uma biblioteca C tradicional?»

Essa é a primeira pergunta que qualquer engenheiro de sistemas faz ao chegar à pool. E a resposta resume toda a filosofia do ridgun-libs:

Sejamos sinceros: lançar uma nova thread ou ator por cada pedido sem limite superior (unbounded spawning) garante que um pico de tráfego esgota a memória do servidor em segundos.

A lib pool fornece um despachante de tarefas com contrapressão explícita (PoolAccept, PoolRejectFull), partição equilibrada de lotes em $K$ vias (pool partition), reequilíbrio por roubo de trabalho (work-stealing) (pool steal rebalance) e execução paralela sobre atores nativos.

Num ecossistema tradicional, resolver as tarefas do domínio AGENT implica arrastar dependências externas em C, lidar com ponteiros brutos, conversões opacas de tipos, exceções não verificadas ou pausas imprevisíveis do coletor de lixo. Em Ridgun, a lib pool (src/main/ridgun/lib/pool.rg) aborda o problema com quatro princípios inegociáveis:

  1. Declare import pool (ou import pool as alias) no início do ficheiro: cada lib define o seu espaço de nomes module :: pool e em modo --strict as funções multi-palavra são sempre invocadas com espaços naturais.
  2. Encadeie os seus pipelines da esquerda para a direita com ->: escreva entrada passo um -> passo dois -> resultado, use máscaras (+ _ _ +) para desestruturar sequências e omita _ = em instruções sequenciais (ou descarte com -> ()).
  3. Recursão de cauda com TCO (Tail-Call Optimization): todas as travessias internas da pool são compiladas para ciclos nativos em espaço de pilha $O(1)$.
  4. Memória determinística (RMM1 / RMM2): cada estrutura intermédia é libertada no instante exato em que termina a sua última leitura, sem Garbage Collector.

39.2. Artefactos nativos, importação e catálogo completo da API de pool

No ridgun-libs, pool é uma lib de primeira classe localizada em src/main/ridgun/lib/pool.rg (domínio AGENT). Ao compilar com stable bundle, é empacotada em três formatos nativos:

ArtefactoCaminhoFinalidade
Bundle Ridguntarget/bundles/pool.rglibDistribuição e importação direta com import pool
Ficheiro compiladotarget/pool.rgcArtefacto intermédio verificado pelo ridgunc
Objeto partilhado ELF64target/libpool.soBiblioteca dinâmica nativa sem dependências de C nem libc

Cada lib declara o seu próprio espaço de nomes com module :: pool: basta escrever import pool (ou import pool as alias) no topo e invocar as suas funções com espaços naturais (minha funcao x) e pipelines -> (x minha funcao -> resultado).

39.2.1. Resumo das famílias funcionais da pool

Assinatura / Função / TipoO que faz e quando usar
pool new : Int -> Int -> PoolStateCria um pool limitado com workers vias e capacidade máxima max_queue
pool submit : PoolState -> PoolTask -> (PoolState, PoolDecision)Coloca uma tarefa na fila em round-robin ou devolve PoolRejectFull se saturado
pool partition / pool steal rebalanceDivide lotes por $K$ trabalhadores e rouba metade de uma fila sobrecarregada para um trabalhador livre
pool map sum / pool parallel sum2Despacha cargas de trabalho em paralelo sobre trabalhadores agent nativos

39.2.2. Catálogo exaustivo de tipos e assinaturas em src/main/ridgun/lib/pool.rg

Abaixo encontra-se o inventário completo de tipos algébricos (type), operadores (op ::) e assinaturas de funções (fn ::) definidos em src/main/ridgun/lib/pool.rg (1 tipos, 0 operadores e 14 funções):

Tipos algébricos e registos (type) da pool:

type AgentPool = Pool Int [Agent]
#Função / Assinatura (fn ::)Tipo de Retorno
1fn :: pool size AgentPoolInt
2fn :: pool agents AgentPool[Agent]
3fn :: pool get agent [Agent] IntAgent
4fn :: pool abs IntInt
5fn :: pool ask shard AgentPool Int AB
6fn :: pool broadcast AgentPool A()
7fn :: pool broadcast list [Agent] A()
8fn :: pool drain ready Agent[B]
9fn :: pool drain ready loop Agent [B][B]
10fn :: pool drain step Agent Option [B][B]
11fn :: pool drain all AgentPool[B]
12fn :: pool drain list [Agent] [B][B]
13fn :: pool stop list [Agent]()
14fn :: pool shutdown AgentPool()

39.3. Explorando a pool a fundo: Exemplos passo a passo de cada funcionalidade

Não basta ver a tabela de assinaturas: vamos explorar cada uma das funcionalidades da lib pool através de exemplos progressivos e executáveis em Ridgun. Começaremos pelas duas receitas tabulares de uso diário e depois percorreremos em detalhe todos os cenários funcionais, transformações e casos de fronteira verificados em src/test/ridgun/test pool.rg.

39.3.1. Exemplo 1: Fluxo principal em estilo tabular com pool

Repare como em Ridgun os sinais = e os passos de transformação com pool ficam alinhados como uma tabela limpa, sem variáveis mutáveis desnecessárias nem efeitos colaterais ocultos:

import pool

fn :: despachar a shard AgentPool Int String => String
      despachar a shard p hash_clave msg =
        pool ask shard p hash_clave msg

39.3.2. Exemplo 2: Composição segura e tratamento de casos de fronteira

Todas as funções da lib pool foram desenhadas para se comporem com guardas booleanas | e com as restantes 32 libs do ridgun-libs:

import pool

fn :: difundir y cerrar AgentPool String => ()
      difundir y cerrar p evento =
        pool broadcast p evento
        pool shutdown p

39.3.3. Exemplo 3: Combinadores de atores (agent ask, try ask, send batch, map batch, drain ready), pools particionados e reator de conexões

Neste exemplo prático exploramos de forma exaustiva como a pool se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test spec combinators pool and net agent => ()
      test spec combinators pool and net agent =
        w1 = agent (ag double worker)
        assert int equals (agent ask w1 21) 42 "agent ask 21 -> 42"
        mb = agent map batch w1 [3, 5, 7]
        assert int equals (ag sum ints mb) 30 "agent map batch [3,5,7] -> [6,10,14] sum 30"
        agent send batch w1 [10, 20] -> ()
        rc = agent receive count w1 2
        assert int equals (ag sum ints rc) 60 "agent send batch + agent receive count -> 60"
        c_dr = new counter agent 100
        send 5 to c_dr
        send 10 to c_dr
        dr = agent drain ready c_dr
        assert int equals (ag sum ints dr) 220 "agent drain ready [105, 115] -> 220"
        agent stop all [w1, c_dr] -> ()
        assert false (is agent alive w1) "w1 stopped by agent stop all"
        assert false (is agent alive c_dr) "c_dr stopped by agent stop all"

        s0 = new counter agent 0
        s1 = new counter agent 1000
        pl = Pool 2 [s0, s1]
        assert int equals (pool size pl) 2 "pool size 2"
        assert int equals (pool ask shard pl 0 5) 5 "pool ask shard 0 -> 5"
        assert int equals (pool ask shard pl 1 7) 1007 "pool ask shard 1 -> 1007"
        assert int equals (pool ask shard pl (0 - 3) 3) 1010 "pool ask shard negative key -> shard 1"
        pool broadcast pl 10 -> ()
        all_dr = pool drain all pl
        assert int equals (ag sum ints all_dr) 1035 "pool drain all [15, 1020] -> 1035"
        pool shutdown pl -> ()
        assert false (is agent alive s0) "pool s0 stopped"
        assert false (is agent alive s1) "pool s1 stopped"

        ca = agent (ag echo conn step) (CounterState 0)
        cb = agent (ag echo conn step) (CounterState 0)
        s_eof = conn feed payload (0 - 1) ca ""
        s_err = conn handle event (0 - 1) cb 8
        kept  = reactor sweep next s_eof (reactor sweep next s_err [])
        assert int equals (agent list len kept 0) 0 "reactor sweep next prunes closed slots"
        assert false (is agent alive ca) "ca stopped on EOF"
        assert false (is agent alive cb) "cb stopped on POLLERR"
        cc = agent (ag echo conn step) (CounterState 0)
        reactor shutdown [ConnSlot (0 - 1) cc] -> ()
        assert false (is agent alive cc) "cc stopped on reactor shutdown"

39.3.4. Exemplo 4: Ciclo de vida de agentes (is agent alive, agent status, stop agent) e agente contador com estado isolado (new counter agent)

Neste exemplo prático exploramos de forma exaustiva como a pool se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test agent lifecycle and counter => ()
      test agent lifecycle and counter =
        assert str eq (format agent status AgentRunning) "running" "format AgentRunning"
        assert str eq (format agent status AgentStopped) "stopped" "format AgentStopped"
        assert str eq (format agent status (AgentTimedOut 250)) "timeout after 250 ms" "format AgentTimedOut"
        assert str eq (format agent status (AgentFailed "boom")) "failed: boom" "format AgentFailed"
        assert str eq (format agent reply (ReplyInt 42)) "42" "format ReplyInt"
        assert str eq (format agent reply (ReplyStr "ok")) "ok" "format ReplyStr"
        assert str eq (format agent reply (ReplyBool True)) "true" "format ReplyBool True"
        assert str eq (format agent reply (ReplyBool False)) "false" "format ReplyBool False"
        assert str eq (format agent reply ReplyEmpty) "agent outbox empty" "format ReplyEmpty"
        assert str eq (format agent reply ReplyStopped) "agent stopped" "format ReplyStopped"
        assert str eq (format agent reply (ReplyTimeout 50)) "agent timeout after 50 ms" "format ReplyTimeout"
        assert str eq (format agent reply (ReplyError "bad")) "agent error: bad" "format ReplyError"

        c   = new counter agent 10
        assert ok (is agent alive c)
        assert str eq (format agent status (agent status c)) "running" "counter running"
        assert str eq (format agent reply (try poll int c)) "agent outbox empty" "empty outbox before send"
        assert eq (counter get c) 10
        assert eq (counter add c 5) 15
        assert eq (counter add c 7) 22
        assert str eq (format agent reply (ask int c 8)) "30" "ask int 8 -> 30"
        assert str eq (format agent reply (ask int with timeout c 12 200)) "42" "ask int with timeout -> 42"
        assert eq (counter reset c) 0
        assert eq (counter get c) 0
        bs  = ask batch int c [1, 2, 3, 4]
        assert eq (ag sum ints bs) 20

        c2  = new counter agent 100
        rel = relay int c c2 5
        assert str eq (format agent reply rel) "115" "relay int c (10+5=15) -> c2 (100+15=115)"

        st1 = stop agent c
        assert str eq (format agent status st1) "stopped" "stop agent returns AgentStopped"
        assert eq (is agent alive c) False
        assert str eq (format agent status (agent status c)) "stopped" "agent status after stop"
        assert str eq (format agent reply (ask int c 1)) "agent stopped" "ask int after stop"
        assert str eq (format agent reply (try poll int c)) "agent stopped" "try poll int after stop"
        assert str eq (format agent reply (ask int with timeout c 1 50)) "agent stopped" "ask int with timeout after stop"
        assert str eq (format agent reply (relay int c c2 1)) "agent stopped" "relay int after stop"
        c0  = new counter agent 0
        assert int equals (counter get c0) 0 "counter 0 initial"
        assert int equals (counter add c0 3) 3 "counter 0 add 3"
        stop agent c0
        stop agent c2
        assert eq (is agent alive c2) False

39.3.5. Exemplo 5: Agente de registo append-only (new log agent) e armazenamento chave-valor em memória por passagem de mensagens (new kv agent)

Neste exemplo prático exploramos de forma exaustiva como a pool se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

fn :: test log and kv agents => ()
      test log and kv agents =
        lg  = new log agent "\n"
        assert ok (is agent alive lg)
        assert str eq (format agent reply (try poll str lg)) "agent outbox empty" "log empty outbox"
        assert str eq (log read lg) "" "initial log empty"
        assert str eq (log append lg "alpha") "alpha" "log append alpha"
        assert str eq (log append lg "beta") "alpha\nbeta" "log append beta"
        assert str eq (format agent reply (ask str with timeout lg "gamma" 200)) "alpha\nbeta\ngamma" "ask str with timeout gamma"
        assert str eq (log read lg) "alpha\nbeta\ngamma" "log read"
        assert str eq (log clear lg) "" "log clear"
        assert str eq (log read lg) "" "log read after clear"
        b   = ask batch str lg ["one", "two"]
        assert str eq (ag join strs b) "one|one\ntwo" "ask batch str"
        lg2 = new log agent ":"
        assert str eq (format agent reply (relay str lg lg2 "three")) "one\ntwo\nthree" "relay str"
        stop agent lg
        stop agent lg2
        assert str eq (format agent reply (ask str lg "x")) "agent stopped" "ask str after stop"

        kv  = new kv agent
        assert ok (is agent alive kv)
        assert int equals (kv count kv) 0 "kv count 0"
        assert false (kv has kv "host") "kv has host false"
        assert str eq (kv put kv "host" "127.0.0.1") "127.0.0.1" "kv put host"
        assert str eq (kv put kv "port" "8080") "8080" "kv put port"
        assert int equals (kv count kv) 2 "kv count 2"
        assert ok (kv has kv "host")
        assert ok (kv has kv "port")
        assert str eq (kv get kv "host") "127.0.0.1" "kv get host"
        assert str eq (kv get kv "port") "8080" "kv get port"
        assert str eq (kv keys kv) "host,port" "kv keys"
        assert str eq (kv put kv "port" "9090") "9090" "kv overwrite port"
        assert str eq (kv get kv "port") "9090" "kv get updated port"
        assert int equals (kv count kv) 2 "kv count after overwrite"
        assert str eq (kv delete kv "host") "127.0.0.1" "kv delete host"
        assert false (kv has kv "host") "kv has host after delete"
        assert int equals (kv count kv) 1 "kv count 1"
        assert str eq (kv clear kv) "" "kv clear"
        assert int equals (kv count kv) 0 "kv count after clear"
        stop agent kv
        assert false (is agent alive kv) "kv stopped"

39.3.6. Exemplo 6: Encaminhamento determinístico por chave (pool ask shard), difusão (pool broadcast), drenagem não bloqueante (pool drain all) e encerramento (pool shutdown)

Neste exemplo prático exploramos de forma exaustiva como a pool se comporta neste bloco funcional, incluindo entradas padrão, combinações de parâmetros e valores limite:

import agent
import pool

fn :: shard worker (state : Int) (delta : Int) => (Int, Int)
      shard worker state delta =
        next = state + delta
        (next, next)

fn :: ejemplo pool completo => (Int, Int, [Int])
      ejemplo pool completo =
        w0   = agent shard worker 100
        w1   = agent shard worker 200
        w2   = agent shard worker 300
        p    = Pool 3 [w0, w1, w2]
        sz   = pool size p
        -- Enrutamiento determinista por clave: abs(key_hash) % 3
        r_a  = pool ask shard p 0 5
        r_b  = pool ask shard p 1 10
        -- Difusión (broadcast) a todos los shards del pool
        pool broadcast p 1 -> ()
        pend = pool drain all p
        pool shutdown p -> ()
        (sz, r_a + r_b, pend)

39.4. Debaixo do capô: como a pool é construída em Ridgun puro (src/main/ridgun/lib/pool.rg)

Uma das maiores vantagens do ridgun-libs é que não existem caixas-pretas em C. Pode abrir src/main/ridgun/lib/pool.rg e ler exatamente como cada operação é implementada usando pattern matching, árvores de guardas | / |. e recursão de cauda (TCO). Vejamos as peças-chave da sua implementação real:

39.4.1. Implementação interna: Core Implementation Part 1

Observe como pool.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

module :: pool

type AgentPool = Pool Int [Agent]

fn :: pool size AgentPool   => Int
      pool size (Pool sz _) =  sz

fn :: pool agents AgentPool    => [Agent]
      pool agents (Pool _ ags) =  ags

fn :: pool get agent [Agent]  Int => Agent
      pool get agent (ag:_)   0   =  ag
      pool get agent (_:rest) idx =  pool get agent rest (idx - 1)

fn :: pool abs Int => Int
      pool abs x
        | x < 0     = 0 - x
        | otherwise = x

fn :: pool ask shard AgentPool Int A => B
      pool ask shard (Pool size agents) key_hash msg =
        (pool abs key_hash) % size -> shard_idx
        pool get agent agents shard_idx -> target_ag
        ask target_ag msg

fn :: pool broadcast AgentPool       A   => ()
      pool broadcast (Pool _ agents) msg =  pool broadcast list agents msg

39.4.2. Implementação interna: Core Implementation Part 2

Observe como pool.rg estrutura primeiro as assinaturas fn :: ... => ... e resolve cada caso através de equações alinhadas e chamadas de cauda:

fn :: pool broadcast list [Agent]   A   => ()
      pool broadcast list []        _   =  ()
      pool broadcast list (ag:rest) msg =
        send msg to ag
        pool broadcast list rest msg

fn :: pool drain ready Agent => [B]
      pool drain ready ag    =  pool drain ready loop ag []

fn :: pool drain ready loop Agent [B] => [B]
      pool drain ready loop ag acc =
        pool drain step ag (try receive from ag) acc

fn :: pool drain step Agent Option [B] => [B]
      pool drain step _ None acc = acc
      pool drain step ag (Some r) acc = pool drain ready loop ag (acc :: [r])

fn :: pool drain all AgentPool       => [B]
      pool drain all (Pool _ agents) =  pool drain list agents []

fn :: pool drain list [Agent]   [B] => [B]
      pool drain list []        acc =  acc
      pool drain list (ag:rest) acc =
        ag pool drain ready -> ready
        pool drain list rest (acc :: ready)

fn :: pool stop list [Agent]   => ()
      pool stop list []        =  ()
      pool stop list (ag:rest) =
        stop ag
        pool stop list rest

fn :: pool shutdown AgentPool       => ()
      pool shutdown (Pool _ agents) =  pool stop list agents

39.5. Garantias algorítmicas, memória RMM1/RMM2 e as 5 Regras de Ouro da pool

  • Garantia algorítmica e de segurança: Capacidade de fila estritamente limitada (queued <= max_queue) para proteger a memória sob sobrecarga e distribuição determinística entre trabalhadores.
  • Complexidade de pilha $O(1)$ com TCO: Todos os ciclos recursivos em src/main/ridgun/lib/pool.rg estão em posição de cauda, pelo que o ridgunc os compila para saltos nativos sem crescimento de pilha.
  • Memória determinística (RMM1/RMM2): Zero pausas de coletor de lixo; todas as estruturas intermédias são libertadas de forma determinística à saída do escopo.
  • Verificação contínua: Testada exaustivamente com stable check e pela suite automatizada src/test/ridgun/test pool.rg.

As 5 Regras de Ouro ao programar com a pool

  1. Declare import pool no início do ficheiro e aproveite a equivalência entre espaços e underscores para que o seu código se leia como prosa.
  2. Alinhe os seus pipelines de dados com =: encadeie as chamadas à pool em passos nomeados e deixe o stable format alinhar as colunas.
  3. Aproveite as funções totais da pool nas suas guardas |: verifique os valores de retorno ou desempacote os ADTs com pattern matching em vez de assumir que a entrada externa é sempre válida.
  4. Evite copiar grandes estruturas se só precisa de consultar um campo: lembre-se de que no RMM2 os argumentos de entrada não incrementam nem decrementam contadores (+0 / -0).
  5. Combine a pool com test (import test): escreva sempre asserções com assert equals ou assert true para fixar os invariantes do seu domínio.

No Capítulo 40 passaremos a explorar em profundidade a lib net_agent (A lib net_agent — Supervisor de Ligações de Rede e Ponte de Eventos Não Bloqueante).