Olá pessoal!
Hoje, gostaríamos de voltar a abordar o tema da execução simultânea e seqüencial em vários programas, especialmente em sistemas distribuídos. Em setembro, publicamos o artigo “
Sincronicidade é um mito ” sobre esse tópico e agora publicamos uma tradução de um estudo mais sério, que, esperamos, ajudará você a navegar melhor com sistemas distribuídos.
Existe apenas um problema real na ciência da computação: admitir que os erros de invalidação do cache são nomeados incorretamente. Esses são apenas erros de unidade relacionados ao uso do tempo.
- Autor desconhecido
O tempo é uma coisa estranha.
Desta vez é tão estranho, porque nós realmente queremos realmente acreditar que é completamente simplificado. Parece-nos que qualquer evento às 15h00 ocorre (como diríamos) antes de qualquer evento às 16h00 - sem exceções, argumentos ou compromissos.
No entanto, a ciência da computação conhece muitos exemplos quando é necessário abordar esse requisito de maneira não tão estrita. Ele se manifesta no nível de processadores, compiladores, nós da rede. De novo e de novo nos cálculos, em diferentes níveis da pilha, nos encontramos em situações em que somos confrontados com dois eventos e não sabemos em que ordem eles ocorreram. O tempo obviamente não é total; ela está fragmentada.
Porque O fato é que não sabemos disso, pois o nível de abstração sobre o qual existimos não fornece uma resposta para essa pergunta. Seja acidental ou não, nossas abstrações computacionais não dão garantias sobre o procedimento. A liberdade de reordenar eventos geralmente permite criar sistemas muito mais produtivos e acessíveis.
O processador pode ter um
modelo de pedido de memória ; reflete o que garante que o processador não deseja fornecer garantias no estágio de montagem - por exemplo, qual instrução foi executada anteriormente e qual posteriormente. O processador decide exatamente como transmitir as instruções e executá-las fora de ordem - ou seja, usa seus chips com mais eficiência do que eu imaginaria.
Uma linguagem pode ter um
modelo de correspondência de memória ("modelo de memória" para abreviar); reflete o que garante que o idioma não fornece ao gerar um assembly, por exemplo, ao distribuir instruções por vários threads. Essa reordenação é, por definição, inerente ao modelo de hardware da memória e, em grande parte, explica por que um conceito tão fraco de tempo é fornecido nos compiladores. É dentro da estrutura de um modelo de memória implementado na linguagem que você programa quando escreve código sem bloqueio.
Um exemplo famoso de um modelo de memória implementado no nível da linguagem é o
modelo de memória forte e fraca no padrão C ++ 11. Por padrão, o C ++ fornece operações atômicas com sincronização, mas também pode enfraquecer o modelo de acesso à memória para melhorar o desempenho. O comportamento fornecido dessa maneira pretende servir como uma abstração das principais arquiteturas de processador usadas atualmente (x86, POWER e ARM).
Finalmente, um sistema distribuído pode ter seu próprio modelo de consistência; reflete o que garante que o sistema não lhe dará em relação à ordem dos eventos nos clientes e réplicas na rede global de computadores. Os pedidos diretamente relacionados à latência da comunicação ou à falta de sincronização explicam principalmente por que em um sistema distribuído você não pode prescindir do modelo de tempo fraco mencionado. É esse modelo de consistência que você programa quando escreve um aplicativo distribuído.
Na prática, há um enorme
zoológico de modelos de consistência que você pode usar ao programar um sistema distribuído. Em todas essas situações, esses modelos descrevem o comportamento (desejado) do sistema observado de fora desse sistema. Se eu - um cliente específico ou um fluxo específico - escrever um valor e imediatamente o ler, é garantido que eu definitivamente verei um registro não mais antigo que o meu? Se o tempo não fosse fragmentado, se tivéssemos sempre uma idéia clara em que ordem as operações em nosso sistema estavam acontecendo - naturalmente, a resposta a essa pergunta seria afirmativa. Seria estranho fazer uma pergunta dessas.
Mas o tempo é fragmentário - portanto, é necessário levantar essa questão.
Modelos de consistência - quero dizer, modelos de memória
Falar sobre uma ordem tão fragmentada é muitas vezes difícil e sempre desagradável. Gostaríamos de começar pelo fato de que, em todos os níveis da pilha, o tempo é sempre absolutamente absoluto - seja com transações ACID ou operações / bloqueios atômicos. Quanto mais rigorosas as garantias, naturalmente mais fácil programar com elas!
Mas todos nós lutamos pela velocidade. Sejam sistemas distribuídos nos quais é necessário sacrificar a consistência estrita por questão de disponibilidade ou programação sem bloqueio, onde um modelo de memória fraco é usado para evitar custos de sincronização, geralmente é aconselhável que um programador que trabalha com qualquer nível da pilha entre nesses argumentos complexos. .
A consistência dos modelos de memória compartilhada e a consistência dos modelos de memória distribuída são
abstratas . Eles descrevem o programador que trabalha com o sistema, a interface deste sistema. Eles possibilitam entender quais tipos de comportamento correspondem a um modelo de memória fraco, já que agora as propriedades gerais da ordenação de eventos no sistema, que consideramos um dado adquirido, não atuam mais nele. Pode parecer que esses dois modelos de memória são semelhantes, no entanto, ambas as comunidades desenvolveram seus próprios discursos para discussão. Os valores usados neles diferem, embora se sobreponham.
Já imaginamos o quão confuso isso pode ser. O que fazer?
Descrição do tempo como entidade, implicando em dois a oito tipos de ordem parcial
Em
seu livro de 2014, Sebastian Burkhardt procura fornecer uma descrição exaustiva das muitas opções para modelos de consistência. Com essa característica, juntamente com outras estruturas matemáticas, são utilizadas duas variantes da ordem lógica dos eventos: “visibilidade” e “arbitragem”, mencionadas anteriormente também em outros trabalhos de Burkhardt et al., Veja, por exemplo, o
artigo sobre apontar e checar tipos de dados replicados (2014).
"Visibilidade" é uma ordem parcial inerente ao condicionamento potencial. Permite rastrear quais eventos (possivelmente em outras réplicas) são visíveis para quais outros eventos. Não há requisitos de visibilidade além da aciclicidade; eventos em um objeto podem ser visíveis para eventos em outro objeto, e a operação de ler ou gravar um evento não afeta sua visibilidade para outros eventos.
"Arbitragem" é uma ordem geral que permite rastrear como um sistema distribuído em que uma situação de escolha surge julgará qual evento ocorre mais cedo e qual depois.
Como os modelos de consistência distribuída são semelhantes aos modelos de memória, verifica-se que esses fenômenos de visibilidade e aleatoriedade também podem ser úteis ao discutir modelos de memória. Em particular,
no apêndice de seu artigo de 2014, Burkhardt demonstra "quão próximo" o modelo de memória fraca do C ++ 11 está da consistência causal baseada em objetos, mas com alguns desvios interessantes. Isso será discutido no restante do post.
Para começar, vamos detalhar a visibilidade e a aleatoriedade, levando em consideração a “leitura” e a “ordem das mudanças”. Ao "ler", a visibilidade entre dois objetos será levada em consideração apenas nas situações em que a leitura e a escrita tocam o mesmo objeto e, ao ler, apenas um registro (ou mais de um) pode ser visível.
Isso corresponde a uma situação em que um processador com memória compartilhada, a qualquer momento, pode registrar informações em apenas uma célula de memória para qualquer objeto em particular, mesmo que diferentes threads possam acessá-las em diferentes momentos de causa e efeito (por outro lado, em um sistema distribuído, a lógica um objeto pode ser gravado imediatamente em muitas réplicas separadas).
A “ordem de modificação” corresponde ao mesmo estágio de concretização da arbitrariedade, é objetiva e permite apenas gravações. Novamente, essa especialização se baseia no fato de que, com uma especificação de memória fraca, garantias categóricas são dadas apenas no nível de um objeto.
A seguir, vamos discutir os axiomas da consistência formulados por Burkhardt e colaboradores e ver como eles se aplicam a um modelo de memória fraca. Observe: mesmo apesar da palavra “axiomas”, essas são simplesmente propriedades que podem ou não ser fornecidas em vários modelos de memória. O artigo de Burkhardt enfoca as propriedades que determinam a causalidade entre objetos.
Coerência em última análise
Para qualquer evento específico, não pode haver um número indefinido de eventos que não o vêem. Ou seja, qualquer evento
é finalmente visível para o sistema.
A criação lógica de tais condições em um sistema com um modelo de memória fraco deve ser um pouco mais difícil: é preciso argumentar que, para qualquer
registro específico, não pode haver um número infinito de operações de leitura que não leram esse registro ou registros anteriores (na ordem de modificação).
Na especificação C ++ 11, a conformidade com esse axioma não é garantida, embora na prática seja difícil encontrar um contra-exemplo.
Consistência Etérea
Ao rastrear a "condicionalidade potencial" no nível dos fluxos / operações do cliente e com relação à visibilidade / legibilidade, você precisa entender que não há tempo de retorno. Por isso, é necessário que os fechamentos ao ordenar os fluxos que implicam a leitura sejam acíclicos. Como regra, não há dúvida de que essa propriedade será observada em sistemas distribuídos; no entanto, é essa propriedade que não permite a visibilidade do usuário em algumas versões especulativas, se o sistema tiver um modelo de memória fraco.
Burkhardt e colaboradores Salientam que esse axioma “não está confirmado” na especificação C ++ 11 e não está claro “não valida” se “ciclos satisfatórios” podem ser
observados na prática .
Axiomas da Condicionalidade
Para especificar a que exatamente o fenômeno da condicionalidade se relaciona sob um modelo de memória fraca, devemos determinar com precisão quais eventos podem influenciar os resultados de quais outros eventos. Para começar, considere nossos axiomas padrão de causa e efeito:
garantias de sessão . Essas são quatro qualidades inter-relacionadas que refletem as propriedades de coerência das operações de leitura e gravação que ocorrem em fluxos diferentes; além disso, elas devem ser especificadas no nível de cada objeto (ver
Burkhardt et al .,
Fig. 23 ).
- RYW (Leia seus registros): a operação de leitura após a operação de gravação é feita na mesma célula, dentro do mesmo fluxo / réplica / sessão, e deve ler dados não menos relevantes que o registro. A variante dessa propriedade para sistemas distribuídos é especificada exclusivamente em termos de visibilidade, enquanto a variante para um modelo de memória fraca deve ser baseada na ordem de leitura e na ordem de alteração.
- RM (leituras monolíticas): as leituras subsequentes (dentro do mesmo fluxo, na mesma célula) também devem ver dados não menos relevantes no futuro.
- WFR (primeira leitura e gravação): se a gravação segue a leitura dentro do fluxo, na mesma célula, na ordem das alterações, ela deve ser posterior à operação de leitura.
- MW (registros monolíticos): registros posteriores (dentro do fluxo, na mesma célula) devem ir posteriormente na ordem de modificação.
As versões originais do WFR e MW existem em duas versões, para aleatoriedade e visibilidade; mas isso é importante apenas ao trabalhar com células de dados mais complexas do que com registros para números inteiros.
Essas propriedades refletem as noções de condicionalidade, consistentes com nosso senso comum; no entanto, eles sentem falta do mais interessante. Em particular, ao analisar em um modelo de memória fraca, esses fenômenos de condicionalidade são limitados pelos limites do fluxo / réplica / sessão e pela célula / objeto específico em que a entrada é feita:
em um artigo de Burkhardt et al . neste caso, é dito sobre "visibilidade condicional objeto a condicional" e "arbitrariedade arbitrária objeto a condicional", também ver fig. 23. Esses fenômenos não limitam completamente o comportamento do sistema quando fluxos diferentes gravam informações em células diferentes.
Em seguida, os axiomas do condicionamento entre objetos descrevem o efeito das relações de causa-efeito no nível de vários objetos / células de memória.
- COCV (Visibilidade condicional de objeto cruzado): o mesmo caso do RYW, mas sem a condição de que a leitura final deva ser feita no mesmo encadeamento / réplica / sessão. As leituras de um objeto que são objetivamente posteriores aos registros desse objeto devem ter dados não menos relevantes do que os inseridos durante a gravação.
A especificação C ++ 11 reflete essas propriedades. Observe: eles são definidos de tal maneira que as restrições na visibilidade da gravação e a arbitrariedade da ordem de modificação não refletem muito essas definições.
Mas isso não se aplica à última propriedade.
- COCA (arbitrário condicional entre objetos): semelhante aos registros monolíticos, mas aplica-se a fluxos diferentes, semelhantes ao COCV - é RYW para fluxos diferentes. No entanto, como a ordem de modificação afeta apenas os registros em um objeto, a formulação para um modelo de memória fraca permite que o sistema tenha uma distribuição inconsistente de eventos de gravação em diferentes objetos, e os registros podem não corresponder a leituras ou ordem no fluxo.
Especificamente, o COCA em um modelo de memória fraca é uma propriedade muito mais fraca. É por isso que, com um modelo de memória fraca, o código a seguir pode retornar
{x ≡ 0, y ≡ 0} .
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return yA ordem em cada fluxo pode ser inconsistente com a ordem do objeto por ordem e a ordem de modificação. Observe: com RYW, não há
x := 0 → x := 1 na ordem de modificação e para
y é o mesmo; portanto, a ordem de modificação deve conter
x := 1 → x := 0 e
y := 1 → y := 0 . Assim, a ordem de modificação obviamente forma um ciclo na ordem dos fluxos.
Esse loop é permitido no COCA com um modelo de memória fraca. Não é que a ordem dos fluxos / leituras seja contrária à ordem de modificação, mas que cada fluxo veja um histórico de registros consistente. Essas histórias são consistentes com as histórias de outros fluxos somente se limitarmos objetivamente o escopo de sua aplicação.
O que tudo isso significa?
O tempo está fragmentado.
Embora pareça para nós que o tempo flui de uma maneira muito ordenada, o estudo de sistemas distribuídos e um modelo de memória fraca mostra claramente que isso não é verdade. É por isso que, nessas duas situações, nossa super-aproximação padrão, segundo a qual o tempo é total, limita o desempenho - o que não podemos permitir.
Então, reconhecendo que o tempo é verdadeiramente fragmentado, encontramos muitas diferenças pequenas, porém importantes, entre as variedades de tal parcialidade. Mesmo os dois campos acima mencionados, que parecem tão semelhantes à primeira vista, em muitas nuances sutis, tornam possível distinguir quais tipos particulares de eventos são considerados afetados mutuamente.
É necessário entender com mais detalhes os detalhes técnicos de várias propriedades, já que alguém pode expressar as propriedades de um campo no idioma de outro.
O tempo está fragmentado. Talvez nós apenas precisamos nos acostumar com isso.