⌘ '

raccourcis clavier

Transaction

concurrency

inter-leaved processing: concurrent exec is interleaved within a single CPU.

parallel processing: process are concurrently executed on multiple CPUs.

"\\usepackage{tikz}\n\\usetikzlibrary{arrows.meta, positioning}\n\n\\begin{document}\n\\begin{tikzpicture}[font=\\small, node distance=1.5cm, >=latex]\n\n%------------------------------\n% Interleaved Processing\n%------------------------------\n\n% Place the title higher up\n\\node[font=\\bfseries, align=center] (interleavedTitle) at (5, 1) {Interleaved (Time-Sliced) Processing};\n\n% Draw the timeline axis lower down\n\\draw[->] (-0.5,2) -- (10,2) node[below]{Time};\n\n% Processes above the time line\n% P1 intervals\n\\draw[fill=blue!30] (0,2.4) rectangle (2,3) node[midway]{P1};\n\\draw[fill=blue!30] (4,2.4) rectangle (6,3) node[midway]{P1};\n\\draw[fill=blue!30] (8,2.4) rectangle (9.5,3) node[midway]{P1};\n\n% P2 intervals\n\\draw[fill=red!30] (2,2.4) rectangle (4,3) node[midway]{P2};\n\\draw[fill=red!30] (6,2.4) rectangle (8,3) node[midway]{P2};\n\n%------------------------------\n% Parallel Processing\n%------------------------------\n\\begin{scope}[yshift=-1cm]\n\n% Title for parallel processing\n\\node[font=\\bfseries, align=center] (parallelTitle) at (5,-3.2) {Parallel (Concurrent) Processing};\n\n% Timelines for parallel processing\n\\draw[->] (-0.5,-1) -- (10,-1) node[below]{Time};\n\\draw[->] (-0.5,-2.5) -- (10,-2.5) node[below]{Time};\n\n% Process 1 on core 1 (above the -1 line)\n\\draw[fill=blue!30] (0,-0.6) rectangle (9.5,-0.0) node[midway]{P1 running on Core 1};\n\n% Process 2 on core 2 (above the -2.5 line)\n\\draw[fill=red!30] (0,-2.1) rectangle (9.5,-1.5) node[midway]{P2 running on Core 2};\n\\end{scope}\n\n\\end{tikzpicture}\n\\end{document}"

source code

ACID

atomic: either performed in its entirety (DBMS’s responsibility)
consistency: must take database from consistent state $X$ to $Y$
isolation: appear as if they are being executed in isolation
durability: changes applied must persist, even in the events of failure

Schedule

Venn diagram for schedule

definition

a schedule $S$ of $n$ transaction $T_{1}, T_{2}, \ldots, T_{n}$ is an ordering of operations of the transactions subject to the constrain that

For all transaction $T_i$ that participates in $S$ , the operations of $T_i$ in $S$ must appear in the same order in which they occur in $T_i$

For example:

S_a: R_{1}(A),R_{2}(A),W_{1}(A),W_{2}(A),\text{Abort1},\text{Commit2};

serial schedule: does not interleave the actions of different transactions
equivalent schedule: effect of executing any schedule are the same

serialisable schedule

a schedule that is equvalent to some serial execution of the set of committed transactions

serial

serialisable schedule

Note that this is not a serial schedule, given there are interleaved operations.

$S:R_1(A),W_1(A), R_2(A), W_2(A), R_1(B), W_1(B), R_2(B), W_2(B)$

conflict

operations in schedule

said to be in conflict if they satisfy all of the following:

belong to different operations

access the same item $A$

at least one of the operations is a write(A)

Concurrency Issue	Description	Annotation
Dirty Read	Reading uncommitted data	WR
Unrepeatable Read	T2 changes item $A$ that was previously read by T1, while T1 is still in progress	RW
Lost Update	T2 overwrites item $A$ while T1 is still in progress, causing T1’s changes to be lost	WW

conflict serialisable schedules

Two schedules are conflict equivalent if:

involves the same actions of the same transaction
every pair of conflicting actions is ordered the same way

Schedule $S$ is conflict serialisable if $S$ is conflict equivalent to some serial schedule

If two schedule $S_{1}$ and $S_{2}$ are conflict equivalent then they have the same effect $S_{1} \leftrightarrow S_{2}$ by swapping non-conflicting ops

Every conflict serialisable schedule is serialisable

on conflict serialisable

only consider committed transaction

schedule with abort

Note that this schedule is unrecoverable if T2 committed

However, if T2 did not commit, we abort T1 and cascade to T2

need to avoid cascading abort

if $T_i$ writes an object, then $T_j$ can read this only after $T_i$ commits

recoverable and avoid cascading aborts

Recoverable: a $X_\text{act}$ commits only after all $X_\text{act}$ it depends on commits.

ACA: idea of aborting a $X_\text{act}$ can be done without cascading the abort to other $X\text{act}$

ACA implies recoverable, not vice versa

precedent graph test

is a schedule conflict-serialisable?

build a graph of all transactions $T_i$
Edge from $T_i$ to $T_j$ if $T_i$ comes first, and makes an action that conflicts with one of $T_j$

if graphs has no cycle then it is conflict-serialisable

strict

if a value written by $T_i$ is not read or overwritten by another $T_j$ until $T_i$ abort/commit

Are recoverable and ACA

Lock-based concurrency control

think of mutex or a lock mechanism to control access to a data object

transaction must release the lock

notation

Li(A) means $T_i$ acquires lock for A, where as Ui(A) releases lock for A

Lock Type	None	S	X
None	OK	OK	OK
S	OK	OK	Conflict
X	OK	Conflict	Conflict

lock compatibility matrix

overhead due to delays from blocking; minimize throughput

use smallest sized object
reduce time hold locks
reduce hotspot

shared locks

$S_T(A)$ for reading

exclusive lock

$X_T(A)$ for write/read

strict two phase locking (Strict 2PL)

Each $X_\text{act}$ must obtain a S lock on object before reading, and an X lock on object before writing
All lock held by transaction will be released when transaction is completed

only schedule those precedence graph is acyclic

recoverable and ACA

Example:

T1	T2
L(A);
R(A), W(A)
	L(A); DENIED...
L(B);
R(B), W(B)
U(A), U(B)
Commit;
	...GRANTED
	R(A), W(A)
	L(B);
	R(B), W(B)
	U(A), U(B)
	Commit;

implication

only allow safe interleavings of transactions

$T_{1}$ and $T_{2}$ access different objects, then no conflict and each may proceed

serial action

two phase locking (2PL)

lax version of strict 2PL, where it allow $X_\text{act}$ to release locks before the end

a transaction cannot request additional lock once it releases any lock

implication

all lock requests must precede all unlock request

ensure conflict serialisability

two phase transaction growing phase, (or obtains lock) and shrinking phase (or release locks)

isolation

Isolation Level	Description
`READ UNCOMMITTED`	No read-lock
`READ COMMITTED`	Short duration read locks
`REPEATABLE READ`	Long duration read/lock on individual items
`SERIALIZABLE`	All locks long durations

Deadlock

cycle of transactions waiting for locks to be released by each other

usually create a wait-for graph to detect cyclic actions

wait-die: lower transactions never wait for higher priority transactions
wound-wait: $T_i$ is higher priority than $T_j$ then $T_j$ is aborted and restarts later with same timestamp, otherwise $T_i$ waits

concurrency

inter-leaved processing: concurrent exec is interleaved within a single CPU.

parallel processing: process are concurrently executed on multiple CPUs.

"\\usepackage{tikz}\n\\usetikzlibrary{arrows.meta, positioning}\n\n\\begin{document}\n\\begin{tikzpicture}[font=\\small, node distance=1.5cm, >=latex]\n\n%------------------------------\n% Interleaved Processing\n%------------------------------\n\n% Place the title higher up\n\\node[font=\\bfseries, align=center] (interleavedTitle) at (5, 1) {Interleaved (Time-Sliced) Processing};\n\n% Draw the timeline axis lower down\n\\draw[->] (-0.5,2) -- (10,2) node[below]{Time};\n\n% Processes above the time line\n% P1 intervals\n\\draw[fill=blue!30] (0,2.4) rectangle (2,3) node[midway]{P1};\n\\draw[fill=blue!30] (4,2.4) rectangle (6,3) node[midway]{P1};\n\\draw[fill=blue!30] (8,2.4) rectangle (9.5,3) node[midway]{P1};\n\n% P2 intervals\n\\draw[fill=red!30] (2,2.4) rectangle (4,3) node[midway]{P2};\n\\draw[fill=red!30] (6,2.4) rectangle (8,3) node[midway]{P2};\n\n%------------------------------\n% Parallel Processing\n%------------------------------\n\\begin{scope}[yshift=-1cm]\n\n% Title for parallel processing\n\\node[font=\\bfseries, align=center] (parallelTitle) at (5,-3.2) {Parallel (Concurrent) Processing};\n\n% Timelines for parallel processing\n\\draw[->] (-0.5,-1) -- (10,-1) node[below]{Time};\n\\draw[->] (-0.5,-2.5) -- (10,-2.5) node[below]{Time};\n\n% Process 1 on core 1 (above the -1 line)\n\\draw[fill=blue!30] (0,-0.6) rectangle (9.5,-0.0) node[midway]{P1 running on Core 1};\n\n% Process 2 on core 2 (above the -2.5 line)\n\\draw[fill=red!30] (0,-2.1) rectangle (9.5,-1.5) node[midway]{P2 running on Core 2};\n\\end{scope}\n\n\\end{tikzpicture}\n\\end{document}"

source code

ACID

atomic: either performed in its entirety (DBMS’s responsibility)
consistency: must take database from consistent state $X$ to $Y$
isolation: appear as if they are being executed in isolation
durability: changes applied must persist, even in the events of failure

Schedule

definition

a schedule $S$ of $n$ transaction $T_{1}, T_{2}, \ldots, T_{n}$ is an ordering of operations of the transactions subject to the constrain that

For all transaction $T_i$ that participates in $S$ , the operations of $T_i$ in $S$ must appear in the same order in which they occur in $T_i$

For example:

S_a: R_{1}(A),R_{2}(A),W_{1}(A),W_{2}(A),\text{Abort1},\text{Commit2};

serial schedule: does not interleave the actions of different transactions
equivalent schedule: effect of executing any schedule are the same

serialisable schedule

a schedule that is equvalent to some serial execution of the set of committed transactions

serial

serialisable schedule

Note that this is not a serial schedule, given there are interleaved operations.

$S:R_1(A),W_1(A), R_2(A), W_2(A), R_1(B), W_1(B), R_2(B), W_2(B)$

conflict

operations in schedule

said to be in conflict if they satisfy all of the following:

belong to different operations

access the same item $A$

at least one of the operations is a write(A)

Concurrency Issue	Description	Annotation
Dirty Read	Reading uncommitted data	WR
Unrepeatable Read	T2 changes item $A$ that was previously read by T1, while T1 is still in progress	RW
Lost Update	T2 overwrites item $A$ while T1 is still in progress, causing T1’s changes to be lost	WW

conflict serialisable schedules

Two schedules are conflict equivalent if:

involves the same actions of the same transaction
every pair of conflicting actions is ordered the same way

Schedule $S$ is conflict serialisable if $S$ is conflict equivalent to some serial schedule

If two schedule $S_{1}$ and $S_{2}$ are conflict equivalent then they have the same effect $S_{1} \leftrightarrow S_{2}$ by swapping non-conflicting ops

Every conflict serialisable schedule is serialisable

on conflict serialisable

only consider committed transaction

schedule with abort

Note that this schedule is unrecoverable if T2 committed

However, if T2 did not commit, we abort T1 and cascade to T2

need to avoid cascading abort

if $T_i$ writes an object, then $T_j$ can read this only after $T_i$ commits

recoverable and avoid cascading aborts

Recoverable: a $X_\text{act}$ commits only after all $X_\text{act}$ it depends on commits.

ACA: idea of aborting a $X_\text{act}$ can be done without cascading the abort to other $X\text{act}$

ACA implies recoverable, not vice versa

precedent graph test

is a schedule conflict-serialisable?

build a graph of all transactions $T_i$
Edge from $T_i$ to $T_j$ if $T_i$ comes first, and makes an action that conflicts with one of $T_j$

if graphs has no cycle then it is conflict-serialisable

strict

if a value written by $T_i$ is not read or overwritten by another $T_j$ until $T_i$ abort/commit

Are recoverable and ACA

Lock-based concurrency control

think of mutex or a lock mechanism to control access to a data object

transaction must release the lock

notation

Li(A) means $T_i$ acquires lock for A, where as Ui(A) releases lock for A

Lock Type	None	S	X
None	OK	OK	OK
S	OK	OK	Conflict
X	OK	Conflict	Conflict

lock compatibility matrix

overhead due to delays from blocking; minimize throughput

use smallest sized object
reduce time hold locks
reduce hotspot

shared locks

$S_T(A)$ for reading

exclusive lock

$X_T(A)$ for write/read

strict two phase locking (Strict 2PL)

Each $X_\text{act}$ must obtain a S lock on object before reading, and an X lock on object before writing
All lock held by transaction will be released when transaction is completed

only schedule those precedence graph is acyclic

recoverable and ACA

Example:

T1	T2
L(A);
R(A), W(A)
	L(A); DENIED...
L(B);
R(B), W(B)
U(A), U(B)
Commit;
	...GRANTED
	R(A), W(A)
	L(B);
	R(B), W(B)
	U(A), U(B)
	Commit;

implication

only allow safe interleavings of transactions

$T_{1}$ and $T_{2}$ access different objects, then no conflict and each may proceed

serial action

two phase locking (2PL)

lax version of strict 2PL, where it allow $X_\text{act}$ to release locks before the end

a transaction cannot request additional lock once it releases any lock

implication

all lock requests must precede all unlock request

ensure conflict serialisability

two phase transaction growing phase, (or obtains lock) and shrinking phase (or release locks)

isolation

Isolation Level	Description
`READ UNCOMMITTED`	No read-lock
`READ COMMITTED`	Short duration read locks
`REPEATABLE READ`	Long duration read/lock on individual items
`SERIALIZABLE`	All locks long durations

Deadlock

cycle of transactions waiting for locks to be released by each other

usually create a wait-for graph to detect cyclic actions

wait-die: lower transactions never wait for higher priority transactions
wound-wait: $T_i$ is higher priority than $T_j$ then $T_j$ is aborted and restarts later with same timestamp, otherwise $T_i$ waits

Transaction

Étiquette

publié à

modifié à

durée

source

concurrency

ACID

Schedule

serial

conflict

conflict serialisable schedules

schedule with abort

recoverable and avoid cascading aborts

precedent graph test

strict

Lock-based concurrency control

shared locks

exclusive lock

strict two phase locking (Strict 2PL)

two phase locking (2PL)

isolation

Deadlock

Vous pourriez aimer ce qui suit

Liens retour