Namaran

Code daily. Without assist.

2026-09-26

g_counter.cpp

#include <iostream>
#include <map>
#include <string>

using GCounter = std::map<std::string, int>;

void merge_into(GCounter& self, const GCounter& other) {
    for (const auto& [node, n] : other) {
        self[node] += n;
    }
}

int total(const GCounter& c) {
    int sum = 0;
    for (const auto& [node, n] : c) {
        sum += n;
    }
    return sum;
}

int main() {
    GCounter a{{"a", 2}};
    GCounter b{{"b", 3}};
    merge_into(a, b);
    merge_into(b, a);
    std::cout << total(a) << ' ' << total(b) << '\n';
}

GCounter は、レプリカごとに自分が数えた回数を持ち、その合計を全体の値とするカウンタで、merge_into は他のレプリカの状態を取り込むつもりの関数です。入力は main のとおりで、a が b の状態を取り込み、続いて b が a の状態を取り込んでから、両方の合計を表示します。いまの出力は 5 8 ですが、本来の出力は 5 5 です。どこを直せばよいでしょうか?

Answer

1回目の merge_into(a, b) では、a に "b" の項目がまだ無いので、self["b"] += 3 は 0 + 3 になり、ここまでは正しく見えます。壊れるのは2回目です。a はすでに b の 3 を含んでいて、b がそれを取り込むと、b 自身の 3 に同じ 3 が足されて "b" が 6 になります。b の合計は 2 + 6 で 8 です。

状態を丸ごと送り合う CRDT では、同じ情報が何度届くか、どの順で届くかを決められません。そのため統合は、同じ状態を何度取り込んでも結果が変わらず(冪等)、順序にも依存しない操作である必要があり、足し算はこの条件を満たしません。各項目を増やすのはそのレプリカ自身だけで、値が減ることもないので、2つの状態で値が違えば大きい方が新しい情報です。取り込みは大きい方を取れば足ります:

        self[node] = std::max(self[node], n);

std::max は同じ値を何度渡しても結果が変わらず、引数の順序にも依存しないので、b が自分の 3 を送り返されても 3 のままです(std::max のために <algorithm> のインクルードも足します)。self[node] は項目が無ければ 0 で作るので、初めて見るレプリカの値もそのまま入ります。1回ずつの取り込みだけを見るテストでは += も正しい値を返すので、送り返しや再送が起きて初めて数が合わなくなります。