CMU15445_24_lab0

Author Avatar
Gaoustcer 3月 07, 2024

CMU15445 lab1

word

  1. draft 起草
  2. harmonious 和谐
  3. commutative 可交换的
  4. associative 联想性的
  5. idempotent 幂等的
  6. reconcile 和解，调和
  7. specification 规格，规范，说明书
  8. replica 副本
  9. omnipresent 无所不在的
  10. mock 嘲弄，模拟的

Or-set

多用户同时对文档进行编辑，即使两个用户同时对一段文本采取不同的编辑方式，也需要保证所有用户看到的内容是一样的，CRDT是一种可以在多个分布式节点上复制的数据结构，保证数据的一致性。

例子（CRDT）

如何不加锁的情况下统计一件事发生的次数

每个副本保存自己调用接口的计数器，发生次数=所有副本计数器之和，更新自己计数器无需加锁

Grow only set：只能向集合中添加元素（日志）

每个副本向自己的集合中添加元素，对所有集合取并集

Orset

实现Observed Remove Set，这是一种Conflict-free replicated data type。这种数据结构允许分布式系统之多个节点在同时操作的同时无需实时同步，当所有操作都被执行后，最终系统状态收敛于确定状态。

Orset在Grow only set中考虑到从集合中删除一个元素的remove操作，这个算法维护两个集合E/T，前者用于保存加入元素（用户可见），后者用于保存删除元素

添加元素时需要生成一个独一无二的tag n，将其和元素e一齐加到集合中，

image-20240228174730476

删除元素时需要将删除的pair $(e,n)$加入到T中

image-20240228180047382

合并副本A到副本B，首先检查A中是否有元素存在于B的Tombstone set T中（对B也进行相似操作），删除这些元素后再和B中元素合并，需要实现的接口包括

  1. 查找元素是否在set中（查找每个E并过滤掉每个T） Contains(elem)
  2. 将元素加入到set中 Add(elem,uid)，uid时生成的unique id
  3. 删除元素 Remove(elem)
  4. 合并集合 Merge(set)
  5. 返回集合中所有元素 Elements()，集合中元素存在当且仅当再add set并且不再tombstone set中

为什么要同时维护对应的unique id

删除操作仅限于副本能看到的元素删除操作仅限于副本能看到的元素看到的元素**，例如两个节点A/B，节点A删除了一个节点B插入，但是对于A不可见的元素，则A的删除操作无效，后续B插入并不会受到影响

本质上是一个弱一致性模型，毋须满足任何时候状态都相同

Practical Demystification of CRDT

  1. 解决分布式节点如何在掉线后进行同步，或者因为连接不稳定导致无法实时同步的情况
  2. R: Replicated
  3. C: Conflict Free 自动解决不同副本不一致导致的冲突(Merge)
    1. 需要Merge操作 1）可交换 2）可结合 3）幂等 $x\cdot x = x$
    2. Merge操作的结果收敛于唯一值
  4. 操作
    1. 修改局部保存的数据
    2. merge修改后的数据
    3. converge所有终端的数据

Last Write Win

考虑修改一个变量的情况，现在用户需要记录某个偏好（例如喜欢去的地方），在不同设备上记录了不同的偏好，Last Write Win要求同时保存记录的Wall Time，同步时选择最近的Wall Time记录作为最终的结果

  1. 不能按照发送时间作为判断标准，因为需要考虑设备离线的情况，早的记录可能在较晚时间通过网络发出
  2. 相同Wall Time本身需要强同步。。

以上方法将会导致stale update的问题，即服务器不能判断哪个更新是更新的

2-Phase Set

允许加入/删除元素

  1. 节点A：加入cat/dog，删除ape
  2. 节点B：加入cat/ape

算法

  1. 查找：要求在Addset不在Removeset中
  2. 合并：合并两个集合的Addset和Removalset

这样导致不能重复加入被删除的元素，以及无法直接对集合中的元素进行更新（导致remove set增长迅速）

Solution 1：保存/删除元素时同时保存timestamp，同样维护两个G-set用于加入和删除元素

重新加入删除的元素时比较加入/删除操作的timestamp以保留较新的操作

Or-set

解决在Set中修改元素，引入unique tag标记插入/删除操作

  1. 节点A Add \{(#a,”cat”),(#b,”dog”)\} Rem \{(#a,”cat”\}
  2. 节点B Add \{(#c,”cat”),(#d,”ape”)\} Rem \{(#a,”cat”\}

得到的集合为

  1. Add \{(#a,”cat”),(#b,”dog”),(#c,”cat”),(#d,”ape”)\}
  2. Rem \{(#a,”cat”)\}

为什么要保存特定的identifier？这是为了保证re-add after delete，每次加入时都会添加一个全局唯一的identifier，如果最后的集合写成

Add{(#b,"dog")} Rem{("#a","dog")}这意味dog被re-add after delete，这样也导致删除操作不能删除其它节点添加但是本地并不存在的元素

本站访客数人次