Controle de Concorrência e Consistência
Otimista – Operational Transformation
Lucas Augusto Scotta Merlo
[email protected]
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
2
Introdução

Autoria distribuída

Porque?




Pessoas com um interesse em comum compartilhando um
documento.
Agilidade e comodidade.
Ganho da produção.
Problemas



Necessidade de manter o documento atualizado e consistente.
Permitindo colaboração (no lock).
Minimizando tempo de resposta e visualizações não
atualizadas.
3
Introdução(cont.)

Controle de Concorrência e Consistência:

Pessimista.

supõe que sempre ocorre conflito entre alterações;


bloqueio (locking)
Otimista.

Supõe que não haverão muitos conflitos, mas se houver, uma
forma de se recuperar será executada.

Operational Transformation.
4
Introdução (cont.)

Comumente, a edição textual colaborativa usa
uma estrutura linear, com as seguintes operações:



insert(p; c) - inserts character c at position p;
delete(p) - deletes the character at position p;
Algumas definições para o melhor entendimento
das abordagens para manter consistência:
Relação de
ordem causal.
O1 -> O2
Operações
concorrentes.
O1 || O2
5
Introdução (cont.)

Há dois modos básicos para o merge das
informações.

Baseado em estado (todo o documento deverá ser
trocado).

Ex. CVS e SVN.


Onde o usuário é o auditor de conflitos.
Baseado em operações (msg com operações são
trocadas).


Melhor para resolver conflitos.
Histórico das operações.
6
Introdução (cont.)

Problemas genéricos de inconsistência:
divergência, violação de causalidade e, violação
de intenção.
7
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
8
Protocolos sociais para mediação



Segue a ideia que as pessoas conversam entre si
(chat, vídeo) para resolver os problemas.
Todos podem editar qualquer parte do objeto
compartilhado.
Os 3 problemas citados acima, não são tratados
por essa forma.

Conflitos são descobertos, mas não tratados.
9
Optimistic locking

Ao se solicitar o bloqueio inicia-se a edição.

Se negada, volta ao estado inicial.



O que pode confundir o usuário.
Se permitido, continua a edição.
Alto custo para implementação e possível
confusão devido a negação de aquisição dos
locks.
10
Serialisation

Executa a ordem das operações de forma serial.


Isto é, uma operação só pode ser executada somente
após todas operações precedentes a ela tiverem sido
executadas.
Exemplo:


Supondo que haja três operações que possuem ordem causal,
O1, O2 e O3.
Se a ordem de operação é: O2->O1->O3, esta técnica garante
que nos sites participantes essa ordem não será alterada.
11
Multi-versioning


Abordagem que tenta executar todos os efeitos
das operações de um objeto em comum em
formas de versões.
Preservando a intenção do usuário e violação de
causalidade.

SVN, CVS,... .
12
Multi-versioning (cont.)

A desvantagem dessa técnica é que não há
correlação entre as diferentes versões do mesmo
objeto e do objeto base.


Não ficando claro no fim da edição qual é a versão
correta.
Gerando conflitos no final da edição se mais de um
usuário tentar resolvê-los.
13
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
14
Operational transformation (OT)

Ellis et al, em 1989 propõem a utilização de uma
técnica diferente em seu sistema, GROVE (GRoup
Outline Viewing Edit): OT.


Sub-área de pesquisa há mais de 2 décadas no
contexto de edição em grupo.
Mecanismo que mantém consistente as cópias de
objetos de uma forma otimista.

Usuário alteram sua cópia localmente e recebem
/enviam alterações que devem ser transformadas e
executadas nas cópias remotas.
15
Operational transformation (cont.)

Abordagem mais apropriada para arquitetura de
sistema de edição colaborativa na qual a
consistência das cópias compartilhada é algo que
deve apresentar um bom tempo de resposta.

A operação é executada imediatamente localmente e
depois são geradas as alterações que serão enviadas
para as cópias remotas, onde serão transformadas e
aplicadas.

Transformações são executadas de forma que a intenção do
usuário seja preservada e ao final que as cópias convirjam.
16
Operational Transformation (cont.)


Sua forma não bloqueante, faz que o tempo de
resposta seja quase o mesmo da latência de
transmissão entre redes.
Seu uso é particularmente uma ótima escolha
para autoria colaborativa na Web e no contexto
da Internet.
17
Operational transformation (cont.)
18
Operational transformation (cont.)
19
Operational transformation (cont.)


Abordagem baseada em operações.
Para capturar as relações causais entre as
operações, foi criado um vetor baseado no
esquema timestamping, chamado de vetor de
estados (SV).
20
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
21
Modelos de consistência CC:

Propriedade de Precedência (Causalidade):
assegura a execução das operações dependentes
durante o processo de colaboração


A relação causal entre as duas operações é definida
como relação de Lamport "happened-before".
Convergência: assegura que ao final da edição
compartilhada os documentos são idênticos em
todos os sites. O state-vector é usado para
preservar a propriedade de precedência.
22
Modelos de consistência CCI:

Proposto como um framework mais geral, onde as
seguintes propriedades devem ser seguidas:



Preservação de Causalidade: mesmo do CC
Convergência: mesmo do CC.
Preservação de Intenção: assegura que o efeito da
execução da operação em qualquer site seja o mesmo.
23
Modelos de consistência CSM:

Após estudos, foi formalizado um modelo mais
conciso que o modelo CCI:



Causalidade: mesmo que CC.
Single-operation effects: o efeito de executar qualquer
operação em qualquer estado de execução, atinge o
mesmo efeito no seu estado de geração.
Multi-operation effects: a relação dos efeitos de
quaisquer duas operações são mantidas depois que
ambas são executados em quaisquer estados .
24
Modelos de consistência CA

CSM, requer que a ordem total dos objetos
envolvidos sejam especificadas.


Essa ordem deve ser mantida nas funções de
transformação e nos procedimentos, o que aumenta a
complexidade de tempo e espaço do algoritmo.
CA é baseado na Teoria de Admissibilidade.
25
Modelos de consistência CA (cont.)

Duas condições devem ser satisfeitas:


Causalidade: a mesma do CC.
Admissibilidade: A invocação de cada operação é
admissível no seu estado de execução, ou seja, cada
invocação não deve violar qualquer relação com os
efeitos (ordenação de objeto) que tenham sido
estabelecido por invocações anteriores.
26
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
27
Estrutura de um sistema de OT
28
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
29
Funções em OT

Inclusion Transformation: IT(Oa, Ob) ou
T(op1,op2), a qual transforma uma operação Oa
contrastando-a há uma outra operação Ob, de tal
forma que o impacto do Ob é efetivamente
incluído em Oa.

Exclusion Transformation ET(Oa, Ob) ou
T− 1(op1,op2), a qual transforma uma operação Oa
contrastando-a há uma outra operação Ob, de tal
forma que o impacto do Ob é efetivamente
excluído de Oa.
30
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
31
Propriedades de Transformação

Propriedade de Convergência

CP1/TP1: para cada par de operações concorrentes
op1 e op2, definidas no mesmo estado(contexto), a
função de transformação T, satisfaz as propriedades
TP1 sse:

onde
denota a sequencia de operações contendo opi
seguido por opj, e onde denota a equivalência das duas
sequencias de operações.
32
Propriedades de Transformação (cont.)

Pré-requisito:

CP1/TP1 é necessária apenas se o sistema OT permitir
que qualquer duas operações sejam executadas em
ordens diferentes.
33
Propriedades de Transformação (cont.)

CP2/TP2: Para cada três operações
concorrentes, op1, op2 e op3, definidas no
mesmo estado do documento, a função de
transformação T satisfaz as propriedades de
CP2/TP2 sse:
34
Propriedades de Transformação (cont.)

CP2/TP2 estabelece a igualdade entre duas operações
transformadas no que diz respeito a duas sequencias
equivalentes de operações: a transformação de op3
contrastando a sequencia de operação op2 seguido por T
(op1, op2) devem obter a mesma operação como a
transformação de op3 contrastando a sequencia formada
por op1 e T(op2, op1).
35
Propriedades de Transformação (cont.)

Pré-requisitos:

CP2/TP2 é requerido se o sistema de OT permite que
duas operações op1 e op2 sejam transformadas (IT) em
dois estados diferentes do documento ou contexto.
36
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
37
dOPT (distribtuted Operational Transformation)

Cada site mantém um history buffer (HB) com
todas operações que já foram executadas no site.


Quando uma operação remota é recebida e não é
causally ready (interfere em outra), ela é enfileirada no
HB. No caso de ser, ela é sequencialmente
transformada em operações concorrentes no HB.
Entretanto este algoritmo, não funciona bem quando
transformações têm de ser executadas entre duas
operações que não são do mesmo contexto.
38
dOPT (cont.)



Preservação de causalidade é obtida pelo uso de
vetores de estado.
Convergência não é conquistada.
Como na maioria das abordagem de OT,
preservação de intenção não é explicitamente
definida, mas é incluída nas funções de
transformação.
39
GOT



(Generic Operation Transformation)
Estende a abordagem dOPT.
A ordenação causal determina uma ordem
somente entre as operações precedentes, a
ordem da execução de operações concorrentes
são arbitrárias.
A ordenação entre as operações é usada para
assegurar a convergência de operações
concorrentes.
40
GOT (cont.)


A ordem total entre as operações é definida como
a soma dos elementos do vetor de estados (SV).
Por exemplo, a O1 precede em ordem total a
operação O2 se a soma dos elementos do vetor de
estados associado com O1 é menor que a soma do
vetor de estados associados a O2, ou as somas
serem iguais, mas o identificadores do site onde
O1 foi gerado é menor que o identificador onde a
operação O2 foi gerada.
41
GOT (cont.)


Baseado no ordenamento total entre as
operações, esquemas de undo/-do/redo foram
definidos.
Os dois tipos de transformação usados, IT e ET
são reversíveis.
42
GOT (cont.)


Preservação de causalidade é obtida pelo uso de
vetores de estado.
Convergência é alcançada a partir da ordenação
causal.

Como na maioria das abordagem de OT, preservação
de intenção não é explicitamente definida, mas é
incluída nas funções de transformação.
43
GOT(O)


Versão otimizada do GOT.
Aplica o mesmo algoritmo usado em SOCT2.


Quando uma operação remota é recebida, e esta
precisa ser integrada ao HB, este é reordenado de tal
maneira que as operações que precedem a operação
remota fiquem situadas no HB antes das operações que
são concorrentes dessas operações remotas.
Depois disso, as operações remotas devem ser
transformadas de encontro as operações concorrentes
a ela.
44
GOT(O) (cont.)



Preservação de causalidade é obtida pelo uso de
vetores de estado.
Convergência: Condition C1 e Condition C2
Preservação de intenção Inclusion Transformation
e Exclusion Transformation
45
SOCT2



Faz parte da classe de algoritmos que seguem a
linha do dOPT.
Seja s o estado do objeto e O uma operação,
definimos como s.O o novo estado após a
execução de O em s.
A intenção que é realizada pelo operação O em s,
é denotada como: intention(O, s).
46
SOCT2 (cont.)

A função de transformação que modifica O2
contrastando-a com outra operação é indicada
como: O1 : O2O1, a qual é definida sobre o estado
resultante da execução de O1 e concretizando a
intenção como em O2.
47
SOCT2 (cont.)

Condição C1


Garante que o estado resultante após a transformação
de duas operações concorrentes não dependem da
ordem na qual as operações são executadas.
Tomando O1 e O2 duas operações concorrentes
definidas em um mesmo estado, a transposição
“forward” (IT) verifica C1, sse:
48
SOCT2 (cont.)

Condição C2


Visa tornar a transformação de uma operação com uma
sequencia de operações independente da ordem das
operações em sequencia.
Dado O1, O2 e O3, a transposição “forward” verifica C2,
sse:
49
SOCT2 (cont.)
Site1, O1 ->O2

Site2, O3 é gerado concorrentemente.

No site2, quando O1 chega, é
contrastada com O3, porque O1 e O3 tem o mesmo
estado de geração, sendo o resultado

Mas, quando O2 chega no Site2, ela não pode
ser contrastada usando transpose_fd com O3,
como feito com O2 e O3 pois não possui o mesmo
estado de geração.

O estado geração de O2 inclui a execução de
operação O1, O3, enquanto a operação não
sabe sobre a execução da operação O1.

50
SOCT2 (cont.)

A fim de lidar com esses casos, uma outra função
chamada transposição transpose_bk foi definida.
51
SOCT2 (cont.)


Em cada local S envolvidos na colaboração, é
mantido uma cópia local do documento e um HB
que consiste de uma sequencia de n operações
realizadas na cópia local do documento.
As operações no HS(n) são ordenados de acordo
com sua ordem de execução. Quando uma
operação local é gerada, é simplesmente anexada
ao HB.
52
SOCT2 (cont.)

Quando uma operação remota chega a um site, é
verificado se é conflitante ou não. Se a operação
não é conflitante, é adicionada a uma fila e
executada quando torna-se conflitante, isto é,
todas as operações que precedem forem
executadas.
53
SOCT2 (cont.)

Integração das operações conflitantes ao HB:


A primeira etapa do processo de integração consiste na
reordenação do HB de tal forma que todas as
operações que são causalmente precedente à operação
remota, venham antes das operações que são
concorrentes para a operação remota no HB.
O segundo passo no mecanismo de integração, consiste
em transmitir a transformação da operação remota
de acordo com a sequencia de operações concorrentes.
54
SOCT2 (cont.)



Preservação de causalidade é obtida pelo uso de
vetores de estado.
Convergência: Condition C1 e Condition C2
Preservação de intenção: Forward Transformation
e Backward Transformation
55
treeOPT


Representa os documentos em forma de árvore,
aplicando mecanismos de transformação
operacional recursivamente sobre os diferentes
níveis do documento.
Mantém o histórico distribuído pela árvore,
quando há uma operação a ser transformada,
apenas aquele caminho é varrido e não o histórico
como um todo, reduzindo-se a complexidade.
56
treeOPT (cont.)


Cada site armazena uma cópia local da estrutura
hierárquica do documento compartilhado.
Cada nó (excluindo os nós folhas) mantém um
histórico de operações de inserções e deleções
associadas com os nós filhos.
57
treeOPT (cont.)



Finalmente a nova operação é enviada para todos
os outros sites, e marcada no vetor de estados.
Após receber uma operação remota, o site
receptor irá testá-la para ver se é causally ready.
Se a operação não é causally ready, ela será
colocada na fila, caso contrário, ela será
transformada e então executada.
58
treeOPT (cont.)

A operação remota deve ser transformada
contrastando as operações anteriores, as quais
estão mantidas no HB.


GOT ou SOCT2
Cada nó de uma sub-árvore, ao ser inserida,
contém este histórico (HB) vazio. Ao se gerar a
operação de composição, a mesma é executada
no site imediatamente.

A operação é então gravada no HB associando seus nós
pai de inserção ou deleção.
59
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
60
Exemplo treeOPT
61
Exemplo treeOPT (cont.)
62
Exemplo treeOPT (cont.)
63
64
Agenda


Introdução
Resolução de conflitos de forma otimista

OT







Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT
Exemplo com treeOPT
Conclusão
65
Conclusão



OT é uma técnica muito eficaz no controle de
controle de concorrência e consistência otimista
principalmente para internet/web.
Os principais algoritmos estudados conseguem
resolver os problemas de inconsistência.
Dependendo do problema somente o uso de OT
(ou qq outra abordagem otimista) não é eficaz,
sendo necessário o uso de uma abordagem
pessimista.
66
Questões...



OT tem sido usado para edição em tempo real
para autoria colaborativa. Quem necessita
realmente de editores em tempo real?
Funções de Transformação são difíceis de se
desenvolver e prova.
O que é realmente são as intenções?
67
Agenda


Introdução
Resolução de conflitos de forma otimista

OT





Modelos de consistência
Estrutura de um sistema de OT
Funções em OT
Propriedades de Transformação
Algoritmos para OT


Exemplo com treeOPT
Conclusão
68
Referências






http://en.wikipedia.org/wiki/Operational_transformation
Customizable Collaborative Editor Relying on treeOPT Algorithm - Claudia-Lavinia Ignat
and Moira C. Norrie
C. A. Ellis, e C. Sun, “Operational Transformation in Real-Time Group Editors: Issues,
Algorithms, and Achievements”, Proceedings of the 1998 ACM conference on Computer
supported cooperative work, p.59-68, November 14-18, 1998, Seattle, Washington,
United States.
C. L. Ignat, “Maintaining Consistency in Collaboration over Hierarchical Documents”,
Tese apresentada ao "Swiss Federal Institute Of Technology Zurich", Switzerland, Julho
de 2006
Uwe M. Borghoff, Johann H. Schlichter “Computer-Suppor​ted Cooperative Work:
Introduction to Distributed Applications” Springer Verlag ,2000. ISBN: 9783540669845.
Li, D., Li R. “Preserving Operation Effects Relation in Group Editors”, Proceedings of the
2004 ACM conference on Computer supported cooperative work table of contents.
69
Obrigado!
70