An introduction to state-based CRDTs - 版本历史

Riguz：/* 接下来是什么？ */

2024-09-20T04:03:42Z

接下来是什么？

←上一版本		2024年9月20日 (五) 04:03的版本
第398行：		第398行：

	== 接下来是什么？ ==		== 接下来是什么？ ==
			有了我们武器库中的这一系列数据结构，我们可以构建更高级的类型：

			* 一个例子是最后写优先映射（Last-Write-Wins Map），它很像是<syntaxhighlight lang="fsharp" inline>type LWWMap<'k,'v> = ORSet<('k * LWWReg<'v>)></syntaxhighlight>（记住，比较算法应该只比较key）
			* 另一个例子是图数据结构，它由两个集合构成：一个节点集合和一个边集合

			你可能已经看到，这是一个非常庞大的主题而且在我看来是十分有趣的。
			还有很多其他的东西，像增量更新优化（delta-state based optimizations）和基于操作的CRDT （operation-based CRDTs）等，我们并不打算在这里介绍——只是不想把这篇博客写成一本书——但是我希望能在接下来的系列中继续。

	[[Category:CRDT]]		[[Category:CRDT]]

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:57:15Z

监视删除集合（Observed Remove Set）

←上一版本		2024年9月20日 (五) 03:57的版本
第337行：		第337行：
	<syntaxhighlight lang="fsharp">		<syntaxhighlight lang="fsharp">
	let value (add, rem) =		let value (add, rem) =
	rem \|> Map.fold(fun acc k vr ->		rem \|> Map.fold(fun acc k vr ->
	match Map.tryFind k acc with		match Map.tryFind k acc with
	\| Some va when VClock.compare va vr = Ord.Lt -> Map.remove k acc		\| Some va when VClock.compare va vr = Ord.Lt -> Map.remove k acc
	\| _ -> acc) add		\| _ -> acc) add
	</syntaxhighlight>		</syntaxhighlight>

第395行：		第395行：
	* 更高级的方式是使用[http://basho.com/posts/technical/vector-clocks-revisited-part-2-dotted-version-vectors/?ref=bartoszsypytkowski.com 点状向量]修改现有的实现		* 更高级的方式是使用[http://basho.com/posts/technical/vector-clocks-revisited-part-2-dotted-version-vectors/?ref=bartoszsypytkowski.com 点状向量]修改现有的实现

	~~这些我们聊待下次再表。~~		这些我们留待下次再说。

	== 接下来是什么？ ==		== 接下来是什么？ ==

	[[Category:CRDT]]		[[Category:CRDT]]

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:54:04Z

监视删除集合（Observed Remove Set）

←上一版本		2024年9月20日 (五) 03:54的版本
第348行：		第348行：
	<syntaxhighlight lang="fsharp">		<syntaxhighlight lang="fsharp">
	let add r e (add, rem) =		let add r e (add, rem) =
	// 译者注：		// 译者注：
	// Case 1: If e is found in the add map (Some v)		// Case 1: If e is found in the add map (Some v)
	// Case 2: If e is found in the rem map (Some v)		// Case 2: If e is found in the rem map (Some v)
	// Case 3: If e is not found in either map		// Case 3: If e is not found in either map
	match Map.tryFind e add, Map.tryFind e rem with		match Map.tryFind e add, Map.tryFind e rem with
	\| Some v, _ -> (Map.add e (VClock.inc r v) add, Map.remove e rem)		\| Some v, _ -> (Map.add e (VClock.inc r v) add, Map.remove e rem)
	\| _, Some v -> (Map.add e (VClock.inc r v) add, Map.remove e rem)		\| _, Some v -> (Map.add e (VClock.inc r v) add, Map.remove e rem)
	\| _, _ -> (Map.add e (VClock.inc r VClock.zero) add, rem)		\| _, _ -> (Map.add e (VClock.inc r VClock.zero) add, rem)

	let remove r e (add, rem) =		let remove r e (add, rem) =
	match Map.tryFind e add, Map.tryFind e rem with		match Map.tryFind e add, Map.tryFind e rem with
	\| Some v, _ -> (Map.remove e add, Map.add e (VClock.inc r v) rem)		\| Some v, _ -> (Map.remove e add, Map.add e (VClock.inc r v) rem)
	\| _, Some v -> (Map.remove e add, Map.add e (VClock.inc r v) rem)		\| _, Some v -> (Map.remove e add, Map.add e (VClock.inc r v) rem)
	\| _, _ -> (add, Map.add e (VClock.inc r VClock.zero) rem)		\| _, _ -> (add, Map.add e (VClock.inc r VClock.zero) rem)
	</syntaxhighlight>		</syntaxhighlight>

第369行：		第369行：
	从删除集合中，我们只需要把时间错小于或者等于添加集合中对应元素的值删掉。从而保持数据的精简。		从删除集合中，我们只需要把时间错小于或者等于添加集合中对应元素的值删掉。从而保持数据的精简。

	<syntaxhighlight lang="~~bash~~">		<syntaxhighlight lang="fsharp">
	let merge (add1, rem1) (add2, rem2) =		let merge (add1, rem1) (add2, rem2) =
	let mergeKeys a b =		let mergeKeys a b =
第388行：		第388行：
	(add, rem)		(add, rem)
	</syntaxhighlight>		</syntaxhighlight>

			你可以从这里看出，我们使用一个向量时钟（也是一个map）的map，
			它是一个次优的解决方案。有这些方法可以来改进：

			* 最简单的方式是使用L4Z或者GZip算法压缩二进制的ORSet负载
			* 更高级的方式是使用[http://basho.com/posts/technical/vector-clocks-revisited-part-2-dotted-version-vectors/?ref=bartoszsypytkowski.com 点状向量]修改现有的实现

			这些我们聊待下次再表。

	== 接下来是什么？ ==		== 接下来是什么？ ==

	[[Category:CRDT]]		[[Category:CRDT]]

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:47:50Z

监视删除集合（Observed Remove Set）

@@ 第365行： / 第365行： @@
 这里有一点需要指出，你可能已经注意到我们使用了Map.remove。在这个场景下是安全的，因为我们同时添加了值——时间戳的键值对到相反的map中，仍然将数据的信息保存在对象中。
 == 接下来是什么？ ==
 [[Category:CRDT]]

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:28:42Z

监视删除集合（Observed Remove Set）

←上一版本		2024年9月20日 (五) 03:28的版本
第348行：		第348行：
	<syntaxhighlight lang="fsharp">		<syntaxhighlight lang="fsharp">
	let add r e (add, rem) =		let add r e (add, rem) =
			// 译者注：
			// Case 1: If e is found in the add map (Some v)
			// Case 2: If e is found in the rem map (Some v)
			// Case 3: If e is not found in either map
	match Map.tryFind e add, Map.tryFind e rem with		match Map.tryFind e add, Map.tryFind e rem with
	\| Some v, _ -> (Map.add e (VClock.inc r v) add, Map.remove e rem)		\| Some v, _ -> (Map.add e (VClock.inc r v) add, Map.remove e rem)
第353行：		第357行：
	\| _, _ -> (Map.add e (VClock.inc r VClock.zero) add, rem)		\| _, _ -> (Map.add e (VClock.inc r VClock.zero) add, rem)

	let remove r e (add, rem) =		let remove r e (add, rem) =
	match Map.tryFind e add, Map.tryFind e rem with		match Map.tryFind e add, Map.tryFind e rem with
	\| Some v, _ -> (Map.remove e add, Map.add e (VClock.inc r v) rem)		\| Some v, _ -> (Map.remove e add, Map.add e (VClock.inc r v) rem)

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:19:39Z

监视删除集合（Observed Remove Set）

←上一版本		2024年9月20日 (五) 03:19的版本
第359行：		第359行：
	\| _, _ -> (add, Map.add e (VClock.inc r VClock.zero) rem)		\| _, _ -> (add, Map.add e (VClock.inc r VClock.zero) rem)
	</syntaxhighlight>		</syntaxhighlight>

			这里有一点需要指出，你可能已经注意到我们使用了Map.remove。在这个场景下是安全的，因为我们同时添加了值——时间戳的键值对到相反的map中，仍然将数据的信息保存在对象中。

	== 接下来是什么？ ==		== 接下来是什么？ ==

	[[Category:CRDT]]		[[Category:CRDT]]

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:12:55Z

监视删除集合（Observed Remove Set）

@@ 第341行： / 第341行： @@
              | Some va when VClock.compare va vr = Ord.Lt -> Map.remove k acc
              | _ -> acc) add
 </syntaxhighlight>

Riguz：/* 监视删除集合（Observed Remove Set） */

2024-09-20T03:09:09Z

监视删除集合（Observed Remove Set）

@@ 第331行： / 第331行： @@
      type ORSet<'a when 'a: comparison> = Map<'a, VTime> * Map<'a, VTime>
      let zero: ORSet<'a> = (Map.empty, Map.empty)
 </syntaxhighlight>

Riguz：/* （Observed Remove Set） */

2024-09-20T03:03:41Z

（Observed Remove Set）

@@ 第315行： / 第315行： @@
 * 虽然我们的确可以删除已经添加的元素，但如果我们尝试添加一个已经删除的元素是会出现问题。因为我们不具备任何从底层GSet中删除数据的语义，一旦删除之后，元素就永远呆在墓碑之下了。这将使得元素从最终结果中被删除。所以说大哥，没法重新添加元素哟。再次强调，我们需要额外的元数据来允许我们追溯因果关系从而决定发生的是添加还是删除操作。
-===（Observed Remove Set）===
+=== 监视删除集合（Observed Remove Set）===
 == 接下来是什么？ ==
 [[Category:CRDT]]

Riguz：/* 两阶段集合（2-Phase Set） */

2024-09-20T02:37:39Z

两阶段集合（2-Phase Set）

←上一版本		2024年9月20日 (五) 02:37的版本
第294行：		第294行：

	===两阶段集合（2-Phase Set）===		===两阶段集合（2-Phase Set）===
			接下来是两阶段集合。如同PNCounter的例子一样，
			我们可以把两个GSet简单结合起来——一个为添加元素，一个为删除元素（通常会叫做墓碑tombstone）。
			添加/删除元素和merge操作也跟PNCounter/GCounter十分像。

			<syntaxhighlight lang="fsharp">
			module PSet =
			type PSet<'a when 'a: comparison> = GSet.GSet<'a> * GSet.GSet<'a>
			let zero: PSet<'a> = (GSet.zero, GSet.zero)
			// (add, rem) is a single PSet instance
			let value (add, rem) = add - rem
			let add v (add, rem) = (GSet.add v add, rem)
			let rem v (add, rem) = (add, GSet.add v rem)
			let merge (add1, rem1) (add2, rem2) =
			(GSet.merge add1 add2, GSet.merge rem1 rem2)
			</syntaxhighlight>

			上述的实现存在几个问题：

			* 墓碑机制（逻辑删除）的一个常见情况是删除的集合事实上会无限增长下去，因此为了保持数据一致性最终的值仅只占用实际元数据一部分的大小。也有另外的算法——墓碑清理（tombstone pruning）——来缓解这一问题
			* 虽然我们的确可以删除已经添加的元素，但如果我们尝试添加一个已经删除的元素是会出现问题。因为我们不具备任何从底层GSet中删除数据的语义，一旦删除之后，元素就永远呆在墓碑之下了。这将使得元素从最终结果中被删除。所以说大哥，没法重新添加元素哟。再次强调，我们需要额外的元数据来允许我们追溯因果关系从而决定发生的是添加还是删除操作。

	===（Observed Remove Set）===		===（Observed Remove Set）===

An introduction to state-based CRDTs - 版本历史

Riguz：​/* 接下来是什么？ */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* 监视删除集合（Observed Remove Set） */

Riguz：​/* （Observed Remove Set） */

Riguz：​/* 两阶段集合（2-Phase Set） */

Riguz：/* 接下来是什么？ */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* 监视删除集合（Observed Remove Set） */

Riguz：/* （Observed Remove Set） */

Riguz：/* 两阶段集合（2-Phase Set） */