如何打败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只有几千行代码。

待续..

                   

24
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数据库能更好展现逻辑。关系数据库的数据平铺方式,使得查询速度极快,同时实现了逻辑查询,但这并非从实现“产生事实的逻辑”角度出发的——事件的角度。

好了,就说这么多。

3Go 1 2 3 下一页