AIGC在金融场景是如何落地的? 了解详情
写点什么

Dynamo 论文导读

  • 2019-11-25
  • 本文字数:2336 字

    阅读完需:约 8 分钟

Dynamo论文导读

Dynamo 是一个去中心化的 k-v 存储系统,它的定位是 high availability,无论是任何时候提供能够读写的服务。07 年至今,4000+ citation,被无数的人所关注,时间已经证明,dynamo 是分布式存储系统中的一篇经典论文。本文将带你解读 dynamo。

Dynamo

Dynamo 是一个去中心化的 k-v 存储系统,它的定位是 high availability,无论是任何时候提供能够读写的服务。对于一致性,dynamo 提供最终一致性,本文中也提到,在极少数情况下会出现一数据多版本的情况,dynamo 会返回给上层处理。尽管 dynamo 不完美,但是对于去中心化系统的优化值得好好研读。正如文中所说



07 年至今,4000+ citation,被无数的人所关注,时间已经证明,dynamo 是分布式存储系统中的一篇经典论文。

定位

1.简单的 k-v 接口,没有提供多数据结构的接口,最适用的场景是小 objects(usually less then 1 MB)场景。


2.适用于弱一致性要求的业务,不支持事物。


3.可以满足 99.9%的强时延请求。


4.没有做安全方面的需求。


整体来说本文主要考虑如何解决如何实现高可用的 k-v 存储,即使网络分割(network partitions)或者服务器 down 掉,依然能够提供存储服务。为了实现 always available,论文解决了如下问题:


1 Partitioning

为了实现便于扩展的特性,dynamo 选择了一致性哈希,但是由于一致性哈希负载不平衡的问题,这里引入了虚拟节点(virtual node)。


一致性哈希中将哈希空间均匀哈希成多个 token,这些 token 头尾相连组成一个环。然后将节点随机到哈希到环上的不同位置。



可以看出当前的节点分布并不均匀,例如 A 节点负责(B, A] 的哈希范围,B 节点负责(C, B]的哈希范围。由于 token 是均匀分布,(C,B]的范围显然要高于(B,A]的范围,最终大概率为 B 的负载高于 A 的负载。


引入虚拟节点之后,每一个物理节点被映射到环上的不同虚拟节点上。



如图 A 为物理节点,D 为物理节点映射出来的虚拟节点。同理,B 为物理节点, E 为虚拟节点。可以看出每个节点负责的范围相差不大,负载不均衡的情况被有效缓解了。


文中对于 dynamo 的分片策略进行了进一步的讨论:



此处介绍最优的策略 strategy 3。数据空间 Q 等分,S 为系统中拥有的节点数,Q/S 为每个节点拥有的分片数目。如果有新节点加入,其将会从其他节点接管分片,如果有节点离开将会把自己的分片交给其他节点负责。


个人理解最初加入了虚拟节点的哈希环上的分片是基本上均匀分布的,节点被哈希到环上的随机位置,但是 strategy3 中,每个节点负责的分片个数是固定的,但是分片的分布是任意的。这样的做法使得分片的分布更加灵活,对于节点添加删除,可以将整个分片交给任意的节点负责,同时可以保证保证负载的均衡。

2 High Availability for writes

Replica

dynamo 对于每一次写命令提供了多副本的策略,每一个 key 会对应到其 coordinator node(负责这个 key 的节点,通常是物理节点)。然后按照环上的顺序依次找到其顺时针连续的 N 个节点作为数据副本节点。



图中采用三副本策略 N=3,如果 B 点为 coordinator node,C,D 就为副本节点。

Replica consistency

对于读写操作,dynamo 提供了 get() 和 set() 操作。为了保证副本的一致性,dynamo 提供了一个类似于 quorum system 的协议。



R: 在一次读中必须参与的最小节点个数


W: 在一次写中必须参与的最小节点个数


N: 副本数

read/write process

读写流程中会先在 preference list 中找到应该处理该 key 的 coordinator,这个 list 中的 node 会尽量包含物理节点而不是虚拟节点。之后,对于读写流程需要除本节点外读 R-1 个节点的内容或者等待 W-1 个节点的写返回。


虽然在 2.2 中 dynamo 提出了一种写多副本的策略来保护数据的一致性,然而在一些极端情况下,冲突(版本分歧)还是会出现。本节提供了一种处理分歧的方式。


文中为更好的说明这一现象定义了 vector clock




考虑如下场景,clientA 写入 D1,接下来写入 D2 覆盖了 D1,然后 Sx 挂了,clientA 写入 D3 到 Sy 中。这时候在 D3 写 W-1 个副本的时候 clientB 写入 D4 到 Sz 中,这样就发生了分歧。如果有 clientC 同时读到了 D3 和 D4(w 次读),读到的应该是 D3 和 D4 的集合,(Sx, 2) (Sy, 1) (Sz, 1) 。如果是 client 端处理这种分歧的话,client 将会把这个数据再写入 Sx 中完成分歧处理。最终的数据是 D5 当中的样子。

3 Temporary Failures

对于节点短暂的不可用,dynamo 采用了 Hinted Handoff 的策略,其流程是先将 client 的 request 转移到其他的节点 B(not coordinator node A),然后等到 coordinator node A 可用的时候,将之前暂时存在 B 点的数据转移到节点 A 上。A 节点接下来继续提供服务。

4 Replica Synchronization

对于永久性离开的节点,dynamo 提供了副本同步的机制,可以同步副本之间的数据。为了更快的检查副本之间需要同步的数据,dynamo 引入了 merkle tree。Merkle tree 用来标记每一个 node 上面对于一段范围的数据是否一样。进而确定需要同步的的数据。但是由于引入了 Merkle tree 对于节点的加入和删除将会引入大量的 Merkle tree 重新计算。

5 Failure Detection

dynamo 采用了 gossip 的策略。每个节点都会维护一个完整的环上成员信息(membership information), 该信息的更新就是通过 gossip 策略将环上的成员信息变化传递到周围节点上。

结束

总而言之,dynamo 对于数据分布,容错处理,数据恢复,元信息传递等问题进行了整体的讨论。虽然代码没有开源(很可惜),但是对于稳定运行多年的系统,时间就是检验技术的最好的标准。或许 dynamo 并不完美,但是 dynamo 是一个很好的教科书般的无中心节点分布式存储的实践。有时间的小伙伴可以看看原文。希望本文不要误人子弟。


本文转载自公众号 360 云计算(ID:hulktalk)。


原文链接:


https://mp.weixin.qq.com/s/5muexP5MuwEjjVbo6mt0Zw


2019-11-25 16:40821

评论

发布
暂无评论
发现更多内容

盲盒h5小程序app系统开发

参会指南 | 2021MongoDB南京技术沙龙

MongoDB中文社区

mongodb

【高并发】通过源码深度分析线程池中Worker线程的执行流程

冰河

Java 并发编程 多线程 高并发 异步编程

vue3 学习笔记 (一)——mixin 混入

码仔

Vue3 mixin

单机训练6000万类视觉分类模型,飞桨大规模分类库PLSC做到了

百度开发者中心

飞桨 视觉分类 plsc

许式伟:Go+ Together丨Go+ 1.0 发布会干货分享

七牛云

Go 语言

黄东旭:写给后端程序员看的认知心理学丨Go+ 1.0 发布会干货分享

七牛云

Go 语言

程序员的硬核浪漫 — 女友专属语聊房(内附源码)

ZEGO即构

音视频 语聊房 demo源码 即构科技

许式伟:Go+ v1.x 的设计与实现丨Go+ 公开课 • 第一期

七牛云

Go 语言 goplus

17 K8S之容器资源需求与资源限制

穿过生命散发芬芳

k8s 11月日更

盲盒开发源码搭建小程序app

林昊:开发者如何提升写代码的硬实力丨Go+ 1.0 发布会干货分享

七牛云

Go 语言

干货分享:细说双 11 直播背后的压测保障技术

阿里巴巴中间件

阿里云 云原生 中间件 全链路 PTS

明道云商业化成果巡礼|2021年11月

明道云

基于Guava API实现异步通知和事件回调

Tom弹架构

Java 架构 设计模式

盲盒开发

网易云信发布虚拟形象实时互动融合 SDK ,元宇宙大幕即将开启

网易云信

人工智能 数字化 元宇宙

为AI另辟蹊径的“小”数据

澳鹏Appen

人工智能 大数据 小数据 数据标注 训练数据

如何在浏览器 console 控制台中播放视频?

CRMEB

初识 .NET6

面向对象的猫

.net core .net6

【体验有礼】Serverless 极速搭建 Hexo 博客

阿里巴巴中间件

阿里云 Serverless 云原生 Hexo 中间件

【强势推出】专家带你玩,秒懂数据库!官方证书、万元奖品带回家!

华为云数据库小助手

GaussDB GaussDB(for openGauss) 华为云数据库

盲盒开发盲盒小程序开发

盲盒开发盲盒app开发

盲盒开发盲盒小程序系统开发

HarmonyOS 3.0.0开发者预览版全新发布

HarmonyOS开发者

HarmonyOS ArKUI 3.0 ArkCompiler 3.0

iOS开发面试和底层学习视频整理合集

iOSer

ios iOS面试 ios开发 iOS视频学习 iOS涨薪

盲盒开发小程序app开发源码搭建

盲盒小程序开发盲盒源码搭建

进击的Java(九)

ES_her0

11月日更

自定义View:多点触摸画笔的实现

Changing Lin

11月日更

  • 扫码添加小助手
    领取最新资料包
Dynamo论文导读_文化 & 方法_赵明寰_InfoQ精选文章