如何打败CAP定理?

11-10-14 banq
一篇谈使用读写分离方式实现如何打败CAP定理文章,可以认为是Event Sourcing的一个变种。

CAP定理认为一致性 可用性和分区容错性同时不能获得,通常我们不能丧失分区容错性,那么你就只有在可用性和一致性之间选择,这就催生了NoSQL运行。

一致性意味着你实现一个成功的写以后,将来的读到的总是写的最新结果;可用性意味着你总是能对系统进行读写,在一个分区分布式系统,你只能拥有他们其中一个。

两者权衡时,如果一致性超过可用性,那么如果数据库不能用怎么办?你所做的是将写缓冲起来后来再写,但是所冒风险当这台服务器当机缓冲就丢失,当一个客户端认为写已经成功,但是实际在缓冲中没有写到数据库,就会发生不一致性. 替代方案是你返回错误给这个客户端,说数据库不可用,try again,用户使用这样的产品感受是如何呢?

如果你选择可用性高于一致性, 通过最终一致性实现,使用最终一致性情况下,你可能读取到和你刚才写入的不是同一个数据,有时多个读者读取同样的Key总是得到不同的结果,更新也许不可能传播到所有副本,这样你的一些副本更新了,另外的也许没有更新,这就需要跟踪历史,使用vector clocks 或将更新融合的方式(称为 "read repair").

维护一个最终一致性的应用是一个非常沉重的认为,read repair将受开发人员的粗心等错误影响,一旦read repair有问题,将引入数据库不可逆转的腐败性。

这样,逃避可用性系统不能使用有问题,最终一致性又带来复杂性,又有什么替代方案呢?

你不能逃避CAP,但是能够隔离复杂性,将其不再影响你的大部分系统;CAP引起的复杂性其实来自于我们数据系统,数据系统的根本问题是:数据库中保存的是可变数据,然后有一个增量算法在不断更新这个数据状态,这个交互过程本身带来了复杂性。

CAP定理是数据系统相对机器出错后的容错级别,还有一种容错方式:人工容错,那是开发人员不够完美,Bugs等被带入系统产品,我们数据系统必须忍受有Bug的程序写入坏数据,作者展示的一个能够打败CAP的系统也将展示如何达到更好的人工容错。

作者认为他的方案更加优雅 可扩展性和健壮性。

作者首先发问:什么是数据系统,他认为可以用下面公式简单定义:

Query = Function(All Data)

所有数据系统都可以用这个公式表达,数据系统是回答关于数据集的问题,这些问题是查询Queries, 查询的都是数据,因此Query和Data是两个重要概念。

数据有两个重要属性:首先数据是基于时间的,数据是表达一段时间内一个逻辑为真的事实。另外一个属性是数据本质上是不可变的,因为和时间有关,我们是不能回到过去改变数据的真实性。

这两个属性就意味着:对数据你其实只有两个主要的操作:读取现有数据,并(随着时间)添加更多新的数据,CRUD(增删改查)称为CR(增读)。

这样,CRUD其实没有U修改,因为修改对不可变数据是不其作用的(非常类似DDD中值对象不可变,不能修改,只能更换)。

CRUD中也没有删除Delete,其实大部分删除其实是一种创建新数据,如果Bob停止跟随Mary,但是他们不能改变他曾经跟随过他的事实,删除那个他不跟随她的数据,你会增加一个数据记录,说他在某个时刻不再跟随她了。

作者随后解释了他的这套数据定义和普通没有什么不同(banq认为实际是从业务领域带有OO概念或者说业务逻辑去理解了,对于我们理解了面向对象,事件和状态以及与事实之间关系,这些定义非常容易理解和得到认同)。

下面是对Query查询,查询是一种计算功能,你可以通过查询实现很多功能,聚合,join不同数据类型等等。查询是对整个数据集的一种功能,当然很多查询不需要整个数据集,仅仅需要一个子集,这也不影响查询这个定义。

查询可以看成不可变数据的读,对于一个分布式系统大数据,如果一个每次都是从头开始查询的响应时间又在允许的延迟内

(从头查询因为有新数据加入),那么是否可以认为我们实际通过不可变数据和查询避免了CAP定理?

当然CAP定理还会起作用,关键是不可变数据,这样就避免了数据更新,那就不可能有那么多数据片变成不一致,那就意味着没有vector clocks, or read-repair,只有数据和数据上的查询功能,你就不必面对最终一致性。

之前引起复杂性是增量更新和CAP定理,这两个真的无法很好在一起工作,可变的值需要read=repair,通过拒绝增量更新,强迫不可变数据,从头计算每次查询,你能避免复杂性。

这个方案中挑战性工作是每次都从头计算的查询,这种查询是一种预计算的批处理查询,所幸的是我们有Hadoop,它是进行批处理的最好工具。

使用Thrift和Protocol Buffers可以让Hadoop处理结构化数据,Hadoop由两个部分:分布式文件系统HDF和批处理框架MapReduce,我们将数据不断加入HDFS中,一种Append方式;而预先计算查询依靠MapReduce,也有更易使用的工具: Cascalog, Cascading, and Pig

最好,你需要将预计算的结果索引,这样结果能够被应用很快访问,有一个数据库可以做到这点:ElephantDB and Voldemort read-only

这两个是能够为查询从Hadoop中将key/value数据导出,这些数据库支持批量写和随机读,但是不支持随机写,随机写是数据库中最复杂的,通过不支持能够实现更加简单健壮,ElephantDB只有几千行代码。

待续..

26
banq
2011-10-14 18:49
案例:如果你正在建立一个通过跟踪pageView实现的Web分析应用。你需要每隔一段时间查询PageView的数值:

每个数据记录包含一个page view. 这些数据都保存在HDFS文件中,每个小时通过URL来统计PageView,这作为MapReduce jobs. 发出key是[URL, hour],每个value值死页面访问量,这些key/value数据被导出到ElephantDB数据库中,这样应用程序能够更快地获得[URL, hour]的值. 当应用系统需要知道一段时间内的pageView时,它会查询那段时间内每个小时的PageView数值,然后将它们加在一起得到最后结果。

批处理可以计算有关任何数据的任何功能,这样就可以解决大部分问题,更重要的是它简单可扩展,你只要思考数据和功能,Hadoop为你考虑并行处理。

关于人工容错,因为数据是不可变的,数据集只能append追加,即使有bug的应用程序写入坏数据,也不会覆盖好数据,这是因为没有更新update。

即使MVCC 和 HBase row versioning也不能永远实现人工容错,一旦数据库影响到了行,旧数据已经丢失。

(banq注:不断append追加的好像应该是事件这样的数据,这样新事件不会覆盖旧事件,我们通过事件回放能够找到某个时间段的数据。见Martin fowler的Evetn sourcingLMAX架构)

以上查询是几个小时前的预处理查询,如何实现实时查询呢?需要一个实时系统和前面提到的批处理系统并行运行:

实时系统可以使用依赖修改的 Riak 或 Cassandra, 这些都依赖于增量算法和状态更新。

模拟Hadoop的实时计算是Storm,下面是这样的一个结合并行系统:

Hadoop 和 ElephantDB预先计算几个小时前的数据,最近几个小时数据都在实时系统中计算。

虽然实时系统我们也使用了NoSQL,但是是否又回到了CAP定理的复杂性呢?非也,因为数据只是最近几个小时内的,当然,如果你在实时系统范了错误,也不可能完全丢失数据,因为批处理系统会帮助你纠正。

[该贴被banq于2011-10-14 19:00修改过]

banq
2011-10-14 19:00
这种实时系统使用Storm + Cassandra;批处理系统使用Hadoop + ElephantDB方式可以打败CAP定理,因为它隔离降低了CAP定理的复杂性原因。

作者以亲身经历说明这种方式的人工容错性:作者也没有什么系统监视工具,一天醒来,发现 Cassandra已经超出空间,每个请求都超时出错,这导致Storm当机,数据流被备份在消息队列中,因为消息发不出,一个消息 在那里不停地重复试图发出。(banq注:很显然是一种事件消息队列方式)

因为有批处理系统,作者清空这个队列中消息,重新部署Cassandra,批处理系统象顺时针钟一样几个小时内又恢复正常工作。无数据丢失和不正常查询结果。

垃圾数据回收可以避免数据集随着时间推移越来越大。

最后,作者总结了这种批处理/实时( batch/realtime)结合的架构的好处。

相关其他文章:

为什么要用Event Sourcing?

LMAX架构

闲话淘宝网和新浪微博架构

罗素摹状词理论与面向对象OO(讨论数据与事实的关系,与时间有关的数据准确称是状态,事件是触发状态的因,因此事件与事实最接近)

[该贴被banq于2011-10-15 08:19修改过]

banq
2011-10-16 07:27
2011年10月14日 19:00 "@banq"的内容
数据有两个重要属性:首先数据是基于时间的,数据是表达一段时间内一个逻辑为真的事实。另外一个属性是数据本质上是不可变的,因为和时间有关,我们是不能回到过去改变数据的真实性。 ...

作者这篇文章提出的数据两个重要属性解决了状态和值对象问题,这倒让我想起了SpeedVan的帖子:SpeedVan认为的VO

“数据是表达一段时间内一个逻辑为真的事实”准确名称应为状态,这样能够区别于数据的其他用途;既然状态都是发生过的,那么我们就无法改变,也就是具有不可变性,这种观点也符合我在jivejdon中提出状态是值对象的观念:http://www.jdon.com/mda/ddd.html

当我们认识到状态是一种值对象,是不可变的,那么在对待大数据Big Data情况下,我们采取实时和批处理分离的CQRS架构,就完全符合逻辑。

也由此可见:与其说架构离不开数据结构,不如说架构离不开业务分析,这两者等同的。海量数据抛弃OO说法是片面的,也符合Disruptor并发框架的LMAX团队认为的:Modelling Is Everything

http://www.jdon.com/jivejdon/thread/42571#23136377

[该贴被banq于2011-10-16 11:08修改过]

SpeedVan
2011-10-18 17:06
其实状态变化有两种思维:一种是过程形式,一种是逻辑形式。

过去我们的实体都是列出对其认识的内在属性,当事件发生致使实体发生变化时,往往就是加锁后逐一改变,或者事务方式(类似副本方式)。“逐一改变”就是过程式,具体详细地描述变化过程,于是在并行的时候缺失原子性,为了实现避免脏读等问题,加锁成了一种手段。当然,事务方式也解决了这样的问题,这与非副本的不变值对象方式,是达到同样目的的不同方式,同时这两者都属于逻辑表达。以前我作过比较,在领域当中谈论逻辑变化,我认为后者较好。

值对象是实体状态的一种落实,我过去提出过的观点,这是源自于状态变化的逻辑形式思维。谈论逻辑时,状态迁移必须具有原子性,所以我在某个帖子说值对象不变性,可以达到去锁的目的。

(注意:值对象不变性源自值,并非因为实体状态,是因为值对象具有值的不变性,所以才能成为实体状态的落实。)

一些更深入的认识:

存在状态变化即存在副作用(side effect),所以实体是副作用存在的因。很多人认为副作用是坏的,应该去掉,但这只限于逻辑运算时。只要人们想获得信息,副作用就根本不能避免,最容易理解就是print。

可变的实体与不可变的状态,正好就是副作用存在的分界线。实体之所以会存在,其实是因为人们想获取信息,于是值对象(值)载体便出现了——引用对象(即实体对象)。

状态迁移,就是实体发生变化,它说明实体从一个状态迁移到另一个状态。这里面最小单元是状态,也就是说我们考虑的不是状态的构成及其内在变化(逐一改变),而是计算出新状态,然后以“替换”的手段来实现实体变化。这与我们所说到的值对象不变性和事实是最小单元如出一辙。(所以“状态迁移”是一种事实观)

banq说的『“数据是表达一段时间内一个逻辑为真的事实”准确名称应为状态』,这句话很好说明了事实观与实体观的联系。

过去我思考“什么是实体”,其实实体很简单,就是一个KEY,是为了区别与其他存在的存在。而我们写类的时候,其中的id并非实体KEY,而“类名+类id”才是实体KEY。所以关系数据库中表方式与类方式类似,并不完全满足事实观,而key-value数据库能更好展现逻辑。关系数据库的数据平铺方式,使得查询速度极快,同时实现了逻辑查询,但这并非从实现“产生事实的逻辑”角度出发的——事件的角度。

好了,就说这么多。

banq
2011-10-18 17:50
2011年10月18日 17:06 "@SpeedVan"的内容
过去我思考“什么是实体”,其实实体很简单,就是一个KEY ...

是的,数据可以是实体,可以是值对象,Key的数据就是实体;Value就是值对象,Key/Value = 实体/值对象. Key/Value等NoSQL数据库也就是天然实体/值对象的存储持久库了。

过段时间我们准备写一个关于不变性的文章,我正在拓展抽象,拟取名为immutable is eveything,不可变是一切。

过去,我提出Cache is King,缓存是国王,那么缓存更新怎么办?是一个难题,暴风式的同时更新复制数据肯定不行,这就要引入Vector Clock这些复杂的算法,而且一致性不一定好,而不可变性是解决这个问题一把钥匙,目标实际就是缩小数据复制更新的范围,降低“修”改范围。

不可变性实际是对对象或数据的生命周期Scope or lifecycle的一种思考基础上的提上。

比如为什么有可变状态和不可变状态?实际是你的划分时间边界不同,可变和不可变是相对而言的,每小时变化一次相对于每分钟变化一次就是算不可变的,但是对于每天变化一次又是可变状态。

无论可变状态和不可变状态,本质上都是不可变的,取决于你的时间边界不同,楼主这篇文章他就把几个小时以上数据不变的加入批处理系统,成为不可变的。

但是区分可变状态和不可变状态,又很重要,因为这决定我们的值对象使用方式,如果每秒快速变化的状体,我们使用值对象的复制方式,也就是每次变化更好一个新的值对象状态,无疑临时大量垃圾对象太多,DDD推荐用Flyweight,并且以房间插座为案例,一个房间如果有百个插座,太琐碎了。

所以,我探索总结出,根据状态是由事件行为引起的原理,从事件行为来划分,比如CRUD增删改查四个动作,对于Read因为频繁,每次读都引起状态变化,比如帖子阅读次数,每次读都要加一,如果设计为值对象就产生太多垃圾,采取值对象共享方式,然后对其中字段AtomicLong进行自增,AtomicLong是并行编程的最基础的用法。

如果是创建或修改等动作引起的状态变化,这时可以用值对象复制,每次变化New一个新值对象,然后覆盖原来的,setVO(new VO)即可,无锁,无Blocking,并发。

以上是适合在一个机器内存中,如果把这个思路延展开来,就是楼主上面的批处理/实时结合的大型架构,其实原理和一个内存中类似。

SpeedVan
2011-10-18 18:38
2011年10月18日 17:50 "@banq"的内容
如果设计为值对象就产生太多垃圾,采取值对象共享方式,然后对其中字段AtomicLong进行自增,AtomicLong是并行编程的最基础的用法。 ...

对于不完全对象语言的确有这样的说法,其实若果在完全对象语言中,值对象已经包括AtomicLong的实例,原子性操作的基本类型,本身就是值对象类的一种,在语言中“增1”实际上就是一个原子性操作,它致使“增1”前后两个状态可以相互独立。

我们可以这么想,基本类型变量的变化,是编程中,最小单元,最快,最可靠的状态迁移。

Flyweight思想,我觉得很重要,当年java的String改写原因也正因为大量字符串对象原因。试想,若果1000次运算得出1000个完全不同的字符串,那么Flyweight在此时就失效了。这种效果跟值对象运用Flyweight的效果几乎相同,当然我们设计的值对象一般是几倍,甚至几十倍的String,受一些因数影响会妥协一下,但不代表不能从另外一些方式来解决,我也正致力于这方面的探讨。

banq
2011-10-19 09:26
很巧,在stackoverflow看到这个帖子:在Scala中如何协调不可变和引用有段回复:

原文:

The immutability exists not for the sake of itself. Immutability is abstraction. It does not "exist" in nature. World is mutable, world is permanently changing.....

大意是:不可变性是一种抽象,它并不在自然界中存在,世界是可变的,持续不断变化。所以数据结构是可变的,他们是描述真实世界某段时间内的状态,这个看上去类似OOP设计,核心概念是:在内存中对象object in RAM 并不一定等于真实的对象,数据会有不准确,带来延迟。

在大部分琐碎的需求中将一切看成是可变的也许没有问题,但是当下面情况就不同了:

1.数据结果被并发线程同时修改

2.多个用户对一个共享对象进行冲突性修改。

3.用户提供了无效数据,应该被回滚。

在自然可变的模型下,你会在这些情况下发生不一致性或破碎crushing,显然可变性很容易导致错误。

你需要的是一种新视野,新角度,一种事务transaction视野,当你从事务性程序中看世界时,一切都是不可变的,STM软事务可以以线程安全方式管理一致性。

完毕。

个人认为:事务性=逻辑性=不变性。

世界本为无,道生一,一生二, 1+2 =3, 逻辑诞生了有。世界本变化,逻辑让我们看到了不变性的道。

相关文章:

蒯因与引用透明

[该贴被banq于2011-10-19 19:54修改过]

SpeedVan
2011-10-21 07:46
2011年10月19日 09:26 "@banq"的内容
大意是:不可变性是一种抽象,它并不在自然界中存在,世界是可变的,持续不断变化。所以数据结构是可变的,他们是描述真实世界某段时间内的状态,这个看上去类似OOP设计,核心概念是:在内存中对象object in RAM 并不一定等于真实的对象,数 ...

一、

其实这就是一种“连续”和“离散”思维的区别,尽管世界在我们感官中是连续的,但连续过程和中间的“切面状态”不是我们关注的,业务说的是规则,是逻辑的,正如我们经常说的“业务逻辑”。在规则或者逻辑中,不存在所谓的切面状态。例如“借书”这一个原子动作,有人会“借一半”,或者说“借一半”是我们所关注的状态?

二、

若果我们一个个地改属性,当改了第一个属性值,没改第二个属性值时,这就存在了所谓的切面状态。单线程时,因为顺序执行,不会读出切面状态,变相成为原子操作,但多线程并发时,读出无效的切面状态是可能的。解决的方式:

1)改的时候不能读,就是我们以前用得最多的锁;

2)随时可读,改的时候必须“同一时间”完全改完,而这就是不变性的整体替换;

3)当然后来又想到一种,读与改不会同时进行,暂时感觉比较复杂,没有深入,浅思考了下,感觉实时相对较弱。

三、

还有一点,事务性和不变性,个人认为两者很像,但又有点不同:

事务讲究复制隔离,达到不相互影响,而且最后也需要替换。

不变性无需复制,因为其一开始就要求在逻辑运算期间是“不能改”。

两者相似点:

1)并行时都是相互不影响;

2)更新时都是替换手段。

不同点:

1)事务的参与逻辑是在逻辑执行前就复制好,得到隔离性;事务包装整个过程,实现原子性。

2)不变性方式的“结果对象”是在逻辑执行完后,根据各种条件创建的,其原子性体现在替换,并不是包装过程。

总的来说就是一前一后,事务有点像“平行世界”的概念。还有有趣的一点是,不变性前后两个状态不要求是同构的。不变性还有很多有趣的地方,这里就不一一列举了。而不变性也有缺点的,如要多对象同时改变时,需要机制来处理。

[该贴被SpeedVan于2011-10-21 08:28修改过]

banq
2011-10-21 10:59
2011年10月21日 07:46 "@SpeedVan"的内容
事务讲究复制隔离,达到不相互影响,而且最后也需要替换。

不变性无需复制,因为其一开始就要求在逻辑运算期间是“不能改”。 ...

总结得不错,使用不变性设计能够巧妙地实现事务,事务目的是ACID,原子性 隔离性等,事务是针对无法原子性的操作上的一种设计强迫,如果我们设计上能够自然实现原子性,就无需传统事务那些强制措施了,如锁 堵塞等等,这才真正符合老子大道自然的法则啊。

刚写了不变性immutablity设计,主要针对开发领域,“如何打败CAP定理”又是依据不变性来架构分布式大型云计算系统的,那么不变性设计可以说是统一贯穿于从单个CPU大到云计算一条主要设计原则。

为什么有这样大统一美妙大道至简的现象呢?因为计算机软件系统是本身是符号逻辑或者形式逻辑或分析逻辑的一种体现,而不变性是逻辑上的一个基础概念(蒯因与引用透明),如果你学习了分析逻辑的这个基础,你就找对了方向,但是如果你学习几十年数据结构和算法基础,你不一定能悟出其背后的逻辑真义。

[该贴被banq于2011-10-21 11:01修改过]

xmuzyu
2011-10-21 16:21
2011年10月18日 17:06 "@SpeedVan"的内容
值对象不变性源自值,并非因为实体状态,是因为值对象具有值的不变性,所以才能成为实体状态的落实。 ...

这里我的理解是:

实体状态的变化是相对于一个时间段内的,但是对于某一个时刻实体的状态,其实是静止,永恒的,比如上一秒中的自己和现在的自己肯定发生了变化,但是上一秒的自己已经永恒了,已经是一种过去的静止的状态了.正因为如此,所以我觉得值对象不变性的来自于实体状态在某个时间点上状态是静止的,是不变的,当到下一个时间点时候,可以通过另外一个状态(另外一个值对象)来替换掉原来的状态。

SpeedVan
2011-10-21 17:36
2011年10月21日 16:21 "@xmuzyu"的内容
所以我觉得值对象不变性的来自于实体状态在某个时间点上状态是静止的 ...

这里,我的想法有点不同,VO相对的是RO(ReferenceObject),独立于“状态、实体”概念的,或者说是不同层次的。只是VO和RO出现相对较早,而且比较吻合“状态、实体”概念。所以,值对象只是状态的落实,或者说实现。

“实体状态在某个时间点上状态是静止的”,瞬时的实体状态映射到计算机就是不变的数据,在对象思维中就是值对象。而实体则是RO,不过注意的是这个引用概念有点变化,并不是引用地址,而是变成实体KEY。

值对象的不变性是源自于值概念的,试想为啥非要叫做“值对象”,而不叫“不变对象”。

banq
2011-11-15 09:23
2011年10月14日 18:26 "@banq"的内容
模拟Hadoop的实时计算是Storm ...

该文章作者发布了和其开源Storm框架相结合的数据导入导出实现:

storm-kestrel: Adapter to use Kestrel as a spout

storm-amqp-spout: Adapter to use AMQP source as a spout

storm-jms: Adapter to use a JMS source as a spout

storm-pubsub: A spout that subscribes to a Redis pubsub stream。

https://github.com/nathanmarz/storm/wiki/Spout-implementations

猜你喜欢