Validate Session ConsistencymediumValidate Session Consistency
Replicated systems can provide consistency guarantees for one client session without imposing a single global order on every client. Two useful guarantees are:
- Read-your-writes: after the session writes a version, it must not later read an older version of that key.
- Monotonic reads: after the session reads a version, later reads of that key must not move backward.
Design a SessionConsistencyChecker class:
SessionConsistencyChecker()creates a stateless checker.boolean isConsistent(int[][] operations)returns whether the chronological history satisfies both session guarantees.
Every operation is [type, key, version]:
type = 0records a write ofversionforkey.type = 1records a read ofkeythat returnedversion.
Track the highest version the session has observed for each key across both reads and writes. A read is invalid when its version is lower than that key's current highest observed version. Equal or newer reads are valid. Writes do not make a history invalid, but a lower-version write must not lower the remembered high-water mark.
Each call describes a separate session history. State from one call must not affect another call on the same checker.
Example 1:
Input:
Output:
Explanation: The session writes version 5 of key 1 and then reads version 5. The read sees the session's own write, so the history is consistent.
Example 2:
Input:
Output:
Explanation: The first read raises key 1's high-water mark to 3, and the write raises it to 5. The final read returns version 4, which is older than the session's own version 5, so the history violates read-your-writes.
Constraints
0 <= operations.length <= 200operations[i].length == 3operations[i][0]is either0(write) or1(read).0 <= operations[i][1], operations[i][2] <= 10^9- Operations are listed in chronological order for one client session.
- For the same key, a larger version represents a newer value.
- At most
100calls are made toisConsistent.
| Call | Returns |
|---|---|
| new SessionConsistencyChecker() | null |
| isConsistent([[0,1,5],[1,1,5]]) | true |
The session writes version 5 of key 1 and then reads the same version, so read-your-writes is satisfied.
Run checks these cases. Submit also runs a larger hidden set.