华东师范大学学报（自然科学版）

Select

高可用数据库系统中的分布式一致性协议

储佳佳, 郭进伟, 刘柏众, 张晨东, 钱卫宁

2016 (5): 1-9. doi: 10.3969/j.issn.1000-5641.2016.05.001

摘要 ( 620 )

HTML ( 18 )

PDF(476KB) ( 798 )

可用性和一致性是分布式数据库系统中的两个重要特性和基础, 需要借助分布式一致性协议来保证. 保证一致性需要使用一致性协议为并发的事务更新操作确定一个全局的执行顺序, 并协调局部状态和全局状态不断地达到动态一致. 可用性的实现, 需要一致性协议协调多副本之间的一致来实现主备节点的无缝切换. 可见, 分布式一致性协议是高可用数据库系统的实现基础. 本文梳理、综述了经典的分布式一致性协议以及一致性协议在高可用数据库系统中的主要应用, 并对分布式一致性协议的实现代价和局限性进行了分析与评估.

参考文献 | 相关文章 | 计量指标

Select

面向高通量事务处理的事务编译技术

王冬慧, 朱涛, 钱卫宁

2016 (5): 10-17. doi: 10.3969/j.issn.1000-5641.2016.05.002

摘要 ( 549 )

HTML ( 77 )

PDF(391KB) ( 792 )

针对内存数据库中CPU利用率不高的问题, 目前的研究工作集中在利用事务编译技术提升事务的执行效率和改进事务的并发控制以提升数据库的性能. 本文主要从以下几个方面对内存数据库的事务编译技术进行了综述. 第一, 介绍了事务处理的一般流程, 分析限制系统性能的因素. 第二, 分析了当前使用的事务编译技术, 包括即时编译技术、操作依赖分析技术和事务切片技术. 第三, 结合实例分析事务编译是如何提升数据库性能的, 介绍典型的内存数据库在事务编译方面的研究工作, 如Hekaton、VoltDB等. 最后给出了研究展望.

参考文献 | 相关文章 | 计量指标

Select

内存数据库事务提交的关键技术与挑战

胡爽, 周欢, 钱卫宁

2016 (5): 18-26. doi: 10.3969/j.issn.1000-5641.2016.05.003

摘要 ( 422 )

HTML ( 9 )

PDF(434KB) ( 743 )

ARIES作为传统事务提交机制从20世纪90年代问世以来, 一直是主流商业或开源数据库系统普遍采用的方法. 随着应用的高通量化, 基于传统硬件设备实现的事务提交机制成为了系统性能提升的首要瓶颈. 然而大内存、多核等高性能硬件技术的发展又为事务提交机制的优化提供了新的契机. 本文详细分析并总结了传统事务提交机制中存在的问题, 然后归纳并讨论了现有基于新型硬件的事务提交技术的应用现状与优缺点, 最后探讨了事务提交优化的未来发展与挑战.

参考文献 | 相关文章 | 计量指标

Select

分布式内存数据库系统的容错管理

赵镇辉, 黄承晟, 周敏奇, 周傲英

2016 (5): 27-35. doi: 10.3969/j.issn.1000-5641.2016.05.004

摘要 ( 596 )

HTML ( 10 )

PDF(767KB) ( 661 )

在大数据背景下, 分布式系统被企业广泛部署和应用, 随着分布式系统节点规模的扩大, 系统故障的概率也将随之增加, 在分布式系统中引入容错机制, 对提升分布式系统可用性、可靠性、可恢复性至关重要. CLAIMS系统是面向金融领域的对实时数据进行实时分析的内存数据库系统------在数据不断注入系统时, 提供近实时的查询、分析任务. 本文主要探讨CLAIMS系统中容错机制. 依据租约机制, 实现系统中异常节点的快速发现及标记(即Fail-fast). 在标记异常节点之后, 实现对受影响分析任务的重启(即Fail-over); 对异常节点全局内存状态的恢复(即Fail-back). 实验结果表明, 本文所提算法能够较好地实现CLAIMS系统的容错特性.

参考文献 | 相关文章 | 计量指标

Select

基于LSM Tree的分布式索引实现

隆飞, 翁海星, 高明, 张召

2016 (5): 36-44. doi: 10.3969/j.issn.1000-5641.2016.05.005

摘要 ( 933 )

HTML ( 26 )

PDF(746KB) ( 1330 )

近年来 Log-Structured-Merge(LSM) Tree 在 NoSQL 系统中得到了广泛地应用. 主要是因为 LSM Tree 架构提出了延迟更新和批量写入的算法, 将随机写转换为批量写, 减少了磁盘臂的移动开销, 从而大大地提升了数据库的写入性能. 然而, 读性能却也因此受到影响. LSM Tree 和 B Tree 之间的本质区别使得 NoSQL 系统不适宜直接引用 B Tree 作为辅助索引结构. 本文实现了 LSM Tree 下的一种分布式辅助索引结构, 提出针对这种读写分离架构的索引批量加载策略, 并对 LSM Tree 的查询计划树进行了缓冲优化, 避免了重复的查询解析, 使得索引读的性能得到了相应的提升.

参考文献 | 相关文章 | 计量指标

Select

基于数据关联的分布式对象代理数据库划分方法

王敏, 彭承晨, 李蓉蓉, 彭煜玮

2016 (5): 45-55. doi: 10.3969/j.issn.1000-5641.2016.05.006

摘要 ( 508 )

HTML ( 11 )

PDF(1068KB) ( 654 )

对象代理数据库是一种先进的具有复杂信息管理能力的数据库系统, 随着数据量的剧增, 实现其分布式存储变得十分重要. 然而, 对象代理数据库中的数据存在着很强的关联性, 如果按照传统数据划分方式进行分布式存储, 将导致查询效率低下. 针对这一问题, 本文提出了一种基于关联的高效数据划分方法: 首先根据代理层次将关联对象聚集成对象簇, 每个簇对应一个存储文件; 然后提取对象簇的模式特征和语义特征, 通过聚类算法将对象簇集划分为 k 个子集分配到各存储节点. 将本文方法与随机分布式存储方法进行了比较实验, 结果证明本文方法在查询效率方面具有明显优势.

参考文献 | 相关文章 | 计量指标

Select

面向分布式数据库的相关子查询优化策略

毛思语, 张利军, 张小芳, 高锦涛, 李战怀

2016 (5): 56-66. doi: 10.3969/j.issn.1000-5641.2016.05.007

摘要 ( 629 )

HTML ( 11 )

PDF(698KB) ( 717 )

子查询是指查询语句作为另一个语句的查询条件出现, 相关子查询是指子查询的查询条件依赖于父查询. 相关子查询要对子查询反复求值, 需要多次访问磁盘, 尤其是在分布式的环境中还会产生大量的通信开销, 导致执行效率低下. 在对现有相关子查询优化策略分析研究的基础上, 综合分布式的特点, 将子查询展开、无用子树切除、聚集函数消除等策略应用于分布式关系数据库系统中, 并在开源分布式关系数据库 OceanBase 中应用这些策略实现对谓词EXISTS的相关子查询的优化. 实验表明这些策略能够明显改善相关子查询的查询性能.

参考文献 | 相关文章 | 计量指标

Select

OceanBase 中基于布隆过滤器的连接算法

茅潇潇, 段惠超, 高明

2016 (5): 67-74. doi: 10.3969/j.issn.1000-5641.2016.05.008

摘要 ( 714 )

HTML ( 14 )

PDF(459KB) ( 866 )

在大数据时代, ``去IOE'' 运动的推进以及``双 11''等活动的兴起对分布式数据库系统提出了更高的要求. OceanBase 是阿里巴巴集团自主研发的开源分布式数据库, 支持海量数据跨行跨表事务, 但是对复杂查询的处理性能仍有待提高, 其中连接操作带来的网络传输严重影响了数据库的性能. 本文提出了一种基于布隆过滤器的连接算法, 通过构建布隆过滤器对右表数据进行过滤, 减少了不必要的数据传输开销, 降低了数据处理带来的内存资源的消耗. 本文在 OceanBase 上实现了该算法, 并通过实验证明, 该算法极大提高了连接操作的效率.

参考文献 | 相关文章 | 计量指标

Select

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

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

2016 (5): 75-80. doi: 10.3969/j.issn.1000-5641.2016.05.009

摘要 ( 659 )

HTML ( 17 )

PDF(945KB) ( 1155 )

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

参考文献 | 相关文章 | 计量指标

Select

分布式可扩展数据流连接算法

王晓桐, 房俊华, 张蓉

2016 (5): 81-88. doi: 10.3969/j.issn.1000-5641.2016.05.010

摘要 ( 507 )

HTML ( 12 )

PDF(964KB) ( 755 )

Join-Matrix 是一种高性能的连接矩阵模型, 方便部署于分布式环境下, 支持任意连接谓词的数据流连接操作. 由于采取随机分发元组作为路由策略, Join-Matrix 可利用对元组内容的不敏感性来有效抵御数据倾斜. 为了实现工作节点的负载均衡以及网络传输代价的最小化, 基于连接矩阵模型设计一种高效的数据划分方案尤为重要. 针对数据流连接处理, 本文设计并实现了一种新颖的连接算子, 可灵活地进行划分方案的自适应调整, 以应对实时动态变化的数据分布. 具体来说, 我们根据数据流流量的采样信息和系统额定负载, 通过一个轻量级的决策器制定出一个数据划分方案和相应的数据迁移计划, 在保证输出结果完整性与正确性的情况下, 实现迁移代价的最小化. 本文在多种不同的数据集上进行了大量对比实验, 结果证明, 在资源利用率、系统吞吐率与时间延迟等方面, 该连接算子较对比系统具有更高的性能体现.

参考文献 | 相关文章 | 计量指标

Select

不对称内存计算平台OLAP查询处理技术研究

张延松, 张宇, 周烜, 王珊

2016 (5): 89-102. doi: 10.3969/j.issn.1000-5641.2016.05.011

摘要 ( 505 )

HTML ( 9 )

PDF(2725KB) ( 872 )

给出了一种面向当前和未来不对称内存计算平台的 OLAP 查询处理技术. 不对称内存计算平台是指配置有不同计算类型的处理器、不同存储访问设备的计算机, 因此需要对 OLAP 查询处理模型按不同的计算特点进行优化存储配置和实现算法设计, 从而使 OLAP 查询处理的不同阶段更好地适应相应的存储与计算设备的硬件特点, 提高硬件设备的利用率, 更好地发挥硬件的性能. 提出了 3 阶段 OLAP 计算模型, 将传统基于迭代处理模型的 OLAP 查询处理过程分解为计算密集型和数据密集型负载, 分别由功能完备的通用处理器和并行计算能力强大的协处理器分而治之地完成, 并最小化不同存储与计算设备之间的数据传输代价. 实验结果表明基于负载划分的 3 阶段 OLAP 计算模型能够较好地适应 CPU-Phi 不对称计算平台, 实现通过计算型硬件加速计算密集型负载, 从而加速整个 OLAP 查询处理性能的目标.

参考文献 | 相关文章 | 计量指标

Select

一种基于关系数据库的图计算平台

蒋奎, 陈亮

2016 (5): 103-111. doi: 10.3969/j.issn.1000-5641.2016.05.012

摘要 ( 536 )

HTML ( 10 )

PDF(981KB) ( 672 )

本文提出了一种新的基于关系数据库管理系统 (Relational Database Management System, RDBMS)(本文简称关系数据库) 的图计算平台. 该平台将图数据以原生的形式在关系数据库的表格中存储, 从而在数据表达上和原生图计算平台达到了一致. 该平台将图计算逻辑完整准确地表达为 SQL (Structured Query Language) 查询语句. 关系数据库执行 SQL 查询语句, 从而完成图计算, 并将结果返回. 实验结果表明, 该新的平台有效地利用了关系数据库成熟的查询优化技术, 在很多方面优于现有的原生数据平台; 而目前的性能局限, 也会随着未来关系数据库的不断演化和迭代, 得到有效的解决.

参考文献 | 相关文章 | 计量指标

Select

GraphHP:一个图迭代处理的混合平台

苏静, 索博, 陈群, 潘魏, 李战怀

2016 (5): 112-120. doi: 10.3969/j.issn.1000-5641.2016.05.013

摘要 ( 562 )

HTML ( 10 )

PDF(958KB) ( 881 )

BSP(Bulk Synchronous Parallel, BSP)计算模型是建立大规模迭代式图处理分布式系统的重要基础. 现有平台(如 Pregel、Giraph、Hama)虽然已经实现了较高的可扩展性, 但主机之间高频同步和通信负荷严重影响了并行计算的效率. 为了解决这个关键性问题, 本文提出了一种基于混合式模型的执行平台 GraphHP(Graph Hybrid Processing). 它不仅继承了以顶点为中心的 BSP 编程接口, 而且能够显著减少同步和通信负荷. 通过在图分区内部和分区之间建立混合执行模型, GraphHP 实现了伪超步迭代计算, 把分区内部计算从分布式同步和通信中分离出来. 这种混合执行模型不需要繁重的调度算法或者以图为中心的串行算法, 就能有效减少同步和通信负荷. 最后, 本文评估了经典的 BSP 应用在 GraphHP 平台的实现方式. 实验表明它比现有的 BSP 实现平台效率更高. 本文提出的 GraphHP 平台虽然是基于Hama 实现的, 但它很容易迁移到其他的 BSP 平台.

参考文献 | 相关文章 | 计量指标

Select

基于Map/Reduce的分布式数据排序算法分析

余晟隽, 宫学庆, 祝君, 钱卫宁

2016 (5): 121-130. doi: 10.3969/j.issn.1000-5641.2016.05.014

摘要 ( 694 )

HTML ( 8 )

PDF(1549KB) ( 920 )

为了解决大规模数据的存储与计算, 近年来分布式系统得到了大量的应用. 如何在分布式系统中对大规模数据集进行排序是影响许多应用性能的基础问题, 其中不仅涉及每个节点上排序算法的选择, 更重要的是设计协调各节点的分布式算法. 本文总结了分布式系统中常用的分布式排序算法, 对每种算法的执行流程、代价模型和适用场景进行了分析, 并通过实验对分析结果进行了验证. 本文的工作可以帮助开发人员选择和优化分布式环境下大规模数据排序的算法.

参考文献 | 相关文章 | 计量指标

Select

非阻塞事务型实时数据注入技术研究与实现

余楷, 李志方, 周敏奇, 周傲英

2016 (5): 131-143. doi: 10.3969/j.issn.1000-5641.2016.05.015

摘要 ( 598 )

HTML ( 9 )

PDF(846KB) ( 777 )

伴随着大数据时代来临, 传统数据库系统已逐渐无法应对海量数据处理带来的挑战, 而分布式数据库系统得到了越来越多的部署和应用. 分布式数据库系统部署数据于多台机器上, 利用大规模并行计算技术实现了对海量数据的存储、管理和分析. 但针对金融领域严苛的事务型实时数据注入需求, 现有分布式数据库系统对其支持有限, 其主要原因在于利用锁和两阶段提交等方式实现分布式事务处理, 无法做到非阻塞式数据注入, 极大地影响了数据注入的性能. 华东师范大学数据科学与工程研究院自主研发的分布式内存数据库系统-----CLAIMS, 已能提供面向关系型数据集的实时数据分析服务, 但尚不能支持实时数据注入. 针对上述实时数据注入的问题, 本文重点分析了现有数据注入技术和基于分布式事务处理的实现方式, 设计了面向元数据的集中式事务处理策略, 利用无锁编程技术, 实现了支持分布式事务的高性能实时数据注入框架, 并通过热备机制实现系统的高可用性. 上述框架在 CLAIMS 系统中的实现, 经充分实验表明: 该框架能够实现高通量的事务型实时数据注入, 同时支持低延时的实时数据查询.

参考文献 | 相关文章 | 计量指标

Select

面向OceanBase的存储过程设计与实现

祝君, 刘柏众, 余晟隽, 宫学庆, 周敏奇

2016 (5): 144-152. doi: 10.3969/j.issn.1000-5641.2016.05.016

摘要 ( 724 )

HTML ( 24 )

PDF(763KB) ( 756 )

存储过程是数据库管理系统的一个重要特性, 它是标准结构化查询语言 (Structured Query Language, SQL)的一个扩展. OceanBase是一个新型的支持海量数据处理的分布式数据库系统, 但现有OceanBase的开源版本不支持存储过程功能, 影响了该系统在企业和机构中的推广和应用. 本文在深度分析存储过程原理以及OceanBase查询处理策略的基础上, 设计并实现了支持PL/SQL(Procedural Language/SQL)的存储过程机制.

参考文献 | 相关文章 | 计量指标

Select

DBugHelper:应用于大规模分布式系统开发的Debug协助工具

张燕飞, 张春熙, 李宇明, 张蓉

2016 (5): 153-164. doi: 10.3969/j.issn.1000-5641.2016.05.017

摘要 ( 455 )

HTML ( 6 )

PDF(634KB) ( 659 )

对于大规模分布式系统的开发而言, 其开发周期比较漫长, 包括前期的开发、过程中的 Debug、后期的维护和测试等. 在整个开发周期中, Debug 是一个非常关键和重要的环节, 如何才能在短时间内找到最可靠的方法来解除 bug 成为一个重要的挑战. 对于系统开发人员来说, bug 报告能非常有效地帮助其了解 bug 的所有特征信息, 并找到能修复 bug 的方法. 通过研究发现, 许多大规模分布式系统之间具有较强的相关性和相似性, 因而其 bug 的产生情况和修复方法也具有类似特征. 开发人员可以利用已存在的修复 bug 的方案来协助修复与其一致或相近的 bug. 本文提出一个适用于大规模分布式系统的 Debug 协助工具------DBugHelper, 能为某些大规模分布式系统的开发人员的 bug 修复提供比较有效、正确的帮助. DBugHelper 将最新的 bug 报告进行文本处理, 形成查询向量, 并将大量已被修复的 bug 及其相关信息进行离线处理和缓存, 从而为在线查询提供索引机制. 通过将大量已修复的 bug 报告进行离线处理并同时减少在线处理的数据量, 从而使其准确并快速地为系统开发人员提供必要的 Debug 协助工作, 以此减少系统开发的周期与成本.

参考文献 | 相关文章 | 计量指标

Select

可扩展数据管理系统中的网络请求服务机制

肖冰, 郭进伟, 钱卫宁

2016 (5): 165-172. doi: 10.3969/j.issn.1000-5641.2016.05.018

摘要 ( 471 )

HTML ( 7 )

PDF(582KB) ( 650 )

请求服务机制涉及请求的传输和处理, 是分布式数据管理系统中各组件交互并完成任务的重要前提. 本文以可扩展数据管理系统为背景, 抽象系统中的网络服务模型, 介绍系统中的网络请求服务机制. 从数据库的主要实现出发, 分析不同类型的请求在传输以及处理上的不同要求. 以OceanBase为例, 统计各机制在一个可扩展数据管理系统中的服务比重, 并进行相关的分析.

参考文献 | 相关文章 | 计量指标

当期目录