Maintaining Cache Consistency with
Survey Paper
Abha Gupta
Department of Computer
Science
Why consistency is required in mobile
environments?
5. Classification of Approaches
5.1
Consistency at Mobile Client's Cache
5.2
Maintaining data consistency in mobile database
broadcasts
Abstract:
Mobile environments
involve accessing data from a
wireless network connection which is highly dynamic, unreliable and
insecure.
One of the major issues that wireless networks face is frequent
disconnections
of clients which may result in loss of data packets.
Caching is used in mobile networks to deal
with disconnections, but it is essential to ascertain that the client
cache
have the consistent and updated data. In this survey paper, I have
discussed
about some of the mechanisms that have been proposed
by researchers in the direction of data
consistency maintenance between the clients and the data servers.
Papers have
been classified with respect to the approaches that have been adapted
to
provide consistency.
Keywords: Cache Consistency, file
consistency, concurrency, serializabilty
in database
1. Introduction:
The increasing demand of mobile computing in the recent years have driven the need for developing advanced applications like real-time data update like stock rates, weather updates, news updates, location dependent information, electronic commerce etc. As most of these systems involve real-time processing of data, it becomes imperative to maintain connection between the mobile device and the data server to provide the required data to client. But, mobility cannot be compromised with remaining connected all the time. Mobile devices can be voluntarily or involuntarily disconnected from the network due to limited bandwidth, limited battery power or client may simply turn off the device. This may lead to loss of critical data if the device is ‘sleeping’ or moving into a new network area. To deal with such situations, data must be cached locally in mobile devices as well as in some intermediate level to provide better service to the users. The inconsistency is not only caused due to mobility of clients, but also changes occurring at the server. For example, database can change in the server at a time when client cannot have the access to the server.
2.Problem
Statement :
Why consistency is required in mobile environments?
Mobile environments are prone to data inconsistency between the server and the clients. This is because the clients access data from the data server which is not physically connected to clients as in wired networks. Whatever update is carried at the server may be lost or ‘missed’ by the clients if they are moving into an area where network is not available or if they are ‘sleeping’ at the time of updates sent by server. Moreover, client may also have a local cache that can store some amount of data that has been sent by the server for future use. This cache data in mobile cache should be consistent with the data in the data server in order to correctly serve the user. But, limited network bandwidth, low battery power and low processing power of mobile devices make them more vulnerable to inconsistencies. The inconsistency can be due to several reasons. It can be caused at the client side or server side.
For this survey, I have studied the data consistencies caused due to following :
· Clients: At client side, one reason for inconsistency can be mobile nature of clients, that is, they can be moving into a new cell, thus, losing the information that was sent by the server in the old cell. Limited battery power of mobile devices is another reason which makes users turn off the device voluntarily or involuntarily to save the battery consumption, thus, losing the updates sent by the server while it was ‘sleeping’. The inconsistency is caused at the local cache of the clients. 5 methods to deal with inconsistencies are discussed in this category.
· Servers: The server side inconsistency can be caused to database updates carried out at the server. This type of inconsistency is rectified by making sure that the database updates are serializable and that the clients are accessing the latest update values from the server. The inconsistency can also be caused due to message delays between the data server and client. 7 methods are discussed here.
Figure
1
The above given model depicts the system model of a mobile network. Data servers resides in the fixed networks where high network bandwidth is available. Mobile Service Stations (MSS) run on intermediate level and serves certain number of MUs on server’s behalf. The communication is carried out by sending messages.
5. Classification of Approaches
5.1 Consistency at
Data consistency in mobile cache has been a challenging issue and researchers have proposed several mechanisms to provide it for better usability of mobile devices. Some of them are mentioned as follows:
5. 1.1 CODA File System [1]: This
system was developed by the research
group Prof. M. Satyanarayan at
5.1.2 Invalidation Reports (IR) : This is a push-based data delivery carried out by data server. In this approach, the server broadcasts invalidation report in which the changed data items are indicated. Rather than querying the server directly regarding the validation of cached copies, the clients can listen to these IRs over the wireless channel, and use them to validate their local cache. The server can broadcast IRs periodically [2] or on-demand [3].
5.1.3 Periodic Broadcast of
Invalidation Reports: This technique was proposed by
[2] to ascertain that every mobile device receives the updated value of
all
data items that have been changed at the server. Since, IRs
arrive periodically, clients can go to sleep any time and can retrieve
the data
when they wake up. The drawback of this technique was latency time that
was
incurred due to long IR from the server. Further studies were performed
by [5]
in which the IR size was optimized to decrease the latency time of
cache
validations in the mobile cache.
.
5.1.4 On-Demand Broadcast of
Invalidation Reports: In this approach, the IRs
are received by the mobile devices only if they demand
for it. Two papers that I came across
dealing with on-demand broadcast of IRs are [2] [4]. The most general system model that
is used in these systems is shown below.
In this model, the data servers are on the top level and clients represents the low level.. The intermediate level contains a stationary service provider called Mobile Service Station (MSS) which serves a specific number of Mobile Unit (MU) in its cell. The data server sends the data updates, invalidity reports, timestamps for each data item and MSS forwards them to the MUs. MSS may send the data periodically to the MUs or whenever any MU demands for it.
In mobile environments, the server is stationary and is provided with a relatively high-bandwidth channel which supports broadcast delivery to all mobile clients located inside the geographical region (cell) it covers. An MSS is used to serve a specific number of Mobile Units (MU) on behalf of the data server. MSS helps in reducing heavy traffic between MUs and data servers and also provides a better communication. MUs may demand for data items from the MSS, which gets updated data items from the data server. Some MUs may require accessing to data items that are involved in database transactions at the data server, and hence they should have the latest value derived after the transaction carried out at data server. Some of the applications that may need database items are broadcasting stock updates, weather information, news updates etc. Such information can be highly dynamic and sensitive. Accessing out-dated data items is undesirable and will significantly affect the usefulness of the information to the mobile clients.
Some of the solutions addressing these issues have been discussed below:
5.1.5
Sleepers and Workaholics[2]
This paper was proposed to maintain data consistency between servers and the MUs by periodically sending Invalidation Reports (IR) from the data server to MUs for a data item. The server agrees to the obligation of notifying about the data items that have changed during last w seconds. Every data item is sent with a timestamp, which specifies the latest timestamp of that item in the data server. If the data item is present in MUs cache with an old timestamp, it is updated with this new timestamp that came along in the IR. This algorithm was quite effective in providing the data consistency between the data server and MU’s cache.
Drawback: but the only drawback was that periodic transfers of IRs produced heavy message traffic between the servers and MUs. Also, every MU would get the IRs for data items that they don’t even require.
5.1.6
Asynchronous Stateful (AS) [3]
This paper proposed an algorithm that used asynchronous call-backs for maintaining cache consistency. It uses call-back model and associate a Home Location Cache (HLC), with each MU to deal with the problem of disconnection. Each MSS maintains a distinct HLC for each MU in its cell and this home location cache is used to store additional information specific to each MU in the cell. HLC can be used to cache data even after prolonged period of disconnection of its MU from the network. Thus, no data is lost when the MU is sleeping or entering into a new cell. Whenever an item is update or invalidated at the data server, information is sent to MSS which stores the values in the HLC of the MU which is disconnected. When the MU wakes up, the data item can be retrieved from its HLC.
Drawback: Extra overhead on
MSS to maintain HLC.
5.1.7
Scalable Asynchronous Cache Consistency Scheme (SACCS) [4]
This paper proposes an algorithm to maintain
consistency between the data server and the MUs
by
using a flag bit for every data item. At any time, an MU can ask for a
data
item from the MSS or check whether data item x in its
cache is consistent with the data item in the data server.
The MSS can answer the query or confirm the validity of x by
comparing the timestamp of x
in MU’s cache and the timestamp provided
by the data
server. Whenever a query is issued for x
by any MU, the flag bit for x is set
to 1 in the MSS. If x has been
invalidated by the data server, the IR reports are sent by the MSS to
all MUs if flag bit for x
is set to one. Thus, only the information about data items queried by
any of
the MUs is sent by the MSS.
MU sets all its data items into uncertain
state every time it wakes up or enters into a new cell and asks the MSS
for
validity of data items present in its cache. If the items have been
invalidated,
MSS sends the IRs to MUs,
otherwise sends the valid data with new timestamp provided by the data
server.
Thus, no data is lost.
Advantage: This algorithm
is highly effective in
providing consistency of MU’s cache
without much of
overhead as only a single flag bit is used to distinguish between the
data
items which are required by the MUs and
which are
not. It also provides high degree or
scalability and cooperation among the MUs.
Scalability is provided as number of MUs
can be added
without much work, unlike AS scheme, in which an HLC has to be added
for every
MU added. Cooperation is increased between MUs
as
information about data item x can be shared by all MUs
present in the network even if one MU is requesting for x.
Disadvantage: The drawback of this
algorithm is message overhead that is caused between MSS and the MU.
Every time
an MU wakes up or enters into a new cell, it asks for confirmation of
its data
items and hence, every MU receives the information about data items
even if
they don’t need it.
5.1.8
Bit-Sequences [5]: This paper was proposed for the
database servers to optimize the size of the IRs
which were sent periodically to all the mobile clients. In this
algorithm, all
cache entries in mobile cache are deleted only when half or more of
data
entries in the cache have been invalidated. The server sends a set of
bit-sequences and each bit in the bit-sequence represents the data
item. The
position of the bit decides the indexes of the numbered data items. For
example, the nth bit in size N of sequence represents the data item dn. To indicate the update
status of the data item, each data item is associated with a timestamp.
A bit
“1” in sequence means that item represented by the bit has been updated
since
the time specified by the timestamp. A bit “0” means that data item has
not
been updated since the specified time
5.2 Maintaining data
consistency in mobile database broadcasts
The main issues that are
focused in mobile database systems are :
·
Serializability in databases
·
Concurrency
Control
5.2.1 Update First
with Order (UFO) [6]
This paper is addressed towards data
inconsistency
problem in data broadcast to mobile transactions. While
data items in a mobile computing system are
being broadcast, update transactions may install new values for the
data items.
If the executions of update transactions and broadcast of data items
are
interleaved without any control, the transactions generated by mobile
clients,
called mobile transactions, may observe
inconsistent
data values. Update First with Order
(UFO) algorithm can maintain the serializability
of
update transactions at the database server and the read-only mobile
transactions. Two important properties of the UFO algorithm are
(1) the mobile
transactions do not need to set
any lock before a data item is read from the “air”; and
(2) its impact on
the adopted broadcast
algorithm, which has been shown to be an efficient method for data
dissemination in mobile computing systems, is minimal.
Hence, it can be implemented on any
broadcast
algorithm.
In UFO,
the model is defined
based on the characteristics of the target application systems like
mobile
stock information systems. In these systems, the mobile clients are
palmtops,
wearable computers and notebooks. They generate short read-only
transactions to
retrieve information from the database servers, i.e., stock tickers,
sport news
and traffic conditions. The model consists of a base station (as
server),
mobile clients and low bandwidth network. Update transactions are
generated at
the server and to maintain the "freshness" of the data, values are refreshed. The update transactions are
time-stamped. The time -stamp is used to
indicate at which snapshot the update is generated. It is recorded with
the new
value into the data item as its version number.
The
database server
periodically broadcasts data items from the database one by one. In the model, each broadcast cycle is modeled
as a long read-only transaction called the broadcast
transaction (BT) .
The mobile
clients issue
transactions, called mobile transactions
(MT), to access data from the data server.
It is assumed that each MT is a set of data requests (read
operations)
and each MT is defined with a deadline. MT reads the BT during their
deadlines.
Transactions, which have missed their deadlines, might still be of some
use,
but beyond a certain time interval they would be considered totally
useless.
The period between the arrival time of a transaction and the time when
it is
considered to be useless is called drop
period.
The basic
principle of UFO
is that since mobile transactions read data items from broadcast
transactions,
the serialization order between a BT and a MT is always BT ® MT if they have any
conflicting data items. Thus,
serialization order between a conflicting update transaction and a
mobile
transaction will always be U ® MT (U stands for update) and the final
serialization graph will be serializable.
Although, UFO
can provide the most
updated values of data items to mobile transactions and at the same
time
maintain the serializability of the
execution between
update and mobile transactions; it is designed for read-only mobile
transactions in which operations are unordered.
Drawback: Only MTs
which are read-only can be operated.
Some enhancements have been introduced to
improve the
UFO scheme. Some of these are:
Modified UFO
[7]
- UFO algorithm is extended based on rule-base
approach for mobile transactions in which read-write operations can be
done.
- Enhancements based on an invalidation scheme
are done for accessing consistent data.
In the system model of this approach, every
MSS has a distributed
database system and database server resides on the server. The server
possesses
site autonomy and supports local transaction processing through
Two-Phase
Locking mechanism. Each MSS functions as a mobile transaction
coordinator,
which receives transaction operations from mobile clients and
coordinates their
execution. The
broadcast
process is modeled as a long read-only transaction, called broadcast
transaction. The length of a broadcast transaction is defined based on
the life
span of a mobile transaction that is equal to the time required
(deadline) to
broadcast its data items. Deadline of the mobile transaction and is
equal to
arrival time + life span. It is important to complete a mobile
transaction
before its deadline. Otherwise, it should be restarted.
How write is performed: The new values from the
write operations of a transaction are written in a private workspace of
the
transaction instead into the database immediately. When all the
operations of
the update transaction have been completed, it enters the commit phase
in which
permanent updates of the database will be performed by copying the new
values
from its private workspace into the database. Data conflict with the
broadcast
transaction will be checked in the commit phase, which is performed in
a
critical section.
5.2.2 Ordered UFO [8]
In
this paper, UFO method has been extended into Ordered UFO (OUFO) in
which a
mobile transaction consists of sequence of read operations. Besides
ensuring
consistency and maximizing currency of cached data, OUFO also aims at
reducing
the access delay of the mobile transactions.
Concurrency Control in
Broadcast Environments
Concurrency
control is a crucial consideration in broadcast environments.
Particularly
more, if an environment has limited bandwidth. Advanced applications in
such
environments do need to read data that is mutually consistent as well
as
current. Mutual consistency should ensure that
a)
the
server maintains
mutually consistent data and
b)
clients
can read mutually
consistent data.
Most of the researchers working in this
direction said that serializabily in
broadcast environments is quite
inapplicable. This is because
a) it requires excessive communication
between entities, to obtain
locks, for example
b) requires the
underlying protocol to be
overly conservative thus disallowing certain correct executions.
5.2.3 Matrix Implementation.[9]
this paper has introduced protocols to maintain mutual consistency
between the client and server data. These protocols permit read-only
transactions running on mobile clients to always read the current and
consistent values without contacting the server (to acquire locks or to
validate their reads). This is done by creating a control
matrix for data conflict resolution. This
matrix is
named as F-matrix (short for Full Matrix). For a database of n data
items, a
matrix of size n x n is used. In
each broadcast cycle, the server
broadcasts the latest committed values
of all data items at the beginning of the cycle. A mobile client
performs
consistency checking using the matrix before reading any data items
from the
“air”. The read operation at the client can proceed only if the control
information transmitted is up-to-date otherwise transaction is aborted.
This
method can handle read-only transactions as well as update
transactions. The
write operations are performed on local copies of the data items at the
client.
At the end of a transaction, the whole transaction including all of the
read
and write operations and the cycle numbers in which they are performed
will be
sent to the server for commitment. If the transaction has not performed
any
write operation at the client, then the commit operation does not have
to do
anything and commit succeeds. In case the transaction has performed a
write
operation, a list of all objects written and the values written are
sent to the
server.
5.2.4 Graphs Implementation
In this paper, non-serializability
is detected
by broadcasting serialization graphs. Each client maintains its local
serialization graph for a history H, denoted as SG(H), which is a
directed
graph whose nodes are the committee transactions in H and whose edges
are all
Ti -> Tj ( i
not equal to
j) such that one of the Ti’s operations precedes and conflicts with one of the Tj operations in H. This is because, according
to
serialization theorem, history H is serializable
iff SG (H) is acyclic. It is assumed that
each transaction
reads a data item before it writes it, that is, readset
of a transaction includes its writeset.
Then, there
can be two types of edges Ti -> Tj from
any
transaction Ti to any transaction Tj in
the
serialization graph: dependency edges that express the fact that Tj wrote an item that was previously read by Ti.
Conflict Serializability
[10]: Each
client maintains a copy of the
serialization graph locally. At each cycle, the server broadcasts any
updates
of the serialization graph. Upon receipt of the graph updates, the
client
integrates the updates into its local copy of the graph.
This approach has two drawbacks. First, there
is a heavy overhead in
broadcasting the serialization graphs since every data conflict at the
database
has to be broadcast. Second, each client must listen to the
transmission
channel continuously to maintain and update the serialization graph.
Invalidation Method[10]: This method
is similar to the broadcasting serialization graph except that
invalidation
reports are periodically broadcast before each broadcast cycle. The
invalidation report consists of a list that includes all the data items
that
are updated at the broadcast cycle. The validity of data items accesses
by a
mobile transaction is ensured by checking with the invalidation report.
A transaction
has to be restarted in case of its accessed data items are invalid.
Drawback: Starvation can happen
Multiversion broadcast [10]In this
approach, a multi-version
broadcast is proposed in which the server broadcasts previous versions
of data
items in addition to the committed version of the data items at the
last
broadcast cycle. This means that the values of items at the beginning
of the
last x broadcast cycles are
transmitted along with the version number that indicate the broadcast
cycle to
which each version corresponds. The value of x is
equal to S, the maximum transaction span among all read-only
transactions. When a mobile transaction wants to access a data item, it
will
get the latest version for its first read operation. The subsequent
read
operations of the transaction will read the data items with the largest
version
number which is smaller than or equal to
the data version of the first operation. By allowing a transaction
to read
an older version of a data item, data consistency can be ensured at the
expense
of currency, i.e. a mobile transaction may not receive the latest value
of a
data item.
Multiversion broadcast has two
variations:
1.
Broadcast with Fixed Periodicity [10]: In this variation, the broadcast is done
periodically by the server even when the data item is not updated
during a
cycle. Thus, for some data items, the same value may be repeated on the
broadcast. To eliminate this problem, client cache the data item
locally. For
each data item, versions are transmitted in reverse chronological
order, e.g.,
the most recent first. At each broadcast cycle, the server shifts the
data
values for each data item to the right and appends the new value at the
front.
During the i-th cycle of each read-only
transaction,
the client reads the data version at position S+1-i. There is a need to
broadcast version numbers, since the position of the value in the
broadcast
implies its version.
2.
Broadcast with Variable Periodicity:
In
this approach, a new value is added to the broadcast, only for data
items that
were updated during the previous broadcast cycle (Figure 1 (b)). In
this
version, a version number is sent along with each data value. At each
cycle,
the server discards the k-S, where k is the current broadcast cycle. At
least
one value is broadcast for each data item.
Comparison
Charts for consistency in mobile
cache model
|
|
Message Traffic |
Network Utilization |
Load on Server/MSS |
Good Performance during disconnections |
Duplication of data in the client cache |
Scalability of mobile clients |
Latency |
Serves the purpose of mobility |
|
CODA |
No |
Yes |
Yes |
Yes |
No |
Yes |
No |
Yes |
|
IR Push based |
Yes |
Yes |
Yes |
No |
Yes |
Yes |
No |
No |
|
Periodical Push based |
Yes |
Yes |
Yes |
No |
Yes |
Yes |
Yes |
No |
|
Bit Sequences |
Yes |
No |
No |
Yes |
No |
Yes |
No |
Yes |
|
Timestamp (TS) |
Yes |
Yes |
Yes |
No |
No |
Yes |
Yes |
Yes |
|
Asynchronos Stateful (AS) |
Yes |
Yes |
Yes |
Yes |
No |
No |
No |
Yes |
|
SACCS |
Yes |
Yes |
No |
Yes |
No |
Yes |
No |
yes |
Comparision chart for algorithms
performing consistency in database servers
|
|
Consistency |
Currency |
Serializibilty |
Overhead |
Read-Only or Write Only |
Locking of data item |
|
UFO |
Yes |
Yes |
Yes |
No |
Read-only |
No |
|
Modified UFO |
Yes |
Yes |
Yes |
No |
both |
Yes |
|
OUFO |
Yes |
Yes |
Yes |
No |
Read-only |
No |
|
Matrix Implementation |
Yes |
Yes |
No |
Yes |
both |
No |
|
Graph Implementation |
Yes |
Not necessarily |
Yes |
Yes |
Not specified |
No |
Conclusion:
The
amount of research in this area in the last few years has been
staggering. However, some problems
remain open for research. There is a need for better protocols in the
area of
data sharing, message delays, duplication of data at client caches and
transaction management,. Better interfaces, clever algorithms that
exploit
locality to shape the answers to queries.
[1]
CODA File System.
[2]
Barbara, Imielifiski, " Sleepers and Workaholics:
Caching Strategies in Mobile Environments"
[3] Khurana, Kahol,
Gupta. "A Strategy
to Manage Cache Consistency in a Distributed Mobile Wireless Environment"
[4] Zhijun
Wang, Sajal Das,
Hao Che and
Mohan Kumar, “Scalable
Asynchronous Cache Consistency Scheme (SACCS)”
[5] Jing, Elmagarmid Bit
Sequences: An Adaptive
Cache Invalidation method in client/server environment
[6] Kam-Yiu Lam, Mei-Wai
Au and Edward Chan "Broadcasting Consistent
Data to Read-Only Transactions
from Mobile Clients1"
[7]
A.J Seetha "Maintaining data
consistency in
mobile database broadcasts"
[8] Kam-Yiu Lam, Edward Chan, Hei-Wing
Leung and Mei-Wai Au
“Broadcasting Consistent
Data to
Mobile Clients with
Local Cache”
[9] Jayavel Shanmugasundaram, Arvind
Nithrakashyap "Efficient Concurrency
Control
for Broadcast Enviornments"
[10]Evaggelia
Pitoura,
“Supporting Read-Only
Transactions in
Wireless Broadcasting”