Nossos usuários escrevem mensagens uns para os outros sem se cansarem.
Isso é bastante. Se você se propusesse a ler todas as mensagens de todos os usuários, levaria mais de 150 mil anos. Desde que você seja um leitor bastante avançado e não gaste mais do que um segundo em cada mensagem.
Com tamanho volume de dados, é fundamental que a lógica para armazená-los e acessá-los seja construída de forma otimizada. Caso contrário, num momento não tão maravilhoso, pode ficar claro que em breve tudo dará errado.
Para nós, esse momento chegou há um ano e meio. Como chegamos a isso e o que aconteceu no final - contamos em ordem.
Fundo
Na primeira implementação, as mensagens do VKontakte funcionavam em uma combinação de backend PHP e MySQL. Esta é uma solução completamente normal para um site de pequeno estudante. Porém, este site cresceu descontroladamente e passou a exigir para si otimização de estruturas de dados.
No final de 2009, o primeiro repositório de mecanismo de texto foi escrito e, em 2010, as mensagens foram transferidas para ele.
No mecanismo de texto, as mensagens eram armazenadas em listas – uma espécie de “caixas de correio”. Cada lista é determinada por um uid - o usuário que possui todas essas mensagens. Uma mensagem possui um conjunto de atributos: identificador do interlocutor, texto, anexos e assim por diante. O identificador da mensagem dentro da “caixa” é local_id, ele nunca muda e é atribuído sequencialmente para novas mensagens. As “caixas” são independentes e não estão sincronizadas entre si dentro do motor; a comunicação entre elas ocorre no nível do PHP. Você pode observar a estrutura de dados e os recursos do mecanismo de texto por dentro .
Isso foi suficiente para a correspondência entre dois usuários. Adivinhe o que aconteceu a seguir?
Em maio de 2011, o VKontakte introduziu conversas com vários participantes – multi-chat. Para trabalhar com eles, criamos dois novos clusters - chats de membros e membros de chat. O primeiro armazena dados sobre chats por usuários, o segundo armazena dados sobre usuários por chats. Além das próprias listas, isso inclui, por exemplo, o usuário que convidou e o horário em que ele foi adicionado ao chat.
“PHP, vamos mandar uma mensagem para o chat”, diz o usuário.
“Vamos, {username}”, diz PHP.
Existem desvantagens neste esquema. A sincronização ainda é responsabilidade do PHP. Grandes bate-papos e usuários que enviam mensagens simultaneamente para eles são uma história perigosa. Como a instância do mecanismo de texto depende do uid, os participantes do chat podem receber a mesma mensagem em momentos diferentes. Poderíamos conviver com isso se o progresso parasse. Mas isso não acontecerá.
No final de 2015, lançamos mensagens comunitárias e, no início de 2016, lançamos uma API para elas. Com o advento dos grandes chatbots nas comunidades, foi possível esquecer a distribuição uniforme da carga.
Um bom bot gera vários milhões de mensagens por dia - mesmo os usuários mais falantes não podem se orgulhar disso. Isso significa que algumas instâncias do mecanismo de texto em que viviam esses bots começaram a sofrer ao máximo.
Os mecanismos de mensagens em 2016 são 100 instâncias de chat-membros e chats de membros e 8000 mecanismos de texto. Eles foram hospedados em mil servidores, cada um com 64 GB de memória. Como primeira medida de emergência, aumentamos a memória em mais 32 GB. Estimamos as previsões. Sem mudanças drásticas, isso seria suficiente por mais um ano. Você precisa adquirir hardware ou otimizar os próprios bancos de dados.
Devido à natureza da arquitetura, só faz sentido aumentar o hardware em múltiplos. Ou seja, pelo menos dobrar o número de carros - obviamente, esse é um caminho bastante caro. Vamos otimizar.
Novo conceito
A essência central da nova abordagem é o chat. Um bate-papo possui uma lista de mensagens relacionadas a ele. O usuário tem uma lista de chats.
O mínimo exigido são dois novos bancos de dados:
- mecanismo de bate-papo. Este é um repositório de vetores de bate-papo. Cada chat possui um vetor de mensagens relacionadas a ele. Cada mensagem possui um texto e um identificador de mensagem exclusivo dentro do chat - chat_local_id.
- mecanismo do usuário. Este é um armazenamento de vetores de usuários - links para usuários. Cada usuário possui um vetor de peer_id (interlocutores - outros usuários, multi-chat ou comunidades) e um vetor de mensagens. Cada peer_id possui um vetor de mensagens relacionadas a ele. Cada mensagem possui um chat_local_id e um ID de mensagem exclusivo para esse usuário - user_local_id.
Novos clusters se comunicam entre si usando TCP – isso garante que a ordem das solicitações não mude. As próprias solicitações e suas confirmações são registradas no disco rígido - para que possamos restaurar o estado da fila a qualquer momento após uma falha ou reinicialização do motor. Como o mecanismo do usuário e o mecanismo de bate-papo têm 4 mil fragmentos cada, a fila de solicitações entre os clusters será distribuída uniformemente (mas na realidade não há nenhuma - e funciona muito rapidamente).
Trabalhar com disco em nossos bancos de dados, na maioria dos casos, é baseado em uma combinação de um log binário de alterações (binlog), instantâneos estáticos e uma imagem parcial na memória. As alterações durante o dia são gravadas em um log binário e um instantâneo do estado atual é criado periodicamente. Um snapshot é uma coleção de estruturas de dados otimizadas para nossos propósitos. Consiste em um cabeçalho (metaindex da imagem) e um conjunto de metarquivos. O cabeçalho é armazenado permanentemente na RAM e indica onde procurar os dados do instantâneo. Cada metarquivo inclui dados que provavelmente serão necessários em momentos próximos — por exemplo, relacionados a um único usuário. Ao consultar o banco de dados usando o cabeçalho do instantâneo, o metarquivo necessário é lido e, em seguida, as alterações no log binário que ocorreram após a criação do instantâneo são levadas em consideração. Você pode ler mais sobre os benefícios desta abordagem .
Ao mesmo tempo, os dados no próprio disco rígido mudam apenas uma vez por dia - tarde da noite em Moscou, quando a carga é mínima. Graças a isso (sabendo que a estrutura do disco é constante ao longo do dia), podemos substituir vetores por arrays de tamanho fixo - e com isso, ganhar memória.
O envio de uma mensagem no novo esquema fica assim:
- O back-end do PHP entra em contato com o mecanismo do usuário com uma solicitação para enviar uma mensagem.
- user-engine faz proxy da solicitação para a instância desejada do chat-engine, que retorna para user-engine chat_local_id - um identificador exclusivo de uma nova mensagem dentro deste chat. O chat_engine então transmite a mensagem para todos os destinatários do chat.
- user-engine recebe chat_local_id do chat-engine e retorna user_local_id para PHP - um identificador de mensagem exclusivo para este usuário. Este identificador é então utilizado, por exemplo, para trabalhar com mensagens através da API.
Mas além de realmente enviar mensagens, você precisa implementar mais algumas coisas importantes:
- As sublistas são, por exemplo, as mensagens mais recentes que você vê ao abrir a lista de conversas. Mensagens não lidas, mensagens com tags (“Importante”, “Spam”, etc.).
- Compactando mensagens no mecanismo de chat
- Armazenando mensagens em cache no mecanismo do usuário
- Pesquise (em todas as caixas de diálogo e em uma caixa específica).
- Atualização em tempo real (Longpolling).
- Salvando histórico para implementar cache em clientes móveis.
Todas as sublistas são estruturas que mudam rapidamente. Para trabalhar com eles usamos . Essa escolha é explicada pelo fato de que às vezes armazenamos um segmento inteiro de mensagens de um instantâneo no topo da árvore - por exemplo, após a reindexação noturna, a árvore consiste em um topo que contém todas as mensagens da sublista. A árvore Splay facilita a inserção no meio de tal vértice sem ter que pensar em balanceamento. Além disso, o Splay não armazena dados desnecessários, o que economiza memória.
As mensagens envolvem uma grande quantidade de informações, principalmente texto, que é útil poder compactar. É importante que possamos desarquivar com precisão até mesmo uma mensagem individual. Usado para compactar mensagens com nossas próprias heurísticas - por exemplo, sabemos que nas mensagens as palavras se alternam com “não-palavras” - espaços, sinais de pontuação - e também lembramos algumas peculiaridades do uso de símbolos para a língua russa.
Como há muito menos usuários do que chats, para salvar solicitações de disco de acesso aleatório no mecanismo de chat, armazenamos mensagens em cache no mecanismo do usuário.
A pesquisa de mensagens é implementada como uma consulta diagonal do mecanismo do usuário para todas as instâncias do mecanismo de bate-papo que contêm bate-papos desse usuário. Os resultados são combinados no próprio mecanismo do usuário.
Pois bem, todos os detalhes foram levados em consideração, só falta mudar para um novo esquema – e de preferência sem que os usuários percebam.
Migração de dados
Portanto, temos um mecanismo de texto que armazena mensagens por usuário e dois clusters de membros de chat e chats de membros que armazenam dados sobre salas de chat múltiplas e os usuários nelas. Como passar disso para o novo mecanismo de usuário e mecanismo de chat?
member-chats no esquema antigo era usado principalmente para otimização. Rapidamente transferimos os dados necessários para os membros do chat e então ele não participou mais do processo de migração.
Fila para membros do chat. Inclui 100 instâncias, enquanto o chat-engine possui 4 mil. Para transferir os dados, é necessário colocá-los em conformidade - para isso, os membros do chat foram divididos nas mesmas 4 mil cópias, e então a leitura do binlog dos membros do chat foi habilitada no mecanismo de chat.
Agora o chat-engine conhece o multi-chat dos membros do chat, mas ainda não sabe nada sobre os diálogos com dois interlocutores. Tais diálogos estão localizados no mecanismo de texto com referência aos usuários. Aqui analisamos os dados “de frente”: cada instância do mecanismo de chat perguntou a todas as instâncias do mecanismo de texto se elas tinham o diálogo necessário.
Ótimo - o mecanismo de chat sabe quais chats multi-chat existem e quais diálogos existem.
Você precisa combinar mensagens em bate-papos com vários bate-papos para obter uma lista de mensagens em cada bate-papo. Primeiro, o chat-engine recupera do text-engine todas as mensagens do usuário deste chat. Em alguns casos, existem muitos deles (até centenas de milhões), mas com raríssimas exceções o chat cabe inteiramente na RAM. Temos mensagens não ordenadas, cada uma em várias cópias - afinal, todas elas são extraídas de diferentes instâncias do mecanismo de texto correspondentes aos usuários. O objetivo é classificar as mensagens e livrar-se de cópias que ocupam espaço desnecessário.
Cada mensagem possui um carimbo de data/hora contendo a hora em que foi enviada e o texto. Usamos o tempo para classificação - colocamos ponteiros para as mensagens mais antigas dos participantes do multichat e comparamos os hashes do texto das cópias pretendidas, avançando no sentido de aumentar o carimbo de data / hora. É lógico que as cópias terão o mesmo hash e timestamp, mas na prática nem sempre é assim. Como você lembra, a sincronização no esquema antigo era feita por PHP - e em casos raros, o tempo de envio da mesma mensagem diferia entre diferentes usuários. Nesses casos, nos permitimos editar o carimbo de data/hora - geralmente em um segundo. O segundo problema é a ordem diferente das mensagens para destinatários diferentes. Nesses casos, permitimos a criação de uma cópia extra, com diferentes opções de ordenação para diferentes usuários.
Depois disso, os dados sobre as mensagens no multichat são enviados para o mecanismo do usuário. E aí vem um recurso desagradável das mensagens importadas. Na operação normal, as mensagens que chegam ao mecanismo são ordenadas estritamente em ordem crescente por user_local_id. As mensagens importadas do mecanismo antigo para o mecanismo do usuário perderam essa propriedade útil. Ao mesmo tempo, para a comodidade do teste, você precisa poder acessá-los rapidamente, procurar algo neles e adicionar novos.
Usamos uma estrutura de dados especial para armazenar mensagens importadas.
Representa um vetor de tamanho onde está todo mundo - são diferentes e ordenados em ordem decrescente, com uma ordem especial de elementos. Em cada segmento com índices os elementos são classificados. Procurar um elemento em tal estrutura leva tempo através pesquisas binárias. A adição de um elemento é amortizada ao longo .
Então, descobrimos como transferir dados de motores antigos para novos. Mas esse processo leva vários dias - e é improvável que durante esses dias nossos usuários abandonem o hábito de escrever uns para os outros. Para não perder mensagens durante esse período, mudamos para um esquema de trabalho que utiliza clusters antigos e novos.
Os dados são gravados nos membros do chat e no mecanismo do usuário (e não no mecanismo de texto, como na operação normal de acordo com o esquema antigo). o mecanismo do usuário faz proxy da solicitação para o mecanismo de bate-papo - e aqui o comportamento depende se esse bate-papo já foi mesclado ou não. Se o chat ainda não foi mesclado, o mecanismo de chat não grava a mensagem para si mesmo e seu processamento ocorre apenas no mecanismo de texto. Se o chat já tiver sido mesclado no chat-engine, ele retornará chat_local_id ao user-engine e enviará a mensagem a todos os destinatários. O mecanismo do usuário faz proxy de todos os dados para o mecanismo de texto - para que, se algo acontecer, possamos sempre reverter, tendo todos os dados atuais no mecanismo antigo. o mecanismo de texto retorna user_local_id, que o mecanismo do usuário armazena e retorna ao back-end.
Como resultado, o processo de transição é assim: conectamos clusters vazios de mecanismo de usuário e mecanismo de chat. O chat-engine lê todo o log binário dos membros do chat e, em seguida, o proxy é iniciado de acordo com o esquema descrito acima. Transferimos os dados antigos e obtemos dois clusters sincronizados (antigo e novo). Tudo o que resta é mudar a leitura do mecanismo de texto para o mecanismo do usuário e desativar o proxy.
Descobertas
Graças à nova abordagem, todas as métricas de desempenho dos motores foram melhoradas e os problemas de consistência dos dados foram resolvidos. Agora podemos implementar rapidamente novos recursos nas mensagens (e já começamos a fazer isso - aumentamos o número máximo de participantes do chat, implementamos uma busca por mensagens encaminhadas, lançamos mensagens fixadas e aumentamos o limite do número total de mensagens por usuário) .
As mudanças na lógica são realmente enormes. E gostaria de observar que isso nem sempre significa anos inteiros de desenvolvimento por uma equipe enorme e inúmeras linhas de código. mecanismo de bate-papo e mecanismo de usuário, juntamente com todas as histórias adicionais, como Huffman para compactação de mensagens, árvores Splay e estrutura para mensagens importadas, tem menos de 20 mil linhas de código. E foram escritos por 3 desenvolvedores em apenas 10 meses (no entanto, vale a pena ter em mente que - campeões mundiais ).
Além disso, em vez de duplicar o número de servidores, reduzimos o seu número para metade - agora o motor do utilizador e o motor de chat funcionam em 500 máquinas físicas, enquanto o novo esquema tem uma grande margem de carga. Economizamos muito dinheiro em equipamentos – cerca de US$ 5 milhões + US$ 750 mil por ano em despesas operacionais.
Nós nos esforçamos para encontrar as melhores soluções para os problemas mais complexos e de grande escala. Temos muitos deles - e é por isso que procuramos desenvolvedores talentosos no departamento de banco de dados. Se você adora e sabe resolver esses problemas, possui um excelente conhecimento de algoritmos e estruturas de dados, convidamos você a fazer parte da equipe. Entre em contato com nosso para detalhes.
Mesmo que esta história não seja sobre você, observe que valorizamos recomendações. Conte a um amigo sobre , e se ele concluir com êxito o período probatório, você receberá um bônus de 100 mil rublos.
Fonte: habr.com