分布“系统中Semi-Join算法的实现

钱招明,王雷,余晟隽,宫学庆

(华东师范大学数据科学与工程研究院,上海200062)

分布“系统中Semi-Join算法的实现

钱招明,王雷,余晟隽,宫学庆

(华东师范大学数据科学与工程研究院,上海200062)

随着新型分布式系统的使用范围越来越广,应用不再满足于仅使用主键访问方式来读取数据,如何在这些系统中高效实现Join等复杂操作成为研究的热点.本文介绍了如何基于Semi-Join算法在分布式系统中实现Join操作,提出了两种获取右表数据的方法,并通过实验分析了该算法的性能.

分布式数据库;Join操作;Semi-Join算法

0 引言

随着云计算技术的快速发展,各种新型的分布式系统不断涌现,越来越多的应用开始采用分布式架构存储和管理数据.早期的NoSQL系统多数采用简单的Key-Value模型存储数据,提供按键值(Get操作)或按键值范围(Scan操作)访问数据的方法.随着分布式系统越来越广泛的被应用,应用系统对数据访问方法提出了更高的要求,如何在分布式系统中高效实现连接(Join)、聚合(Aggregation)等操作成为近期研究的热点问题之一.

Join是传统数据库系统中的基本操作之一,在集中式环境下已经有很多成熟的算法用于实现Join操作,例如,Nest Loop Join、Merge Join、Hash Join等.在分布式环境下,我们仍然可以使用这些算法来实现Join操作,但受网络传输延迟的影响,算法的执行效率可能会非常差.Semi-Join是20世纪80年代提出的用于优化分布式数据库中Join操作的算法[1],本文将该算法应用于新型的分布式系统,用于优化Join操作的实现.在Semi-Join算法的实现流程中,本……