一种事务并发控制方法

1.本发明属于分布式数据库
技术领域：
：，具体涉及一种事务并发控制方法。
背景技术：
：：2.事务是一组访问或修改数据项操作的有序集合，它保证了acid的特性。事务并发控制算法的任务是确保在多个事务同时存取数据库中同一数据时不破坏事务的隔离性。主流的事务并发控制算法包括以下几类技术：3.两阶段锁(two-phaselocking，2pl)：通过在事务的执行过程中加锁来保证隔离性。在增长阶段，事务为读、写的数据项分别获取共享锁、独占锁。事务可能会因为所请求的数据项已被加锁而需要等待锁被释放；在收缩阶段，事务释放所持有的锁，并不允许获取新的锁。两阶段锁的方式在数据项有大量冲突场景下优势明显，它通过锁机制保证了事务的推进是有效的，然而在少量冲突场景下，加锁机制却没有优势。相反加锁所产生的开销(在分布式环境下网络通信开销)逐渐成为影响并发控制性能的瓶颈。4.乐观并发控制(optimisticconcurrencycontrol，occ)：在执行阶段会并发执行事务，多事务间不相互产生影响；在验证阶段则需要根据自事务开始以来提交的所有事务或当前处于验证阶段的所有事务来验证事务是否可序列化来确定执行结果。如果事务可以提交，则需要将该事务产生的修改持久化到存储，否则会回滚事务。相比于两阶段提交，在低冲突场景下，乐观并发控制节约了不必要的加锁的开销。但在高冲突场景下两阶段锁的并发控制方法能够让事务逐个提交，然而乐观并发控制会产生很多事务回滚，对事务执行的效率产生影响。5.分区并发控制(partitionconcurrencycontrol，partcc)：将所有数据项划分为多个数据分区，每一个分区存在唯一的锁。事务中对任意数据项的修改需要首先获取数据项所在分区的锁，在事务结束时释放所持有的锁。这种并发控制方法适用于可分区的事务场景，即一个事务中所有修改的数据项，均存在于一个数据分区，这样事务的执行过程中只需要获取该分区的锁。然而当一个事务中所有修改的数据项分布在多个不同的分区时，由于需要获取多个分区的锁，分区并发控制的性能将会下降。6.两阶段提交(two-phasecommit，2pc)：将分布式事务分成了两个阶段，分别为准备(prepare)阶段和提交(commit)阶段。在准备阶段由协调者去询问所有的参与者，是否可以执行事务，只有当所有参与者都确定之后，才可以进入提交阶段真正让参与者执行事务。7.通过上述几种并发控制方法不难看出，合适的并发控制方法是一种权衡。对于不同的负载场景，相同并发控制方法的吞吐量可能会有几倍的变化。因此没有一种并发控制方法是可以适用于所有负载场景，不合适的并发控制方法可能会导致性能显著下降。业务人员需要提前对要执行的工作负载中的事务冲突程度、类型、规模进行分析权衡后在进行选择。技术实现要素：8.为解决上述技术问题，本发明提出了一种事务并发控制方法，应对实时多变的事务类型和不同的工作负载，根据实时收集到的数据项事务特征信息(即数据项事务特征信息)，来调整数据的分区，并为每个分区选择合适的并发控制方法(对每个分区中数据的写操作采用对应并发控制方法)，同时根据分区的负载信息，来移动或合并分区，以均衡节点之间的负载。9.本发明采用的技术方案为：一种事务并发控制方法，具体步骤如下：10.s1、构建一套事务系统；11.s2、事务系统中每个事务索引实时收集分区的数据项的事务特征信息并动态调整事务的分区；12.s3、基于步骤s2，为每个分区选择合适的并发控制方法，生成一个并发控制计划，交给分区管理器；13.s4、分区管理器根据并发控制计划调整事务索引中的数据分区，并向客户端分发并发控制计划，根据并发控制计划中的分区范围，和每个分区的并发控制方法来进行读写操作，完成自适应的事务并发控制方法。14.进一步地，所述步骤s1中，所述事务系统包括客户端sc、事务系统ts和存储系统ss，ts包括一个事务控制器tc和多个事务索引ti。15.进一步地，所述步骤s1中，所述事务索引ti具体如下：16.所述ti包括：txindex，deregion，debucket。17.每一个ti向外提供txopservice服务，并由txopserviceimpl具体实现；txopserviceimpl中的txindex数据结构实现了txopservice服务的方法。18.txindex包括regionpartitiontable和partitionmanager两部分。19.其中，regionpartitiontable是一个map《range，deregionptr，rangecomparator》类型，即是一个从data-range到region的映射组成的数据分区集合。当txindex所实现的方法被调用，首先根据所调用的data-range，从regionpartitiontable中找出其对应的deregion，然后继续调用deregion所实现的txopservice的方法。20.partitionmanager是一个独立于regionpartitiontable的后台模块，通过不断调用partitionservice服务来获取到最新的属于该txindex数据分区信息，并对regionpartitiontable中已有的分区进行调整。21.deregion表示一个data-range中所有data所组成的数据集合。22.deregion包含固定数量的debucket，debucket负责存储数据项数据，data-range中的每一个data会被固定的哈希到一个debucket中。23.当deregion所实现的txopservice的方法被调用时，首先会根据所调用的data找到其所属的debucket，然后继续调用debucket所实现的txopservice的方法。24.debucket包括demvcc和一个mutex。25.当debucket所实现的txopservice的方法被调用时，会首先使用mutex加锁，保证在事务处理阶段的atomic-read-and-write语义。demvcc存储了多版本的数据项数据。26.在deregion中还有regionpersist，regiondependence，regionmetric三个后台模块分别负责将此region中已提交的数据下沉到ss，依赖关系收集和上报，统计信息收集和上报，具体如下：27.regionpersist会定期调用regionservice服务的getminats方法。然后基于最新的min-ats，遍历该region的bucket，寻找可以下沉到ss中的已提交的数据。最终调用storageservice服务中的batchstore方法将数据下沉到ss中，并清除debucket中已被下沉的数据。28.regionmetric会统计一段时间内，其所属region的读写统计信息。这些统计信息使用bvar结构，即bvar：：latencyrecorder数据类型，记录延时和tps信息，并在每次涉及到该region数据项的读写流程完成后更新。29.最终regionmetric会定期的调用regionservice服务的regionmetric方法上报给tc。这些记录在regionmetric中的统计信息，反映了p(partition)中的分区负载情况。30.demvcc结构体记录包括写冲突数量、事务操作数量的统计信息，即bvar：：window《adder《int》》数据类型，记录在一段时间内的累加值，这些信息反映c(data)和l(data)的大小，并可以此计算出数据项的d(data)。当数据项的d(data)大于λ时，将自己加入到regionmetric中的热点数据项集合中。最终会在regionservice服务的regionmetric方法中被上报给tc。tc根据每个region的统计信息，调整region中数据的分布，包括分裂或合并region，并最终由partitionmanager来完成分区中数据的调整。31.进一步地，所述步骤s1中，所述事务控制器tc具体如下：32.所述tc包括：dependencemanager、ccplanner、partitionmanager和txidtable。33.tc提供txservice、regionservice和partitionservice三种服务，由各自的serviceimpl实现。serviceimpl中包括dependencemanager、ccplanner和partitionmanager三个模块，分别负责依赖冲突的发现、并发控制方法的选择，数据分区的管理和变更。34.txidtable是生成，存储，回收每一个事务唯一的txid的结构。txid中主要保存了的事务的开始/结束时间戳、依赖和被依赖的其他txid集合、在事务开始阶段注册的提前验证的回调函数。35.其中，txid由txidmap负责存储和索引。txidmap是一个经过shard的map《timestamp，txidptr》结构，用来建立并存储从事务开始时间戳到txid结构的映射关系。36.regionservice服务的regionmetric方法会被每一个分区定期的调用，上报的统计信息包括：37.(1)在上一个时间周期内，分区处理的读写请求总数量。38.(2)在上一个时间周期内，分区中所有d(data)超过阈值λ的数据项；39.接着regionserviceimpl把收到的分区统计信息依次交给ccplanner。ccplanner根据收到的每个分区的统计信息按如下顺序调整分区：40.1、将上一个时间周期内，分区中所有d(data)超过阈值λ的数据项，即悲观数据项，记录在partitionconfig中，sc会根据partitionconfig中的悲观数据项来进行加锁；41.2、若此时分区中所有悲观数据项的数量超过阈值，则进行分区分裂；42.3、若上一个时间周期内，分区处理的读写请求总数量超过阈值λ，则进行分区分裂；43.4、若该分区与其左侧分区合并后可以满足前两条不分裂，则进行分区合并。44.接着ccplanner把根据分区统计信息产生的分区变更信息传递给partitionmanager。45.partitionmanager中保存了当前的分区路由表(map《range，partitionconfig，rangecomparator》数据类型)，sc和ti不断的通过partitionservice服务的getpartition方法获取最新的分区路由表。当partitionmanager收到来自ccplanner的分区变更信息时，首先会把该变更信息应用到分区路由表上，并使分区路由表的版本号自增。所有ti获取到更新的分区路由表后，ti中的partitionmanager对regionpartitiontable中的deregion进行调整。当所有的ti都完成了分区路由表的更新后，继续下一次的分区变更。46.进一步地，所述步骤s2具体如下：47.首先设置两种数据项的事务特征：48.dataentrycontentionc(data)表示并发事务对数据项的竞争程度，由一段时间内该数据项的冲突率来表示：[0049][0050]其中，w表示一段时间内所有对该数据项的写操作的数量，写操作包括预写和锁，w∈w表示w中写冲突的数量；c(data)表示一段时间内该数据项的冲突率，且c(data)越趋近于1，该数据项的冲突率越高，越需要针对该数据项采用悲观加锁的并发控制方法，减少冲突回滚的概率；c(data)越趋近于0，该数据项的冲突率越小，适合采用乐观的并发控制方法，以减少加锁带来的开销。[0051]dataentrytxnlengthl(dara)表示涉及到对任意数据项写操作的事务中，写该数据项操作后该事务的大小：[0052][0053][0054]其中，ot表示事务t的操作总数，ot∈ot表示事务t的在写数据项data后到提交前的操作数，l(data，t)表示事务t的在写数据项data后到提交前的操作数与t的操作总数的比值；l(data)表示一段时间内，所有涉及到写数据项data操作的事务的l(data，t)按照事务大小的加权平均；l(data，t)越大，写数据项data在事务t中越靠前，越需要针对该数据项采用悲观加锁的并发控制方法，以防止出现由于写数据项冲突，导致大量后续操作需要回滚的情况；反之适合采用乐观的并发控制方法。[0055]在进行对于某一数据项data的并发控制方法选择时，同时考虑c(data)和l(data)两个特征，设置datapessimismdegreed(data)：[0056]d(data)＝α*c(data)+(1-α)*l(data)[0057]其中，α表示系统参数，表示c(data)和l(data)两个特征在d(data)中的比重；当d(data)达到预先设定的阈值λ时，将为该数据项使用悲观的并发控制策略，低于阈值λ时，采用乐观的并发控制策略。[0058]在所述事务系统中，全局的数据项按照data-range进行分区，所有分区分散在ti中。设置partitionloadp(partition)衡量一个数据分区的负载大小，和事务竞争程度，其由两部分组成：[0059](1)一段时间内，该分区内读写操作的总数量，反应该数据分区的负载大小；[0060](2)一段时间内，该分区内所有d(data)大于λ的数据项数量，反映该分区内数据项的事务竞争程度。[0061]每一个事务索引实时收集并计算出分区内的c(data)、l(data)、d(data)、p(partition)信息，分区的大小，范围，以及对应分区的并发控制方法根据分区内的特征信息来实时调整。[0062]进一步地，所述步骤s3具体如下：[0063]基于步骤s2，每个事务索引ti收集并计算出所有属于它的分区的各自的c(data)、l(data)、d(data)、p(partition)信息，并定时上报给并发策略选择器ccplanner；ccplanner根据实时的特征和统计信息，动态调整事务的分区，并为每个分区选择合适的并发控制方法，从而生成一个并发控制计划ccplan。[0064]本发明的有益效果：本发明的方法首先构建一套事务系统，事务系统中每个事务索引实时收集分区的数据项的事务特征信息并动态调整事务的分区，为每个分区选择合适的并发控制方法，生成一个并发控制计划，交给分区管理器，分区管理器根据并发控制计划调整事务索引中的数据分区，并向客户端分发并发控制计划，根据并发控制计划中的分区范围，和每个分区的并发控制方法来进行读写操作，完成自适应的事务并发控制方法。本发明的方法以基于数据项事务特征的自适应并发控制机制，动态地根据事务规模，冲突率等特征动态选择合适的并发控制方法，均衡了节点之间的负载，有效应对了实时多变的事务类型和不同的工作负载。附图说明[0065]图1为本发明的一种事务并发控制方法的流程图。[0066]图2为本发明实施例中事务系统结构框架图。[0067]图3为本发明实施例中ti架构图。[0068]图4为本发明实施例中regionmetric中记录的统计信息图。[0069]图5为本发明实施例中demvcc中记录的统计信息图。[0070]图6为本发明实施例中tc架构图。[0071]图7为本发明实施例中数据分区动态变化的示意图。[0072]图8为本发明实施例中并发控制计划示意图。具体实施方式[0073]下面结合附图和实施例对本发明作进一步的阐述。[0074]如图1所示，本发明的一种事务并发控制方法流程图，具体步骤如下：[0075]s1、构建一套事务系统；[0076]s2、事务系统中每个事务索引实时收集分区的数据项的事务特征信息并动态调整事务的分区；[0077]s3、基于步骤s2，为每个分区选择合适的并发控制方法，生成一个并发控制计划，交给分区管理器；[0078]s4、分区管理器根据并发控制计划调整事务索引中的数据分区，并向客户端分发并发控制计划，根据并发控制计划中的分区范围，和每个分区的并发控制方法来进行读写操作，完成自适应的事务并发控制方法。[0079]在本实施例中，所述步骤s1具体如下：[0080]如图2所示，所述事务系统包括：客户端(sc，sdkclient)、事务系统(ts，transactionsystem)和存储系统(ss，storagesystem)。[0081]sc向外暴露数据项事务接口，并负责开启和结束事务，处理事务请求。包括缓存请求和根据数据分片信息向ss或ts进行读写请求的转发。[0082]ss负责以多版本的形式存储ts中已提交的数据，供sc读取。ss可以由多种存储服务来实现，包括对象存储，文件存储，这些存储服务需要各自实现ss定义的api，才能够完成和sc以及ts之间的交互。[0083]ts负责进行事务间的并发控制以及已提交数据的缓存。ts包括一个事务控制器(tc，transactioncontroller)和多个事务索引(ti，transactionindex)两部分。全局的数据按照data-range进行分区并分布在多个ti中，ti负责缓存已提交的数据和保存未提交事务的预写或锁信息，以提供事务的读写和冲突检测服务，并定期将已提交的数据下沉到ss中。另外还负责收集数据的事务特征、分片的负载信息并上报给tc；tc则负责进行时间戳分配，数据分片调度，以及根据事务特征进行并发控制方法的选择。[0084]在本实施例中，所述步骤s1中，所述事务索引ti具体如下：[0085]transactionindex(ti)的架构如图3所示。[0086]所述ti包括：txindex，deregion，debucket。[0087]每一个ti向外提供txopservice服务，并由txopserviceimpl具体实现。txopserviceimpl中的txindex数据结构实现了txopservice服务的方法。[0088]txindex包括regionpartitiontable和partitionmanager两部分。[0089]regionpartitiontable是一个map《range，deregionptr，rangecomparator》类型，即是一个从data-range到region的映射组成的数据分区集合。当txindex所实现的方法被调用，首先会根据所调用的data-range，从regionpartitiontable中找出其对应的deregion，然后继续调用deregion所实现的txopservice的方法。[0090]partitionmanager是一个独立于regionpartitiontable的后台模块，通过不断地调用partitionservice服务来获取到最新的属于该txindex数据分区信息，并对regionpartitiontable中已有的分区进行调整。[0091]deregion是一个data-range中所有data所组成的数据集合。deregion包含固定数量的debucket，debucket负责存储数据项数据，data-range中的每一个data会被固定的哈希到一个debucket中。当deregion所实现的txopservice的方法被调用时，首先会根据所调用的data找到其所属的debucket，然后继续调用debucket所实现的txopservice的方法。[0092]debucket包括demvcc和一个mutex。[0093]当debucket所实现的txopservice的方法被调用时，会首先使用mutex加锁，保证在事务处理阶段的atomic-read-and-write语义。demvcc存储了多版本的数据项数据。[0094]在deregion中还有regionpersist，regiondependence，regionmetric三个后台模块分别负责将此region中已提交的数据下沉到ss，依赖关系收集和上报，统计信息收集和上报，具体如下：[0095]regionpersist会定期调用regionservice服务的getminats方法。然后基于最新的min-ats，遍历该region的bucket，寻找可以下沉到ss中的已提交的数据。最终调用storageservice服务中的batchstore方法将数据下沉到ss中，并清除debucket中已被下沉的数据。[0096]如图4所示，regionmetric会统计一段时间内，其所属region的读写统计信息。这些统计信息使用bvar结构(bvar：：latencyrecorder数据类型，记录延时和tps信息)，并在每次涉及到该region数据项的读写流程完成后更新。[0097]最终regionmetric会定期的调用regionservice服务的regionmetric方法上报给tc。这些记录在regionmetric中的统计信息，反映了p(partition)中的的分区负载情况。[0098]此外，如图5所示，demvcc结构体还记录了包括写冲突数量、事务操作数量的统计信息(bvar：：window《adder《int》》数据类型，记录了在一段时间内的累加值)，这些信息反映了的c(data)和l(data)的大小，并可以此计算出数据项的d(data)。当数据项的d(data)大于λ时，会将自己加入到regionmetric中的热点数据项集合中。最终会在regionservice服务的regionmetric方法中被上报给tc。tc会根据每个region的统计信息，调整region中数据的分布(包括分裂或合并region)并最终由partitionmanager来完成分区中数据的调整。[0099]在本实施例中，所述步骤s1中，所述事务控制器tc具体如下：[0100]transactioncontroller(tc)的架构如图6所示。[0101]所述tc包括：dependencemanager、ccplanner、partitionmanager和txidtable。[0102]tc提供txservice、regionservice和partitionservice三种服务，它们由各自的serviceimpl实现。serviceimpl中包括dependencemanager、ccplanner和partitionmanager三个模块，分别负责依赖冲突的发现、并发控制方法的选择，数据分区的管理和变更。[0103]txidtable是生成，存储，回收每一个事务唯一的txid的结构。txid中主要保存了的事务的开始/结束时间戳、依赖和被依赖的其他txid集合、在事务开始阶段注册的提前验证的回调函数。[0104]其中，txid由txidmap负责存储和索引。txidmap是一个经过shard的map《timestamp，txidptr》结构，用来建立并存储从事务开始时间戳到txid结构的映射关系。[0105]regionservice服务的regionmetric方法会被每一个分区定期的调用，上报的统计信息包括：[0106](1)在上一个时间周期内，分区处理的读写请求总数量。[0107](2)在上一个时间周期内，分区中所有d(data)超过阈值λ的数据项。[0108]接着regionserviceimpl会把收到的分区统计信息依次交给ccplanner。ccplanner会根据收到的每个分区的统计信息按如下顺序调整分区：[0109]1、将上一个时间周期内，分区中所有d(data)超过阈值λ的数据项(悲观数据项)记录在partitionconfig中，sc会根据partitionconfig中的悲观数据项来进行加锁；[0110]2、若此时分区中所有悲观数据项的数量超过阈值，则进行分区分裂；[0111]3、若上一个时间周期内，分区处理的读写请求总数量超过阈值λ，则进行分区分裂；[0112]4、若该分区与其左侧分区合并后可以满足前两条不分裂，则进行分区合并。[0113]分区分裂是为了防止一个分区内悲观数据项过多，导致其partitionconfig过大，以及单个分区的负载过高；分区的合并是为了减少不活跃分区，节省系统资源。接着ccplanner会把根据分区统计信息产生的分区变更信息传递给partitionmanager。[0114]接着ccplanner会把根据分区统计信息产生的分区变更信息传递给partitionmanager。[0115]partitionmanager中保存了当前的分区路由表(map《range，partitionconfig，rangecomparator》数据类型)，sc和ti会不断的通过partitionservice服务的getpartition方法来获取最新的分区路由表。当partitionmanager收到来自ccplanner的分区变更信息时，首先会把该变更信息应用到分区路由表上，并使分区路由表的版本号自增。所有ti获取到更新的分区路由表后，ti中的partitionmanager会对regionpartitiontable中的deregion进行调整。只有当所有的ti都完成了分区路由表的更新后，才可以继续下一次的分区变更。[0116]在本实施例中，所述步骤s2具体如下：[0117]首先设置两种数据项的事务特征：[0118]datacontentionc(data)表示并发事务对数据项的竞争程度，由一段时间内该数据项的冲突率来表示：[0119][0120]其中，w表示一段时间内所有对该数据项的写操作的数量，写操作包括预写和锁，w∈w表示w中写冲突的数量；c(data)表示一段时间内该数据项的冲突率，且c(data)越趋近于1，该数据项的冲突率越高，越需要针对该数据项采用悲观加锁的并发控制方法，减少冲突回滚的概率；c(data)越趋近于0，该数据项的冲突率越小，适合采用乐观的并发控制方法，以减少加锁带来的开销。[0121]dataentrytxnlengthl(data)表示涉及到对任意数据项写操作的事务中，写该数据项操作后该事务的大小：[0122][0123][0124]其中，ot表示事务t的操作总数，ot∈ot表示事务t的在写数据项data后到提交前的操作数，l(data，t)表示事务t的在写数据项data后到提交前的操作数与t的操作总数的比值；l(data)表示一段时间内，所有涉及到写数据项data操作的事务的l(data，t)按照事务大小的加权平均；l(data，t)越大，写数据项data在事务t中越靠前，越需要针对该数据项采用悲观加锁的并发控制方法，以防止出现由于写数据项冲突，导致大量后续操作需要回滚的情况；反之适合采用乐观的并发控制方法；[0125]由于可能同时存在多个事务涉及到写数据项data的操作，且每个事务的操作总数不同。在进行对于某一数据项data的并发控制方法选择时，需要同时考虑c(data)和l(data)两个特征，设置datapessimismdegreed(data)：[0126]d(data)＝α*c(data)+(1-α)*l(data)[0127]其中，α表示系统参数，表示c(data)和l(data)两个特征在d(data)中的比重；当d(data)达到预先设定的阈值λ时，将为该数据项使用悲观的并发控制策略，低于阈值λ时，采用乐观的并发控制策略。[0128]在所述事务系统中，全局的数据项按照data-range进行分区，所有分区分散在ti中。设置partitionloadp(partition)衡量一个数据分区的负载大小，和事务竞争程度，其由两部分组成：[0129](1)一段时间内，该分区内读写操作的总数量，反应了该数据分区的负载大小；[0130](2)一段时间内，该分区内所有d(data)大于λ的数据项数量，反映该分区内数据项的事务竞争程度。[0131]每一个事务索引实时收集并计算出分区内的c(data)、l(data)、d(data)、p(partition)信息，分区的大小，范围，以及对应分区的并发控制方法根据分区内的特征信息来实时调整。[0132]如图7所示，在本实施例中，由于实时数据热点导致的数据分区动态调整的过程具体如下：[0133]1.初始时，存在两个分区[-∞，datal)和[data1，+∞)，且都采用occ并发控制方法。[0134]2.在某一时刻，有大量事务访问数据项data2，导致其d(data)超过阈值λ，而成为[data1，+∞)分区中的一个悲观数据项，采用2pl的并发控制方法。分区内的其余数据项则依旧采用occ并发控制方法。[0135]3.一段时间后[datal，+oo)分区内data3、data4、data5、data6各自的d(data)也超过阈值λ，因此这些数据项都成为了悲观数据项需要采用2pl的并发控制方法。由于[datal，+∞)分区内的悲观数据项数量过多，超过阈值μ，所以需要进行分裂，分裂成[datal，data4)和[data4，+∞)两个分区。[0136]4.一段时间后[data2，data4)和[data4，+∞)各自分区中已不存在d(data)大于λ的数据项，所以这两个分区内数据项将全部使用occ的并发控制方法。[0137]最终由于[data2，data4)和[data4，+∞)两个分区相邻，且分区中所有悲观数据项的数量小于阈值μ，因此两个分区进行了合并以减少分区的数量。[0138]在本实施例中，所述步骤s3具体如下：[0139]如图1所示，基于步骤s2，每个事务索引ti收集并计算出所有属于它的分区的各自的c(data)、l(data)、d(data)、p(partition)信息，并定时上报给并发策略选择器ccplanner；ccplanner根据实时的特征和统计信息，动态调整事务的分区，并为每个分区选择合适的并发控制方法，从而生成一个并发控制计划ccplan。ccplan如图8所示。[0140]综上，本发明的方法以基于数据项事务特征的自适应并发控制机制，动态地根据事务规模，冲突率等特征动态选择合适的并发控制方法，均衡了节点之间的负载，有效应对了实时多变的事务类型和不同的工作负载。[0141]本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。当前第1页12当前第1页12
技术特征：
1.一种事务并发控制方法，具体步骤如下：s1、构建一套事务系统；s2、事务系统中每个事务索引实时收集分区的数据项的事务特征信息并动态调整事务的分区；s3、基于步骤s2，为每个分区选择合适的并发控制方法，生成一个并发控制计划，交给分区管理器；s4、分区管理器根据并发控制计划调整事务索引中的数据分区，并向客户端分发并发控制计划，根据并发控制计划中的分区范围，和每个分区的并发控制方法来进行读写操作，完成自适应的事务并发控制方法。2.根据权利要求1所述的一种事务并发控制方法，其特征在于，所述步骤s1中，所述事务系统包括客户端sc、事务系统ts和存储系统ss，ts包括一个事务控制器tc和多个事务索引ti。3.根据权利要求1所述的一种事务并发控制方法，其特征在于，所述步骤s1中，所述事务索引ti具体如下：所述ti包括：txindex，deregion，debucket；每一个ti向外提供txopservice服务，并由txopserviceimpl具体实现；txopserviceimpl中的txindex数据结构实现了txopservice服务的方法；txindex包括regionpartitiontable和partitionmanager两部分；其中，regionpartitiontable是一个map<range，deregionptr，rangecomparator>类型，即是一个从data-range到region的映射组成的数据分区集合；当txindex所实现的方法被调用，首先根据所调用的data-range，从regionpartitiontable中找出其对应的deregion，然后继续调用deregion所实现的txopservice的方法；partitionmanager是一个独立于regionpartitiontable的后台模块，通过不断调用partitionservice服务来获取到最新的属于该txindex数据分区信息，并对regionpartitiontable中已有的分区进行调整；deregion表示一个data-range中所有数据项所组成的数据集合；deregion包含固定数量的debucket，debucket负责存储数据项数据，data-range中的每一个数据项会被固定的哈希到一个debucket中；当deregion所实现的txopservice的方法被调用时，首先会根据所调用的数据项找到其所属的debucket，然后继续调用debucket所实现的txopservice的方法；debucket包括demvcc和一个mutex；当debucket所实现的txopservice的方法被调用时，会首先使用mutex加锁，保证在事务处理阶段的atomic-read-and-write语义；demvcc存储了多版本的数据项数据；在deregion中还有regionpersist，regiondependence，regionmetric三个后台模块分别负责将此region中已提交的数据下沉到ss，依赖关系收集和上报，统计信息收集和上报，具体如下：regionpersist会定期调用regionservice服务的getminats方法；然后基于最新的min-ats，遍历该region的bucket，寻找可以下沉到ss中的已提交的数据；最终调用storageservice服务中的batchstore方法将数据下沉到ss中，并清除debucket中已被下沉
的数据；regionmetric会统计一段时间内，其所属region的读写统计信息；这些统计信息使用bvar结构，即bvar::latencyrecorder数据类型，记录延时和tps信息，并在每次涉及到该region数据项的读写流程完成后更新；最终regionmetric会定期的调用regionservice服务的regionmetric方法上报给tc；这些记录在regionmetric中的统计信息，反映了p(partition)中的的分区负载情况；demvcc结构体记录包括写冲突数量、事务操作数量的统计信息，即bvar::window<adder<int>>数据类型，记录在一段时间内的累加值，这些信息反映c(data)和l(data)的大小，并可以此计算出数据项的d(data)；当数据项的d(data)大于λ时，将自己加入到regionmetric中的热点数据项集合中；最终会在regionservice服务的regionmetric方法中被上报给tc；tc根据每个region的统计信息，调整region中数据的分布，包括分裂或合并region，并最终由partitionmanager来完成分区中数据的调整。4.根据权利要求1所述的一种事务并发控制方法，其特征在于，所述步骤s1中，所述事务控制器tc具体如下：所述tc包括：dependencemanager、ccplanner、partitionmanager和txidtable；tc提供txservice、regionservice和partitionservice三种服务，由各自的serviceimpl实现；serviceimpl中包括dependencemanager、ccplanner和partitionmanager三个模块，分别负责依赖冲突的发现、并发控制方法的选择，数据分区的管理和变更；txidtable是生成，存储，回收每一个事务唯一的txid的结构；txid中主要保存了的事务的开始/结束时间戳、依赖和被依赖的其他txid集合、在事务开始阶段注册的提前验证的回调函数；其中，txid由txidmap负责存储和索引；txidmap是一个经过shard的map<timestamp，txidptr>结构，用来建立并存储从事务开始时间戳到txid结构的映射关系；regionservice服务的regionmetric方法会被每一个分区定期的调用，上报的统计信息包括：(1)在上一个时间周期内，分区处理的读写请求总数量；(2)在上一个时间周期内，分区中所有d(data)超过阈值λ的数据项；接着regionserviceimpl把收到的分区统计信息依次交给ccplanner；ccplanner根据收到的每个分区的统计信息按如下顺序调整分区：1、将上一个时间周期内，分区中所有d(key)超过阈值λ的数据项，即悲观数据项，记录在partitionconfig中，sc会根据partitionconfig中的悲观数据项来进行加锁；2、若此时分区中所有悲观数据项的数量超过阈值，则进行分区分裂；3、若上一个时间周期内，分区处理的读写请求总数量超过阈值λ，则进行分区分裂；4、若该分区与其左侧分区合并后可以满足前两条不分裂，则进行分区合并；接着ccplanner把根据分区统计信息产生的分区变更信息传递给partitionmanager；partitionmanager中保存了当前的分区路由表(map<range，partitionconfig,rangecomparator>数据类型)，sc和ti不断的通过partitionservice服务的getpartition方法获取最新的分区路由表；当partitionmanager收到来自ccplanner的分区变更信息时，
首先会把该变更信息应用到分区路由表上，并使分区路由表的版本号自增；所有ti获取到更新的分区路由表后，ti中的partitionmanager对regionpartitiontable中的deregion进行调整；当所有的ti都完成了分区路由表的更新后，继续下一次的分区变更。5.根据权利要求1所述的一种事务并发控制方法，其特征在于，所述步骤s2具体如下：首先设置两种数据项的事务特征：data entry contentionc(data)表示并发事务对数据项的竞争程度，由一段时间内该数据项的冲突率来表示：其中，w表示一段时间内所有对该数据项的写操作的数量，写操作包括预写和锁，w∈w表示w中写冲突的数量；c(data)表示一段时间内该数据项的冲突率，且c(data)越趋近于1，该数据项的冲突率越高，越需要针对该数据项采用悲观加锁的并发控制方法，减少冲突回滚的概率；c(data)越趋近于0，该数据项的冲突率越小，适合采用乐观的并发控制方法，以减少加锁带来的开销；data entry txn lengthl(data)表示涉及到对任意数据项写操作的事务中，写该数据项操作后该事务的大小：项操作后该事务的大小：其中，o
t
表示事务t的操作总数，o
t
∈o
t
表示事务t的在写数据项data后到提交前的操作数，l(data，t)表示事务t的在写数据项data后到提交前的操作数与t的操作总数的比值；l(data)表示一段时间内，所有涉及到写数据项data操作的事务的l(data，t)按照事务大小的加权平均；l(data，t)越大，写数据项data在事务t中越靠前，越需要针对该数据项采用悲观加锁的并发控制方法，以防止出现由于写数据项冲突，导致大量后续操作需要回滚的情况；反之适合采用乐观的并发控制方法；在进行对于某一数据项data的并发控制方法选择时，同时考虑c(data)和l(data)两个特征，设置data pessimism degree d(data)：d(data)＝α*c(data)+(1-α)*l(data)其中，α表示系统参数，表示c(data)和l(data)两个特征在d(data)中的比重；当d(data)达到预先设定的阈值λ时，将为该数据项使用悲观的并发控制策略，低于阈值λ时，采用乐观的并发控制策略；在所述事务系统中，全局的数据项按照data-range进行分区，所有分区分散在ti中；设置partition load p(partition)衡量一个数据分区的负载大小，和事务竞争程度，其由两部分组成：(1)一段时间内，该分区内读写操作的总数量，反应该数据分区的负载大小；(2)一段时间内，该分区内所有d(data)大于λ的数据项数量，反映该分区内数据项的事务竞争程度；每一个事务索引实时收集并计算出分区内的c(data)、l(data)、d(data)、p
(partition)信息，分区的大小，范围，以及对应分区的并发控制方法根据分区内的特征信息来实时调整。6.根据权利要求1所述的一种事务并发控制方法，其特征在于，所述步骤s3具体如下：基于步骤s2，每个事务索引ti收集并计算出所有属于它的分区的各自的c(data)、l(data)、d(data)、p(partition)信息，并定时上报给并发策略选择器ccplanner；ccplanner根据实时的特征和统计信息，动态调整事务的分区，并为每个分区选择合适的并发控制方法，从而生成一个并发控制计划ccplan。

技术总结
本发明公开了一种事务并发控制方法，首先构建一套事务系统，事务系统中每个事务索引实时收集分区的数据项的事务特征信息并动态调整事务的分区，为每个分区选择合适的并发控制方法，生成一个并发控制计划，交给分区管理器，分区管理器根据并发控制计划调整事务索引中的数据分区，并向客户端分发并发控制计划，根据并发控制计划中的分区范围，和每个分区的并发控制方法来进行读写操作，完成自适应的事务并发控制方法。本发明的方法以基于数据项事务特征的自适应并发控制机制，动态地根据事务规模，冲突率等特征动态选择合适的并发控制方法，均衡了节点之间的负载，有效应对了实时多变的事务类型和不同的工作负载。变的事务类型和不同的工作负载。变的事务类型和不同的工作负载。


技术研发人员：马迎春 薛瑞尼 王诏贤
受保护的技术使用者：电子科技大学
技术研发日：2023.06.30
技术公布日：2023/10/7