Re: Need help to review a serializability implementation for MySQL Cluster

[Alex Ou]

The section 'Generic generalization of Serializable Snapshot Isolation to a distributed database system' is up.

This section paves the way of generalizing Serializable Snapshot Isolation to a distributed database system that can take advantage of type D of the Serializability Theorem. Then a technical path utilizing First-Committer-Wins rule is explored. Another technical path employing First-Updater-Wins rule need to be delayed until next section since it requires a field level capable locking system for type D of the Serializability Theorem to apply. The generalization is generic because of the following reasons: a generic 'Clock Condition' is explored so that various distributed clock algorithms satisfying it can be deployed for the underlying Snapshot Isolation; various ways of implementing the underlying Snapshot Isolation are demonstrated so that an implementer can choose from or be inspired; a flag system to eliminate 'dangerous structure's in Cahill's Serializable Snapshot Isolation algorithm is explored so that an implementer got another option other than the hybrid system deployed in PostgreSQL. A characteristic of this technical path is that it doesn't depend on a locking system.

In the case a field level capable locking system is available, besides the First-Updater-Wins rule technical path for Serializable Snapshot Isolation, we may also implement a pessimistic technology system and a hybrid system on top of it. If things are smooth, I will present all these in about 6 months. By then, we'll have four technical paths to achieve serializability in a distributed database system and I'll recommend them to relevant distributed database system implementers, hoping that they could implement at least one of them at 3rd-tier to give us more options at 2nd-tier.

But I don't know if or when this could happen. Even if it would, the serializability implementation I've developed for MySQL Cluster might still trump in performance for the following two reasons:

1. Most of these relevant distributed database system are disk-based, while MySQL Cluster is memory-based.
2. The serializability implementation I've developed for MySQL Cluster is based on a READ-COMMITTED isolation level, which in general allows more concurrency than those based on Snapshot Isolation, like Serializable Snapshot Isolation.

So it looks like we need to hang in to 2nd-tier solutions for at least a while. To make this hang-in easier, I will review TiDB and mount a serializability implementation on their READ-COMMITTED isolation level in a few weeks. I will also provide more details on mounting such an implementation on MySQL InnoDB's READ-COMMITTED isolation level, hoping these trio will sail us through before dawn.

After I finish the major parts of this work, I will also provide better software so that this work is more accessible to 2nd-tier developers.