you fail, you recover, you looks the log

protocols

write data in multiple sites, one site may fail during transaction. In order to keep atomicity, to get commit or abort on both sites to work is very important. This is always gurranted from one state to next state. In order words, if one site fails but the other site commits, you must think how to reover the fail site.

local recovery

Assume you have disk and memory storage to run a transaction. Transaction makes change on memory(because this is faster than writing into disk direclty): disk passes file to memory, transaction changes file in memory, when completed, file change goes to disk.

  • case 1: if trasaction on memory fails before commit. Just discard the transaction.
  • case 2: if transaction on memory fails after commit. The memory doesn’t change. but according to ACID durability, once commit happens, it must persist passing failure during durable stage. Avoid change lost, we hope the memory change will flush to disk. Solution: build log on disk or on another disk. Any transaction on memory will be recorded in log. If failure happens before commit, igonre the log. But if failure happens after commit, when recover the system, we redo the operation in log.

ACID (atomicity, consistency, isolation, durability) is a set of properties of database transactions intended to guarantee validity even in the event of errors, power failures, etc. Change will persist passing failure during durable stage?

If my system doesn’t fail for long time, I keep log all the time, it waste space. Solution: make log circle overwriting. Interval checking pointing(means flush part of log to disk), it decrease recovery time. Every server has this WAL(write ahead log).

global recovery

If one transaction runs different part on two different sites. Solution: 2PC(Two-Phase-Commit).

You have to point a coordinator site to ensure all sites commit o abort. Every site can be a coordinator. Assume we have two sites, one site is coordinator stite and the other is participant site.

Coordinator runs part of the transation, when it’s done, it starts the log of 2PL protocal and asks other sites to vote “do you prepare to commit?”. If the site is also done, it replies”yes” to vote, if the site has a dead lock, in order to abort the dead lock, it replies “no”. According to the votes, the coordinator send messge back to every site “global commit or abort”. If at lease one site votes to abort, it will result to global abort. This means coordinator should keep a list of all sites’ status. Which means each decision(stage) is persistent storage.

Some failures:

  • fail on step 1: before coordinator asks “do you prepare to commit?”, so do nothing in log
  • fail on step 2: after coordinator asks if prepare to commmit, then fail or other sites fail to vote. So abort automitically on coordinator.
  • fail on step 3: before coordinator send messages “do global commit” to other sites, when recover look at log, no need to commit. Or because all votes to commit, coordinator could continue global commit after its recovery.
  • fail on step 4: after coordinator send message “do global commit”, when it recovers, it may send the message again to cotinue.
  • fail on step 5(1): participant site fails and then recover to look the log, it sends commit vote but not recieve any global commit. So coordinator may send “global commit” or “global abort”. The site doesn’t know. It must ask the coordinator again “did you send global commit or abort?”
  • fail on step 5(2): participant site fails as above, and ask coordinator again but coordinator is down. So it start to run termination protocol(A protocol is regarded as terminated when subject enrollment and subject follow-up are discontinued). Ask the coordinator again and again. Ask random sites’ “is this transactioin committed or not?”. But it is message consumming and may couldn’t get answer from anyone because they are down(this is called uncertain failure).
  • fail on step 6: after participant site does commit, it fails. When the site recovers, just send “done” to coordinator again.

2PC: 2 phases commit, including vote phase and decision phase.

2PC(2 phases commit)!= 2PL(2 phases locks).

Reference material:
Book: Distributed Systems, Third edition, Version 3.02(2018), Maarten van Steen and Andrew S. Tanenbaum.
Lectures: University of Waterloo, CS 454/654 (Distributed System), 2020 winter term, Professor Khuzaima Daudjee.