原创｜MySQL WriteSet并行复制分析
提示：公众号展示代码会自动折行，建议横屏阅读
「第一部分 背景」
在mysql支持基于LOGICAL CLOCK的复制后，主从延迟得到了很大的改善，但是LOGICAL CLOCK一定程度上会受到master的并发度的影响。当master的并发度较低，每次组提交的事务数较少的时候，binlog在slave上的回放的并发度也会因此而降低，即使这些事务之间并没有任何冲突。示例：
Trx1 -----L----C---------------------------------->Trx2 ---------------L----C------------------------>Trx3 ------------------------L----C--------------->Trx4 --------------------------------L----C------->假定这些事务之间并没有任何冲突，由于它们的LOGICAL CLOCK周期没有重叠，在slave上也只能串行回放。为了解决这个问题，mysql8.0.1引入了基于WriteSet的复制。
「第二部分 原理」
LOGICAL CLOCK由两部分组成，分别是commit parent和sequence number。commit parent表示当前事务所依赖的事务的序号，只有依赖的事务完成后当前事务才能进行。WriteSet是一种更细粒度的事务冲突检测手段，它是在LOGICAL CLOCK的基础上，对事务的commit parent进行处理。例如，有如下两个事务：
Trx1 -----L----C------------->Trx2 ---------------L----C--->假定这两个事务没有任何冲突，但是他们的LOGICAL CLOCK区间没有重叠，原本不能进行并行回放，经过WriteSet处理后，这两个事务的commit parent可能会被修改，让LOGICAL CLOCK区间有可能重叠，使并行回放成为可能。
WriteSet冲突检测的原理：
- 全局有一个数据结构(实际上使用std::map)维护了一定数量的行的hash值与修改行的事务的sequence number之间的映射。
- 一个事务会记录所修改行的hash值，在事务提交写入binlog的时候，遍历该事务修改的行的hash值，在全局的map中进行查找，如果有相同的hash值表明有两个事务修改了同一行，记录有冲突的sequence number，取最大的sequence number作为该事务的commit parent（如果没有任何冲突，则commit parent设置为map中最小的sequence number）。
更详细的示例：
图中每一个方块代表一个事务，方块对应的区域代表事务影响的范围，如果有重叠则表示事务有冲突，每一个step代表一次组提交，T1-T8代表事务的执行顺序。如果不使用WriteSet，在slave上回放的时候的顺序：
<T1,T2>, <T3>, <T4,T5>, <T6>, <T7,T8>使用WriteSet后，在slave上的回放效果：
回放顺序：
<T1,T2,T3>, <T4,T5,T6,T7>, <T8>这里有一个地方需要注意，就是对于T2和T3，他们对应于同一个连接，然而在回放的时候却是并行的，可能导致事务的提交顺序不一致。解决这个问题有两种方法：
- slave_preserve_commit_order设置为on
- 使用writeset_session模式
writeset_session模式下同一个session的事务不能并发执行。它的原理很简单，在writeset的基础上，将事务的commit parent与当前session的last sequence number进行比较，取较大值作为新的commit parent。
「第三部分 源码分析」
3.1. 事务writeset更新
MySQL 5.7.6引入了事务的写集合，在计算事务依赖的时候可以直接使用。在开启了gtid，且binlog_format为row格式，且transaction_write_set_extraction不为OFF的实例上，写binlog的时候会将事务所修改的行的hash值添加到事务的写集合中，对应的函数是binlog_log_row和add_pke(pke是primary key equivalent的缩写)。函数add_pke所做的事情：
- 对所修改的表的主键和唯一键的key各计算一个hash值（hash字符串由更新行的index，db，table，value按照一定规则拼接，这里不深究），放入到事务的写集合中（利用主键和unique key的唯一性来检测冲突和依赖）。
- 记录表的外键信息，如果表是某一些表的父表，调用Rpl_transaction_write_set_ctx::set_has_related_foreign_keys进行标记；如果表是某一些表的子表，外键列不为NULL，且foreign_key_checks不为0，也会对这样的外键列计算一个hash值。
- 如果没有添加任何hash值到写集合中，调用Rpl_transaction_write_set_ctx::set_has_missing_keys进行标记，说明记录因为某些原因没有计算hash值（比如有的表没有主键）。
需要注意的是，如果表没有人为定义主键（不包括innodb内部自动生成的主键）也没有定义非空唯一键，则不会计算任何hash值，即使表有其它索引。
3.2. 事务依赖计算
在函数MYSQL_BIN_LOG::write_transaction入口处会调用Transaction_dependency_tracker::get_dependency来获取事务的依赖（获取sequence number和commit parent）。函数Transaction_dependency_tracker::get_dependency会根据变量binlog_transaction_dependency_tracking来决定使用哪种方式计算事务的依赖：
void Transaction_dependency_tracker::get_dependency(THD *thd, int64 &sequence_number, int64 &commit_parent) { sequence_number = commit_parent = 0; switch (m_opt_tracking_mode) { // 根据提交时的timestamp来决定依赖，COMMIT_ORDER是5.7引入的，这里不再深究 case DEPENDENCY_TRACKING_COMMIT_ORDER: m_commit_order.get_dependency(thd, sequence_number, commit_parent); break; // 根据事务的写集合来决定依赖 case DEPENDENCY_TRACKING_WRITESET: m_commit_order.get_dependency(thd, sequence_number, commit_parent); // writeset是在COMMIT_ORDER的基础上进行优化 m_writeset.get_dependency(thd, sequence_number, commit_parent); break; // writeset_session，同一个session的事务不能并发执行 case DEPENDENCY_TRACKING_WRITESET_SESSION: m_commit_order.get_dependency(thd, sequence_number, commit_parent); m_writeset.get_dependency(thd, sequence_number, commit_parent); // 在writeset的基础上对同一个session的事务做限制 m_writeset_session.get_dependency(thd, sequence_number, commit_parent); break; default: assert(0); // blow up on debug /* Fallback to commit order on production builds. */ m_commit_order.get_dependency(thd, sequence_number, commit_parent); }}函数Writeset_trx_dependency_tracker::get_dependency根据写集合对事务的commit parent进行优化，关键代码：
void Writeset_trx_dependency_tracker::get_dependency(THD *thd, int64 &sequence_number, int64 &commit_parent) { Rpl_transaction_write_set_ctx *write_set_ctx = thd->get_transaction()->get_transaction_write_set_ctx(); std::vector<uint64> *writeset = write_set_ctx->get_write_set(); // 检查是否能使用writeset bool can_use_writesets = // empty writeset implies DDL or similar, except if there are missing keys (writeset->size() != 0 || write_set_ctx->get_has_missing_keys() || /* The empty transactions do not need to clear the writeset history, since they can be executed in parallel. */ is_empty_transaction_in_binlog_cache(thd)) && // hashing algorithm for the session must be the same as used by other // rows in history (global_system_variables.transaction_write_set_extraction == thd->variables.transaction_write_set_extraction) && // must not use foreign keys !write_set_ctx->get_has_related_foreign_keys() && // it did not broke past the capacity already !write_set_ctx->was_write_set_limit_reached(); bool exceeds_capacity = false; if (can_use_writesets) { /* Check if adding this transaction exceeds the capacity of the writeset history. If that happens, m_writeset_history will be cleared only after using its information for current transaction. */ exceeds_capacity = m_writeset_history.size() + writeset->size() > m_opt_max_history_size; // 起始的parent值，history为空时为0，不为空时为当前history中最小的sequence // number int64 last_parent = m_writeset_history_start; // 遍历一个事务所有修改的行的hash值 for (std::vector<uint64>::iterator it = writeset->begin(); it != writeset->end(); ++it) { // 对每一个hash值都去history中寻找是否有对应的hash Writeset_history::iterator hst = m_writeset_history.find(*it); if (hst != m_writeset_history.end()) { // 如果一个行的hash存在于history中且对应的事务先于当前事务 if (hst->second > last_parent && hst->second < sequence_number) // 修改当前事务所依赖的事务的sequence number last_parent = hst->second; // 标记该行由当前事务修改 hst->second = sequence_number; } else { // 将hash值和事务的sequence number插入到history中 if (!exceeds_capacity) m_writeset_history.insert( std::pair<uint64, int64>(*it, sequence_number)); } } // 同时没有主键和非空唯一键的表不能使用writeset if (!write_set_ctx->get_has_missing_keys()) { // 当前事务所操作的table都有主键的前提下 // 取last parent和commit parent中的较小值 // 作为当前事务的commit parent (last_committed) commit_parent = std::min(last_parent, commit_parent); } if (exceeds_capacity || !can_use_writesets) { // 超过history最大值或者当前事务不能使用writeset则清空当前history m_writeset_history_start = sequence_number; m_writeset_history.clear(); } }}使用writeset有一定的限制：
- DDL不可以使用writeset
- 当前session 的 hash 算法和 writeset history 必须相同
- 事务所更新的列不能被其它表引用
- 事务的写集合存放的hash值数量不能超过binlog_transaction_dependency_history_size设定的最大值
- 没有主键或者非空唯一键的表，事务的依赖获取会退化到COMMIT_ORDER的方式
函数Writeset_session_trx_dependency_tracker::get_dependency对同一个session的事务的commit parent做出限制：
void Writeset_session_trx_dependency_tracker::get_dependency( THD *thd, int64 &sequence_number, int64 &commit_parent) { // 获取当前session提交的上一个事务的sequence number int64 session_parent = thd->rpl_thd_ctx.dependency_tracker_ctx() .get_last_session_sequence_number(); // 在commit parent和session parent中取较大值作为事务的commit parent if (session_parent != 0 && session_parent < sequence_number) commit_parent = std::max(commit_parent, session_parent); // 更新当前session的last sequence number thd->rpl_thd_ctx.dependency_tracker_ctx().set_last_session_sequence_number( sequence_number);}「第四部分 简易测试」
测试数据由sysbench生成：10张表，每张表10万行。使用sysbench进行300s的read-write测试，然后让slave回放压测产生的binlog，slave回放并行度为8，记录回放时间。
从机每秒回放事务数对比图：
可以看到，基于writeset的复制比基于commit_order的复制会快很多；当master并发度较低的时候，基于writeset_session的复制也会较慢，但比commit_order快；当并发度较高的时候writeset_session和writeset的复制速度比较接近，总体上writeset_session的速度要低于writeset。
「第五部分 总结」
在LOGICAL CLOCK的基础上，根据事务的写集合将事务的依赖进一步细化，让事务在从机上的回放的并发度进一步提高。WriteSet主要适用于master上并发度不高的情况，如果主并发度较高或者主从没有延迟则不需要使用，因为WriteSet会带来额外的内存与CPU的消耗，在一些小的实例上可能会造成资源紧张。
「第六部分 参考」
MySQL :: WL#9556: Writeset-based MTS dependency tracking on master：
https://dev.mysql.com/worklog/task/?id=9556
Improving the Parallel Applier with Writeset-based Dependency Tracking | MySQL High Availability：
https://mysqlhighavailability.com/improving-the-parallel-applier-with-writeset-based-dependency-tracking
腾讯数据库技术团队对内支持QQ空间、微信红包、腾讯广告、腾讯音乐、腾讯新闻等公司自研业务，对外在腾讯云上依托于CBS+CFS的底座，支持TencentDB相关产品，如TDSQL-C(原CynosDB)、TencentDB for MySQL(CDB)、CTSDB、MongoDB、CES等。腾讯数据库技术团队专注于持续优化数据库内核和架构能力，提升数据库性能和稳定性，为腾讯自研业务和腾讯云客户提供“省心、放心”的数据库服务。此公众号旨在和广大数据库技术爱好者一起推广和分享数据库领域专业知识，希望对大家有所帮助。