Strong Consistency, 强一致性技术概述

Master Slave (or Single Master)Model

Under this model, each data partition has a single master and multiple slaves.

All update requests has to go to the master where update is applied and then asynchronously propagated to the slaves. Notice that there is a time window of data lost if the master crashes before it propagate its update to any slaves, so some system will wait synchronously for the update to be propagated to at least one slave.

Read requests can go to any replicas if the client can tolerate some degree of data staleness. This is where the read workload is distributed among many replicas. If the client cannot tolerate staleness for certain data, it also need to go to the master.

Master Slave model works very well in general when the application has a high read/write ratio. It also works very well when the update happens evenly in the key range. So it is the predominant model of data replication.

主从模式, 最传统和简单的模式 
写操作, 所有写操作通过master, master写成功即返回, 然后master负责异步propagate到各个slave节点. 为了增强可靠性, 也可以等master至少propagate一个slave后再返回. 
读操作, 如果可以容忍旧数据, 从任一节点读. 如果不能容忍, 所有读操作也要通过master 
缺点, 单点问题, 以及master负载过重 
解决办法, 参考Google的设计, GFS, Bigtable

 

去中心化的方案, Quorum Based 2PC

由于主从模式比较成熟和简单 
对于分布式的场景, 去中心化的设计(无固定master), 如何保证一致性? 这才是近年来, 研究的难点和热点


JimGray在“Notes on Database Operating Systems” (1979)中描述了两阶段提交(2PC)

二阶段提交(2PC)协议

传统的2PC协议用于保证分布式事务的原子性, 分布式存放的数据, 必须要保证同时更新成功或失败. 
所以coordinator必须在第一阶段, 发送prepare请求保证所有的数据复本当前都是ready for update, 在得到所有复本回应后再开始第二阶段, 正真的commit 
这里就比基于master复杂, 不是仅仅master同意, 而是要所有的node都同意, 才能commit

To provide "strict consistency", we can use a traditional 2PC protocol to bring all replicas to the same state at every update.

Lets say there is N replicas for a data. 
When the data is update, there is a "prepare" phase where the coordinator ask every replica to confirm whether each of them is ready to perform the update. 
Each of the replica will then write the data to a log file and when success, respond to the coordinator. 
After gathering all replicas responses positively, the coordinator will initiate the second "commit" phaseand then ask every replicas to commit. 
Each replica then write another log entry to confirm the update.

Notice that there are some scalability issue as the coordinator need to "synchronously" wait for quite a lot of back and forth network roundtrip and disk I/O to complete. 
On the other hand, if any one of the replica crashes, the update will be unsuccessful. As there are more replicas, chance of having one of them increases. Therefore, replication is hurting the availability rather than helping. This make traditional 2PC not a popular choice for high throughput transactional system. 
2PC协议的最大的问题是没有考虑节点fail的case, 任意的节点的fail都会导致block. 
Dale Skeen在“NonBlocking Commit Protocols” (1981)中指出,对于一个分布式系统, 需要3阶段的提交算法来避免2PC中的阻塞(block)问题, 但问题关键很难找到一个好的3PC算法

对于阻塞问题,  其实想当然的是可用通过timeout来解决, 当然问题没有那么简单, 
问题的核心在于,你无法区分一个进程到底是终止了还是正在以极低的速度执行,这使得在异步系统中的错误处理几乎是不可能的 
Fischer, Lynch 和 Paterson在"Impossibility of distributed consensus with one faulty process” (1985) 中证明了这一点

对于一个异步系统来说即使只有一个进程出错,分布式一致性也是不可能达到的,这就是著名的FLP结论

人们意识到一个分布式算法具有两个属性: 安全性(safety)和活性(liveness), 2PC极具安全性,却缺乏活性

在1986年的会议上, 分布式事务被认为是一个新的一致性问题,称为uniform consensus (参见“Uniform consensus is harder than consensus” (2000))

With uniform consensus all processes must agree on a value, even the faulty ones - a transaction should only commit if all RMs are prepared to commit. Most forms of consensus are only concerned with having the non-faulty processes agree. Uniform consensus is more difficult than general consensus.

个人理解, 在节点或进程失效的时候, 仍然可以达成一致性, 而不会存在2PC的block的情况

Paxos, quorum based 2PC

最终Lamport在“The Part-Time Parliament” (submitted in 1990, published 1998)中提出了Paxos一致性算法, 后来Lamport又发表了“Paxos Made Simple (2001).

用于解决uniform consensus的问题.

Paxos的核心, 在于quorum based 2PC, 在分布式环境既然无法要求所有节点能够正常响应 
那么Paxos只需要majority(多数派)正常响应, 就可以达成一致性决议, 从而避免任一节点fail导致的block 
但问题在于, 那些没有响应的节点(因为fail或网络等原因)怎样保证其一致性? 
答案是, 任何一致性决议的达成都需要majority的accept, 任意两个majority集合都一定有交集(至少一个节点) 
而任一节点都只能accept一次proposal(除非具有相同的value), 所以当一个一致性决议达成的情况下, 不可能有不同value新决议被达成(即使在部分节点fail的情况下) 
从而即使fail的节点wake-up后, 仍然可以简单的从其他majority节点learn并保证一致性 
这就是为什么叫quorum based 2PC, 其实本质就是 R +W > N 
并且在一段时间内无法获得majority的响应时, 可以随时主动放弃现有提案, 并提出更高编号的提案, 进一步避免block

传统2PC只是Paxos的一种特殊case (当W = N and R = 1) 
A more efficient way is to use the quorum based 2PC (e.g. PAXOS). 
In this model, the coordinator only need to update W replicas (rather than all N replicas) synchronously. The coordinator still write to all the N replicas but only wait for positive acknowledgment for any W of the N to confirm. This is much more efficient from a probabilistic standpoint.

As you can see, the quorum based 2PC can be considered as a general 2PC protocol where the traditional 2PC is a special case where W = N and R = 1. The general quorum-based model allow us to pick W and R according to our tradeoff decisions between read and write workload ratio.

本文章摘自博客园,原文发布日期:2013-04-03

时间: 2017-05-02

Strong Consistency, 强一致性技术概述的相关文章

Servlet和JSP知识复习(1)Servlet & JSP 技术概述

js|servlet Servlet和JSP知识复习(1)Servlet & JSP 技术概述 1.Servlet的功用    ·读取客户程序发送来的显式数据(表单数据)    ·读取客户程序发送来的隐式数据(请求报头)    ·生成相应的结果    ·发送显式的数据给客户程序(HTML)    ·发送隐式的数据给客户程序(状态代码和响应报头) 2.为什么要动态地构建Web页面?    ·Web页面的内容建立在用户提交的数据之上    ·Web页面的内容由频繁变动的数据导出    ·Web页面用

转贴:Microsoft Application Center 2000 组件负载平衡技术概述(1)

application Microsoft Application Center 2000 组件负载平衡技术概述 作者:Chris Rees 本技术概述将讨论 Microsoft Application Center 2000 (Application Center) 组件负载平衡技术 (CLB). 引言 Microsoft Application Center 2000 (Application Center) 是 Enterprise Server 的一部分,而 Enterprise Ser

转贴:Microsoft Application Center 2000 组件负载平衡技术概述(2)

application  组件负载平衡应用 下面的说明可使 CLB 得到迅速应用.这些说明假设将用 stager 来将内容部署到 Web 层和 COM+ 群集上.并假定您掌握了有关 Visual Basic.ASP 和 HTML 的实际使用知识. 在 stager 上使用 Visual Basic,创建一个导出以下函数的 COM+ 组件. Public Function GetName() As StringSet WS = CreateObject("wscript.network"

《云安全原理与实践》——3.1 主机虚拟化技术概述

3.1 主机虚拟化技术概述 虚拟化技术经过半个多世纪的发展,已日趋成熟并逐渐得到广泛的应用,成为云计算的基础技术. 1959年,在国际信息处理大会上,著名科学家克里斯托弗(Christopher Strachey)发表了一篇名为"大型高速计算机中的时间共享"(Time Sharing in Large Fast Computers)的学术报告.在该报告中,他提出了虚拟化的基本概念,同时这篇文章也被认为是对虚拟化技术的最早的论述. 1965年,IBM公司发布IBM7044,它被认为是最早

《iOS 8应用开发入门经典(第6版)》——第1章,第1.4节开发技术概述

1.4 开发技术概述 iOS 8应用开发入门经典(第6版) 在接下来的几章中,将简要地介绍用来创建iOS应用程序的技术.我们的目标是让您快速了解这些工具和技术,然后开始开发.这意味着几章后您才会编写第一个应用程序,但当您开始编码时,将具备成功创建各种应用程序所需的技能和知识. 1.4.1 Apple开发工具 在本章中,您下载并使用了应用程序Xcode,它自带了iOS模拟器,您在阅读本书的过程中主要使用的就是它.这两个应用程序很重要,本书将花两章的篇幅(第2章和第5章)介绍它们的功能和用法. 需要

RIA主流技术——Flex 3.0技术概述

问题描述 RIA主流技术--Flex3.0技术概述RIA富媒体开发应用很早就出现了.但真正兴起是2007年的事情.2007的网络视频的飞速发展,掀开RIA大规模应用的开始.而2008年号称是RIA应用年.在RIA开发技术中,以Adobe的Flex技术和微软的Siverlight为首.而发展最成熟的是Flex技术.现在Adobe推出功能更强大的最新版本Flex3.0.本人跟踪Flex技术多年,深刻体验Flex1.5.2.0版本.经过一年的准备和写作,终于完成这本书.这本书从基础讲解,剖析Flex3

Microsoft .NET Remoting:技术概述

Microsoft .NET Remoting:技术概述Piet Obermeyer 和 Jonathan HawkinsMicrosoft Corporation摘要:本文提供了 Microsoft .NET Remoting 框架的技术概述,其中包括了使用 TCP 通道或 HTTP 通道的示例.目录简介远程对象代理对象通道激活对象的租用生存期总结附录 A:使用 TCP 通道进行远程处理的示例附录 B:使用 HTTP 通道进行远程处理的示例简介Microsoft® .NET Remoting

《大规模元搜索引擎技》——1.3 搜索引擎技术概述

1.3 搜索引擎技术概述 最早的Web搜索引擎基本上就是网页文本检索系统.然而,Web环境中有一些特征,使得构建现代搜索引擎与构建传统文本检索系统显著不同.在本节中,简要概述这些特征以及基于利用这些特征的搜索引擎构建技术. 1.3.1 Web的专门特性 下面是Web环境的一些特性,它们对搜索引擎的发展产生了重大影响.1)Web页面存储在大量的自治Web服务器中.需要一种方法来查找和获取这些Web页面,以便处理后供搜索用.2)大多数Web页面是HTML(HyperText Markup Langu

《大规模元搜索引擎技(1)》一1.3 搜索引擎技术概述

1.3 搜索引擎技术概述 最早的Web搜索引擎基本上就是网页文本检索系统.然而,Web环境中有一些特征,使得构建现代搜索引擎与构建传统文本检索系统显著不同.在本节中,简要概述这些特征以及基于利用这些特征的搜索引擎构建技术. 1.3.1 Web的专门特性 下面是Web环境的一些特性,它们对搜索引擎的发展产生了重大影响.1)Web页面存储在大量的自治Web服务器中.需要一种方法来查找和获取这些Web页面,以便处理后供搜索用.2)大多数Web页面是HTML(HyperText Markup Langu