Transcript Toolkits for Building Mobile Systems

Toolkits for Building Mobile
Systems
3/28/2002
Michael Ferguson
([email protected])
Problem

Mobile computing environments have




Limited network bandwidth
Long periods of disconnection
Data is still stored on servers
Mobile users still want to modify their
documents when they are
disconnected!
Solutions?



Coda filesystem
Isolation Only Transactions
Rover Toolkit
Prior Work - Coda




Coda is a network filesystem
Uses standard UNIX file interface to insulate
application from changes in network
availability
Uses a cluster of servers to meet the goal of
“high availability”
Uses optimistic concurrency control



We can all change the files at once
Conflicts are handled after the fact by file-type
specific handlers
Allows “Disconnected Operation”
Coda Terms

First-class replicas of data are on
servers


Second-class replicas are the client’s
cached copies
Optimistic vs. pessimistic concurrency
control
Coda’s Disconnected
Operation



“Hoard” data by priority when
connected
Users modify local copies of the files
while disconnected
Coda “reintegrates” with servers upon
reconnection; conflicts are handled by
ASRs (application-specific resolvers)
Hoarding in Coda

What if the data isn’t in the hoard?
Coda returns an error, but
can be set to block until connected again


Users must create “hoard profiles” to
describe what data should be available
should they become disconnected
Example Hoard Profile
# Venus source files
# (shared among Coda developers)
a /coda/project/coda/src/venus 100:c+
a /coda/project/coda/include 100:c+
a /coda/project/coda/lib c-
Isolation Only Transactions



What if include old data in my new file?
Add IOT to Coda
Applications can modified to use it to
have better consistency during a
network outage
IOT Terms


First-class transactions are transactions
when there are no partitioned accesses
Second-class transactions are all other
transactions
IOT transaction states
IOT Guarantees




Serializability for first class transactions
Local serializability for second class
transactions
Global serializability for second class
transactions*
Global Certification Order for second
class transactions*
Remember: Serializability = equivalent to serial execution
Global Serializability



Would a pending second-class
transaction be globally serializable if
committed?
Can be tested when network is
reconnected
Use a resolution strategy if not
Global Certification Order

Is a pending transaction




Global Serializable and
Serializable after all committed
transactions?
Again, test once network is
reconnected.
Use a resolution strategy if not
IOT Resolution Strategies




Re-execute the transaction with the
current server files (make example)
Invoke an application specific resolver
(calendar example)
Abort the transaction (makes sense for
load sharing)
Notify the user
IOT implementation



Still use optimistic concurrency control,
even for first-class transactions
Check for global serializability by
looking for cycles in a precedence graph
Log transactional history
Coda & IOT – Pros and Cons
Pros

Works well with existing
applications (without IOT)

UNIX file accesses are almost
always separate

Worked for disconnected
operation of about a day
without hitches

Transactions provide other ways
to resolve conflicts using history
Cons

Coda is a filesystem – it has
only per-file granularity

It was “not intended for
applications that exhibit highly
concurrent, fine granularity data
access”*

Application involvement is
limited – apps lose information
with only a read/write interface
(eg mobile host added, or
server deleted record?)

Requires user involvement on
filesystem level

Applications that read/write files
for synchronization may fail
*From Disconnected Operation in the Coda File System
Rover



Toolkit approach
“Application knows best”
Make all communication explicitly
asynchronous
Rover Toolkit

Relocatable dynamic objects (RDOs)


Distribute objects and processing to reduce
communication requirements
Queued remote procedure calls
(QRPCs)

Applications can make QRPCs without
blocking even when disconnected
Rover Operation




Import objects onto client machine
Invoke methods on those objects
Export logs of method invocations to
servers
Reconcile client data with server data
Rover Operation
Rover Architecture

Access manager



Maintains RDOs and logs their modification
Recovers from local failures
Network Scheduler




Sends requests from QRPC log
Groups operations for each server to amortize connection setup
Compresses headers (and data if application does not)
Chooses transport protocol and medium



Object Cache



HTTP over TCP/IP
SMTP over IP or non-IP networks
Local, private cache for application, and
Global shared cache within access manager
Operation log


Incrementally sent to server
Applications can compact the log/overwrite entries
Rover Architecture
Rover RDOs

Objects which encapsulate all data






the application and
the data it manipulates
QRPC used to lazily fetch RDOs
Updates to cached RDOs are tentatively
committed
Operations are sent to server where they
change primary copies
Application decides which RDOs to fetch and
when
RDO Pros and Cons
Pros

Minimize amount of data on
network

Client GUIs can be run even
when disconnected
Cons

Must split up functionality into
client and server objects
Rover QRPC



Requests are queued
Applications are notified by callback (or
can block) when the request has
completed
Non-FIFO delivery enables prioritization
QRPC Pros and Cons
Pros

Increase network performance
through scheduling, batching,
and compressing

Stable log increases reliability
and reduces retransmission
requests

Only adds 1% latency on
slowest link with Flash RAM
Cons

Recording every QRPC in a
stable log decreases network
performance

Adds 50-300ms to latency
Consistency Control






Primary method is primary-copy, tentative-update, optimistic
Rover also supports other methods, including pessimistic locking
and serializability
Results of reconciliation always override tentative commits
All conflicts are detected and resolved by server
Applications decide when conflicts exist and how to handle
them, although Rover provides version vectors
Uses method invocations instead of new values; eg


Debit, credit, and balance methods
Updating the value would require locking
Rover Applications

Mobile-Transparent Proxies



NNTP Proxy
HTTP Proxy
Mobile-Aware Applications




Rover
Rover
Rover
Rover
Exmh
Webcal
Irolo
Stock Market Watcher
Rover Server



Standalone TCP/IP server, or
CGI plugin to httpd
Implemented for UNIX (Linux and
SunOS)
Experimental Results - Apps
Experimental Results - QRPC
Experimental Results - Proxy
Rover Pros and Cons
Pros

Porting requires only small
effort (person-weeks to months)

Using rover for mobiletransparent applications
increased performance by about
17% on low-bandwidth links

Mobile-aware applications
performed up to 7 times better
on low-bandwidth links

Rover can still use TCP/IP
wireless links prone to error

Rover meets its goal of enabling
disconnected operation
Cons

Applications must be ported

Rover makes performance
slightly worse on ethernet

RDOs may present security
problems

Don’t know how to handle
errors sent back to client
applications which are not
running

Performance studies did not
include cost of starting
application and loading data
Summary

Coda & IOT create a highly available
filesystem




Disconnected operation is an extra
Works well in the home-directory environment
Does not sacrifice performance over fast networks
Rover allows applications and users to make
high-level decisions about replication


Improves cellular performance but reduces
performance over fast links
Fits a highly collaborative environment