Quem precisa de linearização?

Eu tenho lido sobre as diferenças entre serializabilidade e linearizabilidade , que são critérios de consistência para sistemas replicados, como bancos de dados replicados. No entanto, não sei em quais casos a linearizabilidade seria necessária, mesmo que seja mais forte que a serialização.

Você poderia criar cenários em que essa propriedade forte seria realmente necessária?

Considere o design de estruturas de dados simultâneas, sem espera (ou sem bloqueio, o que é mais fraco). Nesse cenário, a linearizabilidade é geralmente necessária, embora em alguns casos, o desempenho e a escalabilidade possam ser aprimorados satisfazendo uma condição de correção mais fraca. A utilidade de uma implementação que satisfaça uma condição tão fraca é geralmente dependente do aplicativo. Por outro lado, uma implementação linearizável é sempre utilizável, porque os designers podem vê-la como atômica.

Além disso, a linearizabilidade é uma propriedade sem bloqueio: nunca é necessário bloquear uma operação total (definida para todos os estados do objeto). Em vez disso, a serialização não é uma propriedade sem bloqueio. Portanto, para aumentar o grau de simultaneidade, os projetistas de estruturas de dados simultâneas sempre contam com linearização.

Reli Herlihy e Wing muitas vezes nos últimos 15 anos. É uma leitura muito difícil. E isso é lamentável, porque, embora existam algumas sutilezas nas bordas, a ideia básica é realmente bastante razoável.

Resumindo: linearizabilidade é como serializabilidade, mas com o requisito adicional de que a serialização respeite restrições adicionais de pedidos entre as transações. O objetivo é permitir que você raciocine rigorosamente sobre uma estrutura de dados atômicos individuais, em vez de ter que raciocinar sobre todo o sistema de uma só vez.

A linearidade também é fácil de obter: basta associar um mutex ao objeto que você deseja linearizar. Toda transação nesse objeto começa bloqueando o mutex e termina desbloqueando o mutex.

Aqui estão as definições que vou usar:

Um sistema é serializável se um determinado conjunto de transações for fornecido sobre um conjunto de dados, qualquer resultado da execução das transações é o mesmo que se as transações fossem executadas em alguma ordem seqüencial e as operações em cada transação estiverem contidas na transação na ordem especificado pelo código da transação.

A serialização permite a aparência de intercalação de operações entre transações diferentes e exige que a ordem escolhida das transações satisfaça a causalidade (se a transação A gravar o valor x, e a transação B ler o valor x que A escreveu, a transação A deverá preceder a transação B em a ordem serial escolhida.) Mas não diz nada sobre outras restrições à ordem das transações (em particular, nada diz sobre processos e a ordem na qual os processos percebem eventos).

Há outra ideia relacionada que adiciona restrições à ordem na qual os processos executam operações (mas não fala sobre transações apenas operações de leitura / gravação individuais):

Um sistema é sequencialmente consistente se o resultado de qualquer execução for o mesmo que se as operações de todos os processos fossem executadas em alguma ordem seqüencial, e as operações de cada processo individual aparecerem nessa sequência na ordem especificada por seu programa. ( Lamport, "Como criar um computador multiprocessador que execute corretamente programas multiprocessos", IEEE T Comp 28: 9 (690-691), 1979 ).

Implícito na definição de consistência sequencial é que só aceitamos ordens sequenciais em que, para cada local da memória (objeto), a ordem sequencial induzida de operações obedece à regra de que o valor retornado por cada operação de leitura para o local xdeve ter o mesmo valor que foi escrito por a operação de gravação imediatamente anterior ao local xna ordem sequencial.

A linearidade tem as boas intenções de (a) combinar a noção de transações (da serialização) com a noção de que os processos esperam que as operações que eles emitem sejam concluídas em ordem (de consistência sequencial) e (b) restringir os critérios de correção para falar sobre cada objeto isolado, em vez de forçá-lo a raciocinar sobre o sistema como um todo. (Eu gostaria de poder dizer que a implementação do meu objeto está correta, mesmo em um sistema em que existem outros objetos que não são linearizáveis.) Acredito que Herlihy e Wing possam estar tentando definir rigorosamente um monitor .

A parte (a) é "fácil": um requisito sequencial semelhante à consistência seria que as transações no objeto emitido por cada processo apareçam na sequência resultante na ordem especificada pelo programa. Um requisito semelhante à serialização seria que as transações no objeto sejam todas mutuamente exclusivas (podem ser serializadas).

A complexidade vem do objetivo (b) (poder falar sobre cada objeto independentemente de todos os outros).

Em um sistema com vários objetos, é possível que as operações no objeto B imponham restrições na ordem em que acreditamos que as operações foram invocadas no objeto A. Se estivermos analisando todo o histórico do sistema, ficaremos restritos a determinadas ordens sequenciais, e precisará rejeitar os outros. Mas queríamos um critério de correção que pudéssemos usar isoladamente (raciocínio exatamente sobre o que acontece com o objeto A sem apelar para o histórico global do sistema).

Por exemplo: suponha que eu esteja tentando argumentar sobre a correção do objeto A, que é uma fila, suponha que o objeto B seja um local de memória e suponha que eu tenha os seguintes históricos de execução: Thread 1: A.enqueue (x), A. desenfileirar () (retorna y). Thread 2: A.enqueue (y), A.dequeue () (retorna x). Existe uma intercalação de eventos que permitiria que essa implementação da fila estivesse correta? Sim:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

Mas agora e se o histórico ( incluindo o objeto B ) for: B começa com o valor 0. Thread 1: A.enqueue (x), A.dequeue () (retorna y), B.write (1). Tópico 2: B.read () (retorna 1) A.enqueue (y), A.dequeue () (retorna x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Agora, gostaríamos que nossa definição de "correção" diga que esse histórico indica que nossa implementação de A é incorreta ou nossa implementação de B é incorreta, porque não há serialização que "faça sentido" (o Tópico 2 precisa ler um valor de B que ainda não foi gravado ou o Thread 1 precisa retirar da fila um valor de A que ainda não foi enfileirado.) Portanto, enquanto nossa serialização original das transações em A parecia razoável, se nossa implementação permite uma história como a segunda, então está claramente incorreta.

Portanto, as restrições adicionadas pela linearização são bastante razoáveis ​​(e necessárias mesmo para estruturas de dados simples, como filas FIFO.) São coisas como: "sua implementação deve proibir dequeue () um valor que não será enfileirado () até algum tempo no futuro." A linearidade é bastante fácil (e natural) de alcançar: basta associar um mutex ao seu objeto, e cada transação começa bloqueando e termina desbloqueando. O raciocínio sobre linearização começa a ficar complicado quando você está tentando implementar sua atomicidade com técnicas sem bloqueio, sem bloqueio ou sem espera, em vez de simples mutexes.

Se você está interessado em algumas dicas para a literatura, encontrei o seguinte (embora eu ache que a discussão sobre "tempo real" seja um dos truques que tornam a linearização mais difícil do que precisa) https: // stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

Primeiro, linearização e serialização não são diretamente comparáveis. Como a tabela abaixo mostra, a principal diferença é que, no lado esquerdo, todas as operações individuais são atômicas (como ter um java em synchronizedtorno de cada operação . No lado direito, a unidade de atomicidade é uma transação; uma operação individual não é atômica É por isso que a serialização sempre fez parte da literatura do banco de dados, enquanto o lado esquerdo foi objeto da literatura sobre memória do processador (a operação de leitura / gravação é atômica) .O Key-Value original armazena (como dbm e memcached) começou no lado esquerdo (o get / put é atômico), mas os mais novos estão cada vez mais suportando transações (como a chave do Google).

obj. operações são atômicas | As transações são atômicas
-------------------------------- + ----------------- ----------------
Linearizabilidade |
Consistência sequencial | Serializability
Consistência causal |
Consistência do cache |

A linearidade requer que um sistema de objetos em uma configuração simultânea se comporte de forma idêntica a um sistema seqüencial que lida com uma operação (um par de solicitação / resposta) por vez - em um universo paralelo - de maneira que (a) os clientes em ambos os universos, vemos exatamente as mesmas respostas (b) a ordem temporal é preservada (mais sobre isso abaixo).

A definição de serialização, como consistência sequencial, requer apenas o primeiro critério.

Preservação de ordem temporal significa o seguinte: se A: x.op1 () (A é um cliente, x é um objeto e op1 é uma operação) concluída antes que outra operação B: y.op2 () inicie, então no universo seqüencial o pedidos são tratados na mesma ordem. Isso não é necessário na Consistência sequencial (SC); o objeto pode enfileirar a solicitação de um cliente, responder ao cliente e avaliá-lo mais tarde. Além disso, o objeto pode manipular uma solicitação posterior de algum outro cliente fora da vez, avaliando-a antes de chegar à primeira.

A não preservação da ordem temporal é um problema. Depois de A: x.op1 (), suponha que A atendeu o telefone e disse a B sobre isso, então B ligou para x.op2 (). Não há como o sistema saber sobre essa cadeia causal de eventos, pois a segunda etapa envolveu uma mensagem não rastreada pelo sistema. Em muitos casos reais, não é irracional para A supor que, uma vez que x tenha respondido a ela, a chamada de B possa confiar no estado atualizado. Se a ordem temporal não foi preservada, A e B surpreendem. Isso não aconteceria em um sistema linearizável.

A segunda boa propriedade da preservação da ordem temporal é a localidade e a composicionalidade, que um sistema construído com objetos linearizáveis ​​é ele próprio linearizável. Portanto, em vez de ter um armazenamento monolítico de valor-chave, você pode dividi-lo em várias partições separadas, cada uma gerenciada por seu próprio servidor de armazenamento KV; se cada um deles é linearizável, o banco de dados inteiro funciona como um armazenamento monolítico KV linearizável, sem nenhum esforço extra.