Subject: [GSOC][weekly report 4] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions

From: "Mengxing Liu" <[email-masked]>
Date: Thu, 29 Jun 2017 11:36:34 +0800 (GMT+08:00)

In the last week:

I added a tpcb benchmark and refactored the test code. It likes a framework now. We can add other benchmarks easily if necessary. https://github.com/liumx10/pg-bench
Analyzed the code acquiring SerializableFinishedListLock and provided a new proposal to improve it. My proposal is as below. 
As I reported in previous emails, lots of backend were blocked by SerializableFinishedListLock in heavy contention. 
There are only three functions acquiring this lock:

SummarizeOldestCommittedSxact: After transforming the conflict information into SLRU format, we need to release this SerailizableXact object. The lock protects the release operation and removing it from the finished list.
ReleasePredicateLocks: After releasing the predicate locks of the current transaction, if the transaction is rolled back, we need to release the SerializableXact object; if the transaction is committed, we should insert it to the finished list. The lock protects the release operation or insert operation.
ClearOldPredicateLocks: Look through the finished transaction list to find if any transaction object can be released. Thus the lock protects looking through the list, releasing transaction objects, and removing objects from the list.
As we can see, the lock protects two things: 1) the finished transaction list  2) releasing serializable transaction objects. 
Using a single global lock to protect all will cause a lot of contentions. 
So I decoupled the lock's duty into two parts: protecting the finished transaction list and 
protecting releasing a single serializable transaction objects.

The SerializableFinishedListLock is reserved to protect the finished transaction list. 
Thus the function SummarizeOldestCommittedSxact and ReleasePredicateLocks are not changed.
For function ClearOldPredicateLocks, I scan the list and pick up the transactions which could be released first,
but not release these objects directly. After releasing the SerializableFinishedListLock, invoking
 ReleaseOneSerializableXact to release them.

At first, I want to use a partition lock or spinlock in each SerailizableXact object to protect ReleaseOneSerializableXact.
But I found it is not necessary to add new locks. in ReleaseOneSerializableXact, firstly, it released all predicate locks, 
which is protected by SerializablePredicateLockListLock; Then, it released all conflicts, which is protected by SerializableXactHashLock.
So I didn't change the function ReleaseOneSerializableXact. 

I have implemented this idea. But unfortunately, it didn't improve the performance or reduce the contention on SerializableFinishedListLock. 
I'll try to find out why in the next days.
But I'm really looking forward to your advice for my proposal. We can't be too careful to modify the code related to locks. 

--

Sincerely

Mengxing Liu