Caching Strategies for Mobile Devices

Caching Strategies for Mobile Devices

Randolph Chung

Department of Computer Science, Cornell University

Ithaca, New York

-1-

1) Introduction

With the increasing popularity of Personal Digital Assistants (PDAs) and other mobile devices, new applications are being developed to take advantage of the mobility and ubiquitous nature of these devices. A large class of these applications are information-gathering in nature: for example, to look up stock quotes, local weather, traffic conditions, etc. Presumably, each of these queries are personalized and depend on a profile that a stored within the users' PDA. Although individual queries may be customized, with the proliferation of these applications, it is likely that the same data (e.g. traffic condition in a particular area) will be queried by a large number of users. Caching techniques are essential to minimize connection time for mobile devices and to make these systems scalable.

Unfortunately, traditional caching strategies are often not applicable nor useful in mobile applications. To better understand why this is so, one must first understand traditional caching strategies, and examine the characteristics of mobile devices:

Traditional caching strategies for client-server architectures: [2]

Stateful:

 Server sends invalidation or refresh messages

 Server keeps track of which clients are present

 Clients inform server when they connect/disconnect

Stateless:

 Server does not know about which clients are connected, nor the age of clients’ caches

 Server broadcasts state changes / invalidation reports as data changes [asynchronous]

 Server periodically broadcasts invalidation reports [synchronous]

Characteristics of mobile devices:

 Often disconnected

 Would like to minimize connection time to save resources

In light of these limitations and requirements, a number of researchers have been working on novel caching strategies that provide the flexibility required for mobile applications. This survey paper will present a number of these strategies.

2) ACID vs. BASE

In traditional database applications, the ACID (Atomicity, Consistency, Isolation and Durability) properties are considered to be of paramount importance. The design of caching strategies thus reflected this requirement. In order to maintain consistency between data on a database system and data maintained in caches, either:

i) caches have to periodically check with main database to verify that their data is still valid; or

ii) the system has to notify caches of changes either as they occur or on a periodic basis.

While these strategies work well in cases where the main server and the caches are close together and well connected, a lot of effort must be expended to deal with cases when the subsystems cannot communicate with each other. This may be due to temporary network partitions, or failure of some of the components of the system. In either case, if data were to be written to the database while part of the system is unavailable, some means must be available to reconcile conflicts in the data when the separated components later reappear. Methods for handling these situations include:

i) not allowing writes unless all components are reachable; this is obviously not desirable unless partitions are very rare;

ii) using a quorum-based technique, such that only writes to a group with some majority of members are accepted; this does not work well in small group settings

In either case, there appears to be a tradeoff between availability and maintaining consistency. If the ACID properties were to be taken seriously (as is necessary in many applications), then it is expensive, if not impossible, to provide high availability.

In mobile applications, mobile devices are often disconnected for long periods of time. This wrecks havoc with techniques mentioned above that require, for the most part, continuous connectivity. In light of the fact that many of the applications that mobile devices are used for do not require absolute adherence to the ACID properties, strategies have been developed that provide high availability at the cost of absolute consistency. Some researchers have dubbed this level of consistency as BASE [4] – basically available, soft-state, eventual consistency. Most caching strategies described to date for mobile system take this approach ([3]). Essentially, this is a “read-any, write-any” approach, where data can be read from or written to the database (or other permanent storage) at any time, even if some components are unavailable. Conflicts in the data are resolved as they arise, often by using semantic information and, though undesirable, sometimes by human intervention. BASE semantics are desirable in cases where approximate answers delivered quickly are more useful than exact answers delivered slowly.

3) Paper summaries

To better understand different approaches to caching strategies, this section will summarize four papers describing research work done over the past few years at Rutgers, CMU and the Xerox Palo Alto Research Center. As mentioned earlier, most of these approaches are based on the idea of trading consistency for availability, though each paper attacks a different part of the problem.

a) “Replication and Mobility”, B. R. Badrinath and T. Imieliński. Department of Computer Science, Rutgers University

The premise of this paper is that mobility is the next most challenging issue facing distributed systems and thus an important area of research. This paper raises (though it does not answer) the following questions:

 What are the conditions under which we need replication?

 What objects do we want to replicate? At which level do we replicate data? Do we replicate dynamically changing information such as location information?

 How does mobility affect users and their usage patterns? How do you design systems that allow data to follow users intelligently?

In order to be able to compare different strategies, one must understand the associated costs of each technique. Badrinath and Imieliński make the observation that in mobile systems, the cost of looking for data on a central, fixed server (a “location server”) and the cost of finding data on mobile clients or servers is highly asymmetrical. In particular, it is relatively simple and inexpensive for clients to locate a fixed server, while it is expensive for the location server to locate mobile clients because they may be constantly moving and are only intermittently connected. In their model, a mobile architecture is built up of a three-tier system – fixed location servers, or access points, are immobile and have permanent connectivity. Each access point typically handles a group of base stations, which might be thought of as PCs to which mobile devices connect and communicate. Finally, mobile units consist of servers and clients. Each server and client is associated with a “home location server.” Mobile units may move from one base station to another, but are assumed to stay within the range of a single location server. With this model in mind, the authors enumerated six different caching/replication strategies:

i) The server replicates the copy of the data at the mobile client. On each write, the server needs to write to the copy on the mobile client. Writing requires locating the mobile client. Reading is from a local copy on the mobile client.

ii) The replicated copy resides at the location server of the client. Thus, the client reads from its own location server. Here, reads and writes are on static copies. However, the copy is closer to the reader than the writer.

iii) The server has a copy of the data at its home location server. The client reads from this server. Thus, reading and writing is on static remote copies.

iv) The server has a cached copy at its home location server. Location server copy is invalidated upon the first write since the last read request from the client. Reading an invalid cache will require locating the mobile server. However, if the cache is valid then the read takes place from the copy at the location server

v) A cache of the server's copy exists at the client's location server. Location server copy is invalidated upon the first write since the last read request from the client. Reading an invalid cache will require locating the mobile server. However, if the cache is valid then the read takes place from the copy at the location server.

vi) The cache is maintained at the mobile client. If there was a read since the last update, the server upon each write sends invalidation message to the mobile client. If client wants to read and the cache is invalidated, then the mobile server is contacted to complete the read.

Some preliminary results on se strategies were presented, pointing to the (obvious) fact that the optimal strategy to choose depends on the range of mobility needed and the ratio of read vs. write activity desired.

b) Mobile Information Access”, M. Satyanarayanan. School of Computer Science, Carnegie Mellon University

Satyanarayanan argues that the barrier to mobile information access is not hardware limitations, but rather, in software support. There is no software available today that will allow a user to easily move from one environment to another while continuing to work on the same piece of information that exist at some remote location. Satyanarayanan’s main and most famous work is with the Coda filesystem. While Coda was designed as a filesystems and thus with slightly different assumptions, a lot of the ideas are still using for mobile database caching and replication.

The author identifies several intrinsic constraints on mobile systems in order to motivate the design of the Coda filesystem and the Odyssey system for mobile information sharing.

i) mobile elements are always resource-poor as compared with static elements

ii) mobility is inherently dangerous (it is easier to steal a small, mobile device than something anchored to a desk)

iii) mobile connectivity is highly variable in terms of performance and reliability

iv) mobile elements rely on finite resource (battery, etc)

Within this context, the Coda and Odyssey projects attempt to address issues of scalability and diversity. Scalability is desirable as mobile computing become more pervasive. Diversity refers to the fact that data that users wish to access are often diverse in form and that techniques which exploit semantic information within the data are often useful.

Coda is a descendant of AFS, both of which were filesystems developed at CMU. Although they share certain similarities, Coda is designed explicitly to support mobile users. To this end, Coda supported the notion of “disconnected operation” – clients have read/write access to data in their caches even when they are disconnected from the network. To support disconnected operation, any client on the Coda network moves between three states: hoarding, emulating, and reintegrating.

 Hoarding: during normal usage, the system predicts which pieces of data the client might need to ensure that they will be cached before disconnection. A user can also explicit specify data (files) to be cached.

 Emulating: when a client has disconnected from the server, requests for data must be serviced solely from the cache. Cache misses appear as failures to applications, and persistence of write operations is maintained by keeping a log file of what the user has changed.

 Reintegrating: upon reconnection, a reintegration process kicks in which tries to automatically assimilate changes made during disconnected usage. This process uses application-specific resolvers (ASRs) to help resolve conflicts. Unresolvable conflicts are presented to the user for manual integration.

Coda’s optimistic replica control strategy allows full read/write access during disconnected operation. By using application-specific resolvers, semantic information is exploited to allow multiple access to the same data resource while minimizing conflicts. When conflicts do occur, they can usually be resolved in a “smart”, application-dependent manner. The claim is that this allows finer-granularity access to data while preserving their integrity.

While Coda was originally designed for disconnected usage, in many mobile applications one might also be interested in weakly-connected operation – for example, when connection reliability or performance is low. Several extensions to Coda have been developed to take advantage of weak-connectivity:

 Rapid cache validation: similar to the idea of multiple level locks – instead of validating data one piece at a time, organize data into groups and maintain modification information at the group level. If a group has not changed, then neither have its members.

 Trickle reintegration: allows operation to start more quickly after reconnection, without waiting for reintegration to complete

 User-assisted cache-miss handling: uses a “user patience model” to decide when it’s worthwhile to pull in large files over a slow link, and when it should just be reported as being not available

 Isolation-only transactions support: provides the notion of read-write file conflicts and “psuedo-transaction” support for filesystem accesses. The idea here is that if a disconnected user writes to a record B based on record A in her cache, but record A has changed while she is disconnected, then upon reconnected, the user should be informed that record B may need to be updated.

Since Coda relies extensively on a cache, good performance requires that locality in the data to be accessed. This may not be suitable for some applications, such as web searches or some database operations.

Odyssey is a system designed to address some of the shortcomings of Coda when applied to smaller mobile devices. The new idea here is to use application-aware adaptation. For example, for things like images and video, the “fidelity” of the object can be adjusted according to connectivity characteristics. At the time this paper was written, a simple skeletal implementation of Odyssey existed and was used for some simple experiments. Performance was “modest” but is being improved over time.

c) “The Bayou Architecture: Support for Data Sharing among Mobile Users”, Alan Demers, Karin Petersen, Mike Speitzer, Douglas Terry, Marvin Thiemer, Brent Welch. Xerox Palo Alto Research Center

Bayou is a platform being developed at Xerox PARC which plans to provide replicated, highly-available, variable-consistency mobile databases for building collaborative, mobile applications.

Bayou is a client-server architecture – servers are responsible for storing data and clients read and write data. Unlike Coda, however, Bayou does not maintain a strong distinction between clients and servers. Mobile systems may act as servers for some databases and clients for others. This allows the formation of adhoc groups. For example, if a group of people (each with a mobile device) get together, they can share information that is available on each of the devices without needing an external server.

The Bayou architecture uses BASE semantics (though the BASE terminology comes after Bayou’s introduction). Servers maintain weakly consistent replication which is guaranteed to reach eventual consistency. Essentially, the technique used to allow read all/write all access is similar to that employed in Coda. Bayou uses a “peer-to-peer anti-entropy” protocol to propagate updates. Updates done at one server is replicated to all other servers. In other to maintain consistency, there is a requirement that servers process updates in the same order.

Like Coda, updates to the database can be processed incrementally to improve response time upon connection. Also like Coda, Bayou can detect update conflicts by performing dependency checks on writes. Bayou also uses application-specific methods for detecting and resolving conflicts, but it is more flexible than Coda in that conflict detection and resolution may be done on a write-by-write basis, rather than on a per-file basis as in Coda.

In order to preserve a high level of consistency, the Bayou system attempts to write committed data to servers as soon as possible to minimize inconsistencies. In order to write updates, the various servers with replicated data must agree on an order in which to process the write requests. Bayou uses the notion of primary and secondary servers in order to order writes. There is a single primary at any time in the system which has the final say on write ordering. Secondary servers receive write requests from the mobile clients and propagate them as “tentative” writes to the primary server. Once an ordering is established by the primary, the write is marked as committed. Mobile systems can query whether their writes are tentative or committed and make decisions about future actions accordingly.

Although writes may be tentative, clients might still wish to see their own updates while they continue processing other data. In order to support this, Bayou servers maintain two views of a database: one that contains only committed data, and one “full” database containing tentative changes as well. Moreover, clients (and applications) can select the type of “session guarantees” that they desire:

 read your writes – read operations reflect earlier writes (possibly at another server)