sincronia Virtual - Virtual synchrony

Sincronia virtual é uma mensagem entre processos passar (às vezes chamado ordenou, multicast confiável) tecnologia. Sistemas de sincronia virtuais permitem que os programas em execução em uma rede para organizar-se em grupos de processos , e para enviar mensagens para grupos (em oposição a enviá-los para processos específicos). Cada mensagem é entregue a todos os membros do grupo, na ordem idêntica, e isso é verdade mesmo quando duas mensagens são transmitidas simultaneamente por diferentes remetentes. Design da aplicação e implementação é bastante simplificada por esta propriedade: cada membro do grupo vê os mesmos eventos (alterações de membros de grupo e mensagens recebidas) na mesma ordem.

Um serviço praticamente síncrona é tipicamente implementado usando um estilo de programação chamada replicação máquina de estado , em que um serviço é implementado pela primeira vez usando um único programa que recebe entradas de clientes através de alguma forma de mensagem remoto passando infra-estrutura, em seguida, entra em um novo estado e responde em uma maneira determinista. A implementação inicial é então transformada para que várias instâncias do programa pode ser lançado em máquinas diferentes, usando uma mensagem de praticamente síncrona sistema passando para replicar as mensagens recebidas ao longo dos membros. As réplicas vai ver os mesmos eventos na mesma ordem, e são nos mesmos estados, daí eles vão fazer as mesmas transições de estado e permanecem em um estado consistente.

A replicação do serviço fornece uma forma de tolerância a falhas: se uma réplica falhar (por deixar de funcionar), os outros permanecem e podem continuar a fornecer respostas. Diferentes membros do grupo de réplica também pode ser programado para subdividir a carga de trabalho, normalmente usando a associação de grupo para determinar os seus respectivos papéis. Isso permite que um grupo de membros N para executar tanto como N vezes mais rápido do que um único membro, ou para lidar com N vezes como muitos pedidos, enquanto continua a oferecer tolerância a falhas em caso de acidente.

sincronia virtual se distingue de replicação máquina de estado clássica porque o modelo inclui funcionalidades em que um programador pode solicitar a entrega antecipada (otimista) de mensagens, ou formas descontraídas de pedidos. Quando utilizada apropriadamente, estas características podem permitir aumento de velocidade substancial. No entanto, o programador precisa ter certeza de que o relaxamento das garantias não irá comprometer a exatidão.

Por exemplo, em um serviço que utiliza bloqueio para proteger os dados simultaneamente atualizados, o sistema de mensagens pode ser instruído a usar uma forma barata de mensagem de encomenda, em que o sistema de mensagens respeite a ordem em que os remetentes individuais enviar mensagens (garantia FIFO), mas faz não tente impor uma ordem acordado se as mensagens são enviadas simultaneamente por diferentes remetentes. Desde que o remetente bloqueios sobre os dados de fato realizada, pode-se mostrar que FIFO ordenação é suficiente para a correção. A vantagem é que FIFO ordenação é muito menos dispendioso de implementar do que ordenação total das mensagens simultâneas.

Para dar outro exemplo, a entrega de mensagens de forma otimista, sistemas de sincronia virtuais podem superar os Paxos que é normalmente necessários para a implementação de replicação de máquina de estado: Paxos normalmente exige um protocolo de 2 fases, enquanto protocolos sincronia virtuais otimistas podem entregar mensagens imediatamente após a sua chegada. No entanto, isso poderia resultar em uma violação da propriedade de segurança do modelo de replicação máquina de estado. Para evitar tais problemas, o programador que usa este recurso é necessário para invocar um chamado primitivo nivelada , o que atrasa o chamador até que todas as mensagens otimista entregues atingiram todos os membros do grupo. Desde que o programador entende esse comportamento e tem o cuidado de chamar flush antes de interagir com os clientes externos ou armazenamento persistente, maior desempenho pode ser alcançado sem perda de segurança.

A flexibilidade associada a estas formas limitadas de evento reordenação e plataformas sincronia virtuais início licença entrega otimistas para alcançar taxas de dados extremamente altas e ainda preservar muito fortes garantias de tolerância a falhas e consistência.

Discussão detalhada

Sistemas informáticos distribuídos muitas vezes precisam de uma maneira de replicar os dados para a partilha entre os programas em execução em várias máquinas, ligados por uma rede. Sincronia virtual é uma das três principais tecnologias para resolver este problema. A ideia-chave é criar uma forma de distribuição máquina de estado associado ao item de dados replicados. Chamado de grupo de processo , estas máquinas de estado compartilhar cópias dos dados, e as atualizações são entregues como eventos que ocorrem na mesma ordem em todas as cópias. Se um processo falha ou falha, esta é relatado para os outros processos no grupo; se um processo junta-se, este é semelhante relatado, e uma transferência de estado é usado para inicializar o membro aderir. Um aplicativo com lotes de itens de dados para replicar pode fazê-lo usando um único grupo para o conjunto, ou pode criar grupos diferentes para diferentes itens, com a primeira abordagem usada quando os itens são replicadas nos locais idênticos, eo último sendo usada quando os padrões de replicação diferente.

Cada grupo de processo tem um nome, visível dentro da rede. Um programa único aplicativo pode se tornar um membro de vários grupos ao mesmo tempo. Com efeito, um grupo processo torna-se uma abstracção para partilha de dados, coordenar as acções, e monitorando outros processos. Nas bibliotecas de software mais amplamente utilizados para execução do modelo, sincronia virtual é tipicamente empregue dentro de objectos individuais, que são depois incorporados no código orientado objeto em linguagens como Java ou C #. Os próprios objectos actuar como uma unidade de replicação com propriedades sincronia virtuais.

O termo sincronia virtual refere-se ao fato de que as aplicações de ver evoluir os dados compartilhados no que parece ser uma forma síncrona. Esta forma de sincronização é virtual porque a situação real é mais complexo do que parece ser o caso da perspectiva de um programador. Como um compilador que às vezes reordena a execução de instruções para um desempenho superior, ou um sistema operacional que, por vezes, armazena memória de acesso aleatório no disco , sincronia virtual, por vezes, reordena eventos em maneiras que melhoram o desempenho, e ainda assim não será perceptível para os aplicativos.

Usando o modelo de sincronia virtual, é relativamente fácil de manter dados replicados tolerantes a falhas em um estado consistente. em seguida, pode-se construir abstrações de nível superior nos mecanismos de replicação básicas. Por exemplo, muitas bibliotecas sincronia virtuais também ferramentas de apoio para a construção de lojas de valor-chave distribuídos, replicação de arquivos externos ou bases de dados, bloqueio ou de outra forma coordenar as ações dos membros do grupo, etc.

replicação sincronia virtual é usado principalmente quando as aplicações são replicar informações que evolui muito rapidamente. Como discutido mais adiante, os tipos de aplicações que necessitam deste modelo incluem multiusuário role-playing games, sistemas de controle de tráfego aéreo, bolsas de valores, e interruptores de telecomunicações. Claro, existem outras maneiras de resolver os mesmos problemas. Por exemplo, a maioria dos on-line multi-utilizador role-playing games de hoje dar aos usuários uma sensação de que eles estão compartilhando dados replicados, mas na verdade os dados vive em um servidor em um centro de dados, e qualquer informação passa através dos centros de dados. Esses jogos provavelmente não iria usar modelos como sincronia virtual, no presente. No entanto, como eles empurram para taxas de dados cada vez maiores, levando o servidor para fora do caminho crítico de desempenho torna-se importante, e com este passo, modelos como sincronia virtual são potencialmente valiosa.

A tendência para a computação em nuvem aumentou o interesse na replicação estado consistente. Sistemas de computação em nuvem são grandes centros de dados virtualizados, operados por empresas de pesquisa de internet ou de comércio, tais como IBM, Microsoft, Google e Amazon. Dentro de uma plataforma de computação em nuvem se encontra serviços como sistemas de gerenciamento de bloqueio (Google é chamado Chubby e Yahoo! usa um chamado Zookeeper ), e estes são implementados usando sincronia virtual ou modelos intimamente relacionados. Outros serviços que podem ser implementadas usando sincronia virtual incluem as ferramentas de gerenciamento de cluster que relançar aplicações fracassou quando nós em um acidente aglomerado, ferramentas de notificação de eventos que informam aplicações quando ocorrem eventos significativos, e ferramentas de registro que ajudam uma aplicação salvar seu estado para reprodução durante a recuperação .

Três modelos distribuídos de replicação de dados

Virtual Synchrony é um modelo popular de computação, intimamente relacionado com o modelo serializability uma cópia transacional (usado principalmente em replicados sistemas de banco de dados ) ea máquina de estado modelo (consenso), também conhecida como " Paxos ", o nome dado ao mais citado implementação de estado da máquina.

  • Entre estes, a replicação transacional é provavelmente o modelo da maioria dos livros de banco de dados mais amplamente conhecidos discutir o assunto. No entanto, as despesas gerais são muito elevados quando se utiliza verdadeira serializability uma cópia, portanto, a abordagem à replicação nunca foi um sucesso comercial. Turing Award vencedor Jim Gray oferece algumas reflexões sobre esta questão em um artigo que ele escreveu sobre "Os perigos de replicação e uma solução" . Hoje, alguns produtos de banco de dados suportam a replicação verdadeira do tipo Grey adverte sobre. Em vez disso, eles fragmentar grandes bases de dados em que são chamados cacos, e muitas vezes eles relaxar consistência, oferecendo um chamado modelo NoSQL em vez do modelo de replicação completa ACID. O relaxamento resultante de consistência é adequada para alguns propósitos, mas os sistemas de computação de missão crítica muitas vezes precisam de garantias mais fortes.
  • Sincronia virtual oferece opções para manter a consistência nos níveis de desempenho mais elevados exigidos em ambientes exigentes. O modelo também foi padronizado como parte do CORBA modelo de referência, e é suportada por JGroups , uma parte da tecnologia JBoss amplamente utilizado. No entanto, as mesmas características que permitem estes altos níveis de desempenho também fazer sincronia virtual relativamente difícil de usar corretamente-programadores precisa de algum treinamento, e sem o cuidado adequado, correção de um serviço replicado pode ser afetado.
  • A máquina de estado / Paxos é utilizado num certo número de produtos comerciais que eléctricas de grande sistemas escaláveis, tais como carnudo , um serviço de bloqueio usados por aplicações Google. No entanto, Paxos pode ser lento e escalas mal, e como a sincronia virtual, pode ser bastante difícil de usar corretamente.

Replicação de dados e tolerância a falhas

O objectivo de base para todos estes protocolos é para replicar os dados em um sistema distribuído de uma maneira que faz com que a entidade replicado indistinguível de um objecto que não seja replicado implementar a mesma interface. Por exemplo, se imaginarmos uma simples variável, x , que pode ser lido ou escrito, uma versão replicado pode consistir de um conjunto de réplicas x 0 , x 1 , ... x n e um protocolo associado, de tal forma que lê e escreve às repetições são realizadas de uma forma que parece indistinguível de lê e escreve para a variável original. O desafio é lidar com casos em que várias atualizações são iniciadas simultaneamente (às vezes chamado de conflito de edição ), ou em que uma falha interrompe uma atualização enquanto ele ainda está em andamento. Quando criamos um grupo de processo, a idéia é que cada um de seus membros vai realizar uma réplica. As atualizações são entregues aos membros do grupo através de uma interface de notificação de eventos implementado de uma forma que elimina esses tipos de problemas.

A diferença fundamental entre os três modelos é que a sincronia virtuais assume que a variável é replicada na memória por um conjunto de processos executados em alguns conjunto de máquinas em uma rede. Transacional one-copy serializability assume que os dados residem em uma coleção de bancos de dados transacionais (no disco), e implementa as transacionais completos ACID propriedades, com o habitual begin / commit / abortar interface. Consenso Estado-máquina está em algum lugar no meio: as variáveis são consideradas persistente (por exemplo, eles podem ser armazenados em arquivos), mas não são assumidos ter propriedades ACID completos e acesso não é assumido que passar por um transacional começar / commit / abortar interface.

Nenhum dos três modelos é particularmente difícil de suportar em um sistema onde o conjunto de processos que participam é estável, e onde as mensagens são entregues de forma confiável. No entanto, em redes reais, os computadores podem falhar ou tornar-se desligado e as mensagens podem ser perdidos. A necessidade de preservar as propriedades do modelo ao mascarar falhas e mantém o alto desempenho é o que torna o problema de replicação de dados tão difícil.

Todos os três modelos assumem que as máquinas podem falhar por deixar de funcionar: um computador pára, ou algum processo em que pára, e outros processos sentir o fracasso por timeout. Timeout, é claro, é uma maneira potencialmente imprecisa de perceber falhas (timeouts sempre descobrir verdadeiros acidentes, mas às vezes um tempo limite irá disparar por alguma outra razão, como um problema de conectividade transitória.) Uma plataforma de implementação de qualquer um destes modelos devem fornecer o programador com um conjunto de chamadas de sistema que permite que ele ou ela para escrever código que vai continuar a respeitar o modelo, mesmo que esses tipos de problemas ocorrem. Com efeito, a plataforma esconde este difícil problema de tolerância a falhas do programador.

Nenhum dos três modelos podem lidar com falhas mais complexas, tais como máquinas que são assumidas por um vírus, ou uma rede que, por vezes, modifica as mensagens transmitidas. O chamado acordo bizantina modelo vai além dos esquemas de replicação de dados discutidos aqui também por resolver tais problemas, mas fá-lo a um preço: protocolos de replicação bizantinos normalmente exigem um maior número de servidores, e pode ser muito mais lento.

Outros usos para sincronia virtual

sincronia virtual é útil para mais do que apenas dados replicar, embora a replicação é provavelmente o uso mais comum. Outros mecanismos que podem ser construídos "sobre" uma plataforma de sincronia virtual incluem:

  • Notificação de eventos (também chamado de publicação-assinatura ). Estes são interfaces que permitem aplicações publicar mensagens de eventos, marcá-los com nomes de tópicos . Os aplicativos podem se inscrever para um tópico, ou um padrão que corresponde muitos temas, especificando uma função a ser chamado quando uma mensagem correspondente é recebido. A plataforma combina editores para os assinantes. Com a comunicação do grupo, isso é feito através da criação de um grupo para corresponder a cada tópico, ou para um conjunto de tópicos. Cada novo evento é publicado pela multicast-lo dentro do grupo.
  • Locking. Muitos sistemas necessitam de algum tipo de travamento ou um mecanismo de sincronização. Bloqueio pode ser facilmente implementado em cima de um subsistema de sincronia virtual. Por exemplo, um sistema pode associar um token com cada grupo, e fazer a regra de que para manter o bloqueio, um processo deve ganhar a "propriedade" do token. Um multicast é utilizado para solicitar o bloqueio: cada membro do grupo irá, assim, aprender de cada pedido. Para liberar um bloqueio, o titular seleciona a mais antiga solicitação pendente, e multicasts uma mensagem liberando o bloqueio do processo que emitiu esse pedido mais antigo. Cada processo no grupo vai, assim, aprender que o bloqueio tem sido passado, e para quem. Da mesma forma, se um detentor de bloqueio falhar, todo o processo vai aprender que isso aconteceu, e um líder (geralmente, o membro mais velho do grupo não caiu) pode tomar medidas correctivas, em seguida, liberar o bloqueio.
Porque é que a sincronia virtual do valor de tal solução? Lembre-se que a camada de comunicação implementação de sincronia virtual deve tomar medidas para assegurar que cada membro do grupo vê cada mensagem, e tem uma definição do que significam estes termos (em termos do modelo temporal, visto anteriormente). Isto faz com que seja relativamente fácil de provar que o protocolo de bloqueio é correcta.
Compare isso com o mesmo protocolo, mas em um sistema sem sincronia virtual (por exemplo, usando multicast UDP, que fornece nenhuma garantia em tudo). Mesmo se a mesma seqüência de eventos ocorre e as mesmas mensagens são enviadas, o protocolo torna-se muito difícil raciocinar sobre, porque os processos podem entrar ou sair do grupo, ou não, enquanto o protocolo está em execução. Se alguns processos perca um pedido de bloqueio, ou uma mensagem de bloqueio de liberação, erros podem facilmente surgir. Assim sincronia virtual tornou fácil para resolver este problema; sem sincronia virtual, o problema é extremamente difícil de resolver.
  • Tolerância ao erro. Um grupo pode facilmente apoiar-formas de backup primário de tolerância a falhas, em que um processo executa acções e um segundo se destaca por como cópia de segurança. Mesmo mais sofisticado é o modelo "coordenador / coorte", em que cada pedido é atribuído a um processo coordenador diferente. Outros processos do grupo são classificados para servir como uma cópia de segurança primário, secundário, etc. Uma vez que as falhas são raros, o efeito é que um grupo com N membros pode potencialmente tratar N vezes a carga computacional. No entanto, se ocorrer uma falha, o grupo pode lidar com isso de forma transparente.
  • caching cooperativa. Membros de um grupo podem compartilhar listas de dados que eles têm em seus caches. Dessa forma, se um processo necessita de um objeto que algum outro processo tem uma cópia, os membros do grupo podem ajudar um ao outro e evitar buscar o objeto de um servidor que pode estar distante, sobrecarregado ou caro.
  • Outros mecanismos de peer-to-peer. Um grupo pode implementar as funções de uma tabela hash distribuída (DHT), uma vez que cada membro conhece a identidade de todos os outros membros. Os grupos também podem ser uma infra-estrutura útil para a implementação de algoritmos enxame, como os usados em BitTorrent .

atuação

Entre os três modelos, sincronia virtual atinge os mais altos níveis de desempenho, mas isso tem um custo: para obter maior desempenho o programador deve relaxar ordenação e empregar recursos de entrega de início otimistas que expõem o serviço a algum risco de inconsistência. Implementações sincronia virtuais empregam um primitivo chamado nivelado para forçar o serviço de volta para um estado consistente antes de interações com clientes externos ou sistemas de armazenamento. O efeito é o de oferecer um modelo muito forte, mas somente se os vários recursos são empregados corretamente.

O Paxos e modelos transacionais garantir um maior grau de durabilidade na presença de ruídos elétricos, e às vezes são percebidos como mais fácil de usar, mas ao preço de reduziu drasticamente o desempenho ea escalabilidade. Ambos os modelos precisa primeiro garantir que uma atualização é registrada em um log write-ahead antes de qualquer processo pode realmente realizar a atualização. Isto introduz uma forma de confirmação de duas fases no protocolo, e, portanto, atrasa as coisas: em primeiro lugar a atualização é enviado e registrado, e todos os membros confirmar que eles têm, e só então é executada. Em contraste, as implementações de sincronia virtuais com replicação de dados in-memory geralmente podem atualizar uma variável replicado assim que uma mensagem descrevendo a atualização atinge os membros do grupo relevantes. Eles podem transmitir altas taxas de atualizações por embalagem várias atualizações em uma única mensagem.

Para dar algum sentido da velocidade relativa, experimentos com variáveis replicados 4 nós empreendidas nos sistemas de Isis e Hórus na década de 1980 sugeriu que as implementações sincronia virtuais em redes típicas foram cerca de 100 vezes mais rápido do que a replicação state-máquina usando Paxos, e cerca de 1.000 10.000 vezes mais rápido que um copy-serializability transacional de pleno direito. Naturalmente, estes tipos de ordem dos números de magnitude são altamente sensíveis à implantação e escolha da plataforma, mas também refletem obrigações subjacentes dentro dos protocolos utilizados para implementar os modelos. Os sistemas modernos como a propagação Toolkit , mercúrio , e corosync podem atingir taxas de dados de 10.000 multidifuss por segundo ou mais, e pode ser dimensionado para grandes redes com grande número de grupos ou processos.

A maioria distribuída plataformas de computação suportar um ou mais desses modelos. Por exemplo, as orientadas a objetos amplamente apoiadas CORBA plataformas todas as transações de apoio e alguns produtos CORBA apoiar a replicação transacional no modelo one-copy-serializability. O "CORBA tolerante a falhas objetos padrão" é baseado no modelo de sincronia virtual. Sincronia virtual também foi usado no desenvolvimento da arquitetura de tolerância a falhas New York Stock Exchange, o sistema francês Air Traffic Control, o sistema US Navy AEGIS, arquitetura de replicação de Processos de Negócios da IBM para WebSphere de e Microsoft arquitetura de cluster do Windows para o Windows Longhorn servidores corporativos.

características essenciais do modelo sincronia virtual

Sincronia virtual é geralmente apresentado aos programadores através de uma biblioteca de programação distribuída simples que suporta pelo menos três interfaces básicas. Em primeiro lugar, um processo (um programa em execução) pode se juntar a um grupo de processos . Cada grupo tem um nome (um pouco como um nome de arquivo, embora estes nomes são interpretados dentro de uma rede, e não em relação a um disco), e cada um tem uma lista de membros. A juntar-se retornos primitivos alguma forma de controle sobre o grupo. O processo pode, em seguida, registrar um manipulador de eventos de entrada, e pode enviar multicasts para o grupo.

A garantia básica associada ao modelo é que todos os processos pertencentes a um grupo ver os mesmos eventos, na mesma ordem. A plataforma detecta falhas (usando o tempo limite), mas informa-los de maneira consistente a todos os membros do grupo. mensagens de multicast podem ser iniciadas simultaneamente por vários remetentes, mas será entregue em alguma ordem fixa selecionados pelos protocolos de aplicação do modelo.

Observe que a garantia apenas descrito incorpora o que pode parecer uma contradição. Sabemos que tempo limite não pode ser usado para detectar falhas com precisão. No entanto sincronia virtual permite que as notificações de falha tratar utilizador (ver alterações) como eventos de confiança, infalíveis. O aspecto chave é que a sincronia virtual é implementado por um sistema de software que cria uma abstração no qual o código do usuário é executado. Assim, a detecção de falha pela plataforma (usando tempos de espera) desencadeia acordo protocolo interno (dentro da plataforma). Só quando este protocolo termina é um evento de falha entregue ao aplicativo. A aplicação é poupado da necessidade de implementar o mecanismo de acordo, e vê um evento de notificação de falhas simples e aparentemente precisa.

Eventos são de vários tipos. Primeiro, cada multicast recebido é entregue como um evento. Mas as mudanças de filiação no grupo também são relatados através de eventos; estes são chamados de novos pontos de vista do grupo. Além disso, quando um processo se junta a um grupo, alguns membro existente é convidado a criar um posto de controle : uma mensagem descrevendo o estado do grupo no momento o processo se juntou. Esta é relatado para o novo membro como uma transferência de estado evento, e é usado para inicializar o processo de adesão.

Por exemplo, suponha que um sistema de controle de tráfego aéreo mantém algum grupo associado com os aviões voando no setor XYZ sobre Paris. Cada controlador de tráfego aéreo que monitora que o setor teria um processo em execução em sua máquina, e estes processos se juntar ao grupo XYZ como eles iniciar. Os membros seria replicar a lista de planos de controlo de tráfego aéreo e pistas associadas ao setor XYZ. Ao aderir, um processo seria obter uma cópia do estado do setor a partir do momento em que se juntou, entregue como um posto de controle através de um evento de transferência de estado. Carregando um tal ponto de verificação é análogo ao ler um arquivo que lista o estado atual do setor. Mais tarde, quando ocorrem eventos que impactam o status do setor, seriam multicast de modo a que todos os membros do grupo podem ver esses eventos. Uma vez que cada membro é no mesmo estado, e recebe as mesmas atualizações, cada controlador de tráfego aéreo vê o mesmo status setor e que vê-lo evoluir da mesma maneira. Se ocorrer uma falha, os sistemas de sobreviventes podem assumir papéis que anteriormente eram detidos por aquele caiu.

A Time-Space Ilustração do Synchrony Conceito Virtual

  • A Figura 1 (A verdadeira sincronia)

  • A Figura 2 (temporização relaxado)

  • A Figura 3 (sincronia virtual)

Os três execuções mostrados acima ilustram o tipo de evento de reordenação utilizado em sistemas de sincronia virtuais. Cada mostra um conjunto de processos (chamado p, q, etc.) execução no decorrer do tempo, da esquerda para a direita. Eles interagem pela troca de mensagens, que são mostrados como setas de processo para processo. Observe que as três figuras são bastante semelhantes, mas diferem em aparentemente pequenas formas: na primeira figura, as setas de transmissão de mensagens são verticais, como se o envio de uma mensagem foi um evento instantâneo. Na segunda figura, o envio de uma mensagem leva "tempo", e vemos isso porque as setas estão agora inclinado para a frente. Na terceira figura, alguns da mensagem enviando flechas atravessar um ao outro.

Vamos começar por olhar atentamente para a figura 1 (você pode querer aumentá-la para que você possa ver as setas claramente). Considere a seqüência de eventos que ocorrem no decorrer do tempo, da esquerda para a direita.

No início, p cria um grupo processo e é o único membro. Então q junta e com a ajuda de p, inicializa-se. A seta indica a pesada a criação de um ponto de verificação por p, que é copiado para q, e, em seguida, carregado por q. Talvez este grupo lista o estado de controle de tráfego aéreo para algum setor sobre Paris. Agora t, um terceiro, pede ao grupo alguma pergunta. Ele envia uma mensagem, e os membros do grupo cooperar para responder (talvez eles cada metade busca de um ATC do banco de dados, afinal, cada um sabe que o grupo tem dois membros e cada um sabe a sua própria posição, de modo a computação paralela torna-se fácil! Em seguida, vemos alguns de atualização mensagens-multicasts-trocados por p e q. Processo r se junta ao grupo, mas q tanto acidentes ou não. Observe que cada evento é visto na ordem idêntica por todos os membros. Isto torna mais fácil para controlar o estado grupo evoluindo . Alguns poderiam chamar isso de uma máquina de estado de execução.

O que torna um sistema praticamente síncrona virtual em vez de verdadeiro é que a ordenação de eventos síncrona é na verdade uma ilusão. Se o momento em que o sistema não é perfeitamente sincronizado, as mensagens podem ser entregues com algum atraso (Figura 2). Agora, os atrasos em questão pode não ser significativo para a percepção humana. Mas como pode a aplicação sabe o fim de processar os eventos em? Nós não podemos usar o tempo do relógio verdadeira para isso: mesmo com GPS relógios, a sincronização não será melhor do que alguns milissegundos.

Em um cenário de pior caso, os eventos realmente acontecer fora de ordem (Figura 3). O ponto de este número se destina a fazer é que, por vezes, um sistema pode entregar eventos fora de ordem e ainda a aplicação pode não notar. Vamos discutir casos em que isso ocorre momentaneamente. Ao desviar a ordem síncrono, sistemas de sincronia virtuais ganhar velocidade e melhorar a tolerância a falhas (eles são menos propensos a experimentar acidentes correlacionados onde alguns mensagem faz com que todos os membros de funcionar simultaneamente).

Em sistemas de sincronia virtuais, os sinais de programador de aplicações para a plataforma qual a forma de ordenação é realmente necessário. Por exemplo, o programador pode indicar que multicast m atualiza dados diferentes multicast n . Sistemas de software sincronia virtuais torná-lo fácil de fazer esse tipo de coisa, embora nós não vamos entrar em detalhes aqui. Basicamente, o programador diz que "você pode entregar mensagens m e n em qualquer ordem que desejar, porque a minha candidatura não vai notar". Quando permitido fazê-lo, o sistema de comunicação podem agora economizar tempo, não atrasar mensagens sob condições onde proporcionando ordem de entrega idênticos para n e m teria introduzido um custo extra e, assim, abrandou a taxa de dados.

Quando podemos ir longe com esse tipo de coisa? A resposta geralmente depende da aplicação. Mas um bom exemplo surge quando um grupo é a manutenção de dados sobre alguns coleção de objetos que tendem a ser acessado de forma independente. Por exemplo, talvez o grupo representa os quartos em um jogo de role-playing multi-usuário. Os usuários são apenas em um quarto de cada vez, portanto multicast que atualizam dados em salas diferentes podem ser entregues em ordens diferentes. Se um usuário vê um desses multicast (por exemplo, o usuário passa a ser na sorveteria de Sarah quando a entrega de uma mensagem que faz com que o telefone toque), eles não vão ver o outro (porque isso afetou o estado de algum outro sala). Voltando ao nosso exemplo de controle de tráfego aéreo, diferentes grupos podem representar diferentes setores do céu, altura em que surgem os mesmos tipos de opções. Um programador projetar um aplicativo como, muitas vezes, têm maneiras simples de perceber que este é o caso, e pode, em seguida, sinalizar isso através de um sistema de chamada apropriada.

Porque se importar? A questão fundamental diz respeito à velocidade da aplicação: a comunicação sistema ganha desempenho como suas obrigações de ordenação estão relaxados. Assim, sincronia virtual é motivada por um objectivo de desempenho. O sistema procura ser tão rápido como um confiável UDP multicast e ainda ter fortes garantias de tolerância a falhas e de ordenação, semelhantes aos de Paxos .

semântica de falha

Mencionamos que há um sentido no qual sincronia virtual é uma mais fraca modelo do que uma cópia serializability ou estado consenso máquina transacional no estilo de Paxos. Em parte, isso se refere a ordenação: sincronia virtual muitas vezes enfraquece a ordem de entrega de mensagens para ganhar desempenho. Como mencionado acima, isso pode às vezes aumentar a robustez também. Se cópias diferentes, por vezes, processar eventos em diferentes ordens (fazê-lo apenas quando isso não terá qualquer impacto sobre o estado final do objeto), as cópias podem ainda ser um pouco mais robusto contra mensagens que causam exceções. Afinal, muitos erros são extremamente sensíveis à seqüência exata dos eventos que um processo de experiências, de modo que os processos que vêem as mesmas coisas, mas em ordens diferentes muitas vezes pode sobreviver problemas que poderiam ser fatal em alguns ordenação específica.

Mas o outro sentido no qual sincronia virtual é um modelo mais fraco relaciona-se com exatamente o que acontece quando algum processo falhar. Suponha que o processo p envia um multicast a um grupo G, e depois p e alguns membros do grupo, dizer q, ambos acidente. No processo que permanece operacional tem uma cópia do multicast. Qual deveria ser a plataforma de fazer?

Em sincronia virtual, o grupo continua a executar como se nenhuma mensagem nunca foi enviada. Afinal, não há nenhuma evidência em contrário. P e Q têm ambos caiu, para que eles não se comportam de uma forma incompatível com o modelo. No entanto, é possível que q recebeu a mensagem de p e entregues para a aplicação certa antes do acidente. Portanto, há um caso em que sincronia virtual parece estar: ele se comporta como se nenhuma mensagem foi enviada, e ainda os processos acidentados pode realmente ter trocado uma mensagem.

Isso nunca acontece em Paxos ou sistemas transacionais, o que os torna um bom jogo para atualizar arquivos de banco de dados em um disco. Em ambos os sistemas, se q depois se recupera e se junta ao grupo, todos os dados que recolheu antes de bater ainda será válido, salvo na medida em que ele perdeu atualizações entregues aos outros membros do grupo enquanto ele estava para baixo. O custo desta garantia é, no entanto, bastante elevado. Asynchronous Paxos, e sistemas transacionais, impor um longo atraso antes de qualquer processo pode entregar uma mensagem. Em primeiro lugar, essas plataformas se certificar de que a mensagem atinja todos os seus destinos, pedindo-lhes para atrasar a mensagem recebida antes de entregá-la. Só após a primeira etapa é concluída são destinatários disse que é seguro para entregar a mensagem para o aplicativo. (Em uma variante nestes modelos, a plataforma única garante que um quorum (a maioria) receber a mensagem, mas o atraso é comparável).

O atraso associado a esta rodada extra de comunicação pode ter um grande impacto no desempenho.

Experiência com sincronia virtual mostra que para a maioria das aplicações, a forma fraca, mas rápido de entrega é apenas multa. Para raros casos em que são necessárias garantias mais fortes, o programador da aplicação pode solicitar que uma entrega mais lento ser realizada, pagando um preço mais elevado pouco frequente, mas somente quando necessário. O desempenho resultante será muito maior do que se a propriedade de entrega mais lenta, mais conservadora foi usado para todas as mensagens.

Sistemas que suportam sincronia virtual

Sincronia virtual foi apoiada pela primeira vez pela Universidade de Cornell e foi chamado de "Isis Toolkit" . Versão mais atual de Cornell, Vsync foi lançado em 2013 sob o nome Isis2 (o nome foi mudado de Isis2 para Vsync em 2015, na sequência de um ataque terrorista em Paris por uma organização extremista chamado ISIS), com atualizações periódicas e revisões desde aquela época . A libertação estável mais corrente é V2.2.2020; Foi lançado em 14 novembro de 2015; o lançamento V2.2.2048 está atualmente disponível em versão beta. Vsync visa os centros de dados maciços que suportam a computação em nuvem .

Outros tais sistemas incluem o "sistema de Horus" , o sistema Transis, o sistema Totem, um sistema IBM chamado Phoenix, um sistema de gerenciamento distribuído chave de segurança chamado Rampart, o "sistema Ensemble" , o Quicksilver sistema, "O projeto OpenAIS" , o seu derivado do motor Cluster corosync e uma série de produtos (incluindo os da IBM e da Microsoft mencionados anteriormente). No momento da redação deste artigo, toolkits sincronia virtuais que os programadores podem usar para implementar novas aplicações praticamente síncronos incluem o Toolkit Espalhe , JGroups , o sistema C-Ensemble, Appia , Quicksilver , e o motor de Cluster corosync .

As referências citadas

Referências adicionais

Sistemas de confiança distribuída: tecnologias, serviços web e aplicações. KP Birman. Springer Verlag (1997). Textbook, abrange um amplo espectro de conceitos de computação distribuída, incluindo sincronia virtual.

Sistemas Distribuídos: Princípios e Paradigmas (2nd Edition). Andrew S. Tanenbaum, Maarten van Steen (2002). Textbook, abrange um amplo espectro de conceitos de computação distribuída, incluindo sincronia virtual.

"A abordagem grupo processo de computação distribuída de confiança" . KP Birman, Communications of the ACM (MCCA) 16:12 (dezembro 1993). Escrito para não-especialistas.

"Especificações de comunicação em grupo: um estudo abrangente" Gregory V. Chockler, Idit Keidar, Roman Vitenberg. ACM Computing Surveys 33: 4 (2001). Introduz um formalismo matemático para estes tipos de modelos, em seguida, usa-lo para comparar o seu poder expressivo e seus pressupostos de detecção de falhas.

"Impacto prático da teoria da comunicação Grupo." Andre Schiper. Direções futuras em computação distribuída. Springer Verlag Lecture Notes in Computer Science 2584 (julho de 2005). A história da região, assume familiaridade com o tema geral.

"O Parlamento part-time" . Leslie Lamport. ACM Transactions em sistemas informáticos (TOCs), 16: 2 (1998). Introduz a implementação Paxos de máquinas de estado replicados.

"Explorando sincronia virtual em sistemas distribuídos" . KP Birman e T. Joseph. Anais do 11º ACM Simpósio sobre princípios sistemas operacionais (SOSP), Austin Texas, novembro de 1987. uso mais antigo do termo, mas provavelmente não a melhor exposição do tema.

"Reflexões sobre a História dos Sistemas de Pesquisa Operacional na tolerância a falhas" . KP Birman. Ensaio que acompanha a palestra proferida no Seminário Dia História ACM SIGOPS em novembro de 2015, associado à ACM Symposium 25 em princípios de sistemas operacionais (SOSP), Monterey Califórnia, 2015. novembro Uma visão ampla da pesquisa sobre tolerância a falhas pela computação distribuída comunidade, com a discussão da evolução da sincronia virtual e protocolos Paxos e comparação de suas características, bem como sobre o chamado CATOCS controvérsia do período de 1993 e a conjectura PAC, que é, em muitos aspectos, uma revisitação mais contemporânea de CATOCS .