MVCC实现

在InnoDB存储引擎中，每个表都是索引组织表，如果建表时没有指定主键索引，会自动创建一个6字节的自增列来作为隐藏主键。

每条聚簇索引的索引记录都包含下面两个隐藏列：

• 事务ID列，用于标识该版本记录由那个事务修改产生。
• 回滚指针列，用于指向“存放上一个版本记录数据”的Undo Log指针。

PS：对于存放在Undo Log上的“版本记录”，除包含变化前的用户数据外，也包含事务ID列和回滚指针列

InnoDB存储引擎基于事务ID列和回滚指针列来实现多版本并发控制(multi version concurrencey control)，为判断事务应读取记录的那个版本，会为事务分配一个read view数据结构，存放如下信息：

• m_low_limit_id：当前事务能看到的"最大事务ID"，超过m_low_limit_id的事务产生的修改对当前事务不可见。
• m_up_limit_id：当前事务能看到的”最小事务ID“，小于m_up_limit_id的事务产生的修改对当前事务可见。
• m_creator_trx_id：当前事务的事务ID，当前事务产生的修改对当前事务可见。
• m_ids：创建read view时活跃事务ID链表，该活跃实例链表中的事务产生的修改对当前事务不可见(事务没提交)。

InnoDB存储引擎的事务系统使用数据结构trx_sys_t来存放一些全局事务信息，

 /*!< The smallest number not yet
 assigned as a transaction id or
 transaction number. This is declared
 volatile because it can be accessed
 without holding any mutex during
 AC-NL-RO view creation. */
 volatile trx_id_t max_trx_id;
 
 /*!< Array of Read write transaction IDs
 for MVCC snapshot. A ReadView would take
 a snapshot of these transactions whose
 changes are not visible to it. We should
 remove transactions from the list before
 committing in memory and releasing locks
 to ensure right order of removal and
 consistent snapshot. */
 trx_ids_t rw_trx_ids; 

trx_sys_t->max_trx_id 用来储存当前未分配的最小事务编号，通过trx_sys_t->max_trx_id能快速获取到read view的m_low_limit_id初始值。

trx_sys->rw_trx_ids 用来存储当前活跃的事务链表，该全局事务连接按照事务ID逆序存放，最小的事务ID存放在链表尾部，通过trx_sys->rw_trx_ids 来初始化m_up_limit_id和m_ids。

read view结构

private:
  // Disable copying
  ReadView(const ReadView &);
  ReadView &operator=(const ReadView &);

 private:
  /** The read should not see any transaction with trx id >= this
  value. In other words, this is the "high water mark". */
  /* 最高水位 */
  trx_id_t m_low_limit_id;

  /** The read should see all trx ids which are strictly
  smaller (<) than this value.  In other words, this is the
  low water mark". */
  /* 最小水位 */
  trx_id_t m_up_limit_id;

  /** trx id of creating transaction, set to TRX_ID_MAX for free
  views. */
  /* 当前事务id */
  trx_id_t m_creator_trx_id;

  /** Set of RW transactions that was active when this snapshot
  was taken */
  /* 活跃事务id */
  ids_t m_ids;

  /** The view does not need to see the undo logs for transactions
  whose transaction number is strictly smaller (<) than this value:
  they can be removed in purge if not needed by other views */
  /* m_low_limit_no 用于undo log的purge操作 */
  trx_id_t m_low_limit_no;

#ifdef UNIV_DEBUG
  /** The low limit number up to which read views don‘t need to access
  undo log records for MVCC. This could be higher than m_low_limit_no
  if purge is blocked for GTID persistence. Currently used for debug
  variable INNODB_PURGE_VIEW_TRX_ID_AGE. */
  trx_id_t m_view_low_limit_no;
#endif /* UNIV_DEBUG */

  /** AC-NL-RO transaction view that has been "closed". */
  bool m_closed;

  typedef UT_LIST_NODE_T(ReadView) node_t;

  /** List of read views in trx_sys */
  byte pad1[64 - sizeof(node_t)];
  node_t m_view_list;
};

#endif

初始化read_view

/**
Opens a read view where exactly the transactions serialized before this
point in time are seen in the view.
@param id		Creator transaction id */

void ReadView::prepare(trx_id_t id) {
  ut_ad(mutex_own(&trx_sys->mutex));

  m_creator_trx_id = id;

  m_low_limit_no = m_low_limit_id = m_up_limit_id = trx_sys->max_trx_id;

  if (!trx_sys->rw_trx_ids.empty()) {
    copy_trx_ids(trx_sys->rw_trx_ids);
  } else {
    m_ids.clear();
  }

  ut_ad(m_up_limit_id <= m_low_limit_id);

  if (UT_LIST_GET_LEN(trx_sys->serialisation_list) > 0) {
    const trx_t *trx;

    trx = UT_LIST_GET_FIRST(trx_sys->serialisation_list);

    if (trx->no < m_low_limit_no) {
      m_low_limit_no = trx->no;
    }
  }

  ut_d(m_view_low_limit_no = m_low_limit_no);
  m_closed = false;
}

判断记录是否可见

/* storage\innobase\include\read0types.h */

/** Check whether transaction id is valid.
@param[in]	id		transaction id to check
@param[in]	name		table name */
static void check_trx_id_sanity(trx_id_t id, const table_name_t &name);

/** Check whether the changes by id are visible.
@param[in]	id	transaction id to check against the view
@param[in]	name	table name
@return whether the view sees the modifications of id. */
bool changes_visible(trx_id_t id, const table_name_t &name) const
    MY_ATTRIBUTE((warn_unused_result)) {
  ut_ad(id > 0);

  if (id < m_up_limit_id || id == m_creator_trx_id) {
    return (true);
  }

  check_trx_id_sanity(id, name);

  if (id >= m_low_limit_id) {
    return (false);

  } else if (m_ids.empty()) {
    return (true);
  }

  const ids_t::value_type *p = m_ids.data();

  return (!std::binary_search(p, p + m_ids.size(), id));
}

MySQL Innodb Engine--MVCC代码瞎猜