这个数据结构简单来看就是一个拥有固定大小的数组，而对于InnoDB使用来说里面保存的就是写入log buffer或者加入到flush list的数据的大小.数组的每个元素可以被原子的更新.

由于在8.0种写入log buffer会有空洞的产生，因此这个数据结构就用来track当前log buffer的写入情况,也就是说每次写入的数据大小都会保存在linkbuffer中，而每次写入的位置通过start lsn来得到(hash), 假设有空洞(某些lsn还没有写入)，那么它对应在linkbuffer中的值就是0,这样就能很简单的track空洞.

最后要注意的是这个数据结构的前提就是LSN是一直增长且不会重复的.因此在InnoDB中只在redolog中使用.

源码分析

我们先来看这个数据结构的核心字段.

  1. Distance 这个累心表示了我们的Link_buf所包含的内容的类型(一般是lsn_t).
  2. m_capacity 表示Link_buf的大小.
  3. m_links所有的内容都是保存在这里(也就是一个动态数组).
  4. m_tail表示当前buffer的结尾(这里的结尾的意思是第一个空洞的位置,也就是可以保证m_tail之前都是连续的).

 

这里构造函数就是根据传递进来的capacity,创建对应大小的数组(m_links),然后初始化数组的内容.

  2. Link_buf<Position>::Link_buf(size_t capacity)
  3.     : m_capacity(capacity), m_tail(0) {
  4.   if (capacity == 0) {
  5.     m_links = nullptr;
  6.     return;
  7.   }
  9.   ut_a((capacity & (capacity - 1)) == 0);
  10.   m_links = UT_NEW_ARRAY_NOKEY(std::atomic<Distance>, capacity);
  12.   for (size_t i = 0; i < capacity; ++i) {
  13.     m_links[i].store(0);
  14.   }
  15. }

add_link函数主要是用来将将要写入的数据的在lsn中的起始以及结束位置进行保存.流程如下。

  1. 首先根据from计算当前的写入lsn应该在数组的那个位置.
  2. 然后保存写入的大小到当前的slot.

slot_index函数就是用来计算slot，计算方式很简单，和数组的大小取模，这里或许有疑问了，如果当前的slot已经被其他的lsn占据了应该怎么办？这里的解决方式就是通过has_space进行判断.

  2. inline size_t Link_buf<Position>::slot_index(Position position) const {
  3.   return position & (m_capacity - 1);
  4. }

has_space函数就是用来判断对应的position是否已经被占据.

  1. template <typename Position>
  2. template <typename Stop_condition>
  3. bool Link_buf<Position>::advance_tail_until(Stop_condition stop_condition) {
  4.   auto position = m_tail.load();
  6.   while (true) {
  7.     Position next;
  8.     bool stop = next_position(position, next);
  10.     if (stop || stop_condition(position, next)) {
  11.       break;
  14.     */* Reclaim the slot. */*
  15.     claim_position(position);
  17.     position = next;
  18.   }
  20.   if (position > m_tail.load()) {
  21.     m_tail.store(position);
  23.     return true;
  25.   } else {
  26.     return false;

而上面的代码可以看到每次都会读取next_position,这个函数用来返回下一个slot是否为0,如果是0则返回true，也就是说已经到达空洞.