Retrospective Lock List (RLL) to avoid deadlocks.
More...
Retrospective Lock List (RLL) to avoid deadlocks.
- What it is
- Retrospective Lock List (RLL) is a thread-private list of locks the thread took or tried to take in a previous transaction on the same thread. It's used when the previous transaction aborted due to a read-conflict (OCC verification failure) or a lock-conflict (giving up acquiring a write-lock for possible deadlocks). The thread uses the list to pro-actively take locks in a canonical-mode during the next transaction, expecting that the next transaction will need almost the same accesses. This protocol rules out deadlocks, thus dramatically improves concurrency for highly contended workload. It's also very simple and scalable on many-cores.
- Canonical Mode
- When a thread is trying to acquire a lock, the thread is said to be in a Canonical Mode if and only if all locks the thread has already taken, either read-lock or write-lock, are universally-ordered before the lock the thread is trying to take.
- Universal Order of locks
- We can use arbitrary ordering scheme as far as it's universally consistent. For example, we can just order by the address of locks (except, we need to be a bit careful on shared memory and virtual addresses). In the example, a lock X is said to be ordered before another lock Y if and only if addr(X) < addr(Y).
- Benefits of Canonical Mode
- When one is taking a lock in canonical mode, the lock-acquire is guaranteed to be deadlock-free, thus the thread can simply wait for the lock unconditionally.
- How we keep Canonical Mode as much as possible
- We do a couple of things to keep the transaction in canonical mode as much as possible:
- Following to the SILO protocol, we always acquire write-locks during pre-commit in a universal order. As far as we don't take read-locks (pure OCC), then we are always in canonical mode.
- When we want to take a read-lock in a retry of a transaction, we use the retrospective list to take locks who are ordered before the lock the thread is taking. We keep doing this until the end of transaction.
- When we find ourselves risking deadlocks during pre-commit, we might release some of the locks we have taken so that we go back to canonical mode. This is done in best-effort.
- When Canonical Mode is violated
- Initially, every thread is trivially in canonical mode because it has taken zero locks. The thread goes out of canonical mode over time for various reasons.
- The thread has no retrospective lock list, probably because it's the first trial of the xct.
- The thread has used the retrospective lock list, but the thread for some reason accessed different physical pages/records due to page splits, concurrent updates, and many other reasons.
- The thread needs to take a page-lock for page-split etc. In this case, to avoid deadlock, we might have to discard retrospective locks.
- Despite the best-effort retry to keep the canonical mode, there always is a chance that we better give up. This case most likely resulting in aborts and just leaving retrospective list for next trial.
When this happens, still fine, it's not a correctness issue. It just goes back to conditional locking mode with potential timeout, then even in the worst case aborts and leaves the RLL for next run.
What if the thread keeps issuing locks in very different orders and it needs to take read-locks for avoiding verification failure? Umm, then this scheme might keep aborting, but I can't think of any existing scheme that works well for such a case either... except being VERY pessimisitic (take table lock!).
- Ohter uses of RLL
- We can also use RLL to guide our decision to take read-locks or not. If we got an OCC verification failure, we leave an entry in RLL and take a read-lock in the next run. Or, potentially, we can leave an opposite note saying we probably don't need a read-lock on the record. In many cases the per-page stat is enough to guide us, but this is one option.
| bool foedus::thread::Thread::is_hot_page |
( |
const storage::Page * |
page | ) |
const |
1.8.10 
