crdts的python库(无冲突复制数据类型)
python3-crdt的Python项目详细描述
蟒蛇3 crdt
crdts的python库(无冲突复制数据类型)
安装
您可以直接从pypi获得库:
pipinstallpython3-crdt
用法
如果您已经安装了python3 crdt包,您可以立即开始使用crdts:
frompy3crdt.gsetimportGSetgset1=GSet(id=1)gset2=GSet(id=2)gset1.add('a')gset1.add('b')gset1.display()# ['a', 'b'] ----- Outputgset2.add('b')gset2.add('c')gset2.display()# ['b', 'c'] ----- Outputgset1.merge(gset2)gset1.display()# ['a', 'b', 'c'] ----- Outputgset2.merge(gset1)gset2.display()# ['a', 'b', 'c'] ----- Output
部署的CRDTS:-
- gcounter.gcounter
- pncounter.pncounter
- gset.gset
- twopset.twopset
- lww.lwwelementset
- orset
- 序列。序列
API
- add()
- 删除()
- 合并()
- display()
- query()
测试
使用以下命令测试软件包
python-munittesttests.test_<package_name>
CRDTS简介
什么是CRDTS?
crdts或无冲突复制数据类型是简化网络中多个设备之间数据复制的数据结构。任何更改/更新都在本地应用,然后传输到其他副本。每个副本将其本地副本与传入的更改/更新合并。合并过程中可能会出现不一致,但crdts从数学上保证,如果每个副本执行所有更改/更新,则副本最终会收敛。
CRDTs的类型
基于操作的CRDTS
在这些crdt中,更改/更新操作被传输到其他副本。每个复制副本接收操作并将操作应用于其本地状态。这些也被称为cmrdt(可交换复制数据类型),因为操作是可交换的,因此,发送操作的顺序无关紧要。最终得到的状态将是相同的。但是这些操作不是等幂的,因此,必须确保在传输过程中没有重复的操作。
基于状态的CRDTS
在这些crdts中,完整状态被传输到其他副本。副本接收状态并将其与本地状态合并。合并函数作为cmrdts是可交换的,但也是幂等的和关联的。这也被称为cvrdt(聚合复制数据类型),因为在每次传输中都会发生状态合并,最终导致所有副本聚合到同一状态。
三角洲CRDTS
在这些crdt中,只有最近应用的更改才会传输到其他副本,而不是完整状态。它只是一个优化的基于状态的crdt。
CMRDT和CVRDT之间的比较
cmrdts增加了传输机制的工作负载,但当事务数小于内部状态的大小时,它比cvrdts占用的带宽更少。但是,由于cvrdt merge函数是关联合并,因此状态会生成对该副本的所有先前更新,并且由于它是等幂的,因此可以多次传输状态,但会导致相同的状态。
在此库中部署的CRDTS
G计数器(仅增长计数器)
它实现了一个节点数组,其中数组的值用作计数器。array的值是数组中节点的值之和。为每个节点分配一个与数组中节点的索引等效的id。数组相当于一组节点。更新包括每个节点递增其在数组中的索引值。合并是通过取集群中每个节点值的最大值来实现的。包含比较函数以验证增量。根据比较函数应用每个更新函数,内部状态单调增加。
pn计数器(正负计数器)
此计数器支持递增和递减操作。它结合了两个G计数器,即"P"(用于递增)和"N"(用于递减)计数器。计数器的值是P计数器的值减去N计数器的值。合并包括单独合并P和N计数器。
G集(仅增长集)
这涉及到创建一组元素,其中元素只能添加一次,元素已添加,无法删除。合并返回两个G集的并集。
2P组(两相组)
它包括创建一个集合,可以在其中添加和删除元素。与pn计数器类似,它结合了两个g集,即"add"和"remove"集。对于添加/删除元素,将其插入"添加/删除"集合。如果元素在"add"集中,但不在"remove"集中,则它是集合的成员。查询函数返回元素是否是集合的成员。因此,如果删除了某个元素,查询将永远不会为该元素返回true,因此无法重新添加该元素。合并包括"添加/删除"集合的并集。
lww元素集(最后写入wins元素集)
类似于2P集合,除了每个元素都是用时间戳添加/删除的。如果元素在"add"集中而不是"remove"集中,或者它同时在"add"和"remove"集中,则"remove"集中的时间戳应小于"add"集中最新时间戳的时间戳。如果时间戳相等,则"bias"起作用,时间戳可以指向"add"或"remove"。在这个集合中,一个元素可以在被移除后重新插入,因此,它比2P集合具有优势。
或集合(观察到的移除集合)
类似于lww元素集,只是它使用唯一的标记而不是时间戳。对于每个元素,都会维护一个添加/删除标记的列表。通过将新生成的唯一标记添加到元素的"添加标记"列表中,可以添加元素。删除一个元素需要将其"添加标记"列表中的所有标记复制到其"删除标记"列表中。元素是集合的成员,如果"添加标记"列表中存在不在"删除标记"列表中的标记。
顺序crdts
它包含一个有序的集合、列表或元素序列。这个crdt可以建立在其他基于集合的crdt之上,通过对它们进行某种排序。 我们已经使用这个crdt构建了一个协作的代码/文本编辑器。