一种基于HashGraph的NoSQL型分布式存储因果一致性模型 - 谭坚, 罗巧玲, 王丽一, 胡夏晖, 范昊, 徐占.pdf
免费下载
计 算 机 研 究 与 发 展
DOI
:
１０．７５４４∕issn１０００Ｇ１２３９．２０２０．２０１９０６８６
JournalofCom
p
uterResearchandDevelo
p
ment ５７
(
１２
):
２７０３ ２７１６
,
２０２０
收稿日期
:
２０１９
－
０９
－
１９
;
修回日期
:
２０２０
－
０２
－
１７
基金项目
:
国家自然科学基金青年科学基金项目
(
６１８０２１０６
)
Thisworkwassu
pp
ortedb
y
theNationalNaturalScienceFoundationofChinaforYoun
g
Scientists
(
６１８０２１０６
)
．
通信作者
:
王彦骉
(
w
y
bhbu＠１６３．com
)
一种基于
HashGra
p
h
的
NoS
Q
L
型分布式存储因果一致性模型
田 俊 峰
王 彦 骉
(
河北大学网络空间安全与计算机学院
河北保定
０７１００２
)
(
河北省高可信信息系统重点实验室
(
河北大学
)
河北保定
０７１００２
)
(
t
j
f＠hbu．edu．cn
)
CausalＧPdh
:
CausalConsistenc
y
ModelforNoS
Q
LDistributedDataStora
g
eUsin
g
HashGra
p
h
TianJunfen
g
and Wan
g
Yanbiao
(
Schoolo
f
C
y
berSecurit
y
andCom
p
uter
,
HebeiUniversit
y
,
Baodin
g
,
Hebei
０７１００２
)
(
Ke
y
Laborator
y
on Hi
g
hTrustedIn
f
ormationS
y
stemin HebeiProvince
(
HebeiUniversit
y
),
Baodin
g
,
Hebei
０７１００２
)
Abstract Thecausalconsistenc
y
ofdatainadistributedenvironmentmeansthatwhendata with
causalde
p
endenceisu
p
dated
,
thede
p
endenc
y
metadatainotherdistributedco
p
iesmustbeu
p
dated
simultaneousl
y
,
while meetin
g
hi
g
her availabilit
y
and
p
erformance re
q
uirements．To solve the
p
roblemofusers
p
utlatenc
y
andu
p
datin
g
visiblelatenc
y
inexistin
g
results
,
basedonthedatacenter
stablevectors
,
combinedwiththe
p
rinci
p
leofh
y
bridlo
g
icalclocksandtheHashGra
p
h
,
we
p
ro
p
ose
theCausalＧPdh model．Toreducethecommunicationoverheadcausedb
y
exchan
g
in
g
databetween
re
p
licates
,
p
artialstabelvectorsre
q
uired b
y
s
y
nchronizin
g
dataand Hash valueasthe messa
g
e
si
g
naturesareusedinsteadofthewholedatacenterstablevectors．The
p
rinci
p
leofvirtualvotin
g
in
HashGra
p
hisusedtoim
p
rovethe
p
rocessofs
y
nchronizin
g
thelatestentriesineachdatacenter．Just
likeGossi
p
aboutGossi
p
:
each
p
arentnodealsorandoml
y
exchan
g
esthelateststatus
,
andu
p
datesthe
clockre
g
ularl
y
．This
p
ro
g
ressreducesthetimeofvirtualvotin
g
betweenthere
p
licates．Finall
y
,
itis
verifiedb
y
ex
p
erimentsthattheCausalＧPdhmodelnotonl
y
doesntaffectthethrou
g
h
p
utoftheclient
q
uer
y
,
butalsoreducesthewaitlatenc
y
ofusers
p
uto
p
erationb
y
２０．８５％ whentheclockskewis
severe．Whenthe
q
uer
y
isam
p
lifiedinthes
y
stem
,
theres
p
onsetimeofre
q
uestisreducedb
y
２３．３７％．
Ke
y
words dataconsistenc
y
;
causalconsistenc
y
;
distributedstora
g
e
;
HashGra
p
h
;
h
y
bridlo
g
ical
clocks
摘
要
分布式环境中的数据因果一致性指的是对具有因果依赖性的数据进行更新时
,
须同步更新其他
分布式副本中的依赖性元数据
,
同时满足较高的可用性和性能需求
．
为解决现有成果中更新可见延迟较
高的问题
,
在数据中心稳 定向 量 的基 础 上
,
结合 混 合逻 辑 时 钟 和
HashGra
p
h
原 理
,
提 出 了
CausalＧPdh
模型
．
使用部分向量和校验值作为消息签名代替了所有向量
,
并且借鉴
HashGra
p
h
的原理
,
改进了各个
数据中心同步最新条目的过程
,
各个父节点随机与其他父节点同步最新状态
,
从而降低了虚拟投票所使
用的时间
．
最后通过实验验证了
CausalＧPdh
模型不仅没有影响客户端的吞吐量
,
而且在时钟偏移较严重时
降低了
２０．８５％
的用户
PUT
等待延迟
,
在系统中存在查询放大的情况时
,
PUT
响应时间降低了
２３．２７％．
关键词
数据一致性
;
因果一致性
;
分布式存储
;
Hash
图
;
混合逻辑时钟
中图法分类号
TP３９２
分布式云存储是新一代数字时代发展的重要基
石
,
公有云服务商的数据中心部署在不同的地方
,
为
用户提供可扩展的计算
、
存储等服务
[
１
]
．
然而在 提供
高速
、
便捷服务的同时
,
保障分布式副本之间的数据
一致性
、
因果一致性就成了比较严峻的问题
．
在理想
的环境中下
,
副本中 所有 元 数据 的 即时 更 新在 其 他
节点中都立即可见
,
这种模型称为强一致性
．
但在分
布式存储环境下
,
不牺牲一定的可用性和性能几乎无
法实现
;
即使在没有对数据进行分区
、
分块存储
,
强一
致性的实 现 也有 着 极高 的 性 能 成 本
．
例 如
Guerraoui
等人
[
２
]
基于增 量更新 提出的
ICG
(
incrementalconＧ
sistenc
yg
uaranteesforre
p
licatedob
j
ects
)
方 案
,
在
牺牲通信开销和查询正确度的前提下提高了强一致
性的操作延迟
．
因此
,
许多系 统使用 最终一 致性来 保障用 户数
据安全
,
例如亚 马 逊的
D
y
namo
[
３
]
存储 平 台
．
该平 台
对用户数据可用性做出的唯一保障就是要求用户更
新最终实现一致
;
为了确保多个副本都收敛到相同的
数据状态
,
最终一致性的系统通常使用某种规则在多
个差异的副本状态中选择一个作为最终稳定状态
[
４
]
．
在
Twitter
、
微 博 等 社 交 软 件 或 大 型 网 站 应 用
中
,
最终一致性是最常见的数据一致性约束
,
其次便
是因果一致 性
,
如
Mon
g
oDB
数 据 库 就是 典型 的因
果一致性数据 存 储 产 品
．
因 果 一 致 性 是 一 种 中 间 一
致性模型
,
该模型只 在 系统 要 求可 见 的因 果 依赖 性
时
,
才要求保障记录用户事件的元数据的因果序
．
因
果序就是前后
２
个用户事件之间一种有依赖性要求
的发生顺序
,
有
２
个来源
,
一个是同一客户端中有前
后顺序的更新
,
另一个 是 不同 客 户端 中 对同 一 个值
的
２
次更新
[
５
]
．
为了实现数据因果一致性约束
,
分布
式云存储模型需要提供验证因果一致性依赖关系的
数据存取规则
．
具体来说
,
若用户要求某些元数据的
因果依赖性不可见
,
那么 系 统中 须 保留 一 个对 用 户
透明的变量
．
对 于 由 多 台 机 器 组 成 的 多 节 点 数 据 分
区来说
,
对因果依赖关系的校验就成了较难的问题
．
１
相关工作和主要工作
１．１
相关工作
因果一 致性可 以在客 户端与 服务端 分别实 现
,
例如
Zawirski
等人
[
６
]
提出 的 客 户 端 一 致 性 方 案
．
现
有的工作中
,
在服务 端实 现 因果 一 致性 的 解决 方 案
都有较大性能开销
,
例如
Llo
y
d
等人
[
７
]
在
２０１１
年提
出的
COPS
(
clustersoforderＧ
p
reservin
g
servers
)
模
型
,
Du
等 人
[
８
]
在
２０１３
年 提 出 的
Orbe
模 型 是 较 早
的因果一致性 数 据 存 储 模 型
．
该 类 模 型 会 对 用 户 当
前读取的值保持跟 踪
,
当客 户 端写 入 某个 新 的键 值
时
,
系统中对客户端 正 在写 入 的新 值 因果 依 赖关 系
定义为
:
该客户端读取过的所有值
．
在分区同步消息
中
,
这种明确的因果 依 赖关 系 校验 机 制要 求 极高 的
消息复杂度
,
导致分区间通信开销很大
．
１
)
近年来多 数 的 成 熟 研 究 方 案 采 用 物 理 时 钟
方法对元数 据和 分 区状 态 进行 同 步
,
如
GentleRain
是
Du
等人
[
９
]
在
２０１４
年提出 的方案
,
依赖物 理时钟
的紧密同步
、
分区之 间定 期 地进 行 通信 来 保障 用 户
数据的因果序
、
正确性和系统性能
．
但该模型依赖于
同步单调的物理时 钟
,
若底 层 协议 如 网络 时 钟协 议
(
networktime
p
rotocol
,
NTP
)
出现异常
(
例如时钟
偏移
),
就 会 导 致
GentleRain
对
PUT
(
用 户 向 服务
端写入新的数据
)
操作进行延迟等待
．
２０１６
年
Tomsic
等人
[
１０
]
提出的
Ph
y
siCSＧNMSI
是一种使用了物理 时 钟
,
但对 时 钟的 稳 定性 没 有要
求的数据因果 一 致 性 模 型
．
该 模 型 也 使 用 一 个 单 向
的标量对数据依赖 关 系进 行 检查
,
并且 提 供数 据 因
果一致性快照
,
保障用户写入事件操作的原子性
,
从
而避免
PUT
等待
、
操作冲突等问题
．
２
)
混合逻 辑时 钟
(
h
y
bridlo
g
icalclocks
,
HLC
)
是
Kulkarni
等人
[
１１
]
在
２０１４
年提出的一种基于物理
时钟和逻辑时钟的 时 钟同 步 方法
,
用于 在 分布 式 存
储系统中检查 因 果 依 赖 关 系
．
该 方 法 在 物 理 时 钟 基
础上
,
用
１
组向量来表示用户数据条目的时间戳
,
优
化了传统的物理时钟方法造成的
PUT
等待等缺陷
．
Oka
p
i
是
Didona
等人
[
１２
]
在
２０１７
年提出的一种使用
了混 合 逻 辑 时 钟 和 全 局 稳 定 向 量
(
g
lobalstable
vector
,
GSV
)
的因果一致性模型
,
类似于文献
[
９
]
中
的全局稳定时间
(
g
lobalstabletime
,
GST
),
该模型
设定一个状态值来校 验 和追 踪 当前 分 区最 新 条目
、
及其时间戳
,
时间戳 不小 于 该状 态 值的 元 数据 条 目
才被允许写入 到 分 区 内
．
该 系 统 要 求 用 户 的 查 询 操
作须约束在所有节 点 都同 步 完用 户 更新 之 后
,
因此
这个约束会大量增加
Oka
p
i
的更 新 可见 性 延迟
,
甚
至超过
GentleRain．
４０７２
计算机研究与发展
２０２０
,
５７
(
１２
)
of 14
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论