建议程序员都读一读的31篇论文系列笔记(1~2)

序:前几日网上偶然看到”程序员必读论文系列“,顺便搜了一下,发现有多个版本共31篇,不过看起来都不错,故准备花时间都读一下,可以拓宽下视野。来源论文题目主要参考 http://blog.csdn.net/turingbook/article/details/3946421 和 http://top.jobbole.com/17733/ 。每读完一篇论文就写些笔记,或长或短,也就是这几篇文章的由来。

1. An Axiomatic Basis for Computer Programming. 1969年的一篇论文,主要讲用公理基础证明计算机编程的正确性,包括赋值/递推/组合/循环等。不是那么容易读懂,特别是一些数理符号,想要完全看懂估计得查不少书。扫过重要的部分,关键就是 P{Q}R, 即前置条件满足assert(P) 为true,Q是一段程序(可以是多个子程序的组合),后置条件R是人们可以期望的正确结果,跟Q的执行输出有关,若assert(R)为true,可以证明Q是正确的程序。

2. Dynamo: Amazon’s Highly Available Key-value Store.2007年的这篇论文长达16页,详细介绍了曾经服务于Amazon Services的一个key/value 分布式存储系统,包括背景需求,设计与实现,同类产品的研究工作,生产过程中使用Dynamo的经验等。Amazon Services是高度去中心化,松耦合和以服务为导向的架构,故Dynamo也是去中心化的,对于Amazon Services来说只需要通过Key查询数据,故传统关系型数据库复杂的查询逻辑在此派不上用场,此外关系型数据库也没有很好的复制技术,以便支撑因为负载均衡而产生的数据库的扩展和分区需求。如下图所示。一个客户端请求需要多个services服务,需要Aggregator Services来做聚合。一个node认为是一台host,一个instance是多个node的集合,一个services使用自己的instances。

Dynamo 的可扩展性和可用性采用的都比较成熟的技术,数据分区并用改进的(virtual node)一致性哈希[3](consistent hashing)方式进行复制,利用数据对象的版本化和vector clock实现最终一致性。更新时因为副本之间产生的一致性问题的维护采取类似 quorum[1] 的机制以及去中心化的复制同步协议[2]。

Dynamo的实现是一个最终一致性的数据存储,对于分布式系统的CAP原理来说,牺牲了部分一致性,也就是弱一致性模型,提高可用性,即”always writeable"。

对于数据冲突的解决并不是传统的 read only write all,而是类似quorum机制把部分压力给了read。而解决冲突的执行者不是application而是data store,使用的是简单的"last write wins" 策略。

数据分区策略:采用改进的一致性哈希算法,也就是引入virtual nodes,即可以将一个真实物理host映射为n个虚拟nodes,这样可以实现load balance,特别是不同物理host的容量不一致的情况下,比如容量大的主机的n值可以大些。

数据复制策略:Dynamo 会将数据复制在N台host上,N是一个instance的配置参数。通常除由一个协调node存储在本地外,还负责复制到它的两个顺时针走向的N-1个node上。注意,如果使用了virtual node,则负责如下图Key K (K=hash(dataobject))的 preference list 会跳过一些位置,以保证list只包含真正的物理nodes。To account for node failures, preference list contains more than N nodes.

如上图所示,Key K 的数据会存在node B, C, D(N=3)。同理对于node D来说,Node D will store the keys that fall in the ranges (A, B], (B, C], and (C, D].

数据同步策略:采用类似于 Quorum 系统的一致性协议实现(“sloppy quorum”: all read and write operations are performed on the first N healthy nodes from the preference list, which may not always be the first N nodes encountered while walking the consistent hashing ring.)。这个协议有两个关键值:R 与 W。R 代表一次成功的读取操作中最小参与节点数量,W 代表一次成功的写操作中最小参与节点数量。R + W>N ,则会产生类似 quorum 的效果。该模型中的读(写)延迟由最慢的 R(W)副本决定,为得到比较小的延迟,通常R 和 W各自的值设置得比 N 小。

若(N,R,W) 的值设置为 (3, 2 ,2)。举例get()和put()操作来说,读写通常由一个协调node来处理(preference list的第一个node)。

对于一个key的put()操作,协调node会为此版本的数据产生vector clock 类似[Sx, 1](Sx表示node),并将数据写在本地,此外会将数据带上vector clock信息发送给另外N-1=2个node,但只要W-1=1个node回应就表示说写成功(当然最后一个node的写进程还是在进行的)。

同样地,对于一个key的get()操作,协调node会向所有存在此数据任何版本的node发起请求(包括自己),如果有R=2个node响应表示读取成功。如果此时两个版本的数据不一致,协调node会进行合并操作并将最新的版本write back。

注:对于一般的session信息存储,是由协调node来执行"last write wins" 合并数据版本。而类似购物车信息之类的是由application logic 自己来执行合并数据版本。

数据容灾策略:以上图N=3为例,如果在一次写操作时发现节点A挂了,那么本应该存在A上的副本就会发送到D上,同时在D中会记录这个副本的元信息(MetaData)。其中有个标示,表明这份数据是本应该存在A上的,一旦节点D之后检测到A从故障中恢复了,D就会将这个本属于A的副本回传给A,之后删除这份数据。Dynamo中称这种技术为“Hinted Handoff”。另外为了应对整个机房掉线的故障,Dynamo中应用了一个很巧妙的方案。之前说过“Preference List”,每次读写都会从这个列表中取出R或W个节点。那么只要在这个列表生成的时候,让其中的节点是分布于不同机房的,自然数据就写到了不同机房的节点上。

“Hinted Handoff”的方式在少量的或是短暂的机器故障中表现很好,但是在某些情况下仍然会导致数据丢失。如上所说,如果节点D发现A重新上线了,会将本应该属于A的副本回传过去,这期间D发生故障就会导致副本丢失。为了应对这种情况,Dynamo中用了基于 Merkle Tree[4]的Anti-Entropy系统,如下图所示:

A Merkle tree is a hash tree where leaves are hashes of the values of individual keys. Parent nodes higher in the tree are hashes of their respective children. 也就是说如果比对两个副本,只需要从root节点开始比对,如果相等则数据一致,否则继续找子节点比对下去,直至找到hash值不一致的节点,同步这部分数据即可。

伙伴关系和失败发现策略

由于各种各样的原因,暂时性的节点掉线是时有发生的。如果因为一个节点暂时性的掉线,而导致副本迁移等代价高昂的操作显然是不合适的。所以Dynamo提供了一组命令行接口和HTTP接口供管理员手工添加,删除节点。一旦一个节点的角色发生改变(上线或下线等),它都会将状态改变的时间存储到一个持久的数据库中,这些数据构成了一个节点的状态变迁历史。然后通过一个Gossip-Based Protocol 将这个消息传递出去。节点在收到其它节点的消息时,会将收到的消息与自己本地存储的消息进行合并,最终每个节点都会得到整个集群的信息。为了应对可能出现的“logical partitions”现象,某些Dynamo节点作为“种子”节点,种子节点可以通过全局的方式被其它所有节点发现,最终所有的节点自己存储的状态信息都与种子节点的状态信息合并。与正常节点发现类似,对错误节点的发现机制也是使用的Gossip-Based Protocol,每个节点都记录自己与其它节点的连通状态。

具体实现:Dynamo的一个存储node主要由三个组件组成,包括请求处理、伙伴关系与失败检测、持久型存储引擎。这三者都是用java实现。对于存储引擎来说,提供多种选择,application可以选择适合自己的引擎,比如 Berkeley Database (BDB) Transactional Data Store2, BDB Java Edition, MySQL, and an in-memory buffer with persistent backing store. 

参考:

[1]. http://www.cnblogs.com/jzhlin/archive/2012/07/23/Quorum.html

[2]. http://dbanotes.net/tech-memo/amazon_dynamo.html

[3]. http://dl.acm.org/citation.cfm?id=258660

[4]. http://blog.csdn.net/xtu_xiaoxin/article/details/8148237

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏铭毅天下

Elasticsearch常见的5个错误及解决策略

网罗Elasticsearch最佳实践,实际应用场景中常见错误要预知和避免,以最大化提升集群性能。

100
来自专栏运维一切

ceph osd full故障 原

资料(传送门)[http://bbs.ceph.org.cn/question/363]

882
来自专栏JAVA高级架构

如何设计一个麻雀般的微型分布式架构?

设计该系统初衷是基于描绘业务(或机器集群)存储模型,分析代理缓存服务器磁盘存储与回源率的关系。系统意义是在腾讯云成本优化过程中,量化指导机房设备扩容。前半部分是...

843
来自专栏吉浦迅科技

放下王者农药这锅,玩一把Tensorflow吧

暑期开始了!对于Lady姐来说,如何安排儿子的暑期生活是一件大事,显然是不能沉迷于王者农药, ? 于是Lady姐随手扔了一个教程给他:按照这份教程,在家里Win...

36610
来自专栏FreeBuf

以针对Yahoo! 的安全测试为例讲解如何高效的进行子域名收集与筛选

平常我在Hackerone平台上寻找新目标时,常常会关注厂商响应信息,如果厂商响应越积极我就越感兴趣。相对于响应信息很少的厂商而言,我们更能从中摸索到问题的本质...

2747
来自专栏程序人生

想让服务器跑得快,并不是换个编程语言那么简单

最近一个读者问我:程序君,我是一个经常被你黑的phper,我想学一门新的语言,做服务器开发,看你好像用过好多语言,能推荐一个么?最好是开发效率高,支持并发,性能...

3448
来自专栏携程技术中心

携程2015 Open House获奖项目:火车票订单中心重构

给绿皮车换上高铁发动机 火车票订单中心重构 web订单系统,对我们来说,都不是一个陌生的东西。然而,高并发从技术的角度来说,这对于Web系统是一个巨大的考验。当...

1968
来自专栏小二的折腾日记

我的hexo折腾笔记

由于以前都是直接使用的github私人仓库做的图床,但是有时候就是访问不到,因为博客是采用双部署的,可能coding上的已经是外链了被屏蔽了,所以还是得想点别的...

581
来自专栏达摩兵的技术空间

bug常识入门

962
来自专栏AI研习社

用GPU加速深度学习: Windows安装CUDA+TensorFlow教程

背景 在Windows上使用GPU进行深度学习一直都不是主流,我们一般都首选Linux作为深度学习操作系统。但很多朋友如果只是想要了解深度学习,似乎没有必要...

6984

扫码关注云+社区