如何修改多值寄存器CRDT（MVR-CRDT）实现中的merge()方法？

问题概述 #

在MVR-CRDT的简易实现中，merge()方法未能将所有非null值合并到目标副本。预期通过遍历两个ArrayList，在非null索引处比较向量时钟，用时钟值更高的覆盖对应索引值，但实际合并后目标副本未更新。

实现代码 #

import java.util.ArrayList;
import java.util.Collections;

public class MVR_CRDT{

    //variables
    static int size;
    private ArrayList<Integer> vectorClock;
    private ArrayList<Object> values;
    
    //constructor
    public MVR_CRDT(int size) {
        this.vectorClock = new ArrayList<Integer>(Collections.nCopies(size, 0));
        this.values = new ArrayList<Object>(Collections.nCopies(size, null));
    }    
    
    //sets a value and increments its corresponding vector clock
    public void setValue(int index, Object value) {
        //check if value is different
        if (value != this.values.get(index)){
            this.vectorClock.set(index, this.vectorClock.get(index) + 1);
            this.values.set(index, value);
            //goes over the other indexes and empties their value
            for (int i = 0; i < size; i++) {
                while (i != index){
                    this.values.set(i, null);
                }
            }
        }
    }

    //the second replica merges into the first
    public static void merge(MVR_CRDT first, MVR_CRDT second){
            //loops through the ArrayList
            for (int i = 0; i < size; i++) {
                //if there is a value to be merged
                if (second.values.get(i) != null){
                    first.vectorClock.set(i, max(first.vectorClock.get(i), second.vectorClock.get(i)));
                    first.values.set(i, second.values.get(i));
                }
            }
    }
    
    private static Integer max(Integer integer, Integer integer2) {
        return null;
    }

    //gets the value at index position of a replica
    public Object getValue(int index) {
        return this.values.get(index);
    }

    public Integer getVector(int index) {
        return this.vectorClock.get(index);
    }

    //prints the replica
    public void query() {
        System.out.println("Vector Clock: " + this.vectorClock.toString());
        System.out.println("Values: " + this.values.toString() + "\n");
    }

    public static void main(String[] args) {
        MVR_CRDT Alice = new MVR_CRDT(3);
        MVR_CRDT Bob = new MVR_CRDT(3);
        MVR_CRDT Charlie = new MVR_CRDT(3);

        Alice.setValue(0, "Hello");
        Alice.setValue(0, "Hello"); //to show that Alices counter does not increase
        System.out.println("Alice's replica: ");
        Alice.query();

        Bob.setValue(1, 12312);
        System.out.println("Bob's replica: ");
        Bob.query();

        // Charlie.setValue(2, false);

        merge(Alice, Bob);
        System.out.println("Alice's replica after merging: ");
        Alice.query();

        // System.out.println(Bob.getValue(1) + " , " + Bob.getVector(1));

    }

}

预期与实际输出 #

预期合并后输出 #

Vector Clock: [1, 1, 0] Values: [Hello, 12312, null]

实际输出 #

Alice's replica: 
Vector Clock: [1, 0, 0]
Values: [Hello, null, null]

Bob's replica:
Vector Clock: [0, 1, 0]
Values: [null, 12312, null]

Alice's replica after merging:
Vector Clock: [1, 0, 0]
Values: [Hello, null, null]

问题分析与修复 #

1. static变量size未初始化 #

size被定义为static变量，但构造函数中并未对其赋值，导致merge()方法中的循环条件i < size始终为false（默认值0），循环根本不会执行。

修复方式：将size改为实例变量，避免static带来的多实例冲突问题：

private int size; // 替换static int size;

// 构造函数中初始化
public MVR_CRDT(int size) {
    this.size = size; // 添加这行
    this.vectorClock = new ArrayList<Integer>(Collections.nCopies(size, 0));
    this.values = new ArrayList<Object>(Collections.nCopies(size, null));
}

// 修改merge方法，从实例获取size
public static void merge(MVR_CRDT first, MVR_CRDT second){
    // 用first的size，确保两个实例size一致
    int size = first.size;
    for (int i = 0; i < size; i++) {
        // ... 原有逻辑
    }
}

2. max()方法逻辑错误 #

max()方法直接返回null，导致合并时向量时钟被设置为null，不仅逻辑错误，还会引发潜在的空指针异常。

修复方式：实现正确的最大值获取逻辑：

private static Integer max(Integer integer, Integer integer2) {
    return Math.max(integer, integer2);
}

3. setValue()方法中的死循环与错误逻辑 #

setValue()里的while (i != index)是死循环，当i不等于index时会无限执行this.values.set(i, null)；同时MVR-CRDT的设计允许多个索引持有值，不需要清空其他索引的内容。

修复方式：移除错误的循环代码：

public void setValue(int index, Object value) {
    if (value != this.values.get(index)){
        this.vectorClock.set(index, this.vectorClock.get(index) + 1);
        this.values.set(index, value);
        // 移除下面的错误循环代码
        // for (int i = 0; i < size; i++) {
        //     while (i != index){
        //         this.values.set(i, null);
        //     }
        // }
    }
}

修复后测试结果 #

合并后Alice的副本输出与预期一致：

Alice's replica after merging: 
Vector Clock: [1, 1, 0]
Values: [Hello, 12312, null]

内容的提问来源于stack exchange，提问作者rinbeq