Namaran

Code daily. Without assist.

2026-09-26

lww_register.cpp

#include <iostream>
#include <string>
#include <tuple>

struct Reg {
    long ts;
    std::string node;
    std::string value;
};

Reg merge(const Reg& a, const Reg& b) {
    return std::tie(a.ts, a.node) < std::tie(b.ts, b.node) ? b : a;
}

int main() {
    const Reg x{5, "node-10", "red"};
    const Reg y{5, "node-9", "blue"};
    const Reg z{4, "node-99", "green"};
    std::cout << merge(merge(x, y), z).value << ' '
              << merge(z, merge(y, x)).value << '\n';
}

これは何を出力するでしょうか?

Answer

blue blue と出力されます。

merge は (ts, node) の組を std::tie で作って比べ、大きい方の書き込みを残します。タプルの < は辞書順なので、先頭の ts で決まればそこで終わり、ts が等しいときだけ node を比べます。z は ts が 4 なので、node がどれほど大きくても、ts が 5 の x と y には勝てません。

x と y はどちらも ts が 5 で、勝負は "node-10" と "node-9" の比較に持ち越されます。std::string の比較は数の大小ではなく1文字ずつの辞書順なので、6文字目の '1' と '9' で決まり、"node-10" の方が小さくなります。残るのは y の blue です。

2つの式は、統合の順序も引数の順序も違うのに、どちらも blue になります。merge が可換で結合的なので、各レプリカが他の書き込みをどの順で受け取っても同じ値に収束するからです。同着を node で決めているのはこの性質を守るためで、ts だけを比べて等しければ a を返すようにすると、merge(x, y) は red、merge(y, x) は blue になり、レプリカ同士で値が食い違ったままになります。ノード名に数字を含めるなら、桁をそろえるか数値で持たないと、人が思う大小と比較の結果がずれます。