Let me explain CAP in purely intuitive terms. First, what C, A and P mean:
Consistency: From the standpoint of an external observer, each "transaction" either fully completed or is fully rolled back. For example, when making an amazon purchase the purchase confirmation, order status update, inventory reduction etc should all appear 'in sync' regardless of the internal partitioning into sub-systems
Availablility: 100% of requests are completed successfully.
Partition Tolerance: Any given request can be completed even if a subset of nodes in the system are unavailable.
What do these imply from a system design standpoint? what is the tension which CAP defines?
To achieve P, we needs replicas. Lots of em! The more replicas we keep, the better the chances are that any piece of data we need will be available even if some nodes are offline. For absolute "P" we should replicate every single data item to every node in the system. (Obviously in real life we compromise on 2, 3, etc)
To achieve A, we need no single point of failure. That means that "primary/secondary" or "master/slave" replication configurations go out the window since the master/primary is a single point of failure. We need to go with multiple master configurations. To achieve absolute "A", any single replica must be able to handle reads and writes independently of the other replicas. (in reality we compromise on async, queue based, quorums, etc)
To achieve C, we need a "single version of truth" in the system. Meaning that if I write to node A and then immediately read back from node B, node B should return the up-to-date value. Obviously this can't happen in a truly distributed multi-master system.
So, what is the solution to your question? Probably to loosen up some of the constraints, and to compromise on the others.
For example, to achieve a "full write consistency" guarantee in a system with n replicas, the # of reads + the # of writes must be greater or equal to n : r + w >= n. This is easy to explain with an example: if I store each item on 3 replicas, then I have a few options to guarantee consistency:
A) I can write the item to all 3 replicas and then read from any one of the 3 and be confident I'm getting the latest version B) I can write item to one of the replicas, and then read all 3 replicas and choose the last of the 3 results C) I can write to 2 out of the 3 replicas, and read from 2 out of the 3 replicas, and I am guaranteed that I'll have the latest version on one of them.
Of course, the rule above assumes that no nodes have gone down in the meantime. To ensure P + C you will need to be even more paranoid...
There are also a near-infinite number of 'implementation' hacks - for example the storage layer might fail the call if it can't write to a minimal quorum, but might continue to propagate the updates to additional nodes even after returning success. Or, it might loosen the semantic guarantees and push the responsibility of merging versioning conflicts up to the business layer (this is what Amazon's Dynamo did).
Different subsets of data can have different guarantees (ie single point of failure might be OK for critical data, or it might be OK to block on your write request until the minimal # of write replicas have successfully written the new version)
There is more to talk about, but let me know if this was helpful and if you have any followup questions, we can continue from there...
[Continued...]
The patterns for solving the 90% case already exist, but each NoSQL solution applies them in different configurations. The patterns are things like partitioning (stable/hash-based or variable/lookup-based), redundancy and replication, in memory-caches, distributed algorithms such as map/reduce.
When you drill down into those patterns, the underlying algorithms are also fairly universal: version vectors, merckle trees, DHTs, gossip protocols, etc.
The same can be said for most SQL solutions: they all implement indexes (which use b-trees under the hood), have relatively smart query optimizers which are based on known CS algorithms, all use in-memory caching to reduce disk IO. The differences are mostly in implementation, management experience, toolset support, etc
unfortunately I can't point to some central repository of wisdom which contains all you will need to know. In general, start with asking yourself what NoSQL characteristics you really need. That will guide you to choosing between a key-value store, a document store or a column store. (those are the 3 main categories of NoSQL offerings). And from there you can start comparing the various implementations.
[Updated again 4/14/2011]
OK here's the part which actually justifies the bounty.. I just found the following 120 page whitepaper on NoSQL systems. This is very close to being the "NoSQL bible" which I told you earlier doesn't exist. Read it and rejoice :-)
There are many applications where eventual consistency is fine. Consider Twitter as a rather famous example. There's no reason that your "tweets" have to go out to all of your "followers" instantaneously. If it takes several seconds (or even minutes?) for your "tweet" to be distributed, who would even notice?
If you want non-web examples, any store-and-forward service (like email and USENET) would be require eventual consistency.
It's not impossible to get transactions or consistency in NoSQL. A lot of people define NoSQL in terms of a lack of transactions or as requiring eventual consistency at best, but this isn't accurate. There are transactional nosql products out there - consider tuple spaces, for example - that scale very well even while providing app consistency.
发布评论
评论（3）
让我用纯粹直观的术语来解释 CAP。首先，C、A、P 的含义：
一致性：从外部观察者的角度来看，每个
“事务”要么完全完成，要么完全回滚。例如，
在亚马逊购买时，购买确认、订单状态
更新、库存减少等都应该“同步”出现
无论内部划分为子系统
可用性：100% 的请求成功完成。
分区容错性：任何给定的请求都可以完成，即使
系统中的节点子集不可用。
从系统设计的角度来看，这些意味着什么？ CAP 定义的张力是什么？
为了实现P，我们需要副本。很多！我们保留的副本越多，即使某些节点离线，我们所需的任何数据也可用的机会就越大。对于绝对“P”，我们应该将每个数据项复制到系统中的每个节点。 （显然，在现实生活中，我们会在 2、3 等方面做出妥协）
为了实现 A，我们不需要单点故障。这意味着“主/从”或“主/从”复制配置将不再适用，因为主/主是单点故障。我们需要使用多个主配置。为了实现绝对的“A”，任何单个副本都必须能够独立于其他副本处理读取和写入。 （实际上，我们在异步、基于队列、仲裁等方面做出了妥协）
为了实现 C，我们需要系统中的“单一版本的事实”。这意味着如果我写入节点 A，然后立即从节点 B 读回，节点 B 应该返回最新值。显然这在真正的分布式多主系统中是不可能发生的。
那么，您的问题的解决方案是什么？可能是为了放松一些限制，并在其他方面做出妥协。
例如，要在具有 n 个副本的系统中实现“完全写入一致性”保证，读取次数 + 写入次数必须大于或等于 n ：r + w >这很容易用一个例子来解释：如果我将每个项目存储在 3 个副本上，那么我有几个选项来保证一致性：
A) 我可以将项目写入所有 3 个副本，然后读取从这 3 个中的任何一个，请相信我会获得最新版本
B) 我可以将项目写入其中一个副本，然后读取所有 3 个副本并选择 3 个结果中的最后一个
C) 我可以写入 3 个副本中的 2 个，并从 3 个副本中的 2 个读取，并且我保证我将在其中一个副本上拥有最新版本。
当然，上述规则假设在此期间没有节点发生故障。为了确保 P + C，你需要更加偏执......
还有近乎无限数量的“实现”黑客 - 例如，如果存储层无法写入最小仲裁，则它可能会导致调用失败，但即使返回成功后，也可能会继续将更新传播到其他节点。或者，它可能会放松语义保证，并将合并版本控制冲突的责任推到业务层（这就是亚马逊的 Dynamo 所做的）。
不同的数据子集可以有不同的保证（即，对于关键数据来说，单点故障可能是可以的，或者可以阻止写入请求，直到最小数量的写入副本成功写入新版本）
。谈论，但请告诉我这是否有帮助，如果您有任何后续问题，我们可以从那里继续...
[继续...]
解决 90% 情况的模式已经存在，但每个 NoSQL 解决方案将它们应用于不同的配置。这些模式包括分区（基于稳定/散列或基于变量/查找）、内存缓存中的冗余和复制、分布式算法（例如映射/归约）。
当您深入研究这些模式时，底层算法也相当通用：版本向量、merckle 树、DHT、gossip 协议等。
对于大多数 SQL 解决方案来说也是如此：它们都实现了索引（在下使用 b 树） the hood），具有基于已知 CS 算法的相对智能的查询优化器，全部使用内存缓存来减少磁盘 IO。差异主要体现在实施、管理经验、工具集支持等方面，
不幸的是我无法指出一些包含您需要了解的所有知识的中央知识库。一般来说，首先要问自己真正需要什么 NoSQL 特性。这将指导您在键值存储、文档存储或列存储之间进行选择。 （这些是 NoSQL 产品的 3 个主要类别）。从那里您可以开始比较各种实现。
[再次更新 4/14/2011]
好的，这是真正证明赏金合理的部分..
我刚刚找到了以下关于 NoSQL 系统的 120 页白皮书。这非常接近于我之前告诉过你的“NoSQL 圣经”并不存在。阅读它并感到高兴 :-)
NoSQL 数据库，Christof Strauch
Let me explain CAP in purely intuitive terms. First, what C, A and P mean:
Consistency: From the standpoint of an external observer, each
"transaction" either fully completed or is fully rolled back. For example,
when making an amazon purchase the purchase confirmation, order status
update, inventory reduction etc should all appear 'in sync'
regardless of the internal partitioning into sub-systems
Availablility: 100% of requests are completed successfully.
Partition Tolerance: Any given request can be completed even if a
subset of nodes in the system are unavailable.
What do these imply from a system design standpoint? what is the tension which CAP defines?
To achieve P, we needs replicas. Lots of em! The more replicas we keep, the better the chances are that any piece of data we need will be available even if some nodes are offline. For absolute "P" we should replicate every single data item to every node in the system. (Obviously in real life we compromise on 2, 3, etc)
To achieve A, we need no single point of failure. That means that "primary/secondary" or "master/slave" replication configurations go out the window since the master/primary is a single point of failure. We need to go with multiple master configurations. To achieve absolute "A", any single replica must be able to handle reads and writes independently of the other replicas. (in reality we compromise on async, queue based, quorums, etc)
To achieve C, we need a "single version of truth" in the system. Meaning that if I write to node A and then immediately read back from node B, node B should return the up-to-date value. Obviously this can't happen in a truly distributed multi-master system.
So, what is the solution to your question? Probably to loosen up some of the constraints, and to compromise on the others.
For example, to achieve a "full write consistency" guarantee in a system with n replicas, the # of reads + the # of writes must be greater or equal to n : r + w >= n. This is easy to explain with an example: if I store each item on 3 replicas, then I have a few options to guarantee consistency:
A) I can write the item to all 3 replicas and then read from any one of the 3 and be confident I'm getting the latest version
B) I can write item to one of the replicas, and then read all 3 replicas and choose the last of the 3 results
C) I can write to 2 out of the 3 replicas, and read from 2 out of the 3 replicas, and I am guaranteed that I'll have the latest version on one of them.
Of course, the rule above assumes that no nodes have gone down in the meantime. To ensure P + C you will need to be even more paranoid...
There are also a near-infinite number of 'implementation' hacks - for example the storage layer might fail the call if it can't write to a minimal quorum, but might continue to propagate the updates to additional nodes even after returning success. Or, it might loosen the semantic guarantees and push the responsibility of merging versioning conflicts up to the business layer (this is what Amazon's Dynamo did).
Different subsets of data can have different guarantees (ie single point of failure might be OK for critical data, or it might be OK to block on your write request until the minimal # of write replicas have successfully written the new version)
There is more to talk about, but let me know if this was helpful and if you have any followup questions, we can continue from there...
[Continued...]
The patterns for solving the 90% case already exist, but each NoSQL solution applies them in different configurations. The patterns are things like partitioning (stable/hash-based or variable/lookup-based), redundancy and replication, in memory-caches, distributed algorithms such as map/reduce.
When you drill down into those patterns, the underlying algorithms are also fairly universal: version vectors, merckle trees, DHTs, gossip protocols, etc.
The same can be said for most SQL solutions: they all implement indexes (which use b-trees under the hood), have relatively smart query optimizers which are based on known CS algorithms, all use in-memory caching to reduce disk IO. The differences are mostly in implementation, management experience, toolset support, etc
unfortunately I can't point to some central repository of wisdom which contains all you will need to know. In general, start with asking yourself what NoSQL characteristics you really need. That will guide you to choosing between a key-value store, a document store or a column store. (those are the 3 main categories of NoSQL offerings). And from there you can start comparing the various implementations.
[Updated again 4/14/2011]
OK here's the part which actually justifies the bounty..
I just found the following 120 page whitepaper on NoSQL systems. This is very close to being the "NoSQL bible" which I told you earlier doesn't exist. Read it and rejoice :-)
NoSQL Databases, Christof Strauch
在许多应用程序中，最终一致性都很好。 Twitter 就是一个相当著名的例子。您的“推文”没有理由必须立即发送给所有“关注者”。如果您的“推文”需要几秒钟（甚至几分钟？）才能发布，谁会注意到？
如果您想要非 Web 示例，任何存储转发服务（如电子邮件和 USENET）都需要最终一致性。
There are many applications where eventual consistency is fine. Consider Twitter as a rather famous example. There's no reason that your "tweets" have to go out to all of your "followers" instantaneously. If it takes several seconds (or even minutes?) for your "tweet" to be distributed, who would even notice?
If you want non-web examples, any store-and-forward service (like email and USENET) would be require eventual consistency.
在 NoSQL 中获得事务或一致性并非不可能。许多人将 NoSQL 定义为缺乏事务或最多要求最终一致性，但这并不准确。有一些事务性的 nosql 产品 - 例如考虑元组空间 - 即使在提供应用程序一致性的同时也可以很好地扩展。
It's not impossible to get transactions or consistency in NoSQL. A lot of people define NoSQL in terms of a lack of transactions or as requiring eventual consistency at best, but this isn't accurate. There are transactional nosql products out there - consider tuple spaces, for example - that scale very well even while providing app consistency.