Karteikarten
CONCURRENCY CONTROL
Karten in diesem Stapel (35)
- 1What is concurrency control?Concurrency control deals with the isolation and consistency properties of transactions.
Ensuring transaction consistency on the
other hand, is the objective of concurrency control mechanisms
Concurrency control is the problem of synchronizing concurrent transactions such that the consistency of
the database is maintained while, at the same time, maximum degree of concurrency is achieved.
It tries to solve the problems : - lost updates
- inconsistent
retrievals - 2What is an Execution history?A history R (also called a schedule) is an order in which the operations of a set of transactions are
executed. It is defined over a set of transactions
T = {T1
,T2
, …,Tn} - 3What is serial history?If in a complete history H, the operations of various transactions are not interleaved (i.e., all the actions of
a transaction occur consecutively), the history is said to be serial.
If each transaction is consistent (i.e., obeys integrity rules), then the database is guaranteed to be
consistent at the end of executing a serial history.
- 4What is serializable history?Serilizable history is an order of transactions that execute concurrently, but the net effect of the resulting
history upon the database is equivalent to some serial history with respect to conflicting operations. In other words,
A schedule S is said to be serializable if and only
if it is conflict equivalent to a serial schedule. - 5What is conflict equivalence and conflicting operations with regards to serializable history?If the relative order of execution of the conflicting operations belonging to unaborted transactions in two
histories are the same, the two histories are said to be conflict equivalence. Conflicting operations
means two incompatible operations (e.g., Read and Write) if they both access the same data item.
Note that read operations do not conflict with each other, thus the
ordering of two read operations is insignificant. - 6What is a precedance graph for serializability?The precedence graph for a schedule S contains:
A node for each committed transaction in S
An arc from Ti
to Tj
if an action of Tiprecedes and conflicts with one of Tj
's actions.
It is used to test serializable schedules, e.g., the history (schedule) is conflict serializable if there is acyclic
(no cycles), and it is not conflict serializable if there is a cycle through the committed transactions.
For each transaction Ti
participating in the schedule S, create a node labelled Ti
. If Tj
executes a read
operation after Ti
executes a write operation on any data item, create an edge from Ti
to Tj
(Ti
→ Tj
). If Tj
executes a write operation after Ti
executes a read operation on any data item, also create an edge from
Ti
to Tj
(Ti
→ Tj
). If Tj
executes a write operation after Ti executes a write operation on any data item,
create an edge from Ti
to Tj
(Ti
→ Tj
). Note that Read-Read is not considered as conflicting. - 7What is to be considered of serializable history for distributed database management system?local histories
and global history: If the
database is not replicated and each local history is serializable, their union (called the global history) is
also serializable as long as local serialization orders are identical.
- 8What are different types of concurrency algos?f twophase
locking-based (2PL) algorithms, timestamp ordering (TO) based algorithms, and hybrid
algorithms - 9What are concurrency control with locking method?The main idea of locking-based concurrency control is to ensure that a data item that is shared by
conflicting operations is accessed by one operation at a time. This is accomplished by associating a "lock"
with each lock unit. This lock guarantees exclusive use of a data item to a current transaction and is
required to prevent another transaction from reading inconsistent data.
, the scheduler is a lock manager (LM). The transaction manager passes to the
lock manager the database operation (read or write) and associated information (such as the item that is
accessed and the identifier of the transaction that issues the database operation). The lock manager then
takes responsibility for assigning and managing the locks used by transactions. - 10What are different levels of lock?: (1) database-level lock where entire
database is locked; (2) table-level lock where entire table is locked; (3) page-level lock where entire
diskpage is locked; (4) row-level lock that allows concurrent transactions to access different rows of same
table, even if rows are located on same page; (5) field-level lock that allows concurrent transactions to
access same row, as long as they require use of different fields (attributes) within that row. - 11what are the different lock modes?er read lock (rl) [also
called shared lock] or write lock (wl) [also called exclusive lock] - 12When are 2 lock modes compatible?Two lock modes are compatible if
two transactions that access the same data item can obtain these locks on that data item at the same
time. read locks are compatible, whereas read locks and write locks conflict
(because Read and Write operations are incompatible). - 13Explain 2 phase locking.he two-phase locking rule simply states that no transaction should request a lock after it releases one of
its locks (should not release a lock until it is certain that it will not request another lock). A transaction
locks an object before using it. When an object is locked by another transaction, the requesting
transaction must wait. When a transaction releases a lock, it may not request another lock. - 14How does 2pl transaction execute?2PL algorithms execute transactions in two phases. Each transaction has a growing phase, where it
obtains locks and accesses data items, and a shrinking phase, during which it releases locks. The lock
point is the moment when the transaction has achieved all its locks but has not yet started to release any
of them.
- 15What is cascading aborts?it is difficult for the lock manager to know that the transaction has obtained all its locks and will
not need to lock another data item. The lock manager also needs to know that the transaction no longer
needs to access the data item in question, so that the lock can be released. Finally, if the transaction
aborts after it releases a lock, it may cause other transactions that may have accessed the unlocked data
item to abort as well. This is known as cascading aborts. - 16What is strict 2PL?hold locks until the end and releases all the locks together when the transaction
terminates (commits or aborts)
- 17What is centralized 2PL?2PL algorithm discussed in the preceding section can easily be extended to the distributed DBMS
environment. One way of doing this is to delegate lock management responsibility to a single site only.
This means that there is only one 2PL scheduler in the distributed system and lock requests are issued to
the central scheduler.
This communication is between the transaction
manager at the site where the transaction is initiated (called the coordinating TM), the lock manager at
1 CONCURRENCY CONTROL
11
the central site, and the data processors (DP) at the other participating sites. The participating sites are
those
that store the data item and at which the operation is to be carried out. - 18What is distributed 2PL?Distributed 2PL (D2PL) requires that 2PL schedulers are placed at each site and each scheduler handles
lock requests for data at that site. A transaction may read any of the replicated copies of item x, by
obtaining a read lock on one of the copies of x. Writing into x requires obtaining write locks for all copies
of x
- 19What is the primary copy 2PL?As for the primary copy 2PL protocol, when data is replicated, one copy is selected as the primary copy.
Lock management is implemented at several sites and each site is responsible for managing a number of
locks. During transaction, the primary copy of data is located and the lock request is sent to the
responsible lock manager. During any updates, the primary copy will be locked and then all the changes
will be reflected to the other copies - 20Whats timestamp ordering?The transaction manager assigns each
transaction Ti
a globally unique timestamp, ts(Ti
), at its initiation Transaction manager attaches the
timestamp to all operations issued by the transaction. Each data item is assigned a write timestamp (wts)
and a read timestamp (rts):
rts(x) = largest timestamp of any read on x
wts(x) = largest timestamp of any write on x
With this information, it is simple to order the execution of the transactions' operations according to their
timestamps. Conflicting operations are resolved by timestamp.
A scheduler that enforces the TO rule
checks each new operation against conflicting operations that have already been scheduled. If the new
operation belongs to a transaction that is younger than all the conflicting ones that have already been
scheduled, the operation is accepted; otherwise, it is rejected, causing the entire transaction to restart
with a new timestamp. - 21What is basic Timestamp ordering?A read request is handled in the following manner:
If TS < W-ts(x) then
reject read request and abort corresponding transaction
else
execute transaction
Set R-ts(x) to max{R-ts(x), TS}
A write request is handled in the following manner:
If TS < R-ts(x) or TS < W-ts(x) then
reject write request
else
execute transaction
Set W-ts(x) to TS.
If a transaction is aborted, it is restarted with a new timestamp. This can result in a cyclic restart where a transaction can repeatedly restart and abort without ever completing. Another disadvantage is that it has storage overhead for maintaining timestamps ( two timestamps must be kept for every data object). - 22what is conservative timestamp ordering?Adv - avoids too many restarts like basic TO ordering
Cons: - delay may result in the formation of deadlocks.
The conservative TO algorithms attempt to lower this system overhead by reducing the number of
transaction restarts. Conservative timestamping delays each operation until there is an assurance that it
will not be restarted, which means that no other operation with a smaller timestamp can arrive at the
scheduler - 23Advantages and cons of timestamp ordering?con- --may cause starvation - if older timestamp may keep coming and get rejected.
--cascade aborts may happen
not recoverable cuz allowed allowed particular transaction to read and write and it may commited and not aborted if later its realized that it should not have been allowed to commit.
adv- conflict serializable
no deadlock - 24...multiversion timestamp ordering??Multiversion TO is another attempt at eliminating the restart overhead cost of transactions. In
multiversion TO, the updates do not modify the values in the database, but create new values. Each
version of that data item is marked by the timestamp of the transaction that creates it. In doing so, it
processes each transaction on a state of the database that it would have seen if the transactions were
executed serially in timestamp order. The operations are processed by the histories as follows:
1.A Ri
(x) is translated into a read on one version of x. This is done by finding a version of x (say xv
) such
that ts(xv
) is the largest timestamp less than ts(Ti
). Ri
(xv
) is then sent to the data processor to read xv
.
2. A Wi
(x) is translated into Wi
(xw) and accepted if the scheduler has not yet processed any Rj
(xr
) such that
ts(Ti
) < ts(xr
) < ts(Tj
)
- 25Optimistic concurrency control algos are..?delay the validation phase until just before the write phase(sequence of phases: validation (V), read (R),
computation (C), write (W)).
Thus an operation submitted to an optimistic scheduler is never delayed. The read, compute, and write
operations of each transaction are processed freely without updating the actual database. Each
transaction initially makes its updates on local copies of data items.s. The validation phase consists of
checking if these updates would maintain the consistency of the database. If the answer is affirmative,
the changes are made global (i.e., written into the actual database). Otherwise, the transaction is aborted
and has to restart.
- 26Difference between optimistic and pessimistic CA?pessimistic in nature. In other
words, they assume that the conflicts between transactions are quite frequent and do not permit a
transaction to access a data item if there is a conflicting transaction that accesses that data item. Thus
the execution of any operation of a transaction follows the sequence of phases: validation (V), read (R),
computation (C), write (W). But for optimistic the sequence is read (R),
computation (C), validation (V), write (W). - 27Compare different types of timestamp orderings...?Look at other flashcards and think and recollect. lol no more spoonfeeding.
- 28Doubt... in conservative timestamp ordering how does delaying help? if Transaction is not restarted then why would it be accepted when faced the same conditions as before? since its timestamp will be older?Ask someone
- 29What is deadlock?A transaction is deadlocked if it is blocked and will remain blocked until there is intervention. As we
indicated before, any locking-based CC (concurrency control) algorithms may cause deadlocks, since
there is mutual exclusion of access to shared resources (data) and transactions may wait on locks. TObased
algorithms that involve waiting may also cause deadlocks - 30how can we analyze deadlocks?A useful tool in analyzing deadlocks is a wait-for graph (WFG). A WFG is a directed graph that represents
the wait-for relationship among transactions. If transaction Ti
waits for another transaction Tj
to release a
lock on an entity, then an edge Ti
→ Tj
exists in the WFG. A deadlock occurs when the WFG contains a
cycle.
- 31how can we analyze deadlocks in DDBS?transactions that participate in a deadlock condition may be running at different sites. We call this
situation a global deadlock. it is also necessary to form a global wait-for graph
(GWFG), which is the union of all the LWFGs.
Example :
- 32How many approaches to deadlock management?ignore, prevention, avoidance, and detection and
resolution.
Ignore approach simply lets the application programmer deal with it, or restart the system. Prevention
guarantees that deadlocks can never occur in the first place, checking transaction when it is initiated and
requiring no run time support. Avoidance detects potential deadlocks in advance and taking action to
insure that deadlock will not occur, which requires run time support. Detection and Recovery allows
deadlocks to form and then finding and breaking them. As in the avoidance scheme, this requires run
time support. - 33What are different types of Deadlock Avoidance approaches?Wait-Die Algorithm :
if ts(Ti
)ts(Tj
), then Ti
is aborted and restarted with the same timestamp.
WAIT-DIE is a non-preemptive algorithm, which means that Ti
never preempts Tj
, and it prefers younger
transactions.
Wound-Wait Algorithm
:
if ts(Ti
) - 34What is general deadlock detection and resolution method?Detection is done by studying the
GWFG for the formation of cycles. Resolution of deadlocks is typically done by the selection of one or
more victim transaction(s) that will be preempted and aborted in order to break the cycles in the GWFG. - 35What are different deadlock detection topologies>?centralized, hierarchical,
and distributed.
CENTRALIZED: one site is designated as the deadlock detector for the
system. Each scheduler periodically sends its local WFG to the central site which merges them to a global
WFG to determine cycles. The length of intervals for transmitting this information is a system design
decision: if it is too often, it results in higher communication cost but lower delays in detecting
deadlocks; if it is too late, it leads to higher delays in detecting deadlocks, but lower communication cost.
eg. Distributed INGRES
SUITABLE WHEN? - concurrency control algorithm is also
centralized
Hierarchical Deadlock Detection:
Involves building of a hierarchy of deadlock detectors. Each site also
sends its LWFG to the deadlock detector at the next level enabling it to detect deadlocks.
Distributed Deadlock Detection:
delegate the responsibility - individual
siteseach site receives the potential deadlock cycles from other sites from their WFG and adds it to their LWFG helping them detect deadlocks and pass info to other sites.
Informationen
- Beschreibung
- Distributed Database Karteikarten am CONCURRENCY CONTROL, erstellt von Varun m am 30/05/2017.
- Erstellt von
- Varun m
- Aufrufe
- 2
- Bewertung