发布于 由admin

InnoDB 的`Buffer Pool`管理：`LRU`列表、`Free`列表和`Flush`列表的`物理`实现与`源码`分析。

InnoDB Buffer Pool 管理：LRU、Free 和 Flush 列表的物理实现与源码分析

大家好！今天我们来深入探讨 InnoDB 存储引擎中至关重要的组成部分：Buffer Pool。Buffer Pool 是 InnoDB 缓存数据和索引的关键区域，直接影响数据库的性能。我们将重点关注 Buffer Pool 中三个核心列表：LRU (Least Recently Used) 列表、Free 列表和 Flush 列表，并结合源码分析来理解它们的物理实现和管理机制。

1. Buffer Pool 的基本概念

Buffer Pool 类似于一个内存中的数据缓存，用于存储从磁盘读取的数据页（data page）和索引页（index page）。当 InnoDB 需要访问某个数据或索引时，首先会检查 Buffer Pool 中是否存在相应的页。如果存在，则直接从内存中读取，避免了昂贵的磁盘 I/O 操作，这被称为 "Buffer Pool hit"。 如果 Buffer Pool 中没有需要的页，则会发生 "Buffer Pool miss"，InnoDB 需要从磁盘读取该页到 Buffer Pool 中，这会涉及 I/O 开销。

Buffer Pool 的大小由 innodb_buffer_pool_size 参数控制，合理设置这个参数对于数据库性能至关重要。Buffer Pool 太小会导致频繁的磁盘 I/O，而太大则会占用过多系统内存，影响其他应用程序的运行。

2. LRU (Least Recently Used) 列表

LRU 列表用于管理 Buffer Pool 中页的访问热度。它的核心思想是：最近被访问的页更有可能在将来被再次访问，因此应该保留在 Buffer Pool 中；而长时间未被访问的页则应该被淘汰，以便为新的页腾出空间。

2.1 LRU 列表的物理实现

在 InnoDB 中，LRU 列表实际上是一个双向链表。每个节点代表 Buffer Pool 中的一个缓存页 (buf_page_t)。链表头部指向最近被访问的页，链表尾部指向最久未被访问的页。

// 在 storage/innobase/include/buf0buf.h 中定义了 buf_page_t 结构体 (简化)
struct buf_page_t {
  ulint           state;        /* Page state */
  ulint           oldest_lsn;   /* Oldest LSN in the page */
  buf_block_t*    frame;        /* Pointer to the frame in buffer pool */
  buf_page_t*     next_old;    /* Next page in the LRU list */
  buf_page_t*     prev_old;    /* Previous page in the LRU list */
  ulint           space;        /* Tablespace ID */
  ulint           offset;       /* Page number */
};

buf_page_t 结构体中的 next_old 和 prev_old 指针分别指向 LRU 列表中下一个和前一个 buf_page_t 结构体，从而构成双向链表。frame 指针指向实际存储在 Buffer Pool 中的数据页。space 和 offset 用于唯一标识一个数据页。

2.2 LRU 列表的管理策略

当一个页被访问时（例如，读取或写入），它会被移动到 LRU 列表的头部。当需要从 Buffer Pool 中淘汰页时，InnoDB 会从 LRU 列表的尾部选择一个页进行淘汰。

为了提高 LRU 列表的效率，InnoDB 引入了 "midpoint insertion strategy"（中点插入策略）。LRU 列表被分为两个部分：new sublist 和 old sublist。 默认情况下，新读取的页会被插入到 LRU 列表的中点附近（即 new sublist 和 old sublist 的交界处），而不是直接插入到列表的头部。 这样做可以避免一些只被访问一次的页（例如，全表扫描）迅速占据 LRU 列表的前端，从而影响其他更重要的页的缓存效果。

可以使用 innodb_old_blocks_time 参数来控制一个页在被移动到 LRU 列表头部之前，必须在 old sublist 中停留的时间（以毫秒为单位）。如果一个页在 innodb_old_blocks_time 时间内没有被再次访问，它就不会被移动到列表头部，从而降低了它被长期保留在 Buffer Pool 中的概率。

2.3 LRU 列表相关的源码分析

下面我们分析一些和LRU列表管理相关的源码片段。

// 在 storage/innobase/buf/buf0lru.cc 中定义了 buf_LRU_get 函数，用于从 LRU 列表中获取一个页
buf_page_t* buf_LRU_get(
    ulint           purpose,        /*!< in: BUF_GET_... */
    ulint           space,          /*!< in: tablespace id */
    ulint           offset,         /*!< in: page number */
    ulint           size,           /*!< in: page size */
    ulint           priority,       /*!< in: BUF_PRIORITY_... */
    ulint           latch_mode,     /*!< in: X_LOCK or S_LOCK */
    ulint           mtr_magic_n,    /*!< in: MTR magic number */
    mtr_t*          mtr)            /*!< in: mini-transaction handle */
{
  buf_page_t* page;

  /* 1. 尝试从 hash 表中查找该页 */
  page = buf_page_hash_get(space, offset, size);

  if (page == NULL) {
    /* 2. 如果 hash 表中没有找到，则需要从磁盘读取 */
    page = buf_LRU_oldest_page(purpose, space, offset, size, priority, mtr_magic_n, mtr);
    if (page == NULL) {
      return(NULL); /* Out of memory */
    }

    /* 3. 从磁盘读取页到 Buffer Pool */
    if (buf_page_init(page, space, offset, size, purpose, mtr_magic_n, mtr) != DB_SUCCESS) {
        return(NULL);
    }

    /* 4. 将页添加到 hash 表和 LRU 列表 */
    buf_page_add_to_hash(page);
    buf_LRU_add_page(page);

  } else {
    /* 5. 如果 hash 表中找到了该页，则将其移动到 LRU 列表的头部 */
    buf_LRU_move_page(page);
  }

  /* 6. 对页进行加锁 */
  buf_page_latch(page, latch_mode, mtr);

  return(page);
}

// 在 storage/innobase/buf/buf0lru.cc 中定义了 buf_LRU_add_page 函数，用于将一个页添加到 LRU 列表
void buf_LRU_add_page(buf_page_t* page) {
  mutex_enter(&buf_pool->mutex);

  // 将页添加到 LRU 列表的中点附近 (midpoint insertion strategy)
  if (buf_pool->LRU_oldest == NULL) {
    buf_pool->LRU = page;
    buf_pool->LRU_oldest = page;
    page->next_old = NULL;
    page->prev_old = NULL;
  } else {
    // 获取 LRU 列表的中间位置
    buf_page_t* midpoint = buf_pool->LRU_oldest;
    for (ulint i = 0; i < buf_pool->LRU_len / 2; i++) {
      if (midpoint->prev_old == NULL) {
        break;
      }
      midpoint = midpoint->prev_old;
    }

    // 将页插入到 midpoint 的前面
    page->next_old = midpoint;
    page->prev_old = midpoint->prev_old;
    if (midpoint->prev_old != NULL) {
      midpoint->prev_old->next_old = page;
    } else {
      buf_pool->LRU = page;
    }
    midpoint->prev_old = page;

    // 更新 LRU_oldest 指针
    if (page->state == BUF_PAGE_CLEAN) {
      buf_pool->LRU_oldest = page;
    }
  }

  buf_pool->LRU_len++;
  mutex_exit(&buf_pool->mutex);
}

// 在 storage/innobase/buf/buf0lru.cc 中定义了 buf_LRU_remove_page 函数，用于将一个页从 LRU 列表移除
void buf_LRU_remove_page(buf_page_t* page) {
  mutex_enter(&buf_pool->mutex);

  // 从 LRU 列表中移除页
  if (page->next_old != NULL) {
    page->next_old->prev_old = page->prev_old;
  } else {
    buf_pool->LRU_oldest = page->prev_old;
  }

  if (page->prev_old != NULL) {
    page->prev_old->next_old = page->next_old;
  } else {
    buf_pool->LRU = page->next_old;
  }

  page->next_old = NULL;
  page->prev_old = NULL;

  buf_pool->LRU_len--;
  mutex_exit(&buf_pool->mutex);
}

buf_LRU_get 函数首先尝试从 hash 表中查找所需的页。如果找到，则将其移动到 LRU 列表的头部 (buf_LRU_move_page)；如果没有找到，则从磁盘读取该页，并将其添加到 LRU 列表中 (buf_LRU_add_page)。buf_LRU_add_page 函数实现了中点插入策略。buf_LRU_remove_page 函数用于从 LRU 列表中移除一个页。

3. Free 列表

Free 列表用于管理 Buffer Pool 中空闲的缓存页。当 InnoDB 需要从磁盘读取新的页到 Buffer Pool 中时，首先会尝试从 Free 列表中获取一个空闲页。

3.1 Free 列表的物理实现

类似于 LRU 列表，Free 列表也是一个双向链表。每个节点也代表 Buffer Pool 中的一个缓存页 (buf_page_t)。链表头部指向第一个空闲页，链表尾部指向最后一个空闲页。

// 在 storage/innobase/include/buf0buf.h 中定义了 buf_pool_t 结构体 (简化)
struct buf_pool_t {
  mutex_t         mutex;          /* Mutex protecting the LRU and free lists */
  buf_page_t*     free;           /* List of free buf_page_t's */
  ulint           n_free;         /* Number of buf_page_t's in the free list */
  buf_page_t*     LRU;            /* LRU list of buf_page_t's */
  buf_page_t*     LRU_oldest;     /* Last page in the LRU list */
  ulint           LRU_len;        /* Length of the LRU list */
};

buf_pool_t 结构体中的 free 指针指向 Free 列表的头部，n_free 记录了 Free 列表中空闲页的数量。

3.2 Free 列表的管理策略

当 Buffer Pool 启动时，所有可用的缓存页都会被添加到 Free 列表中。当 InnoDB 需要从磁盘读取新的页时，会从 Free 列表的头部获取一个空闲页。如果 Free 列表为空，则 InnoDB 需要从 LRU 列表中淘汰一个页，将其从 LRU 列表中移除，并将其添加到 Free 列表中。

当一个页被释放时（例如，被淘汰），它会被添加到 Free 列表的头部。

3.3 Free 列表相关的源码分析

// 在 storage/innobase/buf/buf0buf.cc 中定义了 buf_pool_alloc_page 函数，用于从 Free 列表中分配一个页
buf_page_t* buf_pool_alloc_page(void) {
  buf_page_t* page;

  mutex_enter(&buf_pool->mutex);

  // 从 Free 列表中获取一个页
  page = buf_pool->free;

  if (page != NULL) {
    buf_pool->free = page->next;
    if (buf_pool->free != NULL) {
      buf_pool->free->prev = NULL;
    }
    page->next = NULL;
    page->prev = NULL;

    buf_pool->n_free--;
  }

  mutex_exit(&buf_pool->mutex);

  return(page);
}

// 在 storage/innobase/buf/buf0buf.cc 中定义了 buf_pool_free_page 函数，用于将一个页添加到 Free 列表
void buf_pool_free_page(buf_page_t* page) {
  mutex_enter(&buf_pool->mutex);

  // 将页添加到 Free 列表的头部
  page->next = buf_pool->free;
  page->prev = NULL;
  if (buf_pool->free != NULL) {
    buf_pool->free->prev = page;
  }
  buf_pool->free = page;

  buf_pool->n_free++;

  mutex_exit(&buf_pool->mutex);
}

buf_pool_alloc_page 函数从 Free 列表中获取一个空闲页。buf_pool_free_page 函数将一个页添加到 Free 列表的头部。

4. Flush 列表

Flush 列表用于管理 Buffer Pool 中被修改过的脏页（dirty page）。脏页是指 Buffer Pool 中被修改过但尚未写入磁盘的页。为了保证数据的持久性，InnoDB 需要定期将脏页刷新到磁盘。

4.1 Flush 列表的物理实现

Flush 列表也是一个双向链表。每个节点代表 Buffer Pool 中的一个脏页 (buf_page_t)。链表头部指向最近被修改的脏页，链表尾部指向最久未被修改的脏页。

// 在 storage/innobase/include/buf0buf.h 中定义了 buf_pool_t 结构体 (简化)
struct buf_pool_t {
  mutex_t         mutex;          /* Mutex protecting the LRU and free lists */
  ...
  buf_page_t*     flush_list;     /* List of dirty pages to be flushed */
  ulint           n_flush_pages;  /* Number of pages in the flush list */
  ...
};

buf_pool_t 结构体中的 flush_list 指针指向 Flush 列表的头部，n_flush_pages 记录了 Flush 列表中脏页的数量。

4.2 Flush 列表的管理策略

当一个页被修改时，它会被添加到 Flush 列表中。InnoDB 使用后台线程（page cleaner thread）定期将 Flush 列表中的脏页刷新到磁盘。刷新策略包括：

  • LRU flushing: 从 LRU 列表的尾部选择脏页进行刷新。
  • Flush list flushing: 按照 Flush 列表的顺序刷新脏页。
  • Adaptive flushing: 根据系统负载和脏页的数量动态调整刷新策略。

innodb_max_dirty_pages_pct 参数控制 Buffer Pool 中脏页的最大比例。当脏页的比例超过这个值时，InnoDB 会更加积极地刷新脏页到磁盘。

4.3 Flush 列表相关的源码分析

// 在 storage/innobase/buf/buf0flush.cc 中定义了 buf_flush_page 函数，用于将一个页刷新到磁盘
ulint buf_flush_page(
    buf_page_t*     page,           /*!< in: buffer page to flush */
    ulint           flush_type,     /*!< in: BUF_FLUSH... */
    ulint           mtr_magic_n,    /*!< in: MTR magic number */
    mtr_t*          mtr)            /*!< in: mini-transaction handle */
{
  ulint   ret;

  /* 1. 检查页是否是脏页 */
  if (!buf_page_is_dirty(page)) {
    return(DB_SUCCESS);
  }

  /* 2. 从 Flush 列表中移除该页 */
  buf_flush_list_remove_page(page);

  /* 3. 将页写入磁盘 */
  ret = fil_io(TRUE, FIL_WRITE, page->space, page->offset, page->zip_size,
         page->page.addr, IO_BLOCK_SIZE, mtr);

  /* 4. 将页标记为干净页 */
  buf_page_clear_dirty(page);

  return(ret);
}

// 在 storage/innobase/buf/buf0flush.cc 中定义了 buf_flush_list_add_page 函数，用于将一个页添加到 Flush 列表
void buf_flush_list_add_page(buf_page_t* page) {
  mutex_enter(&buf_pool->mutex);

  // 将页添加到 Flush 列表的头部
  page->flush_next = buf_pool->flush_list;
  if (buf_pool->flush_list != NULL) {
    buf_pool->flush_list->flush_prev = page;
  }
  page->flush_prev = NULL;
  buf_pool->flush_list = page;

  buf_pool->n_flush_pages++;

  mutex_exit(&buf_pool->mutex);
}

// 在 storage/innobase/buf/buf0flush.cc 中定义了 buf_flush_list_remove_page 函数，用于将一个页从 Flush 列表移除
void buf_flush_list_remove_page(buf_page_t* page) {
  mutex_enter(&buf_pool->mutex);

  // 从 Flush 列表中移除页
  if (page->flush_next != NULL) {
    page->flush_next->flush_prev = page->flush_prev;
  }

  if (page->flush_prev != NULL) {
    page->flush_prev->flush_next = page->flush_next;
  } else {
    buf_pool->flush_list = page->flush_next;
  }

  page->flush_next = NULL;
  page->flush_prev = NULL;

  buf_pool->n_flush_pages--;

  mutex_exit(&buf_pool->mutex);
}

buf_flush_page 函数将一个页刷新到磁盘。buf_flush_list_add_page 函数将一个页添加到 Flush 列表的头部。buf_flush_list_remove_page 函数将一个页从 Flush 列表中移除。

5. 总结概括：Buffer Pool 核心列表的作用

  • LRU 列表：通过双向链表管理页面的访问热度，最近访问的页面保留，长时间未访问的页面淘汰，提高缓存命中率。
  • Free 列表：管理空闲的缓存页，快速分配给需要加载新数据的操作，避免频繁内存分配。
  • Flush 列表：管理修改过的脏页，定期刷新到磁盘，保证数据持久性。

理解这三个列表的物理实现和管理机制，对于优化数据库性能至关重要。希望今天的讲解对大家有所帮助！

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注