Cinco alunos e três lojas de valores-chave distribuídos

Ou, como escrevemos a biblioteca C ++ do cliente para o ZooKeeper, etcd e Consul KV

No mundo dos sistemas distribuídos, existem várias tarefas típicas: armazenar informações sobre a composição do cluster, gerenciar a configuração de nós, detectar nós com falha, escolher um líder e outros . Para resolver esses problemas, foram criados sistemas distribuídos especiais - serviços de coordenação. Agora estaremos interessados ​​em três deles: ZooKeeper, etcd e Consul. De toda a rica funcionalidade do Consul, vamos nos concentrar no Consul KV.



De fato, todos esses sistemas são armazenamentos de valores-chave linearizados e tolerantes a falhas. Embora seus modelos de dados tenham diferenças significativas, que discutiremos mais adiante, eles nos permitem resolver os mesmos problemas práticos. Obviamente, cada aplicativo que usa o serviço de coordenação está vinculado a um deles, o que pode levar à necessidade de oferecer suporte a vários sistemas que resolvem as mesmas tarefas em um datacenter para aplicativos diferentes.

A idéia, projetada para resolver esse problema, teve origem em uma agência de consultoria australiana e nós, uma pequena equipe de estudantes, tivemos que implementá-la, sobre a qual vou falar.

Conseguimos criar uma biblioteca que fornece uma interface comum para trabalhar com o ZooKeeper, etcd e o Consul KV. A biblioteca é escrita em C ++, mas há planos para portar para outros idiomas.

Modelos de dados

Para desenvolver uma interface comum para três sistemas diferentes, você precisa entender o que eles têm em comum e como eles diferem. Vamos acertar.

Zookeeper



As chaves são organizadas em uma árvore e são chamadas de nós (znodes). Assim, para o site você pode obter uma lista de seus filhos. As operações de criação do znode (create) e alteração do valor (setData) são separadas: somente as chaves existentes podem ler e alterar valores. Os relógios podem ser anexados às operações de verificar a existência de um nó, ler um valor e obter filhos. O Watch é um acionador único que é acionado quando a versão dos dados correspondentes no servidor é alterada. Nós efêmeros são usados ​​para detectar falhas. Eles são anexados à sessão do cliente que os criou. Quando um cliente fecha uma sessão ou para de notificar o ZooKeeper sobre sua existência, esses nós são excluídos automaticamente. Transações simples são suportadas - um conjunto de operações com êxito ou com falha, se pelo menos uma delas for impossível.

etcd



Os desenvolvedores deste sistema foram claramente inspirados pelo ZooKeeper e, portanto, fizeram tudo de maneira diferente. A hierarquia de chaves não está aqui, mas elas formam um conjunto lexicograficamente ordenado. Você pode obter ou excluir todas as chaves que pertencem a um determinado intervalo. Essa estrutura pode parecer estranha, mas na verdade é muito expressiva, e a visão hierárquica através dela é facilmente imitada.

Não há operação padrão de comparação e configuração no etcd, mas há algo melhor - transações. Obviamente, eles estão nos três sistemas, mas nas transações etcd são especialmente boas. Eles consistem em três blocos: verificação, sucesso, falha. O primeiro bloco contém um conjunto de condições, a segunda e a terceira - operações. Uma transação é realizada atomicamente. Se todas as condições forem verdadeiras, o bloco de sucesso será executado, caso contrário - falha. Na API versão 3.3, os blocos de sucesso e falha podem conter transações aninhadas. Ou seja, é possível executar atomicamente construções condicionais de um nível quase arbitrário de aninhamento. Você pode aprender mais sobre quais verificações e operações existem na documentação .

Os relógios também existem aqui, embora sejam um pouco mais complexos e reutilizáveis. Ou seja, depois de instalar o relógio em um intervalo de teclas, você receberá todas as atualizações nesse intervalo até cancelar o relógio, e não apenas o primeiro. No etcd, as concessões são equivalentes às sessões do cliente ZooKeeper.

Consul KV

Também não existe uma estrutura hierárquica rigorosa, mas o Consul pode criar a aparência que existe: você pode receber e excluir todas as chaves com o prefixo especificado, ou seja, trabalhar com a "subárvore" da chave. Tais consultas são chamadas recursivas. Além disso, o Consul pode selecionar apenas chaves que não contenham o caractere especificado após o prefixo, o que corresponde ao recebimento de “filhos” imediatos. Mas vale lembrar que essa é precisamente a aparência de uma estrutura hierárquica: é bem possível criar uma chave se seu pai não existir ou excluir uma chave que tenha filhos, enquanto os filhos continuarão sendo armazenados no sistema.


Em vez de relógios, existem solicitações HTTP de bloqueio no Consul. Em essência, são chamadas comuns ao método de leitura de dados, para as quais, juntamente com outros parâmetros, é indicada a última versão conhecida dos dados. Se a versão atual dos dados correspondentes no servidor for maior que a especificada, a resposta será retornada imediatamente, caso contrário, quando o valor for alterado. Também há sessões aqui que podem ser anexadas às chaves a qualquer momento. Vale ressaltar que, diferentemente do etcd e do ZooKeeper, onde a exclusão de sessões leva à remoção de chaves relacionadas, existe um modo em que a sessão é simplesmente desanexada delas. As transações estão disponíveis, sem ramificação, mas com todos os tipos de cheques.

Junte tudo

O modelo de dados mais rigoroso tem o ZooKeeper. Solicitações de intervalo expressivas disponíveis no etcd não podem ser emuladas de maneira eficiente no ZooKeeper ou no Consul. Tentando tirar o melhor de todos os serviços, obtivemos uma interface quase equivalente à interface do ZooKeeper, com as seguintes exceções significativas:

• sequência, contêiner e nós TTL não são suportados
• ACLs não são suportadas
• O método set cria uma chave se não existir (no ZK setData retorna um erro neste caso)
• Os métodos set e cas são separados (em ZK, eles são essencialmente a mesma coisa)
• O método apagar apaga o vértice junto com a subárvore (em ZK delete retorna um erro se o vértice tiver filhos)
• para cada chave, existe apenas uma versão - a versão do valor (em ZK, existem três )

A rejeição de nós seqüenciais se deve ao fato de que no etcd e Consul não há suporte interno para eles e, além da interface da biblioteca resultante, eles podem ser facilmente implementados pelo usuário.

A implementação do mesmo comportamento ao remover o ZooKeeper superior exigiria a manutenção de um contador filho separado no etcd e no Consul para cada chave. Como tentamos evitar o armazenamento de meta-informações, foi decidido excluir a subárvore inteira.

Sutilezas de implementação

Vamos considerar com mais detalhes alguns aspectos da implementação da interface da biblioteca em diferentes sistemas.

Hierarquia no etcd

Manter uma visão hierárquica no etcd foi uma das tarefas mais interessantes. As solicitações de intervalo facilitam a obtenção de uma lista de chaves com um prefixo especificado. Por exemplo, se você deseja tudo o que começa com "/foo" , solicita o intervalo ["/foo", "/fop") . Mas isso retornaria toda a subárvore inteira da chave, o que pode não ser aceitável se a subárvore for grande. Inicialmente, planejamos usar o mecanismo de conversão de chaves implementado no zetcd . Envolve adicionar um byte no início da chave, igual à profundidade do nó na árvore. Eu darei um exemplo

 "/foo" -> "\u01/foo" "/foo/bar" -> "\u02/foo/bar" 

Então você pode obter todos os filhos imediatos da chave "/foo" solicitando o intervalo ["\u02/foo/", "\u02/foo0") . Sim, em ASCII, "0" segue imediatamente "/" .

Mas como, então, excluir um vértice? Acontece que você precisa excluir todos os intervalos do formulário ["\uXX/foo/", "\uXX/foo0") para XX de 01 a FF. E, então, chegamos a um limite no número de operações em uma única transação.

Como resultado, um sistema simples de conversão de chaves foi inventado, o que nos permitiu implementar efetivamente a remoção da chave e o recebimento de uma lista de filhos. Basta adicionar um símbolo especial antes do último token. Por exemplo:

 "/very" -> "/\u00very" "/very/long" -> "/very/\u00long" "/very/long/path" -> "/very/long/\u00path" 

A exclusão da chave "/very" torna-se a exclusão de "/\u00very" e o intervalo ["/very/", "/very0") e ["/very/", "/very0") todos os filhos a uma solicitação de chaves do intervalo ["/very/\u00", "/very/\u01") .

Removendo uma chave no ZooKeeper

Como já mencionei, no ZooKeeper você não pode excluir um nó se ele tiver filhos. Queremos excluir a chave junto com a subárvore. Como ser Estamos fazendo isso de maneira otimista. Primeiro, percorremos recursivamente a subárvore, obtendo os filhos de cada vértice em uma consulta separada. Em seguida, criamos uma transação que tenta excluir todos os nós da subárvore na ordem correta. Obviamente, podem ocorrer alterações entre a leitura de uma subárvore e a exclusão. Nesse caso, a transação falhará. Além disso, a subárvore pode mudar durante o processo de leitura. Uma consulta para os filhos do próximo nó pode retornar um erro se, por exemplo, esse vértice já tiver sido excluído. Nos dois casos, repetimos todo o processo novamente.

Essa abordagem torna a exclusão de uma chave muito ineficaz se ela tiver filhos, e ainda mais se o aplicativo continuar trabalhando com a subárvore, excluindo e criando chaves. No entanto, isso nos permitiu não complicar a implementação de outros métodos no etcd e Consul.

definido no ZooKeeper

No ZooKeeper, existem métodos separados que trabalham com a estrutura em árvore (criar, excluir, getChildren) e que trabalham com dados em nós (setData, getData) Além disso, todos os métodos têm pré-condições estritas: create retornará um erro se o nó já estiver criado, excluído ou setData - se ainda não existir. Precisávamos do método set, que pode ser chamado sem pensar na chave.

Uma opção é aplicar uma abordagem otimista, como ao excluir. Verifique se o nó existe. Se existir, chame setData; caso contrário, crie. Se o último método retornou um erro, repita novamente. A primeira coisa a observar é a inutilidade de verificar a existência. Você pode ligar imediatamente para criar. A conclusão bem-sucedida significa que o nó não existia e foi criado. Caso contrário, create retornará o erro correspondente, após o qual setData deverá ser chamado. Obviamente, entre as chamadas, o vértice pode ser removido por uma chamada concorrente e setData também retornará um erro. Nesse caso, você pode repetir tudo novamente, mas vale a pena?

Se os dois métodos retornaram um erro, sabemos com certeza que houve uma exclusão concorrente. Imagine que essa exclusão ocorreu após chamar o conjunto. Então, não importa qual valor tentemos estabelecer, ele já será apagado. Portanto, você pode assumir que o conjunto foi bem-sucedido, mesmo que nada tenha sido escrito.

Mais detalhes técnicos

Nesta seção, discordamos de sistemas distribuídos e falamos sobre codificação.
Um dos principais requisitos do cliente era entre plataformas: no Linux, MacOS e Windows, pelo menos um dos serviços deve ser suportado. Inicialmente, realizamos o desenvolvimento apenas no Linux e, em outros sistemas, começamos a testar mais tarde. Isso causou muitos problemas, o que, por algum tempo, não ficou totalmente claro como abordar. Como resultado, todos os três serviços de coordenação agora são suportados no Linux e MacOS e apenas o Consul KV no Windows.

Desde o início, tentamos usar bibliotecas prontas para acessar serviços. No caso do ZooKeeper, a escolha caiu no ZooKeeper C ++ , que no final não pôde ser compilado no Windows. Isso, no entanto, não é surpreendente: a biblioteca está posicionada como somente linux. Para a Consul, a ppconsul era a única opção. Eu tive que adicionar suporte a sessões e transações a ele . Para o etcd, uma biblioteca completa que suporta a versão mais recente do protocolo nunca foi encontrada; portanto, apenas geramos um cliente grpc .

Inspirados na interface assíncrona da biblioteca ZooKeeper C ++, decidimos implementar a interface assíncrona também. No ZooKeeper C ++, primitivas futuras / promessas são usadas para isso. No STL, infelizmente, eles são implementados de maneira muito modesta. Por exemplo, não existe um método que aplique a função passada ao resultado futuro quando ela estiver disponível. No nosso caso, esse método é necessário para converter o resultado no formato da nossa biblioteca. Para contornar esse problema, tivemos que implementar nosso pool de encadeamentos simples, porque, a pedido do cliente, não podíamos usar bibliotecas pesadas de terceiros, como o Boost.

Nossa implementação então funciona da seguinte maneira. Quando chamado, um par adicional de promessa / futuro é criado. O novo futuro é retornado e o transferido é colocado junto com a função correspondente e uma promessa adicional na fila. Um encadeamento do pool seleciona vários futuros da fila e os pesquisa usando wait_for. Quando o resultado fica disponível, a função correspondente é chamada e seu valor de retorno é passado para a promessa.

Usamos o mesmo pool de threads para executar solicitações ao etcd e Consul. Isso significa que vários segmentos diferentes podem trabalhar com as bibliotecas subjacentes. O ppconsul não é seguro para threads, portanto, as chamadas para ele são protegidas por bloqueios.
Você pode trabalhar com o grpc a partir de vários threads, mas existem sutilezas. Os relógios Etcd são implementados por meio de fluxos grpc. Estes são canais bidirecionais para certos tipos de mensagens. A biblioteca cria um único fluxo para todos os relógios e um único fluxo que processa as mensagens recebidas. Então o grpc proíbe gravações paralelas para transmitir. Isso significa que, ao inicializar ou excluir o relógio, é necessário aguardar até que o envio da solicitação anterior seja concluído antes de enviar a próxima. Usamos variáveis ​​condicionais para sincronização.

Sumário

Veja você mesmo: liboffkv .

Nossa equipe: Raed Romanov , Ivan Glushenkov , Dmitry Kamaldinov , Victor Krapivensky e Vitaly Ivanin .