Crisp Reading Notes on Latest Technology Trends and Basics

Archive for the ‘Relational Database’ Category

Lock Modes for the first “Lock Manager”

These are notes for VAX/VMS based “Distributed Lock Manager”, which is one of the first systems providing “Locks as a Service”. Most Database manager have followed a variant of this.

In this article, I explain the “Lock Modes”, which is a pluggable logic for the VAX/VMS version. This is a pluggable logic, that varies from System to System.

References

Lock-Modes

Basic Lock Modes

There are three basic Lock Modes

PR Protected Read In this mode, the Readers are guaranteed the data is stableie, There are no Writers changing the data
PW Protected Write In this mode, the Writer is guaranteed the data is stableie, There are no other Writers modifying the data
EX Exclusive In this mode, there is only one application.There are no Readers or Writers modifying the data

The Compatibility Matrix between these modes is as follows

 

PR

PW

EX

Having PR

Yes

No

No

Having PW

No

No

No

Having EX

No

No

No

Basic Non-Lock Modes

In these modes, the entities / threads do not need locks. To these applications, it does not matter what the other applications are doing.

However, this will dilute the commitment made to the other applications that have registered for “Protected Read” or “Protected Write”.

For this reason, these non-locking applications are required to state their Intent, before they execute on the specified operation. This is done by acquiring two weak locks – Concurrent Read (CR), or Concurrent Write (CW)

The two additional “Lock Modes” are

CR Concurrent Read In this mode, the application is allowed to read the dataHowever, no guarantees are made on the isolation
CW Concurrent Write In this mode, the application is allowed to write the dataHowever, no guarantees are made on the isolation

The Compatibility Matrix among these modes is as follows

 

CR

CW

PR

PW

EX

Having CR

Yes(3)

Yes(4)

Yes(3)

Yes(3)

No(2)

Having CW

Yes(3)

Yes(4)

No(1)

No(1)

No(2)

Having PR

Yes(3)

No(1)

Yes

No

No

Having PW

Yes(3)

No(1)

No

No

No

Having EX

No(2)

No(2)

No

No

No

An explanation of the various entries

  1. With a Concurrent Write, neither a Private Read, nor a Private Write is allowed
  2. With an Exclusive Lock, neither Concurrent Read, nor Concurrent Write is allowed
  3. A Concurrent Read is harmless, and is allowed with any lock except “Exclusive”.
  4. With a Concurrent Read, a Concurrent Write is allowed, since neither cares about isolations

Hierarchy

Resource Hierarchy

Each resource in the system is placed in a hierarchy

  • For a database the hierarchy may be
  1. Database
  2. Table
  3. Page
  4. Tuple
  • The hierarchy is usually known from the name of the resource. For example
//financial/expenses/17/85

 

Hierarchical Locking

 

  • Locks may be obtained on objects at all levels in the Object Hierarchy.  The rules for the same can also be specified as set of basic rules

Obtain a CR or CW at a higher level, before you obtain a PR or PW lock at the leaf node.

  • For example, to obtain a Write lock on the record
  1. Obtain CW lock on  Database – //financial
  2. Obtain CW lock on Table – //financial/expenses
  3. Obtain CW lock on Partition – //financial/expenses/
  4. Obtain CW lock on Page – //financial/expenses/17
  5. Obtain PW lock on Tuple – //financial/expenses/17/85

Hierarchical Unlocking

  • In order to avoid deadlocks, either
    • The locks are obtained at one-shot, or
    • The locks are released in reverse order – bottom to top.

Optimistic Timestamp – (on MVCC)

Timestamping with Multi-Version Concurrency Control

Overview

  • Multi-version Concurrency Control allows the designer to take snapshots, and verify their data at commit/abort time.
  • Every transaction goes through three phases
    • Read / Local Modify
    • Validation
    • Write
  • The Timestamp of each transaction Tiis created at Validation time
    • Note that it is not necessary to have timestamps while tracking Read/Write.

Terminology

ST(Ti) Starting time of Transaction Ti
TS(Ti) Validation time of Transaction Ti
RS(Ti) Read-set of Transaction Ti
WS(Ti) Write-set of Transaction Ti
  • Note that this is a Snapshot abstraction. Changes of Ti are not visible until Ti decides to commit.
  • While validating a Transaction,
    • Consider transactions that were active and have validated, since this transaction started

Backward Validation of Transaction

B(T) { Tj | Tjis active when T started, andTS(Tj) < TS(T), that is Tj preceeds T in timestamp ordering }
  • For each of these transactions Tj,
    • Transaction T should not have read from Tj
      • There should be no RS(T) à WS(Tj) dependency
      • This is because T would have picked up its snapshot before Tj wrote the values back
  • So, the algorithm is
sub validate(T) {valid ß truefor all Tj in B(T) {

if RS(T) ∩ WS(Tj) == Φ

valid ß false

}

}

Forward Validation of Transactions

  • In addition to the above technique of looking back at the transaction, we could look forward at the Transactions that are currently active.
  • If anything in the Write-Set of the current transaction has been read by the Transactions that have not yet got the Validation Timestamp, then
    • These transactions will most likely get aborted when they try to Commit
    • So, we could abort these new transactions right at this stage.

Backward Validation is required even if we use Forward Validations

  • Note that through “Forward Validations”, we do not know the Full Read-Set of the forward transactions
    • So, some of the Forward transactions may actually abort when they try to commit.
    • This check can be made only when the Forward transaction tries to Commit, and the check is a “Backward Validation”.
    • For this reason, “Forward Validation” is required, even if we use “Backward Validation”.

Why Forward Validations

  • Forward Transactions abort Active Transactions.
  • It is less expensive to abort “Validating Transactions”, as opposed to “Active Transactions”.

Distributed Optimistic Control

  • The “Validation Timestamps” have to be strictly ordered.
    • On multiple nodes, there needs to be a mechanism to generate strict ordering

Locking on a Single Node

  • Also, when we are validating a Transaction,
    • If there is only “Backward Validation”, no locking is needed
    •  For “Forward Validation”, locks are needed for the Read-Set and Write-Set of all items on the list

Conservative Timestamping

http://www.cs.cityu.edu.hk/~cs4404/08_occ_ts.ppt

http://www-i4.informatik.rwth-aachen.de/content/teaching/lectures/sub/vs/vsSS06/08_Transactions2_1P.pdf

Conservative Timestamp Ordering

Introduction

  • With Timestamp Ordering schemes, there is no Locking
  • We assign timestamps to Transactions and to data-items
  • We describe below, one of the techniques of Timestamping, which is conservative, and to a large extent, Single Versioned
  • I will add notes for Multi-Versioned Timestamping at a later point in time

Terminology

TS(Ti) Starting time of Transaction – Ti

The starting time forms the Id of the transaction

RTS(Oj) Read timestamp of item

The most recent transaction that have read the item

WTS(Oj) Write timestamp of item

The most recent transaction that have written the item

  • The reads and writes to the database are executed without locking
  • Instead, the following two conditions should be satisfied with each read/write

Read rule

  • If Ti reads Oj,
    • If WTS(Oj) > TS(Ti), a later transaction has written the data. So, abort current transaction
    • Else RTS(Oj) ß max( RTS(Oj), TS(Ti) ), and
      • add a dependency DEP(Ti ).add(WTS(Oj) à TS(Ti))

Write Rule

  • If Ti writes Oj,
    • If RTS(Oj) > TS(Ti), a later transaction has read data. So, abort transaction if Isolation level is Read Committed
    • If WTS(Oj) > TS(Ti), a later transaction has written the data. So, skip the write
    • Else
      • OLD(Ti).add(Oj,WTS(Oj))
      • update Oj

Commit Rule

  • It Ti wants to commit,
    • If there is a transaction in DEP(Ti)- an aborted transaction from which Tihas read data,
      • then abort the transaction
      • If there is a transaction in DEP(Ti), – a running transaction from which Tihas read data,
        • then either abort the transaction, or wait till the running transaction completes

Abort Rule

  • If Tiwants to abort,
    • For every item in <Oj,oldOj> in OLD(Ti), if WTS(Oj) = TS(Ti),
      • WTS(Oj) ß oldOj

Summary

Read from

Older Txn

Write from

Older Txn

Read from

Newer Txn

Write from

Newer Txn

Read Object OK OK OK Abort.

Cannot serialize

Write Object OK OK Abort.

Cannot serialize

OK

No overwriting

Older Txn Aborted Older Txn Committed Older Txn Pending
Commit OK

if no read dep

from older to newer

OK

 

Wait

On completion,

check for read dep or commit

Abort OK OK OK

Notes on wait state during commit

  • An observant reader will notice that there is a “Wait State” during the “Commit” of a transaction
  • This state could be easily engineered as an Abort action. In that case, the later transaction will also be forced to Abort, causing “Cascading Aborts”. This is something we seek to avoid

Database Normal Forms

http://www.bkent.net/Doc/simple5.htm#label4.1

First Normal Form

  • A Relational Database is a table of Atomic Values
  • Every record contains the same number of fields
  • Lists must be flattened out
  • The First Normal Form is responsible for causing various Redundancies, that other Normal Forms try to remove

Second Normal Form

  • Every non Primary-key column must fully depend on all the Primary-Key columns
  • If a Value column Vj depends on keys <K1, K2, …, Kn>,
    • then a separate table of < K1, K2, …, Kn, Vi >  must be created

Third Normal Form

  • There must be no dependencies among non Primary-Key fields
  • If a Value column Vi depends on column Vj, then
    • A separate table Vj must be created

Boyce-Codd Normal Form

  • There must be no dependencies from non-keys to any portion of the keys
  • That is, there must be no dependencies from the non-keys
  • Cannot decompose a 3NF to a BCNF, while preserving dependencies

Fourth Normal Form

  • Two independent multi-valued attributes must not be present in the same table
  • If keys <K1, K2, …, Kn > have two multi-valued columns Vi and Vj
    • Then separate tables – < K1, K2, …, Kn, Vi >  and < K1, K2, …, Kn, Vj > must be created

Fifth Normal Form

  • This applies to decomposition of a table with only keys
  • If there are multivalued relationships, among the candidate keys, then they may be decomposed into Fifth Normal Form.

Isolation Levels

This write-up will contain notes from the following reference.

http://www.cs.umb.edu/~poneil/iso.pdf

According to the reference, there are six types of isolation provided by Database Providers.

Two of these – Cursor Stability and Snapshot Isolation are variants of the four ANSI standards, because of ambiguity in the ANSI standards.

The paper also tries to map Execution History in terms of “Multi Version Concurrency Control”, which is a new concept.

Situation implemented Situation to avoid History to avoid Locks Required Avoided with Locks
Read Committed Read Uncommitted W1(x),R2(x), { C1 or C2 } Write Lock till Commit W1(x),R2(x),{ C1 or A1 or C2 or A2 }
Repeatable Read Write after Read R2(x),W1(x), C1, R2(x), { C1 or C2 } Read lock till Commit R2(x),W1(x),

Tag Cloud