Optimization of the proposed protocol

[rickyyx]

Problem

Currently, the PNVM is almost 2x slower than the OCC version with moderate conflict (4 out of 8 transaction types are conflicting transactions)

Here is a footprint of the time spent at executing a transaction from profiling:

The bottlenecks are :

1. The lock guard on checking the current PieceStatus while spinning
2. The lock guard on executing the piece (before and after the piece runs)
3. Updating the TxnRegistry during commit()

Most of the things above can be supported by lock-free concurrency control.

   1 | register_txn: 0.242699ms
   2 | execute_txn: 2.831689ms
   3   | can_run: 0.1044ms
   4     | has conflict info: 0.0967ms
   5       | conflict with [TXN_0:Pid(0)]: 0.0108ms
   6       | conflict with [TXN_2:Pid(0)]: 0.0464ms
   7         | with instance [Tid(529)]: 0.02ms
   8         + 0.0264ms
   9       | conflict with [TXN_3:Pid(0)]: 0.0251ms
  10         | with instance [Tid(527)]: 0.0153ms
  11         + 0.0098ms
  12       + 0.014399994ms
  13     + 0.0077000037ms
  14   | execute_piece: 0.031ms
  15     | piece.run: 0.0042ms
  16     + 0.0268ms
  17   | can_run: 0.0793ms
  18     | has conflict info: 0.0739ms
  19       | conflict with [TXN_0:Pid(1)]: 0.008ms
  20       | conflict with [TXN_2:Pid(1)]: 0.0333ms
  21         | with instance [Tid(529)]: 0.0244ms
  22         + 0.008900002ms
  23       | conflict with [TXN_3:Pid(1)]: 0.0238ms
  24         | with instance [Tid(527)]: 0.0106ms
  25         + 0.013200001ms
  26       + 0.008799996ms
  27     + 0.005400002ms
  28   | execute_piece: 0.025399ms
  29     | piece.run: 0.0018ms
  30     + 0.023598999ms
  31   | can_run: 0.879797ms
  32     | has conflict info: 0.874897ms
  33       | conflict with [TXN_0:Pid(2)]: 0.0503ms
  34         | with instance [Tid(538)]: 0.0208ms
  35         + 0.029499998ms
  36       | conflict with [TXN_2:Pid(2)]: 0.0572ms
  37         | with instance [Tid(529)]: 0.015ms
  38         + 0.0422ms
  39       | conflict with [TXN_3:Pid(2)]: 0.0393ms
  40         | with instance [Tid(540)]: 0.0292ms
  41         + 0.010099998ms
  42       + 0.72809696ms
  43     + 0.0048999786ms
  44   | execute_piece: 0.0163ms
  45     | piece.run: 0.0029ms
  46     + 0.0134000005ms
  47   | can_run: 0.088399ms
  48     | has conflict info: 0.083499ms
  49       | conflict with [TXN_0:Pid(3)]: 0.0218ms
  50         | with instance [Tid(538)]: 0.0113ms
  51         + 0.0105ms
  52       | conflict with [TXN_2:Pid(3)]: 0.020499ms
  53         | with instance [Tid(529)]: 0.011699ms
  54         + 0.0088ms
  55       | conflict with [TXN_3:Pid(3)]: 0.0199ms
  56         | with instance [Tid(540)]: 0.0112ms
  57         + 0.0087ms
  58       + 0.021299997ms
  59     + 0.004900001ms
  60   | can_run: 0.0023ms
  61   | execute_piece: 0.0092ms
  62     | piece.run: 0.0012ms
  63     + 0.008ms
  64     ....
  65     ....
  66   | wait_for_dep: 1.127995ms
  67   | commit: 0.0606ms
  68   + 0.041000526ms

Solution

crossbeam will be the library to use to support lock-free concurrency control. (It leverages on epoch memory deallocation)

For example, each TxnInfo can be a HashMap of <Pid, ArcCell<PieceState>>, and the writer will not be blocked by readers, and it will update the PieceState immediately (atomically), and readers afterwards will get to the updated version, while the old copy will be GCed after the last reader exits.

[rickyyx]

Potential race condition at can_run

Need to check again before executing. Use something like compare_and_swap for the final switch.

Or an alternative to detect conflicts can be:

• Mark each conflict segment(T1.P1 -- T2.P2 -- T3.P1) as a group
• At any point of time, only one of them can be running - guarded by an atomic flag
• Use this to ensure mutual exclusion
• (However, this is not enough for tracking dependencies 😢, dependency tracking requires knowing states of the conflicting pieces)

[rickyyx]

Current Comparison with OCC (Non-persistence)

   4         #Conflict Txns  |  #Threads   |  #Txns/Second(Per thread) |  mSecond/Txn   | Retries/Txn
   5         -------------------------------------------------------------------------------------
   6 OCC         0                4              2000(500)                 ~2.35             0
   7 OCC         0               16              8000(500)                 ~2.40             0
   8 OCC         0               32              10,667(334)               ~3.29             0
   9 OCC         0               64              9142(142)                 ~3.40             0
  10
  11
  12 PNVM        0               4               2000(500)                 ~2.18             0
  13 PNVM        0               16              8000(500)                 ~2.40             0
  14 PNVM        0               32              10,677(334)               ~3.30             0
  15 PNVM        0               64              10,677(166)               ~3.30             0
  16
  17
  18
  19 PNVM        8               32               8000                     ~3.00 - ~3.95     0
  20 OCC         8               32               10667                    ~3.30             1000