Information Technology Reference
In-Depth Information
2.
Write actions
of the form WŒx;;
u
;
v
that retrieve the current version .x;
u
/ of
the tuple with key x (if any) and create a new version .x;
v
/ with timestamp .
If no timestamp is specified, a timestamp is generated (and returned) that is
greater than the timestamp for any existing version. If no version .x;
u
/ exists,
u
D?
.
3.
Check-and-write actions
of the form
CAW
Œx;
u
;
v
that check whether or not
.x;
u
/ is the current version of the tuple with key x and, if so, performs the write
action WŒx;
u
;
v
; otherwise, the write action is not performed and an error is
returned.
The check-and-write actions are used to eliminate inconsistencies arising from
unrepeatable reads: if an application first reads the latest version .x;
u
/ of a tuple
and later wants to create a new version .x;
v
/ where the new value
v
depends on the
read value
u
, the atomic action
CAW
Œx;
u
;
v
is used to create the new version. If the
action returns with error, the application knows that .x;
u
/ is no longer the current
version and hence must reconsider the update.
Some recent key-value-store management systems allow transactions with the
restriction that a transaction can only update a group of co-located tuples residing on
a single server. At the logical database level, this setting can be portrayed as follows.
We assume that our key-value store consists of a single relation r.
X
;
Y
;V/,where
each tuple .x; y;
v
/, identified by key .x; y/,representsan
entity
belonging to an
entity group
(also called a
key group
) identified by x.Thevaluesx of the attribute
set X thus divide the entire entity set into disjoint entity groups.
Such a key-value store is horizontally partitioned into many horizontal fragments
r
i
.
X
;
Y
;V/, each of which is composed of whole entity groups, so that for any
value x of X only one fragment contains tuples .x; y;
v
/ for some values y of Y
and
v
of V . Each fragment is placed in its entirety on a single server in a datacenter.
The tuples in the fragments stored on a server are organized as a clustered index
structure such as a sparse B-tree on key XY , which thus places the entities of an
entity group near each other.
A transaction on a key-value store must be declared either as a
read-only trans-
action
, in which case it cannot contain update actions, or an
updating transaction
on
agiven
entity group
x, in which case it can contain read actions (on any entities)
and update actions on entities in entity group x only. A set of updating transactions
on an entity group is called a
transaction group
.
As each entity group resides on a single server, each updating transaction on
that entity group updates only entities stored on that server, so that any transaction
either runs entirely on one server or is a distributed transaction consisting of a
single updating subtransaction (on the updating site) and one or more read-only
subtransactions (on the other sites). When no log records are written for read-only
transactions, all the log records generated by any transaction are found in the log
of a single server, assuming that the transaction is coordinated by the updating site,
and not some other, remote site. In any case, transaction coordination is expected to
be much more light-weight and efficient than in the case in which a transaction were
allowed to update entities in different entity groups residing on different servers.
