CRDT是什么？Paxos? Raft?
CRDT是Conflict-Free Replicated Data Types的缩写，直译的话即“无冲突可复制数据类型”。
研究分布式系统，尤其是研究最终一致性分布式系统的过程中，一个最基本的问题就是，应该采用什么样的数据结构来保证最终一致性？ 这是一个关键的，难度超过一般人想象的问题。
CRDT即是理论界目前对于这个问题的答案（一篇集大成的论文在这里）。
当然理论界的思路现在不是所有人能跟上的，需要更加简单的解释。
一致性的难题
先回顾一下分布式系统。分布式系统即运行在多物理计算机上的系统。它的好处，不用说了，这是人类目前实际可行的构建超大规模系统的唯二办法之一（另一种就是构建超级计算机）。如果考虑上经济可行这个因素，那么分布式系统就是唯一可行之法。
CAP定理告诉我们，在构建分布式系统的时候，Consistency（一致性），Availability（可用性），Partition tolerance（分区容错性），这三者只可以同时选择两样。
即，就算给我们再多的资源（比如人力，智力，机器，钱这些壕的东西），在目前的计算机体系结构下，三样同时选择，理论上无可能的。如果谁做到了？就是不科学。
不幸的是，分区容错性是实际运营的分布式系统所必需的。设想下，谁能保证系统的各节点永远保持网络联通？ 这是不给GFW面子。
所以接下来我们需要在一致性和可用性中二选其一。
选择一致性，构建的就是强一致性系统，比如符合ACID特性的数据库系统。选择可用性，构建的就是最终一致性系统。前者的特点是数据落地即是一致的，但是可用性不能时时保证，这意思就是，有时系统在忙着保证一致性，无法对外界服务。后者的特点是时时刻刻都保证可用性，用户随时都可以访问，但是各个节点之间会存在不一致的时刻。
需要注意的是最终一致性的系统不是不保证一致性，而是不在保证可用性和分区容错性的同时保证一致性。
最终我们还是要在最终一致性的各节点之间处理数据，使他们达到一致。
再谈CRDT
想在实际系统中应用，我们必须要考虑更多的数据类型和应用场景。于是设计一个能够保持最终一致性的数据结构，就会变成一件很难的事情。甚至于这件事情本身会喧宾夺主，成为一个最终一致性系统中的最麻烦的问题。
有了这样的概念，现在我们可以回头看CRDT。
CRDT就是这样一些适应于不同场景的可以保持最终一致性的数据结构的统称。围绕着CRDT的理论，则涵盖了
- 它们应该具有怎样的基本表现形式，
- 满足一些什么样的基本条件才可以保持最终一致性（毕竟大家不想每次都穷举所有的情况），
- 以及在不断的寻找一些通用的，有大量应用场景的CRDT，并努力提高它们的空间和时间效率。
之前提到的那篇论文很好的总结了目前为止人们在CRDT这件事情上的认识程度。简要的总结，它
- 定义了CRDT
- 列举了CRDT的两种基本形式，即基于状态的CRDT与基于操作的CRDT。前者存储的是一个个的最终值，类似我们的例子，后者存储的是一个个的操作记录，类似于我们例子里面的推导过程
- 界定了CRDT能满足最终一致性的边界条件。简单说，设计一个CRDT，只需要验证它是否满足这些边界条件，即可知道它是否能保持最终一致
- 界定了两类CRDT在系统中应用时，需要的信息交换的边界条件。即回答怎样叫做“收集到足够多的信息”
- 枚举了当前人类所知的CRDT，包含了计数器(counter)，寄存器(register)，集合(set)和图(graph)等几类
- 在现实中应该如何应用CRDT，尤其是对于存储空间怎样进行回收的问题
简要的就是，这篇文章是一本字典，它包含了CRDT方面人类的知识结晶。
怎样在实际系统中应用
说了这么多，CRDT其实还是停留在纸上，或许对于系统构建者来说，更加关心怎么在自己的最终一致性系统中使用？以什么样的方式？
这样的问题或许太大，但是我们可以看看如何在RiakCore这样的最终一致性分布式框架中使用
- 抛弃自己所写的数据结构，实现CRDT，或者使用已经实现好的CRDT library
- 参照CRDT的一致性可判断条件（即"收集到足够多的信息"），在需要判断最终一致性时收集它们
- 抛弃自己所写的一致性判断算法，实现CRDT的一致性合并算法，或者使用已经实现好的存在于CRDT library中的方法
就是这样简单。
其实整个过程，与使用类似map/stack这样的数据结构并不不同的地方。
谁应该使用？谁在使用？
所有力求最终一致性的分布式系统，都应该使用CRDT。
如果一个最终一致的分布式系统至今还没有使用，那么要么是其所使用的数据结构已经实现了（很可能是粗糙的）CRDT的一种或者几种，要么是这个系统在最终一致性上的保证就存在问题。
至于谁在使用呢？应该说大部分的最终一致性系统都在自觉不自觉的向之迈进。Fifo已经全面的采用了; RiakKV也已经采用了，做为1.4版本的重要特性; 随着Riak_dt的开源，越来越多Erlang/OTP的程序也有希望尽快使用上CRDT。
Raft or CRDT or Paxos
用分布式系统的术语来说，两者是完全不同的，并且服务于非常不同的用例。虽然两者都旨在实现强大的一致性，但CRDT通常在不牺牲可用性的情况下这样做，而Raft这样做是以牺牲可用性为代价的。面对网络分区，CRDT将保持可用，但Raft群集可能会部分或完全不可用。Raft是一种共识算法，它依赖于群集中的大多数彼此通信来进行。
每个人可以管理的状态类型也有所不同。CRDT用来表示一组有限且定义明确的数据类型，而Raft和其他共识算法可用于对更广泛的潜在数据结构和算法进行建模。筏通常用于建模复制状态机。通过Raft算法记录并复制到状态机的命令，并将其应用于状态机。状态机可用于对诸如地图和集合之类的数据结构进行建模，或者通过对诸如锁，领导者选举和信号量之类的事物进行建模来控制并发性。
您还必须从可伸缩性角度看待您的系统，并且Raft和CRTD在这里也很重要。Raft是基于领导者的系统。Raft选择一个节点作为领导者，并且对Raft复制状态机的所有状态更改都将通过该单个领导者，并在应用于状态机之前被同步复制到大多数跟随者。另外，CRDT不受单个节点的限制，因此可伸缩性更高。
最终，筏和CRDT之间的差异是一致性和性能之间的差异。Raft旨在创建单个系统的一致视图，并着重于安全而不是性能。通常，诸如Raft之类的共识算法用于诸如配置管理和服务发现之类的事情。CRDT被设计为在不牺牲可用性的情况下尽可能快且一致。通常，CRDT用于存储在更多与可用性相关且不太重要的系统中。
CRDT和Paxos这类强一致性协议具有不同的目标，并且在不同的情况下使用。它们的共同点是可以帮助程序员处理并发/复制。CRDT是假设会发生并发更新的数据类型。Paxos是一种协议，通过对它们按照顺序强制执行来保证一致性。
使用Paxos可以保证每个副本将以相同顺序执行对集合的写入操作。更一般而言，它保证所有副本都同意集合状态的演变。
例如，如果您有user 1在 副本1上执行 update1，将 element1 添加到复制集中，而 user 2同时执行了 update2，在副本2上添加 element2，则Paxos将使副本就给定的更新顺序达成一致。或者可能同意选择一个副本根据您的使用方式和要实现的目标，丢弃第二个更新。
例如，如果 update1 在 update2 之前，那么每个副本将按该顺序更新集合。结果，与这些更新同时读取集的用户可以观察到，无论他们从何处（在哪个副本上）读取，都只能观察到集的以下状态（假设集在开始时为空）：
{}（空集）
{element1}
{element1，element2}
那么，更新完成之后，集合所有的结果都会同步为{element1，element2} 。
但如果两个副本无法互相通信（网络分区），则集合将无法更新，因为无法达成协议。
低性能，高延迟：协议要求副本在回复客户端之前进行同步。这会导致与副本之间的延迟成比例的延迟。
CRDT的保障较弱。CRDT集不等同于顺序的单副本集。假设在副本的更新方式上没有协议或总顺序。
CRDT保证：如果集合的两个副本都具有相同的更新（无论它们看到它们的顺序如何），那么它们将表现出相同的状态；副本将收敛。
积极的一面：高可用性：如果副本之间无法相互通信（网络分区），也可以更新。副本重新连接时，它们将进行同步，由于是最终一致性，所以此时看到的结果可能不是你期望的结果。
高性能，低延迟：副本服务器在回复客户端后立即回复客户端并在后台同步。
