建议程序员都读一读的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 条评论
登录 后参与评论

相关文章

来自专栏owent

关于BUS通信系统的一些思考(一)

如何保证一个进程或线程能安全稳定地把一段消息发送到另一个进程和线程,甚至是另一台机器的进程或线程,再或是要通过代理转发到另一个进程或线程,一直是一个比较麻烦的问...

761
来自专栏微信公众号:Java团长

你的项目应该如何正确分层?

说起应用分层,大部分人都会认为这个不是很简单嘛 就controller,service, mapper三层。看起来简单,很多人其实并没有把他们职责划分开,在很多...

923
来自专栏数据和云

数据库选型:多核还是多线程?

数据库选型,是用多核主机还是多线程主机?我是否可以用比较便宜的单核超线程(Hyper-Threading,HT)的机器,来替代双核非HT的机器? 回答这个问题,...

3137
来自专栏Linyb极客之路

你的项目应该如何正确分层?

说起应用分层,大部分人都会认为这个不是很简单嘛 就controller,service, mapper三层。看起来简单,很多人其实并没有把他们职责划分开,在很多...

1143
来自专栏H2Cloud

RedRabbit——基于BrokerPattern服务器框架

RedRabbit 经典网游服务器架构 ? 该图省略了专门用途的dbserver、guildserver等用于专门功能的server,该架构的优点有: l Lo...

2926
来自专栏架构之美

五分钟学会分布式事务

1172
来自专栏吴伟祥

验证框架Hibernate Validator 分组

有的时候,我们对一个实体类需要有多中验证方式,在不同的情况下使用不同验证方式,比如说对于一个实体类来的id来说,保存的时候是不需要的,对于更新时是必须的,可以如...

863
来自专栏racaljk

《代码整洁之道》摘录总结

1.     以下全部条款源于·<Clean Code Robert.C.Martin>Chapter 17,这里对其进行文字层面的加工,简化,便于以后能短时浏...

633
来自专栏Hadoop数据仓库

HAWQ取代传统数仓实践(八)——维度表技术之角色扮演维度

        单个物理维度可以被事实表多次引用,每个引用连接逻辑上存在差异的角色维度。例如,事实表可以有多个日期,每个日期通过外键引用不同的日期维度,原则上每...

20610
来自专栏乐沙弥的世界

Oracle DB Time 解读

Oracle DB Time是Oracle数据库在时间维度上剖析性能的一个重要指标,通过逐级分解该指标,定位到浪费资源或者资源争用的首要事件上,从而通过减少等待...

381

扫码关注云+社区