Transcript Powerpoint slides

Leveraging
Operational Transformation
in
Collaborative Object Groups
G. Henri ter Hofte
[email protected]
Telematica Instituut, The Netherlands
It takes 100 ms ...
• for humans to react, or
for humans to perceive a response is not immediate
• for 40 million clock cycles to run on a 400 MHz Pentium II
• for 15,5 Mb of data to be sent on an ATM link
• … for 1 bit of that data to reach its destination
on an international link
• (for light to travel about 3/4 around the world)
latency: it won’t go away!
What if …
• Latency > 100 ms and you need “immediate”
response?
replication!
• for performance of groupware (despite high latency)
• You want to work together while disconnected?
replication!
• for availability in nomadic computing (i.e. despite disconnection)
• A computer crashes and you need the functionality?
replication!
• for fault-tolerance in critical applications (i.e. despite partial faults)
Collaborative zipper
file status
Legend:
edit status
uncoupled status
view control
status
coupled status
(centralized)
user interface
control status
coupled status
(synchronization)
Replication complexities
• consistency management
• due to ordering anomalies
• waiting on “the other side(s)” is expensive
• e.g. don’t lock unless really necessary!
• latecomers & earlyleavers
• how to handle without disrupting service?
Remote Method Invocation
Java Virtual
Machine 1
Java Virtual
Machine 2
A
B
Java RMI
Multicast RMI ?
JVM
1
JVM
2
JVM
3
A
B1
B2
Multicast RMI (MRMI)
Object group invocation
object group
(server)
object group
(client)
Object group invocation
request(s)
response(s)
object group
(server)
object group
(client)
collation
multicast
multicast
collation
Proposed solution: GroupRMI
• replicated object groups
• programmers can treat them as normal (non-replicated) objects
• replication transparency
• adhere to Java RMI, works for arbitrary remote objects
• “programmers that know how to RMI, know how to GroupRMI”
• shallow learning curve
• default policies + allow for policy plug-ins
• to allow advanced programmers to deal with special cases
• to allow various (optimistic) consistency policies
• coupling/uncoupling, operational transformation, merging
• selective replication transparency
One level
Legend:
uncoupled status
coupled status
(centralized)
coupled status
(synchronization)
One level
Legend:
uncoupled status
coupled status
(centralized)
coupled status
(synchronization)
One object group
Legend:
uncoupled status
coupled status
(centralized)
coupled status
(synchronization)
One object group
Legend:
uncoupled status
coupled status
(centralized)
coupled status
(synchronization)
One object group member
One object group member
Java object
Local done queue
(outbound queue (aggregation),
optimistically performed actions,
undo/redo & latecomer log)
Outbound Coupler
(presence aggregation filter)
Concurrency Control:
Exclusive Access
and/or Ordering
multicast channel
total order token
Acccess Control
Inbound Coupler
(awareness aggregation filter)
Local to-do queue
(pessimistically delayed local actions)
actions,
& inbound queue (aggregation))
Java RMI scenario
client JVM
lookup
(“rmi://h1/nm”)
Registry
“nm”
Naming
lookup(“nm”)
server JVM (“h1”)
bind(“nm”)
Naming
bind(“nm”)
B
A
stub for B
myCall()
myCall()
stub for B
skeleton for B
myCall
GroupRMI scenario
JVM
A
session1
newInstance
(“CB”,“nm”)
myCall()
myCall()
B
“nm”
JVM
session1
“nm”
newInstance
(“CB”,“nm”)
A
’
myCall()
B’
Operational transformation
matrix: two operations
• commutative: do nothing special
• masking: delete one from history buffer
• memoryless: masking all, empty buffer
• conflicting: specify transformation function
• application specific
• fork history (parallel versions) is an option
followed by version merging tools
Use of operational
transformation
• State transfer = intentional latency
• Group undo/redo = “ delayed” undo
• Version merging = human-assisted form of operational
transformation
Issues
• terminology
• find better quality criteria
• e.g. from serializability to consistency causality, intention preservation
• performance studies
• e.g. impact of latency, use of IP multicast, algorithms
• simulation of network
• usability tests
• what DO users expect, what IS their intention
• build application-specify transformation matrices
Issues (cont’d)
• share algorithms
• common experimentation platform
• with pluggable policies
• + simulation
That’s all folks!
Questions? Comments?