Client server databases and concurrent access

Many clients, one database: the lost update, and the four ways to prevent it: record locks, serialisation, timestamp ordering and commitment ordering.

A11.7Databases and big dataA level60 min

So far one program has owned each database. In a real club, every robot logs its runs to one shared database on the teacher's computer, the scoreboard on the projector reads it, and two teams can score at the same moment. At GCSE (F10.1) you met the client server model for networks. This lesson applies it to databases and deals with the problem it brings: many clients changing the same data at the same time.

Client server databases

In a client server database, one server runs the DBMS and holds the data. Clients (the robots, the scoreboard, a teacher's laptop) send it requests, usually SQL, over a network. The server runs each request and sends back only the result.

That last row is the rest of this lesson.

The lost update

Hawks' score is 10. Two robots on the team score at the same moment: A adds 2 and B adds 3. Each update is a read, then a write:

The score should be 15. B's write replaced A's, and A's 2 points are gone: a lost update. Neither transaction did anything wrong on its own; the problem is how they were interleaved.

database = {"score": 10}

def transaction(name, points):
    """A transaction as two steps, a read and a write, so two transactions can be interleaved."""
    seen = {}
    def read():
        seen["score"] = database["score"]
        print(f"{name} reads {seen['score']}")
    def write():
        database["score"] = seen["score"] + points
        print(f"{name} writes {database['score']}")
    return read, write

a_read, a_write = transaction("A", 2)
b_read, b_write = transaction("B", 3)
for step in [a_read, b_read, a_write, b_write]:
    step()
print("final score:", database["score"], "(should be 15)")

Run this in the simulator

Change the order of the steps to [a_read, a_write, b_read, b_write] and the answer is right. A DBMS needs a way to make sure it always is. There are four methods to know.

1. Record locks

A record lock gives one transaction sole use of a record. A transaction must lock a record before it reads it for an update; any other transaction that wants the record must wait until the lock is released, when the first transaction commits or rolls back.

database = {"score": 10}
locks = {}

def lock(name, record):
    if locks.get(record, name) != name:
        print(f"{name} must wait: {record} is locked by {locks[record]}")
        return False
    locks[record] = name
    return True

lock("A", "score")
a_seen = database["score"]; print("A reads", a_seen)
lock("B", "score")                                   # B is refused and waits
database["score"] = a_seen + 2; print("A writes", database["score"])
del locks["score"]; print("A commits and releases the lock")

lock("B", "score")
b_seen = database["score"]; print("B reads", b_seen)
database["score"] = b_seen + 3; print("B writes", database["score"])
del locks["score"]; print("B commits:", database["score"])

Run this in the simulator

Locks bring a new danger, deadlock. A locks score and then asks for led; meanwhile B has locked led and asks for score. Each waits for the other, forever. DBMSs deal with it by making transactions lock records in a fixed order, by timing out a transaction that waits too long, or by detecting the cycle of waiting and rolling one transaction back.

2. Serialisation

Serialisation makes transactions behave as if they ran one after another, never overlapping. In its simplest form a transaction cannot start until the one before it has committed, so updates cannot be lost. That is safe but slow, since clients queue even when they want different records. So a DBMS aims for a serialisable schedule instead: the operations may interleave, but the final result must be the same as running the transactions in some serial order. Locking and timestamp ordering are two ways of guaranteeing it.

3. Timestamp ordering

In timestamp ordering, every transaction is given a timestamp when it starts, so an older transaction has a smaller timestamp. Every record keeps two timestamps of its own: its read timestamp, the largest timestamp of any transaction that has read it, and its write timestamp, the largest of any that has written it. Both start at 0. Before each operation the DBMS checks:

• Read. If the transaction's timestamp is less than the record's write timestamp, a younger transaction has already overwritten the value, so the transaction is aborted. Otherwise it reads, and the read timestamp becomes the larger of the two.
• Write. If the transaction's timestamp is less than the record's read timestamp or its write timestamp, a younger transaction has already used or replaced the value, so the transaction is aborted. Otherwise it writes, and the write timestamp becomes the transaction's timestamp.

An aborted transaction is rolled back and restarted with a new, later timestamp. Try it on the lost update: A has timestamp 1, B has 2. A reads (read timestamp 1), B reads (read timestamp 2), then A tries to write: 1 < 2, so A is aborted. B writes 13. A restarts as transaction 3, reads 13 and writes 15. The result is the same as running A after B, and no transaction ever waits, so there is no deadlock.

In the style of AQA's pseudo-code:

FOR EACH (ts, op, record) IN schedule
  IF op = 'read' THEN
    IF ts < WriteTS[record] THEN
      abort ts
    ELSE
      ReadTS[record] ← MAX(ReadTS[record], ts)
    ENDIF
  ELSE
    IF ts < ReadTS[record] OR ts < WriteTS[record] THEN
      abort ts
    ELSE
      WriteTS[record] ← ts
    ENDIF
  ENDIF
ENDFOR

4. Commitment ordering

Commitment ordering lets transactions run at the same time and controls the order in which they commit. The DBMS works out how transactions depend on each other: if transaction A used a record before B changed it, A must commit before B. It then commits the transactions in an order that respects those dependencies (and, where there is a choice, the order they started), making a transaction wait or aborting it if it would commit out of order. Transactions that touch different records never hold each other up, and the result is still serialisable.

Task: timestamp ordering

schedule is a list of operations in the order they reach the DBMS. Each is (ts, op, record): the transaction's timestamp (a whole number from 1 to 5), "read" or "write", and the record's name.

Apply timestamp ordering exactly as described above. Every record's read and write timestamps start at 0. For each operation, in order, print T<ts> <op> <record>: <result>, where result is:

• skipped if transaction ts has already been aborted (do not restart it; its later operations are skipped);
• abort if the rules refuse the operation (the transaction is now aborted);
• ok otherwise, updating the record's timestamp.

Then print committed: followed by the transactions that were never aborted, and aborted: followed by those that were, each as T<ts> in increasing order, separated by a comma and a space: for example aborted: T1, T2, T4. Fourteen lines in all. The robot does not move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# (transaction timestamp, operation, record)
schedule = [
    (1, "read", "balls"),
    (2, "read", "balls"),
    (2, "write", "balls"),
    (1, "write", "balls"),
    (3, "write", "score"),
    (1, "read", "score"),
    (2, "read", "score"),
    (3, "read", "balls"),
    (2, "write", "score"),
    (3, "write", "balls"),
    (5, "write", "led"),
    (4, "write", "led"),
]

Challenges

1. Draw the timeline for the deadlock between A and B, with the time each lock is taken and requested.
2. Run the lost update with locks, but let B lock first. What is the final score?
3. In the task schedule, T4 is aborted only because T5 wrote led first. Does that write actually conflict with anything T4 has done? (Look up the Thomas write rule.)