这篇论文来自NSDI 2019，作者是来自斯坦福的博士生Seo Jin Park和John Ousterhout教授，John Ousterhout教授也是raft算法的作者。论文提出了一种无序复制算法，将基于Primary-Backup的复制时延降低到了1个RTT。
如图，在没有复制的系统中，客户端向服务器发起一个写操作（x=1)，服务器接收到客户端请求后，将x=1写入到存储中并返回一个ok回复，这个过程耗时1个RTT。
但是在分布式系统中,数据存储通常有多个备份。如果继续使用之前的复制方法，就会导致节点数据的顺序不一致（由于网络等原因，客户端请求到达的顺序发生变化）。因此，为了多节点数据的一致性，大部分分布式系统采用了Primary-Backup模型。
如图，客户端发送一个写操作（x=1）到Primary节点，Primary节点先将x=1写到本地，然后将其同步到所有的Backup节点。当所有Backup节点成功保存数据后，Primary节点返回ok给客户端。这样一个过程耗时2个RTT。
CURP的大致结构如图：
CURP引入了witness节点，client不仅需要发送request到主服务器同时也需要发送到所有的witness节点，witness中的记录是无序的。主服务器在接受到request后，将数据写到本地后立即返回OK无需等待同步到Backups。当客户端收到primary和所有witness的OK回复后，写操作完成，client确认这个操作已经持久化，这个过程耗时1个RTT。
这个过程中如果witness拒绝了client的请求，此时witness需要向primary发送同步请求并等待primary把所有数据同步到backups后返回OK，才能确认数据完成持久化。这个过程大部分情况下耗时2个RTT（client发送同步请求时primary已经同步完成）,最坏情况下耗时3个RTT。
witness接收到request时需要对其进行交换性（commutativity)检查。如图中所示，z <- 7和y <- 5这两个记录就是可交换的，不论以什么顺序执行，不影响最后的结果。但是z < -7和z <- 2就不满足交换性，这两条记录必须严格按client发起的顺序执行。witness如果检查到request不满足交换性就会拒绝这个请求。
CURP分两个阶段恢复。第一步从Backup里恢复，第二步从Witness里回复。首先新Primay从一个Backup里恢复数据，然后选择一个可用的witness，要求它停止接受更多的operation。新primary在检查了witness中的所有记录都满足可交换性后，进行恢复。通过这两步，新Primary节点恢复看所有的数据。replay过程有3个潜在的问题：
第一，从witness中恢复的数据是乱序的。由于witness中的数据满足交换性，所以无论以何种顺序执行，都不影响最终的结果。
第二，operation的重复执行。primary节点将operation同步到Backups后，会向witness发送垃圾回收请求，witness中已经完成同步的op就会被垃圾回收。如果Primary节点在发送垃圾回收请求前宕机，此时witness和Backup中就会存在两条相同的op。如图所示，这时从witness中恢复的op就会覆盖掉Backup中的op，破坏了数据的一致性。作者使用了自己发表在SOSP 15的一篇论文《Implementing linearizability at large scale and low latency》中的方案解决了这个问题。
第三，Primaries May Reveal Not-yet-durable Data。如图所示，首先client A发送一个 x <- 3操作，几乎同时client B来读取x的值，此时x并没有被同步到Backup中。x <- 3此时可能没有被记录到witness中。primary返回x=3给client B后宕机了，这个时候新primary恢复数据后，x<-3就没了。在Client B看来，数据的一致性遭到了破坏。因此，在CURP中，如果client的op基于primary中未同步的op，此时client必须等待同步完成。
以上就是CURP的大致实现，更多的细节如垃圾回收、数据迁移, backup crash, witness crash等，请看论文。