Distributed serializability and CO Commitment ordering
1 distributed serializability , co
1.1 distributed co
1.2 distributed optimistic co (doco)
1.3 examples
1.3.1 distributed ss2pl
1.3.2 variations
1.3.3 hypothetical multi single-threaded core (music) environment
distributed serializability , co
distributed co
a distinguishing characteristic of co solution distributed serializability other techniques fact requires no conflict information distributed (e.g., local precedence relations, locks, timestamps, tickets), makes uniquely effective. utilizes (unmodified) atomic commitment protocol messages (which used) instead.
a common way achieve distributed serializability in (distributed) system distributed lock manager (dlm). dlms, communicate lock (non-materialized conflict) information in distributed environment, typically suffer computer , communication latency, reduces performance of system. co allows achieve distributed serializability under general conditions, without distributed lock manager, exhibiting benefits explored above multidatabase environments; in particular: reliability, high performance, scalability, possibility of using optimistic concurrency control when desired, no conflict information related communications on network (which have incurred overhead , delays), , automatic distributed deadlock resolution.
all distributed transactional systems rely on atomic commitment protocol coordinate atomicity (whether commit or abort) among processes in distributed transaction. also, typically recoverable data (i.e., data under transactions control, e.g., database data; not confused recoverability property of schedule) directly accessed single transactional data manager component (also referred resource manager) handles local sub-transactions (the distributed transaction s portion in single location, e.g., network node), if these data accessed indirectly other entities in distributed system during transaction (i.e., indirect access requires direct access through local sub-transaction). recoverable data in distributed transactional system typically partitioned among transactional data managers. in such system these transactional data managers typically comprise participants in system s atomic commitment protocol. if each participant complies co (e.g., using ss2pl, or cocos, or combination; see above), entire distributed system provides co (by theorems above; each participant can considered separate transactional object), , (distributed) serializability. furthermore: when co utilized atomic commitment protocol distributed deadlocks (i.e., deadlocks span 2 or more data managers) caused data-access locking resolved automatically. following corollary concluded:
the co based distributed serializability theorem
let distributed transactional system (e.g., distributed database system) comprise transactional data managers (also called resource managers) manage system s recoverable data. data managers meet 3 conditions:
then
furthermore: data managers being co compliant necessary condition (distributed) serializability in system meeting conditions 1, 2 above, when data managers autonomous, i.e., not share concurrency control information beyond unmodified messages of atomic commitment protocol.
this theorem means when ss2pl (or other co variant) used locally in each transactional data manager, , each data manager has exclusive control of data, no distributed lock manager (which utilized enforce distributed ss2pl) needed distributed ss2pl , serializability. relevant wide range of distributed transactional applications, can designed meet theorem s conditions.
distributed optimistic co (doco)
for implementing distributed optimistic co (doco) generic local co algorithm utilized in atomic commitment protocol participants in system no data access blocking , no local deadlocks. previous theorem has following corollary:
the distributed optimistic co (doco) theorem
if doco utilized, then:
thus, no deadlock handling needed.
examples
distributed ss2pl
a distributed database system utilizes ss2pl resides on 2 remote nodes, , b. database system has 2 transactional data managers (resource managers), 1 on each node, , database data partitioned between 2 data managers in way each has exclusive control of own (local node) portion of data: each handles own data , locks without knowledge on other manager s. each distributed transaction such data managers need execute available atomic commitment protocol.
two distributed transactions,
t
1
{\displaystyle t_{1}}
,
t
2
{\displaystyle t_{2}}
, running concurrently, , both access data x , y. x under exclusive control of data manager on (b s manager cannot access x), , y under on b.
t
1
{\displaystyle t_{1}}
reads x on , writes y on b, i.e.,
t
1
=
r
1
a
(
x
)
{\displaystyle t_{1}=r_{1a}(x)}
w
1
b
(
y
)
{\displaystyle w_{1b}(y)}
when using notation common concurrency control.
t
2
{\displaystyle t_{2}}
reads y on b , writes x on a, i.e.,
t
2
=
r
2
b
(
y
)
{\displaystyle t_{2}=r_{2b}(y)}
w
2
a
(
x
)
{\displaystyle w_{2a}(x)}
the respective local sub-transactions on , b (the portions of
t
1
{\displaystyle t_{1}}
,
t
2
{\displaystyle t_{2}}
on each of nodes) following:
the database system s schedule @ point in time following:
r
1
a
(
x
)
{\displaystyle r_{1a}(x)}
r
2
b
(
y
)
{\displaystyle r_{2b}(y)}
(also
r
2
b
(
y
)
{\displaystyle r_{2b}(y)}
r
1
a
(
x
)
{\displaystyle r_{1a}(x)}
possible)
t
1
{\displaystyle t_{1}}
holds read-lock on x ,
t
2
{\displaystyle t_{2}}
holds read-locks on y.
w
1
b
(
y
)
{\displaystyle w_{1b}(y)}
,
w
2
a
(
x
)
{\displaystyle w_{2a}(x)}
blocked lock compatibility rules of ss2pl , cannot executed. distributed deadlock situation, voting-deadlock (see below) distributed (global) cycle of length 2 (number of edges, conflicts; 2 frequent length). local sub-transactions in following states:
t
1
a
{\displaystyle t_{1a}}
ready (execution has ended) , voted (in atomic commitment)
t
1
b
{\displaystyle t_{1b}}
running , blocked (a non-materialized conflict situation; no vote on can occur)
t
2
b
{\displaystyle t_{2b}}
ready , voted
t
2
a
{\displaystyle t_{2a}}
running , blocked (a non-materialized conflict; no vote).
since atomic commitment protocol cannot receive votes blocked sub-transactions (a voting-deadlock), abort transaction missing vote(s) timeout, either
t
1
{\displaystyle t_{1}}
, or
t
2
{\displaystyle t_{2}}
, (or both, if timeouts fall close). resolve global deadlock. remaining transaction complete running, voted on, , committed. aborted transaction restarted , re-executed.
comments:
variations
in scenario above both conflicts non-materialized, , global voting-deadlock reflected cycle in global wait-for graph (but not in global conflict graph; see exact characterization of voting-deadlocks global cycles above). database system can utilize co variant same conflicts , voting-deadlock situation, , same resolution. conflicts can either materialized or non-materialized, depending on co variant used. example, if sco (below) used distributed database system instead of ss2pl, 2 conflicts in example materialized, local sub-transactions in ready states, , vote blocking occurs in 2 transactions, 1 on each node, because of co voting rule applied independently on both , b: due conflicts
t
2
a
=
w
2
a
(
x
)
{\displaystyle t_{2a}=w_{2a}(x)}
not voted on before
t
1
a
=
r
1
a
(
x
)
{\displaystyle t_{1a}=r_{1a}(x)}
ends, ,
t
1
b
=
w
1
b
(
y
)
{\displaystyle t_{1b}=w_{1b}(y)}
not voted on before
t
2
b
=
r
2
b
(
y
)
{\displaystyle t_{2b}=r_{2b}(y)}
ends, voting-deadlock. conflict graph has global cycle (all conflicts materialized), , again resolved atomic commitment protocol, , distributed serializability maintained. unlikely distributed database system, possible in principle (and occurs in multi-database), can employ ss2pl while b employs sco. in case global cycle neither in wait-for graph nor in serializability graph, still in augmented conflict graph (the union of two). various combinations summarized in following table:
comments:
hypothetical multi single-threaded core (music) environment
comment: while examples above describe real, recommended utilization of co, example hypothetical, demonstration only.
certain experimental distributed memory-resident databases advocate multi single-threaded core (music) transactional environments. single-threaded refers transaction threads only, , serial execution of transactions. purpose possible orders of magnitude gain in performance (e.g., h-store , voltdb) relatively conventional transaction execution in multiple threads on same core. in described below music independent of way cores distributed. may reside in 1 integrated circuit (chip), or in many chips, possibly distributed geographically in many computers. in such environment, if recoverable (transactional) data partitioned among threads (cores), , implemented in conventional way distributed co, described in previous sections, doco , strictness exist automatically. however, downsides exist straightforward implementation of such environment, , practicality general-purpose solution questionable. on other hand, tremendous performance gain can achieved in applications can bypass these downsides in situations.
comment: music straightforward implementation described here (which uses, example, usual in distributed co, voting (and transaction thread) blocking in atomic commitment protocol when needed) demonstration only, , has no connection implementation in h-store or other project.
in music environment local schedules serial. both local optimistic co (oco; see below) , global co enforcement vote ordering strategy condition atomic commitment protocol met automatically. results in both distributed co compliance (and distributed serializability) , automatic global (voting) deadlock resolution.
furthermore, local strictness follows automatically in serial schedule. theorem 5.2 in (raz 1992; page 307), when co vote ordering strategy applied, global strictness guaranteed. note serial locally mode allows strictness , optimistic (no data access blocking) together.
the following concluded:
the music theorem
in music environments, if recoverable (transactional) data partitioned among cores (threads), both
automatically exist globally unbounded scalability in number of cores used.
comment: however, 2 major downsides, need special handling, may exist:
^ robert kallman, hideaki kimura, jonathan natkins, andrew pavlo, alex rasin, stanley zdonik, evan jones, yang zhang, samuel madden, michael stonebraker, john hugg, daniel abadi (2008): h-store: high-performance, distributed main memory transaction processing system , proceedings of 2008 vldb, pages 1496 - 1499, auckland, new-zealand, august 2008.
Comments
Post a Comment