Transcript Building Undo for Operators: An Undoable E

Spheres of Undo:
A Framework for Extending Undo
Aaron Brown
January 2004 ROC Retreat
Motivation: Why Spheres of Undo?
• Provide conceptual model to help explain
ROC Undo concepts
– time travel
– paradoxes
– boundaries
• Develop framework for extending Undo to
more complex systems
– nested undo: undo for desktops, shared servers
– distributed undo: undo for distributed systems
Slide 2
What is a Sphere of Undo (SoU)?
• SoU: a “bubble” of state & time
– isolated from external world
– defines boundaries of undo operation
• Example: productivity application
Productivity
Application
Sphere of
Undo
In-memory
document
external
observer
end user
disk
Slide 3
ROC Undo as Spheres of Undo
• ROC Undo == system-wide undo for services
– entire service is now enclosed in sphere of undo
Service
Application
Sphere of
Undo
state
operator
timeline
end users
timeline
• Challenge: end-users now outside boundary
Slide 4
The Problem of Paradoxes
Paradox!
t=3
Service
Application
Sphere of
Undo
end user
3
t
state
operator
1 2 3 4 5 6
t
undo
• Operator’s undo can cause externally-visible
temporal inconsistencies: paradoxes
– sphere of undo establishes paradox boundary
Slide 5
Addressing Paradoxes: Nested SoUs
• Add replay of end-user updates via an
additional sphere of undo
– restores end-user state when operator commits undo
end
users
Application
Service
user
state
operator
• Outer sphere
provides undo
only (all state)
• Inner sphere
provides undo &
redo (user state)
system
state
• But end users can still see inconsistencies!
Slide 6
Coping with Remaining Paradoxes
• In general, impossible to make transparent
• Solution: identify paradoxes and compensate
– via framework for detecting, explaining inconsistency
– works for services with human users
• Sphere of Undo defines points needing
paradox management
– wherever information flows out across SoU boundary
– whenever state outside SoU is altered
Slide 7
Outline
• Motivation
• Spheres of Undo
• Modeling Today’s ROC Undo
• Extending Undo: Hierarchical Services
• Extending Undo: Distributed Services
• Wrapup
Slide 8
Undo for Hierarchical Services
• ROC Undo only works for monolithic services
– all service state in one sphere of undo
– entire service time-travels as a unit
• Can we extend it to hierarchical services?
– multiple-granularity undo in e-mail
» per-user undo as well as whole-system undo
– ASP with shared machines
» undo of each share plus whole-machine undo
– desktop system
» undo of app config, system config, or entire system
Slide 9
Nested Spheres of Undo
• SoUs nest according to state hierarchy:
E-mail
user1
mail
Service 1
users
App.
service 1
OS
State
userN
mail
...
...
...
...
E-mail
users
ASP
E-mail
user’s
SoU
App.
service N
E-mail
Service
SoU
Service N
users
ASP
Service
SoU
Slide 10
Nested SoUs: Composition Model
Post-Undo
Pre-Undo
Self-contained Service
(single sphere of undo)
S1
c
S1
c
S1
S2
Nested spheres of undo
S2
S1 undoes
S1
S2
Key:
S1
timeline
current time
c
S2 undoes
S1
S1
S2
S2
compensation
Slide 11
Nesting Undo Models
• Each nest can use a different undo model
– we saw this before with paradox management:
end
users
Application
Service
user
state
operator
• Outer sphere
provides undo
only (all state)
• Inner sphere
provides undo &
redo (user state)
system
state
Slide 12
Example of Nesting Undo Models:
Desktop Environment
P
Desktop
Application
documents
P
User
app cfg
state
P
platform
cfg. state
Software
installer
OS bins;
low-level
state
Slide 13
Implementing Nested SoUs
• Foundation: nested rewindable storage layer
– independent rollback of substate
• Multiple proxy points for verb generation
– record user actions at multiple levels
• New APIs for inner spheres of undo
– invoke, commit, cancel nested undo
• Minor changes to verb log structure
– maintain tentative verb log during replay; install on
commit
Slide 14
Outline
• Motivation
• Spheres of Undo
• Modeling Today’s ROC Undo
• Extending Undo: Hierarchical Services
• Extending Undo: Distributed Services
• Wrapup
Slide 15
Undo for Distributed Services
• Goal: allow unilateral undo of one service in
a network of cooperating services
end
users
Credit-card
Service
Shopping
Service
state
Orders
state
Fulfillment
Service
Charges
E-Shopping Example
state
• Challenge: paradoxes between spheres
Slide 16
Paradoxes and Distributed Undo
• Two choices for handling paradoxes
– coordinated spheres: propagate undo from paradox
producer to paradox consumer c
c
S1
S2
S1
Undo of
S1
S1
S2
S2
S1
S2
– uncoordinated spheres: paradox producer invokes
compensation on consumer
c
c
S1
S1
S2
S2
c
S1
Undo of
S1
S2
S1
S2
Slide 17
Implementing Distributed Undo
• SoUs provide undo for each subservice &
define paradox management points
• Coordination of SoUs is likely complex
– separation of input and output verbs
– correlation of requests across spheres of undo
– epoch-based log architecture with paradox detection
across epochs
– challenges with non-request-response comm. patterns
• We have tentative algorithms & APIs
– but definitely a fertile area for future study
Slide 18
Outline
• Motivation
• Spheres of Undo
• Modeling Today’s ROC Undo
• Extending Undo: Hierarchical Services
• Extending Undo: Distributed Services
• Wrapup
Slide 19
Wrapup
• Spheres of Undo provide a foundation for
understanding and extending undo
– define boundaries of state and time
– identify paradox management points
– suggest hierarchical and distributed extensions
» first step in undo for desktops and distributed services
• Fertile area for future study and
implementation work!
Slide 20
Spheres of Undo:
A Framework for Extending Undo
• For more info:
– [email protected]
– dissertation:
A. Brown. “A Recovery-Oriented Approach to Dependable
Services: Repairing Past Errors with System-Wide Undo.” UCB
Technical Report UCB//CSD-04-XXXX
– tech report on distributed undo:
A. Brown. “Toward System-Wide Undo for Distributed
Services.” UCB Technical Report UCB//CSD-03-1298.
Backup Slides
Output Paradoxes & Distributed Undo
• Output verbs needed to detect scenarios
like:
Original Execution
rA
A
rB
B
outC
C
After coordinated Undo of A & B
outC
rA
A
r'B
B
out'C
C
PARADOX!
Slide 23
J2EE PetStore as Spheres of Undo
end
users
manager
Storefront
Service
e-mail
confirmations
orders
Management
Service
queries, order approval/rejection
(async)
(sync)
Order-processing
Service
inventory updates
(sync)
orders
(async)
Supplier 1
. . .
Supplier N
Slide 24