文档章节

一致性hash在DynamoDB上的应用

wier
 wier
发布于 2017/11/15 10:25
字数 3117
阅读 1224
收藏 37
点赞 1
评论 1

一致性哈希在维基百科中,是这么定义的

一致哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

​这一篇借助这个主题,顺便来了解下Dynamo在一致性hash上的应用,熟悉其应用场景以及原理。

 

一、dynamo特点介绍

dynamo 的中文意思是发电机,意思是像发电机一样,提供源源不断的服务。它是Amazon提供的一个分布式Key/Value存储的NoSQL 数据库,完全托管在云端,支持文档和键值存储模型。


其主要特点是如下:

特点 描述
数据模型灵活 schema freee,Nosql必然支持的,没什么说的
效率(速度) 数据采用SSD来进行存储,服务端平均延迟通常不超过十毫秒。随着数据量增多,DynamoDB 会使用自动分区和 SSD 技术来满足吞吐量需求,并针对任意规模的数据库提供低延迟。
高可用 Dynamo 为了达到高可用性和持久性,防止由于节点宕机故障或者数据丢失,将同一份数据在协调者和随后的 N-1 个节点上备份了多次
高度可扩展 dynamo 不会对数据规模大小进行限制,会把数据分布到各个机器上,只需为其指定目标使用率,容量便会自动根据应用程序请求数量的增加或减少而扩展或缩减,无需担心数据库的缩扩容问题
完全托管 无需担心数据库的管理,比如管理集群,软硬件的配置与预设以及监控、部署,省去开发者部署、监控、维护数据库的环境
去中心化 节点对称性、去中心化:系统采用P2P架构,每个节点都是对等的、有相同的责任
ACID属性 为了获得更为灵活的可水平扩展的数据模型,NoSQL 数据库通常会放弃传统关系数据库管理系统 (RDBMS) 的部分 ACID 属性,而且在保证ACID的数据存储时往往有很差的可用性。Dynamo的目标应用程序是高可用性,弱一致性(ACID中的”C”)。


我觉得dynamo最吸引人的地方就是高度扩展性,以及完全托管,这个会节省开发人员大量的运维工作。
当然了不好的地方也是它的数据一致性要求不是很高,在99.94% 左右,而且遇到了不一致问题,都抛给了上层来解决,类似于git merge操作,如果对一致性要求比较高的话,这个还是挺麻烦的,当然了这个主要看应用的选型需求了,后期再详细介绍。

dynamo的高度扩展性,就是采用了一致性hash的原理来实现,我们来着重分析一下,它是如何采用采用一致性hash而达到高扩展性的。

 

二、数据分布

在dynamo 中创建table的时候,必须要指定一个分区键(partition),分区键可以用hash值,也可以用户自己指定,做唯一主键的时候,不能有重复。

对于刚接触Dynamo的时候不是很明白要如何应用分区键。那么为何要用分区键?

 

我们回顾一下,一致性hash的实现原理,一致性hash是把数据均匀的映射到一个线性空间,以保证分配的均匀性,以及提高数据的单调性。同时为了减少由于节点数过少导致移动过多的数据项,又加入了虚拟节点。如下:

 

引入了“虚拟节点”后,映射关系就从【object--->node】转换成了【object--->virtual node---> node】。查询object所在node的映射关系如下图所示。

以上virtual node我们就可以称为 partition,当增加新的node服务器的时候,由于virtual node没有变化,数据的hash值也是固定不变的,因此只需要处理一下,virtual node和node的重分配,这个对数据迁移的影响是最小的。

我们看下代码实现:

我们假设有256个node(2^8),有partition数4096(2^12)。由于MD5码是32位的,使用PARTITION_SHIFT(等于32- PARTITION_POWER)将数据项的MD5哈希值映射到partition的2^12的空间中。此处引入了partition power 。

ITEMS = 10000000
NODES = 256
PARTITION_POWER = 12
PARTITION_SHIFT = 32
PARTITION = PARTITION_SHIFT - PARTITION_POWER
node_stat = [0 for i in range(NODES)]

#获取hash值
def _hash(value):
    k = md5(str(value)).digest()
    ha = unpack_from(">I", k)[0]
    return ha

ring = []
part2node = {}

#虚拟节点和node节点做映射关系
for part in range(2 ** PARTITION_POWER):
    ring.append(part)
    part2node[part] = part % NODES

for item in range(ITEMS):
    #把32位的hash值映射到12位的空间中
    h = _hash(item) >> PARTITION
    #查找最近的partition
    partition = bisect_left(ring, h)
    n = partition % NODES
    node_stat[n] += 1

_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)


这个就是为何dynamo在创建表的时候要指定分区键partition,因为要保证其数据的高扩展性,需要把数据分配到不同的node数据服务器上。
有了partition,一张表的数据,就可以分散到不同的node上,同时在数据进行扩容增加node的时候,因为数据的partition并没有发生变化,只是partition对应的node映射发生了变化,对数据的迁移影响是最小的。

 

三、数据冗余

在上述模型中,虽然解决的数据的扩展性问题,但数据的高可用问题,并没有去达成,每个node节点的数据都是单一的,如果这个节点出故障了,数据怎么处理?


为了让系统达到高可用性和持久性,防止由于节点宕机故障或而造成数据丢失,Dynamo中的数据被复制成N份存于多台主机中。
除了本地存储其范围内的每个结点将同一份数据在协调者和随后的 N-1 个节点上备份了多次,N 是一个可以配置的值,默认情况下是3,其理论依据主要来源于NWR策略。

NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中,就应用NWR来控制一致性。每个字母的涵义如下:

 

      N:同一份数据备份的份数

      W:是更新一个数据对象的时候需要确保成功更新的份数

      R:读取一个数据需要读取的最少节点(备份)的份数

 

只要满足W+R > N,就可以保证当存在不超过一台机器故障的时候,至少能读到一份有效的数据。如果应用重视读效率,可以设置W=N,R=1; 如果应用需要在读/写之间权衡,一般可设置成N=3, W=2, R=2。Dynamo推荐使用322的组合。  

 

我们在这里称为Replica,在分布式系统中,数据的单点是不允许存在的,即线上正常存在的Replica数量是1的情况是非常危险的。


因为一旦这个Replica再次错误,就可能发生数据的永久性错误。假如我们把N设置成为2,那么,只要有一个存储节点发生损坏,就会有单点的存在。所以N必须大于2。N约高,系统的维护和整体成本就越高。工业界通常把N设置为3。

比如上图中,黄色区域的值会存储在三个节点 A、B 和 C 中,蓝色的区域会被 D、E、F 三个节点处理,负责存储某一个特定键值对的节点列表叫做偏好列表(preference list),因为虚拟节点在环中会随机存在,为了保证出现节点故障时不会影响可用性和持久性,偏好列表中的全部节点必须都为不同的物理节点。

我们来看实现方式

我们在上述代码中引入replica,数量设置为3,其中 node_ids记录的是3个replica存放的node id。part2node[part]是根据partition id 找到对应的node id,也是分区和node节点的映射关系。

ITEMS = 10000000
NODES = 100
PARTITION_POWER = 12
PARTITION_SHIFT = 32
PARTITION = PARTITION_SHIFT - PARTITION_POWER
PARTITION_MAX =2**PARTITION_POWER-1
REPLICAS = 3

node_stat = [0 for i in range(NODES)]

def _hash(value):
    k = md5(str(value)).digest()
    ha = unpack_from(">I", k)[0]
    return ha

ring = []
part2node = {}

#虚拟节点和node节点做映射关系
for part in range(2 ** PARTITION_POWER):
    ring.append(part)
    part2node[part] = part % NODES

for item in range(ITEMS):
        #把32位的hash值映射到12位的空间中
    h = _hash(item) >> PARTITION
    part = bisect_left(ring, h)
    node_ids = [part2node[part]]
    node_stat[node_ids[0]] += 1

#数据replica处理,一份数据存放临近的3个物理节点
    for replica in xrange(1, REPLICAS):
        while part2node[part] in node_ids:
            part += 1
            if part > PARTITION_MAX:
                part = 0
        node_ids.append(part2node[part])
        node_stat[node_ids[-1]] += 1


_ave = ITEMS / NODES* REPLICAS
_max = max(node_stat)
_min = min(node_stat)

 

四、数据一致性

1、冲突

由于加入了replica,特别是NWR 是322的情况下,一个读操作,必须得等待2个节点的数据返回对应结果,才认为当前请求结束了,也就是说会请求时间会受最慢节点的影响,写的情况也是相同。唯一的不同是,发现节点中数据出现了冲突,会对冲突尝试进行解决并将结果重新写回对应的节点。

Dynamo对数据的一致性要求没有那么高,会出现数据不一致情况,当然了多数情况下,Dynamo 都不会出现这种情况,并且即便出现了,Dynamo 能够确保一旦数据之间发生了冲突不会丢失,但是可能会有已被删除的数据重新出现的问题。

针对这种情况,Dynamo提供了向量时钟来解决,每一个对象版本中都存在一个或者多个向量时钟,每次更新数据的时候,都会更新向量时钟的版本。
如果待更新数据的向量钟的每一项都不小于本地向量钟,那么数据无冲突,新的值可以被接受。当客户端再次 请求时就会发现数据出现了冲突,由于 Dynamo 无法根据向量时钟自动解决,所以它需要客户端合并不同的数据版本。就类似git 的merge 操作,把问题抛给了调用方来解决。

 

2、故障

在一个节点出现临时性故障时,数据会自动进入列表中的下一个节点进行写操作,并标记为handoff数据,如果在指定的时间内该机器重新提供服务,则其他机器会通过Gossip协议发现,并将暂存的数据回传给该临时性故障的机器。

 

如果超时了一定的间隔,该机器还是处理宕机状态,则会认为是永久下线了,此时需要从其它副本同步数据。为了更快地检测副本之间的不一致性,并减少传输的数据量,Dynamo采用了Merkle树。Merkle树是一个哈希树,其叶子结点是各个key的哈希值,树中较高的父结点均为其各自孩子节点的哈希,通过这种方式构建的树形结构能够保证整棵树不会被篡改,任何的改动都能被立刻发现。如此检测快,数据传送的量也小,同步时只同步从根结点到叶子的所有节点值均不相同的文件。

引用:

https://draveness.me/dynamo

http://www.cnblogs.com/yuxc/archive/2012/06/22/2558312.html

end

 


关注游戏研发和个人成长,致力于游戏技术社区的推进,扫描二维码,关注更多原创文章。

© 著作权归作者所有

共有 人打赏支持
wier
粉丝 658
博文 46
码字总数 122193
作品 0
东城
高级程序员
加载中

评论(1)

justintung
justintung
v
如何将DynamoDB的数据增量迁移到表格存储

Amazon DynamoDB是一个完全托管的NoSQL数据库服务,可以提供快速的、可预期的性能,并且可以实现无缝扩展。由于DynamoDB并可以根据实际需求对表进行扩展和收缩,这个过程既不需要停止对外服务...

表格存储 ⋅ 05/17 ⋅ 0

上海云栖大会阿里云产品这波降价“狠”不一般,详情对比走起

在上周刚刚结束的2018云栖大会·上海峰会上,阿里云一口气发布了数款产品,不无例外的是,阿里云延续历届云栖大会风格,在宣布新产品发布之余,宣布多款产品价格下调,包括ECS 企业级实例规格...

云攻略小攻 ⋅ 06/14 ⋅ 0

盘点知名云计算公司的数据库服务(国外篇)

  【IT168 评论】“跨界”是现在很火的一个词,它是指从某一属性的事物进入另一属性的运作,其不只在演艺圈掀起了一阵热潮,同时也在科技圈也带起了一阵狂潮。今天,我们就来看看科技圈第一...

it168网站 ⋅ 04/16 ⋅ 0

从事分布式系统、计算、hadoop 等方面工作需要哪些基础?

作者:知乎用户 链接:https://www.zhihu.com/question/19868791/answer/18144881 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 先看百度文库这篇《分...

chenhao_asd ⋅ 04/25 ⋅ 0

Gravitational Teleport 2.6.0 发布,已登录 AWS 市场

Teleport 2.6.0 发布了,此版本带来了新功能、显着的性能和可用性改进以及常规 bug 修复。 New Features 支持 DynamoDB 存储审计日志事件 #1755 支持 Amazon S3 存储记录的 SSH 会话 #1755 ...

雨田桑 ⋅ 06/01 ⋅ 0

AR/VR 开发工具 Amazon Sumerian 正式上线

去年 AWS 赶在 re:Invent 大会前,推出 AR/VR 开发工具 Amazon Sumerian,让开发者可以在 Oculus Rift、HTC Vive、iOS 移动装置,甚至网页浏览器环境制作3D、虚拟现实或增强现实(VR/AR)应用...

雨田桑 ⋅ 05/18 ⋅ 0

Python 如何传递运算表达式

点击关注异步图书,置顶公众号 媒体与你分享IT好书 技术干货 职场知识 首先要说明的一下,所描述的是 Python 中的 运算表达式 的部分,不是 Python 表达式的部分。 关于什么是 Python 中的运...

异步社区 ⋅ 05/02 ⋅ 0

Amazon全栈工程师:从淘汰Oracle数据库的事说起

公司搞淘汰Oracle数据库的事情已经搞了好久了,这个事情其实和国内淘宝系搞的去IOE(IBM、Oracle和EMC)是类似的,基本上也是迫不得已,Oracle的维护成本太高,而公司内部基于Oracle数据库的...

四火 ⋅ 2016/07/05 ⋅ 0

Amazon DynamoDB

DynamoDB 是Amazon最新发布的NoSQL产品,那什么是DynamoDB呢? DynamoDB 是一个性能好、可靠高且具有可扩展性的NoSQL云数据库服务,DynamoDB集15年分布式非关系性数据库开发之精粹,又通过内...

长平狐 ⋅ 2013/01/06 ⋅ 0

Hadoop 3相对于hadoop2的 新特性

相对于之前主要生产发布版本Hadoop 2,Apache Hadoop 3整合许多重要的增强功能。 Hadoop 3是一个可用版本,提供了稳定性和高质量的API,可以用于实际的产品开发。下面简要介绍一下Hadoop3的主...

yongge1981 ⋅ 05/30 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 12分钟前 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 38分钟前 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

C++难点解析之const修饰符

C++难点解析之const修饰符 c++ 相比于其他编程语言,可能是最为难掌握,概念最为复杂的。结合自己平时的C++使用经验,这里将会列举出一些常见的难点并给出相应的解释。 const修饰符 const在c...

jackie8tao ⋅ 昨天 ⋅ 0

聊聊spring cloud netflix的HystrixCommands

序 本文主要研究一下spring cloud netflix的HystrixCommands。 maven <dependency> <groupId>org.springframework.cloud</groupId> <artifactId>spring-clo......

go4it ⋅ 昨天 ⋅ 0

Confluence 6 从其他备份中恢复数据

一般来说,Confluence 数据库可以从 Administration Console 或者 Confluence Setup Wizard 中进行恢复。 如果你在恢复压缩的 XML 备份的时候遇到了问题,你还是可以对整个站点进行恢复的,如...

honeymose ⋅ 昨天 ⋅ 0

myeclipse10 快速搭建spring boot开发环境(入门)

1.创建一个maven的web项目 注意上面标红的部分记得选上 2.创建的maven目录结构,有缺失的目录可以自己建立目录补充 补充后 这时候一个maven的web项目创建完成 3.配置pom.xml配置文件 <proje...

小海bug ⋅ 昨天 ⋅ 0

nginx.conf

=========================================================================== nginx.conf =========================================================================== user nobody; #......

A__17 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部