什么是分布式系统中的 CRDT？
What is CRDT in Distributed Systems?
我是分布式系统的新手，我想深入了解 CRDT 的概念。
我意识到它有三个符号：
Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type
谁能举个我们在分布式系统中使用CRDT的例子？
非常感谢。
这三个缩写词的扩展基本上都是同一个意思。
如果在不同序列中应用相同的操作产生（收敛）相同的结果，则 CRDT 是收敛的。也就是说，这些操作可以被交换——它是一个可交换的 RDT。操作可以以不同的顺序应用并仍然得到相同结果的原因是操作没有冲突。
所以 CRDT 的意思是一样的，无论你使用三个扩展中的哪个 - 尽管我个人更喜欢 "Convergent".
CRDT 的灵感来自 Marc Shapiro 的作品。在分布式计算中，无冲突复制数据类型（简称CRDT）是一种专门设计的数据结构，用于实现强最终一致性（SEC）和单调性（无回滚）。确保 SEC 有两种替代途径：基于操作的 CRDT 和基于状态的 CRDT。
不同副本上的 CRDT 可能彼此不同，但最后它们可以安全地合并，提供最终一致的值。换句话说，CRDT 有一个合并方法，它是幂等的、交换的和结合的。
这两种选择是等价的，因为一个可以模仿另一个，但是基于操作的 CRDT 需要通信中间件的额外保证。 CRDT 用于在网络中的多台计算机之间复制数据，无需远程同步即可执行更新。这将导致使用传统最终一致性技术的系统发生合并冲突，但 CRDT 的设计使得冲突在数学上是不可能的。在 CAP 定理的约束下，它们为 available/partition-tolerant (AP) 设置提供了最强的一致性保证。
使用它们的一些例子
Riak 是 CRDT 最流行的开源库，被 Bet365 和英雄联盟使用。下面是一些支持 Riak 的有用链接。
1- Bet365（使用 Erlang 和 Riak）
http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf
2- 英雄联盟为其游戏内聊天系统使用 Riak CRDT 实现（每秒处理 750 万并发用户和 11,000 条消息）
3- 由支持 LWW 时间戳集的 SoundCloud 实现的 Roshi：
-博客post：https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events
CRDTs 使用 Math 来强制跨分布式集群的一致性，而不必担心共识和相关的 latency/unavailability。
CRDT 可以随时取值的集合属于半格（特别是连接半格）的范畴，它是具有最小上界函数的 POSET（部分有序集） (LUB).
简单来说，POSET 是不是所有项目都具有可比性的项目集合。例如。在一对数组中：{(2,4), (4, 5), (2, 1), (6, 3)}、(2,4) < (4,5)，但不能与 (6,3) 进行比较（因为一个元素较大，另一个元素较小）。现在，半格是一个 POSET，其中给定 2 对，即使你不能比较两者，你也可以找到一个大于两者的元素 (LUB)。
另一个条件是对该数据类型的更新需要增加，CRDT 具有单调增加的状态，客户端永远不会观察到状态回滚。
这个excellent article以我上面用的数组为例。对于维护这些值的 CRDT，如果 2 个副本试图在 (4,5) 和 (6,3) 之间达成共识，他们可以选择一个 LUB = (6,5) 作为共识并将两个副本分配给它。由于值
正在增加，这是一个很好的选择。
CRDT 有 2 种方法可以跨副本保持同步，它们可以定期传输状态（收敛复制数据类型），或者它们可以在获取更新时传输更新（增量）（交换复制数据）类型）。前者需要更多的带宽。
SoundCloud 的 Roshi 是一个很好的例子（尽管它似乎不再开发），它们存储与时间戳相关的数据，其中时间戳显然是递增的。任何带有小于或等于存储的时间戳的更新都将被丢弃，这确保了幂等性（重复写入是可以的）和可交换性（乱序写入是可以的。可交换性是 a=b means b=a，在这种情况下意味着 update1 followed by update2 等同于 update2 followed by update1)
写入被发送到所有集群，如果某些节点由于缓慢或分区等问题而无法响应，它们预计稍后会通过 read-repair 赶上来，这确保了值收敛.可以通过我上面提到的 2 个协议实现收敛，将状态或更新传播到其他副本。我相信 Roshi 是前者。作为 read-repair 的一部分，副本交换状态，并且由于数据遵守半格 属性，它们会收敛。
PS。使用 CRDT 的系统最终是一致的，即它们在 CAP theorem.
中采用 AP（高可用和分区容错）
我是分布式系统的新手，我想深入了解 CRDT 的概念。 我意识到它有三个符号：
Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type
谁能举个我们在分布式系统中使用CRDT的例子？ 非常感谢。
这三个缩写词的扩展基本上都是同一个意思。
如果在不同序列中应用相同的操作产生（收敛）相同的结果，则 CRDT 是收敛的。也就是说，这些操作可以被交换——它是一个可交换的 RDT。操作可以以不同的顺序应用并仍然得到相同结果的原因是操作没有冲突。
所以 CRDT 的意思是一样的，无论你使用三个扩展中的哪个 - 尽管我个人更喜欢 "Convergent".
CRDT 的灵感来自 Marc Shapiro 的作品。在分布式计算中，无冲突复制数据类型（简称CRDT）是一种专门设计的数据结构，用于实现强最终一致性（SEC）和单调性（无回滚）。确保 SEC 有两种替代途径：基于操作的 CRDT 和基于状态的 CRDT。
不同副本上的 CRDT 可能彼此不同，但最后它们可以安全地合并，提供最终一致的值。换句话说，CRDT 有一个合并方法，它是幂等的、交换的和结合的。
这两种选择是等价的，因为一个可以模仿另一个，但是基于操作的 CRDT 需要通信中间件的额外保证。 CRDT 用于在网络中的多台计算机之间复制数据，无需远程同步即可执行更新。这将导致使用传统最终一致性技术的系统发生合并冲突，但 CRDT 的设计使得冲突在数学上是不可能的。在 CAP 定理的约束下，它们为 available/partition-tolerant (AP) 设置提供了最强的一致性保证。
使用它们的一些例子
Riak 是 CRDT 最流行的开源库，被 Bet365 和英雄联盟使用。下面是一些支持 Riak 的有用链接。
1- Bet365（使用 Erlang 和 Riak） http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf
2- 英雄联盟为其游戏内聊天系统使用 Riak CRDT 实现（每秒处理 750 万并发用户和 11,000 条消息）
3- 由支持 LWW 时间戳集的 SoundCloud 实现的 Roshi： -博客post：https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events
CRDTs 使用 Math 来强制跨分布式集群的一致性，而不必担心共识和相关的 latency/unavailability。
CRDT 可以随时取值的集合属于半格（特别是连接半格）的范畴，它是具有最小上界函数的 POSET（部分有序集） (LUB).
简单来说，POSET 是不是所有项目都具有可比性的项目集合。例如。在一对数组中：{(2,4), (4, 5), (2, 1), (6, 3)}、(2,4) < (4,5)，但不能与 (6,3) 进行比较（因为一个元素较大，另一个元素较小）。现在，半格是一个 POSET，其中给定 2 对，即使你不能比较两者，你也可以找到一个大于两者的元素 (LUB)。
另一个条件是对该数据类型的更新需要增加，CRDT 具有单调增加的状态，客户端永远不会观察到状态回滚。
这个excellent article以我上面用的数组为例。对于维护这些值的 CRDT，如果 2 个副本试图在 (4,5) 和 (6,3) 之间达成共识，他们可以选择一个 LUB = (6,5) 作为共识并将两个副本分配给它。由于值
正在增加，这是一个很好的选择。
CRDT 有 2 种方法可以跨副本保持同步，它们可以定期传输状态（收敛复制数据类型），或者它们可以在获取更新时传输更新（增量）（交换复制数据）类型）。前者需要更多的带宽。
SoundCloud 的 Roshi 是一个很好的例子（尽管它似乎不再开发），它们存储与时间戳相关的数据，其中时间戳显然是递增的。任何带有小于或等于存储的时间戳的更新都将被丢弃，这确保了幂等性（重复写入是可以的）和可交换性（乱序写入是可以的。可交换性是 a=b means b=a，在这种情况下意味着 update1 followed by update2 等同于 update2 followed by update1)
写入被发送到所有集群，如果某些节点由于缓慢或分区等问题而无法响应，它们预计稍后会通过 read-repair 赶上来，这确保了值收敛.可以通过我上面提到的 2 个协议实现收敛，将状态或更新传播到其他副本。我相信 Roshi 是前者。作为 read-repair 的一部分，副本交换状态，并且由于数据遵守半格 属性，它们会收敛。
PS。使用 CRDT 的系统最终是一致的，即它们在 CAP theorem.
中采用 AP（高可用和分区容错）