博文
CAP是什么东西？（120301）
|||
CAP是什么东西？（120301）
闵应骅
看见IEEE Computer 2月号上几乎全本都是CAP，我有些好奇。冷丁一看，我以为CFP，是Call For Papers。其实不是。大致了解一下，原来C是指Consistence（一致性），A是指Availability（可用性)，P是指Partition tolerance（分区容忍性)。在分布式计算系统中，所谓一致性就是所有节点在同一时间能看到相同的数据。因为数据不断更新。这一点是不容易做到的。可这很重要，我银行帐户里的钱不能说在北京看是10万，而在上海看只有1万。所谓可用性是指保证每一个请求都能得到一个成功或失败的响应。这个要求也很重要。如果用户的一个请求没有响应，未知可否，用户将无所适从，而给攻击者造成便利条件。所谓分区容忍性是指在信息丢失的情况下系统仍能继续工作。这一条也很重要，因为在网络环境下，信息丢失是不可避免的。不能说有信息丢失，系统就崩溃了。
2000年UC Berkely的Eric Brewer 提出一个猜想，说CAP这三点要同时做到是不可能的。到2002年MIT的Seth Gilbert和 Nancy Lynch给这个猜想来了一个形式的证明，而称之为Brewer猜想。此后，人们称这个结论为CAP定理。其证明的思路是给出一种情况，一个复制的服务碰到了两个在同一时刻不同地点的冲突的请求，而此时这二者的链路断了。为了在局部故障的情况下提供可用性，服务应该得到响应；可至少有一个响应与实现真正的一次复制语义的服务是不一致的。当然，最终达到一致是可能的。这段故事使我想起计算机科学怎么做基础研究。我们一般认为：计算机科学技术就是做系统、开发产品、提出一个方法，甚至是比照国外的一个什么技术，我们也扩充、推广、结合一番，很少有这种基础性的研究。
从工业界来看，最近海量数据形成所谓“数据雪崩”，传统的关系数据库管理系统碰到了严重的问题，而需要高度可扩展的数据库系统。由于现在商用服务器很便宜。公用和私用云存储可以处理大数据，而进入分布式系统。
为了管理指数竲长的数据流量，Google, Amazon, Yahoo, Facebook, Twitter开发了许多变通的办法，像NoSQL数据库，它不用SQL，而成为开放式的非关系型的分布式数据库。它通过数据中心存储和复制数据，以提高可扩展性和可靠性。为了容忍网络分区和限制写入潜在期，这些系统放宽一致性要求，数据更新可以不同步，而数据冲突在读入时检查。但是，当数据中心多起来以后，仍然有一致性的问题。
CAP定理的基础研究表明：这三个要素最多只能同时实现两点，不可能三者兼顾。因此在进行分布式架构设计时，必须做出取舍。而对于分布式数据系统，分区容忍性是基本要求，否则就失去了价值。因此设计分布式数据系统，就是在一致性和可用性之间取一个平衡。现在工业界用的就是牺牲一致性而换取高可用性。当然，牺牲一致性，只是不再要求关系数据库中的强一致性，而是只要系统能达到最终一致性即可。考虑到客户体验，这个最终一致的时间窗口，要尽可能的对用户透明，也就是需要保障“用户感知到的一致性”。通常是通过数据的多份异步复制来实现系统的高可用和数据的最终一致性的。这可以说是基础研究引领产品开发的一个例子。
我相信，这些类似的例子在计算机科学技术里面还会有。希望我们国家的科学家也在这方面做出一些原创性的工作来。
https://wap.sciencenet.cn/blog-290937-542808.html
上一篇：祖师爷图灵诞辰100周年纪念（120214）
下一篇：磁计算机（120310）
闵应骅
看见IEEE Computer 2月号上几乎全本都是CAP，我有些好奇。冷丁一看，我以为CFP，是Call For Papers。其实不是。大致了解一下，原来C是指Consistence（一致性），A是指Availability（可用性)，P是指Partition tolerance（分区容忍性)。在分布式计算系统中，所谓一致性就是所有节点在同一时间能看到相同的数据。因为数据不断更新。这一点是不容易做到的。可这很重要，我银行帐户里的钱不能说在北京看是10万，而在上海看只有1万。所谓可用性是指保证每一个请求都能得到一个成功或失败的响应。这个要求也很重要。如果用户的一个请求没有响应，未知可否，用户将无所适从，而给攻击者造成便利条件。所谓分区容忍性是指在信息丢失的情况下系统仍能继续工作。这一条也很重要，因为在网络环境下，信息丢失是不可避免的。不能说有信息丢失，系统就崩溃了。
2000年UC Berkely的Eric Brewer 提出一个猜想，说CAP这三点要同时做到是不可能的。到2002年MIT的Seth Gilbert和 Nancy Lynch给这个猜想来了一个形式的证明，而称之为Brewer猜想。此后，人们称这个结论为CAP定理。其证明的思路是给出一种情况，一个复制的服务碰到了两个在同一时刻不同地点的冲突的请求，而此时这二者的链路断了。为了在局部故障的情况下提供可用性，服务应该得到响应；可至少有一个响应与实现真正的一次复制语义的服务是不一致的。当然，最终达到一致是可能的。这段故事使我想起计算机科学怎么做基础研究。我们一般认为：计算机科学技术就是做系统、开发产品、提出一个方法，甚至是比照国外的一个什么技术，我们也扩充、推广、结合一番，很少有这种基础性的研究。
从工业界来看，最近海量数据形成所谓“数据雪崩”，传统的关系数据库管理系统碰到了严重的问题，而需要高度可扩展的数据库系统。由于现在商用服务器很便宜。公用和私用云存储可以处理大数据，而进入分布式系统。
为了管理指数竲长的数据流量，Google, Amazon, Yahoo, Facebook, Twitter开发了许多变通的办法，像NoSQL数据库，它不用SQL，而成为开放式的非关系型的分布式数据库。它通过数据中心存储和复制数据，以提高可扩展性和可靠性。为了容忍网络分区和限制写入潜在期，这些系统放宽一致性要求，数据更新可以不同步，而数据冲突在读入时检查。但是，当数据中心多起来以后，仍然有一致性的问题。
CAP定理的基础研究表明：这三个要素最多只能同时实现两点，不可能三者兼顾。因此在进行分布式架构设计时，必须做出取舍。而对于分布式数据系统，分区容忍性是基本要求，否则就失去了价值。因此设计分布式数据系统，就是在一致性和可用性之间取一个平衡。现在工业界用的就是牺牲一致性而换取高可用性。当然，牺牲一致性，只是不再要求关系数据库中的强一致性，而是只要系统能达到最终一致性即可。考虑到客户体验，这个最终一致的时间窗口，要尽可能的对用户透明，也就是需要保障“用户感知到的一致性”。通常是通过数据的多份异步复制来实现系统的高可用和数据的最终一致性的。这可以说是基础研究引领产品开发的一个例子。
我相信，这些类似的例子在计算机科学技术里面还会有。希望我们国家的科学家也在这方面做出一些原创性的工作来。
https://wap.sciencenet.cn/blog-290937-542808.html
上一篇：祖师爷图灵诞辰100周年纪念（120214）
下一篇：磁计算机（120310）
