面向日志结构化数据存储的高效数据加载

丁国浩; 徐辰; 钱卫宁

doi:10.3969/j.issn.1000-5641.2019.05.012

面向日志结构化数据存储的高效数据加载

doi: 10.3969/j.issn.1000-5641.2019.05.012

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

基金项目:

国家重点研发计划 2018YFB1003400

上海市青年科技英才扬帆计划 19YF1414200

详细信息

作者简介:
丁国浩, 男, 硕士研究生, 研究方向为分布式数据管理系统.E-mail:guohao.ding@outlook.com

通讯作者:
徐辰, 男, 副教授, 研究方向为大规模分布式数据管理系统.E-mail:cxu@dase.ecnu.edu.cn

中图分类号: TP392
计量
- 文章访问数: 101
- HTML全文浏览量: 90
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2019-07-28
- 刊出日期: 2019-09-25

Efficient data loading for log-structured data stores

School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

摘要

摘要: 近年来，随着互联网技术的快速发展，无论是互联网企业还是传统的金融机构，用户量和业务处理数据量都在快速地增长.传统的通过增加服务器并采用基于分库分表的方法来解决扩展性问题，需要大量的人工维护成本和硬件开销.为降低开销和分库分表带来的各种问题，业界通常用新型数据库系统替换原有的系统，其中，基于日志结构合并树存储的数据库系统（如OceanBase）被广泛采用，这类系统磁盘上存储数据块呈现全局有序的特征.在从传统数据库切换到新型数据库过程中，需要将大量数据加载到新数据库系统中，长时间加载的过程中可能出现数据库节点宕机.为了减少总加载时间和故障恢复时间，提出了一种负载均衡且支持高效容错的数据加载方法；为了支持负载均衡的数据加载，与预确定分区划分数据的方法不同，考虑到目标系统默认存储块大小，采用通过基于文件大小和目标系统默认存储块大小预计算分区数目，并利用分库分表的数据导出往往已经排序的特点，采用选取部分采样块和等间隔选取样本的方式确定分区之间的切分点，避免了全局采样和随机或头部样本选取方式确定切分点带来的高开销；为了加快故障恢复速度，利用日志结构合并树存储系统的多备份减少故障恢复时的数据量，提出了基本副本局部故障恢复方式，避免了完全重新加载的故障恢复方式.实验结果表明，相比采用预确定分区数目和全局选取采样块的随机或头部选取样本方法，采用预计算分区数目和部分选取采样块的等间隔选取样本确定切分点的方法，提高了数据加载的性能，并且验证了基于副本局部故障恢复方法相比完全重启加载恢复方法的高效性.
- 数据加载 /
- 负载均衡 /
- 容错 /
- 日志结构
Abstract: With the rapid development of Internet technology in recent years, the number of users and the data processed by Internet companies and traditional financial institutions are growing rapidly. Traditionally, businesses have tackled this scalability problem by adding servers and adopting methods based on database sharding; however, this can lead to significant manual maintenance expenses and hardware overhead. To reduce overhead and the problems caused by database sharding, businesses commonly replace heritage equipment with new database systems. In this context, new databases based on log-structured merge tree storage (such as OceanBase) are being widely used; the data blocks stored on the disks of such systems exhibit global orderly features. In the process of switching from a traditional database to a new database, a large amount of data must be transferred, and database node downtime may occur when there is extended loading. In order to reduce the total time for loading and failure recovery, we propose a data loading method that supports load balancing and efficient fault tolerance. To support balanced data loading, we pre-calculate the number of partitions based on the file size and the default block size of a target system rather than using a pre-determined number of partitions. In addition, we use the feature that the data exported from the sharding database is usually sorted to determine the split points between partitions by selecting partial sampling blocks and selecting samples in sampling blocks at equal intervals, avoiding the high overhead caused by global sampling and selecting samples randomly or at the head in sampling blocks. To speed up the recovery process, we propose a replica-based partial recovery to avoid restart-based complete reloading; this method uses the multi-replica of an LSM-tree system to reduce the amount of reloaded data. Experimental results show that by pre-calculating the number of partitions and partial sampling blocks and by using equal-interval sampling, we can accelerate data loading relative to pre-determining the number of partitions and global sampling blocks as well as relative to random or head sampling strategies. Hence, we demonstrate the efficiency of replica-based partial failure recovery compared to restart-based complete reloading.
- data loading /
- load balance /
- fault tolerance /
- log-structured

HTML全文

图 1 LSM树的实现

Fig. 1 Implementation of an LSM-tree

下载: 全尺寸图片幻灯片

图 2 基于文件的加载过程

Fig. 2 File-based loading process

下载: 全尺寸图片幻灯片

图 3 采样块数

Fig. 3 Number of sampling blocks

下载: 全尺寸图片幻灯片

图 4 样本选取

Fig. 4 Sample selection

下载: 全尺寸图片幻灯片

图 5 故障恢复过程

Fig. 5 Recovery process

下载: 全尺寸图片幻灯片

图 6 分区数目对加载性能影响

Fig. 6 Effect of the number of partitions on loading

下载: 全尺寸图片幻灯片

图 7 部分采样对加载性能影响

Fig. 7 Effect of partial sampling on loading

下载: 全尺寸图片幻灯片

图 8 选取样本方法对加载性能影响

Fig. 8 Effect of sample selection on loading

下载: 全尺寸图片幻灯片

图 9 故障恢复

Fig. 9 Fault recovery

下载: 全尺寸图片幻灯片

算法1 故障发现和恢复

1:获取集群的节点状态信息

2:获取加载表的各个子tablet的加载状态

3: for每个加载失败的子tablet do

4: 重新分配加载任务到其他节点

5: end for

下载: 导出CSV

算法2 基于副本的故障恢复

1: for每个需要加载的分区$P$ do

2: need_copy //检查分区$P$是否满足副本数

3: if need_copy then

4: 选择存储节点

5: if分区$P$的副本数=0 then

6: 从数据源选择加载

7: else

8: 从其他副本选择复制

9: end if

10: 添加新加载任务

11: end if

12: end for

下载: 导出CSV

表 1 服务器配置

Tab. 1 Server setup

类型	描述
OS	CentOS release 6.5(Linux version 2.6.32)
CPU	2$\times$Intel(R) Xeon(R) CPU E5-2620 0 @ 2.00 GHz(6 cores/CPU)
Memory	165 GB
Network	Broadcom Corporation NetXtreme BCM5719 Gigabit Ethernet

下载: 导出CSV

表 2 不同采样比例下$\varepsilon $对加载性能影响

Tab. 2 Influence of $\varepsilon $ on loading performance under different sampling ratios

采样方式	采样比例	$\varepsilon $
采样方式	采样比例	0	1	2	3	4
全局采样	1	518	496	497	497	499
部分采样	1/2	465	455	457	458	461
	1/3	457	453	418	429	430
	1/4	427	414	413	417	425
	1/5	483	478	461	445	442

下载: 导出CSV

参考文献(16)

[1]	O'NEIL P, CHENG E, GAWLICK D, et al. The log-structured merge-tree (LSM-tree)[J]. Acta Informatica, 1996, 33(4):351-385. doi: 10.1007/s002360050048
[2]	CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: A distributed storage system for structured data[C]//OSDI'06 Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation-Volume 7. 2006: 205-218.
[3]	LevelDB[EB/OL].[2019-06-09]. https://github.com/google/leveldb.
[4]	Hbase[EB/OL].[2019-06-09]. http://hbase.apache.org/.
[5]	OceanBase[EB/OL].[2019-06-09]. https://github.com/alibaba/oceanbase/.
[6]	TiDB[EB/OL].[2019-06-09]. https://university.pingcap.com/
[7]	COOPER B F, RAMAKRISHNAN R, SRIVASTAVA U, et al. PNUTS:Yahoo!'s hosted data serving platform[J]. Proceedings of the VLDB Endowment, 2008, 1(2):1277-1288. doi: 10.14778/1454159.1454167
[8]	SILBERSTEIN A, COOPER B F, SRIVASTAVA U, et al. Efficient bulk insertion into a distributed ordered table[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008: 765-778.
[9]	SILBERSTEIN A E, SEARS R, ZHOU W, et al. A batch of PNUTS: Experiences connecting cloud batch and serving systems[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. ACM, 2011: 1101-1112.
[10]	Hadoop[EB/OL].[2019-06-09]. https://hadoop.apache.org/
[11]	Cassandra[EB/OL].[2019-06-09]. http://cassandra.apache.org/.
[12]	CDEAR[EB/OL].[2019-06-09]. https://github.com/daseECNU/Cedar/.
[13]	AZQUETA-ALZÚAZ A, PATIÑO-MARTINEZ M, BRONDINO I, et al. Massive data load on distributed database systems over HBase[C]//Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. IEEE, 2017: 776-779.
[14]	DEAN J, GHEMAWAT S. MapReduce:Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113. doi: 10.1145/1327452.1327492
[15]	BARCLAY T, BARNES R, GRAY J, et al. Loading databases using dataflow parallelism[J]. ACM Sigmod Record, 1994, 23(4):72-83. doi: 10.1145/190627.190647
[16]	RAMAKRISHNAN S R, SWART G, URMANOV A. Balancing reducer skew in MapReduce workloads using progressive sampling[C]//Proceedings of the 3rd ACM Symposium on Cloud Computing. ACM, 2012: Article No.16.