专栏首页开发与安全建议程序员都读一读的31篇论文系列笔记(1~2)

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

相关文章

  • JSONP存在的JSON Hijacking漏洞以及与csrf/xss漏洞的关系

    在实习过程中接触过所谓的JSON Hijacking 漏洞,但最近在写论文时发现理解得不深,好像跟xss与csrf又有点区别与联系,索性深入学习了下JSONP(...

    s1mba
  • 学习 iOS Application Security 需要注意的一些点

    1. mobileTerminal 使用 源 http://cydia.angelxwind.net 的版本;vim 版本7.1-3p,不要升级到7.3-1;

    s1mba
  • C++的引用与const指针的关系以及各种传递方式

    首先我们知道 const int *p 与 int const *p 是一样的,即 *p 是常量;而 int * const p 跟上面是不一样的,即 p 是常...

    s1mba
  • 你真的很熟分布式和事务吗?

    微吐槽 hello,world. 不想了,我等码农,还是看看怎么来处理分布式系统中的事务这个老大难吧! 本文略长,读者需要有一定耐心,如果你是高级码农或者架构师...

    企鹅号小编
  • POJ 1655 Balancing Act【树的重心】

    Balancing Act Time Limit: 1000MS Memory Limit: 65536K Total Submissions:...

    Angel_Kitty
  • 分布式计算(1)

    网格计算强调资源共享,使用者同时也是资源共享者,用于计算集中性服务(不便扩展 )。云计算的服务提供者少数而集中,资源专有,便于自动化扩展(其中对等计算更便于扩展...

    gojam
  • 【董天一】IPFS: BitSwap协议(数据块交换)

    IPFS在BitTorrent的基础上实现了p2p数据交换协议:BitSwap协议

    圆方圆学院
  • (1)解锁MongoDB replica set核心姿势

    本文倒腾目前大热的MongoDB Replica Set集群,在倒腾的同时串讲一些 MongoDB特性。

    小码甲
  • 十年架构师带你剖析B树和B+树

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    美的让人心动
  • Druid实时OLAP数据分析存储系统极简入门

    Druid 是一个开源的,分布式的,列存储的,适用于实时数据分析的存储系统,能够快速聚合、灵活过滤、毫秒级查询、和低延迟数据导入。

    王知无

扫码关注云+社区

领取腾讯云代金券