李雪菲,李 铮,张 贺,荣国平

1(南京大学 软件学院,南京 210046)2(隆德大学 电气与信息技术系,瑞典 隆德 22363)

1 引 言

亚马逊是云服务行业最早开发业务的领先巨头,其弹性云更是受到广泛应用.其中,弹性云的定价模式共有三种:按需、预定以及竞价[1,2].

1)按需:消费者根据固定使用单元,为其使用的虚拟机来付费,不需长期承诺.

2)预定:消费者为服务提前支付一定费用,并从其使用情况获得折扣和更低价格.

3)竞价:消费者为资源竞价,当投标价超过定价则消费者方可获得使用权.

竞价型云服务以其低廉的价格和易用性受到广泛欢迎,可以在花费最少的情况下使用高性能的计算资源.

由于商业保密等原因,亚马逊公司并不向外公布其定价模式[3].但是,由于竞价型云服务的巨大潜力,研究该种定价模式一方面可以帮助云服务供应商参考并提供类似的定价模式,另一方面,可以帮助使用竞价型云服务的用户选择合适自身的消费组合,以达到节约其成本的目的[4].

本次研究以从亚马逊官方网站获得的价格历史作为样本,对数据进行了整理、筛选和清洗,获得了1053种云服务的价格历史,每条价格历史的价格数量从几百条到五十万条不等.之后,对应绘制了走势图,完成了云服务价格历史的可视化,像股票走势一样,可以直观地判断价格的变化.

为了挖掘数据中隐藏的规律和特征,采用两种分类方法:KNN分类算法和k-means聚类算法,对竞价型云服务做了分类.结果显示,可以很好地对云服务进行分类,可从中比较出较为典型的价格实例.同时,对于源数据和过程产生的数据进行了朴素统计分析,从中发现了大量的规律.

综上,本文对亚马逊官方提供的大量混杂数据做了整理、筛选和清洗,以及可视化、分类和数据挖掘.继而,对价格历史绘制了相应的走势,并以两种分类方法对云服务做出了分类.未来将以此为基础,继续总结价格的典型规律,寻找价格走势共同的特点,从而获得更多对于定价策略的认识,以达到为云服务提供商的定价参考和对用户的消费建议的目的.

2 课题背景及国内外研究现状

2.1 云服务定价研究现状

随着计算机水平的发展,云计算技术和云计算理念正在不断发展.云计算以一种新型的商业模式,联合基础设施、平台以及软件作为服务的内容,通过网络租赁的方式提供给用户使用.

黎春兰[5]等根据即用即付费(pay-per-use)和预订(subscription)这两种定价模型及其四种形式:每单位定价、分级定价、预订定价和动态定价,以服务内容为依据,进一步分析了 IaaS、PaaS和SaaS三种基本的云服务模型的定价策略;殷秀叶[6]等提出一种刺激机制,可以通过历史资源使用情况制定预定价格.

2.2 竞价型实例研究现状

Javadib等[7]认为,在公共云的现货市场中,随机调度算法和容错机制是竞价型实例的特征,并通过最大期望算法和混合高斯分布为竞价型实例提出了一个数学模型[8],这种模型可以拟合竞价型实例的价格历史,但由于定价政策在不断变化,该存在着一定的局限性;Wee[9]将竞价型实例视为具有实时定价性质的计算资源;Orna Agmon等人[10]认为价格并不是由市场驱动的,有时可能是由亚马逊官方指定、提前假设好;Vivek等[11]提供了一种现货价格预测算法,以尽可能地延长连续使用云服务的时间,这一研究非常具有现实意义.

Saha[12]提出了一些关于中小型企业使用实例的推荐、Sangho Yi[13]则采用研究断点的方式,以及Mattess等[14]等研究都针对于减少用户成本.

而William[15]提出了一种资源分配策略,能够快速地在间歇性的虚拟机池上运行计算密集型作业;陈冬林[16]等运用数学模型求解出最优定价区间,通过算例验证了价格变动对市场需求和利润的影响,并分析了需求价格弹性对利润的敏感性.

3 难点分析与解决方案

1)数据集含有大量数据,实例种类混杂,需要分析的源数据总量达到15.5G以上,析出云服务种类达1053条.仅根据数据集文本,难以直接判断单个实例的价格变动历史和价格变动趋势.

2)整理以后,析出1053种云服务实例,发现许多实例具有相似的走势形状,然而,难以直接判断价格的共同特征.这意味着,需要对实例进行分类,许多实例有可进一步分析的相似之处.然而,使用监督学习类的KNN分类方法对1053种云服务分类,较为依赖主观的人工标签.

3)另外,数据蕴含着许多隐藏规律,需要找出这些规律.

4)由于不同云服务产生价格的时刻不同,因此,在比较不同云服务实例时,用欧氏距离判断远近有一定的误差.

对于难点1),可编写程序,整理数据集,将每条实例的价格历史整理、筛选、清洗出来.

对于难点2),将对实例的价格历史绘制走势图做好可视化,其次,对实例做分类,挖掘不同云服务实例价格历史的共同数据规律.对于人工标签的误差,将引入k-means算法共同分类,选取两种分类结果的交集,作为比较典型的分类结果.

对于难点3),将使用朴素统计方法对官方原始数据以及程序运行过程中获得的数据进行统计分析,获取最值、方差等等,挖掘数据的内部规律.

对于难点4),将补齐价格产生的时间.

4 数据整理与处理

从亚马逊官方网站下载的原始数据集,是根据时间排列而混杂排布的,如表1所示.因此,第一步需要将按照种类、运行的操作系统,以及数据中心所在的地区这三个条件组合,筛选出单条组合价格历史,以便后续对其进行更细致的分析.

由于亚马逊官方网站只提供过去两个月内的数据,因此需要在距离上次下载不到两个月的时间内,下载新的数据集,这样可以保证数据集能在时间上完整地覆盖.因此数据集与数据集之间,含有许多重复的数据.

首先,整理和筛选了官方网站下载的混乱数据集,获得了1053种云服务的购买组合方式,每一种云服务组合都含有一条价格历史.其次,对于价格历史做了可视化整理,发现许多云服务有相似的价格轨迹.将基于逐条整理的云服务价格历史做进一步的分析,以反向推导的方式推测其定价策略.

4.1 单条数据集整理

由于数据集中实例仅按照价格产生时间点排列,因此难于直接分析每个实例的特点和历史.从内容来看,种类、系统、地区三个条件唯一决定一条实例,因此,程序依次遍历这三个条件,将相同种类、使用相同系统、运行在相同数据中心的实例数据集合到一起.表1是需要整理的数据集,来自2015年9月8日的官网.对其运行单条实例整理程序,析出的某一条实例的价格历史如表2所示,由于篇幅有限仅展示部分.

在整理数据以后,可获得规定时段内的、通过条件组合筛选的价格历史.

4.2 数据清洗与可视化

由于每个数据集的大小从0.2GB到4GB不等,因此如果直接执行拼接所有数据集并剔除重复数据的程序,会使得整个数据集异常庞大,不利于扩展使用.因此,使用一种不断扩充的方法.首先,对数据集分别执行实例整理程序.在2015年11月4日下载的数据集中,获得了879个实例,最后一个数据集,即为从2016年11月19日下载的数据集中,获得了1050个数据.

表1 从亚马逊网站获得的云服务竞价型实例的历史价格(部分)
Table 1 Price history of Amazon spot instance from their official website

价格价格产生的时间点实例类型操作系统地区0.27242015-09-08T15:32:31+0200cc2.8xlargeLinux/UNIX(Amazon VPC)us-east-1b0.41802015-09-08T15:32:30+0200r3.8xlargeLinux/UNIX(Amazon VPC)us-east-1a0.37772015-09-08T15:32:30+0200r3.8xlargeLinux/UNIX(Amazon VPC)us-east-1b0.27932015-09-08T15:32:30+0200m3.2xlargeWindowsus-east-1b0.05122015-09-08T15:32:28+0200c1.mediumWindowsus-east-1b0.07522015-09-08T15:32:28+0200m2.xlargeWindowsus-east-1a0.01132015-09-08T15:32:27+0200m1.mediumLinux/UNIXus-east-1c0.07082015-09-08T15:32:26+0200m3.xlargeSUSE Linuxus-east-1e0.06642015-09-08T15:32:26+0200m3.xlargeSUSE Linuxus-east-1c0.08712015-09-08T15:32:25+0200m3.2xlargeLinux/UNIX(Amazon VPC)us-east-1c

表2 经整理us-east-1a地区的c1.medium 在Linux/Unix(Amazon VPC)系统运行的价格历史
Table 2 Price history of c1.medium at us-east-1a zone with Linux/Unix OS

价格时间点价格实例类型操作系统地区2015-09-07T22:08:09+02000.0162c1.mediumLinux/UNIX(Amazon VPC)us-east-1a2015-09-06T22:07:56+02000.0162c1.mediumLinux/UNIX(Amazon VPC)us-east-1a2015-09-05T22:05:56+02000.0162c1.mediumLinux/UNIX(Amazon VPC)us-east-1a2015-09-04T22:02:47+02000.0162c1.mediumLinux/UNIX(Amazon VPC)us-east-1a2015-09-04T21:56:04+02000.0161c1.mediumLinux/UNIX(Amazon VPC)us-east-1a2015-09-04T21:49:24+02000.0162c1.mediumLinux/UNIX(Amazon VPC)us-east-1a2015-09-04T19:39:49+02000.0161c1.mediumLinux/UNIX(Amazon VPC)us-east-1a

在清洗数据的过程中,还显示了数据产生或结束的时段.比如实例cc1.4xlarge Windows us-east-1b在9月28号以后就不再产生数据了,然而,实例i2.4xlarge Windows us-east-1a从2015年11月12日开始才产生数据.

结果,截至2016年11月19日下载的数据集,共从中整理出了1053种实例的价格历史.

图1 来自美国东部数据中心运行在Linux/Unix系统上的c1.medium实例价格轨迹图例Fig.1 Plot of price history from c1.medium instance at us-east-1a zone with Linux/Unix OS

在获得全年价格历史以后,我们仍然无法直观地判断价格变动的历史.因此,对其可视化,绘制走势图,将会直观反映出实例在一年以内的变化历史,这将有助于判断云服务的类型,直观显示它的特点.图像中,时间为横轴,价格为纵轴.走势图形式如图1所示.

绘图程序会自动根据价格的最大值和最小值来决定图像坐标轴的数据大小.可视化以后,可以对数据的走势有更为直观的判断和了解.

另外,实现了用哈希码判断图像相似度的比较算法[17],可以通过汉明距离判断两个实例是否相似.哈希值表征为64位01数字序列.一般认为,汉明距离大于10,可以直接判断这两个图像不相似,而如果汉明距离小于5,可认为两张图像非常相似.

5 KNN分类算法

在绘制了上文中图中所示的走势图之后,可以发现,许多实例有着相同的走势历史.因此,对实例价格走势进行进一步的分类,可以将某一些可以分成一类的云服务特点归纳起来,以求找到比较典型的特点.[18]KNN是一种监督学习算法,因此需要先验知识,首先,需要对实例手工标注标签.

参照实例图像走势情况,给1053个数据中的48个做了标签,共有7种标签,每种6至8个,由于共析出1053条数据,因此人工判断是否相近会有一定误差,在这里,笔者选取了认为走势最为典型的实例并将其划分为可确定的7种类型.在选取典型实例作标签以后,使用哈希码计算了汉明距离,以确认类中各实例确实相似.典型类别的走势缩略如下:

A类:后三个月显著增长且波动稳定;B类:后三个月显著增长且波动剧烈;C类:有少量稳定出现的固定值;D类:无固定峰值,波动剧烈,但是存在稳定变化的区间;E类:波动剧烈且不存在稳定变化的区间;F类:价格呈段式变化;G类:固定峰值出现频率极高.典型类别与其代表图像如图2所示.根据已标注标签样本测试数据的分类.通过交叉验证,可以证明,在K=15的情况下,准确度可以达到85%以上.每个类别含有实例数量表格如表3所示.

表3 每个类别含有实例数量
Table 3 Instance type and amount

实例类别实例数量A182B220C273D81E47F3G199

可以发现,测试的结果中,F类别仅有3个实例.然而,数量比较多的实例类别大概为200-300左右.这显示出,人工标注的某些类别可能含有的实例较少,而类别含实例数量较多的,很有可能可以从中细分出一些子类别.

6 k-means聚类算法

KNN分类算法需要获得先验知识,属于一种监督学习算法.在KNN分类算法中,我们需要对数据标注分类,这会产生一些由于人为造成的误差.与分类算法不同的是聚类算法.聚类算法不需要人工为样本标注标签,是一种将相似点集合到一起的无监督学习算法.

图2 典型类别与其代表图像Fig.2 Classical types and trend plots

可以很好地避免掉由于人为产生的误差.k-means算法作为最经典的一种聚类算法,结构简明,运行效率高,且可以展现出较好的聚类结果.

表4 K-means 每种
类别实例数量统计
Table 4 Result of k-means
and instance amount

实例类别实例个数02051927310041085566103721181299411084

在确定k值时,使用簇半径和平均质心距离作为判定标准,测试k值从2到30,对于每个k值做了50次k-means计算,取平均值作为判断依据,结果显示如表4所示.

随着k值的增大,类别的数量会越来越大.另一方面,平均质心距离则会不断减小.为了权衡平均质心和k值的关系,计算了平均质心距离的下降速度.可发现,从k=2开始平均质心距离迅速下降,在k=11时下降到0.874左右,在此期间,质心距离差从0.27迅速下降到0.05左右.之后,质心距离差下降速度非常慢,基本维持在0.01-0.02左右.因此,本次研究中,k-means算法中的k值取11.聚类的每个类别含有的实例组合购买方式的数量如表5所示.

受机器学习中Boosting方法启发,使用多种分类器,然后采用投票的方式,最终将多种分类器整合到一起以加强分类效果.两种方法比较,可以选取分类结果的交集,通过投票法获得最终结果,这部分类型便会是潜在的典型价格类别.

7 补齐法

竞价型云服务产生价格的时间点不完全相同,因此直接计算价格分类会产生一些误差.有学者在研究时间序列时按照周或日的时间单位,如果云服务产生价格的时间点全部相同,那么就能够更加精准地判断云服务的分类.使用补齐法,将没有价格的时间点用变化之前的价格补充进去,就能使得不同的云服务在相同的时间点上都有价格.

按照亚马逊对动态定价云服务的使用规则说明,在价格再次浮动之前,用户可按照当前价格购买云服务.换句话说,我们在补充的虚构数据采集时间点上的价格可以视作下一次变动之前的“当前价格“,亦即上一次变动后一直没再改变的价格.这一补充数据的处理方法除了带来数据量的增加,对真实时间序列上的价格数据走势并未做任何本质上的改动,故此应该是可以接受的.这一目的是为了能够让不同云服务实例的价格数据在相同的时间序列上严格公允地对比.

此外,经过分析和浏览已获得的价格历史数据,发现存在着不同的实例,他们的价格范围不同但是变动趋势相似,因此也将被归为同一类.为此,在KNN算法中,可用补齐后的数据做差,以标准差做为判断样本远近的条件.

由于全年数据量达到10G以上,因此在测试程序之初只使用了2016年11月18日的价格数据.从中发现,即使是以天为单位做计算,仅对两个实例补齐,使用标准差做分类判别依据时,计算时长仍然可达到16小时以上.然而,如果仅以天作为样本单位,那么全年的数据将会失去其本身的全局意义.

表5 K-means 最佳k值选择测试结果
Table 5 Determine the optimal number of clusters in a dataset

k值平均质心距离类簇半径k值平均质心距离类簇半径k值平均质心距离类簇半径21.78596277.422658376120.8579416445.062190141220.6950251034.40473745431.5109948526.704772864130.8314372424.855551549230.6960980584.30238814841.2726391586.388680257140.8185823224.791342623240.6825492754.23618649751.2491980255.84864931150.8022433464.463512342250.6582042414.1693276261.1322707835.66575769160.8024003724.558108948260.6613133854.18726427471.0570068845.615079648170.7606917494.596851188270.6423600563.93589368981.0108023795.393959469180.7527539784.576849456280.6429504124.23576851690.9614493755.225730334190.7473217854.364603997290.6346306864.137234481100.9098293215.165907359200.7299064874.425607615110.8741819515.09299484210.7091923044.519128251

对于聚类算法的数据,应对全局进行补齐,可以推测,其运行的时间更长.测试全局补齐程序仅使用了从2016年1月1日至2016年1月7日一周的数据.测试以后发现,测试时长过长,总时间点数量达到了24万个,占到一周时间点总数(60万)的大约三分之一.

在测试的过程中,还计算了相同的时间点.从中发现,即便是肉眼可判断为相似的实例,其产生价格的时间点相同度也非常低.测试挑选了四个实例做测试(c1.mediumSUSE Linux(Amazon VPC)us-east-1a实例、c1.mediumSUSE Linux(Amazon VPC)us-east-1b实例、c1.mediumSUSE Linux(Amazon VPC)us-east-1c实例以及c1.mediumSUSE Linux(Amazon VPC)us-east-1e).这些实例是经过人工挑选的相近实例,经计算,对应的标准差极小但重复时间点个数占比仍不足20%.因此补齐法在理论上可行,但由于工程上计算时间过长,所以当前可行性不大.为解决该问题,可以压缩价格基本不变的区间,避免补齐带来的大量重复数据.只对价格变动大的部分进行价格在时间维度上的补齐.

综上,通过补齐法可分类,但由于时间过长,因此现阶段虽然具有理论可行性,但是其算法却需要优化.

8 数据特点分析与总结

实验所使用的数据来源于亚马逊的官方网站,从2015年9月开始,到2016年11月为止.在测试的过程中,从原始数据、衍生数据以及经过计算得到的数据中,发现了许多特点和规律.本节将着重描述从数据本身发现的规律和特点.

从这些规律中,可以发现:

1)价格变化更频繁,产生得更密集;服务种类不断增加,由2015年11月的879个增加到2016年11月的1050个.如表6所示.

2)朴素数据统计,[15]从数值统计表中可发现,不同实例有相似值.例如相同的最值、中位数,或是相近的方差,这说明亚马逊官方很可能设置了固定的价格.

3)许多实例存在着“固定价格”,这里是指:某个固定的价格出现多次.可以在许多其他的实例中发现相同的现象这个固定值可能是最高值,或者是最低值,或者是某个中间值,它会在一段或多段时间内大量反复地出现.

表6 文件大小和实例数量统计表
Table 6 Size of source files and types amount

序号起始时间数据集大小/MB实例数量/个12015.09.23256.287922015.10.26510.897232015.12.06596.597242016.01.2071697252016.02.17854.897162016.04.181177.697272016.06.041546.2498182016.06.151628.1698192016.06.161638.4981102016.08.032539.521041112016.09.214300.81050

4)产生价格的时间点则不同,从现在的价格数据历史可以看出,有一些实例的价格变动的时间间隔已经大大缩小,并且越来越趋于无规律化;然而,有一些实例的价格在全局时间内甚至没有变化过.有一些实例的价格变动的时间间隔已经不是过去的一个小时或两三个小时,而是变得更加密、更加无序.

5)计算每个月的平均价格发现,许多实例的价格数据在很长一段时间内都维持在固定价格或有小幅波动:在2015年11月至2016年8月间,有相当一部分实例的价格没有发生变化,这说明在2015年11月左右,以及2016年8月左右,亚马逊对竞价型实例的定价策略做了一定的调整.在2016年9月至2016年11月期间,可以发现,价格区间明显变小,数据量明显增多.许多实例的价格开始升高.这说明,在2015年11月和2016年8月亚马逊很有可能修改了其定价策略.

9 总 结

经过对数据整理、合并、剔除重复数据,现有程序可以完美地整合数据,并可以将从亚马逊官方网站上新下载的数据做新一轮的整合.同时,可以根据实例历史数据绘制对应的价格变动历史走势图像,通过图像相似度判定的算法判定两个实例是否相似.另外,还计算了月平均数据,从中发现,亚马逊公司在2015年11月左右和2016年8月左右对其价格政策做出了调整.

亚马逊目前的动态定价云服务共有1053种实例类型,其历史价格走势多数杂乱无章参差不齐,故此在未来工作中对全部云服务实例进行研究是不现实的,对这1053种云服务实例的价格走势进行分类,可以帮助我们挑选出最典型的、最具有代表性的价格数据,参与到下一步基于历史数据的云服务价格预测及定价模式的挖掘分析工作中.

现在已有的两种分类聚类算法,KNN分类算法和k-means聚类算法可以对实例进行划分类别,分类算法需要人工判断部分样本类别并对剩余样本判断分类,聚类则根据样本自身性质将样本适当地划分成不同的类别.两种方法并行实施,采用Boosting算法,可以对云服务的分类结果进行分析,使用多种分类器,采用投票的方式,最终将多种分类器整合到一起以加强分类效果.选择两个分类中都会产生的类别,那么这部分一定就是最典型的类型.

然而,每种云服务购买组合产生价格的时间点都不同,这会对分类结果的判断产生一定偏差.因此,引入了补齐法和以标准差作为判断样本距离的标准,能够让不同的服务有相同的时间点,减少计算的误差.设计实现的补齐法虽然在理论上与实践上均可行,但由于补齐法产生的时间点过多,所以运行时间过长,在工程上缺乏可建设性.

如果能够对数据补齐算法进行优化,将会使看起来没有关系的价格数据显示出更多的相似之处,可以减少因为时间点不一致而带来的误差.

未来将继续以亚马逊竞价型云服务的价格历史作为样本,结合云计算和机器学习算法知识进行深入研究.我们将继续深入分析价格历史、并相应地展开预测模型的构建等相关工作.我们将着手于在下一步的工作中分析典型的价格轨迹,运用统计分析以及建模的方式获得其价格的变动特性与特征.进而,通过回归测试或其他方法拟合价格的生成算法,以期对亚马逊竞价型云服务的价格做出一定的预测,并给出一个确切的预测准确度.