基于共享图和部分复制策略的分布式存储因果一致性模型

田俊峰，杨万贺，庞亚南，张俊涛

（1.河北大学网络空间安全与计算机学院，河北 保定 071002；2.河北省高可信信息系统重点实验室，河北 保定 071002）

1 引言

云存储是当今互联网服务的重要组成部分[1]。为了给用户提供高效率和可扩展的服务，云存储采取分布式数据存储方式，将数据中心部署在不同位置实现大数据存储，数据中心之间的数据一致性成为保证数据可用的关键[2]。

数据一致性一般分为强一致性和弱一致性[3]。在理想情况下，对任何数据的更新在其所有副本中立即可见称为强一致性。强一致性虽然有简单的语义，但是引发了高时延和不允许网络分区现象；多个节点的状态没有充分同步但仍可以处理读写操作称为弱一致性。弱一致性对数据的及时更新没有要求，难以为用户提供最新的数据[4]。因果一致性是介于强一致性和弱一致性中间的协议[5]，既可以有效解决高时延和网络分区等问题，也能保证数据的及时更新。

目前，基于因果一致性协议的模型成为构建地理复制数据存储中有吸引力的模型[6]。在地理复制数据存储中，分布在不同地理位置的数据中心通过网络时钟协议（NTP,network time protocol）更新当前的节点时钟，不同数据中心利用数据复制策略完成数据同步[7]。Agrawal 等[8]对分布式存储系统中的数据复制策略进行了分类，详细阐述了地理复制模型中的数据一致性方法，数据复制策略分为完全复制策略和部分复制策略。

基于完全复制策略的因果一致性模型要求每个数据中心都存储完整的数据集，本地数据中心写入数据需要向其他所有远程数据中心同步数据[9]。例如，文献[10]模型在完全复制策略的基础上，仅依靠单一标量时间戳实现对因果关系的追踪。文献[11]提出通用稳定向量和混合逻辑时钟相结合的全局稳定策略，提高了模型的吞吐量。文献[12]提出数据中心稳定向量和混合逻辑时钟相结合的全局稳定策略，解决了操作时延问题，降低了数据的更新可见时延。但数据中心稳定向量中的条目包含所有数据中心，增加了元数据开销，数据中心之间的同步开销大。

随着数据中心存储的数据量迅速增长，为降低数据中心之间的同步开销，基于部分复制策略的因果一致性模型得到了广泛应用[13]。基于部分复制策略的因果一致性模型要求每个数据中心存储完整数据集的子集，本地数据中心写入数据仅需向部分远程数据中心同步新数据。文献[14]模型中的每个数据中心都设置序列化器，利用时间戳对操作进行序列化，实现了操作的高并发性，并降低了操作时延。但是，该模型取消了数据中心之间的全局稳定。文献[15]模型利用共享树表示数据中心之间的拓扑关系和部分元数据作为标签，数据中心之间的所有更新操作都通过共享树和标签实现，提高了数据的可见性和系统的吞吐量，但是造成了数据中心之间的元数据传播开销。Xiang 等[16]提出的模型是对数据中心之间的全局稳定方法进行扩展，利用全局稳定时间戳和物理时钟的全局稳定策略实现模型的全局稳定性。该模型降低了元数据开销，提高了系统的吞吐量，但会产生操作时延，从而造成较高的更新可见时延。

为了有效降低操作时延并权衡元数据传播开销和远程更新可见性能，本文提出一种基于共享图和部分复制策略的分布式存储因果一致性模型（CCSGPR,causal consistent model for distributed data stores based on shared graph and partial replication strategy），利用共享图表述数据中心之间的拓扑关系，通过共享稳定向量和混合逻辑时钟相结合的全局稳定策略实现因果一致性。本文主要工作如下。

1) CCSGPR 使用部分复制策略实现分布式数据存储，每个数据中心存放完整数据集的子集，利用共享图表示数据中心之间的邻接关系，元数据通过同步消息和心跳信息传播，仅需在有邻接关系的部分数据中心传播，降低元数据传播开销和数据远程更新可见时延。

2) 提出一种全局稳定策略，该策略使用混合逻辑时钟标记操作的时间戳，可为新数据标记满足因果依赖关系的混合逻辑时间戳，避免写入数据操作时延。同时，在混合逻辑时钟的基础上提出了共享稳定向量，该向量仅由2 个时间戳构成，这降低了元数据开销，通过选取远程数据中心中时间戳的最小值为远程更新稳定的界限，避免读取数据操作时延。

2 背景介绍

2.1 基于部分复制策略的分布式模型

分布式模型采取多版本键值存储方式，一个键对应一个版本链，版本链包含键的多个版本，每个版本又包括键对应的值和元数据，写（PUT）操作会为键的版本链增加一个新版本，模型定期处理版本链中的旧版本[17]，数据存放在不同的数据中心，用户可以在不同的数据中心完成数据的写入、更新或下载[18]。基于部分复制策略的分布式模型如图1 所示。由图1 可知，完整数据集被分为m个子集，每个数据中心存储完整数据集的子集；每个数据中心由n个分区（服务器）构成，所存储的数据子集根据哈希函数按键分配到n个分区。服务器完成写入数据操作后，为对应的键创建一个新版本，新版本仅需同步到部分数据中心，数据中心之间通过点对点FIFO（first in first out）通道进行通信。

基于部分复制策略的分布式模型包含以下2 个基本操作。

1) PUT→(k,v)。PUT 操作将值v赋给键k标识的数据。若键k标识的数据存在，创建一个值为v的新版本；否则，创建一个键为k且初始值为v的新数据。

图1 基于部分复制策略的分布式模型

2) val←GET（k）。GET 操作返回键k标识的数据的值v，返回的值v需满足因果一致性。

2.2 因果一致性

因果一致性根据 2 个操作之间的happens-before 关系[19]定义，要求服务器返回的值与因果关系定义的顺序一致。对于2 个任意操作a1和a2，若满足以下条件，称a1因果依赖于a2，记作a1→a2。

1)a1和a2是同一线程中的操作，a1发生在a2之前。

2)a1为写数据操作，a2为读数据操作，且a2读a1写的值。

3) 存在其他操作a3，其中a1→a3，a3→a2。

定义1数据稳定性。若键k标识的数据可以被客户端c读取，且该数据的依赖项也可被客户端c读取，则称该数据具有稳定性。

定义2全局稳定性。分布式存储模型划定一个时间戳界限，该时间戳范围内的所有数据都具有稳定性，则称分布式存储模型在该时间戳具有全局稳定性。

定义3更新可见时延。键k标识的数据在其原始数据中心写入的时刻到该数据在此数据中心具有稳定性的时刻间隔称为更新可见时延。

定义4并发操作。存在2 个操作a1和a2，若a1既不因果依赖于a2，a2也不因果依赖于a1，则称a1和a2为并发操作。

定义5冲突操作及其处理规则。若a1和a2是对键k标识的同一数据进行并发写操作，则称a1和a2为冲突操作。冲突操作造成键k标识的同一数据产生2 个相互冲突的版本，相互冲突的版本按照不同的顺序同步到远程数据中心，这会造成数据中心之间的不一致性问题。基于部分复制策略的分布式模型使用最后更新为准（last-writer-wins）规则[20]处理数据的冲突操作。该规则规定，对于键k标识的同一数据的2 个写入操作，规定时间戳大的操作为后发生的，从而写入的值为时间戳大的操作所确定的值，若2 个操作的时间戳相等，则通过数据的写入数据中心ID 来解决冲突。

3 共享图

共享图（shared graph）是无权无向图，由顶点的有穷非空集合和顶点之间边的集合组成，记作Gs=（Vs,Es），其中Vs={1,2,3,...,n}为顶点集合；Es为边的集合，包含实线边和虚线边2 种，实线边集合记作E1（Gs），虚线边集合记作E2（Gs）。CCSGPR使用共享图表述分布式结构，顶点i∈Vs代表数据中心i；若数据中心i和数据中心j存在共享键，则存在实线边（i,j）∈E1（Gs），若存在客户端c可以访问数据中心i和数据中心j，则存在虚线边（i,j）∈E2（Gs）。

Ni表示与数据中心i存在实线连接的数据中心集合；Pi表示与数据中心i存在虚线连接的数据中心集合；Ki表示存储在数据中心i的键的集合；Kij=Ki∩Kj表示数据中心i和数据中心j的共享键。数据中心邻接关系的共享图如图2 所示。由图2 可知，共享图Gs由i、V1、V2、V3、V4、V5顶点组成，2 个数据中心的共享键标记在图中的实线边上，存在客户端c可以访问数据中心i、V2、V3和V5，因此，顶点i、V2、V3和V5之间存在虚线边，如Ni={V1,V4}，Pi={V2,V3,V5}，。

图2 数据中心邻接关系的共享图

在部分复制数据存储中，每个数据中心只存放完整数据集的任意子集，本文利用共享图表述数据中心之间的邻接关系，取消数据中心之间额外的同步开销，本地数据中心i写入新数据仅需向Ni集合中其他远程数据中心发送数据同步消息和心跳信息，若数据中心i存储的子集不包含待读取的数据，则向Pi集合中其他数据中心发送迁移操作。元数据利用数据同步消息和心跳信息实现传播，通过共享图拓扑结构，元数据不需要传播到所有的数据中心，同时，允许不同数据中心的服务器之间直接传播数据同步消息和心跳信息，降低元数据同步开销，以提供高吞吐量并降低远程更新可见时延。

4 全局稳定策略

目前，基于部分复制策略的因果一致性模型取消了传统的依赖项检查信息，通过NTP 实现服务器的同步，并利用全局稳定时间戳（GST,global stable timestamp）和物理时钟相结合的全局稳定策略实现模型的全局稳定性（见2.2 节的定义2）。

较目前的因果一致性模型，CCSGPR 提出了一种共享稳定向量和混合逻辑时钟相结合的全局稳定策略。首先，CCSGPR 用混合逻辑时钟（HLC,hybrid logical clock）代替物理时钟来跟踪时间的进展，完成时间戳的更新。混合逻辑时钟结合了物理时钟和逻辑时钟[21]，其时间戳t由一个物理组件t.p和一个逻辑组件t.l 组成，记作，其中t.p 是操作发生的物理时钟值，t.l 是追踪因果关系的计数器。因此，混合逻辑时钟充分发挥了两者的优势，既包含物理时钟自发递增的优点，也包含逻辑时钟易追踪因果关系的优点。在分布式模型中，由于距离差异等原因会造成节点之间存在一定的时钟偏差，存在2个PUT操作e1和e2，若e1“happens-before”e2，则e2因果依赖e1，受时钟偏差的影响，e2的时间戳小于e1的时间戳。为保证上述PUT 操作满足因果性，使用物理时钟的因果一致性模型发生操作阻塞，等待e2的物理时钟超过e1的时间戳，造成PUT 操作时延。CCSGPR 中e2不需要阻塞等待，直接完成操作并为e2标记te1.p

其次，记某数据的写入时间戳为t，因果一致性模型全局稳定的界限为T，规定仅当t

CCSGPR 在共享图拓扑结构的基础上，利用混合逻辑时钟有效避免了写操作时延，同时，共享稳定向量仅包含2 个时间戳，其根据选取最小值的原则，避免了读取操作时延，降低了元数据开销和数据中心之间的同步开销。

5 CCSGPR 协议

CCSGPR 协议是在分布式存储中稳定运行的通信协议，在操作满足因果一致性要求的前提下，为用户提供安全快速的写入、查询和存储服务。

5.1 元数据

图3 CCSGPR 中数据中心之间的心跳同步

元数据是描述数据属性的信息，用来支持历史数据、资源查找、文件记录、指示存储位置等功能，元数据开销和效率是衡量系统性能的重要指标，如Facebook 中，元数据比数据本身大，大型元数据会增加通信和存储开销[22]。分布式模型中，采取多版本键值存储方式，用d表示元组，该元组包括，其中，k是标识键唯一的ID；v是键对应的值；ut 是键的更新时间，即该数据的写入时间戳；sr 是d的源副本，即创建d的数据中心ID。

客户端c维持SSVc，SSVc仅由2 个时间戳组成。客户端c还维持依赖向量（DV,dependency vector）DVc，存储远程数据中心的依赖项，以保证后续操作满足因果一致性。

5.2 操作

CCSGPR 协议中包含6 个基本操作：GET 操作、PUT 操作、数据同步操作、更新共享稳定向量操作、心跳机制操作和迁移操作。

5.2.1 GET 操作

客户端c发起读取数据操作，存储该数据的服务器响应操作，如算法1 所示。其具体流程如下，客户端c发起请求，其中k为待读取数据的键，服务器接收到请求后，为确保安装最新快照使用SSVc更新。服务器选择键k的版本链中最新数据的版本，其中版本是本地数据中心写入或远程数据中心写入且更新时间戳小于中的时间戳。服务器把最新、键k对应版本的值v、源副本sr 和键k对应版本的更新时间戳ut 以GETREPLY 消息格式返回客户端c。客户端c接收GETREPLY 消息后，通过maxDV算法用更新时间戳ut 和源副本sr 更新DVc，用更新SSVc。

算法1数据中心m中客户端c的操作

5.2.2 PUT 操作

客户端c发起写数据操作，服务器响应写操作，如算法2 所示。其具体流程为，客户端c发起请求，其中k为待写入数据的键，v为键对应的值，DVc为依赖向量，记录客户端c的依赖项。服务器接收写数据请求后，用DVc值更新，使用update clock 算法（算法3 中的update clock on PUT 算法）更新，保证PUT操作满足因果关系。服务器为数据k的版本链中创建一个新版本，该版本的键为k，键对应的值为v，键对应的更新时间戳ut 为，键对应的源副本sr 为该数据中心的ID。服务器把最新、键k对应的更新时间戳ut 和源副本sr 以PUTREPLY 消息格式返回客户端c。同理，客户端c接收PUTREPLY 消息后，通过maxDV 算法用更新时间戳ut 和源副本sr 更新DVc，用更新SSVc。

算法2服务器响应客户端c的请求操作

5.2.3 数据同步操作

分布式存储系统由不同节点（数据中心）协同为用户提供存储、查询服务的平台，所以服务器完成PUT 操作后，其他数据中心要同步最新数据，即本地数据中心i写入新数据后，需向Ni集合中的数据中心发送同步数据信息。服务器间的数据同步如图4 所示。由图4 可知，数据中心i中的服务器发送Replicate 消息到其他数据中心（算法2 中的Replicate 算法），Ni集合中的数据中心接收Replicate消息后，服务器将数据的新版本增加到该数据的版本链中，更新其PV 中服务器对应的条目，即设置，完成服务器间的数据同步。

图4 服务器间的数据同步

5.2.4 更新共享稳定向量操作

一个数据中心内的服务器定期更新全局稳定向量SSV，规定每过θ时间间隔（θ的具体时间在仿真实验中设置），服务器之间彼此共享其分区向量PV，并计算SSV 为所有服务器的分区向量PV中的最小值（算法3 的更新共享稳定向量算法），从而确保该数据中心数据稳定界限内的数据在所有服务器内可读。

5.2.5 心跳机制操作

算法3服务器的时钟管理和心跳机制操作

5.2.6 迁移操作

如算法2 所示，客户端c发起读取数据操作，数据中心m作为响应客户端c操作的本地数据中心，若数据中心m存储的数据子集不包含待读取的数据，则根据共享图表示的数据中心之间的邻接关系，向Pm集合中其他数据中心发送迁移操作，完成读取数据操作。其具体流程为，数据中心m的服务器向Pm集合中的数据中心发送迁移操作请求，包括数据中心的ID 和；数据中心i中的服务器响应迁移操作请求，更新其共享稳定向量，完成迁移操作。

6 仿真实验与结果分析

6.1 对比分析

本节对现有的因果一致性模型进行对比分析，表1 为各因果一致性模型的比较。文献[10]模型和文献[11]模型基于完全复制策略，较文献[10]模型，文献[11]模型使用混合逻辑时钟与通用稳定向量相结合的全局稳定策略，降低了操作时延，但增加了元数据开销。文献[10]模型和文献[16]模型都使用物理时钟与全局稳定时间戳相结合的全局稳定策略，较文献[10]模型，文献[16]模型使用部分复制策略，有效降低了远程更新可见时延，但操作时延仍然较高。CCSGPR 基于部分复制策略，使用混合逻辑时钟与共享稳定向量相结合的全局稳定策略，在保证元数据开销小的基础上，有效降低了操作时延，定量对比结果详见以下实验内容。

6.2 仿真实验设置

CCSGPR 使用Java 实现，采用Berkeley DB 进行键值数据的存储和检索。Berkeley DB 数据库是以key-value 为结构的嵌入式数据库，既有关系型数据库中的完整 ACID（Atomicity,Consistency,Isolation,Durability）事务语义支持，也提供NoSQL中简单的数据库编程接口。为验证本文所提方法的有效性，在数据一致性HBU-Cluster 平台上实现分布式键值存储仿真实验，并与经典的基于完全复制策略文献[11]模型和基于部分复制策略文献[16]模型进行实验对比。数据一致性HBU-Cluster 平台是项目组为因果一致性测试设计的仿真平台，该平台为分布式键值存储管理框架，使用Google 的Protocol Buffer将数据因果一致性协议结构化，并集成Yahoo的YCSB（Yahoo! Cloud Serving Benchmark）基准测试模块作为性能测试工具。仿真实验中服务器的配置是Windows10 x64，Intel Core i5-4590，3.3 GHz，16.00 GB 内存，256 GB 固态磁盘存储。根据现有模型的性能测试，仿真实验采取传统的测试方法从模型吞吐量、操作响应时间和远程更新可见时延3 个方面进行定性对比。

根据实际基于Internet 的应用设置，在仿真实验中设置默认参数如下：数据中心数目为4，分区数目为6，读写比例为3:1。客户端依据uniform 记录选择策略访问分区数据，服务器之间采取NTP同步方法，每次实验前都同步时钟。CCSGPR 中的混合逻辑时间戳使用64 位编码，其中48 位设置为物理部分，16 位设置为逻辑部分，通过这些设置，混合时间戳可以编码多达216个逻辑事件，可以跟踪到微秒的物理时间，有效避免了由于逻辑部分已经达到最大值，但又必须增加其逻辑部分以保证因果一致性导致分区发生的阻塞等待。规定分区之间每5 ms 交换分区向量PV，若分区在1 ms 内未接收更新数据操作和同步数据操作，则该分区接收心跳信息。

6.3 吞吐量

吞吐量是单位时间内模型更新键值的总量，是衡量模型性能的一项重要指标。本节实验采取分别增加数据中心和分区数目的传统实验方式评估模型的吞吐量性能。

首先，分析数据中心数对模型吞吐量的影响，控制分区变量，设置每个数据中心的分区数为6，客户端向本地数据中心发送读写请求，数据中心之间定期同步数据。图5(a)描述了数据中心数2～12 所对应吞吐量的变化情况，随着数据中心数的增加，文献[11]模型的吞吐量变化明显，而文献[16]模型和CCSGPR模型的吞吐量变化较小。其原因是文献[11]模型基于完全复制策略，数据中心增加导致数据同步开销增大，从而降低了模型的吞吐量。文献[16]模型和CCSGPR 基于部分复制策略，仅模型中的部分数据中心同步数据，模型的吞吐量变化不大。当数据中心数为8 时，CCSGPR 比文献[11]模型提高了23.47%的吞吐量性能，比文献[16]模型提高了14.43%。与文献[11]模型相比，文献[16]模型和CCSGPR 使用部分复制策略，提高了模型的吞吐量。与文献[16]模型相比，CCSGPR 的全局稳定策略中使用混合逻辑时钟避免了操作时延，实现了更高的吞吐量。

表1 不同因果一致性模型的比较

其次，分析分区数对模型吞吐量的影响，控制数据中心数变量，设置数据中心数为4，改变数据中心的分区数量。图5(b)描述了分区数2～32 对应吞吐量的变化情况，随着分区数的增加，模型的吞吐量呈上升趋势，吞吐量性能提高了18.93%。与文献[11]模型和文献[16]模型比，CCSGPR 利用共享图表述数据中心之间的邻接关系，其分区向量PV 仅存储具有邻接关系的部分数据中心元数据，元数据通过同步消息传播，降低了元数据开销，实现了吞吐量的提升。

6.4 操作响应时间

根据传统测试操作响应时间的实验方式，本节实验分两部分来测量模型操作的响应时间，第一部分分区之间不设置时钟偏差，通过改变数据中心分区数的方式观察模型操作响应时间的变化情况；第二部分在一台物理设备上部署2 个虚拟服务器，以循环方式发送2 000 个操作请求，人为地控制服务器之间的时钟偏差值，准确分析服务器之间的时钟偏差对操作响应时间的影响。

图5 不同数据中心数和不同分区数的吞吐量

图6 不同分区数和不同时钟偏差的操作响应时间

图6(a)描述了模型中操作响应时间随分区数的变化情况，图6(b)描述了模型中操作响应时间随分区之间的时钟偏差值的变化情况。随着分区数和分区之间的时钟偏差值的增加，模型的操作响应时间也会增加，与文献[11]模型和CCSGPR 相比，文献[16]模型的全局稳定策略中使用物理时钟，受分区之间的时钟偏差影响大，产生了较高的操作时延。文献[11]模型和CCSGPR 的全局稳定策略中使用混合逻辑时钟，当分区之间存在时钟偏差时，可为操作提供符合因果依赖关系的时间戳，有效避免了操作时延。与文献[11]模型比，CCSGPR 的分区向量中仅同步共享图Ni集合中的数据中心所对应分区的元数据，受分区总数目变化影响较小，其共享稳定向量规定选取远程数据中心中时间戳的最小值，划定数据可读的下限，降低了11.72%操作响应时间。

6.5 远程更新可见时延

远程更新可见性时延指的是本地数据中心写入的数据同步到远程数据中心的时间间隔，在衡量模型性能中也占据着重要地位，即使只有几毫秒的时延，也会导致读取错误的过时数据而造成异常。

远程更新可见性时延是由服务器接收的最小时钟值决定，首先通过人为地控制服务器之间的时钟偏差值的方式，分析时钟偏差对远程更新可见时延的影响。其次服务器之间不设置时钟偏差，增加模型中数据中心数目，观察远程更新可见时延的变化情况。

图7(a)描述了远程更新可见时延随时钟偏差值的变化情况，图7(b)描述了远程更新可见时延随数据中心数目的变化情况。结果表明，远程更新可见性时延受服务器之间的时钟偏差影响，随时钟偏差值呈线性增长，其节点接收心跳信息值的数量随数据中心数线性增加，远程更新可见时延也会增加。与文献[11]模型比，文献[16]模型和CCSGPR 基于部分复制策略，远程更新仅在部分数据中心之间同步，降低了远程更新可见时延。较文献[16]模型，CCSGPR 降低了28.57%的远程更新可见时延。文献[11]模型中使用通用稳定向量UST，一个数据中心对应向量中的一个时间戳，远程更新规定所有远程数据中心都完成同步才可见，模型的远程更新可见性时延取决于本地数据中心同步到所有远程数据中心的时间，受数据中心数影响较大。文献[16]模型中使用全局稳定时间戳GST，模型的远程更新可见性时延取决于本地数据中心（即数据写入的数据中心）同步到其时延最大的数据中心的时间，数据中心数的增加会产生更小的全局稳定时间戳，从而造成远程更新可见时延增加。CCSGPR 中使用SSV，向量中仅包括本地数据中心的时间戳t1和远程数据中心的时间戳t2，模型的远程更新可见性时延取决于本地数据中心i与共享图Ni集合中数据中心同步的时间。由于CCSGPR 模型其SSV 中远程数据中心时间戳t2的选取最小值原则，随着数据中心数的增大，CCSGPR 的远程更新可见时延会略高于文献[16]模型。

图7 不同时钟偏差和不同数据中心数的远程更新可见时延

7 结束语

本文提出了基于共享图和部分复制策略的分布式存储因果一致性模型CCSGPR，该模型以部分复制策略为前提，利用共享图表示数据中心间的邻接关系。此外，利用混合逻辑时钟标记符合因果关系的时间戳，共享稳定向量选取远程数据中心心跳时间戳的最小值作为数据稳定的下限，以降低操作时延。通过数据一致性平台对CCSGPR 进行吞吐量、操作响应时间和远程更新可见时延验证，在降低操作响应时间的同时，权衡了远程更新可见性能和元数据开销。但CCSGPR 未考虑敏感数据恶意篡改等安全问题，实现可信约束下的分布式存储因果一致性模型是未来要做的工作。