To provide strict serializable isolation among transactions, PostgreSQL needs to track read-write conflicts (rw-conflicts for short in the following context) executed concurrently at runtime. PostgreSQL uses a double-linked list in the shared memory to record all conflicts of each transaction. Based on the list structure, the rw-conflict tracking has a time complexity of O(N^2). The designer assumed that the list is short so that the overhead can be ignored. However, some benchmarks reported that the conflict-tracking took up to half the CPU time at high concurrency levels, where searching the list becomes a bottleneck. There are five static functions existing in the project to manage the rw-conflicts. We intend to rewrite these functions by replacing linked list with other data structures to support faster search. There are two possible replacements. Hash table is the first choice because there is an existing implementation of hash table (HTAB) in shared memory in PostgreSQL. Skip list is the other choice as it is similar to the linked list.



Mengxing Liu


  • alvherre
  • Kevin Grittner