异构混合存储的软硬件协同数据放置策略*

2020-05-06李鸿飞杜溢墨

国防科技大学学报 2020年2期

李鸿飞，杜溢墨，曾熠，王磊

(1. 信息工程大学地理空间信息学院，河南郑州 450001； 2. 中国人民解放军31008部队，北京 100091)

随着网络信息技术的发展，特别是近年来，智能移动终端和多媒体技术深入社会生活各个领域，数据爆炸增长的趋势愈加显著。根据国际数据公司IDC发布的研究报告，互联网数据总量已达40 ZB[1]。除了体量大以外，数据还呈现出类型多、价值密度低、实时性强等“大数据”特性。

为了高效存储管理“大数据”，学术界和产业界面向不同应用特性提出了各类存储管理系统和存储设备：存储管理系统主要有关系型数据库、非关系型数据库(Not only Structured Query Language, NoSQL)存储和以HDFS(Hadoop distributed file system)为代表的分布式文件系统等；存储设备主要有传统磁盘、闪存固态盘和相变存储器(Phase Change Memory, PCM)、自旋扭矩转换随机存储器(Shared Transistor Technology Random Access Memory, STT-RAM)、阻变式存储器(Resistive Random Access Memory, RRAM)等新型存储器件。这些存储管理系统和存储设备特点各异，适用于不同应用类型，但大数据环境下的应用复杂多样，批处理、流处理、交互式应用可能同时存在，而这些应用在数据类型、访问特性、时效要求上都有很大不同，单一存储管理系统和存储设备难以满足存储需求。混合存储，因能综合利用各类存储系统和设备的优点，成为一种较好选择，被企业、数据中心等广泛采用[2]。

当前的混合存储设计或只考虑了软件层面存储系统的混合，或只考虑了硬件层面存储设备的混合，无法综合利用混合存储系统和混合存储设备的优势。一种简单的软硬混合存储设计是将两个层面的混合进行堆叠，软件层面采用关系型数据库、非关系型数据库以及分布式文件系统混合的存储管理模式，硬件层面采用机械硬盘与固态盘混合的模式。但该设计需要进行两次数据特征识别和数据分配，既造成时间和资源的浪费，又由于数据分配没有同时考虑存储系统和存储设备，无法从全局角度为要存储的数据规划最合适的存储系统和存储设备。

本文提出的软硬件协同的数据放置策略，虽然位于存储系统之上，但除了能感知混合存储系统外，也能通过配置文件感知底层存储设备，相比软件层混合与硬件层混合简单堆叠的方法，只需通过一次特征识别和数据分配就能为数据选择合适的存储管理系统和存储设备，提高了存储执行效率。为适应不同需求，在软硬协同数据放置基础上，又提出了静态放置和动态放置两种放置模式。静态放置是在数据分配前，根据应用、存储系统、存储设备特性为不同应用事先规划好数据存放路径。动态放置是根据应用访问历史记录预测下一时刻应用特征，然后为数据选择适合存放的存储系统和存储设备，相比静态数据分配策略，其对应用识别的粒度更细，合理性更好，缺点是记录数据存放位置的元数据信息多，增加了时间和空间开销。

1 现状综述

1.1 NoSQL存储

NoSQL存储相比关系型数据库，具有可扩展性好、存储模式灵活、数据模型与应用层数据结构接近等优势，越来越多地用于大数据存储环境中,包括Key-Value存储、列家族存储、文档存储、图存储等。Sadalage等[3]全面介绍了NoSQL存储，包括起源、特性、典型应用等。Catell[4]比较了结构化查询语言(Structured Query Language, SQL)和几种典型的NoSQL数据库，并给出了不同类型数据库的适用场景。综合分析几种典型的NoSQL存储，其主要特点如表1所示。

1.2 混合存储管理系统

Nance等[5]认为虽然NoSQL在大数据时代应用广泛，但关系型数据库仍有生存空间和应用场景，涵盖NoSQL与关系型数据库的混合存储管理系统就被很多数据中心采用。联想采用混合存储架构为智慧城市提供数据存储，其中，12 PB的非结构化数据采用分布式NoSQL存储，33 TB的结构化数据采用关系型存储[6]。淘宝推出的数据魔方产品主要提供行业数据分析、店铺数据分析功能，其存储层采用OldSQL+NoSQL混合模式，由基于MySQL的分布式关系型数据库集群MyFOX和基于HBase的NoSQL存储集群Prom组成[7]。安洋等[8]提出了行列混合的存储布局，可实现实体的行式存储或列式存储,同时在一个实体内部,可针对不同字段的稀疏、稠密等数据特征,选择适合的行存储或列存储格式。Huang等[9]提出了一种基于NoSQL与SQL混合数据库管理系统的负载均衡机制，动态检测系统中的热点，并将热点上的数据迁移到冷节点上，从而提高混合存储系统的吞吐量。Grolinger等[10]分析比较了NoSQL和NewSQL数据库以及它们各自适用的场景，并为数据库系统设计人员选择合适的数据存储提供指导和借鉴。Lawrence[11]针对NoSQL数据库访问接口各异且不支持SQL的问题，提出了一种统一架构，将NoSQL存储与SQL存储集中统一管理，通过设置虚拟层，能将SQL和Java数据库连接(Java DataBase Connectivity, JDBC)访问转换成对NoSQL的访问。

表1 典型的NoSQL存储及其特征Tab.1 Typical NoSQL stores and characteristics

1.3 混合存储设备

闪存、PCM等新型存储器件的引入，改变了以往基于动态随机存取存储器(Dynamic Random Access Memory, DRAM)、磁盘的存储架构。由于存储器件特性各异，而大数据应用需求千差万别，综合应用各类存储设备的混合存储架构为解决大数据存储瓶颈提供了新思路。Ouyang等[12]指出，百度采用混合存储设备，将经常访问的网页和图片等数据存储在定制化的固态盘(Solid State Drive, SSD)上，不经常访问的数据存储在硬盘(Hard Disk Drive, HDD)上，提升了整体数据访问性能。金培权[13]针对大数据存储与管理中的高效存储、实时处理等挑战，研究了通过引入闪存、PCM等新型存储器件构建混合大数据存储架构的解决思路，包括基于DRAM与PCM的混合主存架构，DRAM、闪存与磁盘共存的混合层次架构，冷热数据分离的混合分布式存储等。Sang等[14]提出采用SSD与HDD混合的存储架构，利用SSD读和大块写性能比HDD要好的特点，用SSD代替部分HDD存储事务日志、回滚段、临时表空间等，可以显著提高数据库应用性能。Canim等[15]提出使用SSD代替部分HDD，作为数据系统缓存区的扩展，可以有效减少HDD上的I/O访问，显著提高数据库性能。

2 软硬协同混合存储

2.1 问题描述

当前的大数据中心具有以下几个特点：一是服务的应用类型多样，包括事务处理、在线分析、实时交互等；二是存储管理系统多样，包括关系型数据库、Key-Value存储、列家族存储等；三是存储设备多样，包括HDD、SATA SSD、NVMe SSD等。为了同时服务不同类型的应用，综合利用不同存储系统和存储设备的优势，数据中心通常采用混合存储体系架构：软件层包含各类存储管理系统的混合，硬件层包含各类存储设备的混合。对于混合存储架构，需要考虑的一个重要问题是数据放置，即为数据选择合适的存储管理系统和存储设备。通常，数据放置可分为两步：第一步是特征识别，识别对象包括应用、存储系统、存储设备；第二步是数据分配，根据第一步识别的特征为数据选择合适的存放位置。

(a) 只考虑混合存储系统(a) Only considering hybrid storage management systems

(b) 只考虑混合存储设备(b) Only considering hybrid storage devices

(d) 同时考虑混合存储系统和混合存储设备(d) Considering hybrid storage management systems and hybrid storage devices simultaneously图1 混合存储架构中各类数据放置策略设计Fig.1 Data placement strategies for hybrid store architecture

图1给出了混合存储架构中各类数据放置策略设计，其中图1(a)～(b)是当前已有的，图1(c)是图1(a)和图1(b)的结合，图1(d)是本文提出的。图1(a)的数据放置模块位于应用层与存储管理系统层之间，数据放置时只考虑应用和存储管理系统的特征。图1(b)的数据放置模块位于存储管理系统与存储设备之间，数据放置时只考虑存储管理系统和存储设备的特征。这两类数据放置策略都只考虑了应用、存储管理系统、存储设备三个要素中的两个，显然不是全局最优。如果综合考虑三个要素，简单直观的设计是将图1(a)、(b)结合，设置两个数据放置模块，如图1(c)所示。然而，该设计虽然考虑了三个要素，但还存在两个问题：一是需要设置两层数据放置模块，开销较大；二是每一层的数据放置只考虑了其上下层，即两个要素的特性，虽然总体上涵盖了三个要素，但并没有将三个要素综合考虑，也难以达到全局最优。针对这两个问题，本文提出了软硬件协同混合存储数据放置策略，如图1(d)所示，只有一层数据放置模块，位于应用层与存储系统层之间，但进行数据放置时不仅考虑这两层的特征，也能通过读取存储设备配置文件同时感知存储设备的特征。相比图1(c)，该设计有两个优势：一是只有一层数据放置策略，但包含了图1(c)中两层数据放置的功能，减少了开销；二是数据放置策略一次性综合考虑应用特征、混合存储管理系统、混合存储设备三个要素，提高了数据放置的合理性。

图1四种策略的形式化描述如下：假设数据放置策略用P表示，影响放置策略的三个要素——应用、存储管理系统、存储设备分别用A、S、D表示，各种放置策略其实是P关于A、S、D的函数，分别用F1、F2、F3、F4表示，如表2所示。图1(c)的放置策略使用了三个函数进行表示，F3是在F1、F2各自最优解基础上的最优解，明显优于F2；图1(d)的放置策略用F4表示，综合考虑了A、S、D，是(A，S，D)三维空间上的最优解，要优于F3的最优解。具体证明过程此处不再赘述。

表2 图1中各放置策略的数学表示和含义Tab.2 Mathematic expression and meaning of data placement strategies in the Fig.1

2.2 总体设计

图1(d)展示了软硬件协同数据放置策略概要架构，图2进一步描述了数据放置策略的详细设计。图2中的数据放置模块是数据放置策略的核心，主要包括应用特征识别器、放置策略设置器、放置策略执行器、数据打包器和数据分流器五个部件。其中，应用特征识别器对所有应用的访问进行识别分类，生成应用特征参数，作为放置策略的一个输入。放置策略设置器读入应用特征参数、存储管理系统参数文件、存储设备参数文件，根据设定的算法生成存储路径信息，包括存储数据的存储管理系统和存储设备。放置策略执行器用于执行放置策略，将数据的存储路径作为元数据信息记入元数据记录表中。数据打包器根据元数据记录的存储路径信息给数据加上存储设备标签，用于混合存储管理系统选择存储设备位置。数据分流器根据元数据记录的存储路径信息，将打包好的数据分配到相应的存储系统。

图2 软硬协同混合存储体系架构设计Fig. 2 Software and hardware co-design of hybrid store architecture

图2还展示了软硬协同数据放置策略的数据存储流程。首先，各应用的数据访问请求发送到应用特征识别器，经分析后生成应用特征结果，同时，访问请求发送到数据打包器。数据打包器接收请求后，判断请求类型，若是读请求，读取元数据记录表，给请求加上存储设备标签后发送到数据分流器。若是写请求，需三步完成：①调用放置策略设置器，放置策略设置器读取应用特征识别器生成的应用特征参数、存储管理系统参数文件、存储设备参数文件，生成数据存储路径；②调用放置策略执行器，将数据存储路径登记在元数据记录表中；③根据元数据记录的存储路径信息给请求加上存储设备标签，明确请求要存放的存储设备，然后将请求发送到数据分流器。数据分流器对接收的读写请求，读取元数据记录表，根据存储路径信息将请求分配到相应的存储管理系统。

存储管理系统采用各自存储管理模式对数据请求进行处理，然后调用设备标签解析器提取出数据请求中的存储设备信息，再将请求发送到相应的存储设备，具体在设备上的位置仍由存储管理系统自身管理。除了应用本身需要存储的数据，存储管理系统自身还会产生一些数据，用于存储的管理，比如索引、日志等，由于这些数据经常访问，通常存放在访问速度较快的存储设备上[11，14]。

2.3 数据放置策略设计

放置策略设置器根据应用、存储管理系统、存储设备类型及特性，为数据选择尽可能“最优”的存储路径。“最优”通过应用执行时间的长短来衡量，所选的存储路径使应用的执行时间越短，则路径越优。最优存储路径寻找问题和方法的形式化描述如下：

假设数据中心有l个应用，分别表示为A1,A2,…,Al；m个存储系统，分别表示为S1,S2,…,Sm；n个存储设备，分别表示为D1,D2,…,Dn。为数据选择最优存储路径时，首先明确该数据所在的应用，假设为Ak(1≤k≤l)，为应用Ak的数据选择存储系统Sp(1≤p≤m)、Dq(1≤q≤n)，使得应用执行时间T最短，T可以表示成T(Ak,Sp,Dq)，Sp、Dq即为应用Ak中数据的最优存储路径。通过求解方程式(1)可得Sp、Dq。

T(Ak,Sp,Dq)=min(T(Ak,S1,D1)，…，T(Ak,S1,Dn),T(Ak,S2,D1)，…,T(Ak,S2,Dn),T(Ak,Sm,D1),…,T(Ak,Sm,Dn))

(1)

方程左边表示应用Ak的数据在最优存储路径下的执行时间，右边表示应用Ak的数据在所有存储路径下最短的执行时间。应用执行时间与应用、存储管理系统、存储设备的部分特征有关，选取重要特征作为计算执行时间的依据，用式(2)表示。

T(Ak,Sg,Dh)=FAk·Ia+FSg·Ig+FDh·Ih

(2)

式中：FAk、FSg、FDh分别表示应用Ak、存储管理系统Sg、存储设备Dh的特征值向量；Ia，Ig，Ih分别表示各特征值向量对执行时间的影响因子向量。应用特征向量FAk包括读写比例、读写块大小、局部性强弱等要素；存储管理系统特征向量FSg包括读写访问延迟、存储容量、一致性强弱等要素；存储设备特征向量FDh包括设备读写访问延迟、吞吐量、存储容量等要素。Ia、Ig、Ih可以通过在不同存储管理系统和存储设备组合的环境下运行负载得到应用执行时间后，根据式(2)进行估算。

根据不同应用场景，提出两种数据放置模式：静态放置和动态放置。

1)静态放置是在系统运行前就规划好数据存储路径的放置策略。采用静态放置策略时，应用、存储管理系统、存储设备的特征都根据经验和参数文件确定，对应用特征进行识别时，将各应用视为一个整体，一旦为整个应用规划好了存储路径，该应用产生的所有数据都按规划的途径存储。每种应用在各类存储路径下的执行时间在运行前根据式(2)计算，然后根据式(1)，在系统运行前为应用选择出存储路径。例如：应用甲、应用乙分别是在线事务处理和批处理应用，基于以往对此类应用特征的认识以及各类存储管理系统和存储设备的特点，为应用甲规划以下存储路径——关系型数据库、SATA SSD，为应用乙规划以下存储路径——Key-Value存储、HDD。

2)动态放置是在系统运行过程中规划数据存储路径的放置策略。采用动态放置策略时，应用特征根据应用的历史访问记录动态分析识别，存储管理系统和存储设备特征根据系统实时状态确定，然后通过式(2)和式(1)计算出存储路径。应用、存储管理系统和存储设备的特征值在不同时段可能发生变化，根据式(1)和式(2)计算出的数据存储路径也相应跟着变化。相比静态放置，动态放置实时感知系统运行状态，对应用的感知粒度更细，能提高存储路径规划的合理性，但其实现有一定的时空开销，在实验部分将对其进行比较。

2.4 元数据设计

元数据记录表由一系列访问请求存储路径的记录组成，每条记录包含三部分，分别是逻辑地址、存储管理系统号和存储设备号，其设计如图3所示。

图3 元数据设计Fig. 3 Meta-data design

为减少元数据开销，采用两种优化方法：一是采用逻辑块组减少元数据记录表条目。在元数据记录表中记录逻辑块组地址，而非各逻辑块地址。根据设定的组大小，取逻辑块地址的前x位(x=逻辑地址位数-log2(组大小))作为逻辑块组地址。当逻辑块组确定好存储路径后，该组下的所有逻辑块均采用该存储路径。二是采用索引加速元数据搜索。将元数据记录表分为若干大小相同的子表，每个子表第一个表项的逻辑块组地址作为索引表中的逻辑块组起始地址，该子表自身地址作为元数据记录表位置，将它们依次记录在索引表中。根据逻辑块组地址查找元数据记录表时先查询索引，确定元数据记录子表后，再在子表中查询。子表大小根据索引表可用空间大小确定，索引表可用空间越大，子表越小，查询效率也越高。

3 实验测试及结果分析

3.1 实验配置

数据放置策略需要感知存储管理系统和存储设备的状态，部分存储管理系统和设备没有相关接口，故采用仿真方法实现各类数据放置策略并进行测试。对于存储管理系统和存储设备，根据官方参数文件对其性能进行建模。测试负载来源于实际场景，主要包括查询、更新、归档应用，根据系统运行特点，选取三个时间段，分别截取负载记录，并分析存储设备访问轨迹，特点如表3所示。

表3 测试负载类型及特点Tab. 3 Test workloads` types and characteristics

存储管理系统从关系型数据库和三类NoSQL存储中分别选取了典型的一种，关系型数据库性能来源于Oracle官方性能文档[16]；NoSQL存储性能来源于试验测试报告[17-19]，对其在相同配置、负载量下的性能进行了分析，如表4所示。

表4 存储管理系统性能参数Tab.4 Storage management systems performance data ms

存储设备选取了SAS HDD、SAS SSD和NVMe SSD三类，根据官方参数文件[20-22]，对其在相同配置、负载下的性能进行了分析，如表5所示。

表5 存储设备性能参数Tab.5 Storage devices performance data

实验测试比较了五种放置策略：Str.a、Str.b、Str.c是基准测试策略，Str.d.static和Str.d.dynamic是本文提出的软硬件协同数据放置策略，分别表示静态放置和动态放置。对于Str.d.static和Str.d.dynamic，从三种应用、四种存储管理系统和三种存储设备中选取可量化的典型特征值，如表6所示。

表6 应用、存储管理系统和存储设备所用的典型特征值Tab.6 Selected typical feature factors of applications, storage systems and devices

1)Str.a：基于混合存储管理系统的数据放置策略，数据放置只考虑存储管理系统类型和性能差异，对于存储设备，按比例轮流分配，即图1(a)所示策略。

2)Str.b：基于混合存储设备的数据放置策略，数据放置只考虑存储设备类型和性能差异，对于存储管理系统，按比例轮流分配，即图1(b)所示策略。

3)Str.c：基于混合存储管理系统和存储设备的软硬件独立数据放置策略，数据放置需分两次进行，分别针对混合存储管理系统和混合存储设备，即图1(c)所示策略。

4)Str.d.static：基于混合存储管理系统和存储设备的软硬件协同数据放置策略，数据放置一次性完成，同时考虑混合存储管理系统和混合存储设备特点，数据放置采用静态放置。

5)Str.d.dynamic：与Str.d.static一样，都是基于混合存储管理系统和存储设备的软硬件协同数据放置策略，区别是数据放置策略采用动态放置。

3.2 加载时间

在执行负载之前，需要对存储管理系统加载数据。为了比较不同数据放置策略下存储管理系统加载数据的性能，分别测试了10万、100万、500万条数据下，五种不同数据放置策略的数据加载时长，并以Str.a的加载时长为基础进行了标准化，如图4所示。在五种数据放置策略中，Str.b的数据加载时间最长，Str.d.dynamic相比Str.c可以缩短近25%的加载时间。数据加载量从10万条到100万条时，随着加载量变大，Str.d的性能显著提升，但加载量从100万条到500万条时，性能提升不明显。这是由于在数据量为10万条时，带宽还有较大富余，而到100万条时，由于实验中网络带宽设置较低，Str.d带来的性能改善受到了带宽瓶颈的限制。在真实数据中心，网络带宽较高，性能提升不会受带宽影响。

图4 不同数据量下五种数据放置策略数据加载时间Fig.4 Data loading time of 5 data placement strategies for different loading volume

3.3 执行时间

为了比较不同数据放置策略的性能，测试了五种不同数据放置策略在加载10万条数据记录后执行三类负载的执行时间，并以Str.a的执行时间为基础进行了标准化，如图5所示。三类负载下，Str.d.dynamic都具有最短的执行时间，相比Str.a，最大可缩短近30%；相比Str.d.static, Str.d.dynamic的执行时间可缩短约10%。

图5 五种数据放置策略执行三类负载的时间Fig.5 Execution time of 5 data placement strategies under 3 kinds of workloads

3.4 时空开销分析

本文提出的软硬件协同数据放置策略的空间开销主要是元数据所用空间，时间开销主要是查询元数据记录表所用时间。静态放置策略的元数据记录表大小只与应用个数、数据存储管理系统个数和存储设备个数相关，由于应用、存储管理系统和存储设备个数通常都不大，相比软硬独立设计的数据放置策略，其时空开销可以忽略。动态数据放置策略的元数据包括索引和元数据记录表两部分。元数据记录表每条记录大小为10 B(LBGA：8 B，MSN：1 B，DSN：1 B)，索引表每条记录的大小为9 B(LBGAI：1 B，MRTL：1 B)。若逻辑块组大小设置为16 KB，对于1 TB的数据量，所需元数据记录表大小为640 MB，索引表大小为6.4 MB。由于元数据存储在内存中，相比I/O访问，其时间开销可以忽略[23]。