Quem precisa de linearização?

13

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?

Eduardo Bezerra
fonte
Você pode verificar na wikipedia: en.wikipedia.org/wiki/… ou no artigo de Herlihy e Wing: "Linearizabilidade: uma condição de correção para objetos concorrentes".
Eduardo Bezerra

Respostas:

5

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.

Massimo Cafaro
fonte
1
esta não é uma boa resposta, pois ela usa outro conceito inexplicável para explicar o conceito em dúvida .. (ler isso é uma perda de tempo) .. as respostas abaixo são muito melhores ...
Richard
Parece que você não leu a pergunta OP original. O OP não estava perguntando o que é linearizabilidade, ele perguntou "Quem precisa de linearizabilidade"? Minha resposta é apropriada, pois fornece ao OP um exemplo de cenário (pelo menos, foi considerado apropriado e selecionado pelo OP). O fato de você não saber o que são estruturas de dados simultâneas e sem espera é uma questão completamente diferente. A propósito, o OP sabia do que eu estava falando. Se tivéssemos de explicar todos os conceitos que usamos em uma resposta, a resposta nunca terminará ;-)
Massimo Cafaro
10

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

Lógica Errante
fonte
O que você quer dizer com afirmar que `` acredito que Herlihy e Wing podem estar tentando definir rigorosamente um monitor ''? Você poderia adicionar alguns detalhes. (Estou lendo o jornal de Herlihy e Wing.)
Hengxin
1
Eu não acho que quis dizer algo profundo. Antes de ler Herlihy e Wing, tudo o que eu havia lido sobre monitores estava operacional. Algo como "um monitor é um tipo de dados abstrato que implicitamente possui um mutex e todo método do tipo adquire o mutex no início e libera o mutex no final", seguido de uma discussão complicada sobre quando é aceitável wait()e notify(). A linearidade fornece uma maneira de falar sobre a correção de implementações de monitores muito mais complicadas / otimizadas.
Wandering Logic
Faz sentido para mim. Valeu. Hoje eu li a Related Workparte do artigo de Herlihy e Wing. Eles mencionaram monitorcomo ilustração sua afirmação disso Our notion of linearizability generalizes and unifies similar notions found in specific examples in the literature. No entanto, uma pergunta geral: a noção de linearizabilidade foi amplamente adotada em sistemas multiprocessadores (por exemplo, hardware, compilador, linguagem de programação e estruturas de dados concorrentes)? (Sendo míope, sei apenas coisas como monitor.) Se não, quais são os obstáculos? Qual é o estado da arte?
evergrow
Eu acho que é considerado uma propriedade desejável que às vezes é muito cara de aplicar. Veja, por exemplo: cursos.csail.mit.edu/6.852/01/papers/p91-attiya.pdf . Também na prática, acho que a maioria dos hashmaps simultâneos tem um bloqueio por bucket, mas nenhum bloqueio global e, portanto, pode ter um comportamento estranho sempre que uma inserção / exclusão faz com que a tabela de hash seja redimensionada.
Wandering Logic
Obrigado pela resposta longa, mas eu tenho medo que você não me disse quando transação atômica foi interessante, mas só definiu-lo e, para essa matéria, que definiu errado: é não o suficiente para que cada processo vê as operações em a ordem em que foram emitidos. A ordem em todos os processos também deve ser consistente. Mas me corrija se eu estiver errado ...
Eduardo Bezerra
2

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.

Sriram Srinivasan
fonte