# Contention-Aware Lock Scheduling

## Contention-Aware Lock Scheduling for Transactional Databases

### 0x02 算法

#### Most Locks First (MLF)

The intuition is that a transaction with more locks is more likely to block other transactions in the system. However, this approach does not account for the popularity of objects in the system. In other words, a transaction might be holding many locks but on unpopular objects, which are unlikely to be requested by other transactions.



#### Most Blocking Locks First (MBLF)

An improvement over the previous criterion is to only count those locks that have at least one transaction waiting on them.
...
The issue with this criterion is that it treats all blocked transactions as the same, even if they contribute unequally to the overall contention.



#### Deepest Dependency First (DDF)

A more sophisticated criterion is the depth of a transaction’s dependency subgraph. For a transaction t, this is defined as the subgraph of the dependency graph comprised of all vertices that can reach t (and all edges between such vertices). The depth of t’s dependency subgraph is characterized by the number of transactions on the longest path in the subgraph that ends in t.

DDF使用了dependency graph的深度来决定那个txn最先运行，就有可能让更对的dependency graph的“深度”更加浅的尽快得到运行，减少contention。但是缺点是没有考虑到深度很深的，但是之间contention很少的情况，比如就是一条比较长的链结构的case。


### 0x03 Largest-Dependency-Set-First

​ 思路如下：

Consider two transactions t1 and t2 in the system. If there is a path from t1 to t2 in the dependency graph, we say that t1 is dependent on t2 (i.e., t1 depends on t2’s completion/abortion for at least one of its required locks). We define the dependency set of t, denoted by g(t), as the set of all transactions that are dependent on t (i.e., the set of transactions in t’s dependency subgraph). Our LDSF algorithm uses the size of the dependency sets of different transactions to decide which one(s) to schedule first. For example, in Figure 4, there are five transactions in the dependency set of transaction t1 (including t1 itself) while there are four transactions in t2’s dependency set. Thus, in a situation where both t1 and t2 have requested an exclusive lock on object o1, LDSF grants the lock to t1 (instead of t2) as soon as o1 becomes available.


### 0x04 The bLDSF Algorithm

bLDSF Algorithm来源于这样一个动机：LDSF algorithm中当一个shared lock被准许是，是给了所有的等待这个lock的txn，在一些情况下不是一个很好的策略。比如：在一个有很多shared lock的object上，只有当最后一个txn释放这个lock时，需要这个object上X lock的txn才能运行(和rwlock存在的一些问题很相似)。 bLDSF Algorithm解决这个问题的方式是：首先，找到一个等待一个X lock的txn，这个txn有最大的dependency set，记这个度量的值为p(具体的定义可以参考下面论文片段or直接看原论文) 。然后，找到在等待一些shared lock的事务，这些事务使得综合的等待最长，记这个度量为q。根据p q的大小关系决定那个先运行。简单的一个理解就是区分X 和 S锁，当要准许一个lock是，X只能给一个txn，计算一个度量值，S可以给一些txn，计算一个度量值，谁有利于事务平均等待时间更加少就准许那个lock。这个度量的值具体可以参考下面的论文片段，这里有是很多的符号，不好写到Markdown里面：

## 参考

1. Contention-Aware Lock Scheduling for Transactional Databases ，VLDB 2018.