马尔科夫决策过程在移动端云存储策略中的应用

　　摘要: 针对传统移动端云存储系统数据量急剧增加时对存储效率产生严重影响的实际情况，从理论上对移动端云存储的存储状态进行分析，提出了一种基于马尔科夫的移动端云存储策略，该策略以节点存储代价的量化描述为基础，引入马尔科夫决策理论并结合存储节点的状态转移，选择最优存储节点实现移动端云存储访问。通过仿真实验对该存储策略进行了验证，结果表明，当数据大小发生改变时，该存储策略能够准确预测并将数据实时调度到合适的存储组机群的存储节点上，有效降低因数据大小不同而导致存储效率降低的影响。

　　关键词: 马尔科夫; 存储状态; 云存储策略; 存储代价; 决策理论; 状态转移

　　0 引言

　　传统移动端云存储系统的存储密度不大，综合存储效率比较低，不能很好地适应各种不同的应用环境，且不能保证云数据的完整性和机密性，因此将敏感数据直接存放在云上是非常危险的。云存储系统中的存储过程近似为马尔科夫过程，该文提出一种基于马尔科夫的云存储策略以实现移动端可靠安全地存储，从概率的角度来衡量各个存储节点的存储代价并综合调度，选择最优存储节点实现云存储访问。

　　当移动终端发出请求时，基于马尔科夫的云存储策略选择存储代价最优的存储节点能够有效节省时间，提高存储效率，同时保证系统的负载均衡。基于马尔科夫的云存储策略改进优化了传统云存储系统的不足，提出可靠性模型，最后通过一系列仿真实验验证该文提出的基于马尔科夫的云存储策略具有较高的可靠性。

　　1 移动端云系统副本策略

　　传统的移动端云存储系统使用多副本机制，当移动终端发出请求时选择最近的副本，最近的节点是指该节点存储代价最低。云系统副本策略包括动态副本策略( Dynamic Replication Strategies，DRS) 和静态副本策略( Static Replication Strategies，SRS) 。静态副本策略指的是副本个数、放置的位置从创建开始到数据失效期间都是固定不变的，而动态副本策略指的是系统运行中根据系统性能、负载等各种因素的变化，实时调整副本个数及放置位置等，包括小文件动态副本策略( Small File Dynamic Replication Strategies，SFDRS ) 和大文件动态副本策略 ( Large File Dynamic Replication Strategies，LFDRS) 。

　　1. 1 小文件副本策略

　　不超过 10 MB 的文件定义为小文件，小文件副本策略采用 SQLServer 关系数据库。接收到移动终端传来的文件后，调度机群会先判断其大小，一旦确认是小文件，则交给关系数据库机群处理，并且将文件相关属性存储到数据库表中。数据库机群动态选择最优节点，即将机群中负载最轻的数据库服务器选出来存储文件，并保存一份副本确保数据的可靠性。文件所存放的数据库服务器 IP 地址将被存储到主服务器中，查询时需先从主服务器获取文件存放的服务器 IP，然后再与数据库服务器交互。小文件存放处理模式

　　1. 2 大文件副本策略

　　当文件超过 10 MB 时称之为大文件，大文件副本策略采用存储组机群处理，存储组机群系统采用全连接网络，

　　存储组机群的存储空间统一编址且为环状结构。通过虚拟连续存储空间的方式，存储组机群可以抵消不同 PC 机间设备性能的不同。使用哈希算法 - 信息摘要算法 5( Message - Digest Algorithm 5， MD5) 实现地址转换，通过 MD5 算法将实际物理地址处理转换为 32 位信息串，然后再存储到虚拟连续地址中，抵消设备间性能的不同。MD5 算法将地址转换映射到存储组机群的虚拟存储空间环中，将数据存储到第一个被映射的 PC 设备中，并且备份到相邻的 2 个 PC 设备上。

　　存储组机群采用 PC 作为存储介质，PC 可靠性不高，有时还会存储失效，因此需要存储副本确保数据可靠。当某节点故障时，相邻节点会及时修改路由信息并将该设备存储的所有信息进行重新备份。

　　2 基于马尔科夫决策的移动端云存储策略

　　在传统的云存储副本策略中，只有主副本错误了才请求备用副本，不考虑地域，极大地影响存储速度。将马尔科夫转移概率应用到移动端云存储策略，从概率角度衡量各个存储节点的存储代价，预测某时刻云存储策略的存储概率，选择最优存储节点实现数据存储。

　　基于马尔科夫决策的移动端云存储策略( Cloud Storage Strategy Based on Markov，CSSBM) 首先提出对应的存储状态空间转移表达; 然后根据云存储系统的历史数据样本得到状态转移概率矩阵。利用状态转移概率矩阵和当前收敛的存储状态矩阵，快速预测未来某个时刻云系统存储状态的存储概率实现存储。

　　2. 1 有限状态空间及状态分布

　　在云系统中，存储组机群中的服务器叫做存储节点，每个存储节点都可以存储大文件、中文件以及小文件。由于存储组机群中存储节点的硬件性能、负载情况以及网络链路状态都不同，每个存储节点存储大、中、小 3 种不同类别的数据所耗费的成本也不同，导致每个存储节点存储不同大小文件的存储代价不同，一般选择代价最低的存储节点。

　　根据以上分析，将存储组机群中存储节点存储 3 种不同大小的数据的存储过程视为离散状态空间 S，数据存储过程中下一个存储节点的选取只与当前存储节点的存储代价有关，因而云系统的数据存储过程符合马尔科夫链的特征。该文所提出的云存储策略中，状态空间 S 表示为以下 3 种:

　　1) 状态 1( 小文件状态)

　　在小文件状态下，选择存储组机群中存储小文件的最优存储节点，实现数据存储。

　　2) 状态 2( 中文件状态)

　　在中文件状态下，会从存储组机群中选择介于小文件和大文件之间的最优存储节点，实现数据存储。

　　3) 状态 3( 大文件状态)

　　在大文件状态下，会选择存储组机群中存储大文件的最优存储节点，实现数据存储。

　　基于马尔科夫的云存储的状态空间定义为 S = { s1，s2，s3 } 。si ( i = 1，2，3) 分别表示机群中各个存储节点实现小文件、中文件和大文件存储的存储代价。

　　进行云存储策略的研究，存储方案状态的划分以适中为宜。显然，该文定义的存储组机群存储大、中、小文件 3 种状态比较简捷，能很好地满足云系统中对数据存储的要求。

　　状态分布 R 为某一存储节点实现数据存储的存储代价，根据存储节点在大、中、小 3 种不同状态下的存储代价，得到 ti时刻云系统的存储状态分布

　　2. 2 状态转移概率矩阵

　　根据前文分析可知，存储组机群中的每个存储节点均有存储 3 种不同大小文件的存储代价，若云系统中某个存储节点存储大、中、小文件的综合存储代价越高，使用该节点存储数据的可能性越小; 相反，存储大、中、小文件的存储代价越小则被选中的可能性越大。

　　2. 3 基于 Markov 云存储策略算法

　　对于数据在不同节点存储的存储代价，获得系统当前时刻的存储代价矩阵，即系统的状态分布矩阵

　　2. 4 云存储策略的可靠性分析

　　假设系统可靠性为 A，采取不同存储策略实现存储的时间取反并经过归一处理后的值为 Aj ，依据马尔科夫决策不同节点实现数据存储的存储代价经过归一处理后的值为 Ak，云存储的存储状态数为 n，则系统的可靠性模型用式( 6) 表示:

　　A =[1 –( 1 - Aj ) n ][1 –( 1 - Ak ) n ] ( 6)

　　从可靠性模型得出当时间 t→∞ 时，云系统的存储代价也趋近于某一稳定值，此时存储策略的状态趋于稳定，当 Aj和 Ak的值越接近于 1，且存储状态数 n 越大，则云存储策略越可靠。

　　3 实验与结果分析

　　论文使用 python 语言验证 CSSBM 存储策略算法。用蒙特卡罗模拟 8000 次样本，模拟时间间隔为 300 个，统计存储状态在这些间隔内的分布及相邻时间间隔存储状态的变化情况，得到存储策略的状态转移概率矩阵

　　通过存储状态分布矩阵 R( i) 可快速选出存储代价最低的节点以实现数据存储。系统对同等大小的文 件，当采用不同的算法 SFDRS，LFDRS 或 CSSBM 分别进行处理的时间数据。

　　SFDRS 算法对比 LFDRS 存储时间相对较短，对于文件传输总的时间损耗和用户体验影响不大。 LFDRS 存储耗时相对较长，会对系统造成较大的额外时 间 开 销。CSSBM 对文件存储的时间相对 SFDRS 没有明显增加，存储效率较高。

　　利用前面提出的可靠性模型式( 6) ，结合表 1 中对同 等 大 小 的 文 件，采用不同的策略 SFDRS、 LFDRS 或 CSSBM 算法进行数据存储，对时间取反并经过归一处理后的值 Aj越接近 1，同理经过归一处理后的存储代价 Ak也越接近 1，且存储状态数目越多，系统的可靠性也就越高。连续采样移动端 1 小时内使用不同策略的存储时间和传输速率，得到不同策略的可靠性对比图，如图 5 所示。

　　通过对图 5 中的数据对比发现，使用 SFDRS 算法存储系统的可靠性值基本维持在 1，系统可靠性相对较高，即使用 SFDRS 存储数据对于文件传输和用户体验影响不大。LFDRS 算法耗时相对较长，且系统可靠性值抖动较大，使用 LFDRS 存储数据时系统可靠性较低。CSSBM 存储数据时间相对 SFDRS 没有明显增加，可靠性的值也维持在 1 左右，可见，使用 CSSBM 存储数据，系统的可靠性相对较高。

　　通过仿真实验验证了基于马尔科夫的云存储策略具有较高的可靠性，该存储策略能够依据存储状态矩阵和状态转移概率矩阵实现存储状态预测，将数据实时调度到存储代价最低的存储节点实现数据存储，有效节省时间，降低因文件大小不同而导致存储效率降低的影响。

　　4 结语

　　该文用马尔科夫解决云系统的存储调度，预测数据的安全存储。文章首先将云系统的存储状态划分为 3 个，然后分阶段使用马尔科夫决策，并根据存储节点的存储代价获取当前时刻的存储状态矩阵，在足够多样本数量的支持下，统计出状态转移概率矩阵，快速预测未来某时刻云系统的存储状态概率，选择最优存储节点实现数据存储。最后通过仿真实验表明当数据大小发生改变时，该存储策略能够准确预测并将数据实时调度到存储代价最低的节点，有效降低因数据量大小不同而采用相同的存储方法造成的影响，验证了将马尔科夫决策应用在移动端云系统中的存储策略具有较高的可靠性。相关论文还可参考：浅析云计算与云存储技术研究

　　参考文献:

　　[1] 张迪，朱立谷，侯振宇，等. 基于 WEB 的移动端云存储技术研究[J]. 计算机工程与应用，2010，46( 36) : 66.

　　[2] Iliadis I，Sotnikov D，Ta - Shma P，et al. Reliability of georeplicated cloud storage systems[C]. In: 2014 IEEE 20th Pacific Rim International Symposium on Dependable Computing，2014: 169.

　　[3] 徐婧，杨寿保，王淑玲，等. CDRS: 云存储中一种代价驱动的自适应副本策略[J]. 中国科学院研究生院学报， 2011，8( 6) : 759.

　　[4] 冯登国，张敏，张妍，等. 云计算安全研究[J]. 软件学报，2011，22( 01) : 71.

　　[5] 牛德华，马建峰，马卓，等. 基于属性的安全增强云存储访问控制方案[J]. 通信学报，2013，34( Z1) :

《马尔科夫决策过程在移动端云存储策略中的应用》

上一篇：计算机硬件虚拟仿真实验平台的建设与设计

下一篇：并行计算实验课程建设的实践与探讨