Gossip Gloomers: Sequential Consistency semantics of SeqKV store

1

In the exercise Challenge #4: Grow-Only Counter · Fly Docs, it’s not clear if Maelstrom’s seqkv store is “sequentially consistent” at a global level (treating KV store as a black box) or at an individual KV replica level.

I’ve followed a naïve implementation for the read operation to just do a KV.Read(). The evaluation which performs 3 concurrent read operations (I think the logs below indicate no causality?) Naturally
these reads see different results:

12:01:32,141] jepsen worker 0 - jepsen.util 0  :ok     :read   1211
12:01:32,147] jepsen worker 0 - jepsen.util 0  :invoke :read   nil
12:01:32,147] jepsen worker 0 - jepsen.util 0  :ok     :read   1211
12:01:32,149] jepsen worker 1 - jepsen.util 1  :invoke :read   nil
12:01:32,149] jepsen worker 1 - jepsen.util 1  :ok     :read   1212
12:01:32,150] jepsen worker nemesis - jepsen.util :nemesis     :info   :stop-partition nil
12:01:32,150] jepsen worker nemesis - jepsen.util :nemesis     :info   :stop-partition :network-healed
12:01:32,150] jepsen worker nemesis - jepsen.generator.interpreter Waiting for recovery...
12:01:42,152] jepsen worker 0 - jepsen.util 0  :invoke :read   nil
12:01:42,153] jepsen worker 2 - jepsen.util 2  :invoke :read   nil
12:01:42,153] jepsen worker 1 - jepsen.util 1  :invoke :read   nil
12:01:42,153] jepsen worker 0 - jepsen.util 0  :ok     :read   1211
12:01:42,154] jepsen worker 1 - jepsen.util 1  :ok     :read   1212
12:01:42,154] jepsen worker 2 - jepsen.util 2  :ok     :read   1211

and therefore the validation fails:

        ...
        :final-reads (1211 1212 1211),
        :acceptable ([1212 1212])},

But I’m not sure if this evaluation checks sequential consistency of the g-counter reads because the reads are not made sequentially by the test? If they were made sequentially, I expect them to be also sequentially increasing over time as the reads delegate directly to KV.Read().

So maybe it’s not fully defined what “sequentially consistent” means the seqkv store, or maybe I’m getting something wrong.

I’ve found a solution that works but it relies on each read doing a KV.CompareAndSwap(k,v,v) which I assume needs to do a quorum write and is much slower (it also gets ensures stronger consistency guarantees than we need).

2

I think I got my answer from this section of Maelstrom’s Services docs. (The linked g-workload docs make no reference to it.)

I recommend linking to it, as it clearly spells out:

clients may interact with past states of the key-value store, provided that interaction does not violate these ordering constraints.

This explanation is what I was missing.

2 Likes
3

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.