Data Replication In A Mobile Environment

Data Replication in a Mobile Environment Raymond Pon CS244A Wesley W. Chu

December 2, 2002

Outline • Mobile System Architecture • Problem Description • A Simple Data Replication Strategy: Caching • Data Replication Strategies • Evaluation Considerations

Outline • Mobile System Architecture • Problem Description • A Simple Data Replication Strategy: Caching • Data Replication Strategies • Evaluation Considerations

Mobile System Architecture • Two distinct sets of entities: – Mobile units (MU) – Fixed hosts (FH) • Some are Mobile Support Stations (MSS) that have a wireless interface • Can communicate to MUs

• Cell is radio coverage range over which an MSS can communicate with an MU

Outline • Mobile System Architecture • Problem Description • A simple Data Replication Strategy: Caching • Data Replication Strategies • Evaluation Considerations

Problem • • • • • • • • • • •

Bandwidth Considerations and Data Transfer Rates Frequent Network Failures MUs often have limited battery-life. Wireless communication is expensive! Locality Migration: If a MU has initiated a transaction, and moves, the location of the MU within the network must be found prior to completing the transaction Frequent Planned Disconnections Recovery Services: Where are we going to store the recovery logs? Consistency Semantics: If process are frequently interrupted, they may leave data objects in an inconsistent state. Security Human interface: How do we pose queries from a handheld device? Thus, it is important that MUs access online databases in a way that minimizes communication

Outline • Mobile System Architecture • Problem Description • A Simple Data Replication Strategy: Caching • Data Replication Strategies • Evaluation Considerations

A Simple Data Replication Strategy: Caching • If a MU frequently reads a data-item x, and x is updated infrequently… – …then it is beneficial for the MU to allocate a copy of x locally at the MU – MU will receive all updates of x

• If a MU reads x infrequently compared to the update rate… – …then a copy of x should not be stored locally at the MU – Access should be on-demand

Caching Allocation Strategy • Static: allocation scheme does not change over time • Dynamic: allocation scheme changes over time

Dynamic Caching Allocation Scheme • Assumptions for the model: – FH stores the online database – Data item x is stored at the FH at all times – Reads and writes are issued at a MU or another FH – We are going to ignore reads issued by the FH and writes by the MU, since the cost of such requests is fixed. – Relevant requests are writes by FH and reads by MU.

Dynamic Caching Allocation Scheme (cont’d) • Sliding-Window(k) algorithm allocates and deallocates a copy of the data item x at the MU’s cache. • The window can be represented as a sequence of k bits (0 = read, 1 = write)

1

0

1

1

1

0 K bits

1

1

0

0

0

Who’s in Charge? • At any point in time, whether or not the MU has a copy of x, either the MU or the FH is aware of all the relevant requests • If the MU has a copy of x, then all reads at the MU are satisfied locally, and all writes by FH are propagated to the MU • If the MU does not have a copy, then all reads issued by the MU are sent to the FH • Thus, either the MU or the FH is “in charge of maintaining” the window of k requests. Case 1: MU is “in charge” or has X in the cache # reads > # writes

read

MU

FH

read

x x

Case 2: FH is “in charge” or the MU does not have X in the cache # reads < # writes

MU

FH

write

x

write

Case 1: MU has x • If (# reads > # writes) then wait for next operation

• If (# writes > # reads) then deallocate copy • Deallocation: MU sends to FH… – An indication that the FH should not propagate writes to MU – The current window of requests

read

MU

FH

x x

write

Case 2: MU does not have x • If (# reads < # writes) then wait for next operation

• If (# writes < # reads) then allocate copy to MU

• Allocation: FH sends to MU… – Copy of x – An indication to save the copy in the MU’s cache, in which the FH also promises to propagate further writes to MU – The current window of requests

read

MU

FH

x

write

We need more! • Caching helps minimize wireless communication between a MU and FH • But what if the data we want to access resides on another MU, or a mobile host (MH)? • That’s what a more complex data replication scheme can be used for.

MU

MU

FH

MH

Outline • Mobile System Architecture • Problem Description • A Simple Data Replication Strategy: Caching Data • Replication Strategies • Evaluation Considerations

Data Replication • Allocate replicas of mobile user’s data on fixed sites in the network • Now it becomes possible to handle access requests from other users locally on the fixed sites, without accessing the owner MH • So now instead of MU (or a FH) talking to a MH • A MU (or a FH) can now talk to a FH.

MU

MH

FH

Architecture Extension •

We shall extend the definition of a MU to a MH – MH can act as a data client and a data server at the same time – MH, as a data server, is to support transaction operations such as read, write, prepare, and abort – MH, as a data client, must submit transaction operations to the coordinator laid on the MSS of its current cell (if request cannot be satisfied locally)

•

Each MH has a replica of its data on FH called a replica server

Architecture Extension: Coordinators •

•

•

•

Each MSS has a coordinator which receives transactions operations from MH or coordinators of other MSSs, and monitors their execution in the local replica sever if the corresponding replicas exist If the corresponding data replicas do not exist, the coordinator contacts the location server to get information on their locations. On receiving location info on replicas, the coordinator submits transaction operations to coordinator of MSS where each replica exists. The receiving coordinator will send the request to the local replica server for executions.

Architecture Extension: Location Server • Location server keeps information of locations of all MH as well as replicas which are located within its management coverage. • Whenever moving to another cell, a MH has to notify the location server and inform its new location

Data Replication Strategies • Static replica allocation (SRA): locations of replicas are fixed, regardless of movements of MU • Dynamic strategies – Primary-copy tracking replication allocation (PTRA) – User majority replication allocation (UMRA)

SRA Strategy • •

We assume MH do not move too far from their location servers Server replicates the copy of data at the mobile client – On each write, the server needs to write to the copy on the mobile client – Reading is from a local copy on the mobile client

•

The replicated copy resides at the location server of the client – Client reads from its own location server – Reads and writes are on the same copies – Copy is closer to the reader than the writer

•

The server has a copy of data at its home location server – Client reads from the home location server – Reads and writes are on the same copies – Copy is closer to the writer than the reader

PTRA Strategy •

Replica is always allocated at the replica server in the cell where its owner MH exists • Replica relocation is done as the MH moves from cell to cell • When a MH enters a cell, it registers itself to the new cell by notifying the location server • The location server will query the previous location of the MH and will issue a replication relocation request to the coordinator of the previous location

PTRA Strategy (cont’d) • The strategy is a good idea when… – The owner MH will access data more than other MH – If accesses are write-intensive, the cost of writes can be reduced since it does not involve network connections to other cells

• But as the owner’s mobility grows, cost implied by replica relocations will increase

Outline • Mobile System Architecture • Problem Description • A Simple Data Replication Strategy: Caching • Data Replication Strategies • Evaluation Considerations

Evaluation Considerations • The degree of mobility • Cost of searching for MH • Read/Write activity

Conclusion • Caching can minimize communication between a MH and a FH • More complex replication can minimize communication between a MH and a MH • There are more data replication and caching strategies for the mobile environment (to be explored in the term paper)

References        

Budiarto, K. Harumoto, M. Tsukamoto and S. Nishio, “On Strategies for Allocating Replicas of Mobile Databases,” IEICE Trans. on Information & System, Vol.E81-D, No.1, January 1998 Budiarto, K. Harumoto, M. Tsukamoto and S. Nishio, “On relocation Decision Policies of Mobile Databases,” IEICE Trans. on information & System, Vol. E82-D, No.2, February 1999. P. Sistla, O. Wolfson and Y. Huang, “Minimization of communication cost through caching in mobile environments,” IEEE Trans. on Parallel and Distributed Systems, Vol.9, No.4, April 1998. Y. Huang, P. Sistla and O. Wolfson, “Data Replication for Mobile Computers,” ACM SIGMOD, May 1994. Y. Huang and O. Wolfson, “Dynamic Allocation in Distributed System and Mobile Computers,” IEEE Proc. Tenth Int’l Conf. Data Eng. ‘94, pp. 20-29, Houston, Tex., 1994. R. Tewari, P. Grillo, “Data management for mobile computing on the Internet,” Proc. The 1995 ACM 23rd Annual Conference on Computer Science, 1995, pp. 246-252. B.R. Badrinath and T. Imielinski, “Replication and Mobility,” Proc. Second Workshop Management of Replicated Data (WMRD-II), pp. 9-12, Monterey, Calif., 1992. R. Alonso and H.F. Korth, “Database system issues in nomadic computing,” Proc. Of the 1993 ACM SIGMOD Intl. Conf. on Management of Data, pp. 388-392, 1993.

Additional References      



R. Ahuja, R. Bagrodia, L. Bajaj, M. Takai, “Evaluation of optimistic file replication in wireless multihop networks” Global Telecommunications Conference, 1999. GLOBECOM '99 , Vol. 1a , 1999, pp. 259 -265 vol.1a. C. D. Tait and D. Duchamp, “Service interface and replica management algorithm for mobile file system clients,” Proceedings of the Parallel and distributed information systems conference, December 1991. D. Barbara and T. Imielinski, “Sleepers and workaholics: Caching strategies in mobile environments,” Proc. Of the 1994 ACM SIGMOD Intl. Conf on Management of Data, pp. 1-12, 1994. G. H. Forman and J. Zahorjan, “The challenges of mobile computing,” IEEE Computer, pp. 38-47, April 1994. T. Imelinski and A. Badrinath, “Mobile wireless computing: Solutions and challenges in data management,” Technical Report, Rutgers University, 1993. H. V. Leong and A. Si, “On adaptive caching in mobile computing,” In Proceedings of the 1997 ACM Symposium on Applied Computing, 1997, San Jose, CA, pp. 302-309.

M. T. Özsu and P. Valduriez, “Mobile Databases,” Principles of Distributed Database Systems, 2nd Edition, New Jersey, 1999, pp. 596602.