Invocation-Ordered Regular Sequential Serializability

Abstract

Strict Serializability is a consistency model that ensures a single global order for transactions that is consistent with real time. Regular Sequential Serializability (RSS) weakens this guarantee for read-only transactions, instead enforcing a causal constraint. This improves the tail latency of read-only transactions while rarely returning stale values in practice. However, RSS does not have any guarantee against network reordering. Under RSS, the order in which a client invokes its concurrent transactions is not necessarily reflected in the system responses. I introduce Invocation-Ordered Regular Sequential Serializability (IO-RSS), which is a new consistency model that provides observable invocation ordering in addition to the guarantees of RSS. Alongside this, I introduce IO-Spanner-RSS, the protocol that enforces IO-RSS. IO-Spanner-RSS has two variants, Die-Die (both lock holder and requester abort on contention) and OPST (Oldest Predecessor Start Time), which define different locking protocols for handling contention. The performance of IO-Spanner-RSS is measured against Spanner-RSS configured with manual invocation ordering as a baseline. In my evaluations, IO-Spanner-RSS consistently delivers higher throughput in low-to-medium contention settings, though it degrades significantly under extreme contention.