针对高竞争电商负载的事务处理优化原型系统

张舒燕 王清帅 张蓉

摘要：现代多核主存数据库在高竞争的负载下仍然不能达到理想的性能，获得高吞吐量的障碍是试图访问相同数据的并发冲突事务，这些事务争用相同的资源，在传统数据库中必须串行执行，促销活动中的电子商务（电商）负载就是这种高冲突的事务，本研究从两个方面对电商负载的事务处理方案进行了优化，首先，由于产品数量有限，许多购买请求不会成功，数据库系统可以通过提前过滤掉无效请求来节省资源、降低锁竞争，其次，大量的写操作针对同一商品，故在写操作之间实现锁共享，再次降低锁竞争，基于此想法本文实现了原型系统Filmer，大量的实验表明，过滤和合并可以提高处理高竞争电商负载的效。

关键词：事务处理：并发控制：高竞争

中图分类号：TP392 文献标志码：A DOI：10.3969/j，issn，100-5641.202091005

0引言

随着电子商务（电商）业务的发展，大量的离线交易被在线交易取代，作为事务处理的关键支柱，数据库管理系统承受的压力越来越大，不同于传统的实体店交易，在线交易打破了空间的限制，数以百万甚至千万计的顾客可以在同一时间发起购买请求，阿里巴巴在购物节中每秒要处理的交易高达491 000个，这种业务需要数据库有能力处理高并发的负载。

在促销活动期间，大量的用户会在同一时间读或写相同的库存清单，导致多个事务争相访问相同的数据项，造成高竞争，此时，短时间内有大量购买请求同时到达数据库，但由于商品数量有限，只有小部分有效的请求可以成功下单，高竞争的场景会使系统响应时间变长，当一个请求没有获得响应时，用户很可能会重复发送请求，进一步增大了无效的负载量，给数据库管理系统带来了更大的压力，即使使用具有多核处理器的主存数据库，在高竞争的情况下表现出的性能也并不理想。

当前，数据库系统并发控制模块的实现中，乐观的并发控制（optimistic Concurrency Control，OCC）在调度事务的操作时假设没有非可串行化行为发生，并且只在违例很明显的时候做恢复，在高竞争的负载下，基于乐观的并发控制协议频繁回滚事务，所以展现出的性能较差;悲观的并发控制需要频繁地加锁和释放锁，当负载的冲突率很高时会发生严重的锁竞争，即使对并发控制协议做了优化，也无法消除对同一数据的大量写写冲突，这极大地减少了事务之间的并行度并限制了数据库的吞吐量，

为了解决这个问题，本文设计并实现了一个数据库原型系统Filmer，利用工作线程与数据绑定，减少中央锁表上的竞争;通过加入无效操作过滤器以及合并同质操作（定义1）来提高整体的事务处理并发性，无效操作过滤能降低系统处理的任务量，同质操作合并能降低由于写写冲突造成的锁竞争，Filmer的实验证明在数据库内部实现无效流量过滤，以及通过写操作之间共享资源的策略能有效地提高事务系统的性能。

定义1（同质操作）如果Ⅳ个操作满足以下三个条件，则称这Ⅳ个操作为同质操作，

（1）这Ⅳ个操作都是由相同SQL模板生成的update操作;

（2）这Ⅳ个操作只对属性值进行增量的修改;

（3）这Ⅳ个操作访问相同的元组，

本文的内容组织如下：第1章介绍处理高竞争负载的相关工作;第2章简要介绍本文提出的原型系统Filmer的总体框架;第3章详细描述过滤器的工作原理;第4章阐述操作合并模块的设计与实现;第5章通过实验展示了过滤、合并的效果;第6章总结全文。

1相关工作

电商应用对一致性的要求通常不高，所以解决读操作争用资源的方法有很多，一个具有代表性的方法是采用读写分离架构，即读和写由不同的服务器负责，主服务器处理写请求和极小部分的读请求，从服务器处理剩余的读请求，如果想进一步减轻数据库管理系统处理读操作的压力，还可以在数据库的上层构建缓存，使得只有缓存缺失/过期产生的读请求才会被发送到数据库。

写操作对资源的争用较难解决，Orthrus提出了两个原则，一是分配专门的线程负责并发控制，每个并发控制线程负责数据库对象的一个不相交的子集，以避免数据移动和同步开销，二是以一致的顺序为事务授予锁，以避免死锁，竞争感知的锁调度算法罔从另一个角度改善了基于锁的协议，通过捕获并发事务之间的竞争和依赖，该算法优先将锁授予那些阻塞了较多其他事务的事务，本文的工作并不关注锁调度，可与此算法互为补充，MOCC（Mostly-Optimistic Concurrency Control）在OCC中引进了锁机制，当一个事务访问热点数据时，它需要先获取数据上的锁，此方法减少了高冲突事务的回滚率，所有这些工作都没有针对高竞争电商负载中存在的大量无效操作和相似操作进行优化，

负载资源共享也是一个被研究了很久的话题，当一个查询内部有多个相似的子查询时，MQO（Multiple-Query Optimization）支持单个查询内的资源共享，无论子查询在一个OLAP（on-LineAnallytical Processing）类型的查询中出现了多少次，都只被执行一次，MQJoin和CJOIN使用流水线技术在join操作之间共享资源，但是join操作并不是OLTP（on-Line Transaction Processing）负载中的常见操作，SharedDB和BatchDB则考虑了OLTP负载，SharedDB将查询编译成一个较大的查询计划进行批量处理，不同的查询共享相同的操作符，BatchDB将OLTP副本和OLAP副本分离，资源共享只在OLAP型查询中发生，以上研究的焦点都是处理OLAP负载，OLTPShare是最接近本工作的，OLTP负载中的操作被合并執行以适应高负载量的场景，但是，OLTPShare只合并单点的只读操作，而本工作关注的是写操作，另外，OLTPShare要求被合并的语句是其所在事务的唯一语句，Filmer并没有这样的限制。

2Filmer系统架构

在电商应用中，一旦促销活动开始，减库存操作会使得短时间内有大量用户访问极少量数据，是数据库吞吐受限的主要原因，以面向峰值负载的测试基准PeakBench中的造成高冲突的负载订单提交事务为例。

其中，opl是一个读操作，一般不会阻塞数据库系统的执行，op2是一个典型的减库存操作，它将秒杀商品表SeckillPlan中某个商品的剩余数量减少一个，当负载的竞争程度很高时，参数p1的分布符合Zipf分布，即集中在少数几个值上，大量并发的订单提交事务要想修改相同的商品项，冲突的事务必须串行执行以保证执行的正确性，如果可以将这些并发的更新操作合并执行，则会降低锁冲突，提高事务处理的效率，例如，可以将两个不同事务的op2合并为：UPDATE SeckillPlan SET sl skpcount=sl skpcount-2 WHERE sl skpkey=p1 AND sl skpcount>=2.这样就可以一起执行，共享一把写锁，再者，少量商品面对大量订单的话，商品的数量决定了大量op2无法成功，但却还要串行加锁执行，可以尝试在数据库入口处构建过滤器，尽早把这样的无效操作过滤掉，减少其在数据库内的处理，从而减少事务在相同数据上的竞争。

针对这一问题，本文设计并实现了Filmer基于内存的事务型数据管理原型系统，系统架构图见图1.负载的执行分布在四个模块中，其处理流程如下。

客户端发送的SQL操作首先到达查询分析器，查询分析器由一个过滤器和一个分发器组成，过滤器判定当前操作是否有效，对所有无效的操作，系统将直接向客户端返回“fail”;否则，操作由分发器进行进一步的处理，分发器负责两件事：其一，基于要访问的数据将每个CRUD操作（增删改查）分发给执行器处理;其二，将事务操作（事务开始、事务提交或事务中止）传给事务管理器，

在执行器中，数据根据主键划分为不相交的逻辑分区，由于基于乐观的并发控制协议在高竞争的负载下回滚频繁，Filmer实现了2PL悲观协议（Two-Phase Locking），每个逻辑分区都由一个不同的工作线程管理，并且每个工作线程都为其负责的数据维护一个本地锁表，工作线程每次取出一组同质操作，在本地锁表上锁定要访问的数据，无法获取锁的操作将置于等待队列中，并在释放锁后重新执行，当线程执行的操作被挂起时，线程不会阻塞，而是直接执行下一个操作，如果操作成功锁定数据，则工作进程将首先从存储中读取所需的数据，然后在其事务上下文中记录更新的结果和使用的锁，

事务管理器为不同的事务操作选择不同的执行方法，对于一个事务开始或结束操作，它只需要创建或删除相应事务的上下文，对于事务提交操作，事务管理器通知日志管理器写入日志，日志持久化后，日志管理器向事务管理器发送提交消息，然后事务管理器逐个处理消息，将事务上下文中的更新写入存储，此时，事务实际上已完成，最后，查询分析器向客户端答复事务已提交。

Filmer架构的三个主要部分（查询分析器、事务管理器和执行器）中的所有线程都是非阻塞的，减少了由内核中上下文切换造成的资源浪费。

3查询分析器

过滤无效操作可以降低系统负载压力，减少系统资源消耗，过滤后的负载通过分发器发送给执行器或事务管理器。

3.1过滤器

先根据sQL语句的谓词获取要访问元组的主键值，如果定位谓词（那些用来访问索引的谓词）基于主键，则直接获得;如果是基于二級索引的，则系统将通过访问二级索引获取对应的主键值。

预处理之后，任务便被转交给了过滤器，过滤器中会维护一张过滤表来记录失败过的更新，以便确定一个减库存操作是否有效，过滤表中表项格式为三元组，即<表名，主键，列号>，记录减库存失败的对象，其中表名和主键指明该更新试图修改的元组，列号指明该更新修改的具体列，注意，这个列的值域需要被sQL语句中的谓词要求属于一个左闭区间，如果一个失败的减库存操作试图修改多个列，则将在过滤器表中添加多个过滤项。

过滤器处理操作的方式首先取决于操作的类型，如果是减库存/上货操作，则其<表名，主键，列号>将被提取（可能超过一项），用于与过滤表中的项进行比较，如果发现有交集，则分以下两种情况，

（1）对于减库存类型的操作，可以确定其是无效的操作，查询分析器丢弃该操作并直接返回“fail”给客户;

（2）对于上货类型的操作，查询分析器从过滤表中删除产生交集的项并将操作分发给执行器，

对于所有其他情况，操作将直接被判定为有效操作，并转交给分发器。

系统设计的过滤表是一个并发数据结构，会被多个线程并发访问，查询分析器需要检查更新操作的信息是否在过滤器表中，因此过滤表经常被读取，但仅当向过滤表中添加或删除条目时才会写过滤表，因此，系统实现的过程中采用copy-on_write技术优化过滤表操作，另外，在竞争激烈的情况下，过滤表通常很小，并且仅保存已售罄的热门商品，因此复制的成本不高。

3.2分发器

如果一个操作有多个目标元组，分发器将对其进行拆分以确保分发到工作线程的操作不需要访问其他数据分区，每个目标元组对应一个子操作，拆分后，所有操作都是基于主键的单点访问。

分发器根据操作试图访问的数据对应到工作线程，在分发任务之前执行同质操作合并，系统为每个数据分区定义并维护一个模式操作映射表（PO-Map），如图2所示，模式是操作中的关键信息缝合成的字符串，也可以是系统为操作直接分配的唯一字符串，具有相同模式的操作才可能同质，并被放入操作列表。

有机会合并的操作必须满足以下两个条件：

（1）是更新操作;

（2）操作只对属性值进行增量的修改，

模式的构成包括：操作访问的表、操作尝试修改的属性和相应的运算符、条件谓词中的关系运算符和属性，以及要访问的元组的主键值，模式相同的操作会被放在同一个操作列表中，这个方法确保有相同模式的操作一定由相同的事务模板产生并且访问相同的元组，在图2中，01和02具有相同的模式“R3c-c≥”，这意味着它们都访问表R中主键为3的数据，都在属性c上做减法，并且都要求c大于等于某个常数，相对地，如果一个操作不能满足上述两个条件，我们不需要计算它的模式，只需给它分配一个唯一的字符串作为它的模式，然后把它和它的模式一起放人PO-Map中（如图2中的03即可）。

4执行器

在执行器中，工作线程一次从对应的Po-Map中取出一项并检查列表中的操作数，如果有不止一个操作将进行操作合并，set后表达式的合并相对容易，如图2中将01的“set c=c-1”和02的“set c=c-2”合并为“set c=c-3”，谓词通常分为两类：定位谓词和条件谓词，由于同质操作访问相同的元组，它们的定位谓词一定相同，所以不用再进行合并，除了定位谓词之外，一个sQL语句中可能还有其他的谓词，把这些剩余的谓词称作条件谓词，条件谓词的作用是进一步检查定位谓词选出的元组是否符合一些额外的条件，条件谓词的合并需要根据应用逻辑配置，最简单的方法是取交集，例如，将01和02中的“c≥1”和“c≥2”合并为“c≥2”，但是，如果这两个操作的语义是当库存足够的时候减少库存，那么这种取交集的合并方法显然不符合原意，在此场景下，可以将关系运算符之后的数字相加，即合并为“c≥3”，目前，Filmer仅支持这两种谓词合并的方式，OLTP负载中的谓词一般都不复杂，基于应用逻辑指定合并方式是一种可行的方式。

完成操作合并之后，工作线程需要为操作争取数据锁，就像传统的写锁一样，合并操作的写锁不兼容其他写锁和读锁，但是，合并写锁由多个事务共享，没有事务被允许重新获得锁，即使有些事务已经占有了锁，这是为了保证事务的可串行化，所以，需要保证参与合并的事务中除被合并操作之外，没有其他操作同被合并操作访问的数据相同。

另外，在过滤表中添加新项是执行器的责任，当工作线程发现一个减库存操作由于违反了约束属性上的限制而失败，它会将该操作的信息添加到过滤表，为后续的过滤做准备。

在此阶段，所有数据更新都只记录在事务上下文中，在事务提交后更新会被写入存储中，当事务被执行时，它请求的锁和更新就被记录在上下文中，合并操作的更新只需要记录在一个事务的上下文中，这种方法减少了事务操作内存的次数，待事务提交或回滚，事务管理器释放事务上下文中记录的锁，通知工作线程，就可以继续执行被这些锁阻塞的操作了，但是，如果参与合并的事务中有一个发生回滚，则整个合并操作都将被一起回滚，为了保证事务的原子性，必须回滚与之合并的所有事务，为了保证这一点，所有参与合并操作的事务号被记录在同一个合并集合中，只要合并集合中有一个事务回滚，所有其他的事务必须一起回滚，除此之外，在同一个合并集合中的事务还必须同时提交，以避免造成集合中有的事务已经提交了而有的事务却要回滚这样不可恢复的情况，在高竞争的电商负载中，一个成功修改库存的事务被回滚的可能性很小，假设一个事务被回滚的概率为p，那么由n个事务合并而成的一组事务被回滚的概率为1-（1-p）n，由于p很小，即使将n的大小设置为商品库存的数量，（1-p）”仍旧是个接近1的值，这一组事务被回滚的概率依旧很小，比商品库存还大的n是没有意义的，如果大量事务被一起回滚的风险实在不可接受，我们可以调整合并的粒度n来保证每次被合并执行的操作小于某个阈值，合并粒度n越大，系统的吞吐量越大，合并回滚风险也越大，应用开发者需要根据具体应用中事务回滚的概率p选择一个最适合的合并粒度n。

5实验分析

5.1实验环境及测试负载

硬件环境：本系统部署在单个物理节点上，该节点含有2个CPU，型号为Intel Xeon Silver 4 110@2.1 GHz CPU;内存为120 GB;存储为4 TB，RAID-5.7200转的HDD磁盘。

测试负载：实验中的测试负载是PeakBench，PeakBench抽象了秒杀应用的业务模型，可以模拟秒杀活动发生时的高并发事务负载，并控制负载的冲突粒度，其中的订单信息处理请求负载包括五个事务，分别是订单提交、订单支付、订单取消、订单查询和订单过期处理，由于造成大规模高冲突事务的是订单提交事务即减库存操作，所以本实验主要测试订单提交事务的效率，该事务共包括四条SQL操作：一个读操作和三个写操作。

默认设置：默认情况下，Filmer负责查询分析器的I/O线程个数设为4.负责执行器的工作线程个数设为2.负载的Zipf参数（代表负载的竞争程度）设为2.商品个数为1亿。

5.2实验结果

5.2.1无效操作处理效率

本节实验检验过滤器处理无效操作的效率，首先，为了直观展示过滤器对系统处理无效操作效率的影响，本实验将所有商品的库存均设为20万，观察成功事务吞吐和失败事务吞吐随时间的变化，实验结果如图3所示。

从实验结果中可以看出，14 s之前，沒有失败的事务，从第15 s开始，一些比较热门的商品售罄，大量减库存操作开始失败，从而使得失败事务吞吐上升，随着时间的流逝，卖完的商品越来越多，当Filmer的过滤功能开启，系统处理失败事务的效率会提升1.5倍左右，同时，由于无效操作的过滤节省了后续工作线程的资源，成功事务的吞吐也略有提高。

过滤器还改善了数据库系统处理高竞争负载时的可扩展性，图4中的实验将所有商品个数都设为0.此时所有的吞吐都是失败事务吞吐，改变I/O线程或工作线程的个数，观察Filmer的吞吐变化，前4组实验中，工作线程个数都是2.I/O线程个数从1增加到4.可以发现，当过滤功能未打开时，由于负载中大量无效操作都是冲突的，必须由工作线程一个个加锁串行执行，使得工作线程成为“瓶颈”，I/O线程个数到达2之后，再怎么增加系统吞吐也没有明显变化，第五组实验中将工作线程个数增加了一倍，仍旧无法提高吞吐，这是因为负载冲突较高时，大量SQL请求访问同一条数据，同时数据分区和工作线程绑定，增加工作线程的个数无法消除热点数据上工作线程的“瓶颈”，相对地，当过滤功能开启，不同I/O线程可以并行处理冲突的无效操作，极大地改善了系统的可扩展性，但事务中有效的冲突操作仍需交由工作线程处理，当I/O线程组的吞吐大到一定程度后，工作线程会再次成为“瓶颈”，这也是当过滤功能打开时，吞吐无法线性扩展的原因。

5.2.2高竞争更新操作处理效率

高竞争的负载往往具有高并发、高冲突的特点，在传统的数据库执行模式中，当负载的冲突程度很高时，增加并发的数据库事务量并不能提高吞吐，因为这些事务到达数据库后仍旧需要逐个加锁串行执行，Filmer的合并功能很好地解决了这个问题，图5所示的实验中，并发因子代表事务的并发量，并发因子越大，同一时刻数据库中需要处理的事务越多，改变并发因子，观察系统吞吐和时延的变化，关闭合并功能时，增大并发因子并不能使系统吞吐增加，而仅仅使事务时延变得很高，因为大量更新操作是相互冲突的，一个事务需要等待前面到达的冲突事务全部处理完后才能执行，打开合并功能后，冲突的操作可以合并执行，此时并发因子越大，操作合并执行的机会就越大，系统吞吐最高可达之前的3.6倍，同时，因为事务处理效率整体提升，时延也相对合并未打开时降低了很多。

图6所示的实验数据展示了Filmer的合并功能处理高竞争负载的显著优势，将并发因子设为50.改变zipf参数，观察系统吞吐和时延的变化，合并功能关闭时，随着负载冲突程度的增加，吞吐下降明显，同时时延也受到很大影响，打开合并功能后，冲突最高的情况下（zipf参数为2.5），竞争程度也最高，此时吞吐可达之前的3.7倍，而时延只是之前的28%，这是因为合并功能使得冲突操作可以并行执行，合并在一起的操作所属的事务不再需要互相等待，但是合并而成的大事务如果是冲突的，仍旧需要串行执行，所以冲突程度增加后，吞吐仍会下降，时延也略有增加。

6结语

针对高竞争电商负载，本文从两个方面优化数据库管理系统的内核实现，其一是在查询处理的输入层实现无效操作过滤器，将肯定无法返回有效商品的操作直接过滤掉，以降低系统负载压力;其二是将高竞争电商负载中大量冲突的减库存操作合并执行，增大事务的并发执行度，降低锁竞争，本文实现了一个数据库原型系统Filmer，并通过实验证明，过滤和合并操作使系统处理高竞争负载的效率得到了极大提升。