Semântica segura - Safe semantics
A semântica segura é um modelo de consistência de hardware de computador . Ele descreve um tipo de garantia que um registro de dados fornece quando é compartilhado por vários processadores em um computador paralelo ou em uma rede de computadores trabalhando juntos.
História
A semântica segura foi definida pela primeira vez por Leslie Lamport em 1985. Foi formalmente definida no livro de Lamport "On Interprocess Communication" em 1986.
O registro seguro foi implementado em muitos sistemas distribuídos.
Descrição
A semântica segura é definida para uma variável com um único gravador, mas vários leitores (SWMR). Um registro SWMR é seguro se cada operação de leitura satisfizer estas propriedades:
- Uma operação de leitura não simultânea com nenhuma operação de gravação retorna o valor gravado pela última operação de gravação.
- Uma operação de leitura que é simultânea com uma operação de gravação pode retornar qualquer valor dentro do intervalo de valores permitido do registro (por exemplo, 0,1,2, ...).
Em particular, dada a simultaneidade de uma operação de leitura e gravação, a leitura pode retornar um valor que não foi gravado por uma gravação. O valor de retorno precisa pertencer apenas ao domínio de registro.
Um registro seguro binário pode ser visto como uma modelagem de um pouco de oscilação. Qualquer que seja o valor anterior do registro, seu valor pode piscar até que a gravação termine. Portanto, a leitura que se sobrepõe a uma gravação pode retornar 0 ou 1.
Churn refere-se à entrada e saída de servidores de / para um sistema distribuído. Baldoni et al. mostram que nenhum registro pode ter a propriedade mais forte da semântica regular em um sistema síncrono sob churn contínuo. No entanto, um registro seguro pode ser implementado sob churn contínuo em um sistema não síncrono. A modelagem e implementação de um tipo de memória de armazenamento (Registro Seguro) sob churn não quiescente requer alguns modelos de sistema, como sistemas cliente e servidor. Os sistemas cliente contêm um número finito e arbitrário de processos responsáveis pela leitura e gravação do sistema servidor. No entanto, o sistema do servidor deve garantir que as operações de leitura e gravação ocorram corretamente.
Implementação
A implementação do registro seguro envolve:
O registro seguro é mantido pelo conjunto de servidores ativos.
Os clientes não mantêm nenhuma informação de registro.
Sistema eventualmente síncrono
Quora (conjunto de sistemas de servidor ou cliente)
Tamanho da operação de leitura e gravação executada em quora = n - f - J (n é o número de servidores, J é o número de servidores que entram e saem e f é o número de falhas bizantinas .
Algoritmos como juntar, ler e escrever.
Juntar
Um servidor ( si ) que deseja entrar em um sistema servidor transmite uma mensagem de consulta para outros servidores para informá-los de sua entrada, si solicita um valor atual do registro. Assim que outro servidor receber essa consulta, ele enviará mensagens de resposta para si. Depois que si recebe respostas suficientes de outros servidores, ele coleta as respostas e as salva em um conjunto de respostas. O Si espera até obter respostas suficientes (nfj) de outros servidores e, em seguida, seleciona o valor recebido com mais frequência. Si também:
- Atualiza sua cópia local do registro
- Torna-se ativo
- Respostas aos processos no conjunto de respostas
- Se ficar ativo, ele envia mensagens de resposta para os outros servidores. Caso contrário, armazena as consultas, respondendo quando se torna ativo.
- Ao obter respostas de outros servidores, ele adiciona a nova resposta ao conjunto de respostas e descarta o valor antigo.
- Se o valor do servidor de resposta for maior que o valor de si, si reterá o novo valor.
Ler
O algoritmo de leitura é uma versão básica de junção. A diferença é o mecanismo de transmissão usado pela operação de leitura. Um cliente ( cw ) transmite uma mensagem ao sistema e, uma vez que o servidor recebe a consulta, ele envia uma mensagem de resposta ao cliente. Assim que o cliente recebe respostas suficientes (nfj), ele para de enviar uma consulta.
Escreva
O cliente ( cw ) envia uma consulta ao sistema em diferentes rodadas e espera até receber duas confirmações. ( sn = número de sequência)
A razão para receber dois reconhecimentos é para evitar o perigo em um sistema. Quando um processo envia uma confirmação ( ack ), ele pode morrer após um milissegundo. Portanto, nenhuma confirmação é recebida pelo cliente.
A validade do registro seguro (se uma leitura não for simultânea com nenhuma gravação, retorne o último valor gravado) foi comprovada com base no sistema de quorum. Dados dois sistemas de quorum (Qw, Qr), Qw indica os servidores que sabem sobre o valor mais recente e Qr indica os valores das respostas de leitura. O tamanho de cada quorum é igual a nfj. Provar a validade do registro seguro requer provar
onde B é o número de falhas bizantinas.
Prova: a região vermelha indica (Qw∩Qr) \ B e a região azul indica Qr∩B. Partindo do pressuposto, o tamanho de cada quorum é nfj, portanto, a região vermelha tem n-3f-2j servidores ativos. Portanto,
é estritamente maior que f.
