CSE_lecture8:Consistency

Consistency when executing operations concurrently

implement ChatAPP

最简单的方法就是使用一个中心化的服务器，但实际上使用的很少，原因为：

• 每次post都要网络通信，都要等待response
• 每次read都要等待RPC
• 断网时无法访问
• 服务器挂了就无法处理了

因此系统是需要备份的，不仅备份在server上，也要备份在各个设备上(replicated list)

最方便的方法在于只更新本地数据，但这样不能实现备份间的同步

如果向所有备份同步，会导致低性能，同时当部分server挂了时就同步不了

一个常用的方法是只同步在一部分server上，这样可以离线读取聊天记录，但反映不了聊天记录的全貌。因此需要定期同步数据，或者被动接收同步数据

现在的挑战在于：

• 不能同步所有的服务器
• 同步的内容为操作而非数据，因为无法区分哪些数据是正确的
• 采用过滤后追加的方法更新本地数据

这样又带来一个问题，即不同人看到的聊天记录是不一致的

consistency model定义了乱序现象会不会出现，有强弱之分，依情况选择合适的模型

eventual consistency

我们的目标有：

• 一旦能联网就能通信
• 打开微信不一定需要看到最新的消息，可以容忍一定的延迟，但要保证最终消息顺序是一样的

eventual consistency的读写都是只向任意一台服务器发起的，定期进行同步操作即可，即只保证最终一致性（或本地副本读取，写的时候还需要广播）

eventual consistency可能出现一段时间数据不一致现象，但能保证最终数据是一致的，要求为：一旦服务器收到的消息一致，那么给用户呈现的消息也应当一致，即需要保证确定的顺序

将收到的消息缓存在log中，再按照相同的规则进行排序，最后将排序好的聊天记录覆写过去

问题在于怎么实现排序，需要一个total order的timestamp：

• 直接使用系统时间排序，但不同机器可能出现时钟相等的问题，因此不能使用
• 使用<time T, node ID>

但由于不同设备之间的时钟可能不一致，仍然可能出现被引用内容排在引用后面的情况

定义casual relationship X -> Y如下：

• 同一台机器中X发生在Y之前
• 不同机器上，X导致了Y的发生，如Y引用了X
• 存在传递性

故解决方法为lamport clock，即按照casual relationship排序，算法为：

• 每个server维护一个自己的时钟
• 时钟每隔一定时间加一
• 收到其他server（时间戳为T’）的消息时，将自己的时间戳更新为 T = Max(T, T’ + 1)

假设TS(event #1) < TS(event #2)，且在不同node上能否说明以下几点：

• event #1发生的物理时间早于event #2？不一定，可能发生时没有通信
• node #1和node #2通信？不一定，可能初始时node #1时间远小于node #2
• event #1同步到了node #2，event #1发生的比event #2早？还是不一定

但这并不能解决引用内容不存在的问题，因为还是只保证了最终一致性，本地可能在中途没有同步到被引用内容

eventual consistency不能支持所有场景，比如接龙，如果两个用户没有通信，可能就会乱序。解决方法为：

• 如果没有明确的casual relationship，应当回退
• 使用更强的一致性模型

因此应当增加partial order，即存在不能排序的情况。因此使用vector clock，只有每一项都比另一个大时才能排序。实现方法为向量包含本地的lamport clock和它观测到的其他server的lamport clock，未通信时只增加自己的lamport clock；同步时保证每一项都有T = Max(T, T’ + 1)

当出现不能排序的情况时，由应用自己决定怎么解决，这也是缺点之一

strong consistency model

另一个方法是使用更强的一致性模型，此时能保证大家看到的都是一个确定的顺序，而不同强一致性模型的区别就是按照什么顺序

strict consistency严格按照issue time，即操作的发起时间。使用中心化服务器的挑战在于网络延迟：

• 这不能使用本地时间解决
• 等待前面的请求都到了为止，问题在于延迟很久，同时不知道有多少消息要等待

因此strict consistency难以实现

linearizability consistency 按照中心化的服务器排序，收到请求就执行，按照completion-to-issue排序，即才发起的操作排在已经做完的操作后面，并发时可以随意排序，但这不影响不同设备之间的一致性

当出现备份服务器时，linearizability也可以实现，原则为primary-backup model：仅由primary来决定顺序，因此也只能在primary上进行读写，再广播到其他备份上。当primary挂了之后，可以临时启用backup

primary-backup在write时步骤为：

• 先广播到所有backup
• 再本地写
• 返回

这需要保证primary和backup的顺序一致，但网络可能导致乱序，因此需要维护一个全局的seq number

允许read发生在write forward之前，这样虽然读取不到最新的write，但顺序是没有乱的，这样保证了高性能

primary-backup的缺点为性能远不及eventual consistency，同时容错性维护很复杂（如出现多台primary）

sequential consistency进一步优化，即可以在backup上read，下面例子的最后两次read违反了completion-to-issue，即pre-process issuing/completion order

eventual和linearizability比较：

使用哪种模型应当由具体场景决定