InnoDB 读写锁逻辑分析-8.0.25

版本

MySQL 8.0.25

背景

除了 Mutex 的使用, 在 InnoDB 内核中, 为了增加 InnoDB 的并发读写, 引入了读写锁. Mutex 严格的限制只有一个 thread 可以进入临界区, 但是实际的存储引擎中, 例如针对数据 Page 可以区分读和写, 多个读操作同时访问一个数据 Page 是合法的. InnoDB 实现了一套读写锁的逻辑, 除了读锁 S, 写锁 X, 还引入了 SX 锁, SX 锁和 SX 和 X 锁之间互斥, 但是兼容 S 锁. 实际的使用场景例如数据 Page 在刷脏的时候加的是 SX 锁, 但是允许读 S 锁, 这也符合数据库的使用特征.

rw_lock_t 数据结构

struct rw_lock_t 是 InnoDB 读写锁的数据结构, 关键的成员变量有 lock_word, waiters, recursive, writer_thread, 在我们 GDB 调试 InnoDB 代码时, print rw_lock_t 时这几个成员变量可以帮助我们理解该读写锁的持有情况.


/* 锁的兼容矩阵:
 * 1. X 与 X 和 SX 和 S 全部互斥.
 * 2. SX 和 SX 和 X 互斥, 但是兼容 S 锁. */

LOCK COMPATIBILITY MATRIX
    S SX  X
 S  +  +  -
 SX +  -  -
 X  -  -  -

struct rw_lock_t
#ifdef UNIV_DEBUG
    : public latch_t
#endif /* UNIV_DEBUG */
{
  /** ... */

  /** 锁状态. */
  std::atomic<int32_t> lock_word;

  /** 是否有线程等待在这个读写锁. */
  std::atomic<bool> waiters;

  /** 这个锁是否处于递归加锁的状态, 一个线程允许对一个 rw_lock 加了 SX 锁再次申请 X 锁. */
  std::atomic<bool> recursive;

  /** 持有锁的线程 id. */
  std::atomic<std::thread::id> writer_thread;

  /** ... */
};

lock_word

lock_word 代表当前读写锁的锁状态, 所以我们可以从 lock_word 来判断这个锁的持有状态, 比如可以得知该锁目前是 S 锁还是 X 锁, 还是 SX 锁. 如果是 S 锁, 有多少 S 锁, 或者当前这个锁是否已经被一个线程预定了 X 锁等等.

lock_word 初始值为X_LOCK_DECR.

#define X_LOCK_DECR 0x20000000 (10 进制 536870912)
#define X_LOCK_HALF_DECR 0x10000000 (10 进制 268435456)

申请 X 锁

通过函数rw_lock_x_lock_low()来申请获取 X 锁:

判断当前的lock_word是否大于 X_LOCK_HALF_DECR.
如果条件 1 满足就使用 CAS 减去 X_LOCK_DECR, 然后等待lock_word的值为 0.
如果条件 1 不满足, 则判断是否可以递归加锁, 即在申请 X 锁之前是否已经持有了 SX 或者 X 锁.
如果该线程之前已经持有了 SX 锁, 则将lock_word的值减去 X_LOCK_DECR, 然后等待lock_word的值为 -X_LOCK_HALF_DECR, 因为 SX 锁和 S 锁兼容, 所以由 SX 锁升级为 X 锁后, 需要等待其他线程持有的 S 锁释放.
如果该线程之前已经持有了 X 锁, 则修改lock_word后即可.
上述条件都不满足, 即其他线程可能持有了 SX 锁或者 X 锁, 则进入 spin 的等待状态.

UNIV_INLINE
bool rw_lock_x_lock_low(
    rw_lock_t *lock,       /*!< in: pointer to rw-lock */
    ulint pass,            /*!< in: pass value; != 0, if the lock will
                           be passed to another thread to unlock */
    const char *file_name, /*!< in: file name where lock requested */
    ulint line)            /*!< in: line where requested */
{
  if (rw_lock_lock_word_decr(lock, X_LOCK_DECR, X_LOCK_HALF_DECR)) {
    /* 1. 如果当前不存在 S 锁或者 SX 锁或者其他 X 锁, 步骤 1 是满足的,
     * 步骤 2 也无需等待直接返回加锁成功. */
    rw_lock_set_writer_id_and_recursion_flag(lock, !pass);
	
    /* 2. 如果这个锁已经被其他线程加了数量小于 X_LOCK_HALF_DECR 个 S 锁,
     * 步骤 1 也是满足的, 但是步骤 2 需要进入等待逻辑直到所有的 S 锁释放,
     * 即使当前读写锁上已经有其他的 S 锁, 但是为了防止 X 锁饥饿状态,
     * 所以将 X 预先分配给申请线程. */
    rw_lock_x_lock_wait(lock, pass, 0, file_name, line);

  } else {
    if (!pass && lock->recursive.load(std::memory_order_acquire) &&
        lock->writer_thread.load(std::memory_order_relaxed) ==
            std::this_thread::get_id()) {

      /* The existing X or SX lock is from this thread */
      if (rw_lock_lock_word_decr(lock, X_LOCK_DECR, 0)) {
        /* 之前已经持有了 SX 锁, 由 SX 锁升级为 X 锁. */
        rw_lock_x_lock_wait(lock, pass, -X_LOCK_HALF_DECR, file_name, line);

      } else {
        /* 之前已经持有了 X 锁. */
        if (lock->lock_word == 0 || lock->lock_word == -X_LOCK_HALF_DECR) {
        /* 1. 上一次直接申请了 X 锁, 所以 lock_word 为 0.
         * 2. 上一次是 SX 锁升级为 X 锁, 所以 lock_word 为-X_LOCK_HALF_DECR.
         * 3. 所以 X 锁的 lock_word 减去 X_LOCK_DECR. */
          lock->lock_word -= X_LOCK_DECR;
        } else {
          ut_ad(lock->lock_word <= -X_LOCK_DECR);
          /* 之前已经持有了两个 X 锁, 所以当前的 lock_word 递减 1 即可. */
          --lock->lock_word;
        }
      }
    } else {
      /* 申请失败, 返回进入等待. */
      return false;
    }
  }

  ut_d(rw_lock_add_debug_info(lock, pass, RW_LOCK_X, file_name, line));

  lock->last_x_file_name = file_name;
  ut_ad(line <= std::numeric_limits<decltype(lock->last_x_line)>::max());
  lock->last_x_line = line;

  /* 申请 X 锁成功. */
  return true;
}

申请 SX 锁

通过函数rw_lock_sx_lock_low()来申请获取 SX 锁:

判断当前的lock_word是否大于 X_LOCK_HALF_DECR.
如果条件 1 满足就使用 CAS 减去 X_LOCK_DECR, 因为 SX 锁和 S 锁兼容, 所以无需等待 lock_word 的值为 0.
如果条件 1 不满足, 则判断是否可以递归加锁, 即在申请 X 锁之前是否已经持有了 SX 或者 X 锁.
如果该线程之前已经成功申请了一个 X 锁, 所以 lock_word -= X_LOCK_HALF_DECR.
上述条件都不满足, 即 SX 或者 X 锁已经被其他线程持有, 则进入 spin 的等待状态.

bool rw_lock_sx_lock_low(
    rw_lock_t *lock,       /*!< in: pointer to rw-lock */
    ulint pass,            /*!< in: pass value; != 0, if the lock will
                           be passed to another thread to unlock */
    const char *file_name, /*!< in: file name where lock requested */
    ulint line)            /*!< in: line where requested */
{
  if (rw_lock_lock_word_decr(lock, X_LOCK_HALF_DECR, X_LOCK_HALF_DECR)) {
    /* 1. 判断当前的 lock_word 是否大于 X_LOCK_HALF_DECR.
     * 2. 如果条件 1 满足就使用 CAS 减去 X_LOCK_DECR, 因为 SX 锁和 S 锁兼容,
     * 所以无需等待 lock_word 的值为 0. */

    /* lock->recursive == true implies that the lock->writer_thread is the
    current writer. As we are going to write our own thread id in that field it
    must be the case that the current writer_thread value is not the current
    writer anymore, thus recursive flag must be false.  */
    ut_a(!lock->recursive.load(std::memory_order_relaxed));

    /* Decrement occurred: we are the SX lock owner. */
    rw_lock_set_writer_id_and_recursion_flag(lock, !pass);

    /* 设置 sx_recursive 的标记为 1. */
    lock->sx_recursive = 1;

  } else {
    /* ... */
    if (!pass && lock->recursive.load(std::memory_order_acquire) &&
        lock->writer_thread.load(std::memory_order_relaxed) ==
            std::this_thread::get_id()) {
      /* This thread owns an X or SX lock */
      if (lock->sx_recursive++ == 0) {
        /* ... */

        ut_ad((lock->lock_word == 0) ||
              ((lock->lock_word <= -X_LOCK_DECR) &&
               (lock->lock_word > -(X_LOCK_DECR + X_LOCK_HALF_DECR))));
        /* 之前已经成功申请了一个 X 锁, 所以 lock_word -= X_LOCK_HALF_DECR. */
        lock->lock_word -= X_LOCK_HALF_DECR;
      }
    } else {
      /* Another thread locked before us */
      return false;
    }
  }

  ut_d(rw_lock_add_debug_info(lock, pass, RW_LOCK_SX, file_name, line));

  lock->last_x_file_name = file_name;

  ut_ad(line <= std::numeric_limits<decltype(lock->last_x_line)>::max());
  lock->last_x_line = line;

  return true;
}

申请 S 锁

通过函数rw_lock_s_lock_low()来申请获取 S 锁, 判断的逻辑是当前的lock_word是否大于 0, 如果大于 0 则使用 CAS 操作减去 1.

如何通过 lock_word 判断锁信息

lock_word = X_LOCK_DECR: 没有任何锁持有.
X_LOCK_HALF_DECR < lock_word < X_LOCK_DECR: 存在 S 锁, S 锁的数量是(X_LOCK_DECR - lock_word), 并且没有任何 SX/X 锁的申请等待.
lock_word == X_LOCK_HALF_DECR: 存在 SX 锁, 并且没有任何 SX/X 锁的申请在等待.
0 < lock_word < X_LOCK_HALF_DECR: 存在 SX 锁和 S 锁, 并且没有任何 SX/X 锁的申请在等待.
lock_word == 0: 存在 X 锁, 并且没有任何 SX/X 锁的申请在等待.
-X_LOCK_HALF_DECR < lock_word < 0: 存在 S 锁, 并且有一个 X 锁申请在等待.
lock_word == -X_LOCK_HALF_DECR: 存在一个 SX 锁和 X 锁, 是递归持有, 并且没有 SX/X 锁的申请在等待.
-X_LOCK_DECR < lock_word < -X_LOCK_HALF_DECR: 存在 S 锁, 并且有一个持有 SX 锁的线程在等待升级为 X 锁.
lock_word == -X_LOCK_DECR: 存在两个递归持有的 X 锁.
-(X_LOCK_DECR + X_LOCK_HALF_DECR) < lock_word < -X_LOCK_DECR: 存在 X 锁, 数量为 2 - (lock_word + X_LOCK_DECR).
lock_word == -(X_LOCK_DECR + X_LOCK_HALF_DECR): 存在递归持有的 1 个 SX 锁和两个 X 锁.
lock_word < -(X_LOCK_DECR + X_LOCK_HALF_DECR): 存在递归持有的 X 锁和 SX 锁, X 锁的数量是 2 - (lock_word + X_LOCK_DECR + X_LOCK_HALF_DECR).

总结

InnoDB 自行实现了一套读写锁, 并且允许 X 锁的预定从而避免饿死, 不过存在一个可能的情况是如果同时有多个 X 锁来申请, 仍然需要争抢, 并不保证申请顺序.

参考

WL#6363: InnoDB: implement SX-lock for rw_lock