Autor: César Devera

Em 2016, o Facebook lançou na F8 a API da sua plataforma de comunicação instantânea, o Messenger. Imediatamente desenvolvedores de todas as partes começaram a fazer experimentos com a plataforma, e a Movile não foi exceção, criando o ChatClub.

Tínhamos inicialmente a proposta de oferecer salas de bate-papo para múltiplos usuários sobre a plataforma do Messenger, já que ele não foi originalmente criado para conversas em grupo.

Depois, o ChatClub continuou evoluindo e hoje é um produto completo de comunicação, modular e configurável. Mais detalhes em https://chatclub.me

A API do Messenger, assim como diversas outras do Facebook, é totalmente gratuita e aberta para os desenvolvedores, mas nem por isso ela deixa de ter limites e regras de uso. Essa é a única forma de o Facebook compartilhar sua infraestrutura sem comprometer a qualidade do serviço para os usuários.

Entre as regras e limites, está um limite de volume de acessos na API, que restringe a quantidade e a velocidade de chamadas que um desenvolvedor ou projeto externo pode consumir, e é sobre este limite (e como lidar com ele) que se trata este artigo.

O problema

Para começar a desenvolver um chatbot, ou uma aplicação sobre a plataforma Messenger, o desenvolvedor precisa criar um aplicativo no Facebook e, depois, “conectá-lo” a uma (ou mais) página(s). Para cada página que este aplicativo for conectado, ele terá um token de acesso e através dele o aplicativo poderá enviar e receber as mensagens das conversas do Messenger daquela página.

Do ponto de vista do servidor do chatbot, não há limite de mensagens, ou seja, o Facebook garante que irá enviar todas as mensagens das conversas para o nosso aplicativo, e fica por nossa conta lidar com esse volume. Mas o caminho contrário é limitado, ou seja, nosso aplicativo só pode enviar um número limitado de mensagens por segundo, em resposta, para cada página.

Inicialmente, os tokens de acesso tinham um limite de 300 mensagens por segundo, ou seja, um aplicativo poderia mandar no máximo 300 mensagens para o Messenger de cada página, por segundo. Em geral este é um limite bem generoso, especialmente pensando na característica original do Messenger, que é baseado em conversas um-para-um, ou seja, cada usuário conversa individualmente com a página e a página responde diretamente para o usuário. Um limite de 300 mensagens por segundo permite, teoricamente, um máximo de 25.920.000 de mensagens por dia. Lembrando que seriam apenas as 25 milhões de respostas do nosso aplicativo às outras potenciais 25 milhões de mensagens enviadas pelos usuários para a página.

Novamente, é um volume bem confortável considerando: o número médio de seguidores das páginas, o percentual deles que efetivamente se comunica com a página através do Messenger, e a quantidade média de mensagens por sessão conversa.

Mas para a proposta do ChatClub, nós esbarramos rapidamente neste limite.

O Messenger não possui uma função de grupo de conversa, nem uma função de broadcast, então, para criar o efeito de sala de conversa, o ChatClub precisa mediar cada conversa entre o usuário e a página e replicar as mensagens para todas as outras conversas da mesma “sala”. Isso quer dizer que em uma “sala” com 100 pessoas, quando alguém novo chega e envia “oi”, o ChatClub precisa enviar “oi” para as outras 100 pessoas, em 100 mensagens (chamadas na API) diferentes. E se 3 pessoas falarem qualquer coisa no mesmo segundo, nós já atingiremos o limite de 300 mensagens desta página para este segundo.

Ver também: Referência da API de Envio > Limites de volume

Arquitetura básica do ChatClub

Inicialmente a arquitetura de módulos do ChatClub era bem simples:

As mensagens enviadas pelos usuários chegavam do Facebook no módulo configurado como “Webhook”, e a função deste módulo era simplesmente receber cada mensagem, enviá-la para uma fila, e confirmar o mais rapidamente possível para o Facebook o sucesso da operação.

Consumindo as mensagens desta fila de entrada, temos o módulo “Core”, que faz todos os tratamentos necessários, como identificação dos usuários, manutenção das sessões de conversa, e preparação das mensagens de resposta, incluindo o efeito multiplicativo de mensagens (fan-out) nos casos das salas de conversa em grupo. As mensagens de resposta são então encaminhadas para uma fila de saída.

Já as mensagens da fila de saída são consumidas pelo módulo “Dispatcher” que tem como função apenas enviar cada mensagem de volta ao Facebook.

Os módulos foram desacoplados através das filas intermediárias para que pudéssemos escalá-los individualmente de acordo com a necessidade, bem como isolarmos as características específicas de cada um. O problema de controle de vazão, por exemplo, foi tratado apenas no “Dispatcher”, e os outros módulos não foram afetados.

Estratégias disponíveis

Sempre que se trata de controle de vazão, a primeira técnica mencionada é o Leaky Bucket ou Token Bucket.

Basicamente, o algoritmo mantém um acumulador limitado ao valor correspondente à velocidade máxima de transações que se quer permitir. A cada transação, o sistema deve descontar uma unidade deste acumulador. Se a quantidade chegar a zero, a transação deve esperar até a próxima recarga do acumulador, que é recarregado para seu valor máximo a cada unidade de tempo.

No nosso caso, por exemplo, o acumulador seria limitado a 300 unidades, e recarregado com mais 300 (limitado ao saldo máximo de 300) a cada segundo.

Existem diferentes implementações prontas deste algoritmo, incluindo diferentes variações, que permitem maior ou menor controle do efeito final (por exemplo, atenuando rajadas nas recargas, e usando diferentes mecanismos de sincronização e controle).

O problema é que as implementações deste algoritmo normalmente são projetadas para funcionarem dentro de um único processo, num único servidor, mas o módulo Dispatcher do ChatClub era escalado sob demanda em múltiplos servidores. Isso quer dizer que nenhuma implementação disponível nos atendia.

Uma primeira solução seria simplesmente distribuir a vazão pelo número de servidores em uso no momento, por exemplo: se tivéssemos apenas um servidor, ele teria 300 chamadas por segundo disponíveis, mas se escalarmos para dois servidores, cada um teria 150 chamadas por segundo, e assim por diante.

Essa não seria uma solução completamente ruim se o ChatClub estivesse conectado à apenas uma página, pois assim todo tráfego dos servidores seria quase homogêneo. No exemplo de dois servidores, mesmo que o primeiro servidor tivesse alguma lentidão e não chegasse a usar toda sua capacidade de 150 chamadas/segundo, o outro poderia eventualmente atingir suas 150 e o resultado ainda seria próximo do máximo.

Mas no caso do ChatClub, que tem milhares de páginas conectadas, os Dispatchers consomem as mensagens da fila de saída conforme têm disponibilidade. E como as mensagens das diferentes páginas não são uniformemente distribuídas na fila de saída, a chance de cada servidor não atingir o máximo de sua cota de cada página é bem maior. Isso geraria desperdício de recursos, exigindo que tivéssemos muitos mais servidores para explorar toda a cota de cada página.

Como alternativa, ainda contando com a estratégia local de leaky bucket, poderíamos fixar páginas a determinados Dispatchers, ou seja, o tráfego de uma determinada página sairia exclusivamente por uma ou por outra instância de Dispatcher, e isso permitiria que ela controlasse efetivamente a vazão das chamadas.

Esta alternativa também não seria interessante porque exigiria que criássemos filas separadas por página (para garantirmos que cada Dispatcher atendesse apenas as mensagens das páginas sob sua responsabilidade) e balanceássemos as filas entre os Dispatchers. Se não fosse dessa forma, poderíamos ter Dispatchers responsáveis por páginas pouco movimentadas, que ficariam ociosos, e outros por páginas muito movimentadas que nunca alcançariam sua vazão máxima. De qualquer forma, haveria novamente desperdício da capacidade da infraestrutura, bem como um aumento no nosso esforço de gerenciamento.

Seria uma opção implementar uma versão distribuída do leaky bucket?

Nós chegamos a cogitar a possibilidade, essencialmente movendo o acumulador para algum serviço remoto, como um Redis ou Hazelcast, e apontando todos os Dispatchers para este serviço.

Esbarramos então, na questão de que não teríamos apenas um único acumulador, mas um para cada página, e que o tempo de recarga dos buckets deve ser de um segundo. Caso usássemos um cluster de Hazelcast, teríamos um alto volume de sincronizações entre os nós, e de qualquer forma, um alto volume de requisições de tokens (fossem no Redis ou Hazelcast).

As latências das requisições dos tokens se somariam ao tempo normal de entrega das mensagens, e talvez precisássemos de ainda mais capacidade de infraestrutura. Poderíamos aumentar a complexidade do nosso sistema criando buckets locais que pré-carregariam os tokens dos acumuladores remotos, mas isso teria mais ou menos o mesmo efeito de distribuir igualmente os tokens entre os servidores e resultaria num desperdício de recursos da mesma forma (sem contar que a complexidade geral aumentaria, tanto para monitorar quanto para garantir a corretude da implementação).

Poderíamos usar algum gerenciador de locks e estados compartilhados, como o ZooKeeper mas novamente a complexidade geral aumentaria, bem como a exigência de infraestrutura. Outro fator contra a adoção do ZooKeeper (ou equivalente) é que não é recomendado para usos com alto volume de alterações:

ZooKeeper is fast. It is especially fast in “read-dominant” workloads. ZooKeeper applications run on thousands of machines, and it performs best where reads are more common than writes, at ratios of around 10:1.

Alguns serviços online e alguns outros projetos open source aparecem para resolver o problema, mas não chegamos a fazer testes com eles:

Nós procurávamos uma solução simples, que não introduzisse muita complexidade no projeto, nem muitas novas dependências, nem demandasse novos recursos de infraestrutura, nem exigisse muita configuração.

Foi então que pensamos: “o Facebook já controla a vazão da API, ele já trata a granularidade por página e já nos informa quando excedemos a velocidade, então ele que controle isso pra gente!

Solução adotada

documentação do Facebook em prevê o código de erro 613 para a excedente no limite de uso da API:

Erros de limitação:

Uma vez que sabíamos quando uma página havia excedido seu limite naquele segundo, pudemos implementar uma solução local a cada Dispatcher, como um mapa de excedentes. O algoritmo básico funciona assim **:

  1. O Dispatcher busca a próxima mensagem na fila de envios
  2. Ele consulta no mapa de excedentes se esta mensagem é para uma página que já excedeu seu limite naquele segundo
  3. Se a página estiver no mapa de excedentes, ele devolve a mensagem para a fila e busca a próxima e, se não estiver no mapa, tenta enviar a mensagem.
  4. Se a mensagem foi enviada com sucesso, atende a próxima da fila.
  5. Se a mensagem recebeu erro 613, inclui a página no mapa de excedentes e tenta enviá-la novamente (até conseguir ou o erro não ser mais 613).
  6. Quando conseguir enviá-la, remove a página do mapa de excedentes.

[** o módulo do Dispatcher é baseado em threads e, portanto, este algoritmo é executado em cada thread. Assim, no passo 5, quando uma thread ficar no laço de reenvio, apenas esta thread ficará em loop, e as outras continuarão seguindo normalmente.]

Esta implementação permite que cada Dispatcher explore o quanto puder da API do Facebook, pause o atendimento de uma página imediatamente ao primeiro erro de limite, ou seja, maximizamos nossa capacidade de envio e minimizamos os erros e o desperdício de recursos. E tudo isso, sem precisar de comunicação entre os Dispatchers.

Minimizar a taxa de erros é importante não só para reduzirmos nosso consumo de recursos com tentativas que falham, mas também porque o Facebook pode bloquear sua aplicação se ela apresentar muitos erros em uma pequena faixa de tempo.

Resultados

Nossa solução simples mostrou bons resultados: nós conseguimos manter nossa taxa de erros controlada (muito abaixo do limite de bloqueio do Facebook), e também conseguimos manter nossa taxa de envio próxima do máximo permitido.

Nós inclusive comprovamos que o problema de controle de vazão distribuído não é complicado apenas para o nosso projeto, ele é complicado para todo mundo. Durante a implementação, observamos que em alguns segundos, em algumas oportunidades, nós excedemos a vazão permitida pelo Facebook, enviando com sucesso mais mensagens do que ele permitiria.

O gráfico a seguir mostra um desses casos: o fluxo de mensagens estava ao redor, mas abaixo dos 300 msg/s, mas em alguns momentos excedeu um pouco o limite permitido.

Numa avaliação geral, nossa implementação foi bem-sucedida, mas não sem apresentar um ou dois efeitos colaterais também.

O primeiro efeito, que já havíamos previsto, mas decidimos pôr à prova antes de mitigá-lo, era a possibilidade de muitas threads ficarem bloqueadas no laço de reenvio. Cada Dispatcher é criado com um conjunto finito de threads de trabalho e cada uma delas segue o algoritmo proposto: retira mensagem da fila, verifica o mapa de excedentes, tenta enviar, re-tenta em caso de erro, etc.

Se muitas páginas chegassem ao limite ao mesmo tempo, ou em um curto período, muitas threads do Dispatcher (potencialmente todas) ficariam no laço de reenvio e ele deixaria de atender às outras páginas normais com tráfego dentro do limite.

Nossa aposta era de que essa coincidência não seria frequente, e também, de que mesmo que várias threads ficassem bloqueadas, elas acabariam sendo liberadas no segundo seguinte. Não seria uma parada definitiva na operação, mas apenas uma pausa ocasional naquele Dispatcher.

O que observamos em produção é que, graças à distribuição heterogênea das mensagens na fila de mensagens de saída, poucas ficam realmente bloqueadas nos Dispatchers. De qualquer forma, caso observássemos que as páginas estavam enviando volumes maciços de mensagens, suficientes para bloquear a maioria das threads, ainda teríamos como contenção simplesmente escalar mais Dispatchers, pois o volume de mensagens seria mesmo relevante no contexto e justificaria a operação.

O segundo efeito, este inesperado, mas observado já nos testes iniciais, foi um efeito de starvation de múltiplas threads em espera.

Devido ao paralelismo das threads que consomem a fila de saída, múltiplas mensagens estão “em processamento” (ou in-flight) ao mesmo tempo. Supondo que uma determinada página tenha muitas mensagens em processamento ao mesmo tempo, a primeira thread que receber o erro 613 irá sinalizar a página no mapa de excedentes e as threads subsequentes irão obedecer a regra determinada. Mas para todas as outras threads que também estivessem processando mensagens da mesma página já seria tarde demais, e todas elas também ficariam no laço de reenvio.

O problema acontecia quando uma thread tinha sucesso em enviar sua mensagem e retirava a página do mapa de excedentes. Imediatamente threads novas voltariam a tratar as mensagens da página, e as outras threads que estavam em espera das suas respostas entravam na fila de escalonamento, e dependendo da velocidade geral, podiam voltar a ser bloqueadas antes de conseguirem enviar suas mensagens.

A solução para esse efeito foi colocar no mapa de excedentes um contador. Agora quando a página é colocada no mapa de excedentes e cada nova thread in-flight que receber o erro 613, o contador será acrescido.

Enquanto a página estiver no mapa e enquanto o contador for maior que zero, nenhuma nova thread tratará mensagens desta página. Quando a vazão for novamente liberada e as threads que estiverem no laço de reenvio conseguirem enviar suas mensagens, o contador será decrementado, e só quando chegar a zero a página será removida do mapa e novas threads buscarão as novas mensagens.

Comentários finais

Até o momento a solução de controle de vazão tem se mostrado suficiente para a demanda da plataforma, e foi claramente mais simples de desenvolver, manter e adaptar do que as outras opções que analisamos.

Vale comentar também que parte do efeito de fan-out, ou multiplicador, das mensagens, também foi controlado pela limitação do número de pessoas nas salas de conversa. Como no exemplo original, numa sala com 100 pessoas, cada mensagem é replicada 100 vezes e, em uma sala maior com 500 pessoas, a multiplicação seria de 500 vezes.

Mas observamos que nenhuma conversa razoável consegue ser sustentada numa sala com tantas pessoas, então acabamos limitando as salas à 100 pessoas no máximo. A limitação do fan-out também contribuiu diretamente para a moderação dos eventos de pico na plataforma e, para que pudéssemos atender mais pessoas nos bate-papos, nos obrigou a encontrar estratégias como o oferecimento de múltiplas salas, controles de tempo de inatividade, e algumas coisas mais, mas que ficam para outro artigo.

Posted by:Matheus Fonseca

2 replies on “Uma Abordagem Oportunista para Controle de Vazão Distribuído

Deixe seu comentário