[go: up one dir, main page]

CN116932603A - 一种基于有向图的高性能事务并发复制方法 - Google Patents

一种基于有向图的高性能事务并发复制方法 Download PDF

Info

Publication number
CN116932603A
CN116932603A CN202310970070.9A CN202310970070A CN116932603A CN 116932603 A CN116932603 A CN 116932603A CN 202310970070 A CN202310970070 A CN 202310970070A CN 116932603 A CN116932603 A CN 116932603A
Authority
CN
China
Prior art keywords
transaction
playback
strong communication
communication components
directed graph
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202310970070.9A
Other languages
English (en)
Other versions
CN116932603B (zh
Inventor
陈磊
邱卓栋
吴婵
冯友旭
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shanghai Yunxi Technology Co ltd
Original Assignee
Shanghai Yunxi Technology Co ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Shanghai Yunxi Technology Co ltd filed Critical Shanghai Yunxi Technology Co ltd
Priority to CN202310970070.9A priority Critical patent/CN116932603B/zh
Publication of CN116932603A publication Critical patent/CN116932603A/zh
Application granted granted Critical
Publication of CN116932603B publication Critical patent/CN116932603B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2457—Query processing with adaptation to user needs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/248—Presentation of query results
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/284—Relational databases
    • G06F16/285—Clustering or classification
    • G06F16/287—Visualization; Browsing

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明提供一种基于有向图的高性能事务并发复制方法，属于数据处理技术领域，本发明根据事务数据事件kvEvent构建事务之间的依赖关系，根据事务提交事件commitEvent消除事务的循环依赖关系，并且对于有向图的数个强联通分量实现并发回放。通过条件变量以及阻塞队列，轮询多个回放协程，实现多个可回放强联通分量之间的并发回放效果。

Description

一种基于有向图的高性能事务并发复制方法
技术领域
本发明涉及数据处理技术领域，尤其涉及一种基于有向图的高性能事务并发复制方法。使数据库主备节点之间的数据复制一致性。
背景技术
当主节点执行事务时，主节点向从节点发送事务数据事件kvEvent以及事务提交事件commitEvent，从节点收到事务数据事件后kvEvent，根据之间的先后顺序构建冲突关系，并且生成依赖关系，此时依赖关系可能会存在环形依赖。
发明内容
为了解决以上技术问题，本发明提供了一种基于有向图的高性能事务并发复制方法。对于环形依赖，从节点需要接收提交时间戳拆除重复的依赖关系，并且根据提交时间戳排序后，进行事务回放。对于有向图的多个强联通分量，可以进行并发回放处理。
本发明的技术方案是：
一种基于有向图的高性能事务并发复制方法，根据事务数据事件kvEvent构建事务之间的依赖关系，根据事务提交事件commitEvent消除事务的循环依赖关系，并且对于有向图的数个强联通分量实现并发回放。
进一步的，
通过有向图模拟事务之间的依赖关系；
通过强联通分量定义事务顶端；
通过并查集实现互相依赖的事务关系之间的合并；
通过拆分顶端事务与非顶端事务，引入并发实现事务之间互不阻塞；
通过拆分事务数据事件与事务提交事件，引入并发实现事件之间互不阻塞；
通过引入阻塞队列条件变量以及多个回放协程，实现并发的对数个可回放的强联通分量进行并发回放。
再进一步的，
从节点收到主节点发送的事务数据事件后，从节点构建Range级别的冲突关系，并且根据Range级别的冲突关系，生成全局的事务依赖有向图。
当事务出现强联通分量后，即事务之间的依赖关系成环，如果环出现在事务依赖关系的顶端，则事务回放会被卡住，对事务依赖关系进行拆分；当前事务依赖关系的顶端是一个环，则当前事务回放需优先处理顶端的强联通分量。
对从节点消费主节点的事务数据进行并发拆分，根据事件对应的事务是否从属于顶端联通分量，进行拆分。
通过并查集，可发现数个节点是否处于同一个强联通分量，并且如果存在新的节点同时联通两个强联通分量，此时对两个强联通分量进行合并。
当一个环接收到全部的事务数据事件kvEvent以及全部的事务提交事件commitEvent后，可对强联通分量内的事务节点进行排序，此时问题退化为一组数据排序；通过对数据节点按照提交时间戳排序，即可得到最终的事务回放顺序，则事务最终按照事务的提交顺序进行回放。
当出现数个强联通分量同时可回放时，需要构建一个阻塞队列，并通过该阻塞队列不断唤醒回放协程进行工作，对强联通分量内的事务节点进行按顺序回放；每个强联通分量分配一个回放协程，回放协程数量按照CPU核数进行分配，并且可调整数量。阻塞队列通过条件变量不断轮询数个回放协程提醒可以进行回放。
本发明的有益效果是
本发明提出在面向主从的事务一致性复制场景下，通过有向图寻找顶端的强联通分量、并查集实现有向图合并以及按照事务提交时间戳排序，实现有向图的并发处理。通过拆分顶端事务与非顶端事务，事务数据事件与事务提交事件，引入四组并发，以实现互相之间不会阻塞。通过条件变量以及阻塞队列，轮询多个回放协程，实现多个可回放强联通分量之间的并发回放效果。
附图说明
图1是Range1和Range2的事务依赖关系示意图；
图2是事务出现死锁示意图；
图3是当事务出现强联通分量后成环的示意图；
图4是事务数据进行并发拆分示意图；
图5是两个强联通分量进行合并示意图；
图6是得到最终的事务回放顺序示意图；
图7是多个强联通分量同时回放示意图。
具体实施方式
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。
本发明提供了一种基于有向图的高性能事务并发复制方法，引入有向图的概念定义事务之间的依赖关系，并且通过寻找有向图的强联通分量、使用并查集算法合并有向图以及对事务依赖关系排序确定事务之间的回放顺序。
具体实现如下：
1.从节点收到主节点发送的事务数据事件后，从节点需要构建Range级别的冲突关系，并且根据Range级别的冲突关系，生成全局的事务依赖有向图。如图1、2所示。
2.当事务出现强联通分量后，即事务之间的依赖关系成环，如果环出现在事务依赖关系的顶端，则事务回放会被卡住，因此需要对事务依赖关系进行拆分。如图3所示，当前事务依赖关系的顶端是一个环，则当前事务回放需要优先处理顶端的强联通分量。
3.基于此，对从节点消费主节点的事务数据进行并发拆分，分类如下，根据事件对应的事务是否从属于顶端联通分量，进行拆分，可以拆分为
a.Top non-top top non-top
b.KV Commit
c.顶端环事务数据事件
i.并发1
d.顶端环事务提交事件
i.并发2
e.非顶端环事务数据事件
i.并发3
f.非顶端环事务提交事件
i.并发4
g.通过拆分[事务数据事件,事务提交事件][顶端环事务,非顶端事务]这两种类别，可以实现最大程度的事务消费并发性能。
4.通过并查集，可以发现多个节点是否处于同一个强联通分量，并且如果存在新的节点同时联通两个强联通分量，此时可以对两个强联通分量进行合并。步骤如图5所示。
5.当一个环接收到全部的事务数据事件kvEvent以及全部的事务提交事件commitEvent后，可以对强联通分量内的事务节点进行排序，此时问题退化为一组数据排序。通过对数据节点按照提交时间戳排序，即可得到最终的事务回放顺序，则事务最终按照事务的提交顺序进行回放。如图6所示。
6.当出现多个强联通分量同时可回放时，需要构建一个阻塞队列BlockingQueue，并通过该阻塞队列不断唤醒回放协程进行工作，对强联通分量内的事务节点进行按顺序回放。每个强联通分量分配一个回放协程，回放协程数量按照CPU核数进行分配，并且可以调整数量。阻塞队列通过条件变量不断轮询多个回放协程提醒可以进行回放。如图7所示。
7.时间复杂度评估
a.假设图为G＝(V,E)
b.时间复杂度为O(V+E+V+VlogV)
i.处理所有的点集与边集O(V+E)
ii.并查集按秩合并/路径压缩O(V)
iii.数组排序O(VlogV)
iv.整体复杂度为O(E+VlogV)
以上所述仅为本发明的较佳实施例，仅用于说明本发明的技术方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所做的任何修改、等同替换、改进等，均包含在本发明的保护范围内。

Claims (9)

1.一种基于有向图的高性能事务并发复制方法，其特征在于，
根据事务数据事件kvEvent构建事务之间的依赖关系，根据事务提交事件commitEvent消除事务的循环依赖关系，并且对于有向图的数个强联通分量实现并发回放。
2.根据权利要求1所述的方法，其特征在于，
通过有向图模拟事务之间的依赖关系；
通过强联通分量定义事务顶端；
通过并查集实现互相依赖的事务关系之间的合并；
通过拆分顶端事务与非顶端事务，引入并发实现事务之间互不阻塞；
通过拆分事务数据事件与事务提交事件，引入并发实现事件之间互不阻塞；
通过引入阻塞队列条件变量以及数个回放协程，实现并发的对数个可回放的强联通分量进行并发回放。
3.根据权利要求2所述的方法，其特征在于，
从节点收到主节点发送的事务数据事件后，从节点构建Range级别的冲突关系，并且根据Range级别的冲突关系，生成全局的事务依赖有向图。
4.根据权利要求3所述的方法，其特征在于，
当事务出现强联通分量后，即事务之间的依赖关系成环，如果环出现在事务依赖关系的顶端，则事务回放会被卡住，对事务依赖关系进行拆分；当前事务依赖关系的顶端是一个环，则当前事务回放需优先处理顶端的强联通分量。
5.根据权利要求4所述的方法，其特征在于，
对从节点消费主节点的事务数据进行并发拆分，根据事件对应的事务是否从属于顶端联通分量，进行拆分。
6.根据权利要求5所述的方法，其特征在于，
通过并查集，可发现数个节点是否处于同一个强联通分量，并且如果存在新的节点同时联通两个强联通分量，此时对两个强联通分量进行合并。
7.根据权利要求6所述的方法，其特征在于，
当一个环接收到全部的事务数据事件以及全部的事务提交事件后，可对强联通分量内的事务节点进行排序，此时问题退化为一组数据排序；通过对数据节点按照提交时间戳排序，即可得到最终的事务回放顺序，则事务最终按照事务的提交顺序进行回放。
8.根据权利要求7所述的方法，其特征在于，
当出现数个强联通分量同时可回放时，需要构建一个阻塞队列，并通过该阻塞队列不断唤醒回放协程进行工作，对强联通分量内的事务节点进行按顺序回放；每个强联通分量分配一个回放协程，回放协程数量按照CPU核数进行分配，并且可调整数量。
9.根据权利要求8所述的方法，其特征在于，
阻塞队列通过条件变量不断轮询数个回放协程提醒可以进行回放。
CN202310970070.9A 2023-08-03 2023-08-03 一种基于有向图的高性能事务并发复制方法 Active CN116932603B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202310970070.9A CN116932603B (zh) 2023-08-03 2023-08-03 一种基于有向图的高性能事务并发复制方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202310970070.9A CN116932603B (zh) 2023-08-03 2023-08-03 一种基于有向图的高性能事务并发复制方法

Publications (2)

Publication Number Publication Date
CN116932603A true CN116932603A (zh) 2023-10-24
CN116932603B CN116932603B (zh) 2024-10-08

Family

ID=88387748

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202310970070.9A Active CN116932603B (zh) 2023-08-03 2023-08-03 一种基于有向图的高性能事务并发复制方法

Country Status (1)

Country Link
CN (1) CN116932603B (zh)

Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001009751A2 (en) * 1999-07-30 2001-02-08 Accenture Llp A system, method and article of manufacture for maintaining data in an e-commerce based technical architecture
US20050021567A1 (en) * 2003-06-30 2005-01-27 Holenstein Paul J. Method for ensuring referential integrity in multi-threaded replication engines
CN102722401A (zh) * 2012-04-25 2012-10-10 华中科技大学 一种硬件事务内存系统中的伪相联多版本数据管理方法
CN102937933A (zh) * 2012-11-14 2013-02-20 中国矿业大学 基于测试级的类测试顺序确定方法
CN108038304A (zh) * 2017-12-08 2018-05-15 西安交通大学 一种利用时间局部性的格子玻尔兹曼方法并行加速方法
CN110442459A (zh) * 2019-07-04 2019-11-12 北京百度网讯科技有限公司 分布式死锁检测方法及装置、计算机设备及可读介质
CN112463311A (zh) * 2021-01-28 2021-03-09 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质
CN113835847A (zh) * 2021-08-10 2021-12-24 复旦大学 基于快照的分布式账本平台事务处理优化方法
CN114253920A (zh) * 2021-12-07 2022-03-29 中信银行股份有限公司 一种交易重新排序方法、装置、设备及可读存储介质
CN116302328A (zh) * 2023-02-17 2023-06-23 上海加密原生科技有限公司 智能合约数据处理方法和系统
CN116467386A (zh) * 2023-04-13 2023-07-21 上海沄熹科技有限公司 一种备库数据并发回放方法及装置

Patent Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001009751A2 (en) * 1999-07-30 2001-02-08 Accenture Llp A system, method and article of manufacture for maintaining data in an e-commerce based technical architecture
US20050021567A1 (en) * 2003-06-30 2005-01-27 Holenstein Paul J. Method for ensuring referential integrity in multi-threaded replication engines
CN102722401A (zh) * 2012-04-25 2012-10-10 华中科技大学 一种硬件事务内存系统中的伪相联多版本数据管理方法
CN102937933A (zh) * 2012-11-14 2013-02-20 中国矿业大学 基于测试级的类测试顺序确定方法
CN108038304A (zh) * 2017-12-08 2018-05-15 西安交通大学 一种利用时间局部性的格子玻尔兹曼方法并行加速方法
CN110442459A (zh) * 2019-07-04 2019-11-12 北京百度网讯科技有限公司 分布式死锁检测方法及装置、计算机设备及可读介质
CN112463311A (zh) * 2021-01-28 2021-03-09 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质
CN113835847A (zh) * 2021-08-10 2021-12-24 复旦大学 基于快照的分布式账本平台事务处理优化方法
CN114253920A (zh) * 2021-12-07 2022-03-29 中信银行股份有限公司 一种交易重新排序方法、装置、设备及可读存储介质
CN116302328A (zh) * 2023-02-17 2023-06-23 上海加密原生科技有限公司 智能合约数据处理方法和系统
CN116467386A (zh) * 2023-04-13 2023-07-21 上海沄熹科技有限公司 一种备库数据并发回放方法及装置

Also Published As

Publication number Publication date
CN116932603B (zh) 2024-10-08

Similar Documents

Publication Publication Date Title
Chandrasekaran et al. Streaming Queries over Streaming Data.
Pan et al. Parallel correlation clustering on big graphs
US7308436B2 (en) Distributed data mining and compression method and system
Unterbrunner et al. Predictable performance for unpredictable workloads
US8032885B2 (en) Method and medium for combining operation commands into database submission groups
EP4030287A1 (en) Transaction processing method and apparatus, computer device, and storage medium
JP2023546249A (ja) トランザクション処理方法、装置、コンピュータ機器及びコンピュータプログラム
EP2932370B1 (en) System and method for performing a transaction in a massively parallel processing database
US20040221116A1 (en) Method and mechanism for efficient implementation of ordered records
CN111444027B (zh) 事务处理方法、装置、计算机设备及存储介质
WO2015142548A1 (en) Dependency-aware transaction batching for data replication
CN114969200B (zh) 数据同步方法、装置、电子设备及存储介质
CN108241627A (zh) 一种异构数据存储查询方法和系统
CN106095951A (zh) 基于负载均衡和查询日志的数据空间多维索引方法
CN101441579B (zh) 一种基于集群计算系统的三维模型库特征提取方法
CN116932603B (zh) 一种基于有向图的高性能事务并发复制方法
CN116186082A (zh) 基于分布式的数据汇总方法、第一服务器和电子设备
Hooda et al. Distributed synthetic minority oversampling technique
CN111314440B (zh) 图结构数据上的环检测方法及系统
CN115658737B (zh) 大规模轨迹数据时空伴随者查询方法和系统
CN108536758A (zh) 一种数据库模式的数据表重构方法、装置及系统
Jiang et al. Tunable causal consistency: Specification and implementation
CN118250281B (zh) 一种任务数据处理的方法及系统
Shang et al. Mining negative association rules in multi-database
Burys et al. Large-scale clustering using MPI-based canopy

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant