前言
本篇文章中所讨论的锁（ObLatch），并不是用户语义上用于保证数据一致性的锁（Lock），而是用于保护临界区的同步机制。以下主要介绍OceanBase中的两种同步机制–互斥锁和读写锁的实现。或许有同学会问，为什么要自己实现锁，为何不直接用glibc库中的提供的同步机制，如pthread_spin，pthread_rwlock等方法？其实实现ObLatch主要有以下几方面的考虑：
诊断监控：热点的临界区可能在并发访问时产生冲突，此时记录保护此临界区的锁的自旋次数、等待时间和等待次数等诊断信息，会对性能优化有指导意义。而在glibc等库中加入诊断信息几乎是不可能的，所以我们需要实现一个具备诊断能力的锁。关于OceanBase中的诊断监控，详见 https://www.atatech.org/articles/58734 。
锁等待的排队策略：锁冲突时可能会导致工作线程进入等待队列等待（锁内部），当其他持锁的线程释放锁后，有多种唤醒等待队列中等待者的策略。例如在pthread_rwlock中，可以优先唤醒读锁的等待者，或者优先唤醒写锁的等待者。在OceanBase中需要公平的FIFO唤醒策略，以免等锁饿死的现象发生，而这却是pthread_rwlock中没有提供的。
性能问题：详见文中性能对比。
以下，通过基础的互斥锁和读写锁的实现入手，进一步介绍OceanBase中锁的具体实现。
互斥锁
自旋锁
首先通过伪代码介绍完全基于自旋的互斥锁实现。
typedef volatile int32_t Spinlock;void lock(Spinlock &lock){ while (1) { if (0 == lock) { if (ATOMIC_BCAS(&lock, 0, 1)) { // 尝试拿锁
break; // 获得锁
}
}
asm(“pause”); // 自旋
}
}void unlock(Spinlock &lock){
barrier(); lock = 0; // 释放锁}
其中，ATOMIC_BCAS是原子操作compare_and_swap，即如果lock的值为0（表示没有现成持有锁），那么就将lock的值置为1表示持有锁（注：也可以使用thread_id作为lock的值直接表示此线程持有锁）；如果此时lock的值不为0，则进入自旋。此算法会一直自旋尝试拿锁，直到获得锁为止。（注：此算法为非公平的自旋锁，也有很多公平的自旋锁实现，例如ticket-spinlock，MCS，CHL等，但是公平的自旋锁在竞争激烈且线程数大于CPU核数的场景性能较差，详见[1]。）
Spin-then-Park
自旋锁对于临界区较小的场景有比较好的性能，然而如果当临界区较大时，一个线程拿到锁后很久不会释放锁，那么其他要加锁的线程会无限地自旋。这会导致CPU资源的严重浪费，尤其是当要加锁的线程数大于CPU数时，系统的CPU资源可能都会浪费在无谓的自旋中。为了解决这个问题，需要一种’Spin-then-Park’的思路[2]，即在自旋拿到不锁时，不应该无谓地自旋下去，而应该选择适当的时机将自己挂起让出CPU。让出CPU的方法有很多，比如使用sched_yield或者sleep方法让出CPU资源，OceanBase中的锁主要基于更为灵活的Futex方案。
Futex
Futex是Fast Userspace muTexes的缩写，是Linux下的一种快速的同步机制，主要的作用是可以支持等待和唤醒操作，并管理和维护挂起线程的等待队列。Futex主要有两个操作，futex_wait用于挂起线程并加入等待队列，futex_wake用于唤醒等待队列中的等待者。想进一步了解Futex机制的同学可以阅读文献[3]。
Put all together
综合以上的思路和技术，以下给出OceanBase中互斥锁的伪代码：
typedef volatile int32_t Mutex;bool spin_try_lock(Mutex &lock){ if (0 == lock) { if (ATOMIC_BCAS(&lock, 0, 1)) { // 尝试拿锁
return true;
}
} return false;
}void lock(Mutex &lock){
try_spin_cnt = 0; while(try_spin_cnt < MAX_SPIN_CNT) { if (spin_try_lock(lock)) { return;
}
asm(“pause”);;
try_spin_cnt++;
} while (1) {
futex_wait(&lock); // 挂起自己，等待被唤醒
if (spin_try_lock(lock)) { // 被唤醒后，尝试拿锁
return;
}
}
}void unlock(Mutex &lock){
barrier(); lock = 0; if (has_waiter(lock)) {
futex_wake(&lock, 1); // 唤醒一个waiter
}
}
根据伪代码可以看出，OceanBase中的互斥锁采用了“Spin-then-Park”的思路，不会无限自旋等锁，而是在自旋MAX_SPIN_CNT次后，如果无法拿到锁的时候，便使用Futex将自己挂起，让出CPU资源，等待其他线程释放锁后将自己唤醒。其中，MAX_SPIN_CNT是可配置的，这样可以根据使用场景为不同的锁配置不同的数值。
性能对比
采用单测模拟高冲突场景，有多线程争夺锁，每个线程需要拿锁100000次，临界区大约为1-5us。测试机器为24核，测试完成单测所需的时间，测试结果如下表所示：
4线程 8线程 16线程 32线程 64线程 128线程
ob_latch_mutex 0.9s 1.9s 5.5s 11s 22s 44s
pthread_mutex 1.9s 3.5s 7s 13s 26s 51s
读写锁
读写锁和互斥锁类似，是另一种线程同步机制。其特点为：
对于reader：在没有任何writer占有锁时（意味着可以存在一个或者多个reader占有此锁），那么reader可以拿到锁；
对于writer：在没有任何writer并且没有任何reader占有锁时，writer才可以拿到锁。
以下首先通过伪代码介绍完全基于自旋的读写锁实现。
typedef voliate int32_t RWLock;static const uint32_t WRITE_MASK = 1<<31; // lock的最高位被设置表示有writer占有锁void rdlock(RWLock &lock){ while (1) {
l = lock; if (0 == (l & WRITE_MASK)) { // 没有writer占有锁
if (ATOMIC_BCAS(&lock, l, l + 1)) { // 尝试拿读锁，如果拿到读锁，则将读锁counter加1
break; // 拿到读锁
}
}
asm(“pause”); // 自旋
}
}void wrlock(RWLock &lock){ while (1) {
l = lock; if (0 == l) { // 没有writer和reader才能拿到写锁
// 尝试拿写锁，如果拿到写锁，则设置写锁标志位，同时可以把thread_id写入
if (ATOMIC_BCAS(&lock, l, (WRITE_MASK | thread_id))) {
break; // 拿到写锁
}
}
asm(“pause”); // 自旋
}
}void unlock(RWLock &lock){
l = lock; if (0 != (l & WRITE_MASK)) { // 我是writer
barrier() lock = 0; // 将lock置为0
} else { // 我是reader
ATOMIC_AAF(&lock, -1); // 原子操作，将读锁的counter减1
}
}
OceanBase中的读写锁
OceanBase中的读写锁也是基于“Spin-then-Park”的思路实现的，为了实现FIFO的唤醒策略，同时需要自己实现等待队列而不能直接使用Futex中的等待队列。这是因为，在读写锁中，读锁是不互斥的，那么在唤醒等待队列时就不是一次仅唤醒一个等待者，而是(i) 如果唤醒的是写锁，则只唤醒一个；(ii) 如果唤醒的是读锁，则根据唤醒策略唤醒一批读锁。比如读优先策略就是唤醒所有的读锁等待者，而如果是FIFO唤醒策略，那么就是唤醒队列中连续的读等待者，直到一下个写锁等待者为止。例如，如下图表示一个FIFO等待队列，则唤醒顺序为w1，w2，r1-r3(全部唤醒)，w4，w5，r4，w6，r5-r6。
图片
rdlock/wrlock伪代码：
- 尝试MAX_SPIN_CNT次加锁，如果成功则修改锁状态，并进入临界区
- 如果尝试加锁失败，将自己加入等待队列(需互斥锁保护)
- 使用futex_wait将自己挂起并等待唤醒
- 被唤醒，则继续尝试加锁，如果成功则修改锁装态，并进入临界区
- 否则跳到步骤2
unlock伪代码：
- 修改锁状态
- 如果需要唤醒等待队列中的等待者，则从等待队列中取出 合适 的等待者（需互斥锁保护）
- 使用futex_wake唤醒这些等待者
注意：可以根据不同的需求选择不同的顺序唤醒等待者，例如FIFO，READER_PREFER等。
性能对比
采用单测模拟高冲突场景，有多线程争夺锁，通过3各参数模拟不同场景：
读写比：用于产生不同的读写锁的请求，包括3:1、49:1和99:1
临界区大小：包括0.5us、5us和50us
线程数
测试机器为64核，测试完成单测所需的时间。测试结果如下图所示（图中纵轴为使用ob_latch_rw单测耗时与使用pthread_rw的单测耗时之比）。
图片
总结
OceanBase中的锁是一种灵活且性能优秀的锁，更重要的是具备诊断能力，这对于性能优化具有重要的指导意义。有兴趣的同学欢迎交流。
参考文献
[1] Spinlocks and Read-Write Locks. http://locklessinc.com/articles/locks/.
[2] Dave Dice. waiting policies for locks : spin-then-park. https://blogs.oracle.com/dave/waiting-policies-for-locks-%3A-spin-then-park.
[3] Ulrich Drepper. Futexs are tricky. http://dept-info.labri.fr/~denis/Enseignement/2008-IR/Articles/01-futex.pdf.
