Em Spanner, TrueTime & O Teorema CAP , Eric Brewer escreve:
Uma coisa sutil sobre o Spanner é que ele obtém serializabilidade dos bloqueios, mas obtém consistência externa (semelhante a linearizabilidade ) do TrueTime [ ênfase adicionada ].
Qual é a definição de consistência externa , e como ela difere da linearizabilidade ?
Comentários
- Esta é uma ótima pergunta e eu gostaria que Eric tivesse elaborado um pouco aqui. É linearizável ou não? 🙂
Resposta
A consistência externa não tem um significado fixo. Neste contexto, ela tem o significado que aparece na próxima frase do documento:
Para quaisquer duas transações, $ T_1 $ e $ T_2 $ (mesmo se em lados opostos do globo): se $ T_2 $ começar a se comprometer após $ T_1 $ terminar de se comprometer, então o carimbo de data / hora para $ T_2 $ é maior que o carimbo de data / hora para $ T_1 $.
Comentários
- Quanto mais eu penso nisso, isso soa muito como linearizabilidade para mim, porque todas as transações são ordenadas. Infelizmente, às vezes esses termos são sutis. .. Alguém discorda? Quero dizer, as transações são serializáveis e são totalmente ordenadas com base no tempo de confirmação. Talvez a sutileza esteja em como 2PC é implementado no Spanner?
- @Bminer Linearizabilidade é um modelo de consistência que só se aplica a objetos únicos, onde as transações podem envolver vários o bjects.
- @LorinHochstein – Ha! Isso cheira a palavras minuciosas. O objetivo da terminologia é ajudar pessoas reais a conceituar as garantias que recebem, especialmente no que diz respeito às transações. Linearizabilidade + serializabilidade é a garantia mais forte e eu acho que ' é o que os documentos do Spanner se referem ao termo " consistência externa. " Mas isso levanta a questão: alguém realmente sabe o que " consistência externa " meios? 🙂
Resposta
Você pode pensar sobre a consistência externa do isolamento das transações (Tx) e do ponto de vista do pedido . Em termos de isolamento de Tx, a consistência externa é equivalente ao isolamento serializável estrito, onde “estrito” é a parte da restrição em tempo real (como na linearizabilidade).
Isso novamente significa que para um Tx observável do cliente do sistema Os efeitos colaterais são equivalentes a um sistema, onde todos os Tx ocorrem de forma isolada, sem qualquer simultaneidade e onde sua ordem em tempo real, vista pelo cliente, é preservada. Mais importante ainda, esta mesma ordem é vista por qualquer outro cliente não relacionado.
Leia mais sobre a distinção neste blog .
Resposta
Ao mencionar " consistência externa " , Brewer faz referência a B. Liskov. Usos práticos de relógios sincronizados em sistemas distribuídos . Princípios ACM de Computação Distribuída (PODC). Montreal, Canadá, agosto de 1991.
Liskov, no termo, faz referência a Gifford D.K. Armazenamento de informações em um sistema de computador descentralizado . Relatório técnico CSL-81-8, Xerox Corporation, março de 1983
Veja como Gifford define consistência externa:
Externo A consistência garante que uma transação sempre receberá informações atualizadas. Usando os conceitos que acabamos de apresentar, podemos fornecer uma definição formal de consistência externa. A ordem de tempo real em que as transações são concluídas define uma programação serial única. Esta programação serial é chamada de programação externa . Diz-se que um sistema fornece consistência externa se garantir que a programação que usará para processar um conjunto de transações é equivalente à sua programação externa.
Como @Oleg menciona, isso soa como serializabilidade estrita .