0

我了解矢量时钟仅提供部分顺序。所以你不能直接对它们进行排序。出于这个原因，您对并发向量使用 tie-breaker，从而产生一个总顺序。

然而，对矢量时钟进行排序，以使结果列表中的每个原因都出现在结果列表中的每个结果之前似乎不起作用，我也不完全明白为什么。

我有大量的测试表明比较两个向量是有效的：

    @Override
    public int compareTo(VectorClock<K> that) {

        var res = 0;

        if (this.isAfter(that))
            res = 1;
        else if (that.isAfter(this))
            res = -1;
        else
            res = this.timestamp.compareTo(that.timestamp);

        System.out.println("compare " + this + " : " + that + " => " + res);

        return res;
    }

    public boolean isAfter(VectorClock<K> that) {
        boolean anyClockGreater = false;

        var set = new HashSet<K>();
        set.addAll(this.keySet());
        set.addAll(that.keySet());

        for (K key : set) {
            final Clock thatClock = that.get(key);
            final Clock thisClock = this.get(key);

            if (thisClock == null || thisClock.isBefore(thatClock)) {
                return false;
            } else if (thisClock.isAfter(thatClock)) {
                anyClockGreater = true;
            }
        }
        // there is at least one local timestamp greater or local vector clock has additional timestamps
        return anyClockGreater || that.entrySet().size() < entrySet().size();
    }

但是，当对向量时钟列表进行排序时，例如一个具有两个向量的向量时钟，该向量具有发生前的关系，而第三个向量与其他两个向量同时发生，可能会发生只有并发的一个向量与其他两个向量进行比较，以及依赖的向量互不相提并论。相反，他们的顺序是（错误地）由决胜局决定的：

VectorClock<String> v1 = VectorClock.fromString("{0=23, 1=28, 2=15, 3=23, 4=15, 5=22, 6=14, 7=19}"); // after v3
VectorClock<String> v2 = VectorClock.fromString("{0=11, 1=16, 2=28, 3=17, 4=24, 5=15, 6=10, 7=8}");
VectorClock<String> v3 = VectorClock.fromString("{0=15, 1=19, 2=15, 3=20, 4=15, 5=22, 6=14, 7=19}"); // before v1

var s = new ArrayList<>(List.of(v1, v2, v3));
s.sort(VectorClock::compareTo);
assertTrue(s.indexOf(v3) < s.indexOf(v1));

打印（并失败）：

compare {0=11, 1=16, 2=28, 3=17, 4=24, 5=15, 6=10, 7=8} : {0=23, 1=28, 2=15, 3=23, 4=15, 5=22, 6=14, 7=19} => 1
compare {0=15, 1=19, 2=15, 3=20, 4=15, 5=22, 6=14, 7=19} : {0=11, 1=16, 2=28, 3=17, 4=24, 5=15, 6=10, 7=8} => 1

造成这种情况的根本原因是什么？这通常是不可能的还是有错误？

4

0 回答 0